IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2502.03546.html
   My bibliography  Save this paper

Preference graphs: a combinatorial tool for game theory

Author

Listed:
  • Oliver Biggar
  • Iman Shames

Abstract

The preference graph is a combinatorial representation of the structure of a normal-form game. Its nodes are the strategy profiles, with an arc between profiles if they differ in the strategy of a single player, where the orientation indicates the preferred choice for that player. We show that the preference graph is a surprisingly fundamental tool for studying normal-form games, which arises from natural axioms and which underlies many key game-theoretic concepts, including dominated strategies and strict Nash equilibria, as well as classes of games like potential games, supermodular games and weakly acyclic games. The preference graph is especially related to game dynamics, playing a significant role in the behaviour of fictitious play and the replicator dynamic. Overall, we aim to equip game theorists with the tools and understanding to apply the preference graph to new problems in game theory.

Suggested Citation

  • Oliver Biggar & Iman Shames, 2025. "Preference graphs: a combinatorial tool for game theory," Papers 2502.03546, arXiv.org.
    • Handle: RePEc:arx:papers:2502.03546
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2502.03546
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Shayegan Omidshafiei & Karl Tuyls & Wojciech M. Czarnecki & Francisco C. Santos & Mark Rowland & Jerome Connor & Daniel Hennes & Paul Muller & Julien Pérolat & Bart De Vylder & Audrunas Gruslys & Rémi, 2020. "Navigating the landscape of multiplayer games," Nature Communications, Nature, vol. 11(1), pages 1-17, December.
    2. John C. Harsanyi & Reinhard Selten, 1988. "A General Theory of Equilibrium Selection in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262582384, December.
    3. repec:dau:papers:123456789/1014 is not listed on IDEAS
    4. Viossat, Yannick & Zapechelnyuk, Andriy, 2013. "No-regret dynamics and fictitious play," Journal of Economic Theory, Elsevier, vol. 148(2), pages 825-842.
    5. J. B. Cruz & M. A. Simaan, 2000. "Ordinal Games and Generalized Nash and Stackelberg Solutions," Journal of Optimization Theory and Applications, Springer, vol. 107(2), pages 205-222, November.
    6. Basu, Kaushik & Weibull, Jorgen W., 1991. "Strategy subsets closed under rational behavior," Economics Letters, Elsevier, vol. 36(2), pages 141-146, June.
    7. , & , H., 2011. "Survival of dominated strategies under evolutionary dynamics," Theoretical Economics, Econometric Society, vol. 6(3), September.
    8. Panayotis Mertikopoulos & William H. Sandholm, 2016. "Learning in Games via Reinforcement and Regularization," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1297-1324, November.
    9. Gaunersdorfer Andrea & Hofbauer Josef, 1995. "Fictitious Play, Shapley Polygons, and the Replicator Equation," Games and Economic Behavior, Elsevier, vol. 11(2), pages 279-303, November.
    10. Aumann, Robert J, 1987. "Correlated Equilibrium as an Expression of Bayesian Rationality," Econometrica, Econometric Society, vol. 55(1), pages 1-18, January.
    11. Young, H Peyton, 1993. "The Evolution of Conventions," Econometrica, Econometric Society, vol. 61(1), pages 57-84, January.
    12. Josef Hofbauer & Sylvain Sorin & Yannick Viossat, 2009. "Time Average Replicator and Best-Reply Dynamics," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 263-269, May.
    13. repec:ebl:ecbull:v:3:y:2002:i:22:p:1-6 is not listed on IDEAS
    14. Sergiu Hart & Andreu Mas-Colell, 2013. "Uncoupled Dynamics Do Not Lead To Nash Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 7, pages 153-163, World Scientific Publishing Co. Pte. Ltd..
    15. MOULIN, Hervé & VIAL, Jean-Philippe, 1978. "Strategically zero-sum games: the class of games whose completely mixed equilibria connot be improved upon," LIDAM Reprints CORE 359, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. Berger, Ulrich, 2007. "Two more classes of games with the continuous-time fictitious play property," Games and Economic Behavior, Elsevier, vol. 60(2), pages 247-261, August.
    17. Foster, Dean P. & Young, H. Peyton, 1998. "On the Nonconvergence of Fictitious Play in Coordination Games," Games and Economic Behavior, Elsevier, vol. 25(1), pages 79-96, October.
    18. Moulin, Herve, 1984. "Dominance solvability and cournot stability," Mathematical Social Sciences, Elsevier, vol. 7(1), pages 83-102, February.
    19. Monderer, Dov & Shapley, Lloyd S., 1996. "Fictitious Play Property for Games with Identical Interests," Journal of Economic Theory, Elsevier, vol. 68(1), pages 258-265, January.
    20. Tetsuo Yamamori & Satoru Takahashi, 2002. "The pure Nash equilibrium property and the quasi-acyclic condition," Economics Bulletin, AccessEcon, vol. 3(22), pages 1-6.
    21. Endre Boros & Khaled Elbassioni & Vladimir Gurvich & Kazuhisa Makino & Vladimir Oudalov, 2016. "Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden $$2 \times 2$$ 2 × 2 subgames," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(4), pages 1111-1131, November.
    Full references (including those not matched with items on IDEAS)

    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. Ewerhart, Christian & Valkanova, Kremena, 2020. "Fictitious play in networks," Games and Economic Behavior, Elsevier, vol. 123(C), pages 182-206.
    2. Jonathan Newton, 2018. "Evolutionary Game Theory: A Renaissance," Games, MDPI, vol. 9(2), pages 1-67, May.
    3. Andriy Zapechelnyuk, 2009. "Limit Behavior of No-regret Dynamics," Discussion Papers 21, Kyiv School of Economics.
    4. Viossat, Yannick & Zapechelnyuk, Andriy, 2013. "No-regret dynamics and fictitious play," Journal of Economic Theory, Elsevier, vol. 148(2), pages 825-842.
    5. repec:hal:wpaper:hal-00713871 is not listed on IDEAS
    6. Sandholm, William H., 2015. "Population Games and Deterministic Evolutionary Dynamics," Handbook of Game Theory with Economic Applications,, Elsevier.
    7. Ulrich Berger, 2004. "Two More Classes of Games with the Fictitious Play Property," Game Theory and Information 0408003, University Library of Munich, Germany.
    8. Sylvain Sorin, 2023. "Continuous Time Learning Algorithms in Optimization and Game Theory," Dynamic Games and Applications, Springer, vol. 13(1), pages 3-24, March.
    9. van Strien, Sebastian & Sparrow, Colin, 2011. "Fictitious play in 3x3 games: Chaos and dithering behaviour," Games and Economic Behavior, Elsevier, vol. 73(1), pages 262-286, September.
    10. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2012. "Perturbations of Set-Valued Dynamical Systems, with Applications to Game Theory," Dynamic Games and Applications, Springer, vol. 2(2), pages 195-205, June.
    11. Jun Honda, 2015. "Games with the Total Bandwagon Property," Department of Economics Working Papers wuwp197, Vienna University of Economics and Business, Department of Economics.
    12. Konstantinos Georgalos & Indrajit Ray & Sonali SenGupta, 2020. "Nash versus coarse correlation," Experimental Economics, Springer;Economic Science Association, vol. 23(4), pages 1178-1204, December.
    13. Arnaud Z. Dragicevic, 2019. "Market Coordination Under Non-Equilibrium Dynamics," Networks and Spatial Economics, Springer, vol. 19(3), pages 697-715, September.
    14. Bryan McCannon, 2011. "Coordination between a sophisticated and fictitious player," Journal of Economics, Springer, vol. 102(3), pages 263-273, April.
    15. Daniele Condorelli & Massimiliano Furlan, 2024. "Deep Learning to Play Games," Papers 2409.15197, arXiv.org.
    16. Rossella Argenziano & Itzhak Gilboa, 2012. "History as a coordination device," Theory and Decision, Springer, vol. 73(4), pages 501-512, October.
    17. Tercieux, Olivier, 2006. "p-Best response set and the robustness of equilibria to incomplete information," Games and Economic Behavior, Elsevier, vol. 56(2), pages 371-384, August.
    18. van Damme, Eric & Weibull, Jorgen W., 2002. "Evolution in Games with Endogenous Mistake Probabilities," Journal of Economic Theory, Elsevier, vol. 106(2), pages 296-315, October.
    19. , 2021. "The Value of a Coordination Game," SocArXiv ymzrd_v1, Center for Open Science.
    20. J. Durieu & P. Solal & O. Tercieux, 2011. "Adaptive learning and p-best response sets," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(4), pages 735-747, November.
    21. Anke Gerber & Thorsten Hens & Bodo Vogt, "undated". "Coordination in a Repeated Stochastic Game with Imperfect Monitoring," IEW - Working Papers 126, Institute for Empirical Research in Economics - University of Zurich.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:arx:papers:2502.03546. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.