New algorithms for approximate Nash equilibria in bimatrix games

H. Bosse, J. Byrka, E. Markakis

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

27 Citations (Scopus)
103 Downloads (Pure)

Abstract

We consider the problem of computing additively approximate Nash equilibria in non-cooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. Our work improves the previously best known (0.38197¿+¿e)-approximation algorithm of Daskalakis, Mehta and Papadimitriou [6]. First, we provide a simpler algorithm, which also achieves 0.38197. This algorithm is then tuned, improving the approximation error to 0.36392. Our method is relatively fast, as it requires solving only one linear program and it is based on using the solution of an auxiliary zero-sum game as a starting point. The first author was supported by NWO. The second and third author were supported by the EU Marie Curie Research Training Network, contract numbers MRTN-CT-2003-504438-ADONET and MRTN-CT-2004-504438-ADONET respectively.
Original languageEnglish
Title of host publicationProceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007) 12-14 December 2007, San Diego, California, USA
EditorsX. Deng, F.C. Graham
Place of PublicationBerlin
PublisherSpringer
Pages17-29
ISBN (Print)978-3-540-77104-3
DOIs
Publication statusPublished - 2007
Eventconference; WINE 2007, San Diego, California, USA; 2007-12-12; 2007-12-14 -
Duration: 12 Dec 200714 Dec 2007

Publication series

NameLecture Notes in Computer Science
Volume4858
ISSN (Print)0302-9743

Conference

Conferenceconference; WINE 2007, San Diego, California, USA; 2007-12-12; 2007-12-14
Period12/12/0714/12/07
OtherWINE 2007, San Diego, California, USA

Fingerprint Dive into the research topics of 'New algorithms for approximate Nash equilibria in bimatrix games'. Together they form a unique fingerprint.

Cite this