Exponential communication separations between notions of selfishness
Exponential communication separations between notions of selfishness
复制标题
自私观念之间的指数级沟通差距
DOI：
10.1145/3406325.3451127
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zhao, Junyao
中科院分区：
文献类型：
--
作者：
Rubinstein, Aviad;Saxena, Raghuvansh R.;Thomas, Clayton;Weinberg, S. Matthew;Zhao, Junyao
我们考虑在多个玩家之间实现固定社会选择函数的问题（该函数将每个玩家的 typeti 作为输入并输出结果 f(t1,…,tn)），其中必须激励每个玩家遵循协议。特别是，我们研究了协议的通信要求，该协议：（a）实现f，（b）实现fand计算支付，使其事后激励兼容（EPIC）遵循协议，以及（c）实现fand以使其与主导策略激励兼容（DSIC）遵循协议的方式计算支付。我们显示了所有这三个量之间的指数分离，仅针对两个参与者。也就是说，我们首先构造一个f，使得f可以在通信c中实现，但是任何EPIC实现（具有任何支付选择）都需要通信exp(c)。这回答了 [Fadel 和 Segal，2009 年；巴拜奥夫等。等，2013]。其次，我们构造一个f，使得EPIC协议通过通信C来实现f，但是所有DSIC实现都需要通信exp(C)。
We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a typetifrom each playeriand outputs an outcomef(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) implementsf, (b) implementsfand computes payments that make it ex-post incentive compatible (EPIC) to follow the protocol, and (c) implementsfand 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 anfsuch thatfcan be implemented in communicationc, but any EPIC implementation off(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 anfsuch that an EPIC protocol implementsfwith communicationC, but all DSIC implementations offrequire communication exp(C).
登录
查看更多内容
区分真实和非真实组合拍卖的通信复杂性
DOI：
10.1145/3357713.3384267
发表时间：
2020
期刊：
Symposium on Theory of Computing
影响因子：
--
作者：
Assadi, Sepehr;Khandeparkar, Hrishikesh;Saxena, Raghuvansh R.;Weinberg, S. Matthew
通讯作者：
Weinberg, S. Matthew
明显的优势和随机的优先级
DOI：
--
发表时间：
2019
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
M. Pycia;Peter Troyan
通讯作者：
Peter Troyan
解决与两个次级买家的组合拍卖的通信复杂性
DOI：
10.1109/focs.2019.00025
发表时间：
2019
期刊：
Foundations of Computer Science
影响因子：
--
作者：
Ezra, Tomer;Feldman, Michal;Neyman, Eric;Talgam-Cohen, Inbal;Weinberg, Matt
通讯作者：
Weinberg, Matt
DOI：
--
发表时间：
2016
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Shahar Dobzinski
通讯作者：
Shahar Dobzinski
DOI：
--
发表时间：
2009
期刊：
Journal of Economics Theory
影响因子：
--
作者：
R. Fadel;I. Segal
通讯作者：
I. Segal