Two-person knapsack game

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

October 2010, 6(4): 847-860. doi: 10.3934/jimo.2010.6.847

Two-person knapsack game

Zhenbo Wang ^1, , Wenxun Xing ^1, and Shu-Cherng Fang ^2,

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

Received February 2010 Revised June 2010 Published September 2010

Abstract
Related Papers

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: price of anarchy, knapsack problem., game theory, Nash equilibrium.

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

Citation: Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Two-person knapsack game. Journal of Industrial and Management Optimization, 2010, 6 (4) : 847-860. doi: 10.3934/jimo.2010.6.847

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.

show all references

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.

[1]	Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, Anand Srivastav. Price of anarchy for graph coloring games with concave payoff. Journal of Dynamics and Games, 2017, 4 (1) : 41-58. doi: 10.3934/jdg.2017003
[2]	Fan Sha, Deren Han, Weijun Zhong. Bounds on price of anarchy on linear cost functions. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1165-1173. doi: 10.3934/jimo.2015.11.1165
[3]	Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[4]	Xiaolin Xu, Xiaoqiang Cai. Price and delivery-time competition of perishable products: Existence and uniqueness of Nash equilibrium. Journal of Industrial and Management Optimization, 2008, 4 (4) : 843-859. doi: 10.3934/jimo.2008.4.843
[5]	Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
[6]	Yannick Viossat. Game dynamics and Nash equilibria. Journal of Dynamics and Games, 2014, 1 (3) : 537-553. doi: 10.3934/jdg.2014.1.537
[7]	Moez Kallel, Maher Moakher, Anis Theljani. The Cauchy problem for a nonlinear elliptic equation: Nash-game approach and application to image inpainting. Inverse Problems and Imaging, 2015, 9 (3) : 853-874. doi: 10.3934/ipi.2015.9.853
[8]	Konstantinos A. Draziotis, Anastasia Papadopoulou. Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme. Advances in Mathematics of Communications, 2018, 12 (3) : 429-449. doi: 10.3934/amc.2018026
[9]	Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete and Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557
[10]	Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics and Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[11]	Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091
[12]	Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51
[13]	Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial and Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531
[14]	Yuzhong Zhang, Fan Zhang, Maocheng Cai. Some new results on multi-dimension Knapsack problem. Journal of Industrial and Management Optimization, 2005, 1 (3) : 315-321. doi: 10.3934/jimo.2005.1.315
[15]	Hsin-Min Sun, Yu-Juan Sun. Variable fixing method by weighted average for the continuous quadratic knapsack problem. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 15-29. doi: 10.3934/naco.2021048
[16]	Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics and Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1
[17]	Dean A. Carlson. Finding open-loop Nash equilibrium for variational games. Conference Publications, 2005, 2005 (Special) : 153-163. doi: 10.3934/proc.2005.2005.153
[18]	Shunfu Jin, Haixing Wu, Wuyi Yue, Yutaka Takahashi. Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060
[19]	Gabriella Pinzari. Global Kolmogorov tori in the planetary $\boldsymbol N$-body problem. Announcement of result. Electronic Research Announcements, 2015, 22: 55-75. doi: 10.3934/era.2015.22.55
[20]	P.K. Newton. N-vortex equilibrium theory. Discrete and Continuous Dynamical Systems, 2007, 19 (2) : 411-418. doi: 10.3934/dcds.2007.19.411

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Zhenbo Wang Wenxun Xing Shu-Cherng Fang
on Google Scholar
Zhenbo Wang Wenxun Xing Shu-Cherng Fang

[Back to Top]