acceptodds
Under review as a conference paper at ICLR 2027

Fast Iterative Combinatorial Auctions via Deep Reinforcement Learning

Abstract

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 in combinatorial auctions. 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.

Primary area:
reinforcement learning
Keywords:
iterative combinatorial auctions, deep reinforcement learning, mechanism design, price discovery, POMDP, graph neural networks, proximal policy optimization, market clearing

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_VNidOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes FastCombo, a recurrent graph policy trained with reinforcement learning for price discovery in single-minded combinatorial auctions. It proves that maximizing immediate clearing probability can require substantially more rounds than informative querying and demonstrates learned informative behavior in a small example. Experiments on CATS show competitive clearing performance and substantially reduced online price-selection computation compared with a Bayesian baseline.

Critical strengths

The theoretical construction clearly explains why informative price queries can improve subsequent decisions, and the controlled example makes the learned behavior interpretable. The reduction in online price-selection cost is supported by multiple training seeds, matched architecture controls, and detailed evaluation protocols.

Critical weaknesses

The evidence for a broader benefit from sequential information acquisition remains limited. The round-count improvement is demonstrated in a small example where another Bayesian precision also achieves the optimum, while Bayesian pricing uses fewer rounds in three of four CATS domains. The larger experiments therefore establish a computational advantage more directly than an advantage in bidder interaction. Since the timing comparison uses a default Bayesian configuration, the tradeoff against cheaper Bayesian settings at comparable clearing performance remains unclear.

The data split limits the generalization conclusions and leaves a comparison detail unresolved. Training, development, and evaluation auctions share the same source-file pool, so generalization to new source files is untested. The Bayesian prior explicitly excludes the evaluated auction’s source bid records, but it is unclear whether those records can appear during policy training. Clarifying this exposure would help assess whether the methods have comparable access to the underlying data.

Questions for authors

How do the round counts and computational advantage change when varying the Bayesian precision and sampling or optimization budget? In particular, can a cheaper Bayesian configuration achieve clearing performance comparable to FastCombo?

Can evaluated bundle–value records occur during FastCombo training, and how does this compare with their exclusion from the Bayesian prior? Are results available with training and evaluation drawn from disjoint source files?

2 comments
AuthorsOpenReview ↗

Response to Reviewer VNid

Thank you for highlighting the Bayesian-configuration and data-exposure questions. We have completed new precision and source-file separation experiments and examined cheaper Bayesian settings.

Question 1: Performance against tuned or cheaper BayesGEN. We agree that comparison with the default Bayesian configuration alone does not resolve the tradeoff against cheaper settings. We therefore varied both precision and computational budget. We tested λ ∈ {1, 0.1, 0.01}, selecting precision on development data. On independent assessment auctions, Paths BayesGEN changes from 91.65% clearing and 13.55 mean rounds at λ = 1 to 92.35% and 13.49 rounds at λ = 0.1. Arbitrary changes from 69.35% and 20.80 rounds to 69.25% and 20.79 rounds at λ = 0.01. Precision tuning therefore has modest effects in this study.

Cheaper Bayesian settings can achieve similar clearing rates and use fewer rounds, but online pricing remains substantially slower in our tests. On Paths in the separate 100-auction-per-domain timing study, BayesGEN with 128 samples and at most 5 iterations clears 89.0%, versus FastCombo’s 88.9%, and uses 11.24 versus 14.31 mean rounds. However, pricing computation remains 3.04 s per auction versus 20 ms. On Arbitrary, 32 samples and at most 10 iterations give 68.0% clearing and 20.57 rounds, versus FastCombo’s 66.1% and 24.09 rounds, at 4.25 s versus 35 ms. These paired timings use matched hardware. Similar clearing point estimates are not formal evidence of equivalent performance.

A separate matched-hardware Paths study on 100 development markets measures 15 ms per auction for FastCombo, 6.4 s for default BayesGEN, and 13.7 s for development-selected precision. These measurements concern online pricing computation and exclude bidder delays. The timing samples differ from the full clearing benchmark in Table 1. In the revision, we will add these comparisons and clearly distinguish the timing samples and measured costs.

Question 2: Record exposure and separate source files. We agree that separate evaluation auctions do not establish generalization to new source files: evaluated bundle–value records could occur during original FastCombo training. BayesGEN excluded the evaluated auction’s records when fitting its prior, but used other records from the same source file. We acknowledge this difference in access to the underlying data.

