Algorithms Seminar

Games, Equilibria, and Evolution

Speaker:Ruta Mehta
Date: Thursday, March 24, 2016
Time: 1:00pm - 2:00pm
Location: D344 LSRC, Duke

Abstract

The tremendous growth of online markets, ad auctions, and social network communities, where agents interact to achieve their own goals, often selfish, has created a need to apply game theoretic solution concepts more than ever before. In this talk I will discuss one of the most important solution concept in game theory, namely Nash equilibrium, for its computational and application aspects. Recently a remarkable connection was discovered between evolution under sexual reproduction and coordination games. Proceeding along these lines I will show some new insights on genetic diversity.

Towards efficient computation, finding Nash equilibrium in two-player normal form game (2-Nash) is one of the most extensively studied problem. Such a game can be represented by two payoff matrices A and B, one for each player. 2-Nash is PPAD-complete in general, while in case of zero-sum games (B=-A) the problem reduces to LP and hence is in P. Extending the notion of zero-sum, in 2005, Kannan and Theobald defined rank of game (A, B) as rank(A+B), e.g., rank-0 are zero-sum games. They asked for an efficient algorithm for constant rank games , where the primary difficulty was disconnected solution set, even in rank-1 games . I will answer this question affirmatively for rank-1 games, and negatively for games with rank three or more (unless PPAD=P); the status of rank-2 games remains unresolved. In the process I obtain a number of other results, including a simpler proof of PPAD-hardness for 2-Nash.

Biography

Dr. Ruta Mehta is an assistant professor in the Department of Computer Science at University of Illinois at Urbana-Champaign. Her research lies at the intersection of theoretical computer science, game theory, and mathematical economics, and their applications to evolution, dynamical systems and learning. She has worked on computability of equilibria, both market and Nash, under various settings, and also on understanding the impact of strategic behavior in multi-agent situations. In addition she has explored learning economic parameters through revealed preferences, fair-division, and genetic evolution under sexual reproduction. She did her PhD from Indian Institute of Technology, Bombay, under the guidance of Prof. Milind Sohoni, and postdoc from Georgia Tech under supervision of Prof. Vijay V. Vazirani. She spent a semester at Simons Institute at UC Berkeley before joining UIUC. She won ACM India Doctoral Dissertation Award 2012. In 2014, she was conferred the Best Postdoctoral Research Award by CoC at Georgia Tech.

Hosted by:
Debmalya Panigrahi