Auction Design for the Efficient Allocation of Service Capacity Under Congestion

Abstract

We consider the problem of efficiently allocating the capacity of a number of service facilities (prone to congestion) to a set of users with private information regarding their willingness to pay for different combinations of throughput versus latency. Auction mechanisms can be used to schedule the service capacity of available facilities. However, the interdependency of users’ valuations implies that simple uniform price adjustment processes (e.g., tatonnement) either fail to effectively clear or are subject to strategic manipulation. In this paper, we propose an iterative auction design and show that (i) it is efficient (i.e., the auction closes with the allocation of service that maximizes the social welfare) and (ii) it is strategy-proof, that is, it is a dominant strategy for users to truthfully reveal their demand for service capacity throughout the auction.