Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Approximate well-supported Nash equilibria below two-thirds

Tools
- Tools
+ 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

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:
DateEvent
2012Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us