Scaling Revenue Maximization to Multi-Item Auctions

47 concepts53 papers1 proposal

In auction theory, the single-item setting is a well-mapped landscape. Thanks to classic economic frameworks, we know exactly how to maximize revenue when selling a single item to multiple buyers: the seller simply computes "virtual valuations" based on the buyers' risk profiles and awards the item to the highest bidder above a reserve price. This works beautifully because an agent's private information—their willingness to pay—is a single number. As Roberto De Prisco et al. note in The Power of Verification for One-Parameter Agents, traditional exact mechanism design is heavily optimized for these "one-parameter" environments.

But when a seller has multiple items to offer, this paradise collapses. A buyer's private type is no longer a single number, but a multidimensional vector representing their valuations for every individual item and combination of items. This shift from one-dimensional to multidimensional mechanism design introduces severe mathematical and computational barriers.

The Curse of Multidimensionality

Why does adding items make mechanism design so much harder? In a single-item auction, the seller's only real decision is setting the right threshold price. In a multi-item auction, the seller can offer complex combinations: selling items individually, bundling them together into a single package, or offering randomized lotteries (e.g., "pay \$10 for a 50% chance at Item A and a 50% chance at Item B").

To maximize revenue against a multidimensional buyer, the seller must design a "menu" of these options. The geometric and mathematical structure of this optimal menu is incredibly intricate. Constantinos Daskalakis et al. demonstrated in Strong Duality for a Multiple-Good Monopolist that finding the exact revenue-optimal mechanism for a multi-good monopolist requires solving a complex optimal transport problem, proving that the clean monotonicity of single-item pricing does not carry over.

Worse yet, this complexity scales exponentially. Li Han et al. proved in Sampling and Representation Complexity of Revenue Maximization that achieving near-optimal revenue in multi-item settings demands both sample sizes and auction rules (representation complexity) that grow exponentially with the number of items. A seller trying to extract the absolute maximum revenue faces an unmanageable explosion in the number of menu options they must present to a buyer.

Bypassing Complexity via Approximate Simplicity

Because finding the exactly optimal mechanism is computationally intractable, the core strategy in modern multi-item auction design is to trade away a tiny fraction of revenue in exchange for massive gains in simplicity. Instead of offering an infinite menu of randomized lotteries, researchers look for simple pricing structures that guarantee a high fraction of the optimal revenue.

Consider a unit-demand buyer—someone who wants at most one item out of many available. Even in this restricted setting, finding the exact optimal pricing is difficult. However, Yang Cai et al. broke through this barrier in Extreme-Value Theorems for Optimal Multidimensional Pricing by developing polynomial-time approximation schemes (PTAS) for independent items. To make these mechanisms practical, Kothari Pravesh et al. introduced the concept of "symmetric menu complexity" in Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries, proving that subexponential menu sizes are sufficient to capture near-optimal revenue by exploiting structural symmetries.

When items are complements—meaning they are worth more together than apart (like a left shoe and a right shoe)—the pricing problem becomes even more volatile. Yet, simplicity still wins. Alon Eden et al. showed in A Simple and Approximately Optimal Mechanism for a Buyer with Complements that a remarkably straightforward strategy—offering either the items individually or as a single "grand bundle"—guarantees a constant-factor approximation of the optimal revenue. Similarly, Yang Cai et al. designed simple, approximately optimal pricing structures for proportional complementarities in Simple and Approximately Optimal Pricing for Proportional Complementarities. By shifting the goal from perfect optimality to provable approximations, simple posted prices become highly effective tools.

The Multi-Buyer Frontier

While the community has made significant strides in understanding how to price multiple items for a single buyer, the ultimate open frontier is generalizing these insights to environments with multiple competing buyers.

When multiple strategic agents enter a multi-item auction, the problem undergoes a phase transition in difficulty. In a single-buyer setting, the seller optimizes against a static probability distribution of a single agent's valuation. In a multi-buyer setting, complex strategic interactions dominate. A mechanism must simultaneously screen each buyer's multidimensional preferences while managing the competitive dynamics and inventory constraints across all participants.

Furthermore, the transition to multi-item or multi-slot environments changes how modern automated bidding agents behave. Ashwinkumar Badanidiyuru demonstrates in Model Monotonicity in Autobidding Auctions: When Do Better Predictions Lead to Better Outcomes? that in multi-slot formats, improving machine learning predictions can paradoxically reduce revenue and advertiser welfare due to the complex feedback loops in automated competition.

Consequently, many of the elegant guarantees derived for single-buyer multi-item settings do not yet carry over to multi-buyer environments:

Bridging this gap requires reconciling the multidimensional geometry of multi-item menus with the game-theoretic equilibrium constraints of multi-agent competition—a challenge that defines the cutting edge of algorithmic mechanism design.

Key Foundational Work

On complexity of single-minded auction (2004) — contributed 1 concept elements to this direction.
Competitive Auctions for Multiple Digital Goods (2001) — contributed 1 concept elements to this direction.
The Power of Verification for One-Parameter Agents (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_generalization_to_multi_item_auctions_b0a0a833,
  title = {generalization to multi-item auctions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalization-to-multi-item-auctions/rdr_b0a0a83388bc4e54ba77572b621b766b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_generalization_to_multi_item_auctions_b0a0a833_v1,
  title = {generalization to multi-item auctions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalization-to-multi-item-auctions/rdr_b0a0a83388bc4e54ba77572b621b766b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake