Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin and Savani, Rahul (2016) Distributed methods for computing approximate equilibria. In: International Conference on Web and Internet Economics, WINE 2016, Montréal, Canada, 11-14 Dec 2016. Published in: Web and Internet Economics. WINE 2016, 10123 pp. 15-28. ISBN 9783662541098. doi:10.1007/978-3-662-54110-4_2 ISSN 0302-9743.

PDF wine2016.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (353Kb)

Request Changes to record.

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(nlogn) payoff queries and always finds a 0.6528-WSNE, which improves the previous best known guarantee of 2/3.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Series Name:	Lecture Notes in Computer Science
Journal or Publication Title:	Web and Internet Economics. WINE 2016
Publisher:	Springer
Place of Publication:	Berlin, Heidelberg
ISBN:	9783662541098
ISSN:	0302-9743
Book Title:	Web and Internet Economics
Editor:	Cai , Y. and Vetta , A.
Official Date:	11 December 2016
Dates:	Date Event 11 December 2016 Published 10 December 2015 Available 24 September 2016 Accepted
Volume:	10123
Page Range:	pp. 15-28
DOI:	10.1007/978-3-662-54110-4_2
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	20 June 2018
Funder:	Engineering and Physical Sciences Research Council (EPSRC), Israel Science Foundation (ISF)
Conference Paper Type:	Paper
Title of Event:	International Conference on Web and Internet Economics, WINE 2016
Type of Event:	Conference
Location of Event:	Montréal, Canada
Date(s) of Event:	11-14 Dec 2016
Open Access Version:	ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item