iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/S10288-017-0354-2
Nondominated Nash points: application of biobjective mixed integer programming | 4OR Skip to main content
Springer Nature Link
Log in

Nondominated Nash points: application of biobjective mixed integer programming

  • Research Paper
  • Published:
4OR Aims and scope Submit manuscript

Abstract

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. There is a another, quite different, concept of Pareto optimality in game theory, where the set of solutions to a game is the set of all possible strategy profiles rather than the set of Nash equilibria. Using that concept, a Pareto optimal solution is not necessarily a Nash equilibrium.

References

  • Altman E, Boulogne T, El-Azouzi R, Jiménez T, Wynter L (2006) A survey on networking games in telecommunications. Comput Oper Res 33(2):286–311

    Article  Google Scholar 

  • Audet C, Hansen P, Jaumard B, Savard G (2001) Enumeration of all extreme equilibria of bimatrix games. SIAM J Sci Comput 23(1):323–328

    Article  Google Scholar 

  • Avis D, Rosenberg DG, Savani R, von Stengel B (2010) Enumeration of Nash equilibria for two-player games. Econ Theory 42(1):9–37

    Article  Google Scholar 

  • Boland N, Charkhgard H, Savelsbergh M (2015) A criterion space search algorithm for biobjective integer programming: the balanced box method. INFORMS J Comput 27(4):735–754

    Article  Google Scholar 

  • Chakravorti B, Conley J (2004) Bargaining efficiency and the repeated prisoners dilemma. Econ Bull 3(3):1–8

    Google Scholar 

  • Chalmet LG, Lemonidis L, Elzinga DJ (1986) An algorithm for bi-criterion integer programming problem. Eur J Oper Res 25:292–300

    Article  Google Scholar 

  • Chankong V, Haimes YY (1983) Multiobjective decision making: theory and methodology. Elsevier, New York

    Google Scholar 

  • Chen X, Deng X (2006) Settling the complexity of two-player Nash equilibrium. In: 47th Annual IEEE symposium on foundations of computer science, pp 261–272

  • Chun Y, Thomson W (1990) Nash solution and uncertain disagreement points. Games Econ Behav 2(3):213–223

    Article  Google Scholar 

  • Dickhaut J, Kaplan T (1991) A program for finding Nash equilibria. Math J 1:87–93

    Google Scholar 

  • Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201–213

    Article  Google Scholar 

  • Ehrgott M (2006) A discussion of scalarization techniques for multiple objective integer programming. Ann Oper Res 147:343–360

    Article  Google Scholar 

  • Ehrgott M, Wang JY, Watling DP (2015) On multi-objective stochastic user equilibrium. Transportation Research Part B: Methodological, 81, Part 3:704–717. ISTTT 21 for the year 2015SI: ISTTT21

  • Elon Kohlberg J-FM (1986) On the strategic stability of equilibria. Econometrica 54(5):1003–1037

    Article  Google Scholar 

  • Fernandez FR, Puerto J (1996) Vector linear programming in zero-sum multicriteria matrix games. J Optim Theory Appl 89(1):115–127

    Article  Google Scholar 

  • Ghose D (1991) A necessary and sufficient condition for pareto-optimal security strategies in multicriteria matrix games. J Optim Theory Appl 68(3):463–481

    Article  Google Scholar 

  • Harsanyi J, Selten R (1988) A general theory of equilibrium selection in games. MIT Press, Cambridge

    Google Scholar 

  • Jansen MJM (1981) Maximal Nash subsets for bimatrix games. Naval Res Logist Q 28(1):147–152

    Article  Google Scholar 

  • Kirlik G, Sayın S (2014) A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems. Eur J Oper Res 232(3):479–488

    Article  Google Scholar 

  • LaValle SM (2006) Planning algorithms. Cambridge University Press, Cambridge

    Book  Google Scholar 

  • Lemke CE, Howson JT (1964) Equilibrium points of bimatrix games. J Soc Ind Appl Math 12(2):413–423

    Article  Google Scholar 

  • Lokman B, Köksalan M (2013) Finding all nondominated points of multi-objective integer programs. J Glob Optim 57(2):347–365

    Article  Google Scholar 

  • Mangasarian OL (1964) Equilibrium points of bimatrix games. J Soc Ind Appl Math 12(4):778–780

    Article  Google Scholar 

  • McKelvey RD, McLennan A (1996) Computation of equilibria in finite games. In: Handbook of computational economics. Elsevier, pp 87–142

  • Mills H (1960) Equilibrium points in finite games. J Soc Ind Appl Math 8(2):397–402

    Article  Google Scholar 

  • Myerson RB (1978) Refinements of the nash equilibrium concept. Int J Game Theory 7(2):73–80

    Article  Google Scholar 

  • Nash JF (1950) The bargaining problem. Econometrica 18:155–162

    Article  Google Scholar 

  • Nash JF (1951) Non-cooperative games. Ann Math 54:286–295

    Article  Google Scholar 

  • Nash JF (1953) Two person cooperative games. Econometrica 21:128–140

    Article  Google Scholar 

  • Nishizaki I, Notsu T (2007) Nondominated equilibrium solutions of a multiobjective two-person nonzero-sum game and corresponding mathematical programming problem. J Optim Theory Appl 135(2):217–239

    Article  Google Scholar 

  • Nishizaki I, Notsu T (2008) Nondominated equilibrium solutions of a multiobjective two-person nonzero-sum game in extensive form and corresponding mathematical programming problem. J Glob Optim 42(2):201–220

    Article  Google Scholar 

  • Pardalos PM, Migdalas A, Pitsoulis L (2008) Pareto optimality, game theory and equilibria. Springer, New York

    Google Scholar 

  • Porter R, Nudelman E, Shoham Y (2008) Simple search methods for finding a Nash equilibrium. Games Econ Behav 63(2):642–662

    Article  Google Scholar 

  • Ralphs TK, Saltzman MJ, Wiecek MM (2006) An improved algorithm for solving biobjective integer programs. Ann Oper Res 147:43–70

    Article  Google Scholar 

  • Sandholm T, Gilpin A, Conitzer V (2005) Mixed-integer programming methods for finding Nash equilibria. In: Proceedings of the 20th national conference on artificial intelligence, vol 2 of AAAI’05, pp 495–501, Pittsburgh, Pennsylvania. AAAI Press

  • Sayın S, Kouvelis P (2005) The multiobjective discrete optimization problem: a weighted min–max two-stage optimization approach and a bicriteria algorithm. Manag Sci 51(10):1572–1581

    Article  Google Scholar 

  • Selten R (1975) Reexamination of the perfectness concept for equilibrium points in extensive games. Int J Game Theory 4(1):25–55

    Article  Google Scholar 

  • Serrano R (2005) Fifty years of the Nash program 1953–2003. Investigaciones Economicas 29:219–258

    Google Scholar 

  • Shoham Y, Leyton-Brown K (2009) Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press, Cambridge

    Google Scholar 

  • van Damme EEC (2002) Strategic equilibrium. In: Aumann RJ, Hart S (eds) Handbook in game theory, vol III. North-Holland Publishing Company, Amsterdam, pp 3–123

    Google Scholar 

  • Voorneveld M, Grahn S, Dufwenberg M (2000) Ideal equilibria in noncooperative multicriteria games. Math Methods Oper Res 52(1):65–77

    Article  Google Scholar 

  • Wang JY, Ehrgott M (2013) Modelling route choice behaviour in a tolled road network with a time surplus maximisation bi-objective user equilibrium model. Transp Res Part B Methodol 57:342–360

    Article  Google Scholar 

  • Zeleny M (1975) Games with multiple payoffs. Int J Game Theory 4(4):179–191

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Management Systems Engineering, University of South Florida, Tampa, USA

    Hadi Charkhgard

  2. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA

    Martin Savelsbergh

  3. Graduate School of Management and Economics, Sharif University of Technology, Tehran, Iran

    Masoud Talebian

Authors
  1. Hadi Charkhgard
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin Savelsbergh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Masoud Talebian
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hadi Charkhgard.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Charkhgard, H., Savelsbergh, M. & Talebian, M. Nondominated Nash points: application of biobjective mixed integer programming. 4OR-Q J Oper Res 16, 151–171 (2018). https://doi.org/10.1007/s10288-017-0354-2

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-017-0354-2

Keywords

Mathematics Subject Classification

Search

Navigation