PRICING GEOMETRIC TRANSPORTATION NETWORKS.

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 L₁ or L₂ metrics. In particular, we propose an O(n log n) algorithm for optimal pricing of a highway under the L₂ metric, and an O(nk log n log³ k) algorithm for orthogonally convex networks of complexity O(k) under the L₁ metric. [ABSTRACT FROM AUTHOR]