-
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
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 |
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
[Back to Top]