Double Auction Mechanisms for Resource Allocation in Autonomous Networks

Abstract

Auction mechanisms are used for allocating a resource among multiple agents with the objective to maximize social welfare. What makes auctions attractive is that they are agnostic to utility functions of agents. Auctions involve a bidding method by agents-buyers, which is then mapped by a central controller to an allocation and a payment for each agent. In autonomic networks comprising self-interested nodes with different needs and utility functions, each entity possesses some resource and can engage in transactions with others to achieve its needs. In fact, efficient network operation relies on node synergy and multi-lateral resource trading. Nodes face the dilemma of devoting their limited resource to their own benefit versus acting altruistically and anticipating to be aided in the future. Wireless ad-hoc networks, peer-to-peer networks and disruption-tolerant networks are instances of autonomic networks where the challenges above arise and the traded resource is energy, bandwidth and storage space respectively. Clearly, the decentralized complex node interactions and the double node role as resource provider and consumer amidst resource constraints cannot be addressed by single-sided auctions and even more by mechanisms with a central controller. We introduce a double-sided auction market framework to address the challenges above. Each node announces one bid for buying and one for selling the resource. We prove that there exist bidding and charging strategies that maximize social welfare and we explicitly compute them. We generalize our result to a generic network objective. Nodes are induced to follow these strategies, otherwise they are isolated by the network. Furthermore, we propose a decentralized realization of the double-sided auction with lightweight network feedback. Finally, we introduce a pricing method which does not need a charging infrastructure. Simulation results verify the desirable properties of our approach.