Novel double auctions for spatially distributed parking slot assignment with externalities

This article considers a parking slot assignment problem in a sharing economy where parking slots are spatially heterogeneous. When buyers (i.e., the slot users) park and take their cars in the reserved parking slots, environment externalities are created. We incorporate the externality costs in our winner determination model and construct a padding-based Vickrey-Clarke-Groves (PV) double auction where each buyer submits an XOR bid on his/her desired parking slots at the same price. In the PV double auction, the padding intuition is adopted on either the supply or demand side. We then propose a padding-based shadow price (PS) double auction by integrating the padding method with the shadow price method. Due to the rises in buying prices and declines in selling prices, the PS double auction is likely to realize higher auctioneer's payoff. Both PV and PS double auctions achieve incentive compatibility, individual rationality, budget balance and asymptotical efficiency. Our numerical experiments demonstrate that the proposed double auctions can realize high efficiency.