Efficient signal proportional allocation (ESPA) mechanisms: decentralized social welfare maximization for divisible resources

摘要

We address the problem of devising efficient decentralized allocation mechanisms for a divisible resource, which is critical to many technological domains such as traffic management on the Internet and bandwidth allocation to agents in ad hoc wireless networks. We introduce a class of efficient signal proportional allocation (ESPA) mechanisms that yields an allocation which maximizes social welfare with minimal signaling and computational requirements for the resource. Revenue limits for this class are obtained and a sequence of schemes that approach these limits arbitrarily closely are given. We also present a locally stable negotiation scheme applicable to the entire class and illustrate efficiency and revenue properties through simulation.