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.  doi: 10.1287/moor.1040.0098.  Google Scholar

[3]

A. Czumaj and B. Vöcking, Tight bounds for worst-case equilibria,, in, (2002), 413.   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.  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, (1999), 404.   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.  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.  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.  doi: 10.1006/game.1996.0027.  Google Scholar

[11]

D. Monderer and L. Shapley, Potential games,, Games and Economic Behavior, 14 (1996), 124.  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.  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.  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, (1998), 299.   Google Scholar

[16]

R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibrium,, Int. J. Game Theory, 2 (1973), 65.  doi: 10.1007/BF01737559.  Google Scholar

[17]

T. Roughgarden and É. Tardos, How bad is selfish routing?,, in, (2000), 93.   Google Scholar

[18]

É. Tardos, Network games,, in, (2004), 341.   Google Scholar

[19]

A. Vetta, Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions,, in, (2002), 416.   Google Scholar

[20]

Z. Wang, W. Xing and S.-C. Fang, Two-group knapsack game,, Theor. Comput. Sci., 411 (2010), 1094.  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.  doi: 10.1287/moor.1040.0098.  Google Scholar

[3]

A. Czumaj and B. Vöcking, Tight bounds for worst-case equilibria,, in, (2002), 413.   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.  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, (1999), 404.   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.  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.  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.  doi: 10.1006/game.1996.0027.  Google Scholar

[11]

D. Monderer and L. Shapley, Potential games,, Games and Economic Behavior, 14 (1996), 124.  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.  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.  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, (1998), 299.   Google Scholar

[16]

R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibrium,, Int. J. Game Theory, 2 (1973), 65.  doi: 10.1007/BF01737559.  Google Scholar

[17]

T. Roughgarden and É. Tardos, How bad is selfish routing?,, in, (2000), 93.   Google Scholar

[18]

É. Tardos, Network games,, in, (2004), 341.   Google Scholar

[19]

A. Vetta, Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions,, in, (2002), 416.   Google Scholar

[20]

Z. Wang, W. Xing and S.-C. Fang, Two-group knapsack game,, Theor. Comput. Sci., 411 (2010), 1094.  doi: 10.1016/j.tcs.2009.12.002.  Google Scholar

[1]

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

[2]

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

[3]

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

[4]

Yannick Viossat. Game dynamics and Nash equilibria. Journal of Dynamics & Games, 2014, 1 (3) : 537-553. doi: 10.3934/jdg.2014.1.537

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2019060

[14]

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

[15]

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

[16]

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

[17]

Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013

[18]

Astridh Boccabella, Roberto Natalini, Lorenzo Pareschi. On a continuous mixed strategies model for evolutionary game theory. Kinetic & Related Models, 2011, 4 (1) : 187-213. doi: 10.3934/krm.2011.4.187

[19]

Anna Lisa Amadori, Astridh Boccabella, Roberto Natalini. A hyperbolic model of spatial evolutionary game theory. Communications on Pure & Applied Analysis, 2012, 11 (3) : 981-1002. doi: 10.3934/cpaa.2012.11.981

[20]

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

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (13)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]