TY - GEN
T1 - A faithful distributed implementation of dual decomposition and average consensus algorithms
AU - Tanaka, Takashi
AU - Farokhi, Farhad
AU - Langbort, Cédric
PY - 2013
Y1 - 2013
N2 - 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 and 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.
AB - 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 and 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.
UR - http://www.scopus.com/inward/record.url?scp=84902324282&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902324282&partnerID=8YFLogxK
U2 - 10.1109/CDC.2013.6760337
DO - 10.1109/CDC.2013.6760337
M3 - Conference contribution
AN - SCOPUS:84902324282
SN - 9781467357173
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 2985
EP - 2990
BT - 2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 52nd IEEE Conference on Decision and Control, CDC 2013
Y2 - 10 December 2013 through 13 December 2013
ER -