How to trade thirty thousand products: A wholesale market design for road capacity

One of the core reasons for urban traffic congestion is the mispricing of the traffic's main resource, the scarce road capacity. Recent proposals suggest a two-stage market for road capacity similar to other major utilities markets such as those for electricity. In such markets an Independent System Operator (ISO) provides road infrastructure which multiple Service Providers (SP) then resell to end consumers. The size of such markets in terms of the number of traded items, road segments per hour, is exceptional. A road network in a city consists of tens of thousands different road segments and it is unclear how a wholesale market for service providers should be designed to keep it tractable for buyers and sellers. Three problems arise in this context: First, how can a service provider express preferences for so many products. Second, the optimization problem is very large and it is far from obvious that problems of this size can be solved. Finally, the allocation problem is non-convex and finding competitive equilibrium prices on such markets is impossible in general. We suggest a parsimonious bid language based on origin–destination pairs and introduce a mixed-integer optimization problem to maximize welfare on such markets. Based on the MATSim traffic simulator, we show that one can solve realistic problems based on traffic data for the city of Berlin to optimality within 15 minutes. Importantly, we approximate competitive equilibrium prices which require only negligible side-payments as the allocation problem is “almost” convex. Overall, the paper provides a tangible proposal for wholesale markets for road capacity.