Invited Session Tue.2.MA 043

Tuesday, 13:15 - 14:45 h, Room: MA 043

Cluster 8: Game theory [...]

Coordination mechanisms for efficient equilibria


Chair: Tobias Harks



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

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.



Tuesday, 13:45 - 14:10 h, Room: MA 043, Talk 2

Rudolf Müller
Mechanism design for decentralized online machine scheduling

Coauthors: Birgit Heydenreich, Marc Uetz


Traditional optimization models assume a central decision maker who optimizes a global system performance measure. However, problem data is often distributed among several agents, and agents take autonomous decisions. This gives incentives for strategic behavior of agents, possibly leading to sub-optimal system performance. Furthermore, in dynamic environments, machines are locally dispersed and administratively independent. We investigate such issues for a parallel machine scheduling model where jobs arrive online over time. Instead of centrally assigning jobs to machines, each machine implements a local sequencing rule and jobs decide for machines themselves. In this context, we introduce the concept of a myopic best response equilibrium, a concept weaker than the classical dominant strategy equilibrium, but appropriate for online problems. Our main result is a polynomial time, online mechanism that - assuming rational behavior of jobs - results in an equilibrium schedule that is 3.281-competitive with respect to the maximal social welfare. This is only slightly worse than state-of-the-art algorithms with central coordination.



Tuesday, 14:15 - 14:40 h, Room: MA 043, Talk 3

Martin Gairing
Coordination mechanisms for congestion games

Coauthor: Giorgos Christodoulou


In a congestion game, we are given a set of resources and each player selects a subset of them (e.g., a path in a network). Each resource has a univariate cost (or utility) function that only depends on the load induced by the players that use it. Each player aspires to minimise (maximise) the sum of the resources's cost (utilities) in its strategy given the strategies
chosen by the other players.
Congestion games have played a starring role in recent research on quantifying the inefficiency of game theoretic equilibria. Most of this research focused on the price of anarchy.
In this talk, we will discuss coordination mechanisms for congestion games. That is, we study how much we can improve the price of anarchy by certain local modifications to the resource cost/utility functions. We will also discuss when such modifications yield polynomial-time convergence of best-reply dynamics.


  pay day loans . On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.