1st International ICST Workshop on Game Theory for Networks

Research Article

An efficient mechanism for auctioning alternative paths

  • @INPROCEEDINGS{10.1145/1190195.1190209,
        author={Stavros  Routzounis and George D.  Stamoulis},
        title={An efficient mechanism for auctioning alternative paths},
        proceedings={1st International ICST Workshop on Game Theory for Networks},
  • Stavros Routzounis
    George D. Stamoulis
    Year: 2012
    An efficient mechanism for auctioning alternative paths
    DOI: 10.1145/1190195.1190209
Stavros Routzounis1,*, George D. Stamoulis1,*
  • 1: Network Economics and Services Group, Department of Informatics, Athens University of Economics and Business
*Contact email: sroutz@aueb.gr, gstamoul@aueb.gr


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.