Maximizing Revenue under Market Shrinkage and Market Uncertainty

Maria-Florina Balcan, Siddharth Prasad, Tuomas SandholmNeurIPS 2022 · OpenReview

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.

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

Abstract

A shrinking market is a ubiquitous challenge faced by various industries. In this paper we formulate the first formal model of shrinking markets in multi-item settings, and study how mechanism design and machine learning can help preserve revenue in an uncertain, shrinking market. Via a sample-based learning mechanism, we prove the first guarantees on how much revenue can be preserved by truthful multi-item, multi-bidder auctions (for limited supply) when only a random unknown fraction of the population participates in the market. We first present a general reduction that converts any sufficiently rich auction class into a randomized auction robust to market shrinkage. Our main technique is a novel combinatorial construction called a winner diagram that concisely represents all possible executions of an auction on an uncertain set of bidders. Via a probabilistic analysis of winner diagrams, we derive a general possibility result: a sufficiently rich class of auctions always contains an auction that is robust to market shrinkage and market uncertainty. Our result has applications to important practically-constrained settings such as auctions with a limited number of winners. We then show how to efficiently learn an auction that is robust to market shrinkage by leveraging practically-efficient routines for solving the winner determination problem.
BibTeX
@inproceedings{balcan2022maximizing,
  author = {Maria-Florina Balcan and Siddharth Prasad and Tuomas Sandholm},
  title = {{Maximizing Revenue under Market Shrinkage and Market Uncertainty}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=SMVdEKf1ui},
}
Figure