Elias Koutsoupias' weblog and personal page

With George Christodoulou and Angelina Vidali [CKV07], we improved the lower bound of the approximation ratio for the mechanism-design version of scheduling unrelated machines. The problem was proposed and studied in the 1998 seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n, where n is the number of machines. Their paper brought to the attention of the CS theory community the notion of mechanism design and its algorithmic issues. Despite the central role of the scheduling problem in this area, there was no improvement since the original paper of Nisan and Ronen. We improved the lower bound from 2 to 2.41.

2006.08.25-12:09.00
/Research/Game Theory | 0 writebacks | permanent link

With George Christodoulou, we considered the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. We showed that for general (asymmetric) games, the price of anarchy of maximum social cost is \Theta(\sqrt{N}), where N is the number of players. For all other cases of symmetric or asymmetric games and for both maximum and average social cost, the price of anarchy is 5/2.

The paper CK05 will appear in STOC 2005. Similar results, for the case of total latency cost function, were obtained by Awerbuch, Azar, and Epstein. Their paper will also appear in STOC 2005.

2005.02.14-15:33.00
/Research/Game Theory | 0 writebacks | permanent link

With George Christodoulou, we considered the price of stability, which is the optimistic price of anarchy (the ratio of the best equilibrium over the optimal allocation), for Nash and correlated equilibria. We showed that for linear congestion games the price of stability is between 1.577 and 1.6 for dominant strategies, Nash, and correlated equilibria. This holds for the average (sum) social cost. For the max social cost, the price of stability is \Theta(\sqrt{N}), where N is the number of players.

The results can be found in CK05b (submitted to ICALP’05). In the same paper, we extended some of the results of our STOC 05 (and also of the STOC’05 paper of Awerbuch, Azar, Epstein) to correlated equilibria.

2005.02.14-15:32.00
/Research/Game Theory | 0 writebacks | permanent link

Here is a list of my publications from my old personal page—until I populate this weblog with references to these papers.

2004.05.11-10:09.00
/Research/Publications | 3 writebacks | permanent link

In a system with selfish users, the system may run at suboptimality. In CKN04, we propose coordination mechanisms as a way to improve the performance. Coordination mechanisms bring together online algorithms and the price of anarchy in a nice framework with challenging problems.

I also wrote a simple exposition article on the topic in the Bulletin of EATCS which I expanded for the SIGACT News.

2004.05.11-09:23.00
/Research/Game Theory | 0 writebacks | permanent link

The k-server problem is the central problem in the area of online algorithms. In my PhD thesis Kou94 and together with my friend and advisor Christos Papadimitriou KP95, we showed that the Work Function Algorithm has competitive ratio 2k-1; the previous bound, showed by Fiat-Rabani-Ravid and by Grove-Bartal, was exponential in k. Ten years later (as of this writing), the bound 2k-1 is still the best known. The k-server conjecture which states that there is a k-competitive algorithm remains the most challenging problem in the area of online algorithms.

I published a simpler proof of the 2k-1 bound in Kou99. I also published two more papers on the topic: in KP96 we proved the k-server conjecture for metric spaces of k+2 points and in BK04 we proved the conjecture for a few more special cases of metric spaces (line and weighted star).

2004.05.10-23:15.00
/Research/Online Algorithms | 7 writebacks | permanent link

In the paper KP99 with Christos Papadimitriou, we study the degradation in performance due to selfish behavior of the users. The paper is not technically deep but it raised an important question and had a huge impact. Together with a few other pioneering papers, such as Ronen and Nisan’s work on mechanism design, it opened up a beautiful new field in the intersection of Computer Science and Game Theory.

In this paper we view users as players in a non-cooperative game that play at the worst-case Nash equilibrium and compare with the optimal allocation. We initially called this the coordination ratio of the system (to relate it with the competitive ratio and approximation ratio); later Christos Papadimitriou called it the price of anarchy, and the latter term stuck.

In the paper we show that the price of anarchy for 2 facilities (machines, links) is exactly 3/2 and gave weak bounds for more facilities. In a later paper KMS03 with Marios Mavronikolas and Paul Spirakis, we showed tight bounds. Independently, Czumaj and Voecking proved a similar result but greatly expanded it to non-uniform facilities (see a nice review article by Czumaj).

2004.05.10-21:43.00
/Research/Game Theory | 2 writebacks | permanent link