American Institute of Mathematical Sciences

Advanced
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

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 & 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]

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
[2]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002
[3]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[4]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[5]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[6]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[7]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[8]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[9]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[10]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[11]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090
[12]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (46)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences