## 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**

**Abstract:**

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**

**Abstract:**

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**

**Abstract:**

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.