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 -