Auction mechanisms for network resource allocation

Abstract

In the autonomic Internet of the future, auction mechanisms arise as key methods for realizing efficient resource allocation. The major asset of auctions is their obliviousness to node utilities, which renders them capable of achieving a desired resource allocation regime without knowledge of the utility functions of involved entities. Auctions can aid in addressing major research challenges in such autonomic settings, such as the need to cope with diverse and conflicting interests of network entities, the need to carry out resource allocation in a decentralized manner, the requirement for matching dynamic spatiotemporal patterns of demand and supply, and the need to operate under limited or no network state and utility information. In this survey paper, we delineate the main trends and challenges associated with auction design. We start from first principles auction design for maximum auctioneer revenue or maximum allocation efficiency for one or multiple indivisible items and for divisible resources. We gradually move to more composite models, those of position auctions for Internet advertisements and those arising in spectrum sharing in cognitive radio networks.We argue that some directions worth pursuing are: (i) the design of advanced auction models that capture multi-level interaction of involved entities, (ii) the employment of double auctions for multiple seller and buyer interaction, and (iii) the design of decentralized negotiation and resource trading mechanisms.