Exponential Communication Separations between Notions of Selfishness

Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Mathew Weinberg and Junyao Zhao

Papers from arXiv.org

Abstract: We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type $t_i$ from each player $i$ and outputs an outcome $f(t_1,\ldots, t_n)$), in which each player must be incentivized to follow the protocol. In particular, we study the communication requirements of a protocol which: (a) implements $f$, (b) implements $f$ and computes payments that make it ex-post incentive compatible (EPIC) to follow the protocol, and (c) implements $f$ and computes payments in a way that makes it dominant-strategy incentive compatible (DSIC) to follow the protocol. We show exponential separations between all three of these quantities, already for just two players. That is, we first construct an $f$ such that $f$ can be implemented in communication $c$, but any EPIC implementation of $f$ (with any choice of payments) requires communication $\exp(c)$. This answers an open question of [FS09, BBS13]. Second, we construct an $f$ such that an EPIC protocol implements $f$ with communication $C$, but all DSIC implementations of $f$ require communication $\exp(C)$.

Date: 2020-12, Revised 2021-06
New Economics Papers: this item is included in nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://arxiv.org/pdf/2012.14898 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2012.14898

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().