Séminaire de Probabilités commun ICJ/UMPA

An algorithmic solution to the Blotto game using multi-marginal couplings

by Philippe Rigollet

435 (UMPA)




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).