Exponential communication separations between notions of selfishness

DOI10.1145/3406325.3451127MaRDI QIDQ6065222zbMATH OpenOpenAlexFDO

Authors Aviad Rubinstein, Raghuvansh R. Saxena, Clayton J. Thomas, S. Matthew Weinberg

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.14898

zbMATH Keywords

algorithmic mechanism designcommunication complexityimplementation theory

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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)$.

This page was built for publication: Exponential communication separations between notions of selfishness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065222)