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:Approximation through Non-Cooperation
Speaker:Martin Gairing
coming from:International Computer Science Institute (ICSI), Berkeley
Speakers Bio:
Event Type:Talk
Visibility:D1, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Tuesday, 10 March 2009
Duration:45 Minutes
Building:E1 4
Congestion Games are a general framework for modeling the allocation of resources among selfish players. In a congestion game, there is a set of resources and each strategy of a player is a subset of the resources. The cost (or payoff) of a resource is a function in the number of players
sharing this resource.

In the first part of the talk, we survey our recent results for congestion games and extensions thereof. In particular, we present results on the price of anarchy and the complexity of pure Nash equilibria.

In the second part, we will introduce a new class of congestion games that we call covering games. These games have a general covering problem as an underlying structure. For covering a resource the players receive a payoff which is given by a utility sharing function. This function defines the fraction that each covering player receives from the weights of the elements. We show how to construct a utility sharing function that optimizes the price of anarchy.
Moreover, we extend this to a local-search approximation algorithm with best possible approximation ratio.

Name(s):Conny Liegl
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Conny Liegl, 03/09/2009 01:38 PM -- Created document.