Collusion in Atomic Splittable Routing Games

Authors: ChienChung Huang

Publish Date: 2012/08/02

Volume: 52, Issue: 4, Pages: 763-801

PDF Link

Abstract

We study how collusion affects the social cost in atomic splittable routing games Suppose that players form coalitions and each coalition behaves as if it were a single player controlling all the flows of its participants We investigate the following question under what conditions would the social cost of the postcollusion equilibrium be bounded by the social cost of the precollusion equilibriumWe show that if i the network is “welldesigned” satisfying a natural condition and ii the delay functions are affine then collusion is always beneficial for the social cost in the equilibrium flows On the other hand if either of the above conditions is unsatisfied collusion can worsen the social costOur main technique is a novel flowaugmenting algorithm to build equilibrium flows Our positive result for collusion is obtained by applying this algorithm simultaneously to two different flow value profiles of players and observing the difference in the derivatives of their social costs Moreover for a nontrivial subclass of selfish routing games this algorithm finds the exact equilibrium flows in polynomial timeI thank Lisa Fleischer and Kurt Mehlhorn for their comments on earlier drafts and Khaled Elbassioni and Michael Sagraloff for discussions on several technical issues I also thank the two anonymous reviewers for their comments that help improve the presentation of this paper Research supported by an Alexander von Humboldt fellowshipIn the following proof we implicitly assume that all edges are directed from the origin to the destination and the graph is acyclic in the directed edges This does not hurt generality since any edge not on an od path is not used in an optimal flow and no optimal flow is sent along a directed cycleLet Ot and Ot′ be optimal flows of values t and t′ and tt′ Suppose that the proposition does not hold Then in the pseudoflow z=Ot−Ot′ there exists some edge e ∗ on which z e0 Let G′=V′E′ be the largest subgraph of G containing e such that G′ is also seriesparallel and ∑ e∈E′ z e 0 Then there exists another subgraph G″=V″E″ such that ∑ e∈E″ z e 0 and G″ and G′ share the same two terminals o′ and d′We only prove the first part Suppose that G′ is composition of G 1=V 1E 1 and G 2=V 2E 2 If G′ is resulted from the seriescomposition of G 1 and G 2 then sum ein E 1 z e = sum ein E 2 z e0 If G′ is resulted from the parallelcomposition of G 1 and G 2 then either sum ein E 1 z e 0 or sum ein E 2 z e0 In both cases we can apply induction to find out a path p′ in G 1 and/or G 2 so that z e 0 if e∈p′ □

Keywords: