Computational aspects of Shapley's saddles

ABSTRACT

Game-theoretic solution concepts, such as Nash equilibrium, are playing an ever increasing role in the study of systems of autonomous computational agents. A common criticism of Nash equilibrium is that its existence relies on the possibility of randomizing over actions, which in many cases is deemed unsuitable, impractical, or even infeasible. In work dating back to the early 1950s Lloyd Shapley proposed ordinal set-valued solution concepts for zero-sum games that he refers to as strict and weak saddles. These concepts are intuitively appealing, they always exist, and are unique in important subclasses of games. We initiate the study of computational aspects of Shapley's saddles and provide polynomial-time algorithms for computing strict saddles in normal-form games and weak saddles in a subclass of symmetric zero-sum games. On the other hand, we show that certain problems associated with weak saddles in bimatrix games are NP-hard. Finally, we extend our results to mixed refinements of Shapley's saddles introduced by Duggan and Le Breton.

REFERENCES

• 1: R. J. Aumann. Game theory. In J. Eatwell, M. Milgate, and P. Newman, editors, The New Palgrave: A Dictionary of Economics, volume 2, pages 460--482. MacMillan, 1987.
• 2: K. Basu and J. Weibull. Strategy subsets closed under rational behavior. Economics Letters, 36:141--146, 1991.
• 3: Michael Benisch , George Davis , Tuomas Sandholm, Algorithms for rationalizability and CURB sets, Proceedings of the 21st national conference on Artificial intelligence, p.598-604, July 16-20, 2006, Boston, Massachusetts
• 4: Felix Brandt , Felix Fischer, On the Hardness and Existence of Quasi-Strict Equilibria, Proceedings of the 1st International Symposium on Algorithmic Game Theory, April 30-May 02, 2008, Paderborn, Germany [doi>10.1007/978-3-540-79309-0_26]
• 5: F. Brandt and F. Fischer. Computing the minimal covering set. Mathematical Social Sciences, 56(2):254--268, 2008.
• 6: Felix Brandt , Felix Fischer , Paul Harrenstein , Yoav Shoham, Ranking games, Artificial Intelligence, v.173 n.2, p.221-239, February, 2009 [doi>10.1016/j.artint.2008.10.008]
• 7: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 8: Vincent Conitzer , Tuomas Sandholm, Complexity of (iterated) dominance, Proceedings of the 6th ACM conference on Electronic commerce, p.88-97, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064019]
• 9: V. Conitzer and T. Sandholm. A generalized strategy eliminability criterion and computational methods for applying it. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI), pages 483--488. AAAI Press, 2005.
• 10: Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
• 11: J. Duggan and M. Le Breton. Mixed refinements of Shapley's saddles and weak tournaments. Social Choice and Welfare, 18(1):65--78, 2001.
• 12: J. Duggan and M. Le Breton. Dutta's minimal covering set and Shapley's saddles. Journal of Economic Theory, 70:257--265, 1996.
• 13: B. Dutta and J.-F. Laslier. Comparison functions and choice correspondences. Social Choice and Welfare, 16 (4):513--532, 1999.
• 14: J. C. Harsanyi. Oddness of the number of equilibrium points: A new proof. International Journal of Game Theory, 2:235--250, 1973.
• 15: D. E. Knuth, C. H. Papadimitriou, and J. N. Tsitsiklis. A note on strategy elimination in bimatrix games. Operations Research Letters, 7:103--107, 1988.
• 16: R. D. Luce and H. Raiffa. Games and Decisions: Introduction and Critical Survey. John Wiley&Sons Inc., 1957.
• 17: A. McLennan and R. Tourky. Simple complexity from imitation games. Unpublished manuscript, 2005.
• 18: J. Nash. Equilibrium points in n-person games. Proceedings of the National Acadamy of Sciences (PNAS), 36:48--49, 1950.
• 19: J. F. Nash. Non-cooperative games. Annals of Mathematics, 54(2):286--295, 1951.
• 20: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
• 21: L. Shapley. Order matrices. I. Technical Report RM-1142, The RAND Corporation, 1953.
• 22: L. Shapley. Order matrices. II. Technical Report RM-1145, The RAND Corporation, 1953.
• 23: L. Shapley. A condition for the existence of saddle-points. Technical Report RM-1598, The RAND Corporation, 1955.
• 24: L. Shapley. Some topics in two-person games. In M. Dresher, L. S. Shapley, and A. W. Tucker, editors, Advances in Game Theory, volume 52 of Annals of Mathematics Studies, pages 1--29. Princeton University Press, 1964.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
Shapley's saddles, game theory, solution concepts