Elias
Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784
Greece

phone: +30 210 7275122
fax: +30 210 7275114

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.

Here is an (almost) complete list of my publications arranged by topic.

Internet, Games, Power Laws

Elias Koutsoupias: Scheduling without payments. In SAGT 2011. To appear.
G. Christodoulou, E. Koutsoupias, and P. Spirakis. On the performance of approximate equilibria in congestion games. In Algorithmica 61(1): 116-140, 2011
Elias Koutsoupias and George Pierrakos: On the Competitive Ratio of Online Sampling Auctions. WINE 2010: 327-338.
G. Christodoulou, E. Koutsoupias, and A.Kovacs. Mechanism Design for Fractional Scheduling on Unrelated Machines. ACM Transactions on Algorithms 6(2): (2010) G. Christodoulou, E. Koutsoupias, and A. Kovacs. Mechanism Design for Fractional Scheduling on Unrelated Machines. ICALP 2007: 40-52
George Christodoulou and Elias Koutsoupias: Mechanism design for scheduling. Bulletin of the European Association for Theoretical Computer Science (BEATCS) 97:39-59, February 2009.
George Christodoulou, Elias Koutsoupias, Angelina Vidali: A Lower Bound for Scheduling Mechanisms. Algorithmica 55(4): 729-740 (2009).

G. Christodoulou, E. Koutsoupias, and A. Vidali. A lower bound for scheduling mechanisms. SODA 2007: 1163-1170.


Elias Koutsoupias, Christos H. Papadimitriou: Worst-case equilibria. Computer Science Review 3(2): 65-69, 2009.

E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404--413, Trier, Germany, 4--6 March 1999.


George Christodoulou, Elias Koutsoupias, Akash Nanavati: Coordination mechanisms. Theor. Comput. Sci. 410(36): 3327-3336, 2009.
D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis. The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. Theoretical Computer Science, 410(36): 3305-3326, 2009.
G. Christodoulou, E. Koutsoupias, and A. Vidali. A characterization of 2-player mechanisms for scheduling. In ESA, Karlsruhe, Germany, 15-17 September 2008.
E. Koutsoupias, P. Panagopoulou, and P. Spirakis. Selfish Load Balancing Under Partial Knowledge. MFCS 2007: 609-620
E. Koutsoupias and A. Vidali. A Lower Bound of 1+phi for Truthful Scheduling Mechanisms. MFCS, 2007: 454-464.
Georgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, and Martha Sideri. Experiments with an Economic Model of the Worldwide Web. WINE 2005 (Internet and Network Economics: First International Workshop), pages 46-54, Hong Kong, China, December 15-17, 2005.
G. Christodoulou and E. Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games. ESA 2005, 13th Annual European Symposium, pages 59-70, Palma de Mallorca, Spain, October 3-6, 2005.
G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. STOC, pages 67--73, Baltimore, MD,USA, 22--24 May, 2005.
E. Koutsoupias. Coordination mechanisms for congestion games. Sigact News, Vol. 35, No. 4, December 2004, pages 58--71.
C. Brito, E. Koutsoupias, and S. Vaya. Competitive analysis of organization networks or multicast acknowledgement: how much to wait? In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627--635, New Orleans, Louisiana, USA, January 11-14, 2004.
E. Koutsoupias. Selfish task allocation. Bulletin of EATCS, Number 81, pages 79--88, October 2003.
E. Koutsoupias, M. Mavronikolas, and P. Spirakis. Approximate equilibria and ball fusion. Theory of Computing Systems 36(6), pages 683--693, 2003.
A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet. In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), pages 110--122, Malaga, Spain, July 2002.
R. Karp, E. Koutsoupias, C. Papadimitriou, and S. Shenker. Combinatorial optimization in congestion control. In Proceedings of the 41th Annual Symposium on Foundations of Computer Science, pages 66--74, Redondo Beach, CA, 12--14 November 2000.
E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In 16th Annual Symposium on Theoretical Aspects of Computer Science}, pages 404--413, Trier, Germany, 4--6 March 1999.

Online Algorithms

