
The Library
Approximate well-supported Nash equilibria below two-thirds
Tools
Fearnley, J., Goldberg, Paul W., Savani, Rahul and Sørensen, Troels Bjerre (2012) Approximate well-supported Nash equilibria below two-thirds. In: Serna, Maria, (ed.) Algorithmic Game Theory. Berlin: Springer Verlag, pp. 108-119. ISBN 9783642339950
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-33996-7_10
Abstract
In an ε-Nash equilibrium, a player can gain at most ε by changing his behaviour. Recent work has addressed the question of how best to compute ε-Nash equilibria, and for what values of ε a polynomial-time algorithm exists. An ε-well-supported Nash equilibrium (ε-WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most ε less than a best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Publisher: | Springer Verlag | ||||
Place of Publication: | Berlin | ||||
ISBN: | 9783642339950 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Algorithmic Game Theory | ||||
Editor: | Serna, Maria | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Page Range: | pp. 108-119 | ||||
DOI: | 10.1007/978-3-642-33996-7_10 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Description: | 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedings |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |