The Library
Approximate well-supported Nash equilibria in symmetric bimatrix games
Tools
Czumaj, Artur, Fasoulakis, Michail and Jurdzinski, Marcin (2014) Approximate well-supported Nash equilibria in symmetric bimatrix games. In: Lavi, Ron, (ed.) Algorithmic Game Theory : 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. Lecture Notes in Computer Science, Volume 8768 . Springer Berlin Heidelberg, pp. 244-254. ISBN 9783662448021
An open access version can be found in:
Official URL: http://dx.doi.org/10.1007/978-3-662-44803-8_21
Abstract
The ε-well-supported Nash equilibrium is a strong notion of approximation of a Nash equilibrium, where no player has an incentive greater than ε to deviate from any of the pure strategies that she uses in her mixed strategy. The smallest constant ε currently known for which there is a polynomial-time algorithm that computes an ε-well-supported Nash equilibrium in bimatrix games is slightly below 2/3. In this paper we study this problem for symmetric bimatrix games and we provide a polynomial-time algorithm that gives a (1/2 + δ)-well-supported Nash equilibrium, for an arbitrarily small positive constant δ.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
ISBN: | 9783662448021 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Algorithmic Game Theory : 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings | ||||
Editor: | Lavi, Ron | ||||
Official Date: | 2014 | ||||
Dates: |
|
||||
Volume: | Volume 8768 | ||||
Page Range: | pp. 244-254 | ||||
DOI: | 10.1007/978-3-662-44803-8_21 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 4 March 2016 | ||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |