Two-person knapsack game

Zhenbo Wang; Wenxun Xing; Shu-Cherng Fang

doi:10.3934/jimo.2010.6.847

Article Contents

2010, Volume 6, Issue 4: 847-860. Doi: 10.3934/jimo.2010.6.847

This issue Previous Article An exterior point linear programming method based on inclusive normal cones Next Article Adaptive control of nonlinear systems using fuzzy systems

Two-person knapsack game

1.
Department of Mathematical Sciences, Tsinghua University, Beijing
2.
Department of Industrial and System Engineering, North Carolina State University, Raleigh, NC 27695

Received: January 31, 2010

Revised: May 31, 2010

Published: September 2010

Abstract Related Papers Cited by

Abstract

In this paper, we study a two-person knapsack game. Two investors, each with an individual budget, bid on a common pool of potential projects. To undertake a project, investors have their own cost estimation to be charged against their budgets. Associated with each project, there is a potential market profit that can be taken by the only bidder or shared proportionally by both bidders. The objective function of each investor is assumed to be a linear combination of the two bidders' profits. Both investors act in a selfish manner with best-response to optimize their own objective functions by choosing portfolios under the budget restriction. We show that pure Nash equilibrium exists under certain conditions. In this case, no investor can improve the objective by changing individual bid unilaterally. A pseudo polynomial-time algorithm is presented for generating a pure Nash equilibrium. We also investigate the price of anarchy (the ratio of the worst Nash equilibrium to the social optimum) associated with a simplified two-person knapsack game.

Keywords:

Mathematics Subject Classification: Primary: 68Q25, 90B99, 91A05, 91A10.

Citation:

Related Papers

Cited by

References

[1]	R. E. Bellman, "Dynamic Programming," Princeton University Press, 1957.
[2]	J. R. Correa, A. S. Schulz and N. E. Stier-Moses, Selfish routing in capacitated networks, Math. Oper. Res., 29 (2004), 961-976.doi: 10.1287/moor.1040.0098.
[3]	A. Czumaj and B. Vöcking, Tight bounds for worst-case equilibria, in "Proc. 13th ACM-SIAM Symp. on Discrete Algorithms," (2002), 413-420.
[4]	M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," WH Freeman, 1979.
[5]	E. Horowitz and S. Sahni, Computing partitions with applications to the knapsack problem, J. ACM, 21 (1974), 277-292.doi: 10.1145/321812.321823.
[6]	H. Kellerer, U. Pferschy and D. Pisinger, "Knapsack Problems," Springer, 2004.
[7]	E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, in "Proc. 16th Symp. on Theoretical Aspects of Computer Science," (1999), 404-413.
[8]	S. Martello and P. Toth, A mixture of dynamic programming and branch-and-bound for the subset-sum problem, Manage. Sci., 30 (1984), 765-771.doi: 10.1287/mnsc.30.6.765.
[9]	S. Martello and P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Manage. Sci., 45 (1999), 275-288.doi: 10.1287/mnsc.45.3.414.
[10]	I. Milchtaich, Congestion games with player-specific payoff functions, Games and Economic Behavior, 13 (1996), 111-124.doi: 10.1006/game.1996.0027.
[11]	D. Monderer and L. Shapley, Potential games, Games and Economic Behavior, 14 (1996), 124-143.doi: 10.1006/game.1996.0044.
[12]	J. F. Nash, Equilibrium points in $n$-Person games, P. Nalt. Acad Sci., 36 (1950), 48-49.doi: 10.1073/pnas.36.1.48.
[13]	R. M. Nauss, An efficient algorithm for the 0-1 knapsack problem, Manage. Sci., 23 (1976), 27-31.doi: 10.1287/mnsc.23.1.27.
[14]	C. H. Papadimitriou and K. Steiglitz, "Combinatorial Optimization: Algorithms and Complexity," Prentice-Hall, 1982.
[15]	D. Pisinger and P. Toth, Knapsack problems, in "Handbook of Combinatorial Optimization" (eds. D-Z. Du and P. Pardalos), (1998), Kluwer Academic Publishers, 299-428.
[16]	R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibrium, Int. J. Game Theory, 2 (1973), 65-67.doi: 10.1007/BF01737559.
[17]	T. Roughgarden and É. Tardos, How bad is selfish routing?, in "Proc. 41th IEEE Symp. on Foundations of Computer Science," (2000), 93-102.
[18]	É. Tardos, Network games, in "Proc. 36th ACM Symp. on Theory of Computing," (2004), 341-342.
[19]	A. Vetta, Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions, in "Proc. 43th IEEE Symp. on Foundations of Computer Science," (2002), 416-425.
[20]	Z. Wang, W. Xing and S.-C. Fang, Two-group knapsack game, Theor. Comput. Sci., 411 (2010), 1094-1103.doi: 10.1016/j.tcs.2009.12.002.