BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260420T172342Z
UID:Seminar-EcCo-566@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20171213T130000
DTEND:20171213T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Peter Tobenna Igwe: Generation of Lower Bounds for Approximate NE Algorithms \n\nAmongst 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.\n\nFor 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.\n\nBased on a chapter of my PhD thesis.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=566
LOCATION:
END:VEVENT
END:VCALENDAR