[Theory] 10/21 TTIC Colloquium: Ruta Mehta, University of Illinois at Urbana-Champaign

[Mary Marre]

*When:*      Monday, October 21st at 11:00 am



*Where:*     TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who: *      Ruta Mehta, University of Illinois at Urbana-Champaign


*Title: *      Sum-of-Squares Meets Nash: Lower Bounds for Finding Any
Equilibrium

*Abstract:* Computing Nash equilibrium (NE) in the two-player game is a
central question in algorithmic game theory. The main motivation of this
work is to understand the power of the sum-of-squares method in computing
equilibria, both exact and approximate.
We propose a framework of roundings for the sum-of-squares algorithm (and
convex relaxations in general) applicable to finding equilibria in
two-player bimatrix games. Specifically, we define the notion of oblivious
roundings with verification oracle (OV). These are algorithms that can
access a solution to the degree-d SoS relaxation to construct a list of
candidate (partial) solutions and invoke a verification oracle to check if
a candidate in the list gives an (exact or approximate) equilibrium.

This framework captures most known approximation algorithms in
combinatorial optimization including the celebrated semidefinite
programming based algorithms for Max-Cut, Constraint-Satisfaction Problems,
and the recent works on SoS relaxations for Unique Games/Small-Set
Expansion, Best Separable State, and many problems in unsupervised machine
learning.

Our main results are strong unconditional lower bounds in this framework.
Specifically, we show that for ε = Θ(1/poly(n)), there’s no algorithm that
uses a o(n)-degree SoS relaxation to construct a 2^o(n)-size list of
candidates and obtain an ε-approximate NE. For some constant ε, we show a
similar result for degree o(log (n)) SoS relaxation and list size no(log
(n)). Our results can be seen as an unconditional confirmation, in our
restricted algorithmic framework, of the recent Exponential Time Hypothesis
for PPAD.

Our proof strategy involves constructing a family of games that all share a
common sum-of-squares solution but every (approximate) equilibrium of any
game is far from every equilibrium of any other game in the family (in
either player’s strategy). Along the way, we strengthen the classical
unconditional lower bound against enumerative algorithms for finding
approximate equilibria due to Daskalakis-Papadimitriou and the classical
hardness of computing equilibria due to Gilbow-Zemel.

This is joint work with Pravesh Kothari.


Host:  <mcallester at ttic.edu>Madhur Tulsiani <madhurt at ttic.edu>





Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20191015/6cebbfc7/attachment.html>