Approximately Efficient Two-Sided Combinatorial Auctions
Approximately Efficient Two-Sided Combinatorial Auctions
复制标题
近似有效的双边组合拍卖
DOI：
10.1145/3381523
复制
发表时间：
2020
影响因子：
1.2
通讯作者：
Turchetta, Stefano
中科院分区：
文献类型：
--
作者：
Colini-Baldeschi, Riccardo;Goldberg, Paul W.;Keijzer, Bart de;Leonardi, Stefano;Roughgarden, Tim;Turchetta, Stefano
我们发展并扩展了一系列关于双边市场机制设计的近期工作。我们所考虑的市场是由许多物品的买者和卖者组成的，机制的目的是通过安排物品的购买和销售来改善社会福利。一种机制给出了主体对物品估值的先验分布，但没有给出实际估值；因此，目标是使这些分配的预期社会福利最大化。与之前的工作一样，我们感兴趣的是由真实机制实现的社会福利与可能的最佳社会福利之间的最坏比率。我们的主要结果是在买方具有XOS估值和卖方估值是可加性的情况下，激励相容和预算平衡的常因子近似机制。这是第一个双边市场设置的近似机制，其中代理具有组合估值功能。为了实现这个结果，我们引入了一种更通用的需求查询，这种查询在这种情况下似乎是需要的。在更简单的情况下，卖家有单位供给（每个人只有一件商品出售），我们给出了一种新机制，其福利保障比文献中最近的机制有所改善。我们还引入了一个更严格的强预算平衡（SBB）标准版本，旨在排除某些符合SBB的“不自然”交易。我们证明了我们的机制满足了强版本。
We develop and extend a line of recent work on the design of mechanisms for two-sided markets. The markets we consider consist of buyers and sellers of a number of items, and the aim of a mechanism is to improve the social welfare by arranging purchases and sales of the items. A mechanism is given prior distributions on the agents’ valuations of the items, but not the actual valuations; thus, the aim is to maximise the expected social welfare over these distributions. As in previous work, we are interested in the worst-case ratio between the social welfare achieved by a truthful mechanism and the best social welfare possible.Our main result is an incentive compatible and budget balanced constant-factor approximation mechanism in a setting where buyers have XOS valuations and sellers’ valuations are additive. This is the first such approximation mechanism for a two-sided market setting where the agents have combinatorial valuation functions. To achieve this result, we introduce a more general kind of demand query that seems to be needed in this situation. In the simpler case that sellers have unit supply (each having just one item to sell), we give a new mechanism whose welfare guarantee improves on a recent one in the literature. We also introduce a more demanding version of thestrong budget balance(SBB) criterion, aimed at ruling out certain “unnatural” transactions satisfied by SBB. We show that the stronger version is satisfied by our mechanisms.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
J. Brustle;Yang Cai;Fa Wu;Mingfei Zhao
通讯作者：
Mingfei Zhao
影响因子：
3.5
作者：
A. Demming
通讯作者：
A. Demming
一种随机抽样的双重拍卖机制
DOI：
--
发表时间：
2016
期刊：
arXiv.org
影响因子：
--
作者：
Erel Segal;Avinatan Hassidim;Y. Aumann
通讯作者：
Y. Aumann
DOI：
10.1145/1386790.1386801
发表时间：
2008
期刊：
2010 IEEE 51st Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Liad Blumrosen;Thomas Holenstein
通讯作者：
Thomas Holenstein
带预处理的需求查询
DOI：
--
发表时间：
2014
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
U. Feige;Shlomo Jozeph
通讯作者：
Shlomo Jozeph