More Web Proxy on the site http://driver.im/

article

Algorithms for closed under rational behavior (CURB) sets

Authors:

Michael Benisch,

George B. Davis,

Tuomas SandholmAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 38, Issue 1

Pages 513 - 534

Published: 01 May 2010 Publication History

Abstract

We provide a series of algorithms demonstrating that solutions according to the fundamental game-theoretic solution concept of closed under rational behavior (CURB) sets in two-player, normal-form games can be computed in polynomial time (we also discuss extensions to n-player games). First, we describe an algorithm that identifies all of a player's best responses conditioned on the belief that the other player will play from within a given subset of its strategy space. This algorithm serves as a subroutine in a series of polynomial-time algorithms for finding all minimal CURB sets, one minimal CURB set, and the smallest minimal CURB set in a game. We then show that the complexity of finding a Nash equilibrium can be exponential only in the size of a game's smallest CURB set. Related to this, we show that the smallest CURB set can be an arbitrarily small portion of the game, but it can also be arbitrarily larger than the supports of its only enclosed Nash equilibrium. We test our algorithms empirically and find that most commonly studied academic games tend to have either very large or very small minimal CURB sets.

References

[1]

Abbott, T., Kane, D., & Valiant, P. (2005). On the complexity of two-player win-lose games. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 113-122.

[2]

Basu, K., & Weibull, J. W. (1991). Strategy subsets closed under rational behavior. Economics Letters, 36(2), 141-146.

[3]

Battigalli, P., & Siniscalchi, M. (2003). Rationalizable bidding in first-price auctions. Games and Economic Behavior, 45(1), 38-72.

[4]

Bernheim, B. D. (1984). Rationalizable strategic behavior. Econometrica, 52(4), 1007-28.

[5]

Brandt, F., Brill, M., Fischer, F., & Harrenstein, P. (2009). Computational aspects of Shapley's saddles. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 209-216.

[6]

Chen, X., & Deng, X. (2006). Settling the complexity of two-player Nash-equilibrium. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 261-272.

Digital Library

[7]

Conitzer, V., & Sandholm, T. (2005a). Complexity of (iterated) dominance. In Proceedings of the ACM Conference on Electronic Commerce (ACM EC), pp. 88-97.

[8]

Conitzer, V., & Sandholm, T. (2005b). A generalized strategy eliminability criterion and computational methods for applying it. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 483-488.

[9]

Conitzer, V., & Sandholm, T. (2006). A technique for reducing normal form games to compute a Nash equilibrium. In Proceedings of the International Conference on Automated Agents and Multi-Agent Systems (AAMAS), pp. 537-544.

[10]

Daskalakis, C., Goldberg, P. W., & Papadimitriou, C. H. (2009). The complexity of computing a nash equilibrium. Communications of the ACM, 52(2), 89-97.

Digital Library

[11]

Gilboa, I., Kalai, E., & Zemel, E. (1993). The compleixty of eliminating dominated strategies. Mathematics of Operations Research, 18, 553-565.

[12]

Gilboa, I., & Zemel, E. (1989). Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1, 80-93.

[13]

Hurkens, S. (1995). Learning by forgetful players. Games and Economic Behavior, 11(1), 304-329.

[14]

Jordan, P., & Wellman, M. (2010). Algorithms for finding approximate formations in games. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 798- 804.

[15]

Klimm, M., Sandholm, T., & Weibull, J. W. (2010). Finding all minimal sCURB sets in finite games. Mimeo, 3/24/2010.

[16]

Knuth, D. E., Papadimitriou, C. H., & Tsitsiklis, J. N. (1988). A note on strategy elimination in bimatrix games. OR Letters, 7 (3), 103-107.

Digital Library

[17]

Lemke, C., & Howson, J. (1964). Equilibrium points of bimatrix games. Journal of the Society of Industrial and Applied Mathematics, 12, 413-423.

[18]

McKelvey, R. D., McLennan, A. M., & Turocy, T. L. (2004). Gambit: Software tools for game theory, version 0.97.1.5. http://econweb.tamu.edu/gambit.

[19]

