## Invited Session Wed.1.H 3010

#### Wednesday, 10:30 - 12:00 h, Room: H 3010

**Cluster 1: Approximation & online algorithms** [...]

### Scheduling and packing: Approximation with algorithmic game theory in mind

**Chair: Asaf Levin**

**Wednesday, 10:30 - 10:55 h, Room: H 3010, Talk 1**

**Leah Epstein**

Generalized selfish bin packing

**Coauthor: Gyorgy Dosa**

**Abstract:**

In bin packing games, an item has a positive weight and each item has a cost for every valid packing of the items. We study a class of such games where the cost of an item is the ratio between its weight and the total weight of items packed with it, i.e., cost sharing is based linearly on the weights of items. We study several types of pure Nash equilibria (NE): standard NE, strong NE, and strictly/weakly Pareto optimal NE. We show that any game of this class admits all these types of equilibria. We study the (asymptotic) prices of anarchy and stability (PoA and PoS) of the problem for these types of equilibria and general/unit weights. While the

case of general weights is strongly related to First Fit, and all the PoA values are 1.7, for unit weights they are all below 1.7. The strong PoA is equal to approximately 1.691 (another well-known number in bin packing) while the strictly Pareto optimal PoA is lower. The PoS values are 1, except for those of strong equilibria, which is 1.7 for general weights, and approximately 1.611824 for unit weights.

**Wednesday, 11:00 - 11:25 h, Room: H 3010, Talk 2**

**Asaf Levin**

A unified approach to truthful scheduling on related machines

**Coauthors: Leah Epstein, Rob van Stee**

**Abstract:**

We present a unified framework for designing deterministic monotone PTAS's for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the *l*_{p} norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone PTAS's have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it, and have an important role in mechanism design.

The key idea of our novel method is to show that it is possible to compute in polynomial time a structured nearly optimal schedule. An interesting aspect of our approach is that, in contrast to all known PTAS's, we avoid rounding any job sizes or speeds throughout. We can therefore find the exact best structured schedule using a dynamic programming. The state space encodes sufficient information such that no postprocessing is needed, allowing an elegant and relatively simple analysis. The monotonicity is a consequence of the fact that we find the best schedule in a specific collection of schedules.

**Wednesday, 11:30 - 11:55 h, Room: H 3010, Talk 3**

**Rob van Stee**

The price of anarchy for selfish ring routing is two

**Coauthors: Xujin Chen, Benjamin Doerr, Xiaodong Hu, Weidong Ma, Carola Winzen**

**Abstract:**

We analyze the network congestion game with atomic players, asymmetric strategies, and the maximum latency among all players as social cost. While this is an important social cost function, it has so far received relatively little attention in the literature.

We show that the price of anarchy is at most two, when the network is a ring and the link latencies are linear. This bound is tight. This is the first sharp bound for the maximum latency objective on a natural and important network topology.