Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden \(2 \times 2\) subgames

  • Original Paper
  • Published:
International Journal of Game Theory Aims and scope Submit manuscript

Abstract

In 1964 Shapley observed that a matrix has a saddle point in pure strategies whenever every its \(2 \times 2\) submatrix has one. In contrast, a bimatrix game may have no pure strategy Nash equilibrium (NE) even when every \(2 \times 2\) subgame has one. Nevertheless, Shapley’s claim can be extended to bimatrix games as follows. We partition all \(2 \times 2\) bimatrix games into fifteen classes \(C = \{c_1, \ldots , c_{15}\}\) depending only on the preferences of two players. A subset \(t \subseteq C\) is called a NE-theorem if a bimatrix game has a NE whenever it contains no subgame from t. We suggest a method to construct all minimal (that is, strongest) NE-theorems based on the procedure of joint generation of transversal hypergraphs given by a special oracle. By this method we obtain all (six) strongest NE-theorems. Let us remark that the suggested approach, which may be called “math-pattern recognition”, is very general: it allows to characterize completely an arbitrary “target” in terms of arbitrary “attributes”.

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
Fig. 7

Similar content being viewed by others

References

  • Berger U (2007) Two more classes of games with the continuous-time fictitious play property. Games Econ Behav 60(2):247–261

    Article  Google Scholar 

  • Boros E, Gurvich V, Makino K (2009) Minimal and locally minimal games and game forms. Discrete Math 309(13):4456–4468

    Article  Google Scholar 

  • Boros E, Gurvich V, Makino K, Papp D (2010) Acyclic, or totally tight, two-person game forms, characterization and main properties. Discrete Math 310(6–7):1135–1151

    Article  Google Scholar 

  • Chvatal V, Lenhart WJ, Sbihi N (1990) Two-colourings that decompose perfect graphs. J Combin Theory Ser B 49:1–9

    Article  Google Scholar 

  • Edmonds J, Fulkerson DR (1970) Bottleneck Extrema, RM-5375-PR. The Rand Corporation, Santa Monica, Ca., Jan. 1968. J Combin Theory 8:299–306

  • Echenique F (2004) A characterization of strategic complementarities. Games Econ Behav 46(2):325–347

    Article  Google Scholar 

  • Fredman M, Khachiyan L (1996) On the complexity of dualization of monotone disjunctive normal forms. J Algorithms 21(3):618–628

    Article  Google Scholar 

  • Gurvich V (1973) To theory of multi-step games. USSR Comput Math Math Phys 13(6):143–161

    Article  Google Scholar 

  • Gurvich V (1975) Solution of positional games in pure strategies. USSR Comput Math Math Phys 15(2):74–87

    Article  Google Scholar 

  • Gurvich V (1988) Equilibrium in pure strategies. Sov Math Doklady 38(3):597–602

    Google Scholar 

  • Gurvich V, Khachiyan L (1999) On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions. Discrete Appl Math 96–97:363–373

    Article  Google Scholar 

  • Gurvich V, Libkin L (1990) Absolutely determined matrices. Math Soc Sci 20:1–18

    Article  Google Scholar 

  • Gvishiani AD, Gurvich VA (1983) Dual set systems and their applications, Izvestiya Akad. Nauk SSSR, ser. Tekhnicheskaya Kibernetika 4:31–39 (in Russian) [English translation in Sov J Comput Syst Sci (formerly Engineering Cybernetics)]

  • Hofbauer J (1995) Stability for the best response dynamics, mimeo. University of Vienna

  • Hofbauer J (1995) Imitation dynamics for games, mimeo. University of Vienna

  • Kukushkin NS (2007) Shapley’s \(2 \times 2\) theorem for game forms. Econ Bull 3:33, 1–5. http://www.accessecon.com/pubs/EB/2007/Volume3/EB-07C70017A

  • Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14(1):124–143

    Article  Google Scholar 

  • Shannon C (1995) Weak and strong monotone comparative statics. Econ Theory 5:209–227

    Article  Google Scholar 

  • Shapley LS (1964) Some topics in two-person games, in Advances in Game Theory. In: Drescher M, Shapley LS, Tucker AW (eds) Annals of Mathematical Studies, AM52. Princeton University Press, Princeton, pp 1–28

    Google Scholar 

  • Takahashi S, Yamamori T (2002) The pure Nash equilibrium property and the quasi-acyclic condition. Econ Bull 3:22, 1–6. http://www.accessecon.com/pubs/eb/2002/volume3/EB-02C70011A

Download references

Acknowledgments

We are thankful to Bernhard von Stengel and two anonymous referees for careful reading and many helpful remarks and suggestions. We thank also Nikolai Kukushkin who promoted the idea of generalizing Shapley’s (1964) theorem to bimatrix games and various concepts of solution. The first author gratefully acknowledges partial support by the National Science Foundation (Grant IIS-1161476).

Author information

Authors and Affiliations

  1. MSIS Department of RBS and RUTCOR, Rutgers University, 100 Rockafeller Road, Piscataway, NJ, 08854-8054, USA

    Endre Boros & Vladimir Gurvich

  2. Masdar Institute of Science and Technology, Abu Dhabi, UAE

    Khaled Elbassioni

  3. Research Institute for Mathematical Sciences (RIMS), Kyoto University, Kyoto, 606-8502, Japan

    Kazuhisa Makino

  4. Salient Management Company, 15 Roszel Rd. Suite 109, Princeton, NJ, 08540-6248, USA

    Vladimir Oudalov

Authors
  1. Endre Boros
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Khaled Elbassioni
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vladimir Gurvich
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kazuhisa Makino
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Vladimir Oudalov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Khaled Elbassioni.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Boros, E., Elbassioni, K., Gurvich, V. et al. Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden \(2 \times 2\) subgames. Int J Game Theory 45, 1111–1131 (2016). https://doi.org/10.1007/s00182-015-0513-7

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00182-015-0513-7

Keywords

JEL Classification

Search

Navigation