Polyhedral Clinching Auctions for Indivisible Goods
Polyhedral Clinching Auctions for Indivisible Goods
复制标题
DOI：
10.48550/arxiv.2303.00231
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
H. Hirai;Ryosuke Sato
中科院分区：
文献类型：
--
作者：
H. Hirai;Ryosuke Sato
在本研究中，我们提出了迄今为止研究的不可分割物品的多面体夹持拍卖。与Goel et al.（2015）的可分设置一样，我们的机制具有激励兼容性、个体合理性和帕累托最优性，并适用于多矩阵环境。不可分设置的一个显著特点是整个过程可以用买家数量和商品数量的时间多项式来进行。此外，我们还展示了Sato最近为可分设置建立的额外效率保证：我们机制的液体福利（LW）达到最优LW的1/2以上，社会福利大于最优LW。
In this study, we propose the polyhedral clinching auction for indivisible goods, which has so far been studied for divisible goods. As in the divisible setting by Goel et al. (2015), our mechanism enjoys incentive compatibility, individual rationality, and Pareto optimality, and works with polymatroidal environments. A notable feature for the indivisible setting is that the whole procedure can be conducted in time polynomial of the number of buyers and goods. Moreover, we show additional efficiency guarantees, recently established by Sato for the divisible setting: The liquid welfare (LW) of our mechanism achieves more than 1/2 of the optimal LW, and that the social welfare is more than the optimal LW.