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

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

I am a professor at the University of Athens. My research interests are in algorithms and complexity and include algorithmic game theory, its applications to the internet, the web, and the economy, online algorithms, and more-generally decision-making under uncertainty.

I got my undergraduate degree in Electrical Engineering from the National Technical University of Athens and my PhD in Computer Science from the University of California in San Diego (UCSD), in 1994. The next 8-9 years I was assistant and tenured associate professor at the University of California, Los Angeles (UCLA). Since 2000, I have been a professor at the University of Athens.

During the spring semester of 2010-11, I am on leave at the Center of Rationality of the Hebrew University for the special semester on Algorithmic Game Theory organized by Noam Nisan and Michal Feldman.

My current professional activities include: I am co-chair of WINE 2011, co-organizer of GREAT 2011, and program committee member of SAGT 2011 and ICALP 2012 (track A). I am also in the editorial board of the Journal of Computer and System Sciences (JCSS).

Here is a more extended CV.

Research

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.

more...

Talks

Some of my recent presentations and lectures are:
Mechanism design for scheduling unrelated machines
A lecture I gave at the AEOLUS school in Paderborn in April 2008.
Game-theoretic mechanisms
An extended lecture I gave at the DYNAMO school in Reykjavik in July 2008.
Competitive analysis of aggregate max in windowed streaming
A presentation in ICALP, Rhodes, July 2009.
Approximate Price of Anarchy and Stability
An invited talk in SAGT, Paphos, October 2009.
Approximate Price of Anarchy and Stability
A slightly different version presented in a workshop at CRM, Barcelona, November 2009.
Online competitive auctions
For celebrating the 60th birthday of Josep Diaz.
Online competitive auctions
A different version of the previous talk given at the Hebrew University for the special semester in Algorithmic Game Theory.
Contention resolution for congestion games
At the CS department of the Hebrew University.
Online competitive auctions
A different version of the previous talks given at the Technion.

Courses

The fall semester of the academic year 2011-12, I teach the following courses

Math 4 CS
A course on advanced discrete math for undergraduate students.
Algorithms
A course for graduate and advanced undergraduate students which covers the fundamentals of algorithmic design and analysis.
Algoritmic Game Theory
A course for graduate students which covers the recent developments in computational issues of games, the price of anarchy, and mechanisms.

I also plan a project for involving undergraduate students in research.

Research for undergrads
The idea is to create a small group of a few committed undergrads and attempt to solve an open problem. The students will be exposed to the process of conducting research and learning how to pursue an academic/research career. Last year, the response from the students was extremely positive and I enjoyed the process, so I plan to repeat it in the coming academic year.

You can find more information about these courses—and about courses of past years—by following the link Courses.

For students

If you want a recommendation letter, or you are interested in an undergraduate or MS thesis, please make sure you follow these instructions.