At the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Venue: Room LC001, LHC - Lecture Hall Complex, Opposite CSE Building, IIT Bombay
Date: 10th December 2019
Since its inception, complexity has played a central role in algorithmic game theory. One of the most foundational results in this field is the PPAD-hardness of computing a Nash equilibrium. The complexity of vote manipulation is another classic, negative result in this context. Indeed, the study of complexity of game-theoretic solution concepts has led to renewed interest in complexity classes, such as PPAD and PLS, as well as the introduction of new classes, e.g., CLS. Besides computational complexity, a rich literature has also emerged that studies other notions such as communication complexity, query complexity, and menu-size complexity.​
The objective of this workshop is to bring together interested researchers to learn and discuss results on complexity in game theory. Towards this end, the workshop will combine presentations on recent research and tutorial-style talks, along with discussions on interesting, open problems. The encompassing theme of this workshop is aimed at bringing together a diverse audience.
On the Communication-Distortion Tradeoff in VotingAbstract: In the standard model of voting, voters express ranked preferences over alternatives and the voting rule aggregates them into a collective decision. The implicit utilitarian approach to voting posits that these expressed ranked preferences stem from underlying cardinal preferences and proposes to minimize the distortion (i.e. the worst-case approximation of social welfare subject to the available information). But then why ask for rankings? What if we ask the voters to report some other information about their cardinal preferences? How much can we minimize the distortion if we are willing to ask k bits of information from each voter? We survey recent results which chart the Pareto-frontier of the tradeoff between communication complexity and distortion in voting. Based on joint work with Debmalya Mandal, Ariel D. Procaccia, and David Woodruff.
Complexity Theory and Algorithmic Game Theory: Some New ConnectionsAbstract: We survey three recent applications of complexity theory to algorithmic game theory. First, we explain when and how communication and computational lower bounds for algorithms for an optimization problem translate to lower bounds on the price of anarchy (POA) in games derived from the problem. This is a new approach to POA lower bounds, based on reductions in lieu of explicit constructions. These lower bounds are particularly significant for problems of designing games that have only near-optimal equilibria, ranging from the design of simple combinatorial auctions to the existence of effective tolls for routing networks. Second, we study "the borders of Border's theorem", a fundamental result in auction design that gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment. We explain a complexity-theoretic barrier that indicates, assuming standard complexity class separations, that Border's theorem cannot be extended significantly beyond the state-of-the-art. Finally, we explain "why prices need algorithms," in the sense that the guaranteed existence of pricing equilibria (like Walrasian equilibria) is inextricably connected to the computational complexity of related optimization problems: demand oracles, revenue-maximization, and welfare-maximization. This connection implies a host of impossibility results, and suggests a complexity-theoretic explanation for the lack of useful extensions of the Walrasian equilibrium concept. Includes joint work with Parikshit Gopalan, Noam Nisan, and Inbal Talgam-Cohen.
Popular Matchings: Good, Bad, and MixedAbstract: We consider the landscape of popular matchings in a bipartite graph where every vertex has strict preferences over its neighbors. Algorithmically speaking, this landscape seems to have only a few bright spots. However relaxing popular matchings to popular mixed matchings makes several hard problems tractable.
Computability of Equilibria in Two-Player GamesAbstract: One of the most extensively studied problems within algorithmic game theory is the computability of Nash equilibrium, especially in two-player games. Given that the general case succumbs to PPAD-completeness, even for inverse polynomial approximation, there has been extensive work on finding efficient algorithms for subclasses of games as well as obtaining conditional lower bound. In this talk, I will discuss a (non-enumerative) algorithmic tool to solve a class of rank-1 games (rank-2 and beyond is PPAD-hard), and unconditional lower bounds under the sum-of-squares algorithmic framework. This framework is powerful enough to capture 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.
Based on joint works with B. Adsul, J. Garg, P. Kothari, and M. Sohoni)
Towards Efficient Almost Envy-Free AllocationsAbstract: We consider the classical problem of dividing indivisible resource among agents "fairly". The quintessential notion of fairness is "Envy-Freeness", where every agent values his own bundle (resources allocated to him) at least as much as the bundles of the other agents. However, envy-free allocations do not exist in general even in the simplest setting of two agents and one good. Therefore, we look into the notion of fairness closest to envy-freeness: "Envy-Freeness up to any good" (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even with three agents. However, we can find almost EFX allocations with many desirable properties. Henceforth, we look into the aspect of finding almost EFX allocations with good guarantees on efficiency. Common efficiency measures include "Pareto-Optimality" and "Nash Social Welfare" (product of the utilities). We study some very recent results that hint at the existence of complete EFX allocations that are not too inefficient (only for additive valuations). At the same time we also highlight some major efficiency barriers for EFX; in a sense that it demands too much "fairness" and requires some trade-offs with efficiency.
Based on joint work with Kavitha Telikepalli, Kurt Mehlhorn and Alkmini Sgouritsa
Communication complexity of mixed Nash equilibrium in potential gamesAbstract: We prove communication complexity lower bounds for (possibly mixed) Nash equilibrium in potential games. In particular, we show that finding a Nash equilibrium requires $\poly(N)$ communication in two-player $N \times N$ potential games, and $2^{\poly(n)}$ communication in $n$-player two-action games. To the best of our knowledge, these are the first results to demonstrate hardness in any model of (possibly mixed) Nash equilibrium in potential games. We extend these lower bounds to the class of congestion games.