Nudelman, E., Wortman, J., Shoham, Y., & Leyton-Brown, K. (2004). Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms. In Proceedings of the International Conference on Automated Agents and Multi-Agent Systems (AAMAS) , pp. 880-887.

[20]

Pearce, D. G. (1984). Rationalizable strategic behavior and the problem of perfection. Econometrica, 52 (4), 1029-50.

[21]

Porter, R., Nudelman, E., & Shoham, Y. (2004). Simple search methods for finding a Nash equilibrium. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 664-669.

[22]

Pruzhansky, V. (2003). On finding CURB sets in extensive games. International Journal of Game Theory, 32(2), 205-210.

[23]

Sandholm, T., Gilpin, A., & Conitzer, V. (2005). Mixed-integer programming methods for finding Nash equilibria. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 495-501.

[24]

Savani, R., & von Stengel, B. (2004). Exponentially many steps for finding a Nash equilibrium in a bimatrix game. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 258-267.

Digital Library

[25]

Voorneveld, M., Kets, W., & Norde, H. (2005). An axiomatization of minimal CURB sets. International Journal of Game Theory, 33, 479-490.

[26]

Ye, Y. (2006). Improved complexity results on solving real-number linear feasibility problems. Mathematical Programming, 106(2), 339-363.

Digital Library

Cited By

Brandt FBrill M(2016)Computing Dominance-Based Solution ConceptsACM Transactions on Economics and Computation10.1145/29630935:2(1-22)Online publication date: 25-Oct-2016
https://dl.acm.org/doi/10.1145/2963093
Gatti NPanozzo FRestelli MGini MShehory OIto TJonker C(2013)Extensive--form games with heterogeneous populationsProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2485141(1199-1200)Online publication date: 6-May-2013
https://dl.acm.org/doi/10.5555/2484920.2485141
Hansen KMiltersen PSørensen T(2010)The computational complexity of trembling hand perfection and other equilibrium refinementsProceedings of the Third international conference on Algorithmic game theory10.5555/1929237.1929255(198-209)Online publication date: 18-Oct-2010
https://dl.acm.org/doi/10.5555/1929237.1929255

Algorithms for closed under rational behavior (CURB) sets

Recommendations

Algorithms for rationalizability and CURB sets
AAAI'06: Proceedings of the 21st national conference on Artificial intelligence - Volume 1

Significant work has been done on computational aspects of solving games under various solution concepts, such as Nash equilibrium, subgame perfect Nash equilibrium, correlated equilibrium, and (iterated) dominance. However, the fundamental concepts of ...
Impact of Asynchrony on the Behavior of Rational Selfish Agents

The behavior of rational selfish agents has been classically studied in the framework of strategic games in which each player has a set of possible actions, players choose actions simultaneously and the payoff for each player is determined by the matrix ...
Rational behaviour and strategy construction in infinite multiplayer games
FSTTCS'06: Proceedings of the 26th international conference on Foundations of Software Technology and Theoretical Computer Science

We study infinite games played by arbitrarily many players on a directed graph. Equilibrium states capture rational behaviour in these games. Instead of the well-known notion of a Nash equilibrium, we focus on the notion of a subgame perfect ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Artificial Intelligence Research

Journal of Artificial Intelligence Research Volume 38, Issue 1

May 2010

744 pages

ISSN:1076-9757

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Published: 01 May 2010

Published in JAIR Volume 38, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Brandt FBrill M(2016)Computing Dominance-Based Solution ConceptsACM Transactions on Economics and Computation10.1145/29630935:2(1-22)Online publication date: 25-Oct-2016
https://dl.acm.org/doi/10.1145/2963093
Gatti NPanozzo FRestelli MGini MShehory OIto TJonker C(2013)Extensive--form games with heterogeneous populationsProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2485141(1199-1200)Online publication date: 6-May-2013
https://dl.acm.org/doi/10.5555/2484920.2485141
Hansen KMiltersen PSørensen T(2010)The computational complexity of trembling hand perfection and other equilibrium refinementsProceedings of the Third international conference on Algorithmic game theory10.5555/1929237.1929255(198-209)Online publication date: 18-Oct-2010
https://dl.acm.org/doi/10.5555/1929237.1929255

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents