Mechanism Design for Large Scale Network Utility Maximization

Network utility maximization (NUM) is a general framework for designing distributed optimization algorithms for networks. Existing studies proposed (economic) mechanisms to solve the NUM but largely neglected the issue of large-scale implementation. In this paper, we present the Large-Scale Vickery-Clark-Grove (VCG) Mechanism for NUM with a simpler payment rule. The Large-Scale VCG Mechanism maximizes the network utility and achieves individual rationality and budget balance. We show that, as the number of agents approaches infinity, 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 agents to obey the algorithm.