论文标题
大规模网络实用程序最大化的机理设计
Mechanism Design for Large Scale Network Utility Maximization
论文作者
论文摘要
网络实用程序最大化（NUM）是用于设计大规模网络的分布式优化算法的一般框架。在存在战略代理商的私人信息的情况下，出现了经济挑战。现有的研究提出了（经济）机制，但在很大程度上忽略了大规模实施的问题。具体而言，它们需要对部署算法进行某些修改，这可能带来巨大的成本。为了应对这一挑战，我们提出了NUM的大型Vickery-Clark-Grove（VCG）机制，其付款规则为以影子价格为特征。大规模的VCG机制可最大化网络公用事业，并实现个人理性和预算平衡。对于无限的代理商来说，代理商对他们的类型的真实报道是他们的主要策略。对于有限情况，每个代理商的动力将误报告二次收敛至零。为了实施实施，我们引入了一种修改机制，该机制具有其他重要的技术属性，叠加性，这使其能够建立在任何（可能分布的）算法上，该算法可以最佳地解决NUM问题并确保所有代理商遵守算法。然后，当代理类型动态发展为受控的马尔可夫过程时，我们将这个想法扩展到动态情况。在这种情况下，该机制会导致每个时间插槽的激励兼容动作。
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.
