Fast Algorithms for Rank-1 Bimatrix Games
From MaRDI portal
Abstract: The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one, and shows the following: (1) For a game of rank r, the set of its Nash equilibria is the intersection of a generically one-dimensional set of equilibria of parameterized games of rank r-1 with a hyperplane. (2) One equilibrium of a rank-1 game can be found in polynomial time. (3) All equilibria of a rank-1 game can be found by following a piecewise linear path. In contrast, such a path-following method finds only one equilibrium of a bimatrix game. (4) The number of equilibria of a rank-1 game may be exponential. (5) There is a homeomorphism between the space of bimatrix games and their equilibrium correspondence that preserves rank. It is a variation of the homeomorphism used for the concept of strategic stability of an equilibrium component.
Recommendations
- Un nuevo algoritmo para la resolucion de juegos bimatriciales
- Rank-1 bimatrix games, a homeomorphism and a polynomial time algorithm
- Bimatrix games and bilinear programming
- Efficient decomposition of bimatrix games (extended abstract)
- Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
- New algorithms for approximate Nash equilibria in bimatrix games
- On the exact polynomial time algorithm for a special class of bimatrix game
- A sublinear-time randomized approximation algorithm for matrix games
- An algorithm for finding approximate Nash equilibria in bimatrix games
Cites work
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 51788 (Why is no real title available?)
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- scientific article; zbMATH DE number 1538127 (Why is no real title available?)
- A friendly smoothed analysis of the simplex method
- A geometric view of parametric linear programming
- A global Newton method to compute Nash equilibria.
- Bimatrix Equilibrium Points and Mathematical Programming
- Computational complexity of parametric linear programming
- Computing Normal Form Perfect Equilibria for Extensive Two-Person Games
- Computing Simply Stable Equilibria
- Constant rank two-player games are PPAD-hard
- Enumerating the Nash equilibria of rank 1-games
- Enumeration of Nash equilibria for two-player games
- Equilibrium Points of Bimatrix Games
- Equilibrium Points of Bimatrix Games
- Finding an interior point in the optimal face of linear programs
- Hard-to-Solve Bimatrix Games
- Market equilibrium under separable, piecewise-linear, concave utilities
- Maximal nash subsets for bimatrix games
- Nash and correlated equilibria: Some complexity considerations
- New maximal numbers of equilibria in bimatrix games
- Non-cooperative games
- On the Complexity of Nash Equilibria and Other Fixed Points
- On the Strategic Stability of Equilibria
- On the complexity of the parity argument and other inefficient proofs of existence
- On the computation of stable sets and strictly perfect equilibria.
- Parametric simplex algorithms for solving a special class of nonconvex minimization problems
- Rank-1 bimatrix games, a homeomorphism and a polynomial time algorithm
- Row rank equals column rank
- Sensitivity analysis in linear programming: Just be careful!
- Settling the complexity of computing two-player Nash equilibria
- Smoothed analysis of algorithms
- The complexity of computing a Nash equilibrium
- Two-person nonzero-sum games and quadratic programming
- \(NP\)-hardness of linear multiplicative programming and related problems
Cited in
(6)
This page was built for publication: Fast Algorithms for Rank-1 Bimatrix Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4994178)
