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

James R. Wright, Albert Xin Jiang, Kevin Leyton-BrownSIGecom Exch 2011 · DOI · OpenReview

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.
BibTeX
@article{wright2011linear,
  author = {James R. Wright and Albert Xin Jiang and Kevin Leyton-Brown},
  title = {{Linear solvers for nonlinear games: using pivoting algorithms to find Nash equilibria in n-player games}},
  journal = {SIGecom Exch.},
  year = {2011},
  doi = {10.1145/1978721.1978724},
}

Loading related content...

Figure