Design and analysis of an approximation algorithm for Stackelberg network pricing

Sebastien Roch (sebastien.rochpolymtl.ca)
Patrice Marcotte (marcotteiro.umontreal.ca)
Gilles Savard (gillescrt.umontreal.ca)

Abstract: We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of $\frac{1}{2}\log m_T+1$, where $m_T$ denotes the number of toll arcs. Finally we show that the approximation is tight with respect to a natural relaxation by constructing a family of instances for which the relaxation gap is reached.

Keywords: network pricing, approximation algorithms, Stackelberg games, combinatorial optimization, NP-hard problems

Category 1: Combinatorial Optimization

Category 2: Network Optimization

Citation: Cahiers du GERAD, G-2002-61, HEC Montreal, Montreal, Canada, november 2002.

Download: [Postscript][PDF]

Entry Submitted: 03/18/2003
Entry Accepted: 03/18/2003
Entry Last Modified: 03/18/2003

Modify/Update this entry