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.

Request Changes to record.

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:	Date Event 2012 Published
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