Generation of Lower Bounds for Approximate NE Algorithms

13^th December 2017, 13:00
Peter Tobenna Igwe
University of Liverpool

Abstract

Amongst several algorithms for computing approximate Nash equilibria, the TS algorithm for bimatrix games and the Descent algorithm for polymatrix have upper bounds of (0.3393 + d) and (0.5 + d) respectively. Empirical research into both algorithms have found them to perform far better than their theoretical upper bounds. This excellent performance of the algorithms prompts the question as to whether the upper bounds on the quality of approximation of these algorithms are actually tight. In this talk, I will cover the techniques used to generate lower bounds for these algorithms.

For the Descent algorithm, we show a construction of a graph transduction game (which stems from applying game theory towards the problem of classification) that yields a polymatrix game with a high approximation guarantee. With regards to bimatrix games, we look at two methods of heuristic search: Tree-structured Parzan Estimator (a method of performing Bayesian optimization) and genetic algorithms. With slight modifications to a loss function, these search methods can be applied to construct lower bounds for future approximation algorithms.

Based on a chapter of my PhD thesis.