Back to search

Institutes outside Greece

Computing approximate Nash equilibria

Abstract

dc:description

The problem of finding equilibria in non-cooperative games and understanding their properties is a central problem in modern game theory. After John Nash proved that every finite game has at least one equilibrium (so-called Nash equilibrium), the natural question arose whether we can compute one efficiently. After several years of extensive research, we now know that the problem of finding a Nash equilibrium is PPAD-complete even for two-player normal-form games, making the task of finding approximate Nash equilibria one of the central questions in the area of equilibrium computation. In this thesis our main goal is a new study of the complexity of various variants of the approximate Nash equilibrium. Specifically, we study algorithms for additive approximate Nash equilibria in bimatrix and multi-player games. Then, we study algorithms for relative approximate Nash equilibria in multi-player games. Furthermore, we study algorithms for optimal approximate Nash equilibria in bimatrix games and finally we study the communication complexity of additive approximate Nash equilibria in bimatrix games.

Degree

thesis:*
Grantor dc:publisher
Institutes outside Greece
Year dc:date
2017

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Fasoulakis, Michail
  • Φασουλάκης, Μιχαήλ

Subjects

dc:subject × 8

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/55818

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Fasoulakis, Michail; Φασουλάκης, Μιχαήλ. Computing approximate Nash equilibria. Institutes outside Greece, 2017. http://hdl.handle.net/10442/hedi/55818