Algorithmic Game Theory

In the problems we consider in this group, we usually try to optimize some goal function while dealing with selfish agents that may have separate and conflicting goals, and that may lie to us in order to improve their own goal function. In algorithmic mechanism design, we ensure that it is in the best interest of the agents to tell us the truth. We design mechanisms with money and social choice rules without monetary transfers. We also examine the price of anarchy and price of stability to measure quality of equilibria for various problems.

Research Area

Internet users and service providers act selfishly and spontaneously, without an authority that monitors and regulates network operation in order to optimize global criteria (such as total delay or total utility of an allocation). An interesting and topical question is how much performance is lost because of this. This generates new algorithmic problems, in which we investigate the cost of the lack of coordination, as opposed to the lack of information (online algorithms) or the lack of unbounded computational resources (approximation algorithms). The future of much of the complex technology that we are developing today depends on our ability to ensure that participants cooperate despite their diverse goals and interests.

Realizing that some performance loss is unavoidable, there are several directions in which we work, using techniques from game theory, approximation algorithms, and distributed computing. On a fundamental level, we model and analyze user behavior, e.g., by stuying stability properties of a system or convergence of natural dynamics for interaction. For example, we study properties of dynamics and equilibria in congestion games for traffic systems, stable matching problems for network design, or market equilibria for assigning goods to consumers. Based on these insights, we design algorithms for equilibrium computation, e.g., in traffic or market models. To evaluate system performance in equilibrium, we compare equilibria to optimal solutions that could be reached in a centralized setting, where there is a single controller and no freedom for the agents. The price of stability is the ratio of best Nash equilibrium and the best optimal design. The best Nash equilibrium is the optimal solution that can be proposed from which no user will 'defect'. In contrast, when there is no designer to compute and propose a particular solution, we are interested in evaluating the loss to the system due to its deliberate lack of coordination. This worst-case ratio for Nash equilibria is known as the price of anarchy. More generally, in scenarios without Nash equilibria, we are interested in robust performance guarantees that apply to less stringent equilibrium concepts, such as distributions of play arising in natural best-response dynamics or no-regret learning algorithms.

Understanding the price of anarchy is a prerequisite for setting rules and designing protocols for systems with rational agents. This area is commonly known as algorithmic mechanism design. The canonical problem is selling a number of goods to bidders while ensuring truthful revelation of private data (e.g., valuation for goods and services, or willingness to pay) in order to optimize social welfare or revenue. This requires using an auction mechanism based on a suitable approximation algorithm for the problem at hand, which is combined with suitable payments rules to ensure truthfulness of rational bidders. More generally, designing algorithms and protocols for good performance with rational users is a central problem in many systems. Examples include designing routing protocols for traffic systems, scheduling rules for load balancing, profit or cost sharing rules in networks, or voting rules for elections. In some cases, monetary transfers might not be available or desired (e.g., in voting problems), which requires to study social choice problems and mechanisms without money.

Sample Publications

  • Sayan Bhattacharya, Martin Hoefer, Chien-Chung Huang, Telikepalli Kavitha, Lisa Wagner. Maintaining Near-Popular Matchings. Proc. ICALP 2015.
  • , , , . ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria. Proc. ICALP

  • , . Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange. Proc. EC .
  • , , , , . Truthful Mechanism Design via Correlated Tree Rounding. Proc. EC .
  • Paul Dütting, Thomas Kesselheim, Eva Tardos. Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round. Proc. EC 2015.
  • Paul Dütting, Thomas Kesselheim. Algorithms against Anarchy: Understanding Non-Truthful Mechanisms. Proc. EC 2015.
  • , Robert Kleinberg, Eva Tardos. Smooth Online Mechanisms: A Game-Theoretic Problem in Renewable Energy Markets. Proc. EC 2015.
  • , , . Hedonic Coalition Formation in Networks. Proc. AAAI
  • Tobias Harks, Martin Hoefer, Kevin Schewior, Alexander Skopalik. Routing Games with Progressive Filling. Proc. INFOCOM 2014.
  • Sayan Bhattacharya, Sungjin Im, Janardhan Kulkani, Kamesh Munagala. Coordination Mechanisms from (Almost) All Scheduling Policies. Proc. ITCS 2014.
  • Martin Hoefer, Lisa Wagner. Locally Stable Marriage with Strict Preferences. Proc. ICALP 2013.
  • Ran Duan, Kurt Mehlhorn. A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. Proc. ICALP 2013.
  • Elliot Anshelevich, Onkar Bhardwaj, Martin Hoefer. Friendship and Stable Matching. Proc. ESA 2013.
  • Sayan Bhattacharya, Elias Koutsoupias, Janardhan Kulkarni, Stefano Leonardi, Tim Roughgarden, Xiaoming Xu. Near-optimal Multi-unit Auctions with Ordered Bidders. Proc. EC 2013.
  • Martin Hoefer, Thomas Kesselheim, Berthold Vöcking. Truthfulness and Stochastic Dominance with Monetary Transfers. Proc. EC 2013.
  • Leah Epstein, Asaf Levin, Rob van Stee. A Unified Approach to Truthful Scheduling on Related Machines. Proc. SODA 2013