EUVIMEDEUVIMED entdecken
Crossref

Polyhedral Clinching Auctions with a Single Sample

Ryosuke Sato

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →