Mechanism Design for Stochastic Dynamic Parking Resource Allocation

Abstract

In this paper, we study a parking management problem where an operator manages a publicly owned parking service system with unknown parking demand. Assuming that the operator has perfect information, we first formulate the operator's problem as a stochastic dynamic programming problem, and to overcome the curse of dimensionality, we resort to approximate dynamic programming for solving it. However, in practice, some information that is essential for centralized management is usually privately known, which provides incentives for strategic behaviors of drivers and could lead to suboptimal system performance. We design a two-step mechanism and prove that, in step 1, drivers’ choices of whether or not to enter the managed system following the approximate optimal solution satisfy Bayesian-Nash equilibrium (BNE), and in step 2, that truthful reporting is a dominant strategy for all drivers under any circumstance. We investigate the properties of the resulting equilibria, and further modify the mechanism to ensure that the desired approximate system optimum solution is the only resulting BNE. Numerical examples show that the mechanism design not only enhances the average system performance but also increases the system robustness.