pith. sign in

arxiv: 2411.09355 · v3 · submitted 2024-11-14 · 💻 cs.GT · cs.AI· cs.LG

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All

Ermis Soumalias , Jakob Heiss , Jakob Weissteiner , Sven Seuken This is my paper

Pith reviewed 2026-05-23 17:53 UTC · model grok-4.3

classification 💻 cs.GT cs.AIcs.LG
keywords combinatorial auctionsmachine learningpreference elicitationvalue queriesdemand queriesiterative auctionseconomic efficiencyMLHCA
0
0 comments X

The pith

A machine learning algorithm that combines value and demand queries powers a new combinatorial auction with up to ten times lower efficiency loss.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces an ML method for preference elicitation in iterative combinatorial auctions that makes provable use of information from both value queries and demand queries. Earlier work relied on only one query type, but integrating both improves how well the system learns bidder preferences in practice. Building on this, the authors present MLHCA, an auction design that achieves substantially higher efficiency while cutting the number of queries bidders must answer. A reader would care because combinatorial auctions face an exponentially large space of bundles, so better elicitation directly addresses the barrier to deploying them at scale.

Core claim

MLHCA is a new ML-powered iterative combinatorial auction whose elicitation algorithm integrates the full information available from both value queries and demand queries. Experiments demonstrate that this approach reduces efficiency loss by up to a factor of 10 and requires up to 58 percent fewer queries than the previous state-of-the-art method, while also lowering bidders' cognitive load.

What carries the argument

The ML preference-elicitation algorithm that jointly processes value queries and demand queries to guide iterative bidding.

If this is right

  • Combinatorial auctions become viable for larger item sets because the exponential growth in bundles is offset by more efficient information gathering.
  • Bidders face lower participation costs without sacrificing auction outcomes.
  • Future iterative auction designs can treat value and demand queries as complementary rather than alternative inputs.
  • The performance gap between ML-based and traditional elicitation methods narrows when both query types are available.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The hybrid query approach could be adapted to other preference-elicitation settings such as procurement or resource allocation problems.
  • Lower query counts may increase bidder participation rates in practice, an effect not measured in the reported experiments.
  • The method suggests that similar gains might appear if the same ML integration is applied to non-iterative or sealed-bid combinatorial formats.
  • Real-world deployment would benefit from online learning variants that update the model as new auctions run.

Load-bearing premise

The bidder preference distributions and test cases used in the experiments match the distributions that would appear in real deployed combinatorial auctions.

What would settle it

Running MLHCA on a fresh collection of bidder preferences drawn from a distribution outside the paper's test suite and finding no reduction in efficiency loss or query count relative to prior methods.

Figures

Figures reproduced from arXiv: 2411.09355 by Ermis Soumalias, Jakob Heiss, Jakob Weissteiner, Sven Seuken.

