Séminaire Probabilités et Statistiques
An algorithmic solution to the Blotto game using multi-marginal couplings
23
June 2022
logo_team
Intervenant : Philippe Rigollet
Institution : MIT
Heure : 15h45 - 16h45
Lieu : 3L15

The Blotto game was introduced in 1921 by Émile Borel, together with the foundations of game theory. It is a simple resource allocation problem where two players have to allocate a fixed budget across N battlefields; the highest bidder wins the battlefield. Over its century-long existence, the game has received a lot of attention and many variants have been proposed. Solving this game means finding optimal strategies when they exist or, if they don't, finding Nash equilibria. Despite this interest, important cases (including constant-sum games where optimal solutions are known to exist) were still out of reach of explicit methods. In this talk, after an overview of the literature, I will present an algorithmic approach based on probabilistic arguments and that can be implemented using a modification of Sinkhorn iterations, made popular recently in computational optimal transport. This talk assumes no background on game theory.

Joint work with Vianney Perchet (ENSAE) et Thibaut Le Gouic (Centrale Marseille).

All (past and future) events