Introduction
Markets naturally shrink during certain phases of a product's lifecycle—whether it is cord-cutters leaving cable TV, retail shoppers migrating to e-commerce, or restaurant capacities dropping during a pandemic. In the realm of mechanism design and combinatorial auctions (where multiple items are sold to multiple bidders who value specific bundles), designers typically assume they know the pool of participating bidders.
But what happens if each known bidder only shows up independently with a probability $p$? Intuitively, one might expect the revenue to scale down linearly (e.g., retaining 90% of bidders yields roughly 90% of the revenue). However, because auction revenue relies heavily on competition (such as the second-highest bid setting the price), the absence of even a few key bidders can cause revenue to plummet. This paper introduces the first formal model for preserving revenue in multi-item combinatorial auctions when facing such a "shrinking market," providing both theoretical guarantees and efficient learning algorithms.
The Non-Linear Threat of Shrinking Markets
The revenue loss from shrinking markets is rarely linear; reduced competition can be devastating. The authors demonstrate that if bidders have "allocational valuations" (where their value depends on what others receive), the revenue loss can be exponential in the number of items.
Consider a concrete "nightmare scenario": if 100 items are for sale and each bidder shows up with a 90% probability, the guaranteed revenue can drop to a mere 0.52% of the original optimal (VCG) revenue. Tackling this severe market size uncertainty requires designing a prior-free mechanism that maximizes expected revenue despite unpredictable participation.
Methodology: Taming Chaos with Winner Diagrams
To handle the exponential number of possible "shrunken" bidder subsets, the authors invent a novel combinatorial directed graph called a winner diagram.
This graph groups subsets of bidders into equivalence classes based on which bidders actually win items and determine the revenue. By proving that a designer only needs to analyze a specific subgraph of these equivalence classes, the authors reduce an intractable $2^n$ subset problem into a manageable space. This holds provided the auction satisfies "winner monotonicity"—meaning if a bidder wins when a competitor is present, they still win if that competitor drops out.
Using the winner diagram, the authors apply the probabilistic method to define a randomized mechanism. They uniformly sample from a set of mechanisms optimized for "heavy" equivalence classes (subsets of bidders that still retain high welfare). This proves a fundamental concept: as long as the class of auctions is sufficiently expressive, there is always an auction that preserves a mathematically bounded fraction of the optimal welfare and revenue, even under uncertainty.
Sample-Based Learning for Robust Auctions
To compute this robust mechanism efficiently, the designer simulates the shrunken market by sampling subsets of the known bidders. They leverage a structural property called delineability, which parameterizes auctions via hyperplane arrangements. This breaks the parameter space into geometric regions where revenue is linear, allowing the optimal auction to be found via linear programming.
The authors prove that this robust mechanism can be learned with high probability using $N = O(\frac{d \log(dh)}{\epsilon^2} \log(1/\delta))$ simulated samples. The computation takes polynomial time with respect to the number of hyperplanes and dimensions, making it highly tractable for specific parameterizable auction classes.
Key Results and Practical Implications
The paper's Main Possibility Theorem proves the existence of a mechanism $\tilde{M}$ that guarantees an expected revenue of at least: $$ \Omega\left( \frac{p^2}{k^{1+\log_{1/\gamma}(4/p)}} \right) W_M(S) - \epsilon $$ where $W_M(S)$ is the maximum welfare, $p$ is the participation probability, $k$ relates to the maximum number of winners, and $\gamma$ is a parameter measuring welfare drop.
Crucially, these theoretical bounds scale favorably when practical constraints are applied, such as artificially limiting the maximum number of winners (common in sourcing auctions) or enforcing item bundling.
Limitations and Future Work
While the paper establishes strong foundational bounds, the authors acknowledge a theoretical gap between their proven lower bound on revenue and the actual revenue loss seen in simple examples (which is often just a $1-p^2$ fraction). Closing this gap remains a primary direction for future research.
Additionally, the current model assumes the mechanism designer knows the participation probability $p$ to simulate the samples. Future work will explore how to design robust auctions when $p$ is completely unknown, and how to extend winner diagram techniques to settings with unlimited supply or objectives beyond pure revenue maximization.
Summary updated