The Library
Distributed methods for computing approximate equilibria
Tools
Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin and Savani, Rahul (2018) Distributed methods for computing approximate equilibria. Algorithmica . doi:10.1007/s00453-018-0465-y ISSN 0178-4617.
|
PDF
WRAP-distributed-methods-computing-approximate-Czumaj-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (911Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00453-018-0465-y
Abstract
We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same time (for example, by solving a single LP that combines the two players’ payoffs), our algorithm first solves two independent LPs, each of which is derived from one of the two payoff matrices, and then computes an approximate Nash equilibrium using only limited communication between the players. Our method gives improved bounds on the complexity of computing approximate Nash equilibria in a number of different settings. Firstly, it gives a polynomial-time algorithm for computing approximate well supported Nash equilibria (WSNE) that always finds a 0.6528-WSNE, beating the previous best guarantee of 0.6608. Secondly, since our algorithm solves the two LPs separately, it can be applied to give an improved bound in the limited communication setting, giving a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and finds a 0.6528-WSNE, which beats the previous best known guarantee of 0.732. It can also be applied to the case of approximate Nash equilibria, where we obtain a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and always finds a 0.382-approximate Nash equilibrium, which improves the previous best guarantee of 0.438. Finally, the method can also be applied in the query complexity setting to give an algorithm that makes O(n log n) payoff queries and always finds a 0.6528-WSNE, which improves the previous best known guarantee of 2/3.
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Game theory, Equilibrium (Economics), Algorithms | |||||||||
Journal or Publication Title: | Algorithmica | |||||||||
Publisher: | Springer Verlag | |||||||||
ISSN: | 0178-4617 | |||||||||
Official Date: | 11 June 2018 | |||||||||
Dates: |
|
|||||||||
DOI: | 10.1007/s00453-018-0465-y | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 20 June 2018 | |||||||||
Date of first compliant Open Access: | 21 June 2018 | |||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year