Faithful implementations of distributed algorithms and control laws

Takashi Tanaka, Farhad Farokhi, Cedric Langbort

Research output: Contribution to journalArticlepeer-review

Abstract

When a distributed algorithm must be executed by strategic agents with misaligned interests, a social leader needs to introduce an appropriate tax/subsidy mechanism to incentivize agents to faithfully implement the intended algorithm so that a correct outcome is obtained. We discuss the incentive issues of implementing economically efficient distributed algorithms using the framework of indirect mechanism design theory. In particular, we show that indirect Groves mechanisms are not only sufficient but also necessary to achieve incentive compatibility. This result can be viewed as a generalization of the Green-Laffont theorem to indirect mechanisms. Then, we introduce the notion of asymptotic incentive compatibility as an appropriate solution concept to faithfully implement distributed and iterative optimization algorithms. We consider two special types of optimization algorithms: Dual decomposition algorithms for resource allocation and average consensus algorithms.

Original languageEnglish (US)
Pages (from-to)191-201
Number of pages11
JournalIEEE Transactions on Control of Network Systems
Volume4
Issue number2
DOIs
StatePublished - 2017

Keywords

  • Decentralized control
  • distributed computing
  • microeconomics

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Signal Processing
  • Computer Networks and Communications
  • Control and Optimization

Fingerprint Dive into the research topics of 'Faithful implementations of distributed algorithms and control laws'. Together they form a unique fingerprint.

Cite this