Skip to main content
Erschienen in: Journal of Engineering Mathematics 1/2015

01.04.2015

Bridging game theory and the knapsack problem: a theoretical formulation

verfasst von: Kelvin Kian Loong Wong

Erschienen in: Journal of Engineering Mathematics | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper presents an approach to solving the knapsack problem in which the solution can be derived based on a treatment of the classical bargaining problem. In spatial game theory, all the players form an \(n\)-polyhedron in space, and the bargaining set of items is positioned such that the geometrical distance of each item from every player reference vertex point is inversely proportional to its utility to the player. The game-theoretical-based distance of an item to a player is defined as the ratio of the geometrical distance referenced from the player’s vertex position to the sum of distances from all the \(n\)-player vertices of the polyhedron, and its game moment is derived from the product of utility and this distance. Pareto optimality can then be achieved by balancing the effective game-moment contributions from \(n\)-player subsets of items at equilibrium. The Pareto-optimal solution is defined such that for a given set of consolidated items, further addition of items to the knapsack will result in diminishing returns in their payoffs or profits attained together with the corresponding unwanted increases in constraints or burdens to cause destabilization of this equilibrium. This game-theoretical approach is employed by having the game player entities work cooperatively to maximize profit and minimize burdens in order to arrive at a solution and is the first spatial game representation of the knapsack problem.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Bazgan C, Hugot H, Vanderpooten D (2009) Solving efficiently the 0–1 multi-objective knapsack problem. Comput Oper Res 36:260–279CrossRefMATHMathSciNet Bazgan C, Hugot H, Vanderpooten D (2009) Solving efficiently the 0–1 multi-objective knapsack problem. Comput Oper Res 36:260–279CrossRefMATHMathSciNet
2.
Zurück zum Zitat Captivo ME, Climaco J, Figueira J, Martins E, Santos JL (2003) Solving bicriteria 0–1 knapsack problems using a labeling algorithm. Comput Oper Res 30:1865–1886 Captivo ME, Climaco J, Figueira J, Martins E, Santos JL (2003) Solving bicriteria 0–1 knapsack problems using a labeling algorithm. Comput Oper Res 30:1865–1886
3.
Zurück zum Zitat Figueira JR, Paquete L, Simoes M, Vanderpooten D (2013) Algorithmic improvements on dynamic programming for the bi-objective 0,1 knapsack problem. Comput Optim Appl 56:97–111 Figueira JR, Paquete L, Simoes M, Vanderpooten D (2013) Algorithmic improvements on dynamic programming for the bi-objective 0,1 knapsack problem. Comput Optim Appl 56:97–111
4.
Zurück zum Zitat Visee M, Teghem J, Pirlot M, Ulungu EL (1998) Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. J Glob Optim 12:139–155 Visee M, Teghem J, Pirlot M, Ulungu EL (1998) Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. J Glob Optim 12:139–155
5.
Zurück zum Zitat Florios K, Mavrotas G, Diakoulaki D (2010) Solving multi-objective, multi-constraint knapsack problems using mathematical programming and evolutionary algorithms. Eur J Oper Res 203:14–21CrossRefMATHMathSciNet Florios K, Mavrotas G, Diakoulaki D (2010) Solving multi-objective, multi-constraint knapsack problems using mathematical programming and evolutionary algorithms. Eur J Oper Res 203:14–21CrossRefMATHMathSciNet
6.
Zurück zum Zitat Laumanns M, Thiele L, Zitzler E (2006) An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur J Oper Res 169:932–942CrossRefMATHMathSciNet Laumanns M, Thiele L, Zitzler E (2006) An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur J Oper Res 169:932–942CrossRefMATHMathSciNet
7.
Zurück zum Zitat Lust T, Teghem J (2012) The multiobjective multidimensional knapsack problem: a survey and a new approach. Int Trans Oper Res 19:495–520CrossRefMATHMathSciNet Lust T, Teghem J (2012) The multiobjective multidimensional knapsack problem: a survey and a new approach. Int Trans Oper Res 19:495–520CrossRefMATHMathSciNet
8.
Zurück zum Zitat Shah R, Reed P (2011) Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional Knapsack problems. Eur J Oper Res 211:466–479CrossRefMathSciNet Shah R, Reed P (2011) Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional Knapsack problems. Eur J Oper Res 211:466–479CrossRefMathSciNet
10.
Zurück zum Zitat Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271CrossRef Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271CrossRef
11.
Zurück zum Zitat Andonov R, Poirriez V, Rajopadhye S (2000) Unbounded knapsack problem: dynamic programming revisited. Eur J Oper Res 123(2):168–181CrossRefMathSciNet Andonov R, Poirriez V, Rajopadhye S (2000) Unbounded knapsack problem: dynamic programming revisited. Eur J Oper Res 123(2):168–181CrossRefMathSciNet
12.
Zurück zum Zitat Kolesar PJ (1967) A branch and bound algorithm for the knapsack problem. Manag Sci 13(9):723–735CrossRef Kolesar PJ (1967) A branch and bound algorithm for the knapsack problem. Manag Sci 13(9):723–735CrossRef
13.
Zurück zum Zitat Plateau G, Elkihel M (1985) A hybrid algorithm for the 0–1 knapsack problem. Methods Oper Res 49:277–293MATHMathSciNet Plateau G, Elkihel M (1985) A hybrid algorithm for the 0–1 knapsack problem. Methods Oper Res 49:277–293MATHMathSciNet
14.
Zurück zum Zitat Martello S, Toth P (1984) A mixture of dynamic programming and branch-and-bound for the subset-sum problem. Manag Sci 30:765–771CrossRefMATHMathSciNet Martello S, Toth P (1984) A mixture of dynamic programming and branch-and-bound for the subset-sum problem. Manag Sci 30:765–771CrossRefMATHMathSciNet
15.
16.
Zurück zum Zitat Khan MA, Sun Y (2002) Non-cooperative games with many players. In: Handbook of game theory with economic applications, vol 3. Elsevier, Amsterdam, pp 1761–1808 Khan MA, Sun Y (2002) Non-cooperative games with many players. In: Handbook of game theory with economic applications, vol 3. Elsevier, Amsterdam, pp 1761–1808
17.
Zurück zum Zitat Rasmusen E (2001) Games and information: an introduction to game theory, 3rd edn. Blackwell, Oxford Rasmusen E (2001) Games and information: an introduction to game theory, 3rd edn. Blackwell, Oxford
18.
Zurück zum Zitat Nash JF (1950) The bargaining problem. Econometrica 18(2):155–162 Nash JF (1950) The bargaining problem. Econometrica 18(2):155–162
19.
Zurück zum Zitat Viossat Y (2006) The geometry of Nash equilibria and correlated equilibria and a generalization of zero-sum games. SSE/EFI Working Paper Series in Economics and Finance Viossat Y (2006) The geometry of Nash equilibria and correlated equilibria and a generalization of zero-sum games. SSE/EFI Working Paper Series in Economics and Finance
20.
Zurück zum Zitat Davis MD (1997) Game theory: a nontechnical introduction. Dover, MineolaMATH Davis MD (1997) Game theory: a nontechnical introduction. Dover, MineolaMATH
21.
Zurück zum Zitat Von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press, Princeton Von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press, Princeton
22.
Zurück zum Zitat Baron R, Durieu J, Haller H, Solal P (2004) Finding a Nash equilibrium in spatial games is an NP-complete problem. Econ Theory 23(2):445–454 Baron R, Durieu J, Haller H, Solal P (2004) Finding a Nash equilibrium in spatial games is an NP-complete problem. Econ Theory 23(2):445–454
23.
Zurück zum Zitat Nash J (1997) Essays on game theory. Edward Elgar, Cheltenham Nash J (1997) Essays on game theory. Edward Elgar, Cheltenham
24.
Zurück zum Zitat Wong KKL (2010) A geometrical perspective for the bargaining problem. PLoS One 5(4):e10331CrossRefADS Wong KKL (2010) A geometrical perspective for the bargaining problem. PLoS One 5(4):e10331CrossRefADS
25.
26.
Zurück zum Zitat Martello S, Toth P (1990) Knapsack problems—algorithms and computer implementations. Wiley, New YorkMATH Martello S, Toth P (1990) Knapsack problems—algorithms and computer implementations. Wiley, New YorkMATH
27.
Zurück zum Zitat Kumar R, Banerjee N (2006) Analysis of a multiobjective evolutionary algorithm on the 0–1 knapsack problem. Theor Comput Sci 358(1):104–120CrossRefMATHMathSciNet Kumar R, Banerjee N (2006) Analysis of a multiobjective evolutionary algorithm on the 0–1 knapsack problem. Theor Comput Sci 358(1):104–120CrossRefMATHMathSciNet
28.
Zurück zum Zitat Xie N-G, Meng R, Ye Y, Wang L, Cen Y-W (2013) Multi-objective design method based on evolution game and its application for suspension. Struct Multidiscip Optim 47:207–220 Xie N-G, Meng R, Ye Y, Wang L, Cen Y-W (2013) Multi-objective design method based on evolution game and its application for suspension. Struct Multidiscip Optim 47:207–220
31.
Zurück zum Zitat Yuan F, Baochun L, Bo L (2012) Bargaining towards maximized resource utilization in video streaming datacenters. In: Proceedings of IEEE INFOCOM, Orlando, FL, 25–30 March 2012, pp 1134–1142 Yuan F, Baochun L, Bo L (2012) Bargaining towards maximized resource utilization in video streaming datacenters. In: Proceedings of IEEE INFOCOM, Orlando, FL, 25–30 March 2012, pp 1134–1142
32.
Zurück zum Zitat Rui W, Xinxin F, Xiaoying G, Jing L, Haitao L (2013) Femtocell as a relay: a bargaining solution for femto users partition in geometrical perspective. In: International conference on wireless communications and signal processing (WCSP), Hangzhou, 24–26 October 2013, pp 1–6 Rui W, Xinxin F, Xiaoying G, Jing L, Haitao L (2013) Femtocell as a relay: a bargaining solution for femto users partition in geometrical perspective. In: International conference on wireless communications and signal processing (WCSP), Hangzhou, 24–26 October 2013, pp 1–6
Metadaten
Titel
Bridging game theory and the knapsack problem: a theoretical formulation
verfasst von
Kelvin Kian Loong Wong
Publikationsdatum
01.04.2015
Verlag
Springer Netherlands
Erschienen in
Journal of Engineering Mathematics / Ausgabe 1/2015
Print ISSN: 0022-0833
Elektronische ISSN: 1573-2703
DOI
https://doi.org/10.1007/s10665-014-9742-1

Weitere Artikel der Ausgabe 1/2015

Journal of Engineering Mathematics 1/2015 Zur Ausgabe

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.