An agent-basedstochasticrulerapproachforastochasticknapsackproblemwith sequential competition

We examineasituationinwhichadecision-makerexecutesasequenceofresourceallocationdecisions over time,buttheavailabilityoftheindivisibleresourcesatfutureepochsisuncertainduetoactions of competitors.Wecastthisproblemasaspecializedtypeofstochasticknapsackprobleminwhichthe uncertainty ofitem(resource)availabilityisinducedbycompetitorsconcurrentlyfillingtheirownre- spective knapsacks.Utilizingamulti-periodboundedmultiple-choiceknapsackframework,weintroduce a generaldiscretestochasticoptimizationmodelthatallowsanonlinearobjectivefunction,cardinality constraints, andaknapsackcapacityconstraint.Utilizingasetofgreedyselectionrulesandagent-based modeling tosimulatethecompetitorsʹactions,wesolvetheproblemwithastochasticrulerapproach that incorporatesbeamsearchtodetermineitemselectionofthetypesspecifiedbythesolutionrep- resentation. Weillustratethecomputationaleffectivenessofourapproachoninstancesmotivatedbya sports leaguedraftaswellasgenericprobleminstancesbasedontheknapsackliterature.