Eliciting Coordination with Rebates

This article considers network routing games, which can readily be used to model competition in telecommunication, traffic, transit or distribution networks. We study a mechanism based on rebates that provides incentives for participants to cooperate. This mechanism is modeled by a Stackelberg game in which the system owner offers rebates, and participants select their routes considering the rebates. The system owner decides how much to offer taking into account both the potential participants’ cost reduction as well as the cost of providing those rebates. Indeed, the rebate budget may come from the savings that arise from the more efficient solution. We characterize the Stackelberg equilibria of the game, and describe a polynomial-time algorithm to compute the optimal rebates. In addition, we provide tight results on their worst-case inefficiency measured by the so-called price of anarchy. Specifically, we describe the tradeoff between the sensitivity of the owner towards rebate costs and the worst-case inefficiency of the system.