LIDS Tea: Solving Combinatorial Games using Products, Projections and Lexicographically Optimal Bases

What do catching smugglers, competing algorithms, and protecting against noise in communication channels have in common? We're going to view these problems as two-player zero-sum games, where each player has strategies that lie in combinatorial polytopes. In order to find Nash-equilibria for these games, we are going to consider two popular online learning algorithms: online mirror descent (OMD) and the multiplicative weights update (MWU). The OMD requires the computation of a certain Bregman projection, that has closed form solutions for simple convex sets like the Euclidean ball or the simplex. However, for general polyhedra one often needs to exploit the general machinery of convex optimization. We'll discuss our novel primal-style algorithm "Inc-Fix" for computing these projections on the base polytopes of polymatroids. On the other hand, the MWU algorithm converges in time polynomial in the number of pure strategies of the players. This especially becomes a problem when learning combinatorial objects like spanning trees, matchings, paths in a graph (which are exponential in number in the input of the game). Using product distributions, we're going to present a general recipe to simulate the MWU algorithm efficiently under the existence of linear optimization and generalized counting oracles (even if approximate). If time permits, we will discuss the combinatorial structure of symmetric Nash-equilibria and its connections to the lexicographically optimal bases. This is joint work with Michel Goemans and Patrick Jaillet.

About LIDS Tea: LIDS Tea talks are 20 minute long informal presentations for the purpose of sharing ideas and making others aware about some of the topics that may be of interest to the LIDS audience. If you are interested in presenting in the upcoming seminars, please email Marzieh Parandehgheibi or Yasin Yazicioglu.