To address this concern, the new study separates 60 training, 20 development, and 20 assessment source files per domain, excluding assessment files from both policy and Bayesian-prior fitting. With three training seeds and 2,000 assessment auctions per domain, round-selected FastCombo achieves 93.28% clearing and 12.22 mean rounds on Paths, versus tuned BayesGEN’s 92.35% and 13.49 rounds. On Arbitrary, the results are 65.62% and 23.38 rounds, versus 69.25% and 20.79 rounds. Failures count as 50 rounds. Paths’ clearing and round-difference intervals include zero; Arbitrary still favors BayesGEN.

This tests source-file separation for the new fits. The files were already known to the project, and shared public calibration still uses the full corpus. Bayesian priors are now pooled across training files, and value normalization also differs, so these results complement rather than replace Table 1. We will add the evaluation with separate source files and clarify the data-access and calibration protocols in the revision.

Criticism: Limited evidence for informative pricing and round savings. We agree that the toy experiment does not establish an advantage over every Bayesian precision setting: λ = 0.1 also achieves the optimum. However, its purpose is to demonstrate that RL can learn informative queries that improve on greedy clearing, which λ = 1 reproduces on this instance. A one-step Bayesian objective can also favor informative prices here, even without explicitly optimizing future rounds.

We also agree that the original CATS experiments do not establish general round savings over BayesGEN. However, there is little room to improve its clearing rates: BayesGEN is already within 0.68–2.02 percentage points of the linear-price clearing ceiling. This limits the scope for clearing gains, although it does not explain the round-count differences. To test a setting with more room to improve clearing, we extended Paths to multi-minded bidders, where the linear-price feasibility rate is 97.55%, 33.25 percentage points above BayesGEN’s discovery rate. A FastCombo controller adapted to multi-minded settings discovers supporting prices within 50 queries in 72.65% of 2,000 fresh draws from known source files, versus BayesGEN’s 64.30%. We assess approximate price support using a clearing gap below 0.001, independently of the choice among tied demands at a given price. We will add these experiments and clarify the distinct purposes of the toy and larger-market comparisons in the revision.

The eval on separate source files and comparison to cheaper bayesian settings address my main concern, so I adjusted my score.

Reviewer_gS5UOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies sequential price selection in single-minded iterative combinatorial auctions, aiming to reduce the number of demand queries needed to reach clearing. It shows that greedily maximizing the immediate probability of clearing can be arbitrarily suboptimal, then proposes FastCombo, a recurrent bidder–item graph policy trained with PPO on auction trajectories. The paper validates its information-acquisition mechanism in a controlled one-item setting and compares clearing performance and online price-selection cost with Bayesian and subgradient auctions on CATS instances.

Critical strengths
  • The paper identifies and proves a genuine limitation of greedy clearing objectives. Proposition 1 in Section 3 presents a one-item, two-bidder construction in which every policy that greedily maximizes immediate clearing probability requires (K+2)/3(K+2)/3 expected rounds, while an informative policy needs only logarithmically many. This concrete result isolates a failure of one-step objectives even when the valuation distribution is correct and feedback is exact.

  • The empirical evaluation carefully distinguishes what it does and does not establish. Section 7 separates the exact toy setting from the CATS study, uses ten FastCombo seeds on a 5,000-instance holdout, reports uncertainty intervals, and notes that Bayes-GEN uses fewer rounds in three of the four CATS domains (Table 1). Table 2 nevertheless shows a substantial, well-defined reduction in online price-selection cost, supporting the practical amortization claim without conflating it with query savings.

Critical weaknesses
  • The CATS training objective is misaligned with the stated goal of minimizing expected rounds, and the results do not demonstrate improved query efficiency on CATS. Equation 8 defines the objective as minimizing expected capped query count, with a reward of −1-1 per posted price. However, Section 7.2 trains the CATS policies using the discounted normalized-gap surrogate in Equation 11, with γ=.99\gamma=.99; unsuccessful episodes also use critic bootstrapping at the 50-round cap. This may be a reasonable shaping objective for learning to clear, but it differs from the expected-query objective defined in Section 4.

  • The results reflect this distinction. In Table 1, Bayes-GEN uses fewer rounds on the commonly cleared subset in Arbitrary, Paths, and Regions. Table 2 shows that FastCombo has higher capped mean rounds in three domains and no significant advantage in Scheduling. Thus, beyond the deliberately constructed three-profile case, the paper demonstrates amortized online computation and competitive clearing, but does not show that trajectory-level RL learns generally more informative or query-efficient price sequences. To address this gap, the authors could compare the current surrogate with direct unit-query-cost training on one or more CATS domains. Alternatively, they could narrow the central empirical framing to amortized price computation and competitive clearing.

