Max-Planck-Institut für Informatik
max planck institut
informatik
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
Language:English
Date, Time and Location
Date:Tuesday, 10 March 2009
Time:09:15
Duration:45 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:024
Abstract
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.

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