# American Institute of Mathematical Sciences

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

## 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  February 2010 Revised  June 2010 Published  September 2010

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.
Citation: Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Two-person knapsack game. Journal of Industrial & 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.  Google Scholar [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.  Google Scholar [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. Google Scholar [4] M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," WH Freeman, 1979.  Google Scholar [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.  Google Scholar [6] H. Kellerer, U. Pferschy and D. Pisinger, "Knapsack Problems," Springer, 2004.  Google Scholar [7] E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, in "Proc. 16th Symp. on Theoretical Aspects of Computer Science," (1999), 404-413.  Google Scholar [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.  Google Scholar [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.  Google Scholar [10] I. Milchtaich, Congestion games with player-specific payoff functions, Games and Economic Behavior, 13 (1996), 111-124. doi: 10.1006/game.1996.0027.  Google Scholar [11] D. Monderer and L. Shapley, Potential games, Games and Economic Behavior, 14 (1996), 124-143. doi: 10.1006/game.1996.0044.  Google Scholar [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.  Google Scholar [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.  Google Scholar [14] C. H. Papadimitriou and K. Steiglitz, "Combinatorial Optimization: Algorithms and Complexity," Prentice-Hall, 1982.  Google Scholar [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.  Google Scholar [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.  Google Scholar [17] T. Roughgarden and É. Tardos, How bad is selfish routing?, in "Proc. 41th IEEE Symp. on Foundations of Computer Science," (2000), 93-102.  Google Scholar [18] É. Tardos, Network games, in "Proc. 36th ACM Symp. on Theory of Computing," (2004), 341-342.  Google Scholar [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. Google Scholar [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.  Google Scholar

show all references

##### References:
 [1] R. E. Bellman, "Dynamic Programming," Princeton University Press, 1957.  Google Scholar [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.  Google Scholar [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. Google Scholar [4] M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," WH Freeman, 1979.  Google Scholar [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.  Google Scholar [6] H. Kellerer, U. Pferschy and D. Pisinger, "Knapsack Problems," Springer, 2004.  Google Scholar [7] E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, in "Proc. 16th Symp. on Theoretical Aspects of Computer Science," (1999), 404-413.  Google Scholar [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.  Google Scholar [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.  Google Scholar [10] I. Milchtaich, Congestion games with player-specific payoff functions, Games and Economic Behavior, 13 (1996), 111-124. doi: 10.1006/game.1996.0027.  Google Scholar [11] D. Monderer and L. Shapley, Potential games, Games and Economic Behavior, 14 (1996), 124-143. doi: 10.1006/game.1996.0044.  Google Scholar [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.  Google Scholar [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.  Google Scholar [14] C. H. Papadimitriou and K. Steiglitz, "Combinatorial Optimization: Algorithms and Complexity," Prentice-Hall, 1982.  Google Scholar [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.  Google Scholar [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.  Google Scholar [17] T. Roughgarden and É. Tardos, How bad is selfish routing?, in "Proc. 41th IEEE Symp. on Foundations of Computer Science," (2000), 93-102.  Google Scholar [18] É. Tardos, Network games, in "Proc. 36th ACM Symp. on Theory of Computing," (2004), 341-342.  Google Scholar [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. Google Scholar [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.  Google Scholar
 [1] Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, Anand Srivastav. Price of anarchy for graph coloring games with concave payoff. Journal of Dynamics & 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 & 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 & 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 & Management Optimization, 2008, 4 (4) : 843-859. doi: 10.3934/jimo.2008.4.843 [5] Yannick Viossat. Game dynamics and Nash equilibria. Journal of Dynamics & Games, 2014, 1 (3) : 537-553. doi: 10.3934/jdg.2014.1.537 [6] Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123 [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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2005, 1 (3) : 315-321. doi: 10.3934/jimo.2005.1.315 [15] Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics & Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1 [16] 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 [17] 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 & Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060 [18] 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 [19] Miriam Kiessling, Sascha Kurz, Jörg Rambau. The integrated size and price optimization problem. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 669-693. doi: 10.3934/naco.2012.2.669 [20] P.K. Newton. N-vortex equilibrium theory. Discrete & Continuous Dynamical Systems, 2007, 19 (2) : 411-418. doi: 10.3934/dcds.2007.19.411

2020 Impact Factor: 1.801