An efficient mechanism for auctioning alternative paths

We study the application of auctions in simultaneously selling multiple related objects, which may be (imperfect) substitutes for all users. In particular, we consider a routing problem, where the provision of alternative paths to candidate users must take into consideration the user's utility values and special requirements; that is, the exclusive use of only one path, and the existence of preferences for one path over another. We study different mechanisms for winner determination and payment calculation for the paths won, using multi-object sealed-bid one-round VCG auctions. The main contribution of this work is the derivation of a fast incentive compatible algorithm for auctioning alternative paths under the aforementioned user preferences. This algorithm attains the efficient winner determination (i.e. the one maximizing social welfare) and the computation of payments when applying the VCG payment rule in the specific problem we study. We also present an alternative lower-complexity algorithm for uniform-price auctioning, where users' incentives are influenced by the degree of substitutability of the services offered. Finally, we compare the suggested mechanisms with other approaches in the literature, pointing out the importance of the assumptions used in our model and the efficiency of our approach.