Short Bio:

Mehlhorn graduated from the Technical University of Munich, where he studied computer science and mathematics, and earned his Ph.D. in 1974 from Cornell University under the supervision of Robert Constable. Since 1975 he has been on the faculty of Saarland University in Saarbrücken, Germany.

Since 1990 has been the director of the Max Planck Institute for Computer Science, also in Saarbrücken. He has been on the editorial boards of ten journals, a trustee of the International Computer Science Institute in Berkeley, California, and a member of the board of governors of Jacobs University Bremen. He won the Gottfried Wilhelm Leibniz Prize in 1986, the Karl Heinz Beckurts Award in 1994, the Konrad Zuse Medal in 1995, and the EATCS Award in 2010. He was named a Fellow of the Association of Computing Machinery in 1999, a member of the Berlin-Brandenburg Academy of Sciences in 2001, and a member of the German Academy of Sciences Leopoldina in 2004. He has received honorary doctorates from the Otto von Guericke University of Magdeburg in 2004 and the University of Waterloo in 2006.

Abstract:

We reconsider the well-studied Selfish Routing game with affine latency functions. In this game, r units of flow need to be routed in a network from a given source to a given sink. The cost of a flow f is

where fe is the flow across edge e and ℓe(fe) is the latency (cost) of edge e at flow fe. The Price of Anarchy is the ratio of the cost of a Nash flow (= flow is routed along minimum cost paths) to the cost of minimum cost flow. The price of anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou’s network. We improve upon the value 4/3 by means of Coordination Mechanisms.

We increase the latency functions of the edges in the network, i.e., if ℓe(x) is the latency function of an edge e, we replace it by ˆ ℓe(x) with ℓe(x)  ˆ ℓe(x) for all x. Then an adversary is fixing a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if ˆCN(r) denotes the cost of the Nash flow in the modified network for rate r and Copt(r) denotes the cost of the optimal flow in the original network for the same rate then

We exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our mechanism gives 5/4 = 1.25.

We also describe a more complicated mechanism that achieves a engineered Price of Anarchy of at most 1.192 for the case of two parallel links. We also prove that this mechanism is optimal.

The talk is based on joint work with Giorgos Christodoulou and Evangelia Pyrga.