Solving the winner determination problem in combinatorial auctions for fractional ownership of autonomous vehicles

Abstract

The introduction of autonomous vehicles (AVs) to consumer markets will expedite the trend of car sharing and enable co-owning or co-leasing a car. In this paper, we consider a combinatorial auction market for fractional ownership of AVs, which is unique in two aspects. First, items are neither predefined nor discrete; rather, items are continuous time slots defined by bidders. Second, the spatial information of bidders should be incorporated within the winner determination problem (WDP) so that sharing a vehicle is indeed a viable plan. The consideration of spatial information increases the computational complexity significantly. We formulate the WDP, which plays a critical role in various auction designs and pricing schemes, for both discrete- and continuous-time settings. In terms of social welfare maximization, we show that the continuous-time model is superior to the discrete-time model. We provide a conflict-based reformulation of the continuous-time model, for which we develop an effective solution approach based on a heuristic and maximal clique based reformulations. Using samples of the 2010-2012 California Household Travel Survey, we verify that the proposed solution methods provide effective computational tools for the combinatorial auction with bidder-defined items.