Improved Results for Stackelberg Scheduling Strategies

We continue the study initiated in [13] on Stackelberg Scheduling Strategies. We are given a set of m independent parallel machines or equivalently a set of m parallel edges, each with a load dependent latency function. The setting is that of a non-cooperative game: players route their flow so as minimize their individual latencies. Additionally, there is a single player (the leader), who controls an a fraction of the total flow. The goal is to find a strategy for the leader (i.e. an assignment of flow to individual links) such that the selfish users react so as to minimize the total latency of the system. Building on the recent results in [13,14], we devise a fully polynomial approximate Stackelberg scheme that runs in time poly(m, 1/?) and results in an assignment whose cost is within a (1 + ?) factor of the optimum Stackelberg strategy. We also study the generalization to multiple rounds. It is easy to see that more than two rounds do not help. We show that the two round Stackelberg strategy (denoted 2SS) always dominates the one round scheme. We also consider extensions of the above results to special graphs, and special kind of latency functions.