Paper Info
Title
Well supported approximate equilibria in bimatrix games: a graph theoretic approach
Abstract
We study the existence and tractability of a notion of approximate equilibria in bimatrix games, called well supported approximate Nash Equilibria (SuppNE in short).We prove existence of e-SuppNE for any constant e ? (0, 1), with only logarithmic support sizes for both players. Also we propose a polynomial-time construction of SuppNE, both for win lose and for arbitrary (normalized) bimatrix games. The quality of these SuppNE depends on the girth of the Nash Dynamics graph in the win lose game, or a (rounded-off) win lose image of the original normalized game. Our constructions are very successful in sparse win lose games (ie, having a constant number of (0, 1)-elements in the bimatrix) with large girth in the Nash Dynamics graph. The same holds also for normalized games whose win lose image is sparse with large girth. Finally we prove the simplicity of constructing SuppNE both in random normalized games and in random win lose games. In the former case we prove that the uniform full mix is an o(1)-SuppNE, while in the case of win lose games, we show that (with high probability) there is either a PNE or a 0.5-SuppNE with support sizes only 2.
Year
DOI
Venue
2007
10.1007/978-3-540-74456-6_53
MFCS
Keywords
Field
DocType
nash dynamics graph,constant number,graph theoretic approach,random normalized game,original normalized game,normalized game,bimatrix game,large girth,constant e,approximate nash equilibria,approximate equilibrium,nash equilibria,polynomial time
Graph,Discrete mathematics,Combinatorics,e,Logarithm,Nash equilibrium,Mathematics
Conference
Volume
ISSN
ISBN
4708
0302-9743
3-540-74455-X
Citations 
PageRank 
References 
4
0.54
13
Authors
2
Name
Order
Citations
PageRank
Spyros Kontogiannis125928.04
Paul G. Spirakis22222299.05