Source-linked AI summary
Learning Simple Auctions
Jamie Morgenstern, Tim Roughgarden
TL;DR
The paper addresses how to learn revenue-maximizing simple auctions when the designer does not know the valuation distribution. It develops a framework for bounding their sample complexity and concludes that polynomial samples can support learning nearly optimal auctions from the studied classes.
Problem
Designing for a perfectly known prior is difficult in practice because the prior may be unavailable or imperfect, and the optimal auction may be complicated.
Source: §1 · p. 1Method
The framework bounds the complexity of single-buyer mechanisms and reduces multi-buyer sample-complexity analysis to single-buyer bounds for simple auction classes.
Source: §1 · p. 2Results
Polynomial-sized samples suffice to learn nearly optimal auctions from the studied simple classes, including settings with known constant-factor revenue guarantees.
Source: §1 · p. 3Takeaways & Limitations
When a near-optimal simple auction can be computed with a known prior, the framework implies it can also be learned with an unknown prior using polynomially many samples.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We present a general framework for proving polynomial sample complexity bounds for the problem of learning from samples the best auction in a class of "simple" auctions. Our framework captures all of the most prominent examples of "simple" auctions, including anonymous and non-anonymous item and bundle pricings, with either a single or multiple buyers. The technique we propose is to break the analysis of auctions into two natural pieces. First, one shows that the set of allocation rules have large amounts of structure; second, fixing an allocation on a sample, one shows that the set of auctions agreeing with this allocation on that sample have revenue functions with low dimensionality. Our results effectively imply that whenever it's possible to compute a near-optimal simple auction with a known prior, it is also possible to compute such an auction with an unknown prior (given a polynomial number of samples).
1 Introduction
The paper develops a framework for learning revenue-maximizing multi-parameter auctions from samples, addressing the limits of designing for a perfectly known prior. Its results connect prior work on simple auctions to polynomial-sample learning guarantees.
1 Introduction
- Sample-based design addresses the difficulty of specifying a perfect prior, the risk of overfitting an imperfect prior, and the complexity of the resulting optimal auction.The proposed setting uses samples from an unknown distribution and evaluates revenue on a fresh draw.Source: §1 · p. 1
1.1 Related Work
- Earlier pseudo-dimension work established learnability for simple single-parameter auction classes; this paper develops a framework for multi-parameter auctions.The cited prior work connects low pseudo-dimension and small representation error to polynomial-sample learning.Source: §1 · pp. 1–2
1 Introduction
- The framework bounds pseudo-dimension for multi-parameter auction classes, implying that a near-optimal simple auction computable with a known prior can also be learned with an unknown prior.The paper frames this as a polynomial-sample guarantee.Source: §1 · p. 2
- The technical approach measures single-buyer sample complexity and reduces multi-buyer bounds to single-buyer bounds, covering several prominent simple auction classes.The listed classes include item pricings, grand bundle pricings, and second-price item or bundle auctions with reserves.Source: §1 · p. 2
- Polynomial-sized samples suffice to learn nearly optimal auctions from the studied simple classes, including classes with known constant-factor revenue guarantees.The paper names single additive or subadditive bidders, n unit-demand bidders, and n additive bidders among the settings covered.Source: §1 · p. 3
1.1 Related Work
- Prior revenue-approximation results bound representation error for simple auction classes, while this work complements them by bounding generalization error.Earlier anonymous-item-pricing sample-complexity analysis used geometric arguments; the paper proposes linear separability as a tool applicable to more classes, including nonanonymous pricings.Source: §1.1 · p. 3
2 Preliminaries
The preliminaries set the auction and valuation assumptions, then introduce learning tools used to bound revenue sample complexity. The proof roadmap first controls bundle allocations on samples and then the revenue functions consistent with those allocations.
2 Preliminaries
- The setup considers direct-revelation auctions with quasilinear bidders and monotone valuations, whose allocations and payments define the auction.Each bidder knows their own valuation, while the designer chooses the auction before observing the bidders’ valuations.Source: §2 · p. 4
- Bidder valuations are assumed independent across bidders, with the joint distribution supported in [0,H]^n.These distributional assumptions specify the setting for the subsequent sample-complexity analysis.Source: §2 · p. 4
- Pseudo-dimension provides a real-valued function complexity measure used to derive uniform-learning sample-complexity bounds.The paper describes empirical risk minimization as choosing the function with the smallest empirical error.Source: §2 · pp. 4–5
- The roadmap bounds the number of bundle-label patterns on a sample using linear separability, then bounds revenue complexity among auctions sharing a pattern.The paper relates linear separability to compression schemes and restricted labelings.Source: §2 · pp. 5–6
3 A Framework for Bounding Pseudo-dimension Via Intermediate Discrete Labels
The section bounds pseudo-dimension by factoring each function through an intermediate label: the first factor has structured outputs, and fixing those outputs leaves a lower-complexity class of second factors.
Factorization framework
- The framework factors each f as f2(f1(x), x)=f(x), bounding the first factors’ label structure and the second factors’ pseudo-dimension after labels are fixed.This divides the analysis into possible first-factor labelings on a sample and the complexity of second factors within each resulting group.Source: §3 · pp. 6–7
Example 3.2
- For maxima of at most k linear functions from a fixed set G, the first factor is linearly separable in kd dimensions and the fixed-label second-factor class has pseudo-dimension ˜O(kd).The first factor identifies which linear function maximizes at an input; after fixing it, the second factor is linear in the input.Source: §3 · p. 7
Main theorem
- PD(F)=O(max((a+b) ln(a+b), a ln |Q|)) when F is (a, b)-factorable over Q.The bound combines the complexity of the first factor with that of the second factor after fixing its labels.Source: §3 · p. 7
Remark 3.4
- When each input permits only labels in a smaller set Qx, it can suffice to establish linear separability over those input-specific labels rather than all of Q.The remark formalizes this reduction subject to its stated conditions.Source: §3 · pp. 7–8
4 Consequences for Learning Simple Auctions
The framework bounds auction sample complexity by separating allocation structure from revenue complexity once an allocation is fixed on a sample. It applies to sequential auction classes, deriving polynomial pseudo-dimension bounds for several simple auction families.
Framework
- The framework splits each auction into an allocation rule and a revenue function, then bounds allocation patterns and revenue complexity conditional on a fixed allocation.With an allocation fixed on a sample, revenue functions may be constant or depend only mildly on valuations.Source: §4 · p. 8
Reduction and setting
- The reduction targets sequential multi-buyer auctions by relating their sample complexity to single-buyer problems.The paper assumes no ties among utility-maximizing menus or bidders.Source: §4 · p. 8
Sequential allocations
- Sequential allocations extend single-buyer allocation rules across bidders and remaining items; anonymous rules reuse the same rule, while nonanonymous rules may differ by bidder.Theorem 4.2 transfers linear separability: an a-dimensional single-buyer class yields an an-dimensional bound for nonanonymous sequential allocations, while anonymity retains a dimensions.Source: §4 · p. 9
Grand bundle pricings
- O(n log n) is the pseudo-dimension bound for non-anonymous grand bundle pricings.The supplied passages identify the class and its nonanonymous bound, but do not provide the anonymous bound.Source: §4 · p. 10
Second-price item auctions with reserves
- Second-price item auctions with reserves have allocation rules linearly separable in k + 1 anonymous or n(k + 1) nonanonymous dimensions.For fixed allocations, the revenue classes have pseudo-dimension O(k ln(k)) and O(nk ln(nk)), respectively; Yao (2015) provides small representation error for additive buyers, while the corollary establishes small generalization error.Source: §4 · pp. 10–11
Item pricings
- For the two classes, applying Theorem 3.3 under the stated factorability and separability conditions gives pseudo-dimension upper bounds O(k^2) and O(nk^2 ln(n)), respectively.Source: §4 · p. 11
A Open Problems
The open problems ask whether tighter pseudo-dimension bounds are possible for item pricings and how far the paper’s allocation analysis extends beyond additive valuations.
A Open Problems
- Can compression-style arguments tighten item-pricing pseudo-dimension bounds from k^2 and nk^2 to k and nk?The question concerns additive bidders.Source: A Open Problems · p. 13
- For general or subadditive valuations, do item pricings have pseudo-dimension O(nk) or a larger bound?Source: A Open Problems · p. 13
- Can item-specific-reserve allocations be represented as n-fold sequential allocation rules for general valuations, beyond the additive case shown?For general valuations, a bundle that is optimal under item prices may not remain optimal when second-highest bids are incorporated.Source: A Open Problems · p. 13
- What is the pseudo-dimension of second-price item auctions with item-specific reserves for valuations beyond additive or unit-demand, including submodular or subadditive values?The paper notes that a small set of relevant parameter orderings may not suffice to determine each agent’s preferred bundle.Source: A Open Problems · p. 13
B Binary Labeled Learning
Binary labeled learning studies how many labeled examples are needed to learn a target function, with sample complexity governed by the complexity of its function class.
B Binary Labeled Learning
- A set is shattered when the function class realizes every binary labeling of it; the largest such set size is the class’s VC dimension.Source: B Binary Labeled Learning · p. 13
- PAC learning seeks a hypothesis with true error below ε with probability at least 1−δ, and its sample complexity is polynomial in VC dimension, ε, and ln(1/δ).The passage also states that any PAC algorithm must use nearly as many samples as the stated bound.Source: B Binary Labeled Learning · p. 13
- Uniform learnability requires every class member’s empirical error to approximate its true error, and implies PAC learnability with the same sample size.Source: B Binary Labeled Learning · p. 14
C Formal Statements of Known Revenue Guarantees for Simple Mechanisms
Known revenue guarantees for simple mechanisms are stated for particular valuation settings, often under independence assumptions, and differ by buyer and mechanism class.
C Formal Statements of Known Revenue Guarantees for Simple Mechanisms
- For additive and unit-demand buyers with valuations independent across items, individualized item pricings suffice for a constant fraction of optimal revenue.Source: C Formal Statements of Known Revenue… · p. 14
- For a single additive buyer with independent item values, the better of optimal item pricing and grand-bundle pricing earns a constant fraction of optimal revenue.Source: C Formal Statements of Known Revenue… · p. 14
- For multiple additive buyers with values independent across items, the better of individualized-reserve second-price item auctions and second-price bundle auctions is approximately revenue-optimal.The passage derives this guarantee by applying a reduction to single-buyer problems, with a constant-factor revenue loss.Source: C Formal Statements of Known Revenue… · p. 14
- For a single subadditive buyer whose distribution is subadditive over independent items, item or grand-bundle pricing can approximately maximize revenue.The stated distribution conditions include monotonicity, subadditivity, no externalities, and product-distributed underlying coordinates.Source: C Formal Statements of Known Revenue… · p. 15
D A tighter bound on the pseudo-dimension of second-price item auctions with reserves for additive bidders
For additive bidders, the section bounds pseudo-dimension by separating the allocation and payment labels induced on samples from the revenue variation among auctions with fixed labels.
D A tighter bound on the pseudo-dimension of second-price item auctions with reserves for additive bidders
- For anonymous reserves, analyzing items separately and bounding labelings yields the shattering bound m = O(k log k).The proof exploits buyers’ independent behavior across items.Source: D A tighter bound on the… · pp. 15–16
- Anonymous item auctions and second-price item auctions with anonymous reserves have pseudo-dimension O(k log k); nonanonymous item prices or reserves have O(nk log(nk)).These bounds are for additive bidders.Source: D A tighter bound on the… · p. 15
- The proof counts intermediate sample labels combining allocations with whether each item sells at its reserve or second price, then bounds revenue complexity after labels are fixed.Source: D A tighter bound on the… · p. 15
- For nonanonymous reserves, bidder-specific orderings and labels yield m = O(nk ln(nk)); the item-price result follows from the second-price reserve proof.Source: D A tighter bound on the… · pp. 15–16
E Omitted Proofs
The omitted proofs establish separability and revenue-dimension bounds for grand-bundle and item-pricing auctions, then use these structures to bound pseudo-dimension. The resulting bounds range from O(1) for anonymous grand-bundle pricings to O(nk^2 ln(n)) for nonanonymous item prices.
Pseudo-dimension bound
- Theorem 3.3 bounds pseudo-dimension by counting allocation labelings and revenue labelings on a sample, yielding m ≤ (a + b) ln(m) + a ln |Q|.The proof bounds the number of allocation labelings using a compression scheme, then combines it with the pseudo-dimension bound for fixed-allocation revenue functions.Source: E Omitted Proofs · pp. 16–17
Allocation separability
- Theorem 4.2 shows that sequential allocations inherit linear separability by constructing a joint feature map that selects buyers’ allocations in sequence.For repeated allocations, the construction reuses the single-buyer separator while accounting for the remaining feasible items at each step.Source: E Omitted Proofs · p. 17
Grand-bundle pricings
- A single-buyer grand-bundle pricing allocation rule is 2-dimensionally linearly separable, and anonymous grand-bundle allocations retain that dimension.The anonymous case compresses the intermediate label space to {0, 1} before bounding the revenue-function pseudo-dimension.Source: E Omitted Proofs · p. 18
- Anonymous grand-bundle pricings have pseudo-dimension O(1), while nonanonymous grand-bundle pricings have pseudo-dimension O(n log n).Their fixed-allocation revenue functions are linear in one dimension and n dimensions, respectively.Source: E Omitted Proofs · p. 18
Item pricings
- Single-buyer item-pricing allocations are (k + 1)-dimensionally separable, giving anonymous item pricings pseudo-dimension O(k^2).The anonymous case compresses the intermediate label space to {0, 1}^k; the nonanonymous case uses n(k + 1) allocation dimensions and does not compress that space.Source: E Omitted Proofs · pp. 18–19
- The class F has pseudo-dimension at most O(k^2); for the nonanonymous case, it is at most O(nk^2 ln(n)), with F1 linearly separable in n(k+1) dimensions.Source: E Omitted Proofs · p. 19