|
Abstract : |
Eliciting truthful responses from self-interested agents is an important problem in game theory and microeconomics, and it is studied under mechanism design or implementation theory. Truthful mechanisms have received considerable interest within computer science recently for designing protocols for Internet-based applications, which typically involve cooperation of multiple selfinterested agents. A cornerstone of the mechanism design field is the Vickrey mechanism, or more generally the class of Vickrey-Clarke-Groves mechanisms. These mechanisms are known to be incentive-compatible, meaning that rational agents maximize their utility by truthfully revealing their preferences. In the Vickrey-Clarke-Groves (VCG) mechanism, each agent receives a "payment " for his participation, and this payment is proportional to the added "value " he brings to the system. Implementing the VCG mechanism often requires solving a (non-trivial) optimization problem n + 1 times, once with all agents, and once corresponding to each agent's deletion to determine his incremental value. An important algorithmic challenge is to reduce this computational overhead. We investigate this problem in the specific context of network routing, where there has been a surge of interest in pricing network usage. Routing in the Internet involves multiple agents (such as organizations or service providers) who are self-interested, and thus the Vickrey compensation mechanism is relevant for eliciting truthful response. In this context of shortest path routing, we show that the Vickrey payments for all the agents can be computed in the same asymptotic time complexity as for one agent, thus solving an open problem of Nisan and Ronen [12]., |
