ITR: Foundations of Distributed Algorithmic Mechanism Design

Yale University, New Haven CT

Investigators

Abstract

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 the characteristics 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.