Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Computing approximate Nash equilibria

Tools
- Tools
+ Tools

Fasoulakis, Michail (2017) Computing approximate Nash equilibria. PhD thesis, University of Warwick.

[img]
Preview
PDF
WRAP_Theses_Fasoulakis_2017.pdf - Submitted Version - Requires a PDF viewer.

Download (1217Kb) | Preview
Official URL: http://webcat.warwick.ac.uk/record=b3084090~S15

Request Changes to record.

Abstract

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.

Item Type: Thesis (PhD)
Subjects: Q Science > QA Mathematics
Library of Congress Subject Headings (LCSH): Game theory, Noncooperative games (Mathematics), Equilibrium (Economics), Algorithms
Official Date: 2017
Dates:
DateEvent
2017Submitted
Institution: University of Warwick
Theses Department: Department of Computer Science
Thesis Type: PhD
Publication Status: Unpublished
Supervisor(s)/Advisor: Czumaj, Artur ; JurdziƄski, Marcin
Format of File: pdf
Extent: vii, 133 leaves : illustrations
Language: eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us