Eliciting Coordination with Rebates
Patrick Maillé,
Nicolás E. Stier-Moses
Institut Telecom, Telecom Bretagne, Université Européenne de Bretagne, Cesson Sévigné, France
Graduate School of Business, Columbia University, Uris Hall 418, New York, New York 10027
patrick.maille{at}telecom-bretagne.eu
stier{at}gsb.columbia.edu
This article considers a mechanism based on rebates that aims at reducing congestion in urban networks. The framework helps select rebate levels so that enough commuters switch to modes that are under used. Indeed, getting a relative small number of drivers to switch to public transportation can significantly improve congestion. This mechanism is modeled by a Stackelberg game in which the transportation authority offers rebates, and participants factor them into the costs of each mode. A new Wardrop equilibrium arises when participants selfishly select one of the modes of transportation with the lowest updated costs. Rebate levels are chosen taking into account not only the potential reduction of the participants' cost, but also the cost of providing those rebates. Part of the budget for rebates may come from the savings that arise from the more efficient use of capacity. We characterize the Stackelberg equilibria of the game, and describe a polynomial-time algorithm to compute the optimal rebates for each mode. In addition, we provide tight results on the worst-case inefficiency of the resulting Wardrop equilibrium, 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.
Key Words: network pricing; subsidies as incentives; Wardrop equilibrium; Stackelberg games; price of anarchy
History: Received: September 2008;
revised: March 2009;
accepted: April 2009.
Copyright © 2009 by INFORMS.
