Mechanism Design for Large Scale Network Utility Maximization

Meng Zhang and Deepanshu Vasal

Papers from arXiv.org

Abstract: Network utility maximization (NUM) is a general framework for designing distributed optimization algorithms for large-scale networks. An economic challenge arises in the presence of strategic agents' private information. Existing studies proposed (economic) mechanisms but largely neglected the issue of large-scale implementation. Specifically, they require certain modifications to the deployed algorithms, which may bring the significant cost. To tackle this challenge, we present the large-scale Vickery-Clark-Grove (VCG) Mechanism for NUM, with a simpler payment rule characterized by the shadow prices. The Large-Scale VCG Mechanism maximizes the network utility and achieves individual rationality and budget balance. With infinitely many agents, agents' truthful reports of their types are their dominant strategies; for the finite case, each agent's incentive to misreport converges quadratically to zero. For practical implementation, we introduce a modified mechanism that possesses an additional important technical property, superimposability, which makes it able to be built upon any (potentially distributed) algorithm that optimally solves the NUM Problem and ensures all agents to obey the algorithm. We then extend this idea to the dynamic case, when agents' types are dynamically evolving as a controlled Markov process. In this case, the mechanism leads to incentive compatible actions of agent for each time slot.

Date: 2020-03, Revised 2021-01
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2003.04263 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2003.04263

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().