Nash Equilibria in Random Games
Nash Equilibria in Random Games
AbstractWe consider Nash equilibria in 2‐player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; onm×npayoff matrices, it runs in timeO(m2nloglogn+n2mloglogm) with high probability. Our result follows from showing that a 2‐player random game has a Nash equilibrium with supports of size two with high probability, at least 1 −O(1/logn). Our main tool is a polytope formulation of equilibria. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007
- GEORGIA TECH RESEARCH CORPORATION United States
- Hungarian Academy of Sciences Hungary
- UNIVERSITY COLLEGE LONDON, Bartlett School of Planning United Kingdom
- Hungarian Academy of Science Hungary
- ROYAL INSTITUTION FOR THE ADVANCEMENT OF LEARNING MCGILL UNIVERSITY Canada
Probabilistic games; gambling, random games, Stochastic games, stochastic differential games, QA Mathematics / matematika, polynomial time, algorithmic game theory, Nash equilibria
Probabilistic games; gambling, random games, Stochastic games, stochastic differential games, QA Mathematics / matematika, polynomial time, algorithmic game theory, Nash equilibria
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).32 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!