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 Networks with Good Equilibria under Uncertainty
Speaker:Giorgos Christodoulou
coming from:Liverpool
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 12 July 2016
Duration:30 Minutes
Building:E1 4
We will discuss ways to cope with inefficiency of equilibria in systems. The underlying game is a multicast game in a rooted undirected graph with nonnegative edge costs. A set of k terminal vertices or players need to establish connectivity with the root. The social optimum is the Minimum Steiner Tree. We are interested in situations where the designer has incomplete information about the input. We propose two different models, the adversarial and the stochastic. In both models, the designer has prior knowledge of the underlying metric but the requested subset of the players is not known and is activated either in an adversarial manner (adversarial model) or is drawn from a known probability distribution (stochastic model). In the adversarial model, the goal of the designer is to choose a single, universal cost-sharing protocol that has low Price of Anarchy for all possible requested subsets of players.

The main question we will address is: to what extent can prior knowledge of the underlying metric help in the design of good protocols?

Name(s):Kurt Mehlhorn
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Kurt Mehlhorn/AG1/MPII/DE, 07/05/2016 12:06 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Kurt Mehlhorn, 07/05/2016 12:31 PM
  • Kurt Mehlhorn, 07/05/2016 12:06 PM -- Created document.