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 		photo

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, decision-making 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

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:

  • 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:

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

Part of my work is about the Nisan-Ronen conjecture, a central problem in algorithmic mechanism design. Recently, with George Christodoulou and Annamaria Kovacs, we have made significant progress to validate the conjecture.

We have also proved positive results for special inputs.

Here are some of my older papers on this topic.

Game-theoretic issues of blockchains

Bitcoin and blockchains raise some challenging game-theoretic questions.

The following papers study equilibria of mining games:

The next paper is about incentivising blockchain stakeholders to organize into pools

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.

Online algorithms

A large part of my research is about online algorithms.

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

This old paper surprisingly remains the best result on the notorious k-server conjecture:

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

Another challenging online problem is the carpool fairness problem:

Combining markets and online algorithms:

Other

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

Beyond worst-case analysis

With Anna Karlin, we authored the chapter “Beyond competitive analysis” in the recent collection “Beyond worst-case analysis” (edited by Tim Roughgarden). It is partially based 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 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.

Created: 2021-11-28 Sun 19:50