Polyhedral Clinching Auctions for Indivisible Goods

被引：0

作者：

Hirai, Hiroshi ^{[1
]}

Sato, Ryosuke ^{[2
]}

机构：

[1] Nagoya Univ, Grad Sch Math, Nagoya, Aichi, Japan

[2] Keio Univ, Fac Sci & Technol, Yokohama, Kanagawa, Japan

来源：

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION | 2025年 / 13卷 / 01期

关键词：

Auctions; budget constraints; polymatroids; liquid welfare;

D O I：

10.1145/3708506

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this study, we propose a 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 of this mechanism for the indivisible setting is that the entire 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 half of the optimal LW, and the social welfare is more than the optimal LW.

引用

页数：30