The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average.
Xavier AllamigeonPascal BenchimolStéphane GaubertPublished in: ICALP (1) (2014)
Keyphrases
- game theory
- nash equilibrium
- repeated games
- mixed strategy
- payoff functions
- nash equilibria
- special case
- worst case
- game theoretic
- video games
- long term
- light source
- minimum weight
- approximation algorithms
- serious games
- multi agent systems
- undirected graph
- game play
- shadow detection
- dnf formulas
- perfect information
- incomplete information
- directed graph
- computational complexity