Beyond nash equilibrium: solution concepts for the 21st century

ABSTRACT

Nash equilibrium is the most commonly-used notion of equilibrium in game theory. However, it suffers from numerous problems. Some are well known in the game theory community; for example, the Nash equilibrium of repeated prisoner's dilemma is neither normatively nor descriptively reasonable. However, new problems arise when considering Nash equilibrium from a computer science perspective: for example, Nash equilibrium is not robust (it does not tolerate "faulty" or "unexpected" behavior), it does not deal with coalitions, it does not take computation cost into account, and it does not deal with cases where players are not aware of all aspects of the game. Solution concepts that try to address these shortcomings of Nash equilibrium are discussed.

REFERENCES

• 1: Ittai Abraham , Danny Dolev , Rica Gonen , Joe Halpern, Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146393]
• 2: I. Abraham, D. Dolev, and J. Halpern. Lower bounds on implementing robust and resilient mediators. In Fifth Theory of Cryptography Conference, pages 302--319, 2008.
• 3: E. Adar and B. Huberman. Free riding on Gnutella. First Monday, 5(10), 2000.
• 4: R. J. Aumann. Acceptable points in general cooperative n-person games. In A. Tucker and R. Luce, editors, Contributions to the Theory of Games IV, Annals of Mathematical Studies 40, pages 287--324. Princeton University Press, Princeton, N. J., 1959.
• 5: R. Axelrod. The Evolution of Cooperation. Basic Books, New York, 1984.
• 6: Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 7: Imre Bárány, Fair distribution protocols or how the players replace fortune, Mathematics of Operations Research, v.17 n.2, p.327-340, May 1992 [doi>10.1287/moor.17.2.327]
• 8: E. Ben-Porath. Cheap talk in games with incomplete information. Journal of Economic Theory, 108(1):45--71, 2003.
• 9: E. Ben-Sasson, A. Kalai, and E. Kalai. An approach to bounded rationality. In Advances in Neural Information Processing Systems 19 (Proc. of NIPS 2006), pages 145--152. 2007.
• 10: B. D. Bernheim, B. Peleg, and M. Whinston. Coalition proof Nash equilibrium: concepts. Journal of Economic Theory, 42(1):1--12, 1989.
• 11: E. Dekel, B. Lipman, and A. Rustichini. Standard state-space models preclude unawareness. Econometrica, 66:159--173, 1998.
• 12: R. Fagin , J. Y. Halpern, Belief, awareness, and limited reasoning, Artificial Intelligence, v.34 n.1, p.39-76, Dec. 1987 [doi>10.1016/0004-3702(87)90003-8]
• 13: Y. Feinberg. Subjective reasoning--games with unawareness. Technical Report Resarch Paper Series \#1875, Stanford Graduate School of Business, 2004.
• 14: Y. Feinberg. Games with incomplete awareness. Technical Report Resarch Paper Series \#1894, Stanford Graduate School of Business, 2005.
• 15: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 16: F. Forges. Universal mechanisms. Econometrica, 58(6):1341--64, 1990.
• 17: D. Fudenberg and J. Tirole. Game Theory. MIT Press, Cambridge, Mass., 1991.
• 18: D. Gerardi. Unmediated communication in games with complete and incomplete information. Journal of Economic Theory, 114:104--131, 2004.
• 19: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 20: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 21: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 22: D. Gordon and J. Katz. Rational secret sharing, revisited. In SCN (Security in Communication Networks) 2006, pages 229--241, 2006.
• 23: J. Y. Halpern. Alternative semantics for unawareness. Games and Economic Behavior, 37:321--339, 2001.
• 24: J. Y. Halpern. A computer scientist looks at game theory. Games and Economic Behavior, 45(1):114--132, 2003.
• 25: J. Y. Halpern and R. Pass. Game theory with costly computation. Unpublished manuscript, 2008.
• 26: Joseph Y. Halpern , Leandro C. Rêgo, Extensive games with possibly unaware players, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160765]
• 27: J. Y. Halpern and L. C. Rêgo. Interactive unawareness revisited. Games and Economic Behavior, 62(1):232--262, 2008.
• 28: Joseph Halpern , Vanessa Teague, Rational secret sharing and multiparty computation: extended abstract, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007447]
• 29: A. Heifetz, M. Meier, and B. Schipper. Interactive unawareness. Journal of Economic Theory, 130:78--94, 2006.
• 30: Aviad Heifetz , Martin Meier , Burkhard C. Schipper, Unawareness, beliefs and games, Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge, June 25-27, 2007, Brussels, Belgium [doi>10.1145/1324249.1324275]
• 31: Y. Heller. A minority-proof cheap-talk protocol. Unpublished manuscript, 2005.
• 32: Sergei Izmalkov , Silvio Micali , Matt Lepinski, Rational Secure Computation and Ideal Mechanism Design, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.585-595, October 23-25, 2005 [doi>10.1109/SFCS.2005.64]
• 33: E. Kalai. Bounded rationality and strategic complexity in repeated games. In Game Theory and Applications, pages 131--157. Academic Press, San Diego, 1990.
• 34: Ian A. Kash , Eric J. Friedman , Joseph Y. Halpern, Optimizing scrip systems: efficiency, crashes, hoarders, and altruists, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250955]
• 35: G. Kol and M. Naor. Cryptography and game theory: Designing protocols for exchanging information. In Theory of Cryptography Conference, pages 320--339, 2008.
• 36: D. Kreps, P. Milgrom, J. Roberts, and R. Wilson. Rational cooperation in finitely repeated prisoners' dilemma. Journal of Economic Theory, 27(2):245--252, 1982.
• 37: D. M. Kreps. Game Theory and Economic Modeling. Oxford University Press, Oxford, UK, 1990.
• 38: Matt Lepinski , Silvio Micali , Chris Peikert , Abhi Shelat, Completely fair SFE and coalition-safe cheap talk, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011769]
• 39: J. Li. Information structures with unawareness. Unpublished manuscript, 2006.
• 40: J. Li. Modeling unawareness without impossible states. Unpublished manuscript, 2006.
• 41: A. Lysyanskaya and N. Triandopoulos. Rationality and adveresarial behavior in multi-party comptuation. In CRYPTO 2006, pages 180--197, 2006.
• 42: Silvio Micali , Rafael Pass, Local zero knowledge, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132561]
• 43: S. Modica and A. Rustichini. Awareness and partitional information structures. Theory and Decision, 37:107--124, 1994.
• 44: S. Modica and A. Rustichini. Unawareness and partitional information structures. Games and Economic Behavior, 27(2):265--298, 1999.
• 45: D. Moreno and J. Wooders. Coalition-proof equilibrium. Games and Economic Behavior, 17(1):80--112, 1996.
• 46: J. Nash. Equilibrium points in n-person games. Proc. National Academy of Sciences, 36:48--49, 1950.
• 47: A. Neyman. Bounded complexity justifies cooperation in finitely repated prisoner's dilemma. Economic Letters, 19:227--229, 1985.
• 48: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, Cambridge, Mass., 1994.
• 49: Erkut Y. Ozbay, Unawareness and strategic announcements in games with uncertainty, Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge, June 25-27, 2007, Brussels, Belgium [doi>10.1145/1324249.1324280]
• 50: Christos H. Papadimitriou , Mihalis Yannakakis, On complexity as bounded rationality (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.726-733, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195445]
• 51: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 52: A. Rubinstein. Finite automata play the repeated prisoner's dilemma. Journal of Economic Theory, 39:83--96, 1986.
• 53: A. Shamir, R. L. Rivest, and L. Adelman. Mental poker. In D. A. Klarner, editor, The Mathematical Gardner, pages 37--43. Prindle, Weber, and Schmidt, Boston, Mass., 1981.
• 54: A. Urbano and J. E. Vila. Computational complexity and communication: Coordination in two-player games. Econometrica, 70(5):1893--1927, 2002.
• 55: A. Urbano and J. E. Vila. Computationally restricted unmediated talk under incomplete information. Economic Theory, 23(2):283--320, 2004.
• 56: Andrew C. Yao, Protocols for secure computations, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), p.160-164, November 03-05, 1982

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  F. Theory of Computation
  F.0 GENERAL

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Economics, Theory

Keywords:
awareness, game theory, nash equilibrium, resilience, robustness, solution concepts