The randomized communication complexity of randomized auctions
The randomized communication complexity of randomized auctions
复制标题
随机拍卖的随机通信复杂性
DOI：
10.1145/3406325.3451111
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zhao, Junyao
中科院分区：
文献类型：
--
作者：
Rubinstein, Aviad;Zhao, Junyao
研究了具有n个物品组合估价函数的垄断卖家和单一买家之间的激励相容拍卖协议的通信复杂性。由于收益最优拍卖是随机化的(以及Babaioff，Gonczarowski和Nisan的一个公开问题)，我们关注这个问题的随机化通信复杂性(与大多数以前关于确定性通信的工作形成对比)。我们设计了简单、激励相容和收益最优的拍卖协议，其预期的通信复杂性比确定性的拍卖协议要高效得多(实际上是无限的)。我们还给出了近似收益最优拍卖的预期通信复杂性的近似匹配下界。这些结果源于激励相容拍卖协议的简单表征，该协议允许我们证明相对于随机拍卖协议的下限。特别地，我们的下界给出了激励的通信复杂性与实施贝叶斯激励相容的社会选择规则之间的第一近似抵抗指数分离，解决了Fadel和西格尔的一个悬而未决的问题。
We study the communication complexity of incentive compatible auction-protocols between a monopolist seller and a single buyer with a combinatorial valuation function over n items. Motivated by the fact that revenue-optimal auctions are randomized (as well as by an open problem of Babaioff, Gonczarowski, and Nisan), we focus on the randomized communication complexity of this problem (in contrast to most prior work on deterministic communication). We design simple, incentive compatible, and revenue-optimal auction-protocols whose expected communication complexity is much (in fact infinitely) more efficient than their deterministic counterparts. We also give nearly matching lower bounds on the expected communication complexity of approximately-revenue-optimal auctions. These results follow from a simple characterization of incentive compatible auction-protocols that allows us to prove lower bounds against randomized auction-protocols. In particular, our lower bounds give the first approximation-resistant, exponential separation between communication complexity of incentivizing vs implementing a Bayesian incentive compatible social choice rule, settling an open question of Fadel and Segal.
登录
查看更多内容
关于最优简单机构的计算复杂性
DOI：
10.1145/2840728.2840736
发表时间：
2015
期刊：
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
影响因子：
--
作者：
A. Rubinstein
通讯作者：
A. Rubinstein
关于销售多个独立分布的商品的收入最大化
DOI：
--
发表时间：
2013
影响因子：
11.1
作者：
Xinye Li;A. Yao
通讯作者：
A. Yao
区分真实和非真实组合拍卖的通信复杂性
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：
10.1137/1.9781611973075.49
发表时间：
2009
期刊：
ArXiv
影响因子：
--
作者：
Patrick Briest;Shuchi Chawla;Robert D. Kleinberg;S. Weinberg;A. P. Sloan;Foundation Fellowship
通讯作者：
Foundation Fellowship
99%%20收入%20通过%20增强%20竞争
DOI：
10.1145/3219166.3219202
发表时间：
2018
期刊：
Proceedings of the 2018 ACM Conference on Economics and Computation
影响因子：
--
作者：
M. Feldman;Ophir Friedler;A. Rubinstein
通讯作者：
A. Rubinstein