Efficiency and Fairness in Resource Exchange

With the rapid growth of Internet, plenty of applications has been implemented for users to exchange resources with each other over networks. As a result, it has been a critical challenge to efficiently and fairly allocate resource among participating agents. Motivated by the famous BitTorrent system, a BD Mechanism for resource exchange allocation is proposed, which is based on a combinatorial structure called bottleneck decomposition. The mechanism has been shown to lead to market equilibrium, a state optimizing each individual's utility, and to be truthful, that is robust against agents' strategic behaviors. However, the crux on how to compute a bottleneck decomposition of any graph remains untouched. In this paper, we focus on the computation of bottleneck decomposition to fill the blanks and prove that the bottleneck decomposition of a network can be computed in O(n^6\log(nU)) time, where n and U are the number of agents and the maximal amount of resource any agent has in the network. Based on the bottleneck decomposition, a fair allocation in a resource exchange network can be obtained in polynomial time. We further carefully discuss the fairness in resource exchange scenario, showing the derived allocation satisfies several common fairness notions simultaneously.