Games of fixed rank: a hierarchy of bimatrix games

DOI10.1007/S00199-009-0436-2zbMATH Open1202.91007arXivcs/0511021OpenAlexW3136147237MaRDI QIDQ847799FDOQ847799

Authors: Thorsten Theobald, R. Kannan 

Publication date: 19 February 2010

Published in: Economic Theory (Search for Journal in Brave)

Abstract: We propose a new hierarchical approach to understand the complexity of the open problem of computing a Nash equilibrium in a bimatrix game. Specifically, we investigate a hierarchy of bimatrix games $(A,B)$ which results from restricting the rank of the matrix $A+B$ to be of fixed rank at most $k$. For every fixed $k$, this class strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We show that even for $k=1$ the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we can provide polynomial time algorithms for finding an $epsilon$-approximation.

Full work available at URL: https://arxiv.org/abs/cs/0511021

Recommendations

• Games of fixed rank: a hierarchy of bimatrix games
• Fast Algorithms for Rank-1 Bimatrix Games
• Rank-1 bimatrix games, a homeomorphism and a polynomial time algorithm
• Enumerating the Nash equilibria of rank 1-games
• Constant rank bimatrix games are PPAD-hard

zbMATH Keywords

approximationNash equilibriumbimarix gamefixed rank

Mathematics Subject Classification ID

Approximation algorithms (68W25) 2-person games (91A05) Spaces of games (91A70)

Cites Work

• Matrix Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Non-cooperative games
• Equilibrium points in n -person games
• Generic \(4\times 4\) two person games have at most 15 Nash equilibria
• New maximal numbers of equilibria in bimatrix games
• On the maximal number of Nash equilibria in an \(n\times n\) bimatrix game
• A bound on the number of Nash equilibria in a coordination game.
• Title not available (Why is that?)
• On the complexity of the parity argument and other inefficient proofs of existence
• Equilibrium Points of Bimatrix Games
• Approximation algorithms for indefinite quadratic programming
• Title not available (Why is that?)
• Polynomial algorithms for approximating Nash equilibria of bimatrix games
• Algorithms, games, and the internet
• Equilibrium Points of Bimatrix Games
• Computing Normal Form Perfect Equilibria for Extensive Two-Person Games
• On a class of nash-solvable bimatrix games and some related nash subsets

Cited In (26)

• Enumerating the Nash equilibria of rank 1-games
• Title not available (Why is that?)
• Nash equilibria: complexity, symmetries, and approximation
• A Glimpse at Paul G. Spirakis
• Title not available (Why is that?)
• On mutual concavity and strategically-zero-sum bimatrix games
• Fast Algorithms for Rank-1 Bimatrix Games
• Rank Reduction in Bimatrix Games
• Games of fixed rank: a hierarchy of bimatrix games
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem
• Constant rank bimatrix games are PPAD-hard
• A note on approximate Nash equilibria
• Algorithms for Playing Games with Limited Randomness
• A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Well supported approximate equilibria in bimatrix games
• Exploiting concavity in bimatrix games: new polynomially tractable subclasses
• Constant Rank Two-Player Games are PPAD-hard
• Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
• Separable and low-rank continuous games
• Ranking games
• Semidefinite games
• Parameterized two-player Nash equilibrium
• Detection thresholds in very sparse matrix completion
• Computing equilibria: a computational complexity perspective

This page was built for publication: Games of fixed rank: a hierarchy of bimatrix games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q847799)