LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Seminar
How non-computable is finding Nash equilibra in normal form games?
- Date
- 17.12.2019, 11:00
- Place
- Pavillon des Jardins
- Speaker
- Arno Pauly (Swansea University)
Is there an algorithm that takes a game in normal form as input, and outputs a Nash equilibrium? If the payoffs are integers, the answer is yes, and lot of work has been done in its computational complexity. If the payoffs are permitted to be real numbers, the answer is no, for continuity reasons. It is worthwhile to investigate the precise degree of non-computability (the Weihrauch degree), since knowing the degree entails what other approaches are available (eg, is there a randomized algorithm with positive success change?). I will give an introduction to Weihrauch degrees, a full classification of the two player case and an interpretation of it. The multiplayer case is under investigation, and I will present some initial results. This is part joint work with Takayuki Kihara, and part joint work with Tonicha Crook.