An Approximation Algorithm for Stackelberg Network Pricing

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 $1/2{\log }_2{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.

38 pages

Cited by in corpus (5)

• Stackelberg Network Pricing is Hard to Approximate
• The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs
• A Catalog of Formulations for the Network Pricing Problem
• Fare Evasion in Transit Networks
• Specializations and Generalizations of the Stackelberg Minimum Spanning Tree Game