IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v71y2011i1p141-173.html
   My bibliography  Save this article

Action-Graph Games

Author

Listed:
  • Jiang, Albert Xin
  • Leyton-Brown, Kevin
  • Bhat, Navin A.R.

Abstract

Representing and reasoning with games becomes difficult once they involve large numbers of actions and players, because the space requirement for utility functions can grow unmanageably. Action-Graph Games (AGGs) are a fully-expressive game representation that can compactly express utility functions with structure such as context-specific independence, anonymity, and additivity. We show that AGGs can be used to compactly represent all games that are compact when represented as graphical games, symmetric games, anonymous games, congestion games, and polymatrix games, as well as games that require exponential space under all of these existing representations. We give a polynomial-time algorithm for computing a player's expected utility under an arbitrary mixed-strategy profile, and show how to use this algorithm to achieve exponential speedups of existing methods for computing sample Nash equilibria. We present results of experiments showing that using AGGs leads to a dramatic increase in the size of games accessible to computational analysis.2

Suggested Citation

  • Jiang, Albert Xin & Leyton-Brown, Kevin & Bhat, Navin A.R., 2011. "Action-Graph Games," Games and Economic Behavior, Elsevier, vol. 71(1), pages 141-173, January.
    • Handle: RePEc:eee:gamebe:v:71:y:2011:i:1:p:141-173
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899-8256(10)00175-2
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Koller, Daphne & Milch, Brian, 2003. "Multi-agent influence diagrams for representing and solving games," Games and Economic Behavior, Elsevier, vol. 45(1), pages 181-221, October.
    2. Govindan, Srihari & Wilson, Robert, 2003. "A global Newton method to compute Nash equilibria," Journal of Economic Theory, Elsevier, vol. 110(1), pages 65-86, May.
    3. Herbert E. Scarf, 1967. "The Approximation of Fixed Points of a Continuous Mapping," Cowles Foundation Discussion Papers 216R, Cowles Foundation for Research in Economics, Yale University.
    4. Milchtaich, Igal, 1996. "Congestion Games with Player-Specific Payoff Functions," Games and Economic Behavior, Elsevier, vol. 13(1), pages 111-124, March.
    5. Eli Ben-Sasson & Adam Tauman Kalai & Ehud Kalai, 2006. "An Approach to Bounded Rationality," Discussion Papers 1439, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    6. G. van der Laan & A. J. J. Talman & L. van der Heyden, 1987. "Simplicial Variable Dimension Algorithms for Solving the Nonlinear Complementarity Problem on a Product of Unit Simplices Using a General Labelling," Mathematics of Operations Research, INFORMS, vol. 12(3), pages 377-397, August.
    7. Ehud Kalai, 2005. "Partially-Specified Large Games," Levine's Bibliography 784828000000000565, UCLA Department of Economics.
    8. Talman, A.J.J. & van der Laan, G. & Van der Heyden, L., 1987. "Variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using general labelling," Other publications TiSEM fbe9ae2f-e01d-4eef-944c-6, Tilburg University, School of Economics and Management.
    9. Porter, Ryan & Nudelman, Eugene & Shoham, Yoav, 2008. "Simple search methods for finding a Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 63(2), pages 642-662, July.
    10. Ehud Kalai, 2004. "Large Robust Games," Econometrica, Econometric Society, vol. 72(6), pages 1631-1665, November.
    11. Turocy, Theodore L., 2005. "A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence," Games and Economic Behavior, Elsevier, vol. 51(2), pages 243-263, May.
    12. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    13. Govindan, Srihari & Wilson, Robert, 2004. "Computing Nash equilibria by iterated polymatrix approximation," Journal of Economic Dynamics and Control, Elsevier, vol. 28(7), pages 1229-1241, April.
    14. Monderer, Dov & Shapley, Lloyd S., 1996. "Potential Games," Games and Economic Behavior, Elsevier, vol. 14(1), pages 124-143, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wright, James R. & Leyton-Brown, Kevin, 2017. "Predicting human behavior in unrepeated, simultaneous-move games," Games and Economic Behavior, Elsevier, vol. 106(C), pages 16-37.
    2. Rahul Savani & Bernhard Stengel, 2015. "Game Theory Explorer: software for the applied game theorist," Computational Management Science, Springer, vol. 12(1), pages 5-33, January.
    3. Buechel, Berno & Roehl, Nils, 2015. "Robust equilibria in location games," European Journal of Operational Research, Elsevier, vol. 240(2), pages 505-517.
    4. Thompson, David R.M. & Leyton-Brown, Kevin, 2017. "Computational analysis of perfect-information position auctions," Games and Economic Behavior, Elsevier, vol. 102(C), pages 583-623.
    5. Jiang, Albert Xin & Leyton-Brown, Kevin, 2015. "Polynomial-time computation of exact correlated equilibrium in compact games," Games and Economic Behavior, Elsevier, vol. 91(C), pages 347-359.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sam Ganzfried, 2020. "Fast Complete Algorithm for Multiplayer Nash Equilibrium," Papers 2002.04734, arXiv.org, revised Jan 2023.
    2. Cao, Yiyin & Dang, Chuangyin, 2022. "A variant of Harsanyi's tracing procedures to select a perfect equilibrium in normal form games," Games and Economic Behavior, Elsevier, vol. 134(C), pages 127-150.
    3. Jiang, Albert Xin & Leyton-Brown, Kevin, 2015. "Polynomial-time computation of exact correlated equilibrium in compact games," Games and Economic Behavior, Elsevier, vol. 91(C), pages 347-359.
    4. Thompson, David R.M. & Leyton-Brown, Kevin, 2017. "Computational analysis of perfect-information position auctions," Games and Economic Behavior, Elsevier, vol. 102(C), pages 583-623.
    5. Rahul Savani & Bernhard Stengel, 2015. "Game Theory Explorer: software for the applied game theorist," Computational Management Science, Springer, vol. 12(1), pages 5-33, January.
    6. P. Giovani Palafox-Alcantar & Dexter V. L. Hunt & Chris D. F. Rogers, 2020. "A Hybrid Methodology to Study Stakeholder Cooperation in Circular Economy Waste Management of Cities," Energies, MDPI, vol. 13(7), pages 1-30, April.
    7. Porter, Ryan & Nudelman, Eugene & Shoham, Yoav, 2008. "Simple search methods for finding a Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 63(2), pages 642-662, July.
    8. Yiyin Cao & Chuangyin Dang & Yabin Sun, 2022. "Complementarity Enhanced Nash’s Mappings and Differentiable Homotopy Methods to Select Perfect Equilibria," Journal of Optimization Theory and Applications, Springer, vol. 192(2), pages 533-563, February.
    9. Joosten, Reinoud & Talman, Dolf, 1998. "A globally convergent price adjustment process for exchange economies," Journal of Mathematical Economics, Elsevier, vol. 29(1), pages 15-26, January.
    10. Eaves, C. & van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 1996. "Balanced Simplices on Polytopes," Other publications TiSEM 21c51445-984c-4466-9e6a-6, Tilburg University, School of Economics and Management.
    11. P. Herings & Ronald Peeters, 2010. "Homotopy methods to compute equilibria in game theory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 119-156, January.
    12. Kets, W., 2008. "Networks and learning in game theory," Other publications TiSEM 7713fce1-3131-498c-8c6f-3, Tilburg University, School of Economics and Management.
    13. Cao, Ran & Coit, David W. & Hou, Wei & Yang, Yushu, 2020. "Game theory based solution selection for multi-objective redundancy allocation in interval-valued problem parameters," Reliability Engineering and System Safety, Elsevier, vol. 199(C).
    14. Milchtaich, Igal, 2009. "Weighted congestion games with separable preferences," Games and Economic Behavior, Elsevier, vol. 67(2), pages 750-757, November.
    15. Penn, Michal & Polukarov, Maria & Tennenholtz, Moshe, 2009. "Congestion games with load-dependent failures: Identical resources," Games and Economic Behavior, Elsevier, vol. 67(1), pages 156-173, September.
    16. Holzman, Ron & Law-Yone, Nissan, 1997. "Strong Equilibrium in Congestion Games," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 85-101, October.
    17. Kukushkin, Nikolai S., 2018. "A universal construction generating potential games," Games and Economic Behavior, Elsevier, vol. 108(C), pages 331-340.
    18. Sam Ganzfried & Austin Nowak & Joannier Pinales, 2018. "Successful Nash Equilibrium Agent for a Three-Player Imperfect-Information Game," Games, MDPI, vol. 9(2), pages 1-8, June.
    19. Kukushkin, Nikolai S., 2007. "Best response adaptation under dominance solvability," MPRA Paper 4108, University Library of Munich, Germany.
    20. Govindand, Srihari & Wilson, Robert B., 2008. "Computing Equilibria of N-Player Games with Arbitrary Accuracy," Research Papers 1984, Stanford University, Graduate School of Business.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:71:y:2011:i:1:p:141-173. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.