Figure 1
Figure 1. Figure 1: Efficiency loss paths (i.e., regret plots) of MLHCA compared to BOCA, ML-CCA and CCA. Shown are averages [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Efficiency of MLHCA with and without the bridge [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of scaled prediction vs. true values for an mMVNN trained with different query types for the national [PITH_FULL_IMAGE:figures/full_fig_p031_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of MLHCA’s performance in the MRVM domain: (a) Efficiency with and without the bridge bid; (b) [PITH_FULL_IMAGE:figures/full_fig_p040_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Normalized Inferred Social Welfare of MLHCA (with the bridge bid) in all domains. Shown are averages over 50 [PITH_FULL_IMAGE:figures/full_fig_p041_5.png] view at source ↗
read the original abstract

We study the design of iterative combinatorial auctions (ICAs). The main challenge in this domain is that the bundle space grows exponentially in the number of items. To address this, recent work has proposed machine learning (ML)-based preference elicitation algorithms that aim to elicit only the most critical information from bidders to maximize efficiency. However, while the SOTA ML-based algorithms elicit bidders' preferences via value queries, ICAs that are used in practice elicit information via \emph{demand queries}. In this paper, we introduce a novel ML algorithm that provably makes use of the full information from both value and demand queries, and we show via experiments that combining both query types results in significantly better learning performance in practice. Building on these insights, we present MLHCA, a new ML-powered auction that uses value and demand queries. MLHCA significantly outperforms the previous SOTA, reducing efficiency loss by up to a factor 10, with up to 58\% fewer queries. Thus, MLHCA achieves large efficiency improvements while also reducing bidders' cognitive load, establishing a new benchmark for both practicability and efficiency. Our code is available at https://github.com/marketdesignresearch/MLHCA.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces MLHCA, an ML-powered iterative combinatorial auction that elicits bidder preferences using both value and demand queries. It claims a provable guarantee that the algorithm fully exploits information from both query types, and reports experimental results showing up to a factor-of-10 reduction in efficiency loss and up to 58% fewer queries relative to prior SOTA ML-based ICAs. Code is released at the provided GitHub link.

Significance. If the performance gains prove robust, the work would meaningfully advance practical ICA design by improving allocative efficiency while lowering bidder cognitive load. The combination of a claimed information-theoretic guarantee with open code is a positive feature for reproducibility.

major comments (2)
  1. [Experiments] Experiments section (and abstract): the factor-of-10 efficiency-loss reduction and 58% query reduction are measured exclusively on synthetic bidder preference distributions. No sensitivity analysis across distribution families, no external validation against real auction data (e.g., spectrum or procurement complementarities), and no discussion of budget constraints or correlation structures are provided; this directly undermines the practical-superiority claim.
  2. [Algorithm and theoretical analysis] Algorithm and theoretical analysis section: the abstract asserts that the method 'provably makes use of the full information from both value and demand queries,' yet the manuscript provides no explicit statement of the information measure, no derivation showing strict improvement over value-query-only baselines, and no counter-example or edge-case verification; without these details the theoretical contribution cannot be assessed as load-bearing.
minor comments (2)
  1. [Introduction] The abstract and introduction would benefit from a short table comparing query types and information content across prior ML-ICA methods.
  2. [Figures] Figure captions should explicitly state the number of runs, random seeds, and statistical significance tests used for the reported efficiency and query counts.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive feedback. We address each major comment below and indicate where revisions will be made to improve the manuscript.

read point-by-point responses

  1. Referee: [Experiments] Experiments section (and abstract): the factor-of-10 efficiency-loss reduction and 58% query reduction are measured exclusively on synthetic bidder preference distributions. No sensitivity analysis across distribution families, no external validation against real auction data (e.g., spectrum or procurement complementarities), and no discussion of budget constraints or correlation structures are provided; this directly undermines the practical-superiority claim.

    Authors: We agree that the experiments rely exclusively on synthetic distributions and that this limits the strength of the practical-superiority claims. In the revised version we will add sensitivity analysis across additional distribution families, include an explicit discussion of budget constraints and correlation structures, and clearly state the limitations regarding the absence of real auction data validation. revision: yes

  2. Referee: [Algorithm and theoretical analysis] Algorithm and theoretical analysis section: the abstract asserts that the method 'provably makes use of the full information from both value and demand queries,' yet the manuscript provides no explicit statement of the information measure, no derivation showing strict improvement over value-query-only baselines, and no counter-example or edge-case verification; without these details the theoretical contribution cannot be assessed as load-bearing.

    Authors: The manuscript contains a theoretical argument that the algorithm exploits information from both query types. We nevertheless accept that the current presentation lacks sufficient explicitness. We will revise the section to state the information measure clearly, provide a derivation of the improvement relative to value-query-only baselines, and include edge-case verification. revision: yes

Circularity Check

0 steps flagged

No circularity: new algorithm and empirical results are self-contained

full rationale

The paper introduces MLHCA as a novel algorithm that combines value and demand queries, with a provable property on information use and experimental validation on synthetic bidder distributions showing efficiency gains. No equations, derivations, or self-citations are presented that reduce the performance claims to fitted inputs or prior self-referential results by construction. The central claims rest on algorithmic design plus independent experimental measurements, which do not loop back to the inputs via any of the enumerated circular patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, the paper relies on standard machine-learning assumptions (e.g., that a model can be trained to predict bidder responses from mixed query types) and on the representativeness of the experimental preference distributions; no explicit free parameters, axioms, or invented entities are named.

pith-pipeline@v0.9.0 · 5759 in / 1091 out tokens · 26553 ms · 2026-05-23T17:53:24.966630+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    ISBN 9781107135345

    Cambridge University Press, October 2017. ISBN 9781107135345. doi: 10.1017/9781316471609.025. Bikhchandani, S. and Ostroy, J. M. The package assignment model. Journal of Economic theory , 107(2):377–406, 2002. Blum, A., Jackson, J., Sandholm, T., and Zinkevich, M. Preference elicitation and query learning. Journal of Machine Learning Research, 5:649–667, ...

    work page doi:10.1017/9781316471609.025 2017

  2. [2]

    URL https: //doi.org/10.1287/mnsc.2014.2076

    doi: 10.1287/mnsc.2014.2076. URL https: //doi.org/10.1287/mnsc.2014.2076. Golowich, N., Narasimhan, H., and Parkes, D. C. Deep learning for multi-facility location mechanism design. In Proceedings of the Twenty-seventh International Joint Conference on Artificial Intelligence and the Twenty-third European Conference on Artificial Intelligence, pp. 261– 26...

    work page doi:10.1287/mnsc.2014.2076 2014

  3. [3]

    php/AAAI/article/view/5606

    URL https://ojs.aaai.org/index. php/AAAI/article/view/5606. Weissteiner, J., Heiss, J., Siems, J., and Seuken, S. Monotone-value neural networks: Exploiting prefer- ence monotonicity in combinatorial assignment. In Proceedings of the Thirty-First International Joint Con- ference on Artificial Intelligence, IJCAI-22 , pp. 541–

    work page

  4. [4]

    doi: 10.24963/ijcai.2022/

    International Joint Conferences on Artificial Intelli- gence Organization, 7 2022a. doi: 10.24963/ijcai.2022/

    work page doi:10.24963/ijcai.2022/ 2022

  5. [5]

    URL https://doi.org/10.24963/ijcai. 2022/77. Main Track. Weissteiner, J., Wendler, C., Seuken, S., Lubin, B., and P¨uschel, M. Fourier analysis-based iterative combina- torial auctions. In Proceedings of the Thirty-First In- ternational Joint Conference on Artificial Intelligence, IJCAI-22, pp. 549–556. International Joint Conferences on Artificial Intell...

    work page doi:10.24963/ijcai 2022

  6. [6]

    URL http://papers.nips.cc/paper/ 9046-gradient-dynamics-of-shallow-univariate-relu-networks. pdf. 12 Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All A. Extended Preliminaries and Literature Review A.1. Extended Literature Review In addition to the related work mentioned in Section 1, we also want to mention some further recent ...

    work page 2023

  7. [7]

    for each bidder i, the bundle ai(p) maximizes her utility, i.e., vi(ai(p)) − ⟨p, ai(p)⟩ = U(p, vi), ∀i ∈ N, and

    work page

  8. [8]

    (2024c))

    the allocation a(p) ∈ F maximizes the sellers revenue, i.e.,P i∈N ⟨p, ai(p)⟩ = R(p).6 Theorem A.3 extends Bikhchandani & Ostroy (2002, Theorem 3.1), establishing a connection between the aforementioned definitions: Theorem A.3 (Soumalias et al. (2024c)). Consider the notation from Definitions A.1 and A.2 and the objective function W (p, v) := R(p) +P i∈N ...

    work page 2002

  9. [9]

    The outcome is individual rational, i.e, ui = vi(ai) − πi ≥ 0 for all i ∈ N

    work page

  10. [10]

    bid-sniping

    The core constraints ∀ L ⊆ N X i∈N \L πi(R) ≥ max a′∈F X i∈L vi(a′ i) − X i∈L vi(ai) (11) where vi(ai) is bidder i’s value for bundleai and F is the set of feasible allocations. In words, a payment vector π (together with a feasible allocation a) is in the core if no coalition of bidders L ⊂ N is willing to pay more for the items than the mechanism is cha...

    work page 2017

  11. [11]

    Clock phase activity rules, which limit the bundles that an agent can bid on during the clock phase, based on their bids in previous clock rounds

    work page

  12. [12]

    Supplementary round activity rules, which restrict the amounts that an agent can bid on specific sets of items during the supplementary round. 8The notion of ”bid-sniping” originated in eBay auctions with predetermined ending times, where high-value bidders could reduce their payments by submitting bids at the very last moment. 16 Prices, Bids, Values: On...

    work page 2014

  13. [13]

    Final Cap: A bid for bundle x ∈ X should satisfy the revealed-preference constraint (Definition B.5)with respect to the final clock round’s pricepQCCA ∈ R≥0 and bundle xQCCA ∈ X

    work page

  14. [14]

    Relative Cap: A bid for bundle x ∈ X should satisfy the revealed-preference constraint (Definition B.5)with respect to the last clock round for which the bidder was eligible for that bundle x ∈ X , based on the points-based system

    work page

  15. [15]

    weight decay

    Intermediate Cap: A bid for bundle x ∈ X should satisfy the revealed-preference constraint (Definition B.5) with respect to all eligibility-reducing rounds, starting from the last clock round for which the bidder was eligible for x ∈ X based on the point system. Ausubel & Baranov (2017) showed that combining the Final Cap and Relative Cap activity rules l...

    work page 2017

  16. [16]

    First we show that Mθ∗(10) ≤ 10˜p via a contraposition argument. Let’s assume Mθ∗(10) ≥ 10q > 10˜p, then multiplying the last layer’s weights by1 − δ > q ˜p would both reduce the data-loss-term L0 (since the activation the hidden layers of MVNNs are always non-negative) and the regularization costs λ ∥·∥2

    work page

  17. [17]

    Thus, we have shown that Mθ∗(10) ≤ 10˜p holds for any local minima θ∗

    Therefore, no local minima θ∗ can satisfy Mθ∗(10) > 10˜p. Thus, we have shown that Mθ∗(10) ≤ 10˜p holds for any local minima θ∗

    work page

  18. [18]

    Let’s assume again the contraposition that at least one pre-activation is larger than the cut-off

    Next, we show that all pre-activations of our Mθ∗ are smaller or equal to the cut-off of the corresponding bReLU activation function for any input x ∈ X . Let’s assume again the contraposition that at least one pre-activation is larger than the cut-off. In this case, we can scale down all the incoming weights of such a neuron without changing Mθ∗(10). Sca...

    work page

  19. [19]

    First, note that by Item 2, we know that Mθ∗ is convex (since the bReLU is convex below the cut-off)

    Next, we show that all biases of θ∗ are zero. First, note that by Item 2, we know that Mθ∗ is convex (since the bReLU is convex below the cut-off). By combining this fact with Item 1, we obtain that Mθ∗(x) ≤ x˜p, since MVNNs always satisfy Mθ(0) = 0. Let’s assume the counterposition of at least one bias being strictly negative (as by definition biases can...

    work page 2023

  20. [20]

    price discovery phase

    Here, the unique efficient allocation would assign 1 item to bidder 1 and the remaining 9 items to bidder 2, resulting in an SCW of v1(1) + v2(9) = 100 + 9· 9 + 92 25 = 184.24. However, there is no DQ p ∈ Rm ≥0 that bidder 2 would answer with x∗ 2(p) = (9): • If the price p is below 94 10, bidder 2 will answer with x∗ 2(p) = (10); • if the price p = 94 10...

    work page 2020

  21. [21]

    The first training set contains 40 DQs simulating 40 CCA clock rounds, along with 20 VQs for bundles chosen uniformly at random

    work page

  22. [22]

    The second training set consists of 60 DQs, simulating 60 CCA clock rounds, with no VQs

    work page

  23. [23]

    The third training set contains 60 VQs and no DQs. We evaluate the generalization performance of the trained models on two distinct sets: A random bundle set (Vr), which consists of 50,000 bundles sampled uniformly at random from the bundle space. A random price-driven set (Vp), which consists of the bundles requested by the bidder in 200 randomly generat...

    work page 2023