Algorithms, Games, Mechanisms, and the Price of Anarchy

The expansion of the Internet and the development of the World Wide Web have significantly changed computer science in the last two decades. The most dramatic change is that while traditional systems are designed, built, and controlled by single organizations, the new systems are shared among many entities with different and sometimes conflicting objectives. The need to understand such systems and to design better ones that can operate as optimally as possible in such environments gave rise to the new vibrant field of Algorithmic Game Theory.

The objective of this project is to bring together a local team of young researchers who will work closely with international collaborators to advance the state of the art of Algorithmic Game Theory and open new venues of research at the interface of Computer Science, Game Theory, and Economics. The project consists mainly of three intertwined research strands: algorithmic mechanism design, price of anarchy, and online algorithms.

Specifically, we will attempt to resolve some outstanding open problems in algorithmic mechanism design: characterising the incentive compatible mechanisms for important domains, such as the domain of combinatorial auctions, and resolving the approximation ratio of mechanisms for scheduling unrelated machines. More generally, we will study centralised and distributed algorithms whose inputs are controlled by selfish agents that are interested in the outcome of the computation. We will investigate new notions of mechanisms with strong truthfulness and limited susceptibility to externalities that can facilitate modular design of mechanisms of complex domains.

We will expand the current research on the price of anarchy to time-dependent games where the players can select not only how to act but also when to act. We also plan to resolve outstanding questions on the price of stability and to build a robust approach to these questions, similar to smooth analysis. For repeated games, we will investigate convergence of simple strategies (e.g., fictitious play), online fairness, and strategic considerations (e.g., metagames). More generally, our aim is to find a productive formulation of playing unknown games by drawing on the fields of online algorithms and machine learning.