Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
A Polynomial Time Algorithm for Fair Resource Allocation in Resource Exchange
verfasst von : Xiang Yan, Wei Zhu
Erschienen in: Frontiers in Algorithmics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The rapid growth of wireless and mobile Internet has led to wide applications of exchanging resources over network, in which how to fairly allocate resources has become a critical challenge. To motivate sharing, a BD Mechanism is proposed for resource allocation, which is based on a combinatorial structure called bottleneck decomposition. The mechanism has been shown with properties of fairness, economic efficiency [17], and truthfulness against two kinds of strategic behaviors [2, 3]. Unfortunately, the crux on how to compute a bottleneck decomposition of any graph is remain 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 \(G=(V,E;w_v)\) can be computed in \(O(n^6\log (nU))\), where \(n=|V|\) and \(U=max_{v\in V}w_v\). Based on the bottleneck decomposition, a fair allocation in resource exchange system can be obtained in polynomial time. In addition, our work completes the computation of a market equilibrium and its relationship to two concepts of fairness in resource exchange.