Elias Koutsoupias
Professor of Computer Science
University of Oxford
Department of Computer Science
Wolfson Building, Parks Road
Oxford OX1 3QD, UK
Office 363 · +44 (0)1865 610738
firstname.surname@cs.ox.ac.uk
Short Biography
I am a professor of computer science at the University of Oxford.
Before Oxford, I held faculty positions at the University of California, Los Angeles (UCLA) and the University of Athens. I studied electrical engineering at the National Technical University of Athens and received my PhD in computer science from the University of California, San Diego (UCSD).
My research is in algorithmic game theory, mechanism design, and online algorithms, and more broadly in decision-making under uncertainty, the design and analysis of algorithms, and computational complexity. Recently, with George Christodoulou and Annamaria Kovács, I proved the Nisan–Ronen conjecture in algorithmic mechanism design, and with Christian Coester and Marek Zbysiński, I proved the k-server conjecture in online algorithms.
I received the Gödel Prize in 2012 for introducing the price of anarchy. I hold the ERC Advanced Grant “Frontiers of Algorithmic Mechanism Design: Limitations and Promises” (FRAMED, 2026–2031), and previously held the ERC Advanced Grant “Algorithms, Games, Mechanisms, and the Price of Anarchy” (ALGAME).
Prospective students and postdocs
I have a couple of open PhD positions, in any area of my research: algorithmic game theory, mechanism design, online algorithms, and algorithms more generally. To apply, see the DPhil in Computer Science admissions page.
There will also be postdoctoral positions in algorithmic mechanism design, funded by my ERC grant FRAMED. I will advertise them on the FRAMED page and on the usual mailing lists.
Candidates should have a strong background in algorithms, theoretical computer science, game theory, or discrete mathematics. Feel free to email me (firstname.surname@cs.ox.ac.uk) with questions.
Teaching
Current
- Advanced Algorithmic Game Theory, Hilary Term 2026-27
Previous
- Design and analysis of algorithms, Hilary Term 2024-25
- Design and analysis of algorithms, Hilary Term 2023-24
- Design and analysis of algorithms, Hilary Term 2022-23
- Design and analysis of algorithms, Hilary Term 2021-22
- Design and analysis of algorithms, Hilary Term 2020-21
- Probability and Computing, Hilary Term 2018-19
- Probability and Computing, Hilary Term 2017-18
- Probability and Computing, Hilary Term 2016-17
Research interests
Here are some of my papers. An almost complete list can be found at DBLP and at Google Scholar.
Online algorithms
A large part of my research is about online algorithms.
The k-server conjecture, posed by Manasse, McGeoch, and Sleator in 1988, is a central problem in online algorithms. With Christian Coester and Marek Zbysiński, we proved it:
- The k-server conjecture is true - arXiv 2026 (with Christian Coester and Marek Zbysiński)
The previous best bound for general metric spaces, 2k-1, was established in
- On the k-server conjecture - J. ACM 1995 (with Christos Papadimitriou)
The following is a review article on the k-server problem:
- The k-server problem - Computer Science Review 2009
Here are some other 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; ACM TALG 2021 (with Christian Coester and Philip Lazos)
- Weak adversaries for the k-server problem - FOCS 1999
Another challenging online problem is the carpool fairness problem:
- Carpooling in social networks - ICALP 2016 (with Amos Fiat, Anna Karlin, Claire Mathieu, and Rotem Zach)
Combining markets and online algorithms:
- Online market intermediation - ICALP 2017 (with Yiannis Giannakopoulos and Philip Lazos)
Price of anarchy
The concept of the price of anarchy appeared in a joint paper with Christos Papadimitriou in 1999:
- Worst-case equilibria - STACS 1999 (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 - STOC 2005 (with George Christodoulou)
- On the price of anarchy and stability of correlated equilibria of linear congestion games - ESA 2005 (with George Christodoulou)
- On the performance of approximate equilibria in congestion games - ESA 2009; Algorithmica 2011 (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 - ICALP 2004; TCS 2009 (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 - STACS 2019 (with Kurtuluş Gemici, Barnabé Monnot, Christos Papadimitriou, and Georgios Piliouras)
Mechanism design
Together with George Christodoulou and Annamaria Kovács, 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; J. ACM 2026 (with George Christodoulou and Annamaria Kovács)
- A proof of the Nisan-Ronen conjecture - an overview - SIGecom Exchanges 2023 (with George Christodoulou and Annamaria Kovács)
Earlier papers made progress on special cases and developed useful mechanism characterizations.
- On the Nisan-Ronen conjecture - FOCS 2021 (with George Christodoulou and Annamaria Kovács)
- On the Nisan-Ronen conjecture for submodular valuations - STOC 2020; SIAM J. Comput. 2025 (with George Christodoulou and Annamaria Kovács)
We have also established positive results for specific input instances.
- Truthful allocation in graphs and hypergraphs - ICALP 2021; ACM TEAC 2025 (with George Christodoulou and Annamaria Kovács)
- The communication complexity of combinatorial auctions in graphs - STACS 2026 (with George Christodoulou, Annamaria Kovács, and Ioannis Vlachos)
The following are some of my earlier publications on this or related topics.
- A lower bound for scheduling mechanisms - Algorithmica 2009 (with George Christodoulou and Angelina Vidali)
- A lower bound of 1+φ for truthful scheduling mechanisms - MFCS 2007; Algorithmica 2013 (with Angelina Vidali)
- Mechanism design for fractional scheduling on unrelated machines - ICALP 2007 (with George Christodoulou and Annamaria Kovács)
- Scheduling without payments - SAGT 2011; Theory Comput. Syst. 2014
Game-theoretic issues of blockchains
Blockchains raise some challenging game-theoretic questions.
The following papers study equilibria of mining games:
- Blockchain mining games - EC 2016 (with Aggelos Kiayias, Maria Kyropoulou, and Yiannis Tselekounis)
- Energy equilibria in proof-of-work mining - EC 2019 (with Amos Fiat, Anna Karlin, and Christos Papadimitriou)
- Fairness and efficiency in DAG-based cryptocurrencies - Financial Cryptography 2020 (with Georgios Birmpas, Philip Lazos, and Francisco Marmolejo-Cossío)
- Blockchain mining games with pay forward - WWW 2019 (with Philip Lazos, Paolo Serafino, and Foluso Ogunlana)
The next papers explore mechanisms for incentivising blockchain stakeholders to organize into pools:
- Reward sharing schemes for stake pools - EuroS&P 2020 (with Lars Brünjes, Aggelos Kiayias, and Aikaterini-Panagiota Stouka)
- Pool formation in oceanic games: Shapley value and proportional sharing - AFT 2025 (with Aggelos Kiayias, Evangelos Markakis, and Panagiotis Tsamopoulos)
The following paper studies how blockchain protocols should price their resources:
- One-dimensional vs. multi-dimensional pricing in blockchain protocols - WINE 2025 (with Aggelos Kiayias, Giorgos Panagiotakos, and Kyriaki Zioga)
Optimal auctions
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 - EC 2014; SIAM J. Comput. 2018 (with Yiannis Giannakopoulos)
- Selling two goods optimally - ICALP 2015; Inf. Comput. 2018 (with Yiannis Giannakopoulos)
- The FedEx problem - EC 2016 (with Amos Fiat, Kira Goldner, and Anna Karlin)
Other
My research extends to several other areas. Here are a few examples.
EFX allocations on graphs
EFX envy-freeness has received considerable attention recently. The following paper considers the special case where each good can only be allocated between two specific agents.
- Fair allocation in graphs - EC 2023 (with George Christodoulou, Amos Fiat, and Alkmini Sgouritsa)
Computational complexity
With Matan Gilboa, Paul Goldberg, and Noam Nisan, we study the complexity of unambiguous problems in the second level of the polynomial hierarchy.
- Complexity of unambiguous problems in Σ₂ᴾ - arXiv 2025 (with Matan Gilboa, Paul Goldberg, and Noam Nisan)
Beyond worst-case analysis
The chapter “Beyond Competitive Analysis,” co-authored with Anna Karlin, appears in Tim Roughgarden’s collection “Beyond the Worst-Case Analysis of Algorithms” (2020) and draws partially on
- Beyond competitive analysis - FOCS 1994; SIAM J. Comput. 2000 (with Christos Papadimitriou)
Distributed computing
Given a finite task, is there a wait-free distributed algorithm for it? With Eli Gafni, we showed that this problem is undecidable even for extremely simple cases.
- Three-processor tasks are undecidable - SIAM J. Comput. 1999 (with Eli Gafni)
Traveling salesman problem
With Michelangelo Grigni and Christos Papadimitriou, we provided an approximation scheme for a limited case of Euclidean TSP, which was subsumed by Sanjeev Arora’s more general solution.
- An approximation scheme for planar graph TSP - FOCS 1995 (with Michelangelo Grigni and Christos Papadimitriou)