Overcoming Rational Manipulation in Distributed Mechanism Implementations

Abstract

Distributed systems are increasingly made up of nodes governed by disparate self-interested parties. These parties can be modeled as rational (in a game theoretic sense) utility-maximizing players that participate in a distributed algorithm. These rational nodes may choose to deviate from a given specification to increase their utility, but alternatively can be incented to correctly implement part of a distributed mechanism. In dealing with rational agents in distributed systems, computer science has taken a cue from the economics subfield of mechanism design (MD) with recent work in distributed algorithmic mechanism design (DAMD). Previously, work in MD and DAMD has focused on manipulation in agent strategy. However, there are other manipulations available to agents that can damage mechanism implementations. As designers begin to inject mechanism design ideas into distributed systems, non-manipulatability of mechanisms becomes more important. The main contributions of this paper are as follows: We identify four areas of manipulation in mechanism implementations, as well as environmental assumptions that can affect agent behavior. We introduce two properties for non-manipulatable mechanism implementations, communication- and algorithm compatibility, and identify techniques that can be used to achieve these properties. Our wider agenda is that future mechanism design implementation work (centralized or distributed) be done with consideration of these two non-manipulatability properties. To illustrate how this might be done, we demonstrate one way to bring communication- and algorithm compatibility to a well-defined lowest cost interdomain routing problem proposed by Feigenbaum, Papadimitriou, Sami, and Shenker (FPSS) [11]. Our approach does not add significant new processing or communication overhead to the distributed FPSS algorithm. Our end result is an incentive-compatible, communication-compatible, and algorithm-compatible distributed mechanism.