Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. New Algorithms for Approximate Nash Equilibria in Bimatrix Games
 
research article

New Algorithms for Approximate Nash Equilibria in Bimatrix Games

Bosse, Hartwig
•
Byrka, Jaroslaw
•
Markakis, Evangelos
2010
Theoretical Computer Science

We consider the problem of computing additively approximate Nash equilibria in noncooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. We first provide a simpler algorithm, that achieves a 0.38197-approximation, which is exactly the same factor as the algorithm of Daskalakis, Mehta and Papadimitriou.This algorithm is then tuned, improving the approximation error to 0.36392. Our method is relatively fast and simple, 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. Finally we also exhibit a simple reduction that allows us to compute approximate equilibria for multi-player games by using algorithms for two-player games.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1016/j.tcs.2009.09.023
Web of Science ID

WOS:000272123800012

Author(s)
Bosse, Hartwig
Byrka, Jaroslaw
Markakis, Evangelos
Date Issued

2010

Published in
Theoretical Computer Science
Volume

411

Issue

1

Start page

164

End page

173

Subjects

Nash Equilibria

•

Bimatrix Games

•

Additive Approximation

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Available on Infoscience
September 17, 2009
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/42707
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés