Tuesday, 13:15 - 13:40 h, Room: MA 043


Laurent Gourves
On the price of anarchy of the set cover game

Coauthors: Bruno Escoffier, Jerome Monnot


Given a collection C of weighted subsets of a ground set E, the set cover problem is to find a minimum weight subset of C which covers all elements of E. We study a strategic game defined upon this classical optimization problem. Every element of E is a player which chooses one set of C where it appears. Following a public tax function, every player is charged a fraction of the weight of the set that it has selected. Our motivation is to design a tax function having the following features: it can be implemented in a distributed manner, existence of an equilibrium is guaranteed and the social cost for these equilibria is minimized.


Talk 1 of the invited session Tue.2.MA 043
"Coordination mechanisms for efficient equilibria" [...]
Cluster 8
"Game theory" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.