A Faithful Distributed Implementation of Dual Decomposition and Average Consensus Algorithms

We consider large scale cost allocation problems and consensus seeking problems for multiple agents, in which agents are suggested to collaborate in a distributed algorithm to find a solution. If agents are strategic to minimize their own individual cost rather than the global social cost, they are endowed with an incentive not to follow the intended algorithm, unless the tax/subsidy mechanism is carefully designed. Inspired by the classical Vickrey-Clarke-Groves mechanism and more recent algorithmic mechanism design theory, we propose a tax mechanism that incentivises agents to faithfully implement the intended algorithm. In particular, a new notion of asymptotic incentive compatibility is introduced to characterize a desirable property of such class of mechanisms. The proposed class of tax mechanisms provides a sequence of mechanisms that gives agents a diminishing incentive to deviate from suggested algorithm.