Multi-Person Knapsack Game

In this paper,we study a multi-person knapsack game which is a generalization of two-person knapsack game.Some investors bid on a common pool of project under the restriction of their budgets.Each project has an expect potential market profits,which can be shared proportionally by its bidders.Each investor has an objective function which is associated with the profit himself and other investors’profits.In the model,we consider the linear function of their profits.Each investor want to optimize his own objective function under their budget restriction.In this paper,we discuss three cases for the investors’objective function,i.e.“self-ish knapsack game”,“competitive knapsack game”and“mixed knapsack game”.We will show that if the number of the investors is three,pure Nash equilibrium exists in all these three cases and we will also give the bound of the price of anarchy（ratio be-tween worst equilibrium and social optimal）.For the first two cases,we prove the the tight bound of₅³and³_5+2α（0≤α≤2）respectively,whereαis the competitive factor of the“competitive knapsack game”;For the third case,we prove the upper bound₂¹and the lower bound⁶₁₃≈0.462.At the end of the paper,we extend our conclusions to m investors,and consider the first case,i.e.“selfish knapsack game”,we prove pure Nash equilibrium exists and give the tight bound of the price of anarchy^m_2m-1.