Alkmini received her PhD from the University of Liverpool under the supervision of Dr George Christodoulou. She is currently a postdoctoral researcher at the Max Planck Institute for Informatics. Her main research interests are Algorithmic Game Theory, Mechanism Design and Online and Universal Algorithms.

AG 1, MMCI   Info

AG Audience

English

45 Minutes

Saarbrücken

We study a multicast game in a rooted undirected graph with nonnegative edge costs. A set of terminal vertices or players need to establish connectivity with the root. The social optimum is the minimum Steiner tree. There are several ways to split the edge costs among the users and this is dictated by a cost-sharing protocol. Naturally, it is in the players best interest to choose paths that charge them with small cost, and therefore the solution will be a Nash equilibrium. We study the price of anarchy of the game which is the worst case ratio between the cost of any Nash equilibrium and the cost of the minimum Steiner tree.

Different cost-sharing protocols result in different quality of equilibria. In this work, we are interested in the design of protocols that induce good equilibrium, i.e., protocols that guarantee low price of anarchy. [Chen, Roughgarden and Valiant 2010] where the first to address this problem and they considered different informational assumptions from the perspective of the designer: either the designer has full knowledge of the graph and the players' positions, or she doesn't know neither. We propose a model that lies in the middle-ground, where the designer has incomplete information about the input; the designer has prior knowledge of the underlying graph metric, but the players' positions are not known and are activated in an adversarial manner. The goal of the designer is to choose a single, universal cost-sharing protocol that has low Price of Anarchy for all possible sets of players' positions.

The main question we address is: to what extent can prior knowledge of the underlying graph metric help in the design? We first demonstrate that there exist classes of graphs, namely the outerplanar graphs, where knowledge of the underlying graph metric can dramatically improve the performance of good network cost-sharing design. Then, in our main technical result, we show that there exist graph metrics for which knowing the underlying graph metric does not help. We attack this problem by developing new techniques that employ powerful tools from extremal combinatorics, and more specifically Ramsey Theory in high dimensional hypercubes.

Alkmini Sgouritsa

--email hidden

passcode not visible

logged in users only

Price of Anarchy; Network Design; Cost-Sharing Protocols