Polyhedral Clinching Auctions with a Single Sample
ACM Transactions on Economics and Computation · 10.08.2026
DOI: 10.1145/3839359 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, online erschienen am 10.08.2026. Verfasst von Ryosuke Sato. Die Arbeit nennt 53 Literaturangaben.
Abstract (Originalsprache)
We address auctions in two-sided markets with budget-constrained buyers, a fundamental setting with important applications such as display advertising. Our goal is to design efficient mechanisms that satisfy dominant-strategy incentive compatibility, individual rationality, and budget balance. To circumvent known impossibility results, we assume access to a single sample from each seller’s valuation distribution and adopt optimal liquid welfare (LW), rather than social welfare (SW), as our efficiency benchmark. Our main contribution is to strengthen efficiency guarantees and broaden the applicability of polyhedral clinching auctions. We establish the first tight welfare guarantees for the polyhedral clinching auction of Hirai and Sato (2022): the mechanism achieves at least half of the optimal LW, while its SW achieves at least the optimal LW. Building on this result, we design an efficient single-sample mechanism that satisfies all desired properties, and further extend our framework to settings with indivisible goods. A key feature of our approach is its generality, as it applies to both divisible and indivisible goods under polymatroid constraints.
Zitieren
APA
Sato, R. (2026). Polyhedral Clinching Auctions with a Single Sample. ACM Transactions on Economics and Computation. https://doi.org/10.1145/3839359
Vancouver
Sato R. Polyhedral Clinching Auctions with a Single Sample. ACM Transactions on Economics and Computation. 2026. doi:10.1145/3839359
BibTeX
@article{Sato2026,
author = {Sato, Ryosuke},
title = {Polyhedral Clinching Auctions with a Single Sample},
journal = {ACM Transactions on Economics and Computation},
year = {2026},
doi = {10.1145/3839359}
}
EUVIMED