IDEAS home Printed from https://ideas.repec.org/a/spr/jogath/v49y2020i3d10.1007_s00182-020-00723-3.html
   My bibliography  Save this article

Strong Nash equilibria and mixed strategies

Author

Listed:
  • Eleonora Braggion

    (Politecnico di Milano)

  • Nicola Gatti

    (Politecnico di Milano)

  • Roberto Lucchetti

    (Politecnico di Milano)

  • Tuomas Sandholm

    (Carnegie Mellon University)

  • Bernhard von Stengel

    (London School of Economics and Political Science)

Abstract

We study strong Nash equilibria in mixed strategies in finite games. A Nash equilibrium is strong if no coalition of players can jointly deviate so that all players in the coalition get strictly better payoffs. Our main result concerns games with two players and states that if a game admits a strong Nash equilibrium, then the payoff pairs in the support of the equilibrium lie on a straight line in the players’ utility space. As a consequence, the set of games that have a strong Nash equilibrium in which at least one player plays a mixed strategy has measure zero. We show that the same property holds for games with more than two players, already when no coalition of two players can profitably deviate. Furthermore, we show that, in contrast to games with two players, in a strong Nash equilibrium an outcome that is strictly Pareto dominated may occur with positive probability.

Suggested Citation

  • Eleonora Braggion & Nicola Gatti & Roberto Lucchetti & Tuomas Sandholm & Bernhard von Stengel, 2020. "Strong Nash equilibria and mixed strategies," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(3), pages 699-710, September.
    • Handle: RePEc:spr:jogath:v:49:y:2020:i:3:d:10.1007_s00182-020-00723-3
    DOI: 10.1007/s00182-020-00723-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00182-020-00723-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00182-020-00723-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Govindan, Srihari & Wilson, Robert, 2001. "Direct Proofs of Generic Finiteness of Nash Equilibrium Outcomes," Econometrica, Econometric Society, vol. 69(3), pages 765-769, May.
    2. Barnett,William A. & Moulin,Hervé & Salles,Maurice & Schofield,Norman J. (ed.), 1995. "Social Choice, Welfare, and Ethics," Cambridge Books, Cambridge University Press, number 9780521443401.
    3. Milgrom, Paul & Roberts, John, 1996. "Coalition-Proofness and Correlation with Arbitrary Communication Possibilities," Games and Economic Behavior, Elsevier, vol. 17(1), pages 113-128, November.
    4. Rabia Nessah & Guoqiang Tian, 2009. "On the Existence of Strong Nash Equilibria," Working Papers 2009-ECO-06, IESEG School of Management.
    5. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    6. Andelman, Nir & Feldman, Michal & Mansour, Yishay, 2009. "Strong price of anarchy," Games and Economic Behavior, Elsevier, vol. 65(2), pages 289-317, March.
    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. Richárd Kicsiny & Zoltán Varga, 2023. "New algorithm for checking Pareto optimality in bimatrix games," Annals of Operations Research, Springer, vol. 320(1), pages 235-259, January.

    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. Heller, Yuval, 2010. "Minority-proof cheap-talk protocol," Games and Economic Behavior, Elsevier, vol. 69(2), pages 394-400, July.
    2. Bloch, Francis & Dutta, Bhaskar, 2009. "Correlated equilibria, incomplete information and coalitional deviations," Games and Economic Behavior, Elsevier, vol. 66(2), pages 721-728, July.
    3. Heller, Yuval, 2010. "All-stage strong correlated equilibrium," Games and Economic Behavior, Elsevier, vol. 69(1), pages 184-188, May.
    4. Heller, Yuval, 2008. "Ex-ante and ex-post strong correlated equilbrium," MPRA Paper 7717, University Library of Munich, Germany, revised 11 Mar 2008.
    5. Nicholas Ziros, 2011. "Negotiation-proof correlated equilibrium," University of Cyprus Working Papers in Economics 14-2011, University of Cyprus Department of Economics.
    6. Dirk Van de gaer & Michel Martinez & Erik Schokkaert, 1998. "Measuring Intergenerational Mobility and Equality of Opportunity," Working Papers of Department of Economics, Leuven ces9810, KU Leuven, Faculty of Economics and Business (FEB), Department of Economics, Leuven.
    7. Stefan Ambec & Yann Kervinio, 2016. "Cooperative decision-making for the provision of a locally undesirable facility," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 46(1), pages 119-155, January.
    8. Barnett, William A. & Serletis, Apostolos, 2008. "Consumer preferences and demand systems," Journal of Econometrics, Elsevier, vol. 147(2), pages 210-224, December.
    9. Kranich, Laurence, 1997. "Equalizing opportunities through public education when innate abilities are unobservable," UC3M Working papers. Economics 7216, Universidad Carlos III de Madrid. Departamento de Economía.
    10. Tobias Harks & Martin Hoefer & Anja Schedel & Manuel Surek, 2021. "Efficient Black-Box Reductions for Separable Cost Sharing," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 134-158, February.
    11. Tami Tamir, 2023. "Cost-sharing games in real-time scheduling systems," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 273-301, March.
    12. Srihari Govindan & Robert Wilson, 2009. "On Forward Induction," Econometrica, Econometric Society, vol. 77(1), pages 1-28, January.
    13. Effrosyni Diamantoudi, 2003. "Equilibrium binding agreements under diverse behavioral assumptions," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 22(2), pages 431-446, September.
    14. Boniface Mbih & Issofa Moyouwou & Jérémy Picot, 2008. "Pareto violations of parliamentary voting systems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 34(2), pages 331-358, February.
    15. Bernard Monjardet & Jean-Pierre Barthélemy & Olivier Hudry & Bruno Leclerc, 2009. "Metric and latticial medians," Post-Print halshs-00408174, HAL.
    16. Bruno Leclerc & Bernard Monjardet, 2010. "Aggregation and residuation," Post-Print halshs-00504982, HAL.
    17. Dominique Lepelley & Fabrice Valognes, 1999. "On the Kim and Roush Voting Procedure," Group Decision and Negotiation, Springer, vol. 8(2), pages 109-123, March.
    18. James J. Heckman & Apostolos Serletis, "undated". "Introduction to Internally Consistent Modeling, Aggregation, Inference, and Policy," Working Papers 2014-73, Department of Economics, University of Calgary, revised 29 Sep 2014.
    19. Ngo Long & Vincent Martinet, 2018. "Combining rights and welfarism: a new approach to intertemporal evaluation of social alternatives," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(1), pages 35-64, January.
    20. Ehlers, Lars & Klaus, Bettina, 2016. "Object allocation via deferred-acceptance: Strategy-proofness and comparative statics," Games and Economic Behavior, Elsevier, vol. 97(C), pages 128-146.

    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:spr:jogath:v:49:y:2020:i:3:d:10.1007_s00182-020-00723-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.