PRICING GEOMETRIC TRANSPORTATION NETWORKS

Authors:
Publisher website
Google Scholar
Abstract
We propose algorithms for pricing a transportation network in such a way that the profit generated by the customers is maximized. We model the transportation network as a subset of the plane and take into account the fact that the customers minimize their own transportation cost. The underlying theory is a two-player game model called Stackelberg games. We propose algorithms for the cases where the fare does and does not depend on the distance traveled, in the L1 or L2 metrics. In particular, we propose an O(n log n) algorithm for optimal pricing of a highway under the L2 metric, and an O(nk log n log 3 k) algorithm for orthogonally convex networks of complexity O(k) under the L1 metric.