Elias Koutsoupias and George Pierrakos: On the Competitive Ratio of Online Sampling Auctions. WINE 2010: 327-338.
Luca Becchetti, Elias Koutsoupias: Competitive Analysis of Aggregate Max in Windowed Streaming. In ICALP (1) 2009: 156-170.
Elias Koutsoupias: The k-server problem. Computer Science Review 3(2): 105-118 (2009).
C. Brito, E. Koutsoupias, and S. Vaya. Competitive analysis of organization networks or multicast acknowledgement: how much to wait? In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627--635, New Orleans, Louisiana, USA, January 11-14, 2004.
E. Koutsoupias and D. S. Taylor. The CNN problem and other k-server variants. In Theoretical Computer Science, 324(2-3):347--359, September 2004.
Y. Bartal and E. Koutsoupias. On the competitive ratio of the work function algorithm for the k-server problem. In Theoretical Computer Science, 324(2-3):337--345, September 2004.
E. Koutsoupias and A. Nanavati. The online matching problem on a line. Workshop on approximation and online algorithms, pages 179--191, Budapest 2003.
M. Chrobak, E. Koutsoupias, and J. Noga. More on Randomized On-line Algorithms for Caching. Theoretical Computer Science. 290(3): 1997-2008, 2003.
E. Koutsoupias and C. Papadimitriou. Beyond competitive analysis. SIAM Journal on Computing, 30(1):300--317, 2000.
E. Koutsoupias. Weak adversaries for the k-server problem. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York City, NY, pages 444--449, 17--19 October 1999.
X. Deng, E. Koutsoupias, and P. MacKenzie. Competitive implementation of parallel programs. Algorithmica, 23(1):14--30, 1999.
E. Koutsoupias, C. Papadimitriou, and M. Yannakakis. Searching a fixed graph. In International Colloquium on Automata, Languages, and Programming, pages 280--289, Paderborn, Germany, 8--12 July 1996.
E. Koutsoupias and C. Papadimitriou. The 2-evader problem. Information Processing Letters 57(5):249--252, March 1996.
E. Koutsoupias and C. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5):971--983, September 1995.
E. Koutsoupias. On-line algorithms and the k-server conjecture. PhD thesis, University of California, San Diego, La Jolla, California, June 1994.

Approximation Algorithms

G. Christodoulou, E. Koutsoupias, and A. Vidali. A lower bound for scheduling mechanisms. SODA 2007: 1163-1170.
E. Koutsoupias, C. Papadimitriou, and M. Yannakakis. Searching a fixed graph. In International Colloquium on Automata, Languages, and Programming, pages 280--289, Paderborn, Germany, 8--12 July 1996.
M. Grigni, E. Koutsoupias, and C. Papadimitriou. An approximation scheme for planar graph TSP. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 640--645, Milwaukee, Wisconsin, 23--25 October 1995.
E. Koutsoupias, C. H. Papadimitriou, and M. Sideri. On the optimal bisection of a polygon. ORSA Journal on Computing, 4(4):435--438, Fall 1992.

Indexing Schemes

J. M. Hellerstein, E. Koutsoupias, D. P. Miranker, C. H. Papadimitriou, and V. Samoladas. On a model of indexability and its bounds for range queries. Journal of the ACM (JACM) 49(1):35--55, 2002.
E. Koutsoupias and D. S. Taylor. Indexing schemes for random points. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 596--602, Baltimore, Maryland, 17--19 January 1999.
E. Koutsoupias and D. S. Taylor. Tight bounds for 2-dimensional indexing schemes. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Seattle, Washington, June 1--4, 1998.
J. M. Hellerstein, E. Koutsoupias, and C. H. Papadimitriou. On the Analysis of Indexing Schemes. In Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 249--256, Tucson, Arizona, 12--15 May 1997.

Miscellaneous

E. Gafni and E. Koutsoupias. Three-processor tasks are undecidable. SIAM Journal on Computing, 28(3):970--983, 1999.
E. Koutsoupias. Improvements on Khrapchenko's theorem. Theoretical Computer Science, 116(2):399--403, August 1993.
E. Koutsoupias and C. H. Papadimitriou. On the greedy algorithm for satisfiability. Information Processing Letters, 43(1):53--55, August 1992.