[Dmbu-l] TODAY 12pm: "Solving Combinatorial Games"

Natali Ruchansky natalir at bu.edu
Thu Mar 3 06:49:29 EST 2016

*Data Seminar *
*Solving Combinatorial Games using Products, Projections and
Lexicographically Optimal Bases*
Swati Gupta, MIT
*Thursday, March 3, 2016 at 12:00m in MCS 148*

*​Speaker: *Swati Gupta, MIT

*Title: *Solving Combinatorial Games using Products, Projections and
Lexicographically Optimal Bases

*Abstract*: In order to find Nash-equilibria for two-player zero-sum games
where each player plays combinatorial objects like spanning trees,
matchings etc, we consider two online learning algorithms: the online
mirror descent (OMD) algorithm and the multiplicative weights update (MWU)
algorithm. The OMD algorithm 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 give a
novel primal-style algorithm for computing Bregman projections on the base
polytopes of polymatroids. Next, in the case of the MWU algorithm, although
it scales logarithmically in the number of pure strategies or experts N in
terms of regret, the algorithm takes time polynomial in N; this especially
becomes a problem when learning combinatorial objects. We give a general
recipe to simulate the multiplicative weights update algorithm in time
polynomial in their natural dimension. This is useful whenever there exists
a polynomial time generalized counting oracle (even if approximate) over
these objects. Finally, using the combinatorial structure of symmetric
Nash-equilibria (SNE) when both players play bases of matroids, we show
that these coincide with lexicographically optimal bases and can be found
with a single projection or convex minimization without having to rely on
online learning.

This is joint work with Michel Goemans and Patrick Jaillet.

Natali :)

Natali :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/dmbu-l/attachments/20160303/acb56248/attachment.html>

More information about the Dmbu-l mailing list