Research Archive

© Transportation Science, 2009
Volume: 43 | Issue: 4 | Pages: 473-492

Publication type: Journal article

Research Archive Topic: Business Economics and Public Policy

Abstract

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.

Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.

Each topic is linked to an index of publications on that topic.