  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.
