Polyhedral Clinching Auctions with a Single Sample

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.