Source-linked AI summary
Fast Iterative Combinatorial Auctions via Deep Reinforcement Learning
Luis F. Paul Tosta, Quinn Arnold, Gianluca Brero
TL;DR
Iterative combinatorial auctions require costly rounds, while Bayesian pricing does not explicitly optimize the future value of information and uses repeated online inference and optimization. FastCombo learns sequential price policies offline, and across four CATS domains it achieves competitive clearing with substantially lower measured online price-selection computation than the standard Bayesian baseline.
Problem
Iterative combinatorial auctions require repeated consequential bidder decisions, while Bayesian one-step pricing omits future information value and its general rule requires repeated online sampling and optimization.
Source: §1 · pp. 1–2Method
FastCombo formulates minimizing expected rounds to clearing as a POMDP and trains offline on complete auctions to learn price policies that use public feedback.
Source: §1 · p. 2Results
Across four CATS domains, FastCombo achieves competitive clearing while reducing measured online price-selection computation per auction by roughly 300–900 times relative to the standard Bayesian baseline.
Source: §1 · p. 2, §9 · p. 10Takeaways & Limitations
The one-item experiment demonstrates informative query selection, while CATS shows competitive clearing with substantially lower measured price-selection computation.
Source: §9 · p. 10The study uses single-minded bidders with public bundles and myopic demand; scaling and transfer, larger markets, multi-minded and spectrum valuations, and strategic bidders remain untested.
Source: §8 · p. 10
Abstract
from arXiv · showhide
Iterative combinatorial auctions are used in spectrum allocation, transportation, and industrial procurement, but rounds are costly. We introduce FastCombo, a deep reinforcement learning approach to sequential price discovery. Bayesian pricing has sharply reduced auction rounds even against subgradient benchmarks tuned with hindsight for each instance, but relies on a one-step objective and repeated online inference and optimization. We prove that greedily maximizing immediate clearing probability can require arbitrarily more rounds in expectation than an informative policy, even with the true valuation distribution known. FastCombo learns price policies offline, assigning credit to queries for the future decisions they enable and producing each online price update with a single neural-network forward pass. We formulate the objective of minimizing expected rounds to clearing in single-minded auctions as a partially observable Markov decision process and train a recurrent bidder-item graph policy over complete auction trajectories. In a one-item experiment, all five trained policies learn an informative opening, reducing expected rounds from 1.85 to 1.65 relative to the tested Bayesian one-step rule. Across four domains from the Combinatorial Auction Test Suite, FastCombo achieves competitive clearing while reducing measured online price-selection time per auction by a factor of roughly 300-900 relative to the standard Bayesian baseline. These results demonstrate the value of learning sequential price policies for both information acquisition and online computational efficiency.
1. Introduction
Iterative combinatorial auctions impose costly bidder deliberation, and existing Bayesian pricing leaves both future information value and online computation as challenges. FastCombo learns sequential price policies; experiments report competitive CATS clearing with lower measured online price-selection computation.
1. Introduction
- Iterative auctions avoid eliciting complete valuation functions, but repeated bidding decisions impose deliberation costs; Canada’s 2014 700 MHz auction took 108 rounds over 22 business days.Aggressive price increments can shorten the process but risk overshooting clearing prices and sacrificing allocative efficiency.Source: §1 · p. 1
- Even an instance-level subgradient oracle retrospectively selecting the fastest run required 21.3 rounds on Arbitrary instances, versus 4.5 for the general Bayesian rule.The comparison covers single-minded Arbitrary instances cleared by all compared methods.Source: §1 · p. 2
- Bayesian one-step pricing does not explicitly value information that may distinguish valuations requiring different later prices, and its general rule repeatedly samples and optimizes online.These challenges motivate policies that account for future demand responses while keeping online price selection inexpensive.Source: §1 · p. 2
- FastCombo formulates expected rounds to clearing as a POMDP and trains a recurrent graph policy offline over complete auctions to credit queries for information and later clearing.At deployment, one neural-network forward pass maps public feedback to the next item prices.Source: §1 · p. 2
- Across four CATS domains, FastCombo achieves competitive clearing while using roughly 300–900 times as much measured online price-selection computation per auction as the standard Bayesian baseline.The measurements exclude offline training; broader query savings and scalability to large spectrum auctions remain open.Source: §1 · p. 2
- All five trained policies clear in 1.65 expected rounds, versus 1.85 for the Bayesian one-step rule in the controlled one-item experiment.The learned opening accepts a lower immediate clearing chance to make the next query decisive if clearing fails.Source: §1 · p. 2
2. Preliminaries
The preliminaries specify single-minded bidders, item prices, demand feedback, and the clearing criterion. The auction’s objective is to reach clearing in as few posted-price rounds as possible.
2. Preliminaries
- The model has m indivisible items and n single-minded bidders, each with a nonempty desired bundle and a value for any bundle containing it.Each bidder’s value is zero for bundles that do not contain its desired bundle.Source: §2 · p. 2
- The auctioneer posts a common vector of nonnegative item prices, and item prices add to determine the cost of a bidder’s desired bundle.With bundles known, myopic best-response demand reports indicate whether the bidder’s value covers that quoted bundle price; ties favor demand unless stated otherwise.Source: §2 · pp. 2–3
- An efficient allocation maximizes total bidder value while assigning each item at most once.The clearing potential adds bidders’ maximum utilities to posted item prices; its gap above optimal welfare is nonnegative, and zero gap characterizes clearing prices when they exist.Source: §2 · p. 3
- The protocol counts each posted price vector as one demand query and auction round, and aims to reach clearing in as few rounds as possible.Numerical clearing uses a fixed tolerance εclr > 0.Source: §2 · p. 3
3. The Value of Informative Queries
The section compares greedy immediate clearing with informative queries under a known valuation distribution. A construction shows that greedy policies can require unboundedly more expected rounds to clear.
3. The Value of Informative Queries
- The analytical comparison assumes both policies know the true valuation distribution and observe demand and clearing feedback while realized values remain hidden.Values are drawn once from F and remain fixed throughout the auction.Source: §3 · p. 3
- For every K ≥ 2, a one-item, two-bidder construction gives greedy policies an expected round count of (K + 2)/3, while an informative policy needs at most ⌈log2(K + 1)⌉.Both policies know the true distribution, observe demand and exact-clearing feedback, and count every posted price as one round; their ratio is unbounded over the family.Source: §3 · p. 4
- Greedy tests the most likely remaining profile, whose failed query eliminates only one possibility; an informative query tests a middle profile and divides the remaining possibilities in half.The construction therefore yields linear versus logarithmic growth in rounds.Source: §3 · p. 4
- The result establishes that greedy can be suboptimal, but does not claim this for every distribution or quantify the loss on typical auctions.Expected round counts average values drawn from the same stated distribution, motivating whole-sequence optimization without guaranteeing reinforcement learning finds the optimal policy.Source: §3 · pp. 3–4
4. The Auction as a POMDP
The paper formulates minimizing expected rounds to clearing as a POMDP, with hidden values and public auction feedback. Policies choose prices from observable histories, and unit query cost makes maximizing return equivalent to minimizing charged rounds.
4. The Auction as a POMDP
- The POMDP objective minimizes expected rounds to clearing, enabling reinforcement learning to credit queries for later decisions they support.The auction instance remains fixed during the interaction, and clearing leads to an absorbing terminal state.Source: §4 · p. 4
- The public response to a price includes binary bidder demand and a clearing indicator, with observations and termination deterministic given the instance and posted price.A policy chooses the next price distribution from the observable history.Source: §4 · p. 4
- Charging −1 for each posted price, including the clearing query, makes maximizing return minimize expected charged rounds under a round budget.Clearing probability is also reported because a budget-round clear and failure incur the same capped query count.Source: §4 · p. 4
- Private simulator values may provide training feedback, but realized values and rewards do not enter the policy’s public observations.The objective is expected charged rounds, while experiments specify whether training uses unit query cost or a dense surrogate and how it handles the round limit.Source: §4 · p. 4
5. FastCombo Policy
FastCombo learns a price policy offline from simulated auctions, using recurrent item states and a bidder–item graph to map public auction history to price updates. Online, each query requires one neural-network evaluation.
5. FastCombo Policy
- FastCombo combines recurrent item states with a bidder–item graph so prices can reflect successive demand responses and conflicts between overlapping bundles.Two graph passes exchange information between items and bidders; shared bidder maps and mean aggregation make the actor invariant to bidder order.Source: §5 · p. 5
- The policy uses public value bounds that tighten when bidders accept or reject bundles, alongside normalized public auction features.Bounds begin at [0, Cd], where Cd is a public valuation ceiling; neither private values nor realized training rewards enter the actor's inputs or memory.Source: §5 · p. 5
- A shared 32-dimensional GRU item memory summarizes successive price–demand responses.The reset input precedes any response and does not update the recurrent state.Source: §5 · p. 5
- Each query emits a simultaneous price vector directly, without price repair or a second stage.Evaluation is deterministic; training uses clipped independent Normal draws and PPO scores the censored distribution, including boundary probabilities.Source: §5 · p. 5
6. Related Work
Prior work studies iterative price discovery, neural value models, and learned auction mechanisms. FastCombo instead learns the auctioneer’s simultaneous common-item price updates offline, with fixed bidder responses.
6. Related Work
- FastCombo amortizes price-update computation into offline training, unlike Bayesian updates or neural value models followed by optimization.Bayesian clearing methods maintain posterior beliefs and compute price updates; Soumalias et al. (2025, 2024) use neural value models but still optimize after updating them.Source: §6 · p. 5
- Unlike sequential posted-price or revenue-focused mechanisms, FastCombo posts common item prices simultaneously and uses aggregate demand to seek exact market clearing.The cited mechanisms typically visit agents sequentially or optimize revenue.Source: §6 · pp. 5–6
- Unlike multi-agent learning of bidder strategies under a fixed auction, FastCombo fixes bidder responses and learns the auctioneer’s policy.The comparison distinguishes what is learned: bidder strategies in the separate line of work, versus auctioneer price updates here.Source: §6 · p. 6
7. Experiments
The experiments test whether FastCombo learns informative price queries and how its clearing performance trades off against online computation. On a one-item task and four CATS domains, they also examine learned query behavior and architecture components.
7. Experiments
- The one-item Bayesian comparator uses the exact three-profile distribution, whereas CATS BayesGEN uses fitted Gaussian-process priors with repeated MCEM sampling and optimization each round.Both experiments use the recurrent graph actor and privileged critic, trained separately with PPO; private values are absent from the public actor path.Source: §7 · p. 6, §7.1 · p. 6
7.1. Learning Informative Price Queries
- 1.65 expected rounds for all five trained policies versus 1.85 for the Bayesian one-step rule shows learned informative openings on the one-item task.Each learned policy clears all three profiles within two rounds; the first query reveals which price to post next if immediate clearing fails.Source: §7.1 · p. 7, Figure 1 · p. 7
- Prices from 3.429 to 3.628 clear the middle profile with probability .35, while demand counts of zero or two identify the low or high profile for the next query.The second prices lie in [1.479, 1.542] and [5.864, 6.000], respectively.Source: §7.1 · p. 7
7.2. CATS: Clearing and Online Computation
- Across four CATS domains, FastCombo trails BayesGEN by 0.36–2.54 percentage points in clearing, exceeds SG-AuctionD in every domain, and stays within 3.54 points of the linear-price ceiling.On common-cleared subsets, FastCombo uses fewer rounds than SG-AuctionD in every domain and SG-AuctionI in three; it uses fewer than BayesGEN on Scheduling (4.64 versus 4.86).Source: §7.2 · p. 8, Table 1 · p. 8
Online computation.
- 4.97–35.44 milliseconds per auction is FastCombo’s measured price-selection time, roughly 300–900 times lower than BayesGEN; it clears 0.9–2.8 percentage points fewer auctions in the timing sample.FastCombo uses 0.02–4.30 more capped rounds on average in that 100-auction-per-domain sample; the measured computation excludes bidder-response delays.Source: Online computation · p. 9, Table 2 · p. 9
7.3. Architecture Ablations
- 6.60–18.52 percentage points lower clearing follows replacing the structured encoder with a recurrent dense control, while removing recurrence reduces clearing by 2.68–5.33 points.Paired 95% intervals favor FastCombo in all four domains under the matched training protocol.Source: §7.3 · p. 9, Table 3 · p. 9
8. Scope and Limitations
The study evaluates single-minded bidders with public bundles and myopic demand. Its scope and computation measurements leave several practical boundaries explicit.
8. Scope and Limitations
- The study assumes single-minded bidders with public bundles and myopic demand.Source: §8 · p. 10
- Rewards, the critic, and the clearing test use private values; public clearing certificates and strategyproof allocation and payment rules remain separate mechanism-design requirements.Source: §8 · p. 10
- The one-item experiment establishes informative learning only on a three-profile distribution under the specified Bayesian objective and precision, not the same mechanism on CATS or a general query advantage.Source: §8 · p. 10
- Fixed-size, separately trained CATS domains leave scaling and transfer untested, while computation measurements exclude offline training and bidder-response costs.Source: §8 · p. 10
9. Conclusion
FastCombo combines complete-trajectory training with inexpensive online price evaluation. The appendix interprets the clearing gap and proves that greedy clearing can be arbitrarily worse than informative querying.
9. Conclusion
- FastCombo trains over complete auction trajectories and evaluates online prices inexpensively; broader round savings and extensions to larger markets and other valuation and bidder settings remain open.Source: §9 · p. 10
A.1. Clearing Gap and Efficient Allocations
- At efficient allocations, G = 0 exactly when bidders receive utility-maximizing choices and unsold items have zero prices, giving the gap a welfare interpretation.Source: §A.1 · p. 12
A.2. Proof of the Greedy-Clearing Separation
- In the constructed K-profile family, greedy queries test profiles sequentially while informative queries halve the remaining candidates, making their expected-round ratio diverge with K.Source: §A.2 · pp. 12–13
A.3. Analysis of the One-Item Experiment
The one-item analysis contrasts informative openings with Bayesian one-step pricing, then describes the policy architecture, training procedure, and CATS training dynamics.
A.3. Analysis of the One-Item Experiment
- The cited theorem reports that a first price in (a + s, a + s + w), followed by a clearing price for the identified regime, minimizes expected rounds among policies that clear all three regimes.Exact Bayesian updating under Equation (15) costs 2 − ρ2 + ρ0, exceeding the stated policy’s cost of 2 − ρ1 by 1 − 2ρ2 > 0.Source: §A.3 · p. 13
- The Bayesian one-step rule first chooses a2, leaving low and middle indistinguishable on failure, for a cost of 2−ρ2+ρ0.Source: §A.3 · p. 13
- 1.65 expected rounds for the informative optimum versus 1.85 for Bayesian pricing at λ=1; at λ=.1, Bayesian pricing also takes 1.65.Source: §A.3 · p. 14
B.1. Public Features and Architecture
- Public history feeds a shared 32-unit GRU and two-pass bidder-item graph encoder; an itemwise decoder emits clipped price actions, while private values enter only the critic.Source: §B.1 · pp. 14–15
B.2. Optimization and Query Caps
- CATS training treats clearing as termination and an uncleared query cap as truncation, bootstrapping the latter with the critic; PPO updates use 2,048 transitions across eight environments.Source: §B.2 · p. 15
B.3. Training Dynamics on CATS
- Across all four domains, clearing rose rapidly and then remained near a plateau across 50 development evaluations per seed, with temporary declines at some checkpoints.Source: §B.3 · p. 15
B.4. Conceptual Experiment Protocol
The protocol separates a controlled one-item study from CATS benchmarking, with distinct reward, horizon, and checkpoint-selection rules. CATS evaluation also specifies holdout uncertainty procedures and a separate online-computation comparison.
B.4. Conceptual Experiment Protocol
- The one-item study used γ = 1, −1 per query, a three-query horizon, and terminal actors; CATS used γ = .99, normalized-gap reward, a 50-query cap, and development-selected checkpoints.Source: §B.4 · p. 15
- The public actor uses per-item recurrence, two graph passes, shared itemwise decoding, and a fixed price map; training samples a censored Normal action law, while evaluation uses the clipped location.Source: Figure 2 · p. 16, §B.4 · p. 16
C.1. CATS Instances, Baselines, and Uncertainty
- CATS training, development, and holdout draw from 100 source files per domain; development and holdout populations contain 1,000 and 5,000 auctions, respectively.Source: §C.1 · p. 16
- Clearing intervals bootstrap source files jointly with FastCombo seeds, while query comparisons condition on instances cleared by all included methods.Source: §C.1 · p. 18
C.2. Online Computation
- The timing study compares price-generation components on 400 holdout auctions, excluding offline training and several surrounding costs; reported training totals use different hardware and do not determine a same-hardware break-even count.Source: §C.2 · pp. 19–20
D. Architecture Controls and Ablations
The controls compare the complete structured encoder with a recurrent dense alternative and test selected architecture changes. The comparison supports the structured encoder under shared PPO, but does not isolate message passing from other design differences.
D. Architecture Controls and Ablations
- The dense control retained recurrent item states and training-only private-value access, with 386,022 parameters versus 386,446 for the graph model.Source: D. Architecture Controls and Ablations · p. 20
- The structured-encoder comparison supports the complete encoder under shared PPO, but does not isolate message passing from parameter sharing, representation layout, or optimization effects.Changing graph depth or the critic had smaller, domain-dependent effects; removing bidder bounds changed clearing by less than half a percentage point.Source: D. Architecture Controls and Ablations · p. 20
- No-recurrence Paths results use nine matched seeds because one prespecified ablation run did not complete; the re-evaluated Paths reference was 95.106%, versus 95.104% originally.Source: D. Architecture Controls and Ablations · p. 20
- Round comparisons use matched-seed intersections of instances cleared by all three architectures, while capped means include all matched-seed auctions and charge failures 50 rounds.Source: D. Architecture Controls and Ablations · p. 20, Table 7 · p. 21, Table 8 · p. 21