Photo of Elias Koutsoupias

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

Previous

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 previous best bound for general metric spaces, 2k-1, was established in

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

Here are some other papers on the k-server problem and its variants:

Another challenging online problem is the carpool fairness problem:

Combining markets and online algorithms:

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:

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

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

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

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

We have also established positive results for specific input instances.

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

Game-theoretic issues of blockchains

Blockchains raise some challenging game-theoretic questions.

The following papers study equilibria of mining games:

The next papers explore mechanisms for incentivising blockchain stakeholders to organize into pools:

The following paper studies how blockchain protocols should price their resources:

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.

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.

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.

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

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.

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.

Last updated: 2026-11-08 Sun 23:07