Questions for authors
  1. In Section 7.2, did the authors evaluate policies trained directly with Equation 8’s unit per-query reward, without the normalized-gap surrogate in Equation 11? If so, please report the resulting trade-off between clearing performance and capped rounds. This would help establish whether the CATS policies optimize the stated round-minimization objective or primarily the surrogate.

  2. Can the authors also quantify, on the CATS development set or a representative domain, the relationship between Equation 11’s normalized-gap return and capped query count Q50Q_{50}? Evidence that higher surrogate return reliably predicts fewer queries would help address the objective-mismatch concern.

1 comment
AuthorsOpenReview ↗

Response to Reviewer gS5U

Thank you for the constructive review and for suggesting these two experiments. We agree that the normalized-gap reward differs from the round-minimization objective. We have now tested direct round-cost training and measured the relationship between gap return and round count.

Questions 1–2: Direct-cost training and the relationship between gap return and rounds. We agree that the gap reward differs from the stated round-minimization objective and that higher gap return need not imply fewer rounds. To address both concerns, we tested direct round-cost training and examined the relationship between gap return and round count. For Question 1, direct training used Equation (8): −1 per round, no discounting, and termination at the 50-round limit. We compared this with the original gap-based training on Paths and Arbitrary, using the same architecture and training budget, three paired seeds, and 2,000 assessment auctions per domain from source files excluded from training.

When checkpoints are selected by round count, gap-based training achieves 93.28% clearing and 12.22 mean rounds on Paths, versus 1.03% and 49.58 rounds for direct-cost training. On Arbitrary, the corresponding results are 65.62% and 23.38 rounds, versus 32.30% and 39.04 rounds. Average round counts include unsuccessful auctions, each counted as 50 rounds. Gap-based training also performs better when checkpoints are selected by clearing rate.

These results support the practical benefit of the gap reward under the tested training settings. It distinguishes unsuccessful prices by their distance from clearing, whereas every failed auction receives the same total penalty under direct-cost training. This provides useful feedback before clearing occurs. The comparison also changes discounting and the treatment of the round limit, and uses our existing training settings; separately tuning direct-cost training could improve its performance.

For Question 2, we evaluated all 50 checkpoints from each of the six gap-trained fits on development auctions. Pearson correlations between mean discounted gap return and mean capped rounds range from −0.980 to −0.579: higher return generally accompanies fewer rounds. Selecting checkpoints by return rather than round count adds 0.14–0.70 mean rounds on Paths; the selected checkpoints coincide on Arbitrary.

The relationship is imperfect: 167–351 of the 1,225 checkpoint pairs per fit disagree in their ranking. The surrogate can prefer several small gaps to fewer large gaps. These are descriptive comparisons across dependent checkpoints, using observed rewards without the critic’s continuation estimate. They support the surrogate as a useful training signal, while selecting checkpoints by round count directly targets the stated evaluation objective. We will add both analyses and explain the training rationale, the relationship to round performance, and the limitations in the revision.

Criticism: The CATS results do not demonstrate general round savings. We agree that the original CATS results do not establish general round savings over BayesGEN. However, they do establish competitive clearing and faster online computation. For clearing performance specifically, BayesGEN is already within 0.68–2.02 percentage points of the reported linear-price clearing ceiling, leaving little room to improve clearing rates. In a separate multi-minded Paths extension, an adapted FastCombo policy discovers supporting prices within 50 queries in 72.65% of 2,000 fresh draws from known source files versus BayesGEN’s 64.30%. The corresponding linear-price feasibility rate is 97.55%. We assess approximate price support using a clearing gap below 0.001, independently of the choice among tied demands at a given price. We will add these experiments and controller details, and clarify the scope of our claims, in the revision.

Reviewer_GLxJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

FastCombo learns item-price policies for iterative combinatorial auctions with single-minded bidders (POMDP, recurrent bidder–item graph policy, PPO), motivated by a proof that greedy clearing can need far more rounds than an informative policy. It reaches 1.65 versus 1.85 expected rounds on a three-profile toy; on four CATS domains it clears 0.36–2.54 points less than BayesGEN and needs more rounds in three of them, but cuts online pricing computation by roughly 300–900×.

Critical strengths
  1. Rigorous, honest evaluation: ten seeds, a dev/holdout split, paired bootstrap, a reproduction package, and negative results stated in the main text.
  2. Correct theory, and a clean demonstration that RL learns the informative opening in the toy.
Critical weaknesses
  1. It does not win on the problem it poses. Rounds are the stated cost (108 rounds over 22 business days), yet on CATS FastCombo needs more rounds than Bayes in three of four domains and clears less in all four. Its only gain is milliseconds of online computation, but the timing excludes bidder responses — the cost the paper itself motivates — and 3,812 CPU-hours of training come with no break-even. CATS training also optimizes a gap surrogate and selects checkpoints by clearing, so the round-minimization thesis is never tested at scale.
  2. The theory targets a different comparator. Prop. 1 concerns exact-clearing greedy (λ→∞) — in effect linear scan versus binary search — while the baseline uses λ = 1, and App. A.3 shows that λ = 0.1 also reaches 1.65. The only evidence of learned information acquisition is thus a choice of the baseline's precision.
