TY - GEN

T1 - Exponential communication separations between notions of selfishness

AU - Rubinstein, Aviad

AU - Saxena, Raghuvansh R.

AU - Thomas, Clayton

AU - Matthew Weinberg, S.

AU - Zhao, Junyao

N1 - Publisher Copyright:
© 2021 ACM.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type ti from each player i and outputs an outcome f(t1,..., tn)), 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 [Fadel and Segal, 2009; Babaioff et. al., 2013]. 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).

AB - We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type ti from each player i and outputs an outcome f(t1,..., tn)), 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 [Fadel and Segal, 2009; Babaioff et. al., 2013]. 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).

KW - Algorithmic mechanism design

KW - Communication complexity

KW - Implementation theory

UR - http://www.scopus.com/inward/record.url?scp=85108149110&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108149110&partnerID=8YFLogxK

U2 - 10.1145/3406325.3451127

DO - 10.1145/3406325.3451127

M3 - Conference contribution

AN - SCOPUS:85108149110

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 947

EP - 960

BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -