[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Linear solvers for nonlinear games: using pivoting algorithms to find Nash equilibria in n-player games

Published: 01 March 2011 Publication History

Abstract

Nash equilibria of two-player games are much easier to compute in practice than those of n-player games, even though the two problems have the same asymptotic complexity. We used a recent constructive reduction to solve general games using a two-player algorithm. However, the reduction increases the game size too much to be practically usable. An open problem is to find a more compact constructive reduction, which might make this approach feasible.

References

[1]
Chen, X., Deng, X., and Teng, S. 2009. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM) 56, 3, 1--57.
[2]
Daskalakis, C., Fabrikant, A., and Papadimitriou, C. 2006. The game world is flat: The complexity of Nash equilibria in succinct games. Automata, Languages and Programming, 513--524.
[3]
Feige, U. and Talgam-Cohen, I. 2010. A direct reduction from k-player to 2-player approximate Nash equilibrium. Arxiv preprint arXiv:1007.3886.
[4]
Govindan, S. and Wilson, R. 2003. A global Newton method to compute Nash equilibria. Journal of Economic Theory 110, 1, 65--86.
[5]
Govindan, S. and Wilson, R. 2004. Computing Nash equilibria by iterated polymatrix approximation. Journal of Economic Dynamics and Control 28, 7, 1229--1241.
[6]
Howson, J. 1972. Equilibria of polymatrix games. Management Science 18, 5, 312--318.
[7]
Lemke, C. and Howson, J. 1964. Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics 12, 2, 413--423.
[8]
McKelvey, R., McLennan, A., and Turocy, T. 2007. Gambit: Software tools for game theory, version 0.2007. 01.30.
[9]
Nudelman, E., Wortman, J., Shoham, Y., and Leyton-Brown, K. 2004. Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems. 880--887.

Index Terms

  1. Linear solvers for nonlinear games: using pivoting algorithms to find Nash equilibria in n-player games

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM SIGecom Exchanges
    ACM SIGecom Exchanges  Volume 10, Issue 1
    March 2011
    43 pages
    EISSN:1551-9031
    DOI:10.1145/1978721
    Issue’s Table of Contents

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 March 2011
    Published in SIGECOM Volume 10, Issue 1

    Check for updates

    Author Tag

    1. Nash equilibrium

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 78
      Total Downloads
    • Downloads (Last 12 months)5
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 05 Mar 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media