ITR: Foundations of Distributed Algorithmic Mechanism Design

在传统的理论计算机科学(TCS)中，计算代理通常被假设为要么顺从，即遵循规定的算法，要么是相互“竞争”的对手。另一方面，博弈论中的战略主体既不服从也不对抗。尽管人们不能假设他们会遵循规定的算法，但可以假设他们会对激励措施做出反应。因此，经济学文献传统上强调激励，淡化计算复杂性，而塔塔咨询公司的文献传统上则相反。互联网作为分布式计算的标准平台的出现从根本上改变了这种状况：许多自私自利的、独立的各方拥有、运营和使用互联网，这赋予了互联网经济和计算机的特征。分布式算法机制设计(DAMD)是一门新兴的学科，它是TCS、经济学和网络的交叉学科。本项目涉及DAMD的经济和计算基础。所涉及的基本问题包括但不限于DAMD问题的固有的易处理或难处理的概念、被发现固有地难以处理的DAMD问题的近似方法、以及在分布式算法机制中可以保持代理隐私的程度。

In traditional theoretical computer science (TCS), computational agents are typically assumed either to be obedient, i.e., to follow the prescribed algorithm, or to be adversaries who ``play against'' each other. On the other hand, the strategic agents in game theory are neither obedient nor adversarial. Although one cannot assume that they will follow the prescribed algorithm, one can assume that they will respond to incentives. Thus, the economics literature traditionally stressed incentives and downplayed computational complexity, and the TCS literature traditionally did the opposite. The emergence of the Internet as a standard platform for distributed computation has radically changed this state of affairs: Ownership, operation, and use by many self-interested, independent parties give the Internet thecharacteristics of an economy as well as those of a computer.The emerging discipline of Distributed Algorithmic Mechanism Design (DAMD)lies in the intersection of TCS, economics, and networking. This project addresses the economic and computational foundations of DAMD. Fundamental problems addressed include but are not limited to notions of inherent tractability or intractability of DAMD problems, methods of approximation for DAMD problems found to be inherently intractable, and the extent to which agent privacy can be maintained in distributed algorithmic mechanisms.