Ariel Schvartzman Cohenca will present his generals exam Thursday, May 25, 2017 at 1pm in CS 401. The members of his committee are: Matt Weinberg (adviser), Gillat Kol, and Zeev Dvir. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. While Nash equilibria are arguably the most studied notion of equilibrium in strategic games, recent results regarding their communication and computational complexity have undermined their prevalence as a predictable solution concept when agents are computationally bounded. In particular, results show that two players cannot converge to any approximate Nash equilibria in the limited communication setting where each player only knows its utility function. For the case of 2-player games, it has been recently shown that even computing approximate Nash equilibria requires poly(n) bits of communication[BR16]. In addition even in the setting where all the payoffs matrices are known Nash equilibria seem to be unnatural due to their computational hardness. Computing any exact Nash equilibrium is known to be PPAD-complete, making it unlikely to have any polynomial time algorithm [CDT09, Daskalakis2009]. Furthermore, it has been shown that under the Exponential Time Hypothesis (ETH) for the class PPAD, eps-approximate Nash equilibria cannot be computed in time faster than quasi-polynomial in the number of strategies per player[Rubinstein16a]. This almost exactly matches the algorithm of [LMM03]. These results suggest that approximate Nash equilibria may not be efficiently computable. Correlated equilibria arise as an alternative equilibrium concept. This notion, introduced in the seminal work of [Aumann74], allows agents to cooperate in order to reach stability. Informally, a strategy profile is a correlated equilibrium when a referee or trusted party can draw strategy samples according to it and recommend them to the players in such a way that they have no incentive to consistently deviate, assuming everyone else plays according to their recommendation. Computationally, correlated equilibria are in sharp contrast to Nash equilibria: there exists an ellipsoid-based algorithm to compute exact correlated equilibrium polynomial time even for multi-player games for a large (but not universal) class of games including graphical games, anonymous games, congestion games and scheduling games[PR2008]. Unfortunately this result is still unsettling: one can imagine many settings where a referee may not have access to all utility functions or where players may not want to share such information with a referee. With this in consideration it becomes more natural to ask whether there is an efficient communication protocol for computing approximate correlated equilibria better than the naive one where each player sends their payoff matrix to a referee who computes the answer. Given recent developments, this is the next fundamental problem between communication complexity and algorithmic game theory that needs to be addressed, both in terms of communication and query complexity. In this work we address the question posed by [BR16] of providing lower bounds for the communication complexity of approximate correlated equilibrium in 2-player games. The arguments used on the lower bound proof rely on tools from information theory, which lower bounds communication cost. While this talk focuses on a single result, my research interests lie in understanding the complexity of approximate solution concepts. There are different lenses through which we analyze problems when studying equilibria: computation, communication, query (amongst others). Other similar projects I have worked on involve bounds for the menu complexity of optimal and approximate mechanism design and understanding the efficiency loss of ‘simple auctions’ when compared to their optimal counterparts in specific settings. Joint work with Young Kun Ko. Reading list: - Algorithmic Game Theory. E. Tardos, T. Roughgarden, V. Vazirani, N. Nisan. 2007. - 20 Lectures in Algorithmic Game Theory. T. Roughgarden. 2016. Papers: - Settling the complexity of computing approximate two-player Nash equilibria. A. Rubinstein. 2016. - Inapproximability of Nash Equilibrium. A. Rubinstein. 2015. - Adaptive procedure, correlated equilibrium, no regret, regret-matching, simple strategies. S. Hart, A. Mas-Collel. 2000. - Communication complexity of approximate Nash equilibria. Y. Babichenko, A. Rubinstein. 2016. - Playing Large Games Using Simple Strategies. R. Lipton, E. Markakis, A. Mehta. 2003 - How long to equilibrium? The communication complexity of uncoupled equilibrium procedures. S. Hart, Y. Mansour. 2010. - The communication complexity of uncoupled nash equilibrium procedures. S. Hart, Y. Mansour. 2007. - The complexity of computing a Nash equilibrium. C. Daskalakis, A. Goldberg, C. Papadimitriou. 2008. - Settling the Complexity of Computing Two-player Nash Equilibria. X. Chen, X. Deng, S. Teng. 2009. - Computing Equilibria: A Computational Complexity Perspective. T. Roughgarden. 2010. - Communication Complexity (for Algorithm Designers), Chapter 7: Lower Bounds in Algorithmic Game Theory. 2016. - Communication Complexity as a Lower Bound for Learning in Games. V. Connitzer, T. Sandholm. 2004.