Questions for authors
  1. BayesGEN on CATS with smaller λ, and FastCombo trained with the per-query reward and selected by rounds?
  2. In what setting is online pricing computation the binding cost, and after how many auctions does training break even?
1 comment
AuthorsOpenReview ↗

Response to Reviewer GLxJ

Thank you for the careful review. We completed the requested reward, checkpoint-selection, and Bayesian-precision comparisons. The results support the use of the gap reward, although general round savings remain unestablished.

Criticism 1 and Question 1: Round efficiency with direct-cost training and tuned BayesGEN. We agree that the original CATS results do not establish general round savings or higher clearing rates than BayesGEN. To address your question about direct round-cost training and Bayesian precision, we tested Paths and Arbitrary, the domains with the smallest and largest original clearing deficits, using three paired training seeds and 2,000 assessment auctions per domain. Checkpoints were selected by capped round count, and BayesGEN precision was selected on development data from λ ∈ {1, 0.1, 0.01}.

On Paths, gap-trained FastCombo achieves 93.28% clearing and 12.22 mean rounds, versus 1.03% and 49.58 rounds for direct-cost training, and 92.35% and 13.49 rounds for tuned BayesGEN. On Arbitrary, the corresponding results are 65.62% and 23.38 rounds, 32.30% and 39.04 rounds, and 69.25% and 20.79 rounds. Average round counts include unsuccessful auctions, each counted as 50 rounds. The Paths round difference between FastCombo and tuned BayesGEN has a 95% interval of [−2.91, +0.01]; Arbitrary still favors BayesGEN. This comparison uses our existing training settings; separately tuning direct-cost training could improve its performance.

For clearing performance, however, BayesGEN is already within 0.68–2.02 percentage points of the linear-price clearing ceiling, leaving little room to improve clearing rates. To investigate clearing performance beyond these benchmarks, we extended Paths to multi-minded bidders, where BayesGEN discovers supporting prices in 64.30% of markets against a linear-price feasibility rate of 97.55%. A FastCombo controller adapted to multi-minded settings discovers supporting prices in 72.65% of the same 2,000 markets, an 8.35-point improvement. We assess approximate price support using a clearing gap below 0.001, independently of the choice among tied demands at a given price. We will add these experiments, their protocols, and uncertainty estimates, and clarify the scope of our claims about rounds and clearing, in the revision.

Criticism 2: Does the toy comparison match the theory’s greedy comparator? We agree that λ = 0.1 matches 1.65 rounds in the original toy. However, the purpose of this comparison is to show that RL can learn informative queries that improve on greedy clearing, whose behavior λ = 1 reproduces on this toy. Reducing λ can incidentally favor informative prices, as λ = 0.1 does here, but the Bayesian rule still optimizes a one-step score without accounting for how today’s query affects future rounds. We will clarify this connection between the theory and the toy comparison.

Question 2: When does online computation matter, and when does training break even? We agree that faster price updates do not resolve the bidder-response delays motivating the spectrum-auction application. However, moving computation offline can be useful in repeated auctions with fast software bidders. FastCombo is trained beforehand, so little computation is needed during an auction: on matched hardware, Paths pricing takes 15 ms per auction versus 6.4 s for default BayesGEN. This benefit starts with the first auction. Approximately 22,000 auctions are needed for the accumulated computational savings to offset one policy’s training cost, assuming no retraining. The paper’s 3,812 allocated CPU-hours cover 40 training runs, rather than one policy. Subgradient pricing is cheaper still, but the paper’s domain-tuned baseline clears only 80.38% of Paths auctions versus FastCombo’s 95.10%, even with its step size chosen using benchmark outcomes. Selecting a separate step size for each auction can improve clearing, but the reported procedure requires hindsight unavailable during deployment. FastCombo therefore offers inexpensive online pricing with stronger clearing than the domain-tuned subgradient baseline; its practical value depends on bidder delays and clearing requirements. We will add the training-cost accounting and clarify the scope of the computational benefit.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Clarification on the Scope of the Revision

We would like to clarify the scope of our planned revision. The preliminary multi-minded results were intended to illustrate that, beyond the toy example, there are settings where one-step Bayesian pricing leaves room for improvement and an adapted RL approach achieves gains. Since multi-minded bidders go beyond the setting studied in this paper, we intend to reserve these experiments for follow-up work rather than include them in the revision, clarifying our earlier statements. All other experiments discussed in our rebuttal concern the paper's setting and will be included as planned.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.