New algorithms for approximate Nash equilibria in bimatrix games

H. Bosse, J. Byrka, E. Markakis

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

34 Citaten (Scopus)
177 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelProceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007) 12-14 December 2007, San Diego, California, USA
RedacteurenX. Deng, F.C. Graham
Plaats van productieBerlin
UitgeverijSpringer
Pagina's17-29
ISBN van geprinte versie978-3-540-77104-3
DOI's
StatusGepubliceerd - 2007
Evenementconference; WINE 2007, San Diego, California, USA; 2007-12-12; 2007-12-14 -
Duur: 12 dec. 200714 dec. 2007

Publicatie series

NaamLecture Notes in Computer Science
Volume4858
ISSN van geprinte versie0302-9743

Congres

Congresconference; WINE 2007, San Diego, California, USA; 2007-12-12; 2007-12-14
Periode12/12/0714/12/07
AnderWINE 2007, San Diego, California, USA

Vingerafdruk

Duik in de onderzoeksthema's van 'New algorithms for approximate Nash equilibria in bimatrix games'. Samen vormen ze een unieke vingerafdruk.

Citeer dit