Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Designing Cost-Sharing Networks with Good Equilibria Under Uncertainty
Speaker:Alkmini Sgouritsa
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio: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.
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 27 September 2018
Duration:45 Minutes
Building:E1 4
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.

Name(s):Alkmini Sgouritsa
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:Price of Anarchy; Network Design; Cost-Sharing Protocols
Attachments, File(s):

Alkmini Sgouritsa, 09/19/2018 03:40 PM
Last modified:
Uwe Brahm/MPII/DE, 09/27/2018 07:01 AM
  • Alkmini Sgouritsa, 09/19/2018 03:40 PM -- Created document.