Elias Koutsoupias / Publications

My most recent work is in algorithmic game theory, mechanism design, and the price of anarchy.

After almost a decade, I proceeded to publish in a journal (CS Review) the paper of STACS 1999 which introduced the notion of price of anarchy (co-authored with Christos Papadimitriou). At the time, we called it "coordination ratio", but later Christos coined the catchy term "price of anarchy". Nobody could predict the impact of this work---including, of course, the committee which rejected it from a conference. Ten years later, it has more than 1000 references to it, according to scholar.google. A recent Feature Column by Joseph Malkevitch (January 2011) of the American Mathematical Society is devoted to the price of anarchy.

There is a lot of recent work on mechanism design without money. Given the outstanding conjecture of Nisan and Ronen on the scheduling problem, a natural problem is to consider mechanism design without payments for the scheduling problem. Surprisingly this is not as hopeless as it may appear at first glance. See my upcoming SAGT 2011 paper for some mildly positive and at the same time tight results.

In WINE 2010 paper with George Pierrakos, we considered auctions from the competitive analysis point of view when the input is presented in a random order: this problem is a variant of the secretary problem but with a different objective.

With George Christodoulou and Paul Spirakis, we studied how much the price of anarchy and the price of stability change when we consider approximate equilibria. We got almost tight results, as functions of the approximation ratio, for both atomic and non-atomic games, generalizing the existing results on exact equilibria. Surprisingly, we used a common approach for both atomic and non-atomic games.

With George Christodoulou and Angelina Vidali, we studied the approximation ratio of truthful mechanisms for the scheduling problem, one of the most central problems in mechanism design proposed by Nisan and Ronen in 1998. We improved the lower bound from 2 to 2.41 and later to 2.61.

We also considered the important question of characterizing the truthful mechanisms. We managed only to partially settle the question for 2 players (machines). This work appeared in ESA 2008.

With George Christodoulou and Annamaria Kovacs, we studied mechanisms with fractional allocations. We showed a lower bound of 2-1/n (where n is the number of players). We also studied task independent mechanisms and we showed that among them, the SQUARE mechanism—which allocates a task with fractions inversely proportional to the square—has optimal approximation ratio, equal to (n+1)/2.

The volume of CS Review which includes the STACS 1999 paper on the price of anarchy consists of a collection of articles to honor Christos Papadimitriou. My contribution was a review article for the k-server problem.

My recent research activity in online algorithms is focused on streaming algorithms. With Luca Becchetti we used competitive analysis to study a simple problem in streaming computing: how to maintain a maximum or almost maximum element of a sliding window with limited memory. Our main result is a surprising low competitive ratio for the aggregate maximum. More precisely when the algorithm has limited memory $k$ and the objective is the sum of the maximum values in memory, the competitive ratio is $1+\Theta(1/k)$. This ratio is both against offline algorithms with the same limitations in memory and against offline algorithms with unlimited memory.