Elias Koutsoupias
Professor of Computer Science
University of Oxford
Department of Computer Science University of Oxford Wolfson Building, Parks Road Oxford, OX1 3QD, UK Office: 368 Tel: +44 (0) 1865 610738 Email: eliας@cs.ox.ac.uk 

Short Biography
I am a professor of computer science at the University of Oxford.
My research interests include algorithmic aspects of game theory, economics and networks, online algorithms, decisionmaking under uncertainty, design and analysis of algorithms, computational complexity.
I received the Gödel Prize of theoretical computer science in 2012 for my work on the price of anarchy, in reference to laying the foundations of algorithmic game theory. I was also the recipient of the ERC Advanced Grant “Algorithms, Games, Mechanisms, and the Price of Anarchy”.
I previously held faculty positions at the University of California, Los Angeles (UCLA), and the University of Athens. I studied at the National Technical University of Athens (B.S. in electrical engineering) and the University of California, San Diego (Ph.D. in computer science).
Teaching
 Design and analysis of algorithms, Hilary Term 202122
 Design and analysis of algorithms, Hilary Term 202021
 Probability and Computing, Hilary Term 201819
 Probability and Computing, Hilary Term 201718
 Probability and Computing, Hilary Term 201617
Research interests
Here are some of my papers. An almost complete list can be found at DBLP and at Google Scholar.
Price of anarchy
The concept of the price of anarchy appeared in a joint paper with Christos Papadimitriou in 1999:
 Worstcase 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 redesign 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)
Mechanism design
Part of my work is about the NisanRonen conjecture, a central problem in algorithmic mechanism design. Recently, with George Christodoulou and Annamaria Kovacs, we have made significant progress to validate the conjecture.
 On the NisanRonen conjecture  FOCS 2021 (with George Christodoulou and Annamaria Kovacs)
 On the NisanRonen conjecture for submodular valuations  STOC 2020 (with George Christodoulou and Annamaria Kovacs)
We have also proved positive results for special inputs.
 Truthful allocation in graphs and hypergraphs  ICALP 2021 (with George Christodoulou and Annamaria Kovacs)
Here are some of my older papers on this topic.
 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
Gametheoretic issues of blockchains
Bitcoin and blockchains raise some challenging gametheoretic questions.
The following papers study equilibria of mining games:
 Blockchain mining games (with Aggelos Kiayias, Maria Kyropoulou, and Yiannis Tselekounis)
 Energy equilibria in proofofwork mining (with Amos Fiat, Anna Karlin, and Christos Papadimitriou)
 Fairness and efficiency in dagbased cryptocurrencies (with Georgios Birmpas, Philip Lazos, and Francisco MarmolejoCossio)
 Blockchain mining games with pay forward (with Philip Lazos, Paolo Serafino, and Foluso Ogunlana)
The next paper is about incentivising blockchain stakeholders to organize into pools
 Reward sharing schemes for stake pools (with Lars Brünjes, Aggelos Kiayias, and AikateriniPanagiota Stouka)
Optimal auctions
Part of my research focuses on designing auctions that extract optimal profit in Bayesian settings. At the heart of it is a duality framework with partial differential inequalities, which is useful for suggesting an optimal auction and for proving its optimality.
 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)
Online algorithms
A large part of my research is about online algorithms.
The following is a review article on the kserver problem:
This old paper surprisingly remains the best result on the notorious kserver conjecture:
 On the kserver conjecture (with Christos Papadimitriou)
Here are some recent relevant papers on the kserver problem and its variants
 Towards the kserver conjecture: A unifying potential, pushing the frontier to the circle  ICALP 2021 (with Christian Coester)
 The online ktaxi 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)
Other
My research extends to many other areas. Here are a few examples.
Beyond worstcase analysis
With Anna Karlin, we authored the chapter “Beyond competitive analysis” in the recent collection “Beyond worstcase analysis” (edited by Tim Roughgarden). It is partially based on
 Beyond competitive analysis (with Christos Papadimitriou)
Distributed computing
Given a finite task, is there a waitfree distributed algorithm for it? With Eli Gafni, we showed that this problem is undecidable even for extremely simple cases.
 Threeprocessor tasks are undecidable (with Eli Gafni)
Traveling salesman problem
With Michelangelo Grigni and Christos Papadimitriou, we gave an approximation scheme for a special case of the Euclidean version of TSP, which was soon superceded by Sanjeev Arora’s more general result.
 An approximation scheme for planar graph TSP (with Michelangelo Grigni and Christos Papadimitriou)