Elias Koutsoupias
Professor of Computer Science
University of Oxford

The concept of the price of anarchy appeared in a joint paper with Christos Papadimitriou in 1999:

• Worst-case equilibria (with Christos Papadimitriou). Its influence was recognized by the Gödel Prize in 2012.

The following papers contain some followup work on the price of anarchy of finite congestion games:

• The price of anarchy of finite congestion games (with George Christodoulou)
• On the price of anarchy and stability of correlated equilibria of linear congestion games (with George Christodoulou)
• On the performance of approximate equilibria in congestion games (with George Christodoulou and Paul Spirakis)

Coordination mechanisms is one way to try to re-design systems to improve their price of anarchy:

• Coordination mechanisms (with George Christodoulou and Akash Nanavati)

The following paper considers the interplay between price of anarchy and social inequality

• Wealth inequality and the price of anarchy (with Kurtuluş Gemici, Barnabé Monnot, Christos Papadimitriou, and Georgios Piliouras)

Together with George Christodoulou and Annamaria Kovacs, we have proved the Nisan-Ronen conjecture, a major open problem in algorithmic mechanism design.

The proof and a general overview of it are in

• A proof of the Nisan-Ronen conjecture - STOC 2023 (with George Christodoulou and Annamaria Kovacs)
• A Proof of the Nisan-Ronen Conjecture - an Overview - SIGecom Exch. (with George Christodoulou and Annamaria Kovacs)

Earlier papers made progress on special cases and developed useful mechanism characterizations.

• On the Nisan-Ronen conjecture - FOCS 2021 (with George Christodoulou and Annamaria Kovacs)
• On the Nisan-Ronen conjecture for submodular valuations - STOC 2020 (with George Christodoulou and Annamaria Kovacs)

We have also established positive results for specific input instances.

• Truthful allocation in graphs and hypergraphs - ICALP 2021 (with George Christodoulou and Annamaria Kovacs)

The following are some of my earlier publications on this or related topics.

• A lower bound for scheduling mechanisms (with George Christodoulou and Angelina Vidali)
• A lower bound of 1+φ for truthful scheduling mechanisms (with Angelina Vidali)
• Mechanism design for fractional scheduling on unrelated machines (with George Christodoulou and Annamaria Kovacs)
• Scheduling without payments

Blockchains raise some challenging game-theoretic questions.

The following papers study equilibria of mining games:

• Blockchain mining games (with Aggelos Kiayias, Maria Kyropoulou, and Yiannis Tselekounis)
• Energy equilibria in proof-of-work mining (with Amos Fiat, Anna Karlin, and Christos Papadimitriou)
• Fairness and efficiency in dag-based cryptocurrencies (with Georgios Birmpas, Philip Lazos, and Francisco Marmolejo-Cossio)
• Blockchain mining games with pay forward (with Philip Lazos, Paolo Serafino, and Foluso Ogunlana)

The next paper explores mechanisms for incentivising blockchain stakeholders to organize into pools

• Reward sharing schemes for stake pools (with Lars Brünjes, Aggelos Kiayias, and Aikaterini-Panagiota Stouka)

The following papers aim to design profit-maximising auctions in Bayesian settings. This is achieved through a duality framework involving partial differential inequalities, which facilitates both the construction and validation of optimal auction designs.

• Duality and optimality of auctions for uniform distributions (with Yiannis Giannakopoulos)
• Selling two goods optimally (with Yiannis Giannakopoulos)
• The FedEx problem (with Amos Fiat, Kira Goldner, and Anna Karlin)

A large part of my research is about online algorithms.

The k-server conjecture is a central and highly challenging problem in online algorithms. Even after many years, this paper remains the state-of-the-art result:

• On the k-server conjecture (with Christos Papadimitriou)

The following is a review article on the k-server problem:

• The k-server problem

Here are some recent relevant papers on the k-server problem and its variants

• Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle - ICALP 2021 (with Christian Coester)
• The online k-taxi problem - STOC 2019 (with Christian Coester)
• The infinite server problem - ICALP 2017 (with Christian Coester and Philip Lazos)

Another challenging online problem is the carpool fairness problem:

• Carpooling in social networks (with Amos Fiat, Anna Karlin, Claire Mathieu, and Rotem Zach)

Combining markets and online algorithms:

• Online market intermediation (with Yiannis Giannakopoulos and Philip Lazos)

My research extends to several other areas. Here are a few examples.