An Empirical Study on Computation of Exact and Approximate Equilibria



Igwe, Tobenna
(2018) An Empirical Study on Computation of Exact and Approximate Equilibria. PhD thesis, University of Liverpool.

[img] Text
200711903_Jan2018.pdf

Download (1MB)

Abstract

The computation of Nash equilibria is one of the central topics in game theory, which has received much attention from a theoretical point of view. Studies have shown that the problem of finding a Nash equilibrium is PPAD-complete, which implies that we are unlikely to find a polynomial-time algorithm for this problem. Naturally, this has led to a line of work studying the complexity of finding approximate Nash equilibria. This thesis examines the computation of such approximate Nash equilibria within several classes of games from an empirical perspective. In this thesis, we address the computation of approximate Nash equilibria in bimatrix and polymatrix games. For both of these game classes, we provide a library of implementations of algorithms for the computation of exact and approximate Nash equilibria, as well as a suite of game generators which were used as a base for our empirical analysis of the algorithms. We investigate the trade-off between quality of approximation produced by the algorithms and the expected runtime. We provide some insight into the inner workings of the state-of-the-art algorithm for computing ε-Nash equilibria, presenting worst-case examples found for our provided suite of game generators. We then show lower bounds on these algorithms. In the case of polymatrix games, we generate this lower bound from a real-world application of game theory. For bimatrix games, we provide a robust means of generating lower bounds for approximation algorithms with the use of genetic algorithms.

Item Type: Thesis (PhD)
Divisions: Fac of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 16 Aug 2018 07:52
Last Modified: 03 Mar 2021 10:16
DOI: 10.17638/03016935
Supervisors:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3016935