2023/03/01 by Hiroshi Hirai, Hirai, Hiroshi, Ryosuke Sato +1
Business, Management and Accounting · Decision Sciences · Social Sciences · #91B26 #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Supply Chain and Inventory Management
paper · pdf · doi:10.48550/arxiv.2303.00231
openalex publication_date 2023/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.