Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
Authors: Ermis Soumalias
Jakob Heiss
Jakob Weissteiner
Sven Seuken
Venue: ICML 2025 oral (2025)
Keywords: Combinatorial Auctions
Auction Design
Auctions
Market Design
Mechanism Design
Game Theory
Spectrum Auctions
Iterative Auctions
Preference Elicitation
Machine Learning
Neural Networks
Deep Learning
Bayesian Optimization
Active Learning
Computational Economics
Demand Queries
Value Queries
Primary area: theory->game_theory
TL;DR: Our ML-algorithm dramatically outperforms the SOTA for combinatorial auctions by combining demand queries and value queries.

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 *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.

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
Ermis Soumalias * 12 Jakob Heiss 234
Jakob Weissteiner 125 Sven Seuken
Abstract
pression of value. CAs have enjoyed widespread adoption in practice, with their applications ranging from allocating spectrum licenses (Cramton, 2013) to TV ad slots (Goetzen- dorff et al., 2015) and airport landing/take-on slots (Rassenti et al., 1982).
We study the design of iterative combinatorial auctions (ICAs). The main challenge in this do- main 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 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 re- sults in significantly better learning performance in practice. Building on these insights, we present MLHCA, a new MI-poowred auction that uses value and demand queries. MLHCA significantly outperforms the previous SOTA, reducing effi- ciency loss by up to factor 10, with up to 58% fewer queries. Thus, MLHCA achieves large ef- ficiency improvements while also reducing bid- ders' cognitive load, establishing a new bench- mark for both practicability and efficiency, Our code is available at https:// com/ ma rketdees
The key challenge in CAs is that the bundle space grows ex- ponentially in the number of items, making it impossible for bidders to report their full value function in all but the small- est domains. Morcover, Nisan Segal (2006) showed that, for arbitrary value functions, CAs require an exponential number of bids to guarantee full efficiency. Thus, practi- cal CA mechanisms cannot provide efficiency guarantees in real world settings with more than a modest number of items. Instead, the focus has shifted towards iterative com- binatorial auctions (ICAs), where bidders interact with the auctioneer over a series of rounds, providing only a limited (i.e., practically feasible) amount of information, with the aim to maximize the efficiency of the final allocation.
The most established ICA following this interaction paradigm is the combinatorial clock auction (CCA) (Ausubel et al., 2006). Extensively used for allocating spec- trum licenses, the CCA generated over USD 20 billion in revenue between 2012 and 2014 alone (Ausubel & Baranov, 2017). However, a key challenge for any ICA, including the CCA, is balancing speed of convergence with efficiency. Each bidding round involves significant computational costs and complex business modeling for participants (Kwasnica et al., 2005; Milgrom & Segal, 2017; Bichler et al., 2017), making faster convergence highly desirable.
1. Introduction
Large spectrum auctions conducted under the CCA format can require over 100 bidding rounds, prompting practition- ers adopt aggressive price update rules reduce the num- ber of rounds. For example, prices may be increased by up to 10% per round, but such approaches come at the expense of efficiency (Ausubel & Baranov, 2017). This trade-off highlights the ongoing challenge of designing ICAS that achieve both high efficiency and rapid convergence. Given the value of resources allocated in these auctions, even a one mnee-eecentage-peee point improvement in efficiency translates to welfare gains of hundreds of millions of dollars.
Combinatorial auctions (CAs) are used to allocate multiple items among several bidders who may view those items as complements or substitutes. CAs allow bidders to place bids on entire bundles of items, enabling more nuanced ex-
"Equal contribution 'Department of Informatics, University of Zurich, Zurich, Switzerland 'ETH AI Center, Zurich, Switzerland ' "Department of Mathematics, ETH Zurich, Zurich, Switzerland "Department of Statistics. University of California, Berkeley, USA *UBS, Zurich, Switzerland. Correspondence to: Ermis Soumalias <ermis uz..uz Jakob Heiss jjakob.hhiisse berkeley.edu>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Prices, Bids, Values: One ML-Poweredd Combinatorial Auction to Rule Them All
1.1. ML-Powered Iterative Combinatorial Auctions
unprecedented efficiency gains while significantly reducing bidders' cognitive load, establishing new benchmark for both practicability and efficiency.
To tackle this challenge, researchers have explored using machine learning (ML) to enhance the efficiency of ICAs. The foundational works of Blum et al. (2004) and Lahaie & Parkes (2004) were the first to frame preference elicita- tion in CAs as a learning problem. More recently, Brero et al. (2018; 2021) and Weissteiner & Seuken (2020); Weis- steiner et al. (2022b;a; 2023) introduced ML-powered ICAs. Central to these approaches is an ML-based preference elic- itation algorithm that trains an ML. model each bidder's value function to generate informative value queries (VQs) (e.g., "What is your value for the bundle {A, B))"",, which iteratively refine the ML model of each bidder's ' values.'
1.2. Our Contributions
We introduce the Machine Learning-powered Hybrid Com- binatorial Auction (MLHCA), practical ICA that achieves unprecedented efficiency and convergence speed. First, we establish a theoretical foundation and provide illustrative examples to demonstrate the advantages and limitations of DQs and VQs from an auction design perspective (Sec- tion 3). Then we develop learning algorithm that effec- tively leverages both query types (Section 4). We provide strong experimental evidence of the learning benefits of combining both query types, as well as the advantages of starting an auction with DQs instead of VQs.
Soumalias et al. (2024c) took a different approach. To increase the likelihood of their approach being adopted in practice, they introduced ML-CCA, an ML-powered auction that follows the established interaction paradigm of the CCA using demand queries. Building earlier works by Brero & Lahaie (2018); Brero et al. (2019), their design iteratively trains individual ML models for each bidder using their previously answered demand queries (DQs) and then selects the next DQ with the highest clearing potential.
We then integrate these auction and ML insights to design MLHCA, the first ICA to incorporate sophisticated DQ and VQ generation algorithms (Section 5). Simulations in real- istic domains (Section 6) show that MLHCA significantly outperforms the previous SOTA, achieving unprecedented efficiency while also using fewer queries, thus setting a new benchmark for both efficiency and practicality.
Although ML-CCA marked a major step towards a practical ML-powered ICA and outperformed the baseline CCA used in real-world applications, it still faced two key shortcom- ings. First, it fell short of achieving the SOTA efficiency of the VQ-based ML-powered ICAs. Second, like the CCA, it relied on a very large number of supplementary round bids to enhance its efficiency, requiring bidders to decide on additional value bids-a cognitively demanding task.
1.3. F Further Related work
In the field of automated mechanism design. Dütting et al. (2015; 2019), Golowich et al. (2018) and Narasimhan et al. (2016) used ML to learn new mechanisms from data, while Cole & Roughgarden (2014); Morgenstern & Roughgar- den (2015) and Balcan al. (2023) bounded the sample complexity of learning approximately optimal mechanisms. In contrast to this line of prior work, in design, the MI. algorithm is part of the mechanism itself. Lahaie & Lubin (2019) suggest an adaptive price update rule that in- creases price expressivity as the rounds progress in order to improve efficiency and speed of convergence. Unlike that work, we aim to improve efficiency without increasing price expressivity, as that not a popular interaction paradigm in practice, and can cause added cognitive load on the bidders. Preference elicitation is also a key challenge in combina- torial allocation without money. Soumalias et al. (2024b) introduce an ML-powered mechanism for course allocation that improves preference elicitation by asking comparison queries. See Appendix A. for further related work.
We address these shortcomings by introducing the Ma- chine Learning-poweree Hybrid Combinatorial Auction (MLHCA). Leveraging sophisticated DQ and VQ generation algorithms, MLHCA maintains the established interaction paradigm of the CCA while achieving unprecedented ef- ficiency gains. MLHCA outperforms the previous SOTA across all tested domains, reducing efficiency loss by up to factor of ten. Based on the value of goods traded (Ausubel & Baranov, 2017), these efficiency improvements correspond to welfare gains of hundreds of millions of USD. At the same time, MLHCA significantly reduces the cognitive load on bidders: compared to BOCA, the previous SOTA, ML- HCA requires at least 42% fewer queries to achieve the same efficiency, and compared to ML-CCA, the SOTA auction following CCA's interaction paradigm, MLHCA requires at least 26% fewer queries. Moreover, unlike the CCA and ML-CCA, in MLHCA bidders do not need to decide which bundles to bid for in its VQ rounds, as the auction auto- matically suggests these bundles. Thus, MLHCA achieves
1.4. Practical Considerations and Incentives
MLHCA can be seen as a sophisticated modification of the CCA. In practice, many other considerations (beyond pref- erence elicitation complexity and efficiency) are important. For example, Ausubel & Baranov (2017) discussed the vital role of well-designed activity rules to induce truthful bid-
From an optimization perspective, this can be viewed as combinatorial Bayesian optimization problem.
2

---

Prices, Bids, Values: One ML-PPowered Combinatorial Auction to Rule Them All
ding in the clock phase of the CCA. In Appendix B.3, we provide a detailed discussion of the most common activity rules used in the CCA, and we detail how MLHCA can also leverage these rules for the same goal. Additionally, in Appendix B.4, we prove that MI.HCA can immediately detect if bidder's reports are inconsistent.
the auctioneer presents vector of item prices p Rg and each bidder i responds with her utllity-mxximiiigg bundle,
x (p) E arg max (2)(2) - (p. x)} e N, =EX
(I)
where (+-) denotes the Euclidean scalar product in R". Definition 2.2 (Value Query). In value query, the auction- eer presents to bidder a bundle of items I and bidder i responds with her value at those prices, i.., Us (x) E Rg0-
The payment rule used in the supplementary round of the CCA is also important for incentives. Cramton (2013) ar- gued that the use of the VCG-nearest payment rule, while not strategyproof, induces good incentives in practice. Simi- lar to the supplementary round of the CCA, the VQ-based phase of MLHCA is not strategyproof. However, in Ap- pendix B.5, we argue that the VQ-based phase of MLHCA offers strong incentives in practice, and we show that, under two additional assumptions, truthful bidding an ex-post Nash equilibrium (following the arguments from Brero et al. (2021) for the MI.CA..
For bidder E N, we denote her K E N elicited DQs as R {(x) (p"), p"))"")pp))) ) and her L e N elicited VQs as R {2 (x I== Bidder i's reports are denoted as RG = (R ),, We collect the elicited reports of all bidders in the tuple R (R1....,R..)
In auctions using DQs, a key concept is the bidder's inferred value. This represents the maximum lower bound on bidder's value for bundle that the auctioneer can deduce from the bidder's reports, without assuming monotonicity. The inferred value is always weakly lower than the bidder's 's true value, with equality achieved if the bidder has answered the corresponding VQ for that bundle. Formally: Definition 2.3 (Inferred Value). Bidder i's inferred value for bundle x E X' given her reports R, is
2. Preliminaries
2.1. Formal Model for ICAS
We consider multiset CA domains with a set N (I.....n) n) of bidders and a set M = (1....,m) m) of dis- tinct items with corresponding capacities, i.e., number of available copies, c (C1. ................................ Cm) E N We denote bundle
by x. E X = (0..... } x x (0....,cm Gm of items represented as a positive integer vector, where Iy = k iff item j E M is contained k-times in x. The bidders' true preferences over bundles are represented by their (private) value functions v, : X - Rzo, E N, i.e., (xx) represents bidder i's value for bundle E X. We assume that u; is nondecreasing and satisfies (0) 0. We collect the value functions v; in the vector = (v, KEN) By = (d1....,a.) a,,) E X' we denote an allocation of bundles to bidders, where ag is the bundle bidder obtains. We denote the set of feasible allocations by F = fa E X". EiEN aij S Cj. Vj E M). We assume that bidders have quasilinear utility functions of the form us (a.)) = va())) - π, where v; can be highly non-linear and T, E 22 denotes the bidder's payment. This implies that the (true) social welfare V(a) of an allocation a is equal to the sum of all bidders' values ΣiEN 2a.)). We let a" E arg max,er (a) denote a selial- maximiz- ing, i.e., efficient, allocation. The efficiency of any allocation a E F determined as (aa)
(1; R,) = 1s(2), if (x), E R max (((2,)") : (z,p") E R [(0) else.
The ICA'S final allocation RR) E F and payments T. := n. (R) E RRo are computed based only on the elicited reports R. Concretely, a" (R) E F is determined by solving the Winner Determination Problem (WDP):
a" (RR) aarg max REF
Σ (ag Rs),
(3)
where EIEN T,(a,; Rs) is the allocation's 's inferred social welfare, a lower bound on its social welfare ΣiEN v:(a:).
2.2. Benchmark ICAS
In this section, we briefly introduce the three main bench- mark mechanisms considered in this paper.
CCA The most established ICA is the Combinatorial Clock Auction (CCA) (Ausubel et al., 2006). The CCA consists of two phases. The initial clock phase proceeds in rounds. In each round r, the auctioneer sets anonymous (i.e., same prices for all bidders) item prices p" E IRm prompting each bidder to respond to a DQ, declaring her utility- maximizing bundle at p". In the next round, the prices of over-demanded items are increased by a fixed per- centage, until over-demand is eliminated. The second phase
An ICA mechanism defines how the bidders interact with the auctioneer and how the allocation and payments are determined. We consider ICAs that iteratively ask bidders both demand queries (DQs) and value queries (VQs).
Definition 2.1 (Demand Query). In a (linear) demand query.
Note that V(a) = ΣIEN u:(a:) + "lacciooner (a) =
EIEN (a.(a.) - T.) + EIEN म. = -EEN va:)).
3

---

Prices, Bids, Values: One ML--Powered Combinatorial Auction to Rule Them All
of the CCA, known as the supplementary round, allows bidders to report their values for additional bundles of their choice. The clock bids raised heuristic suggests that bidders report their values for all bundles they requested during the clock phase. The final allocation is determined by solving the WDP based on all reports as in Equation (3).
VQ-Based Approaches Rely on Cognitively Complex Random VQs. At the start of an ICA, no specifie infor- mation about bidders' preferences is available, making it challenging to identify bundles relevant to them. Thus, most VQ-based auctions, including the SOTA approach (Weissteiner et al., 2023), begin by querying bidders about randomly selected bundles. However, in practice, answer- ing VQs for such random bundles that do not align with the bidders' interests is cognitively demanding. In contrast, the most widely used ICAs in practice (e.g., the CCA) em- play DQs, which are easier for bidders to answer effectively (Cramton, 2013). This key advantage highlights why rely- ing exclusively on VQs is often impractical in real-world auctions.
ML-CCA The most efficient DQ-based ICA is the Ma- chine Learning-powered Combinatorial Clock Auction (MI.- CCA) (Soumalias et al., 2024c). ML-CCA has the same interaction paradigm as the CCA, but with a substantially more refined DQ --ggerrattinn algorithm in its clock phase. In each round, an ML model is trained to estimate each bidder's value function based on previously submitted DQ responses. Then, the prices are not increased by a percentage like in the CCA, but instead convex optimization problem determines the prices with the highest clearing potential.
DQs Offer Superior Efficiency Gains in Initial Rounds. Even if bidders could easily answer random VQs. in Ap- pendix D.I we detail the significant advantages of DQs in the initial rounds of an ML-ICA, where DQs are providing more actionable and efficient information. This superior efficiency is formalized in the following proposition:
BOCA The SOTA ICA in terms of efficiency is the VQ- based Bayesian optimizatioon-ussed combinatorial auction (BOCA) (Weissteiner et al., 2023). The main idea of BOCA that in each round, the auctioneer creates an estimate of the upper confidence bound of the value function of each agent based on her past responses. Then, the auctioneer solves an ML-based WDP to find the feasible allocation with the highest upper bound on its estimated social welfare, and queries each agent her value for her bundle in that allocation. This allows the mechanism to balance between exploring and exploiting the bundle space.
Proposition 3.1. The expected social welfare of an auction that uses a single random demand query can be arbitrarily larger than that of an auction that uses any constant number (k < 2n) of random value queries.
Additionally, DQs can establish a proof of optimality, allow- ing the auction to terminate early (Proposition D.3). These theoretical insights are validated by our experimental results in Section 6. An auction initialized with DQs has up to 20% points higher efficiency after its initial queries compared to an auction initialized with VQs.
2.3. ML Framework
The ML. models used by ML-CCA, and as basis for the con- struction of the confidence bound estimates in BOCA are monotone-value neural networks (MVNNs) M X + R (Weissteiner et al., 2022a). MVNNs are class of NNs specifically designed to represent monotone combinatorial valuations. MVNNs have also had success in combinatorial allocation domains without money, e.g., for course alloca- tion (Soumalias et al., 2024b). Soumalias et al. (2024c) introduced multisel MVNNs (mMVNNs), an extension of MVNNs that also incorporates at a structural level the infor- mation that some items in the auction are identical copies of each other. In this work, we instantiate our ML models us- ing mMVNNs, and denote agent i's model as M¹ XX' -> IR. Within this work, we will refer to all mMVNNs simply as MVNNs. We provide more details in Appendix C.
VQs Offer Superior Efficiency Gains in Later Rounds. This raises the question: is it sufficient to rely exclusively DOs? Theorem 3.2 proves that the answer is negative:
Theorem 3.2. For every e > O, there exist infinitely many instances of auctions for which no combination of DQs can achieve an efficiency above 50% + This remains true even for infinite combinations of DQs and even if the bidders auditionally report their true values for all bundles they requested in those DQs.
Notably, Theorem 3.2 shows that this limitation persists even when supplementing the auction with the clock-bids raised heuristic. Without this heuristic. adding more DQs can even decrease efficiency. In Proposition 3.3 we prove that a single DQ can reduce the auction's 's efficiency arbitrar- ily close to 100%, whereas VQ-based auctions do not face this issue.
3. A Theoretical Framework for Effectively Combining DQs and VQs
This section develops a theoretical framework for effec- tively combining DQs and VQs. Proofs are deferred to Appendix D.
Proposition 3.3. In a DQ-based ICA, adding DQs can actually reduce efficiency. A single DQ can cause an effi- ciency drop arbitrarily close to 100%. By comparison, in a

---

bundles in Tp. where mixed training Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
VQ-based ICA, adding additional queries can never reduce efficiency (assuming trathful bidding).
OPTIMIZATION TRAIN POINTS
R²
KT
MAE SCALED
R
METRIC
VQs
DQ5
T.
T,
T
T
T.
T. T
It' ON V.
20
40
0.84
0.42
0.79
0.80
0.037
0.044
0.84 0.80
These issues are also very prevalent in the real world. In Section 6, we demonstrate that in realistic domains, the gap in average efficiency between the SOTA DQ-based and VQ-based auctions can reach up to 8% points. Further- more, the average efficiency of the CCA, the prominent DQ-based auction, declines by 8% points during the auc- tion. VQ-based auctions avoid these pitfalls entirely. First, they can always achieve 100% efficiency after sufficiently many VQs (Lemma D.14). Second, asking additional VQs never reduces the efficiency of a VQ-based auction. In Appendix D.2, we provide further theoretical and intuitive arguments on why relying solely on DQs is insufficient.
60
0.73
10.07
0.68
0.64
0.052
0.236
0.74 0.20
0
60
0.24
-3.07
0.77
0.77
0.103
0.128
0.83
0.76
Ae ON V/2
20
40
0.82
0.01
0.79
0.80
0.011
0.062
0.81 0.83
60
0.76
-3.40
0.72
0.62 0.049
0.141
0.77 0.05
60 -0.05
-6:24
0.78
0.72 0:103
0.154
0.84 0.68
Table 1: Learning comparison of training only on DQs, only on VQs, or on both. Shown are averages over ten instances. Winners marked in gray.
prices by treating her MI. model as her true value function. If the predicted reply deviates from the bidder's true reply, the loss equals the difference in predicted utility between the two bundles. This loss function provably captures all information provided by the DQ responses. Additionally, the model is trained on the VQ responses using a standard regression loss. For details, please refer to Appendix E.
Optimally Combining DQs and VQs. Building on the discussion in this section, it is natural to leverage the strengths of both query types by starting with DQs and then transitioning to VQs. Example 1 in Appendix D.3 il- lustrates why this approach is effective: even after infinitely many DQs could not achieve more than 55% efficiency, a single VQ can achieve 100% efficiency. However, caution is required, as introducing even a single VQ can reduce the auction's is efficiency by nearly 100% (Lemma D.7). To address this, we introduce the bridge bid, a specialized VQ designed to seamlessly connect the DQ and VQ phases of a hybrid auction. The bridge bid asks each bidder her value for the bundle she would have received according the WDP (Equation (3)) after the final DQ round. Incorporating the bridge bid guarantees that the auction's final efficiency will be no less than its DQlonly efficiency (Lemma D.9). We demonstrate the significance of this bid in practice in Section 6.3 and Appendix G.8. Appendix D.3 provides further insights into combining DQs with VQs.
4.2. Experimental Analysis
We demonstrate the learning benefits of initializing auctions with DQs rather than VQs and highlight how combining both query types leads to superior learning performance.
We conduct the following experiment: We perform hyper- parameter optimization (HPO) to train MVNN for the most critical bidder in the most realistic simulation domain (see Appendix G.1 for details on the simulation and Ap- pendix E.3 for results for other domains). For this bidder, we generate three training sets: (1) 40 DQs simulating 40 CCA clock rounds and 20 random VQs, (2) 60 DQs sim- ulating 60 clock rounds with no VQs, and (3) 60 random VQs with DQs. The models are evaluated on two valida- tion sets: random bundle set (V,) with 50,000 uniformly sampled bundles, and a price-driven set (Vp) containing bundles requested under 200 random price vectors. V, tests generalization across all bundles, while V, focuses on utility- maximizing bundles. We select the configuration with the best coefficient of determination (R²). averaged over 10 bidder instances.
4. Mixed Query Learning
Combining DQs and VQs not only improves the final effi- ciency of auctions but also enables the global learning of bidders' value functions. In this section, we introduce a mixed training algorithm that leverages both query types. Specifically, we demonstrate the learning benefits of initial- izing auctions with DQs over VQs and show how integrat- ing both query types leads to superior learning performance. Further details are presented in Appendix E.
The selected configurations are then tested on 10 new bid- ders, generating hold-out tests sets T, and Tp in the same way as V, and V,. We report R², Kendall Tau (KT), scaled Mean Absolute Error (scaled MAE), and R² An R² value of indicates perfect learning up to a constant shift, with differences between R² and R² reflecting shift magnitude. HPO procedures were consistent across all training sets, with identical test instances, seeds, search spaces, and com- putation time. Additional details are in Appendix G.3.
4.1. Mixed Training Algorithm
To leverage the advantages of both DQs and VQs, pro- pose two-stage training algorithm compatible with modern NN architectures, including mMVNNs. In each epoch, the ML model is first trained on all DQ responses using the loss function of Soumalias et al. (2024c). The key idea is to predict the bidder's s maximizig bundle at the given
Table shows that training on a mix of DQs and VQs consis- tently outperforms training on either query type, particularly for
5

---

Prices, Bids, Values: One ML-PPowered Combinatorial Auction to Rule Them All
achieves nearly three times lower MAE. The mixed model also closely matches the mean value for both test sets, as indicated by the small gap between R2 and Rta In contrast, DQ-only models lack absolute value information, leading to relative but not unique value function learning, as evidenced by the large difference between Rt² and R2 This limitation goes even beyond constant shifts: Example I shows that even with all possible DQs, unique identification up to a constant shift is impossible. Meanwhile, VQ-only models suffer from distributional shifts between test sets, reflected in the significant discrepancy in R² and MAE across the two test sets. These shifts prevent VQ-trained models from capturing critical, high-value bundles due to the absence of mtliity-axiiizingg bundles in their training data.²
Algorithm 1: MLHCA(Q QT0 Q" T)
Parameters: : CCCA 200, Q90 and x
R R +- (()) (0)
for 1, ...,, QCCA do
DDraww QCCA initial prices
3
v" + C
foreach i E N do
Dnitial DQs
5
11,00 <- I2
U (F=,,)")))))
for r = QCCa + +,,.., QC + d0 do D. -powerrd nos
7
foreach i E N do
8
MR t MIXEDTRAINING( R
b'lgorithm
p" + (MM))
Appendix A.3
10
foreach i E do
R c R2 u ((x
11
12
if Σ (of (1 )), = c Vjj E M then
DQ-trained models generalize better to Tp than VQ-trained models, as Tp emphasizes high-value bundles critical for efficient allocations. This motivates initially training with DQs, as they provide global information about the alloca- tion space and focus on high-value regions from the outset. These learning advantages are so pronounced that, as shown in Section 6, MLHCA only needs to follow up its 40 DQs with most 18 VQs outperform the previous SOTA, which requires 100 VQs.
Ma slearing prices found
a (noo R29) t (x (}= TR R2 + (T:(RP 1
13
14
return a" (RR0 R²9) and a (Ro0, R
16
foreach i E N do
busidge bid
17
R,
R u (1 RTO), (1 R R)))
for Q Que 2, ..., Q + =Q00 + Q do
18
XL powered vQa
19
foreach i do
MM <- MIXEDTRAINING(R))) R2
5. The Mechanism
20
P Algozittm
In this section, we describe our ML-powered Hybrid Com- binatorial Auction (MLHCA), which combines the auction and ML insights from Sections 3 and 4.
NEXTALLOCATION ((MP), R R
21
D Appendix F foreach i do
22
23
R 6 RN U ((a, ((a)))) Value quezy
We present a simplified version of MLHCA in Algorithm In Lines 2 to 5, we generate the first Q E N DQs using the price update rule of the CCA. Similar to ML-CCA, we use larger price increments to arrive to similar prices as the ML-CCA in fewer rounds. In each of the next Q E IN ML- powered rounds, we first train, for each bidder, an mMVNN on her demand responses (Line 8), and call NEXTPRICE (Soumalias et al., 2024c) (see Appendix A.3) to generate the next DQ based on the agents' trained mMVNNs (Line 9). If MLHCA has found market-clearing prices, then the corre- sponding allocation is efficient and is returned, along with payments π (R) according to the deployed payment rule (Line 15). MLHCA is plug-and-play compatible with many payment rules, such as VCG and nCG-nea.est. If, by the end of the ML-powered DQs, the market has not cleared switch to VQ rounds. In the first VQ round (Line 17) we ask each bidder for her bridge bid (see Definition D.8). This single VQ bid ensures that the MLHCA's efficiency is lower bounded by the efficiency after just the DQ rounds (Lemma D.9). For a detailed experimental evaluation of the bridge bid see Appendix G.8. In the final Q - 1 vQ rounds, for each bidder, we query her value for the bundle
responses
24
Calculate final allocation a" (R"O,, R as in Equation (3)
25 Calculate payments T (RRO, R²9) (Appendix 5)
D..g., VCS
26 return a" "100, and n T1100 HR
she is allocated in the predicted optimal allocation (based on all ML models), under the constraint that she has not answered a VQ for that bundle in the past (Lines 21 to 23).4 The final allocation and payments are then determined based all reports (Lines 24 to 25). For details, please see Appendix F.
6. Experiments
In this section, we experimentally evaluate MLHCA. We compare its efficiency against BOCA (Weissteiner al., 2023) and MI-CCA (Soumalias et al., 2024b) the SOTA VQ-based and DQ-based ICAs, respectively.
At the start of a VQ-based auction, models are not accurate enough to target value- maximiziai bundles.
"This VQ algorithm was introduced in Brero al. (2021) and used in most follow-up work following the MI.CA framework.
6

---

Prices, Bids, Values: One ML--Powered Combinatorial Auction to Rule Them All
6.1. Experiment Setup
MRVM further highlights MLHCA's superiority. Here, ML- HCA exceeds the efficiency of all other mechanisms by over 2% points, making MLHCA the first mechanism to substantially outperform CCA. MRVM simulates the 2014 Canadian spectrum auction (Weiss et al., 2017) with a rev- enue of USD 5.27 billion (Ausubel & Baranov, 2017), where 2% points correspond to over USD 100 million.
To generate synthetic CA instances, we use the spectrum auction test suite (SATS) (Weiss et al., 2017). which includes various value models (domains) designed to simulate differ- ent auction environments. Following standard practice in this line of research (e.g., Soumalias et al. (2024c); Weis- steiner et al. (2023)). we conduct experiments on the GSVM, LSVM, SRVM, and MRVM domains (see Appendix G.1 for details). SATS provides access to the true optimal al- location at E F, allowing us to measure the efficiency loss, defined as 1 - V(a" (R))/V(a*) where R represents elicited reports. We focus on efficiency rather than revenue, as do all mechanisms we compare against. This is consistent with the primary application of ICAS in spectrum allocation, a government-run operation with a maliiaaammaimmzaiiinn mandate (Cramton, 2013). For results on revenue, see Ap- pendix G.7. To ensure fair comparison with prior work, we limit all auction mechanisms 100 total queries. These consist of 100 VQs for BOCA, 100 DQs for ML-CCA, and 40 DQs and 60 VQs for MLHCA. For BOCA and ML-CCA, we use the best mechanism configurations and hyperparam- eters reported in their respective papers. For MLHCA's VQ rounds, we performed HPO separately for each bidder type in each domain, as detailed in Appendix E.2. For the DQ rounds, we adopted the HPO parameters reported by Soumalias et al. (2024c), since our learning algorithm, when restricted to DQs, is equivalent to theirs. For further experi- mental details and analysis of MLHCA's low computational costs, please refer to Appendices G.3 and G.4 respectively.
Speed of convergence is another critical factor in these auc- tions. In all domains, MLHCA requires at most 74 queries (40 DQs and 34 VQs) to statistically outperform the final ef- ficiency of both BOCA and ML-CCA, which use 100 VQs and 100 DQs, respectively. Furthermore, in three out of four domains, MLHCA surpasses the 100 DQ efficiency of MI-CCCA with only 40 DQs and VQs. These results align with our theoretical analysis in Appendix D.3, where we show that, once DQs have sufficiently informed the bidders' value functions, a single VQ can lead to 100% efficiency.
Figure I illustrates the efficiency loss path for all domains, highlighting MLHCA's consistent superiority. Up to query 40, MLHCA and ML-CCA perform identically since both mechanisms employ the same DQs and network configu- rations during these rounds. However, after query 40, ML- HCA's integration of VQs leads to marked reduction in efficiency loss compared to ML-CCA, aligning with our insights on the efficiency of VQs and on the learning advan- tages of combining DQs and VQs (Sections 3 and 4). Across all domains, MLHCA also consistently outperforms BOCA, leveraging the early-stage advantages of DQs when ML models are still being quite uninformed and the later-stage learning advantages of combining DQs and VQs.
6.2. Efficiency Results
In summary, MLHCA outperforms both DQ-based and VQ- based SOTA mechanisms in terms of both efficiency and speed of convergence, achieving high efficiency with fewer queries. This makes MLHCA a powerful and practical choice for real-world auction scenarios where high effi- ciency and rapid convergence are crucial. These empirical findings not only highlight the efficiency and convergence speed of MLHCA but also closely align with our theoret- ical insights. In the next section, we analyze how these results validate the predictions and theoretical guarantees established in this paper.
In Table 2, we show the average efficiency loss of each mechanism after 100 queries. For ML-CCA, we also report results if it were supplemented with the clock bids raised heuristic (see Section 2.2), which would involve up to an additional 100 VQs per bidder. Finally, we report the num- ber of queries that MLHCA requires to outperform the final efficiency of each other mechanism, i.e., in GSVM, with 42 queries (40 DQs and 2 VQs) MLHCA statistically outper- forms ML-CCA, even if ML-CCA were supplemented with 100 VQs from the clock bids raised heuristic.
In Table 2, we observe that MLHCA significantly outper- forms all other mechanisms across all domains. Notably, MLHCA is the only mechanism capable of achieving a per- feet 100% efficiency in SRVM. Remarkably, it accomplishes this with fewer than 60 queries, while the other mechanisms fail even with 100 queries. In the LSVM domain, MLHCA achieves 10-fold reduction in efficiency loss compared to BOCA, the previous SOTA. The most realistic domain,
6.3. Alignment with Theoretical Insights
Figure 1 further validates our theoretical findings. The non- monotonicity of DQ-based mechanisms, as suggested in Proposition 3.3, is evident in the efficiency loss path of both the CCA and the ML-CCA. Notably, in the LSVM domain, the CCA achieves higher average efficiency after just 5 DQs compared to 100. Additionally, the comparison between BOCA and ML-CCA underscores the inefficiency of ran- dom VQs in the early stages (Proposition 3. particularly in the MRVM domain, where BOCA's efficiency loss is
'In the clock bids raised heuristic, the bidders only need to report their value for each unique bundle they bid on during the auction, which, for 100 100 DQs, can he up to 100 bundles.
7

---

Prices, Bids, Values: One ML-Powerre Combinatorial Auction to Rule Them All
EFFICIENCY LOss
QUERIES REJECT NULL HYPOTHESIS
DOMAIN
MLHCA
BOCA
ML..CCAcsoc.
MI.-CCAuosi
CCA
BOCA 2 MLHCA ML.CCAAcs0 2 MLHCA MI.-CCA 2 MLHCA
GSVM
0.00 0.00
1.77 1: 0.68
1,07 1 0.37
9.60 1.49
42
42
LSVM
0.04 1: 0.07
0.39
1: 0.31
8,36 1 1.70
3.61 1: 0.77
17.44 :: 1.60
58
42
43
SRYM
0.00 1 0.00
0.06
1 0.02
0.41 0.11
0.07 1 0.02
0.37 1. 0.11
42
42
42
MRVM
1.81 0.57
7.77 = 0.35
6,21
6.68 0.22
7.53 0.48
54
74
79
Table MLHCA (40DQs + 60VQs) BOCA (100VQs), ML-CCA (ML-CCAstea) (100DQs) and ML-CCA with raised
clock bids (ML-CCAuissa) (100DQs and up to 100VQs). Shown are averages and 95% CI. Winners based on t-test with significance level of 5% are marked in grey.
GSVM
LSVM
SRVM
MRVM
10a
10a
10
100
Efficiency Loss (Log Scale)
10-1
10-1
10-1
10
10
10-2
10
10
10-
10
10-1
10-4
10-4
10-1
10
40
60
20
100
60 Number of Elicited Bids
20
100
Number of Elicited Bids
Number of Elicited Bids
Number of Elicited Bids
MLHCA
ML-CCA
CCN
BOCA
Start ML DQ Rounds
---- Start of ML VQ Rounds
Figure I: Efficiency loss paths (i.e., regret plots) of MLHCA compared to BOCA, ML-CCA and CCA. Shown are averages over 50 instances with 95% Cls.
orders of magnitude worse than that of mechanisms em- ploying ML-powered DQs. Finally, MLHCA's performance after query 40 demonstrates the potential efficiency gains of supplementing DQs with VQs. The switch to ML-powered VQs results in dramatic reduction in efficiency loss-by by several orders of magnitude in the GSVM and SRVM do- while the DQ-based ML-CCA, which was identical to MLHCA up to that point, stagnates. This aligns with Theorem 3.2, which proves that once MI. models effectively capture bidder preferences, VQs can dramatically enhance efficiency. In contrast, ML-CCA's reliance on DQs prevents further improvements, even with well-trained models.
ure 2, we plot MLHCA's efficiency in MRVM-the most realistic domain-agaiin the number of bids, comparing performance with and without the bridge bid. Without the bridge bid, MLHCA's efficiency drops by 7.3% points when it transitions to its VQ rounds. Notably, MLHCA requires 20 of our powerful ML-powered VQs just recover the efficiency lost by the introduction of the first VQ. This is consistent with Lemma D.7, where we showed that effi- ciency can arbitrarily decrease when VQ is introduced in DQ-based auction. In contrast, the bridge bid completely mitigates this efficiency drop, as proven in Lemma D.9. In Appendix G.8, we provide a detailed analysis and explaining the bridge bid's efficacy relative to market competition.
Finally, in Appendix G.9, experimentally evaluate the Inverse variant of MI which uses the inverse query or- der: it begins with VQs and then transitions to DQs. Across all tested domains, reversing the query order results in sub- stantial efficiency losses, reaching up to percentage points. In the inverse auction, MI--powered DQs fail to improve upon the efficiency achieved by the preceding VQs. More- over, the early use of VQs alone cannot match the efficiency attained by the later-stage VQs in MLHCA, due sig- nificantly weaker learning performance when the bidders' models have not been trained on both query types. These findings further reinforce our theoretical results on the criti- cal role query ordering in hybrid auctions.
90
Effiliency
70-
MUFICA Efficiency (Bridge Bidi
60-
MUBCA Efficiency (No Bridge Bid)
Start ML VQ Rounds
No Bridge reaches DQ-enly efficiency 60 bids
Bridge matches Bridge Bid ettidency bids
40
40
100
Number
Figure 2: Efficiency of MLHCA with and without the bridge bid (Definition D.8) in the MRVM domain.
To demonstrate the effectiveness of the bridge bid, in Fig-
8

---

Prices, Bids, Values: One ML-Pooeered Combinatorial Auction to Rule Them All
7. Conclusion
have introduced MLHCA, the first ICA to effectively combine both demand and value queries. By employing tailored query generation algorithms, incorporating the full information from both query types, and leveraging the the- oretical insights developed in this work, MLHCA signif- icantly outperforms current SOTA mechanisms across all tested domains and with significantly fewer queries. No- tably, prior to MLHCA, the best-performing mechanism varied by domain, but MLHCA unifies the SOTA, deliver- ing the best performance across all domains.
At first glance, it might seem obvious that combining DQs and VQs improves performance. However, one of the key insights of our work is that the ordering of queries mat- ters. DQs provide broad but imprecise information across the entire space, while VQs offer targeted, precise informa- tion. As a result, DQs are more effective at the beginning of auction, while VQs become advantageous once the auction's 's ML model has already been trained for while. A second insight is that combining both query types requires careful handling. The efficiency of an auction using both DQs and VQs is non-monotone with respect to answered queries, as DQ responses establish lower bounds on bid- ders' valuations for queried bundles. Naively combining the two can lead sharp efficiency drops, particularly in low-competition scenarios. However, by introducing sin- gle, parefully-designee VQ, we can mitigate this effect and guarantee that the auction's 's efficiency does not fall below its DQ-only value.
promising direction for future work incorporating epis- temic uncertainty into MLHCA to enhance efficiency. An- other is developing an algorithm dynamically determine the optimal switch to VQs, reducing cognitive load.

---

Prices, Bids, Values: One ML-Pooeered Combinatorial Auction to Rule Them All
Acknowledgments
ISSN 00028282. URL http: http://wwwwsto.rrrrooo stable e 42920978.
We are grateful to Greg d'Eon, Bin Yu, Josef Teichmann, and Denise Künzli for helpful discussions and their sup- port. This work was supported by the Swiss National Sci- ence Foundation (SNSF) Postdoc.Mobilit fellowship [grant number S000PT_2253555 and ETH Zürich.
Ausubel, L. M.. Cramton, P., and Milgrom, P. The clock- proxy auction: A practical combinatorial auction design. In Cramton, P., Shoham, Y., and Steinberg, R. (eds.), Combinatorial Auctions, pp. 115-138. MIT Press, 2006.
Balcan, M.-F., Sandholm, T., and Vitercik, E. Generalization guarantees for mulli-item profit maximization: Pricing, auctions, and randomized mechanisms, 2023.
Impact Statement
This paper advances the field of iterative combinatorial auctions (ICAs) by introducing MLHCA, novel machine learning-poweeed auction mechanism that achieves unprece- dented efficiency while reducing bidders' cognitive load. The primary goal of this work is to enhance the practicality and efficiency of real-world auctions, such as those used in spectrum allocation, with large potential benefits for social welfare. By enabling more accessible and efficient auc- tions, MLHCA has the potential to positively impact market design, increasing participation and improving resource al- location across various domains.
Bichler, M., Hao, Z., and Adomavicius, G. Coalition-bused
pricing in ascending combinatorial auctions, pp. 493-
528. Cambridge University Press, October 2017. ISBN 9781 107133345. doi: 10.
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-661 667, 2004.
The methods proposed rely standard ML and optimiza- tion techniques, and we do not foresee immediate ethical concerns arising from their application. However, as in any setting involving self-interested agents, potential conflicts of interest between participants may arise. While such con- cerns are important in practice (as they are for any auction mechanism), addressing them lies outside the scope of this paper.
Brero, G. and Lahaie, S. A bayesian clearing mechanism for combinatorial auctions. In inPPre Proceedings of the 32nd AAAI Conference on Artificial Intelligence, 2018.
Brero, G., Lubin, B., and Seuken, S. Combinatorial auctions via machine learning baaend preference elicitation. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, 2018
References
Brero, G., Lahaie, S., and Seuken, S. Fast iterative combina- torial auctions via bayesian learning. In Proceedings of the 33rd AAAI Conference of Artificial Intelligence, 2019.
Almahdi, M., Mohammed, Y. A., and Attia, T. A. Sim- ulating spectrum auctions: A reinforcement learning approach. In 2025 Emerging Technologies for Intel- ligent Systems (ETIS), pp. 1-6, February 2025. doi: 00.11099FTT16440022225.. 10961777 URI ieeexplore, ieee wttp://docmme//11917//2
Brero, G., Lubin, B., and Seuken, S. Machine learning- powered iterative combinatorial auctions. arXiv preprint WrXiv:191.008042 Jan 2021.
Cole, R. and Roughgarden, T. The sample complexity of revenue maximization. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC
Ausubel, L. M. and Baranov, O. A practical guide to the combinatorial clock auction. Economic Journal, 127(605):F334-F355) 2017.
*,, pp. 243-252, New York, NY, USA, 2014. Associa- tion for Computing Machinery. ISBN 978 9781450327 doi: 10.1 111111///1999625555 867. URL ht ht /doi. org /rg/10.111 11t11...11/25999 00177996655991 2591867.
Ausubel, L. M. and Baranov, O. Iterative vickrey pricing in dynamic auctions, 2019.
Ausubel, I.. M. and Baranov, O. Revealed preference and ac- tivity rules in dynamic auctions. International Economic Review, 61 (2):472555,, 2020. doi: https://doi.orr/100 10.
Cramton, P. Spectrum auction design. Review of Industrial Organization, 42(2):161-190, 2013.
11 12431. URL htw.t:ttttt//ttttmttt /ttp:///nnnneeee ibrary. wiley c /o//doo/aaaao abs/ 10. 11w.1/ii1eere.. 12431.
d' Eon, G., Newman, N., and Leyton Bioton-Broow, K. Under- standing iterative combinatorial auction designs via multi- agent reinforcement learning. In Proceedings of the 25th ACM Conference on Economics and Computation, EC '24, pp. 1102-1130, New York, NY, USA, 2024. Associa- tion for Computing Machinery. ISBN 9798400707049,
Ausubel, L. M. and Baranov, O. V. Market design and the evolution of the combinatorial clock auction. The American Economic Review, 104(5):44-4411, 2014.
10

---

Prices, Bids, Values: One ML-Powerred Combinatorial Auction to Rule Them All
doi: 10. (0.1145536670865..673644 URL https::/ddd.t btg/10..144/3670080
ETHHZ-B-000558899 URL SttLtts///aaxiv.coo abs abs/2112.15577
Dütting, P., Fischer, F., Jirapinyo, P., Lai, J. K., Lubin, B., and Parkes, D. C. Payment rules through discriminant- based classifiers. ACM Transactions Economics and Computation, 3(1):5, 2015.
Heiss, J., Teichmann, J., and Wutte, H. How (implicit) regularization of relu neural networks characterizes the learned function part ii: the multi-d case of two layers with random first layer, 2023. URL https: //axivv. org/ abs/////////// 22303 11454.
Dütting, P., Feng, Z., Narasimhan, H., Parkes, D. C., and Ravindranath, S. S. Optimal auctions through deep learn- ing. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Huang, D., Marsolejo-Cossio, F,, Lock, E., and Parkes, D. Accelerated preference elicitation with lIm-based prox- ies, 2025. URL https: aaraiivv.... org/ abs/ 2501. 14625.
Dütting, P., Mirrokni, V., Paes Leme, R., Xu, H., and Zuo, S. Mechanism design for large language models. In Proceedings of the ACM Web Conference 2024, WWW '24, pp. 144-155, New York, NY, USA, 2024. Associa- tion for Computing Machinery. ISBN 9798400701719. doi: 10.114453588333436655555 org/10, 145 0014445/5893444 3645511.
Innovation, Science and Economic Development Canada. 3800 mhz auction provisional results, 2023, URL https://ised: isde www.aa....aaaaaaaaaoaaaaaaaaaaae apettrumnaaagggeeass--eacaaaaaaa en en/sseectrum-aalocctttoo//
URL https::///// //doi.
3800-mhz muz- wttt---roviiiiiio ptt.aaautttooopoooiiioooaaaa-a-a resultss t1. Accessed: 2024-10-08.
Estermann, B., Kramer, S., Wattenhofer, R., and Wang, Y. Deep powweed iterative combinatorial auctions with active learning. In Proceedings of the 2023 Interna- tional Conference on Autonomous Agents and Multiagent Systems, pp. 2919-2921, 2023.
Kwasnica, A. M., Ledyard, J. O., Porter, D., and De- Martini, C. A new and improved design for multi- object iterative auctions. Management Science, 51(3): 419-434, 2005. ISSN 00251909, 15265501. URL http: /www. http://wttttrrrro//////o....ottt wttp/orrg/aeeeeeeeeeee cetttaabee201103440 20110340.
Goeree, J. K. and Holt, C. A. Hierarchical package bidding: paper & pencil combinatorial auction. Games and Economic Behavior,
Lahaie, S. and Lubin, B. Adaptive-price combinato- rial auctions. In Proceedings of the 2019 ACM Con- ference on Economics and Compulation, EC '19, pp. 749-750, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 9781450367929, doi: 10. 1145/332852633329615 URL https: http:////oooo////////// 10. 10.1145/332855 3329615.
2010.
Goetzendorff, A., Bichler, M., Shabalin, P., and Day, R. W. Compact bid languages and core pricing in large multi- item auctions. Management Science, 6187):168411703,
2015. doi: 10. 10.1287/mmss:2214427776 //doi. woooo////// hetp://..111111 /ww.m 20766.
URL https:
Lahaie, S. M. and Parkes, D. C. Applying learning algo- rithms to preference elicitation. In Proceedings of the 5th ACM Conference on Electronic Commerce, 2004.
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-thin -hird European Conference on Artificial Intelligence, pp. 261- 267, 2018
Lubin, B., Seuken, S., Beyeler, M., and Brero, G. imlca: Ma- chine learning-powered powered iterative combinatorial auctions with interval bidding, 2021. URL ptttpp://arxivv
org/ abss22099 1t1/2/009...300 13605.
Heiss, J. Inductive Bias of Neural Networks and Selected Applications. Doctoral thesis, ETH Zurich, Zurich, 2024. URL https: //ts:///wwww wwwww:wweeeeeccceeeecceccce coweceh---olloee http..cchhancleee..500..0. http://2....001110555590500
Maruo, R. and Kashima, H. Efficient preference elicita- tion in iterative combinatorial auctions with many par- ticipants, 2024. URL pectps://arxiv... /abs/ 2403.1900
Heiss, J., Teichmann, J., and Wutte, H. How implicit regular- ization of Neural Networks affects the learned function Part November 2019. URL sattps://i /wt.waawwv.og.//..... abs/ abs/1911.. 02903.
Milgrom, P. and Segal, I. Designing the us incentive auc- tion. Handbook of spectrum auction design, pp. 803-812, 2017.
Morgenstern, J. and Roughgarden, T. The pseudo-dimenstoe of near-optimal auctions. In Proceedings of the 28th Inter- national Conference on Neural Information Processing Systems Volume 1, NIPS' 15, pp. 1444,44, Cambridge, MA, USA, 2015. MIT Press.
Heiss, J. Teichmann, J., and Wutte, H. How in- finitely wide neural networks can benefit from multi- task learning an exact macroscopic characterization. arXiv preprint arXiv:21 2021. doi: /0.3929/

---

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
Narasimhan, H., Agarwal, S. B., and Parkes, D. C. Au- tomated mechanism design without money via machine learning. In Proceedings of the 25th International Joint Conference on Artificial Intelligence, 2016.
Weiss, M., Lubin, B., and Seuken, S. Sats: A universal spectrum auction test suite. In Proceedings of the 16th Conference Autonomous Agents and MultiAgent Sys- tems, Pp. 51-59, 2017.
Nisan, N. and Segal, I. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory, 129(1):192-22) 2006.
Weissteiner, J. Integrating advanced machine learning meth- ods into market mechanisms. PhD thesis, University of Zurich, 2023.
Ongie, G., Willett, R., Soudry, D., and Srebro, N. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint arXiv:1910.01635, 2019. URL https://arxiv org/pdf/19100 01635.pds
Weissteiner, J. and Seuken, S. Deep -ooenin iterative combinatorial auctions. Proceedings of the AAAI Conference Artificial Intelligence, 34(02): 2284-2293, Apr. 2020. doi: 10.1609/aaai.v34000
5606. URL https://ojs aaai. org/ index. http:/AAt/arriicle/veeewe///////
Parhi, R. and Nowak, R. D. What kinds of functions do deep neural networks learn? insights from variational spline theory. SIAM Journal on Mathematics of Data Science, (2):464 489, 2022.
Weissteiner, J., Heiss, J., Siems, and Seuken, S. Monotone- 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- 548. International Joint Conferences on Artificial Intelli- gence Organization, 7 2022a. doi: 10.249633/jcci 2022/ 77. URL https: ///oiii////////// meriioorg/100 .11.....44.55 241.0......icaaaa 2022/773 Main Track.
Rassenti, J.. Smith, V. L., and Bulfin, A combina- torial auction mechanism for airport time slot allocation. The Bell Journal of Economics, pp. 402-417, 1982.
Savarese, P., Evron, I., Soudry, D., and Srebro, N. How do infinite width bounded norm networks look in function space? arXiv preprint arXiv: (etiiv:/9020004444 2019. URL https: / aarivv org/ abs 1902. 05040.
Weissteiner, J., Wendler, C., Seuken, S., Lubin, B., and Püschel, M. Fourier analysis-based iterative combina- torial auctions. In Proceedings of the Thirty-First In- ternational Joint Conference Artificial Intelligence, IJCAI-22, pp. 549-556. International Joint Conferences on Artificial Intelligence Organization, 7 2022b. doi: 10.24963/ijcai 2022/78 10. 2t2224433iccaii 2022/78. Main Track.
Scheffel, T., Ziegler, G., and Bichler, M. On the impact of package selection in combinatorial auctions: an experi- mental study in the context of spectrum auction design. Experimental Economics, 15:667-60 2012a.
Scheffel, T., Ziegler, G., and Bichler, M. On the impact of package selection in combinatorial auctions: an experi- mental study in the context of spectrum auction design. Experimental Economics, 15(4):667-692, 2012b.
URL https:/ /ttps:://oo http//doiiooe org/
Weissteiner; J., Heiss, J., Siems, J., and Seuken, S. Bayesian optimization- based combinatorial assignment. Proceed- ings of the AAAI Conference on Artificial Intelligence, 37, 2023.
Soumalias, E., Curry, M. J., and Seuken, S. Truthful aggregation of Ilms with an application to online ad- vertising. 2024a. URL 2405. 05905.
abs/
Williams, F., Trager, M., Panozzo, D., Silva, C., Zorin, D.,. and Bruna, J. Gradient dynamics of shallow univariate relu networks. In Advances in Neural Information Pro- cessing Systems, pp. 8378 008888377748 233,,0111 2019.
Soumalias, E., Zamanlooy, B., Weissteiner, J., and Seuken, S. Machine learning-powered course allocation. In Proceedings of the 25th ACM Conference on Eco- nomics and Computation, EC '24, pp. 1099, New York, NY, USA, 2024b. Association for Computing Machinery. ISBN 9798400707049.
doi: 10.1145/ 3670865.3673573. URL nttps://doi.orr 1145/3670865.25
Soumalias, E. N., Weissteiner, J., Heiss, J., and Seuken, S. Machine dearning-powered combinatorial clock auction. Proceedings of the AAAI Conference on Artificial Intel- ligence, (899))9891199999 -9000, Mar. 2024c. doi: 10.1609/ aaai. viiiiv3ii..88880 28850. URL ottp:///...ooo.nnntaa//aaaaaaaa. org/ index.php/AAee hndee..pg//AAs//atttilll/eeee//s
12

---

Prices, Bids, Values: One ML-Poowered 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 an ML-based ICAs.
Estermann al. (2023) use more diverse VQs for the initial VQs. They show that this diversity leads to higher efficiency than just asking initial VQs for ii.d. uniformly random bundles. However, this does not solve the problem of it being cognitively very hard for bidders to answer these VQs that are not aligned with their preferences. Moreover, their efficiency results are outperformed by our MLHCA.
Maruo & Kashima (2024) uses multi-task learning to transfer to improve the generalization of the MVNNs by leveraging similarities among the value functions across bidders. This technique should also be compatible with our MLHCA. Thus, it would be an interesting direction for future work to incorporate multi-task learning into MLHCA and to evaluate how much this would improve efficiency. From a game theoretical perspective, one should think very carefully if multi-task learning could change the incentives of bidders. From game- theoretccll perspective, one would achieve incentive-alignment with social welfare, if each bidder i cannot change the marginal efficiency of the economy N {i) (see Appendix B.5). For MLCA, 3 out of 4 VQs actually query these marginal economies, such that M. has no direct influence on these queries, which provides quite a strong game theoretical argument. Via multi-task learning, bidders have a more direct way to influence other bidders' models. While multi-task learning is a very promising direction to explore, one should be aware of potential game-theoretical risks imposed by multi-task learning.
Lubin et al. (2021) allow bidders to answer VQs with an interval over prices instead of exact price. It would be interesting to combine this approach with MLHCA in future work.
Weissteiner (2023) and Heiss (2024, Section 4.4) provide a broader picture on ML-based ICAs.
Huang et al. (2025) explore how LLMs can be leveraged to create a new interaction paradigm for auctions, where the bidders interact with the mechanism by providing only natural language input.
Another related line of research is mechanism design for LLMs, where participants bid effect the output of an ML model, specifically LLM, c.g. Dütting et al. (2024); Soumalias et al. (2024a).
d'Eon et al. (2024); Almahdi et al. (2025) apply reinforcement learning algorithms to combinatorial auctions to better understand bidder strategies. Extending this line of work to mechanisms such as MLHCA would be an interesting direction for future research.
A.2. A Machine Searning-Powerss ICA
In this section, we present in detail the machine learning-powered combinatorial auction (MLCA) by Brero et al. (2021).
At the core of MLCA is a query module (Algorithm 2), which, for each bidder E I C N, determines a new value query q, First, in the estimation step (Line 1), an ML. algorithm A, is used to learn bidder i's valuation from reports RG Next, in the optimization step (Line 2), an ML-based WDP is solved to find a candidate q of value queries. In principle, any ML algorithm A; that allows for solving the corresponding ML-based WDP in fast way could be used. Finally, if q; has already been queried before (Line 4), another, more restricted ML-based WDP (Line 6) is solved and q, is updated correspondingly. This ensures that all final queries are new.
In Algorithm 3, we present MICA. In the following, let R-; (Ri...., R R R.). MLCA proceeds in rounds until a maximum number of queries per bidder QTIxx is reached. In each round, it calls Algorithm 2 (Q 1)n + times: for each bidder E N, rreedd 1 times excluding a different bidder j * i (Lines 5 10, sampled marginal economies) and once including all bidders (Line 11, main economy). In total each bidder is queried Qroudd bundles per round in MLCA. At the end of each round, the mechanism receives reports Reew from all bidders for the newly generated queries gTT and updates the overall elicited reports It (Lines 12-14). In Lines 16-17, MLCA computes an allocation aj that maximizes the reported social welfare (see Equation (3)) and determines VCG payments p( R) based on the reported values R (see Appendix Definition B.
13

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
Algorithm 2: NEXTQUERIES(I, R) (Brem al. 2021) Index set of bidders I and reported values R foreach i E I do Fit A; on R:: [.[R.]
Inputs:
Estimatioo step Optimization step
Solve arg max Σ (a; KEF :E7
3 foreach i E T do
if (gi, v:(q:)) E R; then
Bundle alredd queried
Define F²' = {a E F : as # x, V(z, (x())) R.)
Re-solve q' E arg aa F Lier A (ai)(a))
Update q: = qi
return Profile of new queries q (Q), (Q1....,9.)
Algorithm 3: MLCA(Q Qmii, Qruund) (Brero et 2021)
Params: : QQii Qu Quound initial, and #queries/round foreach E N do
Receive reports R. for QI"l randomly drawn bundles
3 for k 1, 1,.... [(Qme: =Q"")/ do
PRound iterator
foreach i E N do
Marginal economy queries
Draw uniformly without replacement (Qrund_)) bidders from {i) and store them in N
foreach j E do
new = 9 " NEXTQUERIES(N \ (.)R-.)
NOw NEXTQUERIES(N, R)
Mala economy querles
foreach i NNNo do
10
Receive reports 17t for qt" set R. = Rg U T
Given elicited reports I compute OR in Equation (3)
Given elicited reports compute VCG-payments p(I))
13
return Final allocation an and payments P(
A.3. ML-Powered Demand Query Generation
In this section, we reprint the MI-powered demand query generation algorithm from Soumalias al. (2024c). The critical notions behind the idea are those of indirect utility and revenue and clearing prices.
Definition A.1 (Indirect Utility and Revenue). For linear prices p E IR a bidder's indirect utility U and the seller's indirect revenue are defined as
Upp == max (1:(x)
(p,x)) and
(4)
R(p) = max
Σ JEN
(p.
ai)
6
Σ
(5)
a
JEM
ie., at prices p. Equations (4) and (5) are the maximum utility bidder can achieve for all X' and the maximum revenue the seller can achieve among all feasible allocations.
Definition A.2 (Clearing Prices). Prices p E Imm are clearing prices there exists an allocation a(p) E F such that
1. for each bidder i, the bundle (p(p) maximizes her utility, i.e., v((a((p)) (p, ap))) (p, Vi E N, and
2. the allocation ap) FF maximizes the sellers revenue, i.e.. ΣIEN ap,);(p)) R(p).
Theorem A.3 extends Bikhchandani & Ostroy (2002, Theorem 3.1), establishing a connection between the aforementioned definitions:
Theorem A.3 (Soumalias al. (2024c)). Consider the notation from Definitions A.I and A.2 and the objective function
For linear prices, this maximum achieved by selling every item, i.e., Vj E Eie (a.); = =
14

---

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
W(p,v)= R(p) EiEN Up, Ug). Then holds that, if a linear clearing price vector exists, every price veclor
p' arg min
(6a)
$ER
such that
(II( EF
(6b)
is clearing price vector and the corresponding allocation alp') E F. is efficient.
Theorem A.3 does not claim the existence of linear clearing prices (LCPs) p E Ryo For general value functions v, LCPs may not exist (Bikhchandani & Ostroy, 2002). However, in the case that LCPs do exist, Theorem A.3 shows that all minimizers of equation 6 are LCPs and their corresponding allocation is efficient. This is at the core of their ML-powered demand query generation algorithm.
Their key idea generate ML-powered demand queries is the following: As an approximation for the true value function wa they use for each bidder distinet mMVNN My X + Ryo that has been trained the bidder's elicited DQ data R, Motivated by Theorem A.3, they then try to find the DQ p E R minimizing W (p,, (M²) subject to the feasibility constraint equation 6b. This way, we find demand queries E I2 which, given the already observed demand responses Rt have high clearing potential.
Note that equation 6 a hard, bi-level optimization problem. Instead, Theorem A.4 allows them to minimize the problem via gradient descent:
Theorem A.4 ((Soumalias et al., 2024c)). Let (M.) be tuple of trained mMVNNs and let 27 (p) arg max {M, (x) ()) denote each bidder's predicted utility maximizing bundle w.r.t. M Then holds that p+ (pp. (M)) is convex, Lipschitz-contnnovn and a.e differentiable. Moreover,
Σ V (M))
always a sub-gradient and a.e. clussical grudient.
With Theorem A.4, obtain the following update rule of classical GD plaw a.e.
P, (P---le -elee-Ese EiEN (EEN(()())) (p)),, Vj M. Interestingly, this equation has an intuitive economic interpretation. If the jth item is over/under- based on the predicted duilit-maxiiiiznn bundles i (p), then its new price yfe is increased/decreaseed by the learning rate times its over/under-demand To enforce constraint equation 6b in GD, they asymmetrically increase the prices + μ E R20 times more in case of over-demand than they decrease them in of under-demand. This leads to the final update rule:
new Dj
Pj T5 Σ (+(())))) EjeM, iEN
(8a)
7. (1++)
.g < EiEN (w) else
33 =
(8b)
B. Payment and Activity Rules
In this section, we reprint the VCG and VCG-nearest payment rules, as well as give an overview of activity rules for the CCA, and argue why the most prominent choices are also applicable to our MLHCA. Finally, we show how MLHCA can immediately detect if bidder's reports are inconsistent with any valuation function.
B.I. VCG Payments
Definition B.1. (VCG PAYMENTS FROM DEMAND AND VALUE QUERY DATA) Let R = (R). R.) denote an elicited
set of both demand and value query data from each bidder and let R_; = (R,.... Ri-1. R4+1. R.). We then calculate
More precisely, constraint equation should be reformulated as
3 (af (F)) E X x (6)
(1) FF,
FEN
where X (f) = arg max (m((x) (p, x, since theory, xi (f) does not always have to unique.
15

---

types of activity rules that Prices, Bids, Values: One MI--Powered Combinatorial Auction to Rule Them All
the VCG payments π (R) (m)ca (R) .... Fp
(o)) Rg follows:
mi (R)
E By (R-(R)
E JEN((A)
Ty (aaaa Ry).
(9)
JEM((S)
where a" aRR-s) is the allocation that maximizes the inferred social welfare when excluding bidder i, i.e.,
a" (R-s) E arg max aEF
Σ By(af;R))
(10)
JENMON
and a" (R) is the inferred social welfare- welfare-maxinine maximizing allocation (see Equation (3)).
Thus, when using VCG payments, bidder i's urility is:
u: ui(a" (R):) VCG (R)
va (R).)
Σ
(a) R,)
JENUI
Σ ūy (a (R-);;
JENV(A
B.2. VCG-Nearest Payments
To define the VCG-nearest payments, we must first introduce the core:
Definition B.2. (THE CORE) An outcome (a, .T E F R (i.e., a tuple of a feasible allocation a and payments т) is in the core it satisfies the following two properties:
1. The outcome is individual rational, i.e, u, vt(a;) - 2 f all i N
2. The constraints
ALCN Σ (R) > max
Σ va(())
(us(as)
(II)
KENVL
VEL
VEL
where (a:) is bidder i's value for bundle a; and F is the set of feasible allocations.
In words, a payment vector и (together with feasible allocation a) the core no coalition of bidders C is willing to pay more for the items than the mechanism is charging the winners. Note that by replacing the true values vy(a;) with the bidders' (possibly untruthful) inferred values based on their reports ün (a;; R,) in Definition B.2 one equivalently define the revealed core
Now, we can define
Definition B.3, (MINIMUM REVENUE CORE) Among all payment vectors in the (revealed) core, the (revealed) minimum revenue core the set of payment vectors with smallest Inoom,, i.e., which minimize the sum of the payments of all bidders.
We can now define VCG-nearest payments:
Definition B.4. (VCG-NEAREST PAYMENTS) Given an allocation aR for bidder reports R, the VCG-nearest payments π VCGGneames R)) are defined as the vector of payments in the (revealed) minimum revenue core that minimizes the Ln-norm to the VCG payment vector VCG (R.).
B.3. On the Importance of Activity Rules to Align Incentives
In the CCA, activity rules serve multiple purposes. First, they help accelerate the auction process. Second, they reduce "bid-sniping" opportunitie--bidlee concealing their true intentions until the very last rounds of the auction. Third, they limit surprise bids in the supplementary round of the CCA, significantly reducing a bidder's 's ability to drive up opponents' payments by overbidding on bundles they cannot win (Ausubel & Baranov, 2017). There are implemented in CCA:
'The 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: One ML-Pooweeed Combinatorial Auction to Rule Them All
1. Clock phase activity rales, which limit the bundles that an agent can bid on during the clock phase, based on their bids in previous clock rounds.
2. Supplementary round activity rules, which restrict the amounts that an agent can bid on specifie sets of items during the supplementary round.
Traditionally, most clock phase activity rules in the CCA have relied on either revealed preeeeee-reeeeeeeeeeee principles or a points-basel system, where points are assigned each item before the auction, and bidders are only allowed to submit monotonically non-increasing bids in terms of points. In other words, as prices rise across rounds, bidders cannot submit bids for larger sets of items. Both of these approaches, as well as hybrid combinations thereof, were shown to actually further interfere with truthful bidding in some cases (Ausubel & Baranov, 2014; 2020).
However, Ausubel & Baranov (2019) showed that basing clock phase activity rules entirely on the generalized axiom of revealed preference (GARP) can dynamically approximate VCG payoffs, thus improving the bidding incentives of the CCA. GARP imposes errealed-preference constraints (see Definition B.5) on the bidder's demand responses. The GARP activity rule requires that the bidder demonstrates rational behavior in her demand choices, without necessitating monotonic price trajectory. As a result, it can also be applied during the MI.-powered DQ phase of MLHCA, allowing our mechanism to enjoy similar improvements in bidding incentives.
For the supplementary round, the CCA's most prominent activity rules are again based on a combination of points- based systems and evvaled-prefereeee ideas, which we outline below:
Definition B.5. (REVEALED- CONSTRAINT) The eevealed-prefereee constraint for bundle x E X with respect to clock round is
bx(x)) S b,(=")+ (,,xx=x))
(12)
where (x)) E Rgz is bidder i's bid for bundle x E X in the supplementary round, x" E X' is the bundle demanded by the agent at clock round r, bx(x") E RRzo is the final bid for bundle x" E X' and p" E Ryo is the linear price vector of clock round r.
Intuitively, the revealed prefeeed-ppeeeeeceeeeeeeeeeeeeee constraint ensures that bidder cannot claim a higher value for bundle r relative to bundle x", given that they expressed preference for bundle x" at the given prices p" (see Equation (1)). The difference between the three most prominent supplementary round activity rules is with respect to which clock rounds the preffeed-reference constraint should be satisfied. Specifically:
1. Final Cap: A bid for bundle x E X' should satisfy the revealed-prefcrence constraint (Definition B.5) with respect to the final clock round's price DoCCA E RR and bundle 20CA E X.
2. Relative Cap: A bid for bundle x E X should satisfy the revealed-preferrncee constraint (Definition B.5) with respect to the last clock round for which the bidder was eligible for that bundle x E X, based on the points-based system.
3. Intermediate Cap: A bid for bundle x E X should satisfy the grvealed-preference constraint (Definition B.5) with respect to all aigiibliit-rrdducin rounds, starting from the last clock round for which the bidder was eligible for x E X based on the point system.
Ausubel& & Baranov (2017) showed that combining the Final Cap and Relative Cap activity rules leads to the largest amount of reduction in bid-sniping opportunities for the UK 4G auction, as measured by the theoretical bid amount that each bidder would need to increase her bid by in the supplementary round in order to protect her final clock round bundle. Finally, note that the Final- and Intermediate Cap activity rules can also be applied the ML-powered DQ phase of our MLHCA. 9
To conclude, both the DQ and VQ phases of MLHCA are compatible with the most prominent activity rules of the CCA, and MLHCA also remains compatible with the commonly used VCG-nearest pricing rule (Definition B.4). Combined with MLHCA's s similar interaction paradigm to the CCA, these aspects provide strong evidence that our mechanism can leverage activity rules to effectively mitigate bidder misreporting opportumities, much like the classical CCA.
"Soumalias et al. (2024c) argued that with the modification for the Relative Cap rule that the revealed revealed-preference constraint should hold for the CA rounds that follow the same price update rule as the CCA, and then the MI-powered clock rounds should be treated as corresponding the same amount of points, since the prices in these rounds aggregate stay very close the prices of the last Qinit round.
17

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
B.4. MLHCA Can Detect Inconsistent Misreports
In the following lemma, we formally prove that if bidder's reports are inconsistent with any valuation function, then the training loss for that bidder's network will be strictly positive, thus MLHCA can detect such misreports.
Lemma B.6 (Strictly Positive Loss from an Inconsistent Datapoint). Let R (Re2, R²2) be a set of elicited reports by bidder that is rationalizable by some monotone valuation function vo X - Rz0. Suppose, that during the MLHCA auction (Algorithm 1), the bidder responds to the next query, either a DQ (3" (p").ppp") p.p") or a VQ (2, 6(ā)) and assume that no monotone valuation u can simultaneously rationalize all of her responses R'. Then, when using Algorithm 4 (with any regression loss F for the VQ responses that satisfies F 2 and y = y have ming (0) > O.
Fly. ú) = 0) to fit an MVNN M to R', we
Proof. We prove the claim in cases. Case I: Suppose that the bidder misreports in a way that is non-rationalizable by any valuation function during the DQ phase of the auction. In that phase, the bidder's set of reports consists only of demand queries.
For each datapoint (z"("") in R Algorithm 4 attempts to make
(p') E
arg max #EA
M (x) - (V",, =t)
match the reported x² =p"). It it does not match, the loss is incremented by nonnegative amount:
(f) = (+M'(*")")) - (p' (p"))) - [M (x"))))')))))))) - (p', x (x"))
2 0.
Hence the total loss L(0) is always weakly positive.
Suppose, for contradiction, that there exists 0 with L( = 0. If (()) 0, it means the predicted best response matches the reported one, i.e., 2- (p") x² (p") for all including
F.
However, for any 0 E θ, the (m)MVNN M is by construction a valid valuation function satisfying free disposal (Weissteiner et al., 2022a; Soumalias et al., 2024c). The condition 4* (p") x (y") for all r means precisely that M rationalizes all data in D'. Thus, there exists a valuation function rationalizing all data points, including 7 (f"), a contradiction.
Case 2: Suppose that the bidder misreports in a way that is non-rationalizaabl by any valuation function during the VQ phase of the auction. Similarly, given that the loss function in each datapoint (both DQs and VQs) is weakly positive, the only way the loss can be zero is if it is zero every point. But then, the MVNN once again has rationalized the agent's s reports. Thus, a value function exists that rationalizes all of the agent's 's reports, contradiction.
Note that Lemma B.6 can also be applied to the case where we observe O VQs. Thus, Lemma B.6 can also be applied to detect inconsistent misreporting for DQ-only auctions such as ML-CCA.
Further note that Lemma B.6 can always detect inconsistent misreporting, while other forms of misreporting cannot be detected this way.
B.5. On the Importance of Marginal Economies to Align Incentives
In this section, we review the key arguments from Brero et al. (2021) on why MLCA provides strong incentives for truthful reporting in practice. These arguments extend any MI--powered ICA that employs the same VQ-generation algorithm, including MLHCA.
Bidder i's utility in MLCA (and MLHCA) under VCG payments (see Definition B. can be expressed as:
= v.(a" (R).) m.
(R)
= v.(aa" (M))) +
Σ Ty (a R))
Σ Ty (a
JENVES
(EN
(4)
(b) Inferred SW of murginal econony
18

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
Any beneficial misreport by bidder must increase the difference (a) (b).
MLCA has two features that mitigate manipulations. First, MLCA explicitly queries each bidder's marginal economy (Algorithm 3, Line 5), which implies that (b) is practically independent of bidder i's reports. Experimental evidence supporting this claim is provided in Section 7.3 of Brero et al. (2021). Second, MLCA (and also MLHCA) enables bidders to "push" information to the auction which they deem useful. This mitigates certain manipulations that target (a), as it allows bidders to increase (a) with truthful information. Brero et al. (2021) argue that any remaining manipulation would be implausible as it would require almost complete information.
Under further assumptions, can also derive two theoretical incentive guarantees:
Assumption 1 requires that, for all bidders i E N, if all other bidders report truthfully, then the reported social welfare of bidder i's marginal economy (i.e., term (b)) is independent of her value reports.
Assumption 2 requires that, if all bidders i N bid truthfully, then MLCA finds efficient allocation.
Result 1: Social Welfare Alignment Under Assumption I, and given that all other bidders are truthful, MLCA is social welfare aligned. This means that the only way for a bidder to increase her true utility is by increasing the reported social welfare of a² (R) in the main economy (i.e., term (a)), which, in this case, equals the true social welfare of a (R) (Brero et al., 2021, Proposition 3). The same true for the VQ phase of MLHCA, as it employs the same allocation and payment rules.
Result 2: Ex-Post Nash Equilibrium If both Assumption and Assumption 2 hold, then bidding truthfully constitutes an ex-post Nash equilibrium in MLCA (Brero et al., 2021, Proposition 4). The same is true for the VQ phase of MLHCA, it employs the same allocation and payment rules.
Remark B.7 (Experimental Evaluation of Assumption 2). The results shown in Tables and suggest that Assumption 2 is more realistic for MLHCA than for any other mechanism. For GSVM, Assumption 2 is absolutely realistic for MLHCA and was already realistic for other VQ-based mechanisms such the ones proposed by (Weissteiner & Seuken, 2020; Weissteiner et al. 2022a; 2023). Also for SRVM, Assumption 2 is very realistic for MLHCA. In fact, MLHCA is the first method from Table 2 that always found an efficient allocation (only methods from Table 9 that use significantly more than 200 can keep up with this). Theoretically achieving 100% efficiency in all 50 random instances of an auction does not suffice as mathematical proof that the auction will always achieve 100% efficiency. However, for GSVM and SRVM, the fact that MLHCA found an efficient allocation within the first 60 out of 100 queries for all 50 instances, strongly suggests that 100 queries allow MLHCA to find an efficient allocation with almost 100% probability. For LSVM, MLHCA found an efficient allocation in 49 out of 50 auction instances, which from practical point of view also almost satisfies Assumption 2, and with few queries more fully satisfying Assumption might be in reach. At least for every domain, MLHCA is closer to satisfying Assumption 2 than its competitors.
To conclude, MLHCA's compatibility with both activity rules during its DQ rounds and marginal economies during its VQ rounds, well as its compatibility with VCG and VCG-nearest payments, provides strong evidence that MLHCA can effectively mitigate opportunities for bidder misreporting.
19

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
MVNN
The original definition (Weissteiner et al., 2022a) is a special case of the more general definition (Soumalias et al., 2024c) that we state here.
Definition C.1 (MVNN), An MVNN M. X' + Rzo for bidder i E N is defined as
(x)=) Wwk.k Po,05, (... (o,,
(W (W (Dx) 6-.')))) (......)
(13)
+ K2+ (Po ) - are the MVNN-specific activation functions with cutoff 24 > 0, called bounded ReLU (bReLUU)
N is the number of layers (K; hidden layers).
(o, (.) = min(t" (nxx(0,-))
(14)
k=1 with Witk 2 0 and b² = (b**) K.-1 with b** < 0 are the non-negative weights and non-positive biases of dimensions di x di.k-1 and d=ikk whose parameters are stored in A = (Wi, ,b).
w = =Wi+.) K.
D= diag (f/e1...., :/e..) is the linear normalization layer that ensures Dz E [0, 1] and is not trainable.
Remark C.2. The index i of the MVNN (x) emphasizes that we train an individual MVNN for every bidder to approximate U;. In the following, we sometimes omit the index if we just want to make general arguments about the MVNN architecture without.
Remark C.3 (Linear Skip Connection). Sometimes we also use linear skip connections as introduced in Weissteiner et al. (2023, Definition F.1)
Remark C.4 (Initiaization). We always the initialization scheme from Weissteiner al. (2023, Section 3.2 and Appendix E), which offers crucial advantages over standard initialization schemes as discussed in Weissteiner et al. (2023, Section 3.2 and Appendix E).
C.1. On the Inductive Bias of MVNNs
Weissteiner et al. (2022a); Soumalias et al. (2024c) have shown that MVNNs can represent any monotonic normalized function on X' However, for finitely many data points, multiple different monotonic functions can fit the data equally well, but the training algorithm will choose only one of these functions. We want to understand according to which preferences the algorithm makes this choice, i.e., we want to understand its inductive bias.
For certain ReLU-NNs it has been shown that 1.2-regularization (also known as "weight decay") of the parameters corresponds to regularizing a Lp-norm of the second derivative of the function (Heiss et al., 2019; 2023; 2021; Heiss, 2024; Savarese al., 2019; Ongie et al., 2019; Williams et al., 2019; Parhi & Nowak, 2022). Since the second derivative of linear functions is zero, these NNs prefer linear functions.
However, MVNNs use different activation function (Weissteiner et al., 2022a). For MVNNs, no theoretical result about their second derivative has been proven so far. It is quite clear that the L2-regularization of the parameters of a MVNN does not exactly correspond to any Lp-norm of the second derivative. Weissteiner et al. (2023) modified the MVNN architecture by adding so-called linear skip connections (Weissteiner et al., 2023, Definition F.1) to obtain an inductive bias towards linear functions. If one uses unregularized linear skip connections but regularizes all other parameters, it is quite obvious that the optimal parameters will only have non-zero weights in the linear skip connections if a monotonic linear function can perfectly explain the data." 10
In the setting of Example 1 (which is based on the example in the proof of Theorem 3.2) one can also prove that MVNNs with arbitrarily small 1.2-regularization, would always choose a function that is linear on X' given any possible truthful DQ responses from bidder 2, even without linear skip connections.
Proposition C.5. As in Example 1, let n = 2, m = 1, ei = 10 and U2 such that whenever bidder is queried a DQ she answers in the following way:
the price p is below
10" bidder will answer with (p) = (10);
10If the data can be perfectly explained by linear function, then only using the linear skip connections can achieve zero training loss and zero regularization costs, while setting any parameter outside the linear skip connections any non-zero value would lead non-zero L2 regularization costs.
20

---

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
if the price p- Io' bidder? will answer with either wz(p) (10) or xz(p) (0); 94 bidder 2 will answer with <z(p)) = (0). To
if the price is higher than
Let (p', ".......''"" .... C [0, o0) be the subset of prices bidder 2 is queried. Let 0* be any (local) minimizer of the L2-regularized loss from (Soumalias et al., 2024c)
L7 Σ (Mo(E5("))) (5"'"((""))
(Mo(z)(0") (00""))))(MMMMM00 (,, (("))))) + 111112
where (5(p") == arg mix (Ma(z) - (V), Then the MVNN Ma- : X + R is linear.
Proof. We define p= = max {p-: (r) = (10), 1 1sr S "DQ }.
train
1. First we show that Ma- S 10p via contraposition argument. Let's assume Ma- 2 10q 10β, then multiplying the last layer's 's weights by 1 5 > would both reduce the data-loss-term L (since the activation the hidden layers of MVNNs are always non-negative) and the regularization costs X 11-112- Therefore, no local minima 0* can satisfy Mg. (10)= > 10p. Thus, we have shown that MMg- (10) S 10p holds for any local minima 0*,
2. Next, we show that all pre-activations of our MM- 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 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 Mg. (10). Scaling down these weights cannot increase the value of Ma- (z)) for any x E X, so it cannot increase the data-loss term L but scaling down weights obviously decreased the regularization costs. Thus, via this counterposition argument, we have proven that all the pre-activations are smaller or equal to the cut-off for any local minima 0".
3. Next, we show that all biases of 0* are zero. First, note that by Item 2, we know that MMg. is convex (since the bReLU is convex below the cut-off). By combining this fact with Item 1, we obtain that Mg-(z) S xp, since MVNNs always satisfy (0) = O. Let's assume the counterposition of at least one bias being strictly negative (as by definition, biases can never be positive for MVNNs). Then we could increase the bias a little bit without increasing the data-loss-term L 12 but increasing the bias reduces its regularization cost. Thus any local minima 0 satisfies that the biases are zero
By combining Items 2 and 3 we obtain that Mg. is linear.
Remark C.6 (Interpretation of the Inductive Bias of MVNNs). It is important to keep in mind that MVNNs can learn complicated non-linear monotonic functions, if the training data requires it. For example, if we receive the 2 VQs, v(20) = 20$ and v(10)= = 198, there is no linear function that can explain both VQs simultaneously, but an MVNN can casily learn a non-linear monotonic function which perfectly fits both VQs simultancously, i.c., MMa (20) = 20 and Ma- (10) = 19S. Therefore, the ability of MVNNs to learn non-linear monotonic functions is important, since we don't t want the MVNN predict MMg. (10) 10S, if we know already v(10)- = 19$. However in the case that we don't know v(110= = 198, but only observe 1 VQ, v(20) 208, then this section provides intuition understand that the MVNN would typically predict Ma- (10) 108. So the goal of this section is to better understand how MVNNs deal with insufficient information.
"If {p": : : (r) = (10), 1 S S Dain]
ripo I is empty, we define ş = 0. In Example 1. -4--
12 argument relies on the fact that we only queried finitely many DQs. If we asked infinitely many DQs that dense around p= = Io one would need to modify the argument hy not only increasing the biases but simultancously also decreasing certain weights.
84
21

---

Prices, Bids, Values: One ML-PPowered Combinatorial Auction to Rule Them All
D. Details on Section 3
In this section, we examine the limitations of using only VQs or only DQs in auctions and highlight the benefits of combining them.
D.I. Disadvantages of Only Using VQs
Almost all ML-powered VQ-based auctions including the current SOTA, BOCA (Weissteiner et al., 2023) first ask each bidder multiple random VQs (i.e., VQs for randomly selected bundles). These VQs are necessary to initialize the ML estimates of the bidder's value functions. In practice, it is very hard for bidders to answer random VQs since they are not aligned with their preferences." The most popular ICAs in practice (e.g.. the CCA) ask the bidders DQs, which have been argued can be answered by the bidders sufficiently well (Cramton, 2013). 14
Even if bidders manage to respond perfectly to random VQs, the information obtained is limited. This is because, in large combinatorial domains, bidders typically have high values for only a small subset of possible bundles, making the probability of querying one of these high-value bundles at random exceedingly low, On the other hand, querying bidders with DQs at random price vector is more likely to prompt responses that reveal their high-value bundles. This is formalized in Proposition 3.1, which we reprint for convenience:
Proposition D.1 (Restatement of Proposition 3.1). The expected social welfare of an auction that uses a single random demand query can be arbitrarily larger than that of auction that uses any constant number (k < 2nh of random value queries.
Proposition 3.1 Proof. Let n = 2 and C1 = C2 = =...= Cm = =1 i.e., the auction has m unique items. Bidder has a value of zero for the empty set and a value of e > 0 for any non-empty set of items, while bidder 2 has a value of V + xo for the full bundle, and a value of zero for any other bundle. Note that these are proper value functions, as they are both monotone and assign a value of zero to the empty set. The bundle space X has a size of 2mm For the auction that asks random value queries, the probability that bidder 2 is queried her value for the full bundle conditioned on not having been asked that question in the previous k queries is z- For auction instances with large numbers of items, taking oo, the probability of the auction not querying bidder 2 her value for the full bundle in k random value queries is:
lim II M0000
(1- j=1 2
k
(1-
) ( - 1))
= lim II ==1
ds
2 - j =1 2m
- (j 1)) (-)1)) )
(15)
m m0-
If that query for the full bundle is asked to bidder 2, then bidder will be allocated the full bundle and bidder 1 will be allocated the empty bundle, and the social welfare of the final allocation will be equal to V. In any other case, bidder 1 will be allocated non-empty bundle, and the social welfare of the allocation will be equal to
Now let's focus on the auction that asks each bidder single random demand query, and assume that the price of each item is an i...d. random variable with mean value p. The expected total price for the full bundle is m p. Applying Chebyshev's s inequality, the probability that the price of the full bundle is greater than V is zero. Thus, bidder 2 will always request the full bundle.
The only possible scenario in which bidder 2 is not allocated the full bundle is if bidder 1 requests non-empty bundle with equal (or higher) value than the bundle of bidder 2, and ties are broken in bidder I's favor. Given that bidder I's value is at most for any non-empty bundle, with probability 1, the value of the bundle requested by bidder is at most Given that the expected value of the price of each item is p > 0, applying Chebyshev's inequality yields that as m - oc, the probability of the full bundle having a price less than is zero. Thus, with probability bidder 1 will have an inferred value less than bidder 2 for the bundle she requested, and so with probability 1 the full bundle will be allocated to bidder 2, yielding social welfare of - 5o for this auction. This completes the proof.
Remark D.2. This limitation of random VQs is evidenced in practice. Empirical comparisons between VQ-based MI.- powered mechanisms, such as Weissteiner al. (2023), and DQ-based mechanisms, such as (Soumalias et al., 2024c), reveal
13 To provide some intuition, imagine you go to the supermarket because you want to hake a birthday cake for your friend and then you are asked your value for 30 frying pans plus 500 coconuts. It might be hard to estimate your value for such a random combination of items. In our practical supermarket example, now imagine that you view the price tags for the same items. It is quite doable decide which items you want to buy and in which quantities.
22

---

Prices, Bids, Values: One ML-PPowered Combinatorial Auction to Rule Them All
that efficiency after initial queries is significantly lower for VQ-based approaches across all tested domains (see Figure in Section 6).
Beyond auction efficiency, the limited information provided by random VQs poses challenges for learning algorithms in Ml-poowered ICAS. In contrast, DQs provide global information about bidder preferences across the entire bundle space, When bidder responds which reveals valuable information about her preferences across all possible bundles. Strong evidence for this is presented in Appendix E.2, where we show that the network trained only on DQs exhibits better generalization performance than one trained on random VQs.
DQ prices p. she solves the optimization problem: x (p) arg m {v:(x) (p. xt)
Additionally, if DQ prices are sufficiently low, bidders respond with their recover through VQs alone. By incorporating this information, the learning algorithm can more effectively identify critical regions in the allocation space and subsequently focus on refining those areas. This advantage is further supported by our experiments (Figure in Section 6). We show that in our MI-pooeerdd hybrid auction, the first MI--powered VQ after series of DQs achieves significantly higher efficiency compared to the first ML-powered VQ after an equivalent number of random VQs in the current SOTA VQ-based auction.
bundles, which may be hard to
Moreover, even if the auction finds an efficient allocation by using VQs, it cannot terminate early as there is no way for the auctioneer to certify that the auction has reached 100% efficiency. In contrast, for DQ-based auctions there is an easy condition that allows the auction to terminate early:
Proposition D.3. If clearing prices exist, an auction using DQs can provide a guarantee of optimal efficiency and terminate early.
Proof. If clearing prices have been found, the corresponding allocation constitutes a Walrasian equilibrium, and thus has an efficiency equal to 100%. See Soumalias et al. (2024c, Appendix C.1) for detailed proof.
Remark D.4. This is indeed an issue in practice. In Section 6, we experimentally show that, in realistic domains, our MLHCA can often reach 100% efficiency before the common maximum number of 100 rounds used by most ML-powered ICAs (e.g. Weissteiner & Seuken (2020); Weissteiner et al. (2022b;a; 2023); Soumalias et al. (2024c)) is reached.
D.2. Disadvantages of Only Using DQs
In this section, we show the disadvantages of using DQs to elicit the bidders' preferences.
The first major disadvantage of an auction employing only DQs is that the auction's 's efficiency can actually drop by adding more DQS.
Proposition D.5 (Restatement of Proposition 3.3). In a DQ-based ICA, adding DQs can actually reduce efficiency. A single DQ can cause an efficiency drop arbitrurily close to 100%. By comparison, in a VQ-based ICA, adding additional queries can never reduce efficiency (assuming truthful bidding).
Proof. Let m = 2. n = 2, 2 11,22 1,
U1 max (400- 10,21, 2- 1,,21} and
d/2 1.1 12,21-
Suppose the auction has asked two DQs. The first DQ p = (1,1) is responded by both bidders with (1,0) E arg argmax (v((z)- - (p.z)) }.} The second DQ = (1.2,1) is responded by bidder 1 with (1,0) E arg maxzex (o) (x)) - (p, })} and by bidder with (0, 0) E arg max (V2(x) - (p. x).
After these 2 DQs the WDP based on the inferred values (see Equation (3)), would assign item I to bidder (resulting in an inferred social welfare of 1.2 0 1.2). This is the efficient allocation with true social welfare (SCW) of 400, i.e., an efficiency equal to 100%.
Now suppose that a third DQ p = (401, 1) is added to the auction. Bidder I's demand response is (0, e arg max,ex (2) (z) - (p, } and bidder 2's response is (0,0) 0) E arg max,ex (z) - (p, x)). The WDP would now assign item 2 to bidder and item 1 to bidder 2, resulting in an inferred SCW of 1 + = 2). This would result only in an efficiency of 2+1.1 400 < 1%.
23

---

Prices, Bids, Values: One ML-PPowered Combinatorial Auction to Rule Them All
While the inferred SCW obviously cannot decrease in any round (since the set we maximize over cannot decrease in any round and inferred values cannot decrease), we have shown here that the true SCW can decrease substantially. In this example, the SCW dropped by more than 99%. One could easily modify this example to even obtain efficiency drop arbitrarily close to 100% if one decreases the values 1,1.2 and 2 (the prices and the values inside the value functions) by any small factor or increases the numbers 400 and 401, by any large factor. Then the proof would still work, which shows that the efficiency can even fall from 100% to values arbitrarily close to 0%.
On the other hand, if we only ask VQs, there is no difference between inferred SCW and true SCW (assuming truthful bidding), which results in non-decreasing SCW.
Remark D.6. This is significant issue in practice. In Section 6 we experimentally show that in the most realistic spectrum auction domain, the CCA's efficiency drops by over 7% with the introduction of more DQs. In second realistic domain, the CCA actually has higher efficiency after just 5 DQs compared to after 100. This efficiency degradation is not only a concern for the CCA but also affects ML-powered DQ-based ICAs in similar ways.
In the next lemma, we show that the same issue arises in an auction that uses both DQs and VQs:
Lemma D.7. In an auction that first uses DQs and then VQs, adding VQs can actually reduce efficiency. The efficiency drop can even be arbitrarily close to 100%.
Proof. Consider the setting from the proof of Proposition 3.3 including the first DQs. Recall that in this setting after these 2 DQs, the WDP would achieve 100% efficiency. Now instead of the third DQ we ask the following VQ: We ask bidder for her value of the bundle (0, 1) and we ask bidder 2 for her value of the bundle (1, Then the WDP based on these 3 rounds would assign item 2 to bidder 1, and item to bidder 2, as we explain in the following. The inferred SCW in (0, 1) + (2(1, = 2 + 1.1 (which is equal to the true SCW of this allocation) is higher than the inferred SCW of all other allocations consisting of elicited bundles: For bidder the DQ responses were always (1, 0) with inferred value 1.2, and the VQ elicited 2n (0, 1) = 2. For bidder 2, the DQ responses were (1, O) with inferred value 1 and (0. with inferred value 0, and the VQ response was (g 0) = 1.1. So we see that the highest inferred SCW among all feasible allocations is achieved by assigning item to bidder and item bidder (e.g., assigning it the other way around would only achieve an inferred SCW of 1.2 + 0, while the true SCW 0i (1, + (2 1) 400 0 would be much larger).
So the efficiency dropped from 100% to 2+111 1% after the vQ (i.c., the efficiency drops by more than 99%).
Even though Lemma D.7 shows that an auction using DQs followed by VQs can still experience an arbitrarily large efficiency drop, we can completely address this issue using single carefully designed VQ, which we call the "bridge bid."
Definition D.8 (Bridge bid). The bridge bid asks each bidder her value for the bundle she would have been allocated according to the WDP after the last DQ
Lemma D.9. In ICA that first asks DQs and then VQs, by first using single specific VQ, the bridge bid from Definition D&8, the auction can ensure its efficiency is at least as high as the efficiency achieved by its DQs alone.
Proof. The bridge bid itself can obviously not decrease efficiency, because it simply replaces the inferred SCW of the winning allocation of the previous WDP with the true SCW of exactly the same allocation. In other words, the inferred values of the bundles of the previously WDP-winning allocation can be increased or stay the same, while all the other inferred values stay the same. Thus the winning allocation stays the winning allocation when the bridge bid is added. For the remainder of the proof, we will show that all the VQs after the bridge bid can also not decrease the efficiency. In every further WDP another allocation can only outperform the bridge bid allocation if it has higher inferred social welfare. However, if it has a higher inferred SCW, it's true SCW cannot be lower than the one of the bridge bid. And we have shown in the beginning of the proof, the SCW of the allocation of the bridge bid is equal to the SCW of the last WDP winner after the last DQ. Thus, for any VQ after the bridge bid the SCW cannot be worse than the winning allocation of the WDP right after the last DQ.
Remark 10 Again, this in practice is highly impactful. In our experimental section (Section 6), we show that in the most realistic domain, our MLHCA without this bridge bid loses 7 percentage points of efficiency. The auction needs another 20
Note that after every VQ it is still possible that the WDP combines bundles queried during any VQ with bundles that were DQ responses for any old DQ Thus even after some VQs the inferred SCW of the winnigg allocation he strictly smaller than its true SCW.
24

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
VQs recover its DQ-only efficiency. By using just a single specialized VQ, the bridge bid, we can completely alleviate this problem. For more detailed discussion, see Appendix G.8.
The next theorem shows an even more fundamental limitation of only asking DQs. Specifically, asking only DQs can result in low efficiency, even in the limit where we ask all possible DQs.
Theorem 1.11 (Restatement of Theorem 3.2). For every > 0, there exist infinitely many instances of auctions for which no combination" 16 of DQs can achieve efficiency above 50% + This remains true even if the bidders additionally report their true values for all bundles they requested in those DQs.
Proof. First, we give an example with concrete numbers to convey the main intuition of the proof. Let n = 2, m = 1, C1 10, 0i (z) = 1001,; 21, (2(x)) = 9 + 1 z.. Here, the unique efficient allocation would assign 1 iitem to bidder I 25
and the remaining 9 items to bidder 2. resulting in an SCW of (1) + 02 (9) - 100 + 9 9 no DQ p R20 that bidder would answer with xp(p) = (9):
g²
25 = 184.24. However, there
If the price is below 91 bidder 2 will answer with (p) = (10); Io
if the price
94 To
bidder 2 will answer with either =v(v) = (10) or x;)())) = (0);
if the price p is higher than 94 bidder 2 will answer with (p) (0).
10a
Therefore, the WDP cannot assign 9 items to bidder 2 if only DQs were asked, no matter how many DQs were asked. Raising the bids for those bundles would also not help, because this would still not give us any value for 9 items for bidder 2. The best SCW that such WDPs based on DQ responses (and raised DQ responses) can achieve is thus 100, which results in an efficiency of 100
184.24 x 54.28%.
After this concrete intuitive example, we give the general proof. Let n 2, m = 1, max(2. :) < o1 E N, (1) = of 21, 5 E (0, min(0.5, <)), (2(x)= = (c) 5)zı + à पी. Here, the unique efficient allocation would assign item to bidder and
the remaining 11 1 items to bidder 2, resulting in an SCW of 01 (1) + (2 - 1) = of + (c1 (c - 1) + - (c - 1)2.
However, there is no DQ p E Rgo that bidder 2 would answer with xp(p) (c1 1). due to the strict convexity of ey:
If the price p is below rale1) (c1 - 6) + ci
bidder 2 will answer with (p) (ci):
if the price p is exactly v2(e)) bidder 2 will answer with either xp)p) = (cz) or (p) = (0);
if the price is higher than (01)) bidder 2 will answer with (p) = (0).
Therefore, the WDP cannot assign C1 1 items to bidder 2 if only DQs were asked, no matter how many DQs were asked. Raising the bids for those bundles would also not help, because this would still not give us any value for C₁ 1 items for bidder 2. The best SCW that such WDPs based on DQ responses (and raised DQ responses) can achieve is thus of. which results in an efficiency of --- < 50% + e. Since there are infinitely many possible choices of 8 E (0, min.0.5, e)). the proof is concluded. (Note that there are infinitely many other scenarios that were also suitable for this proof.)
Thus, every method that only asks DQs (e.g., CCA or (Soumalias et al., 2024c)) will result in inefficient allocations even in the limit of infinitely many iterations in the case of certain value functions (even if raised clock bids are added in the supplementary round).
Remark D. The issue highlighted in Theorem 3.2 also arises in practical settings. In Section 6, we experimentally show that in the most realistic domain, MRVM, the final 50 DQs of ML-CCA (Soumalias et al., 2024c), the current SOTA DQ-based ICA, only increase efficiency by 0.3% points. If the bidders also report their true values for all bundles they requested, this only causes an efficiency increase of less than 0.2% points. In contrast, for MLHCA, the last 30 VQs cause an efficiency increase of over 1.8% points. For the other domains, we see qualitatively similar picture in Figure 1.
16We want to emphasize that Theorem 3.2 holds for any combination of DQs, even combinations consisting of all (unaccountably many) possible DQs (i.e.. DQ for every price vector in (0)"). For these auction instances, even an oracle with complete knowledge about everything and infinite computational abilities could not ask any combination of DQs resulting in more efficient allocation (see Remark 1.1 Theorem 3.2 implies that no DQ-only mechanism can guarantee an efficiency above 55%.
25

---

Prices, Bids, Values: One ML--Powered Combinatorial Auction to Rule Them All
Remank 1.13. The proof of Theorem 3.2 is not related to Proposition 3.3. Theorem 3.2 also holds if you allow an oracle with complete information to choose any set of DQs (i.e., without using any of the harmful DQs from Proposition 3.3). Theorem 3.2 and Proposition 3.3 are two distinct orthogonal problems of DQs. For example, Theorem 3.2 also holds when the clock-bids raised heuristic is used, while Proposition 3.3 does not hold if the clock-bids raised heuristic is used." !7
In Theorem 3.2, we showed that a DQ-based auction cannot guarantee full efficiency. Intuitively, the driving force behind this limitation is that despite the broad information that DQs provide, they cannot fully reveal a bidder's value function. In Example 1, we show practical example where both linear and non-linear value functions would result in exactly the same response to any DQ by the bidder. However, the same is not true for VQ-based auction, leading to the following result:
Lemma D.14. Asking each bidder IT Cj different VQs guarantees that the allocation will be efficient. This result holds true if DQs are added to the auction.
Proof. If the bidders give us their values for all possible bundles, then we have access to their complete value functions. Then the WDP equivalent to optimizing the SCW.
Thus, (Weissteiner& & Seuken, 2020; Weissteiner et al., 2022b;a; 2023) and the hybrid method that we introduce in this paper have a guarantee to converge to an efficient allocation in the limit of infinitely many iterations." 18
The number IT Cj in Lemma D.14 is obviously just worst-case bound for the worst possible querying strategy. In theory, it would be sufficient to ask each bidder only one VQ vz(a)) corresponding to the efficient allocation a" to achieve 100% efficiency. However, in practice, the auctioneer does not know a'. Our experimental results displayed in Table show that our method MLHCA usually finds the efficient allocation after much fewer queries than I Cj. And once each bidder answers the VQ uy (a)), ), further queries cannot reduce the efficiency anymore.
m
To better understand the importance of asking VQs, we directly compare Theorem 3.2 and Lemma D.14. While Theorem 3.2 proves that there exist auction instances where even an oracle with full information cannot find any combination of DQs that results in a decent efficiency above 55%, we know that an oracle can always find a single VQ that directly results in a perfect efficiency of 100%. Theorem 3.2 proves that even without any prior information, asking at most [ Cj arbitrarily stupidly chosen different VQs always results in 100% efficiency, while Theorem 3.2 proves that even asking infinitely many arbitrarily smartly chosen DQs can result in catastrophically bad efficiencies below 55%. In practice, we neither have full oracle information nor can we afford to ask L==1 Ej stupidly chosen different VQs; however, our experiments show that a few VQs chosen by our MLHCA usually result in very high efficiencies.
m
D.3. The Advantages of Combining DQs and VQs
DQs are Cognitively Simpler Than VQs Early in the Auction. All ML-powered, VQ-based ICAs in the literature begin by asking bidders their values for uniformly at random selected bundles to initialize the MI. models. In contrast, the SOTA ML-powered DQ-based approach (Brero & Lahaie, 2018; Brero et al., 2019; Soumalias et al., 2024c) starts by asking bidders for their preferred bundles at low initial prices that gradually increase over rounds. From a practical standpoint, it is nearly impossible for bidders to accurately assess VQs for randomly chosen bundles, whereas responding to DQs with low prices is far easier."* As the auction progresses and the bidders' ML models become more accurate, VQ-based ML-powered ICA can ask targeted VQs that align better with bidder interests, making them easier to answer. 20 See Appendix D.5 for an extended discussion.
"When the tock-bids raised heuristic used, there are no harmful DQs (i.e., every further DQ can only increase the SCW, but never decrease the SCW). Even then, Theorem 3.2 shows that any arbitrary (possibly infinite) set of DQs cannot reach more than 55% efficiency for the auction instance in the proof of Theorem 3.2 for example.
Note that all these methods always enforee to ask new VQ in any round, i.c., the WDP suggests to ask bidder a VQ for bundle she was already asked for in a previous round, then we solve a constrained WDP instead with the constraint that this bidder is not allowed to he asked for any previously asked bundle again.
IIn the example from Footnotes and 14, imagine being asked your value a bundle of 30 frying pans and 500 coconuts. It's hard to assess such a random combination. Now, imagine shopping at a supermarket with a 50% discount across all items; it's easier to determine what items you want under these conditions.
Continuing with our example, imagine being asked for the value of ingredients specifically for a strawberry cake in one iteration and for a blueberry cake in the next. If your goal is to hake a cake, these targeted VQs are much easier to respond to.
26

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
DQs are More Effective in the Early Stages of the Auction. Initially, the auctioneer lacks knowledge of which bundles align with bidders' interests. Beginning with DQs allows the auctioneer to gather early insights about the bidders' preferences over the whole bundle space, facilitating the use of more targeted queries later on. This practice is well-established in the combinatorial auction community. For instance, the initial DQ phase in the CCA is often referred to as a "price discovery phase" (Ausubel et al., 2006). We argue that the same concept holds even in -o--powered auctions. Our experiments in Section 6 confirm that DQ-based approaches (e.g,, ML-CCA (Soumalias et al., 2024c)) outperform VQ-based approaches (Weissteiner & Seuken, 2020; Weissteiner et al., 2022b;a; 2023) during the early rounds of the auction. However, as suggested by Theorem 3.2 and Lemma D.14, VQ-based approaches eventually surpass DQ-based mechanisms in later iterations.
A key contributing factor as to why VQ-based MI-powered approaches perform better than DQ-based approaches is that they can take into account the WDP, i.e., the downstream optimization problem that will determine the final allocation. 21 In contrast, responses to a single DQ often lead to over-demand for certain items or leave some items unassigned (under- demand). In Example 1, bidder 2 lacks information to know that she should bid for 9 items. Only the auctioneer, having information from all bidders, knows that assigning items to bidder 2 would complement bidder I's preferences. The auctioneer can leverage this aggregated knowledge by asking bidder 2 VQ for 9 items, whereas DQs alone would not provide this opportunity.
Example 1. In the example from the proof of Theorem 3.2, after sufficiently many DQs have been asked, a single VQ would suffice to increase the social welfare from x 56.45% to 100%. MLHCA would ask this VQ in its first VQ round, provided that enough DQs had been asked beforehand, as we explain in the remainder of this example. 01 can be very precisely reconstructed from DQs p = c (which responded by x = (1)), p = 100 c (which responded by x = (1)), and p = 100 + E (which is responded by x (0)). The last two DQs reveal that 100 E S ia (1) S 100 + e. And the first DQ reveals that U1 (z) - e1 (1) S (x 1)e for any 1. Combining these information reveals that 21 S 1001. + 10e and with the help of monotonicity these 3 DQs reveal that 01 2 1001, 21 - e. So, we can reconstruct the true 81 up to 10c. 94++
10 (which is responded by x = 0), we can only reconstruct that 02 < - (.) and that 12 (10) 2 94 - e. E.g., the linear function 94
For bidder 2, from DQs p = 94-c (which is responded by 10) and
TO (-) would not contradict any possible DQ response from bidder 2. Our ML algorithm should not have any problem with estimating U1 sufficiently well. If additionally, our ML algorithm estimates U2 (approximately) as this linear function 10 (-), then the WDP would directly assign item to bidder I and 9 items to bidder 2, which is the efficient allocation. In theory, MVNNs could also express functions that achieve 0 training loss on all DQs for bidder 2 but do not result in efficient allocation. However, these functions would be highly non-linear and for many NN architectures it is shown that they prefer functions which are in certain sense close to linear (Heiss et al., 2019; 2023; 2021; Heiss, 2024). In Appendix C.1 we explain, why our MVNNs would learn a linear approximation of 02. Therefore the WDP would result in the efficient allocation in this example.
Remark D.15. Note that this example is not pathological. In Section 6, we will show that in realistic domains using 40 DQs and only 2 VQs (I bridge bid 1 ML-VQ), our MLHCA can achieve higher efficiency than the SOTA DQ-based mechanism using 100 queries.
Our MLHCA is the first auction to integrate both a sophisticated DQ and VQ generation algorithm. By leveraging insights from auction theory and starting with DQs before transitioning to VQs, MLHCA achieves state-of-the-ar efficiency in all rounds and demonstrates significantly improved final efficiency across all domains compared to the current tfateoo--the-ar
Moreover, we argue that the combination of DQs and VQs is particularly powerful for learning bidders' value functions, as the information from these two query types complements each other nicely (see Appendix E).
D.4. Why One Should Ask DQs Before VQs and Not the Other Way Around
We neither want to claim that DQs are more informative or better than VQs, nor the other way around. We strongly believe that DQs are more informative and practical at the start of the auction, while we also believe that VQs are more informative and more effective at the end of the auction. We have multiple different reasons to believe so, adding up to very large effects in our experiments in Appendix G.9. In the following paragraphs, we' 'll quickly summarize these reasons.
By definition, all the bundles in VQ form a feasible allocation. Furthermore, VQs typically allocate (almost) all items to bidders, they maximize the estimated social welfare. The MVNN architecture ensures monotonicity in the estimated value functions. If the estimated value functions were strictly monotonic, the solution to the MIIPs determining the next VQ would always allocate all items.
27

---

Prices, Bids, Values: One ML-Pooerred Combinatorial Auction to Rule Them All
Reason 1: Congnitively Simpler. While our experiments do not measure the cognitive load on bidders, we already argued in Appendix D.3 that at the early stage of the auction, answering VQs is considered to be extremely difficult by practitioners, while starting ICAs with DQs is and ending them with value-bids is very common in practice. See Appendix D.5 for an extended discussion.
Reason 2: Global Exploration vs Local Exploitation. At the start of an auction, it is not known which regions of the bundle space could be particularly relevant for a bidder. DQs provide very quickly a coarse but global overview of a bidder's s value function. This overview remains very valuable for all later iterations in deciding which regions are worth exploring and which are not. In contrast, the values of some random bundles (which are with high probability far away from the relevant region of the bundle space for large, combinatorial domains) will become almost irrelevant during the later iterations of the auction. This is why DQs are more valuable at the start of the auction. However, towards the end of the auction, entirely the opposite is true; the MI. models already have lots of information the bidders' value functions and therefore can pinpoint which regions of the bundle space are relevant for which bidder. Therefore very precise local information in exactly those regions becomes extremely valuable, and VQs can ask for exactly this kind of information, whereas the coarse, global information of DQs brings almost no additional value at this point. 22 Theorem 3.2 and Example 1 illustrate this point mathematically. They show scenarios in which it is impossible for DQs to provide any additional information on the bidders' value functions, since infinitely many very different value functions with the same concave envelope would result in exactly the same DQ reply, making these value functions indistinguishable from any DQ. At the same time, this information would be crucial for achieving an acceptable efficiency, and those value functions are clearly distinguishable using VQs. In this example, the first ML-VQ after sufficiently many DQs would directly deliver the needed information to almost double the efficiency. And, in contrast to DQs, Lemma D. 14 shows that, asking sufficiently many VQs can always exactly recover the true value function.
Reason 3: VL-VQS Result in Compatible Bids, While DQs Do Not. Each bidder answers DQ with requested bundle. However, combining all these bundles usually does not result in a feasible allocation that allocates all items. In fact, this is only the case if linear clearing prices have been found, which is extremely challenging in realistic domains. In fact, in the most realistic domain, the SOTA approach of Soumalias et al. (2024c) clears 0% of the instances tested, and it is not even known whether linear clearing prices exist. For the auction in Example I, linear clearing prices provably do not exist, making it matherattically impossible to find clearing prices via DQs. However, for our ML-VQs, our algorithm first selects promising feasible allocation (that allocates all items) and then asks each bidder her value for the bundles she receives in that allocation. This implies that for an ML-VQ round, the bids of all the bidders together result in feasible allocation. In the early rounds of an auction, the efficiency of the intermediate WDPs are completely irrelevant, as they are not final. The goal of the first rounds is mainly to gather relevant information for later rounds. Therefore, it does not hurt that the bids from the first DQ-rounds are not compatible. However, exactly the opposite is true in the last rounds of the auction. For example, in the very last round, improving the models of bidders' value functions does provide any value anymore, since these models are not used anymore after the last round. However, obtaining a highly efficient feasible allocation is the number one goal at the end of the auction. Theorem 3.2 and Example 1 show that in many scenarios, even if one had perfect information all the value functions, no combination of DQs can obtain bids that result in feasible allocation with an acceptable efficiency. In contrast, in any possible scenario, a single ML-VQ would always result in feasible allocation with 100% efficiency if one had perfect information on all the value functions. And our experiments show that after 40 DQs (and 1 bridge bid), we often have already sufficient information to directly obtain 100% efficiency after a single ML-VQ, and even if we do not directly achieve 1 100% efficiency after the first ML-VQ, we usually achieve already a very good efficiency a few ML-VQs later.
We think that Reason 1, is the most relevant for implementing practical auctions while being completely unrelated to experimental results. We hypothesize that Reasons 2 and 3 are the main explanations of our experimental results and explain why adding DQs after 80 VQs does not bring any efficiency gains in our experiments in Appendix G.9. Note that both Reason and 3 consist of 4 subreasons each. Each of them consist of an advantage of DQs in early rounds, a disadvantage of VQs in early rounds, a disadvantage of DQs in late rounds and an advantage of VQs in late rounds. They all point in the same direction to first ask DQs and then ask VQs afterwards. While we did not find a single reason to switch the order, we found even further (maybe more subtle) reasons to start the auction with DQs.
For strong empirical evidence of this diminished value of DQs, see Appendix G.9
28

---

Prices, Bids, Values: One ML-PPowered Combinatorial Auction to Rule Them All
Reason 4: At the Start DQs Provide Better Bids and Better Local Information Than VQs Reason 2 says that at the start of the auction, mainly global information is relevant, and Reason 3 says that at the start, one cares mainly about learning the value functions rather than identifying bundles relevant for the WDP. However, even at the start it is beneficial to additionally obtain useful local information and relevant bids. Proposition 3.1 is telling us that at the beginning of the auction DQs even provide more relevant local information than random VQs, especially for high dimensional bundle spaces. While random VQs result in bids for random bundles, DQs always result in bids for bundles that are at least to some extent aligned with the bidders' interests, providing useful local information as well. Figure 6 in Appendix G.9 suggests that the dimension of GSVM and LSVM high enough for this argument to hold, but the 3 dimensions of SRVM are not enough.
D.5. Intuitive Arguments Why DQs are Cognitively Simpler Than VQs Early in the Auction
This subsection offers an intuitive and informal discussion, grounded in common sense and informed by conversations with practitioners, in contrast to the more formal and scientifically rigorous analysis found throughout the rest of the appendix and the main paper. While answering DQ may appear computationally hard in theory"? real-world bidders often do not need to compute the precise value of any bundle to answer a DQ. Instead, they can make comparisons based on relative value. For instance, a bidder may know that certain licenses are not worth their prices and can confidently exclude them without quantifying by how much. This is sufficient to give an exact answer to a DQ
For example, the experimental setting in Scheffel et al. (2012a) does not optimally reflect this reality, In their study, participants were given explicit formulas for their value functions. In that setting, it is relatively easy to evaluate the value of any bundle (i.e., to answer a VQ), but computationally hard to solve the optimization problem required to answer a DQ. However, in actual spectrum auctions, bidders do not have such formulas. Especially for bundles outside their business model, it can be very difficult to estimate values at all. In contrast, bidders often have strong intuition about how different bundles compare to each other, which is exactly what DQs require. In this sense, real-world bidders are often better equipped to answer DQs than OQp-oppo to the assumptions in Scheffel et al. (2012a).
To further illustrate, imagine a shopper who only visits a supermarket once a year and must buy enough food to survive the year-just as telecoms acquire spectrum licenses only in rare, infrequent auctions. may be difficult for the shopper to assign an exact monetary value to the minimum amount of food they need. Yet, when comparing bananas and apples with price tags, it's relatively easy to decide which one to buy more of, based on their relative value. Making this choice corresponds to answering a DQ and does not require the bidder to give absolute values.
In established real-world spectrum auctions, such as the CCA, the auction begins with DQs and only later allows bidders to report values for additional bundles in supplementary round (Ausubel et al., 2006). This structure reflects the widely held belief among practitioners- and one we strongly share-that VQs are more difficult to answer at the beginning of an auction than toward the end, when both bidders and the auctioneer have developed better understanding of relevant bundles and prevailing price levels. While this hypothesis is well aligned with practical auction design, there is still limited scientific work formally analyzing the cognitive demands of DQs versus VQs. We believe future research could provide a more refined and nuanced understanding of when and why each type of query is cognitively easier or harder to answer- innightss that could further inform auction design in practice.
While the worst-case computational cost of answering DQ is exponential, our algorithm computes near-optimal answers millions of times per auction in under 0.2 seconds per query (see Line 4 in Algorithm 4). Although real-world value functions may be more complex than our MVNN approximations, the main bottleneck in practice is not computation but uncertainty in the hidder's 's own value estimates.
29

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
E. Details on Section 4
In this section, we introduce our mixed training algorithm and provide experimental evidence supporting our theoretical analysis from Section 3. Specifically, we demonstrate the learning benefits of initializing auctions with DQs rather than VQs and highlight how combining DQs with VQs leads to superior learning performance.
E. Training Algorithm Detailed Description
In this section, we provide the details on our training algorithm to combine DQs and VQs. To leverage the advantages of both DQs and VQs, we propose straightforward two-stage training algorithm. In each epoch, the ML model is first trained on all DQ responses using the loss function from (Soumalias et al., 2024c) (Lines 4 6). The main idea behind this loss, is that for each DQ. optimization problem is solved to predict the bidder's utility-aximizingg bundle at the given prices, treating her ML model as her true value function. In case the predicted reply disagrees with the bidder's true reply, the loss the difference in predicted utilities between these 2 bundles, given the current prices. Next, in each epoch, the model is trained on the VQ responses using standard regression loss (Lines to 10). This mixed approach ensures that the model benefits from both the broad information of DQs and the precise value information from VQs.
Algorithm 4: MIXEDTRAINING
Input Demand query data R (f),("",, ".""""'""" pr)) D Value query data R { { (1)))) Epochs T e N, Learning Rate 7 > O, Cardinal loss function F (e.g., least-square loss) b weissteiiee ez al. (2023, S.3.2)
1 Oo + init mMVNN
2 for / = 0 1o T - 1 do
for 1 R. do
Venand responses for prices
4
Solve a. (p") E Bargmax (T - (p",x) if 2f (p") # 2 (y²) then
mMNVNN is wrong Add predicted usility
L(0.) +
(MM - (p" (x")))) (M - (6' (,))))))))**
difference to loss
0141 - 02 Y( (0)
SGD step & Valuu Queries Cardinal Loss on SGD step
8
for 1= 1 to T. do
L(O,) ((M (zf) ) (x+))
10
0c+1 - 7( (0))e
return Trained mMVNN M
Remark E.1 (Computationally efficient implementation of Algorithm 4). In practice, running Algorithm 4 exactly the way it printed here would be quite slow. Our actual implementation does not rerun Line 4 every epoch, but reuses # (v") for couple of epochs. This does not violate the bidder's preference due to the positive part in Line In this way, we can significantly speed up the training algorithm.
This training algorithm can be interpreted as a stochastic gradient descent on the loss function
[4(0) = Σ (MP( (x)) (M (. -(()))))) Σ (a))
where and F is loss function (c.g., Fl. 0) (y ;) and (p") E arg max M (x) (p' 2)).
In practice, can obviously use modifications of this algorithm such adding regularization or momentum other typical deep learning techniques.
E.2. Experimental Analysis
In this section, we demonstrate the learning benefits of initializing auctions with DQs rather than VQs and highlight how combining both query types leads to superior learning performance.
We conduct the following experiment: We perform hyperparameter optimization (HPO) to train an mMVNN for the most critical bidder type in the most realistic domain- the national bidder in the MRVM domain. In Appendix E.3 we present the same experiment for all other domains. Our HPO procedure is the following. For a single bidder of that type, we generate three distinct training sets:
30

---

Prices, Bids, Values: One ML--Powered Combinatorial Auction to Rule Them All
OPTIMIZATION TRAIN POINTS
R
KT
MAE SCALED
R
METRIC
VQs
DQS
T.
Tp
T
T5
T.
Tp
T
Tp
R ON V,
20
40
0.84
0.42
0.79
0.80
0.037
0.044
0.84
0.80
60
0
0.73
-
10.07
0.68
0.64
0.052
0.236
0.74
0.20
0
60
0.24
-3.07
0.77
0.77
0.103
0.128
0.83
0.76
R ON V/P
20
40
0.82
0.01
0.79
0.80
0.041
0.062
0.84 0.83
60
0
0.76
33.40
0.72 0.62 0.049
0.141
0.77
0.05
0
60
0.05
- 66244
0.78 0.72 0.103
0.154
0.84
0.69
Table 3: Learning comparison of training only on DQs, only on VQs, or on both. Shown are averages over ten instances for the winning configuration of each HPO procedure. Winners are marked in gray. 1. The first training set contains 40 DQs simulating 40 CCA clock rounds, along with 20 VQs for bundles chosen uniformly at random.
2. The second training set consists of 60 DQs, simulating 60 CCA clock rounds, with no VQs.
3. 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 (V,), 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 200 randomly generated price vectors { where each item's price drawn uniformly between 0 and three times its average value for that bidder type. V, evaluates generalization performance over the entire bundle space, while Vp focuses on the bidder's atility-maximizing bundles for various prices.
For each HPO configuration, we average the performance across 10 bidders of the same type. The best-performing configuration for each validation set is selected based on the coefficient of determination.
For the selected configurations, we evaluate performance on 10 separate test seeds representing new bidders, generating the test sets T. and Tp in the same way as for the validation sets. For each test set, we report the coefficient of determination (R²), Kendall Tau (KT), scaled Mean Absolute Error (sealed MAE) normalized with respect to the average value of bundle in that domain and R2 centered (R²), shift invariant version of R2, An R2 value of indicates that the ML model has learned the bidder's s value function perfectly, up to constant shift. By comparing R with the standard R², we can assess, for the bundles tested, the shift magnitude in the learned value function. 24
Each HPO procedure was conducted under identical conditions, including the same test instances, random seeds, hyperpa- rameter search space, and total computation time. For more details on the HPO process, see Appendix G.3.
Table 1 shows that training on a mixture of DQs and VQs consistently outperforms training on either query type alone. This is evident across all metrics, and especially for the maximi-ma bundles of test set Tp. where mixed training yields almost three times lower MAE compared to other approaches.
Furthermore, the mixed-query model was the only one able to approximately learn the correct mean value for both validation sets, as reflected by the small difference between its R2 and standard R². In contrast, models trained solely on DQs or VQs showed a much larger discrepancy between these two metrics for at least one of the validation sets. As explained in Section 3, when training only on DQs, the model only has relative information about bundle values and thus the value function is not uniquely identifiable, preventing the network from learning accurately. On the other hand, models trained solely on VQs experience distributional shift between the two test sets one set focuses on utility- meliiitymaimizzingggg bundles, while the other contains bundles selected uniformly at random. Since the VQ training set is drawn uniformly random and lacks mailit--maxmmiiigg bundles, the model fails to capture the bidder's 's value function for these critical bundles.
In Table we observe that the models trained only on DQs exhibit much better generalization performance in the bundles of To than the models trained on random VQs, despite of their lack of absolute value information. The reason for the better generalization performance is the strong distributional shift between the bundles of the two sets. But from an allocative value perspective, the bundles in the set Tp are those for which the bidders have high utility, and thus value. Thus, this is the critical
Note that this shift is not perfectly constant as (m) MVNNs map the zero bundle to zero Note that at the start of Mo-pooeeed, VQ-hased auction, the MI. models are not yet sufficiently accurate, preventing the auctioneer from asking VQs for utility- or maximizing bundles.
31

---

Prices, Bids, Values: One ML-PPowered Combinatorial Auction to Rule Them All
area of the allocation space where the auctioneer wants the models to perform well. This gives strong empirical motivation as to why starting the learning process with DQs is more effective than starting it with VQs. In Section 6 we showed that the efficiency after the first ML-powered VQ is, across all domains, much higher for the model trained on DQs compared to the one trained on random VQs. The reason behind this improvement is precisely the fact that the DQ-trained models have learned a better approximation of the bidders' value functions in the most critical part of the allocation space. In fact, the learning performance is so much better that, in two out of the four realistic domains tested, a single ML-powered VQ in the DQ-trained networks suffices to achieve better auction efficiency than the VQ-trained networks using 60 ML-powered VQs.
Comparing the models trained only on DQs with random VQs in Table provides strong empirical evidence of the two main, orthogonal learning advantages of starting ML-powered auction with DQs compared to random VQs. The first advantage is that CCA DQs provide global information about the bundle space, which promotes exploration of the allocation space. This global information that DQs provide is evident from the higher KT that the DQ-trained network can achieve across both test sets compared to the VQ-trained one. The reason for this increased performance is that, as explained in Section 3, DQs provide global relative information about the entire allocation space.
The second learning advantage of starting an auction with CCA DQs is that they provide particularly much information about the critical, high valued areas of the allocation space right from the start. This is evident from the fact that the models trained only on DQs exhibit much better generalization performance in the bundles of Tp than the models trained random VQs, despite their lack of absolute value information. The reason for the better generalization performance is the strong distributional shift between the bundles of the two sets. But from an allocative value perspective, the bundles in the set T are those for which the bidders have high utility, and thus value. Thus, this is the critical area of the allocation space where the auctioneer wants the models to perform well.
These two learning advantages are so critical that, as we will demonstrate in Section 6, the efficiency gains after the first MI-powered VQs is, across all domains, much higher for the model trained on DQs compared to the one trained on random VQs. In fact, the learning performance is so much better that, in two out of the four domains, our hybrid auction (Section 5) using just two ML-pooered VQs, following training on 40 DQs, achieves higher efficiency than the SOTA VQ-based mechanism using 40 random VQs and 60 ML-powered VQs.
In Figure 3, we present prediction vs. true value plots for the rop-performing configurations with respect to R² on V, from Table We compare the model trained on 40 DQs and 20 VQs against the one trained on 60 VQs, corresponding to the first and second rows of Table 1. Bundles from Te are represented by red circles, while those from Tp are shown in blue. For bundles in Tp. we also plot their inferred values, reflecting their price when the bidder requested them.
In Figure 3a we observe that the model trained solely on VQs consistently under predicts values for bundles in Tp- Furthermore, there is a very large spread in the predicted values of these bundles. These bundles are out of distribution for the network, and thus it cannot generalize to them. If we examine the inferred values for the same bundles, we observe a substantial deviation from the true diagonal. The vertical distance between each bundle's inferred value and the true diagonal line corresponds to the bidder's utility when requesting that bundle the quantity she is maximizing. In contrast, as shown in Figure 3b, the model trained on the mixed dataset is able to place the bundles of Ty in an almost perfect parallel line the true diagonal, and with much smaller shift. These bundles not out of distribution for that network, which means it can perform better. For the bundles of T., we observe that the predictions of both models are centered around the true diagonal, indicating that both networks have learned the correct mean value. However, again we can observe that for the network trained on the mixed dataset, its predictions on To are again more tightly clustered in a line around the true diagonal, as was also suggested by the stronger MAE and KT in Table 1. These observations illustrate the powerful synergy between DQs and VQs. The global, relative information provided by DQs enables the network to align its predictions roughly along a consistent
forming parallel line to the true diagonal. The absolute value information from the VQs then fine- tunes this alignment, effectively positioning the line exactly on the true diagonal, ensuring the predicted values match the true values accurately.
E.3. Learning Experiments for Other Domains
In Tables 4 to 6 we present the results of the learning experiment of Appendix E.2 for all additional domains.
Across all domains, the network trained only on DQs demonstrates the worst generalization performance on the dataset T,.. This is primarily due to two factors: the absence of absolute value information that VQs provide and the distributional shift between T, and Tp with the DQ training data being more aligned with Tp-
32

---

Prices, Bids, Values: One ML-PPowered Combinatorial Auction to Rule Them All
DQ validasion
IX, validation DQ validation MN for VO valication
NN Ri for VQ varidtton
Predictions
Predictions
True Values
True Values
(b)
Figure 3: Comparison of scaled prediction true values for an mMVNN trained with different query types for the national bidder in the MRVM domain. (a) Training with 60 demand queries. (b) Training with 40 demand queries and 20 value queries.
The performance of the network trained solely on VQs varies by domain. In the GSVM and SRVM domains, the learning task is relatively easy, as indicated by the already strong performance of previous ML-powered ICAs. In these domains, the networks trained only on VQs perform well across both test sets (Tables and 6). However, in the more challenging LSVM domain domain--smillnne similarly to the MRVM domain discussed in Appendix E.2 the network trained exclusively on VQs performs well the T, test set, which contains points from the same distribution as its training data, but performs worse the maximizing bundles of Tp compared to the network trained on both query types.
This inferior learning performance on the critical dataset Tp explains why MLHCA outperforms pure VQ-based ML-powered ICAs, such as Weissteiner et al. (2023); Weissteiner & Seuken (2020), in the LSVM domain.
OPTIMIZATION TRAIN POINTS
R²
KT
MAE SCALED
R
METRIC
VQs
DQS
T,
T
T
T
T.
Tp
T,
R² ON V,
20
40
0.96
0.95
0.90
0.94
0.07
0.12
0.96
0.98
60
0
0.99
0.98
0.96
0.98
0.03
0.05
0.99
0.98
0
60
0.79
0.97
0.83
0.94 0.04
0.02
0.91
0.98
H ON Vp
20
40
0.96
0.99
0.91
0.96 0.07
0.04
0.97 0.99
60
0
0.99
0.98 0.96
0.98 0.03
0.02
0.99
0.98
0
60
0.79 0.97 0.83 0.94 0.13
0.05
0.91 0.98
Table 4: Learning comparison of training only on DQs, only on VQs, or on both for the GSVM domain.
33

---

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
OPTIMIZATION TRAIN POINTS
R²
KT
MAELCALED
R
METRIC
VQs
DQS
T.
Tp
T
T
Tr
Tp
T.
Tp
R2 ON V.
20
40
0.38
0.88
0.65
0.80
0.46
0.33
0.44
0.91
60
0
0.67
0.80
0.75
0.81
0.30
0.46
0.67
0.87
60
-120
0.99
0.80
0.84
1.10
0.11
0.46 0.99
Rº
0.38
0.46
0.33
0.44 0.91
60
0.65
0.82
0.81
0.88
0.25
0.38
0.66 0.87
60
-2.97 0.96 0.77 0.85 1.51
0.22
0.42 0.97
Table 5: Learning comparison of training only on DQs, only on VQs, on both for the LSVM domain.
OPTIMIZATION TRAIN POINTS
R²
KT
SCALED
R
METRIC
VQs
DQs
T.
т
T.
T
T.
T
T.
Т
R2 ON V,
20
40
1.00
0.89
0.97
0.90
0.02
0.03
1.00
0.93
60
0
1.00
0.96
0.99
0.97
0.00
0.01
1.00
0.97
60
0.93
-0.13
0.96
0.92
0.11
0.10
0.97 0.94
R Vp
1.00
0.94
0.98
0.92
0.01
0.02
1.00 0.94
60
1.00
0.96
0.99
0.97
0.00
0.01
1.00
0.97
60
0.91
0.02 0.96 0.86 0.12
0.09
0.95 0.89
Table 6: Learning comparison of training only on DQs, only on VQs, or on both for the SRVM domain.
34

---

Prices, Bids, Values: One ML-Powerre Combinatorial Auction to Rule Them All
F. Detailed Auction Mechanism
Algorithm 5: MLHCA(QEC) Q Q" Qraad)
Parameters: :eneeterr::Qeea QCCA, Q SPV,QVO
QVO, Quound and π
1 R + (f)))1
2 R000 <- (0)
for 1,,.. C do
braw Q
initial prices
4
p" 4 (C
5
foreach i E N do
Initial demand quezy responses
R + R
U (p)))) . Qeea + Qoe do
7
for = Qucs + ,,.,
MML powered DQs
8
foreach E N do
M MIXEDTRAINING )
D'llgorihhm
D' -NEXIPRICE((MM) =))
Appendix A.3
11
foreach i E N do
Demand query responses for p
12
R2 t R u (p=()")))))
if E (x) 13
Vj E M then
b Narkat-dllarinn
14
a' RR R) (z) (p") T)==1
final allocation clearing allocation
Calculate payments TI (1P R0 t- (1e00 n 1)
15
return a" (1e00 R²0) and T( ( R22)
16
foreach i do R. 4- R, U [(a) (R), sa (R)))}
Bridge
18
for QocA + Q + 2..... ... Q Q + Q
Dil-ppwered vos
20
foreach E N do
21
M MIXED (R, 2)
AAggorichm 4 Query Main Bconemy
22
if r7Qummu 0 then
foreach E N do
24
x' (H) + arg max FFFEEE R EVEN Mf
b. Find predicted optimal allecasion
25
2 (R) <- (R)
26
else
bi Overry Marginal Rooromy
foreach E N do N 4 draw uniformly at random Qraund bidders from N {t)
28
29
x' (R) + arg max TET En EvER M?(
Find predicted optimal allocation in marginal
economy
30
of (H) + (H)
foreach i N do
Value query respenses (R)
32
R. + R₁ U {a (R), ((((()))))
33 Calculate final allocation a" (R) as in Equation (3)
Calculate payments x (())
pB.g., VOG (Appendix B)
return a" (R) and (R)
In this section, we present detailed description of MLHCA. The full auction mechanism is presented in Algorithm 5. In Lines 3 to 6, we generate the first QUCA DQs using the same price update rule as the CCA. In each of the next Q ML-powered rounds, we first train, for each bidder, an mMVNN on her demand responses (Line 9). Next, in Line 10, we call NEXTPRICE (Soumalias et al., 2024c) to generate the next DQ based on the agents' trained mMVNNs (see Appendix A.3), If MLHCA has found market-clearing prices, then the corresponding allocation is efficient and is returned, along with payments =(t) according to the deployed payment rule (Line 16). If, by the end of the ML-powered DQs the market has not cleared we switch to VQ rounds. In the first VQ round (Line 18) we ask each bidder for her bridge bid (see Definition D.8). As proven in Lemma D.9, this single VQ ensures that the MLHCA's efficiency lower bounded by the efficiency after just the DQ rounds. The difference in the algorithm description compared to the version presented in Section 5 lies in the VQ rounds. Specifically, we make use of marginal economies. Once every Qroudd VQ rounds, for each bidder, we query her value for the bundle she receives in the predicted optimal allocation (based on all ML models), under the constraint that the bidder in question receives a bundle for which she has not been queried in the past (Lines 22 to 25). This as described in Section 5. But in the other Qramd rounds, for each bidder, we query her value for the bundle she receives in the predicted optimal allocation based only on the models of the non-marginalizae bidders (Lines 26 to 30). Each time, for each bidder,
35

---

Prices, Bids, Values: One ML-Pooeered Combinatorial Auction to Rule Them All
marginalize Q bidders uniformly random without replacement. The marginal economies have been designed to improve the incentive properties of the auction (for detailed analysis, see Brero et al. (2021)). Similar all papers in this line of work, e.g. Brero et al. (2021); Weissteiner et al. (2022a; 2023), we set Q in all of our experiments. The final allocation and payments are then determined based on all reports (Lines 24 to 25). Note that ML-CCA can be combined with various possible payment rules л R), such as VCG or VCG-nearest.
36

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
G. Experiment Details
Our code is available on GitHub: http:///wwpggg.ttooo../oo///eete
G.1. SATS Domains
In this section, we provide a more detailed overview of the four SATS domains, which we use to experimentally evaluate MLHCA:
Global Synergy Value Model (GSVM) (Goeree Holt, 2010) has 18 items with capacities e = 1 for all j E {l...., 18), 6 regional and 1 national bidder. In this domain the value of package increases by a certain percentage with every additional item of interest. Thus, the value of bundle only depends on the total number of items contained in a bundle which makes it one of the simplest models in SATS. In fact, bidders valuations exhibit at most two-way(i.e. pairwise) interactions between items.
Local Synergy Value Model (LSVM) (Scheffel et al., 2012b) has 18 items with capacities cj = for j E (1,...,,88) 18).
5 regional and national bidder. Complementarities arise from spatial proximity of items.
Single-Region Value Model (SRVM) (Weiss et al., 2017) has items with capacities ei = 6, c2 14, c3 and 7
bidders (categorized local, high frequency, regional, or national) and models UK 4G spectrum auctions.
Multi-Region Value Model (MRVM) (Weiss et al., 2017) has 42 items with capacities cj E [2,3) for all E (1..... 42]
and 10 bidders (local, regional, or national) and models large Canadian 4G spectrum auctions.
In the efficiency experiments in this paper, we instantiated for each SATS domain the 100 synthetic CA instances with the seeds {101, 200}. We used SATS version 0.8.1.
G.2. Compute Infrastructure
All experiments were conducted on a compute cluster running Debian GNU/Linux 10 with Intel Xeon E5-2650 v4 2.20GHz processors with 24 cores and 128GB RAM and Intel E5 2.80GHz processors with 20 cores and 128GB RAM and Python 3...
G.3. Hyperparameter Optimization Details
In this section, we provide details on our exact HPO methodology and the ranges that we used.
We separately optimized the HPs of the mMVNNs for each bidder type of each domain, using differrent set of SATS seeds than for all other experiments in the paper. Specifically, for each bidder type, we first trained an mMVNN using initial data points the demand responses of an agent of that type during 40 consecutive CCA clock rounds, and her value responses for 30 uniformly at random selected bundles, and then measured the generalization performance of the resulting network on a validation set that consisted of 50,000 uniformly at random bundles of items, similar to V, in Appendix E.2. The number of seeds used to evaluate each model was equal for all models and set to 10. Finally, for each bidder type, we selected the set of HPs that performed the best on this validation set with respect to the coefficient of determination (R²2.. The full range of HPs tested for all agent types and all domains shown in Table while the winning configurations are shown in Table 8.
The winning configurations for both metrics are shown in Table 8.
G.4. Computational Costs and Bidder-Perceived Latency
All experiments were conducted using the compute infrastructure described in Appendix G.2.
The average wall-clock runtime for single instance of MLHCA across the GSVM, LSVM, SRVM, and MRVM domains was 1 day, 12 hours, and 42 minutes; 16 hours and 42 minutes; 11 hours and 6 minutes; and 7 days and 36 minutes, respectively. Each instance ran on a single CPU with 20 or 24 physical cores, as detailed in Appendix G.2 without GPU acceleration. GPUs were incompatible with both our training and query generation implementation.
Considering the substantial welfare gains achieved by MIHCA, we regard these compute costs as marginal. In total, we conducted experiments on over 1,000 realistically-sized instances.
Foror the definition of (m MVNNS with a linear skip connection, please see Weissteiner et al. (2023, Definition F.I)
37

---

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
Hyperparameter
HPO-Ranne
Non-linear Hidden Layers
[1,2,3]
Neurons per Hidden Layer
[8, 10, 20, 30]
Learning Rate
(Ie-4, le-2)
Epochs
[30, 50, 70, 100, 300, 500, 1000]
12-Regularization
(Ie-8, le-2)
Linear Skip Connections
[True, False]
Cached DQ solution Frequency
[1, 2, 5, 10]
Batch Size for VQs
[1,5, 10]
Table 7: HPO ranges for all domains.
DOMAIN BIDDER TYPE
HIDDEN LAYERS
HIDDEN UNITS LIN. SKIP LEARNING RATE ARIZATARIATIOON EPOCHS CACHED SOLUTION FREQ. BATCH SIZE
LSVM
REGIONAL
20
0.001
0.000001
100
20
NATIONAL
30
TRUE
0.0001
0.001
1000
10
GSVM
REGIUNAL
30
TRUB
0.0001
0.001
1000
10
NATIONAL
30
FALSE
0.0005
0.0001
200
10
MRVM
LOCAL
20
TRUE
0.001
0.00001
200
REGIONAL
30
TRUE
0.0001
0,000001
1000
20
NATIONAL
2
20
FALSE
0.001
0.000001
100
5
10
SRVM
LOCAL
10
TRUE
0.01
0,0001
1000
REGIONAL
30
FALSE
0.005
0.000001
500
5
HIGH FREQUENCY
10
TRUE
0.005
0.00001
500
10
NATIONAL.
10
TRUR
0.005
0.00001
1000
Table 8: Winning HPO configurations for R²²
Furthermore, in real-world settings, more than two query rounds are typically conducted within a day. Therefore, the hidder-perceivee latency of our mechanism is not concern.
38

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
G.S. Extended Efficiency Results
In this appendix we compare further competitors including some that use significantly more queries in Table 9. Each profit- max bid (see Appendix G.6) used by some of our competitors actually consists of 1 constrained DQ plus VQ. However, we count each profit-max query as only VQ. Although this counting scheme is strongly in favor of the competitors, in the 3 most realistic domains LSVM, SRVM and MRVM, our method (MLHCA) significantly outperforms the efficiency of any other competitor except those who use substantially more queries. Even those mechanisms that use more queries did not manage to outperform our efficiency in any of the 4 domains.
KIFICIENCY LOss IN %
DOMAIN
MLHCA
BOCA
ML-CCAcuos ML-CCARNO ML-CCArem
CCA
CCAgas
CCAnon
MVNN
NN
FT
RS
GSVM
0.00 0.00
1.77 0.68
1,07 1 0.37
0.00
9.60 + 1:49
6.11
0.00
00.00 2 0.00 00.00
0.00
01.
0.96
30.31 : 1.61
LSVM
0.04 0.07
0.39 + 0:31
8.36 1.70
3.61 0.77
17.44 + 1.60
8.40
00.70
02.91
1.44
0.65
31.73
2.15
SRVM
0.00 + 0.00
0.06 +: 0.02
0.41 0.11
0.07 0.02
0.00
0.37 + 0.11
0.19
0.00
00.23
+ 0.06 01.13
0.22
00.
0.16
28, 28.56
+ 1.74
MRVM
1.81 + 0.57
7.77 +: 0.35
6.91
0.68 1: 0.22
6.32
7.53 4 0.48
7,38
6.82
08.16 2 0.11 09.05 :: 0.53
10.37
=
0.57 18.79 + 1.13
NUMBER OF QUERIES
HDQS
40
0
100
100
100
100
100
100
0
0
#VQs
60
100
1-100
101-200
0
1-100
101-200
100
100
#Qs
100
100
100
101-200
201-300
100
101-200
201-300
100
100
100
100
Table 9: Extending Table 2 by ML-CCAPROFT (which adds 100 expensive profit-max bids to ML-CCARAISED). CCARAISED. CCAPROHT. MVNN (Weissteiner et al., 2022a), NN (based on classical neural networks (Weissteiner & Seuken, 2020)), FT (based on Fourier Transforms (Weissteiner et al., 2022b)), and RS (random search, as a baseline). Shown are averages and a 95% CL. Winners based on t-test with significance level of 5% are marked in grey.
G.S.I. COMPARING MLHCA TO ML-CCAPROFIT
In each domain, the 2nd highest efficiency is achieved by ML-CCAPROFI which uses both more DQs and more VQs than our method (see Table 2). In total MI--CAPRRFFT uses 201-300 queries if you count profit-max bids as only query. If you count profit-max bids as 2 queries ML-CCAPROFT uses 301-400 queries. Although ML-CCAPRORT asks 2-4 times more queries than MLHCA, ML-CCAPROFT is not able to outperform MLHCA in any domain, not even slightly. On the contrary, MLHCA substantially outperforms ML-CCAPROFI in the most realistic domain MRVM.
G.5.2. UNDERSTANDING THE SCALE OF THESE EFFICIENCY IMPROVEMENTS.
For example, the most realistic simulator MRVM was specifically designed to simulate the 2014 Canadian 4G spectrum auction. The real 2014 Canadian 4G spectrum auction achieved a revenue of USD 5.27 billion (Ausubel & Baranov, 2017). The revenue of an auction is a very conservative lower bound of the social welfare (SCW), which is typically significantly higher than the revenue. With this conservative lower bound 1% point corresponds to more than USD 50 million, probably even significantly more. For this simulation MRVM, MLHCA is outperforming every other 100-query method by more than 2% point (averaged over 50 random instances of the auction). Even those results of Table 2 that use substantially more than 100 queries, are outperformed by only 100 queries of MI.HCA by over 1.5% points. Every supplemented version of the CCA from Table 2 (with up to 300 queries) is outperformed by only 100 queries of MLHCA by over 2% points. This is particularly interesting, since CCA is among the most popular mechanisms currently used for real-world auctions. Such an improvement 2% points would result in gain in SCW of USD 100 million of a single instance of the 2014 Canadian spectrum auction.
Translating these results to the latest Canadian Spectrum Auction (Innovation, Science and Economic Development Canada, 2023), MLHCA's welfare gains would equate to over 50 million USD compared to all other mechanisms.
Note that repeatedly multiple spectrum auctions are conducted all over the world. E.g., CCA generated over USD 20 billion in revenue between 2012 and 2014 alone (Ausubel & |Baranov, 2017).
G.6. Details on Bidding Heuristics
The second phase of the CCA (or ML-CCA) is the supplementary round. In this phase, each bidder can submit a finite number of additional bids for bundles of items, which are called push bids. Then, the final allocation is determined based on the combined set of all inferred bids of the clock phase, plus all submitted push bids of the supplementary round. This design aims to combine good price discovery in the clock phase with good expressiveness in the supplementary
39

---

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
round. In simulations, the supplementary round is parametrized by the assumed bidder behaviour in this phase, i.e., which bundle-value pairs they choose report. As in (Brero al., 2021), consider the following heuristics when simulating bidder behaviour:
Clock Bids: Corresponds to having no supplementary round. Thus, the final allocation is determined based only on the inferred bids of the clock phase (Equation (3)).
Raised Clock Bids: The bidders also provide their true value for all bundles they bid on during the clock phase.
Profit Max: Bidders provide their true value for all bundles that they bid on in the clock phase, and additionally submit
their true value for the QM bundles earning them the highest utility at the prices of the final clock phase. Le., each profit-max bid can be seen as
one constrained DQ to determine which bundle is best given price vector p, constrained on choosing an already chosen bundle plus
one VQ to determine the exact value of this bundle.
However, in Table 2 we count each profit-max query only VQ.
Note that our mechanism also allows the bidders to voluntarily provide push bids. These additional VQs could probably increase the efficiency of our mechanism even slightly further. However, we evaluate our mechanism in the worst case, where no push bids are provides to MLHCA. And the results Table show that even without receiving any push bids MLCA achieves the highest average efficiency each tested domain.
40

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
G.7. Revenue Results
EFFICIENCY LOss % RELATIVE REVENUE IN
DOMAIN
MLHCA
BOCA
MLHCA
BOCA
GSVM
0.00 + 0.00
70.15 + 4.43
LSVM
0.04 = 0.07
0.39 = 0.31
79.43 + 3.05
73.53 + 3.72
SRVM
0.00 1 0.00
0.06 1 0.02
56.05 1 1.69
54.22 1 1.46
MRVM
4.81 + 0.57 7.77 + 0.35
27.97 + 2.16
42.04 + 1.89
Table 10: Efficiency loss and relative revenue comparison between MLHCA (40DQs + 60VQs) and BOCA (100VQs). Shown are averages and a 95% CL. Winners marked in gray.
In Table 10, present the relative revenue results of MLHCA and BOCA, both using VCG payments (see Appendix B. We define relative revenue as the percentage of optimal welfare recovered revenue a per-instance basis. For detailed discussion of the corresponding efficiency results, please refer to Section 6.
Unlike efficiency, the best- rest-performing mechanism in terms of revenue varies by domain. In the LSVM and SRVM domains, MLHCA generates higher revenue than BOCA, while in the MRVM domain, the opposite is true.
The explanation for MLHCA's higher revenue the LSVM and SRVM domains is straightforward: MLHCA achieves higher efficiency than BOCA in these domains and still has least 42 VQs remaining after matching BOCA's efficiency, This additional exploration afforded by those extra VQs enables MLHCA to identify many value allocations, ultimately driving up prices under the VCG payment rule.
The lower revenue of MLHCA compared to BOCA in the MRVM domain can be explained by examining the DQ rounds of MLHCA. In this domain, lower competition among bidders results relatively low item prices, which reduces the inferred-to-true welfare ratio of the allocations based only on the DQs. This is illustrated in Figure The low inferred value from these queries prevents them from driving up the VCG prices, even though they lead allocations with high efficiency. As result, in this domain, only the VQs contribute significantly to the auction's 's payments. Given that BOCA uses 100 VQs while MLHCA uses only 60, this difference leads to BOCA achieving higher revenue in the MRVM domain.

---

Prices, Bids, Values: One ML-Poowered Combinatorial Auction to Rule Them All
G.8. Evaluating the Effectiveness of the Bridge Bid
SCW
2.0
90
80
Eticiency
Inferred
70
MIHCA Efficiancy (Bridge Bid)
MIHCC Emficlnccy (No Bridge Bkd)
1.0
Start
Rounds
50
Start of ML Rounds
No Bridge reaches DQ-anly efficiency at bids
0.8
MRVM True SCW
MRVM Inferred SCW
Bridge matches Bridge Bid efficiency 82 bids
0.6
Start of ML VQ Rounds
40
20
30
40 50
60 70
80
90
100
Number of Elicited Bids
Number of Elicited Bids
(a) Efficiency MLHCA with and without the bridge bid (Defini- (b) Normalized inferred and true social welfare (SCW) MLHCA without the bridge bid in the MRVM domain. Both quantities are normalized with respect to their average values at the start of the ML-based VQs.
tion D.8) in the MRVM domain.
Figure 4: Comparison of MLHCA's performance in the MRVM domain: (a) Efficiency with and without the bridge bid; (b) Normalized inferred and true SCW. Shown are averages over 50 instances including 95% Cls.
In this section, we experimentally evaluate the effectiveness of the bridge bid from Section 3.
In Figure 4a, we plot MLHCA's efficiency in the MRVM domain as a function of the number of elicited bids, comparing performance with and without the bridge bid. Without the bridge bid, observe a significant efficiency drop of 7.3% points when MLHCA transitions its VQ rounds. This is consistent with theoretical results in Lemma D.7, where we showed that efficiency can decrease when the first VQ is introduced after DQs. In the MRVM domain, the most realistic setting, this effect is particularly pronounced. Notably, the auction requires 20 of our powerful ML-powered VQs just to recover the efficiency lost by the introduction of the first VQ. By contrast, using the bridge bid (Definition D.8) completely mitigates this efficiency drop, as predicted by Lemma D.9. However, as Figure 4a shows, if enough VQs are elicited, MLHCA without the bridge bid can eventually recover its efficiency, and both approaches converge similar performance levels.
However, given that the auctioneer cannot determine the true efficiency of the auction at runtime, it is prudent to the bridge bid version, which ensures consistent performance throughout the auction and significantly outperforms the alternative for the majority of rounds. Therefore, we consider this version the default approach for our MLHCA.
To better understand the cause of this efficiency drop, we refer to Figure 4b, where we plot the normalized inferred and true social welfare of MLHCA without the bridge bid in the MRVM domain. Both quantities are normalized to their values at the start of the Mo-pooeered VQ rounds. At this point, we observe a stark contrast: the first VQ increases inferred social welfare by over 70%. while decreasing true social welfare by more than 7%. Before the ML-powered VQs, agents' reports were limited to their responses to DQs, and the auction's 's inferred social welfare was calculated based on the prices of the allocated bundles, as described in Equation (3). Due to the relatively low competition in MRVM, there was a substantial gap between the agents' true values and the inferred values based on their DQ responses." 27
When the auction transitioned to VQs, agents responded with their true values for the queried bundles, leading to a sharp increase in inferred social welfare. However, the bidders' true values for the bundles they received during the DQ rounds were much higher than their inferred values, which the WDP failed to capture. As a result, transitioning to MI--powered VQs without the bridge bid caused sharp increase in inferred social welfare alongside drop in frue social welfare.
This efficiency drop when transitioning to VQs is less pronounced in other domains. In Figure 5, we plot MLHCA's SCW for all domains as function of the number of elicited bids, normalized to the start of the MI-powered VQ rounds. In these domains, the higher level of competition leads to inferred values for the queried bundles during the DQ rounds being much closer to the true values. Consequently, the bridge bid is less critical in these settings.
Low competition in the auction can be gauged from its revenue, as, in the absence of reserve prices, revenue is primarily driven by competition among bidders. MRVM has lowest ratio of revenue to welfare across all domains by factor of nearly 2; see Appendix G.7.
42

---

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
2.0
Normalized Interred SCW
1.6
1.4
1.2
1.0
LSVM
0.8
MRVM
SRVM
20
90
100
Number Bids
Figure 5: Normalized Inferred Social Welfare of MLHCA (with the bridge bid) in all domains. Shown averages over 50 instances including 95% Cls.
43

---

Prices, Bids, Values: One ML-Pooeered Combinatorial Auction to Rule Them All
G.9. Inverse Query Order
EFFICIENCY LOSS IN %
QUERIES TO REJECT NULL HYPOTHESIS
DOMAIN
MLHCA
INVERSE
BOCA
MI.-CCAcLoce
ML-CCAAass BOCA MLHCA INVERSE
MLHCA ML-CCAAAAER MLHCA
GSVM
0.00 + 0.00
0.28 0.30
1.77 0.68
1.07 0.37
50
LSVM
0.04 = 0.07
5,12 2.18 0.31
8.36 = 1.70
3.61:0077
58
43
43
SRVM
0.00 + 0.00
0.08 + 0.16 0.06 + 0.02
0.41 0.11
0.07 + 0.02
42
42
Table 11: MLHCA (40DQs 60VQs) Inverse (80 VQs 20 DQs), BOCA (100VQs), ML-CCA (ML-CCActcc) (100DQs)
and ML-CCA with raised clock bids (ML-CCAmisee) (100DQs and up 100VQs). Shown are averages and 95% CI. Winners based on (-test with significance level of 5% are marked in grey.
GSVM
LSVM
SRVM
10a
10a
10a
Efficiency Loss (Log Scale)
10
10
20
10
10
10-2
10
10
10
10
10
10 5
10
10
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
Number of Elicited Bids
Number of Elicited Bids
Number of Elicited Bids
MLHCA
Inverse
ML-CCA
BOCA
Start of ML Queries
Start of ML VQs (MLHCA)
Start of ML DQs (Inverse)
Figure 6: Efficiency loss paths (i.e., regret plots) of MLHCA compared to BOCA, ML-CCA and Inverse, an auction that inverses the order of DQs and VQs compared to MLHCA. Shown are averages over 50 instances with 95% Cls.
In this section, experimentally evaluate how the order of queries affects auction performance. To this end, introduce variant of our mechanism, which we refer to as Inverse. This mechanism mirrors the structure of MLHCA described in Section 5, but with the query order reversed: Inverse begins with value queries (VQs), followed by demand queries (DQs), Concretely, while MLHCA starts with 20 CCA-based DQs to initialize learning, followed by 20 ML-powered DQs and then 60 ML-powered VQs, Inverse instead begins with 20 randomly chosen VQs, proceeds with 60 ML-powered VQs, and concludes with 20 poweeee DQs. Unlike MLHCA, Inverse does not use the bridge bid introduced Section 5. Because its final stage consists of DQS, there no need for special bid to preserve its DQ-only efficiency later phases.
To isolate the effect of query order auction efficiency, evaluate all auction formats the same set of auction instances. For the same reason, we use identical hyperparameters for both MLHCA and the Inverse auction, as described in Appendix G.3. For more details on the experimental setup, please refer to Section 6.1.
As in Section 6.2, Table reports the average efficiency loss of each mechanism after 100 queries. For ML-CCA, we additionally report results assuming it is supplemented with the clock bids raised heuristic (see Section 2.2), which may require up 100 additional VQs per bidder. 28 We also report how many queries MLHCA needs statistically outperform the final efficiency of the other mechanisms.
We observe that in all domains tested, 29 MLHCA consistently outperforms the Inverse auction. In the LSVM domain, the efficiency difference reaches 5 percentage points, which would translate to welfare gains exceeding 200 million USD based on the value of goods typically traded in such auctions. Notably, in both the GSVM and LSVV domains, MLHCA statistically outperforms the Inverse auction at the 95% confidence level while using at most half as many queries. At this
28 Under the clock bids raised heuristic, bidders report their value only for each unique bundle they hid on during the auction-up to 100 bundles for 100 DQs.
29 Due to time constraints between the final reviews the camera-ready deadline, results the MRVM domain are not yet availahle.
44

---

Prices, Bids, Values: One ML-Pooeered Combinatorial Auction to Rule Them All
point, Inverse has already asked each bidder 50 of the more cognitively demanding VQs, whereas MLHCA has used asked 10 VQs. In the SRVM domain, despite achieving higher average efficiency, MLHCA does not statistically outperform the Inverse auction. This is due to the simplicity of the domain: the Inverse auction reaches perfect (100%) efficiency in 49 out of 50 instances, rendering the two mechanisms statistically indistinguishable.
To gain a more detailed understanding of the impact of the inverse query order, Figure 1 illustrates the efficiency loss path for the GSVM, LSVM, and SRVM domains. Across all three domains, we observe that placing ML-powered DQs after the ML-powered VQs fails to improve the auction's 's efficiency. This is particularly noteworthy in the LSVM domain, where the efficiency loss after the ML-powered VQ phase was over percentage points, meaning there was still significant room for improvement. Although the bidders' ML models become significantly more accurate once the auction reaches its DQ phase, the DQ algorithm is unable to leverage this improved model accuracy to generate more efficient outcomes.
Taken together, the results in this section provide strong empirical support for our theoretical analysis in Appendices D.3 and D.4: effective hybrid auctions should begin with DQs to gather global information about bidders' valuation functions, and only then transition to VQs to both refine understanding the most critical regions of the allocation space and to obtain bids for bundles that are compatible for a feasible allocation. Across all tested domains, reversing this order results in substantial efficiency losses: ML-powered DQs fail to improve upon the efficiency achieved by the preceding VQs, while VQs, when used upfront, perform worse than in the standard order due to the reduced learning performance from training solely on VQs. These findings underscore the pivotal role of query ordering in the design of machine Sarning-poweree combinatorial auctions.
While all subplots in Figure 6 clearly support our claim that asking DQs before VQs results in better final efficiency than asking them the other way around, certain details in the subplot for SRVM might raise some questions that we answer in Remarks G.1 and G.2.
Remark G.I (Why are 20 random VQs better now than 20 random VQs were for BOCA for SRVM?). In Figure 6, for SRVM, we see that the efficiency of the Inverse auction after its initial random 20 VQs is approximately 4 times better than BOCA after its initial 40 random VQs. The reason for this, is a difference in the data pre-processing used for BOCA from (Weissteiner et al., 2023) and our data pre-processing from (Soumalias et al., 2024c). SRVM (Weiss et al., 2017) has items with capacities ci 6, 02 = 14, c3 9. In (Weissteiner al., 2023), these items were treated as c1 + C3 = 6+ 14 9 = 29 unique items. In other words, we and (Soumalias et al., 2024c) provide the mechanism with the prior knowledge that the first 6 items are indistinguishable copies of each other, and the next 14 items are indistinguishable copies of each other, and the remaining 9 items are indistinguishable copies of each other, while (Weissteiner & Seuken, 2020; Weissteiner et al., 2022b;a; 2023) did not use this prior knowledge in any form. This additional prior knowledge used by Inverse, but not used by BOCA, explains the advantage of Inverse over BOCA in this domain. The reason that those works did not leverage that information is that the multiset MVNNs required to capture that prior knowledge were only introduced in Soumalias al. (2024c), which superseded these works. Nevertheless, the point of the inverse auction is not to compare against the SOTA MI.-powered auction, BOCA, but to empirically evaluate the effect of switching the query order compared to MLHCA. In the end, BOCA can still outperform Inverse for 2 potential reasons: 1) BOCA keeps asking VQs until the end, while Inverse switches to DQs for the last 20 rounds, where DQs lose their effectiveness towards the end of the auction, or 2) BOCA explicitly fosters exploring unexplored regions of the bundle space, which gives it an advantage in the long run.
Remark G.2 (Are initial random VQs better for SRVM than initial CCA-DQ&?). In Figure 6, directly that for GSVM and LSVM, starting the auction with 20 CCA-DQs is better than starting the auction with 20 random VQs. However, for SRVM, the efficiency after the initial random 20 VQs of Inverse is better than the efficiency after the initial 20 CCA-DQs of MLHCA or MI-CCA. Nevertheless, for all considered domains, including SRVM, we can see that MLHCA takes the lead after round 42. Our intuitive explamation is that 1) for all considered domains, including SRVM, the initial 20 CCA-DQs foster a better learning of the value functions, 2) the bundles that bidders request in the CCA-DQs, are usually incompatible, which seems to especially hurt the efficiency of SRVM, and 3) ML-VQs are always asked for perfectly compatible bundles, and if the models understand the value functions already sufficiently well, directly the first MI.VQQ after the bridge bid can result in an allocation with very high efficiency (as intuitively demonstrated in Example I and as supported empirically by all our experiments). In summary, the efficiency observed from DQs can be misleading as signal of learning progress, since the requested bundles are often incompatible and therefore fail to reflect the model's ''s understanding. In contrast, the efficiency observed immediately after an ML-VQ provides a much more accurate reflection of the current learning state, as elicits bids on perfectly compatible bundles across all bidders.
45


Reviews:
[{"review_id": "CZyVCB1YXO", "reviewer": "Reviewer_U2sY", "summary": "The paper introduces MLHCA, a Machine Learning-powered Hybrid Combinatorial Auction that integrates demand queries (DQs) and value queries (VQs) to minimize efficiency loss in iterative combinatorial auctions. The authors provide theoretical insights demonstrating that DQs are most effective in the early auction rounds, while VQs enhance efficiency in later stages by refining allocations. This approach addresses the limitations of previous methods that relied solely on one query type. Empirical results show that MLHCA outperforms existing methods by achieving higher efficiency with fewer queries, significantly reducing bidders’ cognitive load.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and thorough feedback!  If you have any more questions, please let us know.\n\n“A discussion on incentive compatibility would be nice.”\n\nWe discuss incentive compatibility in detail in Appendix B, where we try to provide intuition on this topic and prove some theoretical results under some assumptions. In summary, neither the most established mechanism, the CCA, nor any of the ML-powered approaches discussed in the literature are perfectly strategy-proof. However, there are strong theoretical hints suggesting that MLHCA is more robust to strategic misreports than the CCA, currently used in the real world, or most other ML-powered ICAs, such as Weissteiner et al. 2022a, 2023 and Soumalias 2024c. First, MLHCA’s DQ phase is compatible with the activity rules used in the CCA to improve its incentive properties (Appendix B.3). Second, MLHCA can automatically  detect when a bidder provides inconsistent reports (Lemma B.6). Third, MLHCA leverages marginal economies in the same way as the VQ-based ML-powered auctions to further align incentives. Fourth, as pointed out in Remark B.7, our experiments show that Assumption 2 in Appendix B.5 has become much more realistic for MLHCA than for any previously proposed mechanism.\n\n\"Other approaches for enforcing monotonicity in neural networks?\"\n\nNo, we did not compare MVNNs against other architectures. MVNNs have a strong theoretical foundation and have proven their success in learning value functions across multiple market design papers [Weissteiner et al., 2022a,Weissteiner et al., 2023,  Soumalias et al. 2024b,c]. Additionally, since MVNNs are the main architecture behind these papers that we compare against, by using the same architecture, we can more easily isolate the effect of our query generation algorithms and the learning advantages of combining both query types. From an auction perspective, finding alternatives to MVNNs probably does not have the highest priority, since MVNNs work very well in practice. Finally, there is also no evidence suggesting that the suggested architecture would perform better, as the authors of that paper did not compare against MVNNs. \n\n“In a way, this paper simply combines two existing approaches, but it does so in a principled way with theoretical justifications and empirical validations!”\n\nThank you for this comment—we believe it is a fair and accurate characterization of our work. Indeed, this was precisely the goal of our paper: to combine the two most prominent query types in iterative combinatorial auctions (ICAs) in a principled and effective way. We used our theoretical results to achieve an unprecedented improvement in efficiency while at the same time trying to keep the interaction paradigm as close as possible to the most established interaction paradigm used in practice.\n\nOur aim was not to propose a radically new interaction paradigm, but to improve auction performance in ways that are realistically implementable in high-stakes settings like spectrum auctions. To do this, we developed a new theoretical framework for understanding the advantages of combining demand and value queries, both from a combinatorial optimization and a machine learning perspective. For all theoretical results, we were able to experimentally demonstrate their real-world significance.\n\nWe then leveraged these insights to create MLHCA, an auction that follows the same interaction paradigm as the established CCA, yet achieves substantial perf\normance gains. MLHCA is the most efficient auction in practice, reducing efficiency loss by up to a factor of 10 and surpassing the previous state of the art while using up to 58% fewer queries.\n\nWhile MLHCA’s similarity to the CCA may make it appear less novel at first glance, we believe this is a strength. By identifying the core challenge in value elicitation and addressing it through minimal yet effective changes, we were able to dramatically improve efficiency while remaining fully compatible with established, battle-tested, auction paradigms.\n\nSoumalias, E., Zamanlooy, B., Weissteiner, J., and Seuken,S.\nMachine learning-powered course allocation. EC 2024b\n\nSoumalias, E. N., Weissteiner, J., Heiss, J., and Seuken, S.\nMachine learning-powered combinatorial clock auction. AAAI 2024c\n\nWeissteiner, J., Heiss, J., Siems, J., and Seuken, S.\nMonotone-value neural networks: Exploiting preference monotonicity in combinatorial assignment. IJCAI 2022a\n\nWeissteiner, J., Heiss, J., Siems, J., and Seuken, S.\nBayesian optimization-based combinatorial assignment.  AAAI 2023", "claims_and_evidence": "Yes. All claims made in the paper are theoretical justified and are supported with adequate empirical validation. The paper convincingly demonstrated that the proposed approach is better than existing methods.", "methods_and_evaluation_criteria": "Yes. They are well defined and well justified.", "theoretical_claims": "The proofs seem logically sound. I however didn't go through the proofs in the Appendix in detail", "experimental_designs_or_analyses": "The experimental design is solid - with strong baseline comparisons (BOCA, ML-CCA, CCA) and real-world spectrum auction datasets (SATS). The metrics (efficiency and query count) are also appropriately chosen.", "relation_to_broader_scientific_literature": "This paper extends prior work in ICAs by combining demand queries and value queries (VQs). The problem studied is significant and the proposed achieves better performance than existing SOTA approaches.", "essential_references_not_discussed": "References are adequate.", "other_strengths_and_weaknesses": "In a way, this paper simply combines two existing approaches, but it does so in a principled way with theoretical justications and empirical validations!", "other_comments_or_suggestions": "- A discussion on incentive compatibility would be nice.  Can the agents misreport their preference in the elicitation stage? How robust is the VQ/ DQ and proposed approach to such strategic misreports!\n- Have you tried other approaches for enforcing monotonicity in neural networks (such as [this](https://arxiv.org/abs/2307.07512))", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "x1FKXbl9L5", "reviewer": "Reviewer_yLNu", "summary": "The paper introduces a new auction method called the Machine Learning-powered Hybrid Combinatorial Auction (MLHCA), designed to improve how items are sold in complex auctions where bidders can place offers on combinations of items. In these auctions, figuring out the best combination of bids is difficult because the number of possible combinations grows very quickly as more items are added. Traditional auctions either use demand queries (DQs) (where bidders state which combination they prefer at a certain price) or value queries (VQs) (where bidders say how much they value a specific combination). MLHCA combines both types of queries, starting with DQs to quickly gather general information and then switching to VQs to fine-tune the final outcome. The paper introduces a \"bridge bid\" to make the switch between DQs and VQs smooth. \n\nThe paper provides a few theoretical insights into the failure of DQ-only or VQ-only mechanisms and provides a new mechanism to mitigate those issues. The paper then conducts extensive experiments on standard datasets to validate the proposed mechanism on the standard datasets and shows that it outperforms existing models.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your very detailed review! If you have more questions, please let us know.\n\n“The assumptions on the value function are unclear” \n\nWe only assume that $v(0) = 0$ and monotonicity, which combined imply non-negativity. Both of those assumptions are well-motivated and fairly standard. In Appendix C.1 we reference theoretical results that MVNNs can represent any monotonic function with $v(0)=0.$ We will clarify this in the final revision.\n\n“Combining DQs and VQs in other ways”\n\nIn Appendices D and E we provide a lot of intuition on why starting with DQs and then querying VQs is expected to be much better than the other way around. Initializing an auction with random VQs (there are no better initialization algorithms for ML-powered VQs in the literature) will elicit the values of bundles which are far from optimal for the bidders, providing very little actionable information. The DQs at the end will be ineffective for two reasons: first, they will not provide any further information once the concave envelope of the value function is learned. Second, it is very likely that they will not result in reported bundles which nicely fit together (Example 1 provides good intuition for this). Therefore, we have good reasons to believe that swapping the order would significantly worsen the performance. Finally, one additional argument for this query order is that it results in the same interaction paradigm as the established CCA.  We will emphasize these arguments more in the final revision.\n\n“Is responding to DQs simpler than VQs?” \n\nWhile your argument on theoretical time complexity is correct, in practice, a bidder does not need to exactly evaluate her utility to answer a DQ. To make the supermarket example more intuitive:\nSuppose you go to the supermarket to buy a bundle of food items. \nThen you can easily disregard most other items, e.g., all the electronic items in the store. You only need to know that an electronic item’s added value for you is lower than its price tag. Reporting your precise value for a random bundle containing some food items, an iPad and a charger is much harder than deciding that you don’t want to buy the electronic items given their prices.\nBased on the experience of real-world consultants in spectrum auctions, there are usually many spectrum licenses that a bidder can easily disregard when answering a DQ, knowing that her values for them are below the posted prices without knowing how much below. In contrast to [SZB12], real-world bidders have much more expertise on the values of bundles that fit into their business model than the values of some random bundle. We agree that VQs for good bundles are easy to answer, but this is not true for random bundles in the real world.\n\n“A DQ with an MVNN approximating the value function is time consuming” \n\nUsing 8 cores, it takes on average less than 200 ms. This does not relate to the human complexity for a bidder.\n\n“Does Lemma B.6 require a unique optimal solution?”\nLemma B.6 does not require a unique optimal solution. Instead, all optimal solutions have the same predicted utility for the user, defined as <predicted bundle value> - <bundle price when the bidder requested it>. \n\n“Is it true that DQ-only methods such as ML-CCA can also detect inconsistent misreports?”\n\nYes, we will mention this implication of our result in the final revision. \n\n“What is the meaning of proposition C.5? Do MVNNs always learn an almost linear approximation of the true value function?”\n\nMVNNs can fit queries that cannot be explained by a linear model (once those queries appear in the auction), which gives them a big competitive advantage over linear models. Proposition C.5 provides intuition on how MVNNs apply Occam’s razor in the case of not sufficiently informative queries. Proposition C.5 shows that in Example 1, the first VQ MLHCA would ask after the bridge bid would directly push the efficiency from ~55% to 100%. \n\n“What is the significance of the 55% efficiency in Theorem 3.2?”\n\nFor the final version of the paper, we will modify the proof to show that for every $\\epsilon>0$, there exist infinitely many instances where any DQ-only algorithm cannot achieve more than $50+\\epsilon$% efficiency, no matter how many DQs it generates. Since such a family of instances exists, this constitutes a proof that DQs can be highly inefficient as the sole query type in an auction. \nMathematically it would be an interesting open question if 50% can be reduced to 25%. However, from a practical point of view an efficiency of 50% corresponds to welfare losses of billions of dollars. This theoretically emphasizes that DQs massively lose their power in later rounds even if you ask infinitely many DQs, while VQs can always reach 100% efficiency. So, the claim that “DQs are more informative in an auction” is actually a much more nuanced discussion. \n\n\nFinally, thank you so much for the many typos you pointed out. We will correct them all for the final version of the paper.", "claims_and_evidence": "Most of the proposed claims are well supported. While the experiments clearly show the superior performance of the proposed mechanism which is the highlight of the submission, some of the theoretical insights in the paper are unclear and inadequate. Please see the weaknesses section for more details.", "methods_and_evaluation_criteria": "The authors test MLHCA on realistic datasets from the spectrum auction test suite (SATS), which simulates different auction environments. They measure success using efficiency loss (how close the final allocation is to the optimal one) and the number of queries required to reach that outcome. MLHCA’s ability to reduce efficiency loss by up to a factor of 10 and cut down the number of queries by up to 58% demonstrates its practical value.", "theoretical_claims": "I checked all the proofs presented in the paper and they seem fine.", "experimental_designs_or_analyses": "The experiment design and analysis are correct to the best of my knowledge.", "relation_to_broader_scientific_literature": "The proposed two-stage mechanism overcomes several shortcomings of the DQ-only or VQ-only ML-powered mechanisms in the existing literature. The notion of the bridge bid introduced in this work also indicates that (perhaps) instead of the traditional DQs and VQs, future research in this area can focus on designing better queries or newer methods for combining DQs and VQs to elicit more information from the bidders instead of more elaborate NN models. \n\nThe key contribution of the paper is the mechanism in Algorithm 1 which leverages several existing methods and modules (MixedTraining (a straightforward extension of the TrainOnDQs module of [SWHS24] which uses both DQs and VQs instead of only DQs) and NextPrice [SWHS24]). A considerable portion of the theoretical contribution leverages the results from the MLCA paper [BLS19] and ML-CCA paper [SWHS24] which is cited in the submission. \n\n[BLS19] Brero, Gianluca, Benjamin Lubin, and Sven Seuken. \"Machine learning-powered iterative combinatorial auctions.\" arXiv preprint arXiv:1911.08042 (2019).\n\n[SWHS24] Soumalias, Ermis Nikiforos, et al. \"Machine learning-powered combinatorial clock auction.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 9. 2024.", "essential_references_not_discussed": "All relevant works are discussed in the paper to the best of my knowledge.", "other_strengths_and_weaknesses": "A: **Strengths:**\nThe experiments are well designed and extensive which substantiate the superior performance of the proposed mechanism.\nThe notion of bridge bid is novel conceptually and its effect in practice is also highlighted well.\n\n**Weakness:**\nThe assumptions on the value function are not clear. A crucial aspect in any combinatorial auctions is the structure of the value function. But the authors do not explicitly mention it in the work (Line 121 suggests it is non-negative). By reading the whole paper including the supplementary material, unless I am missing something, the only assumption on the value function is that it is non-negative and monotone. For the rest of my comments, I will assume this. In any case, the authors need to clarify this in the beginning. \n\n**Demand Queries vs Value Queries.** A common theme which is repeated several times in the paper is that the DQs are cognitively simpler than VQs for the bidder. While it is well known that DQs are more informative than VQs in terms of eliciting preferences (which is also evident from the experiments), from a computational point of view, DQs can be quite hard to evaluate especially if the value function is not ‘simple’. Even for submodular value functions, this is known to be NP-Hard [FV10]. Furthermore, there are several experimental studies which suggest that it is hard for participants to optimally respond to a DQ [SZB12, BSW13]. Even the authors argue in Remark E.1 that evaluating a DQ with the MVNN approximating the value function is time consuming for which they reuse the values. So, how is responding to DQs cognitively simpler? In terms of the supermarket example which is used in the paper to provide intuition: if the value function is not ‘nice’ (linear/all-or-nothing etc), then for a given set of prices, to know the optimal combination of frying pans and coconuts, the bidder needs to evaluate the value of x frying pans and y coconuts in the first place which is equivalent to a VQ.\n\n[FV10] Feige, Uriel, and Jan Vondrák. \"The submodular welfare problem with demand queries.\" Theory of Computing 6.1 (2010): 247-290.\n\n[SZB12] Scheel, Tobias, Georg Ziegler, and Martin Bichler. 2012. “On the Impact of Cognitive Limits in Combinatorial Auctions: An Experimental Study in the Context of Spectrum Auction Design.” Experimental Economics, 15: 667–692.\n\n[BSW13] Bichler, Martin, Pasha Shabalin, and Jürgen Wolf. 2013. “Do Core-selecting Combinatorial Clock Auctions Always Lead to High Efficiency? An Experimental Analysis of Spectrum Auction Designs.” Experimental Economics, 16(4): 511–545.", "other_comments_or_suggestions": "A: **Typos:**\nLine 89, 2nd column: the word ‘preference’ is present twice.\n\nLine 197, 1st column: Proofs are deferred to Appendix D.\n\nLine 290, 1st column: An extra ‘R’ is present in the Algorithm 1.\n\nLine 668, 669: Use \\textsc{} for ‘NextQueries’ to be consistent.\n\nLine 692, eq (5): What’s the significance of ‘1’ in \\stackrel{}{}?\n\nLine 843: Use \\mathcal{X} to represent the class of feasible bundles. \n\nLine 1012, 1013: Typo in word ‘appendix’.\n\nLine 1017: MVNNscan -> MVNNs can.\n\nLine 1162: inAppendix E.2 ->  in Appendix E.2\n\nLine 1440: Typo in word ‘optimization’.\n\nLine 1541: … we showed… instead of …we will show…\n\nLine 1855: Missing full stop.\n\n**Suggestions:**\nA key aspect of the paper is combining the DQs and VQs and as the authors argue in Line 419-423 (2nd column), the way in which it is combined is important (which is also one of the key contributions of the work). The paper would have been more compelling if the authors had tried combining the DQs and VQs in other ways (VQs first, then DQs or interleaving them and so on), either theoretically or experimentally. That which would have highlighted the significance of the current method of combining them both.\n\nAs a lot of modules and subroutines in Algorithm 1 are from existing literature, it would help the paper if the authors precisely highlighted their novel contributions in designing the mechanism.", "questions_for_authors": "A: \nIn Lemma B.6, If L(theta)=0, why does it mean that the predicted best response matches the reported one? Am I correct to understand that you are assuming the optimization problem has a unique optimal value? If so, why is that the case? Moreover, the proof handles the DQ phase and VQ phase separately and obtains a contradiction under each setting. So, is it true that DQ-only methods such as ML-CCA can also detect inconsistent misreports? \n\nIn Proposition C.5, do MVNNs always learn an (almost) linear approximation of the value function or is it true only for the given example? More broadly, what is the importance of this result? If MVNNs always learn an (almost) linear approximation of the value function, the paper would be strengthened if the authors also consider a simple linear model to approximate the value function as a baseline to compare it against the more sophisticated MVNNs. \n\nWhat is the significance of the 55% efficiency in Theorem 3.2? The proof only presents an example under which this efficiency can not be achieved. If I chose some other number, say 25%, does a DQ-only auction always guarantee 25% efficiency? I guess with appropriate tweaking of the parameters of the example, one can show that the previous statement is not true. So, why highlight the 55% figure? At a high level, I would suggest presenting this as an Observation/Fact instead of the full-fledged Theorem.\n\n**Minor comments:**\nWhat is the full form of DWP in footnote 15 in Line 1263?\nA minor comment but what is the reasoning behind the three words ‘Prices, Bids, Value’ in the paper title?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "e56CPzCcd3", "reviewer": "Reviewer_xL2f", "summary": "This paper studies Iterative Combinatorial Auctions (ICA) and proposes a novel ML-based ICA mechanism, MLHCA. Their key empirical finding is that the mixed use of Value Queries (VQ) and Demand Queries (DQ) in their ML-based ICA mechanism significantly improves the efficiency and convergence of ICA compared to prior works. Additionally, they complement this finding with theoretical observations highlighting the disadvantages of using VQ or DQ alone.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback! If you have any more questions, please let us know.\n\n “Does not provide a provable positive result for their mixed use, even in a simple toy model.” \n\nLemmata D.9 and D.14, and Example 1 provide positive results, but we agree that our experimental positive results are stronger than our theoretical results. In Appendix D.3 we provide Example 1, which we believe provides very good intuition both on why DQs alone can be ineffective, and on why combining both query types can substantially increase efficiency. \n\n“Is there any hope of strengthening ex-post Nash incentive compatibility into dominant strategy incentive compatibility, possibly under certain assumptions”?\n\nUnder extremely strong assumptions, namely that our auction can request an exponential number of value queries from the agents, it is trivial to show that it satisfies DSIC. Additionally, in appendix B.5, we explain how MLHCA can automatically detect if a bidder’s reports are inconsistent with any valuation function (and  automatically exclude them from the auction. This restricts a bidder's misreport space to consistent value functions. For more mild assumptions however, proving DSIC becomes challenging. Please note that DSIC has not been proven neither for the CCA, the most established ICA in the real world, nor for any of the ML-powered ICAs in the literature that we are aware of. However, in appendix B, we discuss in detail the incentive properties of our MLHCA, and we provide strong theoretical hints suggesting that MLHCA is more robust to strategic misreports than both the CCA, and the other ML-powered ICAs discussed in this paper. Please also see our reply to reviewer U2sY.", "claims_and_evidence": "The core claim of this paper is that a mixed use of value queries (VQ) and demand queries (DQ) in iterative combinatorial auction (ICA) can significantly improve the efficiency and convergence. This claim is primarily supported by experiments, with some (weak) theoretical observations on the disadvantages of using VQ or DQ alone.", "methods_and_evaluation_criteria": "They use a standard benchmark, the Spectrum Auction Test Suite (SATS, Weiss et al., 2017), which is a sensible choice and aligns with prior works cited in this paper.", "theoretical_claims": "I found no issue with theorems proven in this paper.", "experimental_designs_or_analyses": "Their statistical testing method appears sound and standard, and the use of a standard benchmark enhances the transparency of their results. Given that their improvement (i.e., smaller efficiency loss) is substantial across all four benchmarks, we have no objections to their findings or statistical analysis.", "relation_to_broader_scientific_literature": "This paper contributes to the growing literature on ML-based ICAs by providing insights into the mixed use of value queries (VQ) and demand queries (DQ). While previous ML-based ICAs primarily relied on a single query type such as VQ-based approaches in Weissteiner et al., 2023 or DQ-based methods in Soumalias et al., 2024c, this work demonstrates that the hybrid approach significantly improves the efficiency and convergence of ICAs while minimizing bidder cognitive load.", "essential_references_not_discussed": "All essential references are discussed to the best of my knowledge.", "other_strengths_and_weaknesses": "**Strengths**  \n- This paper presents a novel ML-based ICA mechanism that significantly improves the current state-of-the-art.  \n- The main idea of mixing VQ with DQ has the potential for broader impact and deserves a further study.  \n\n**Weakness**  \n- The theoretical argument is somewhat weak, as it only highlights the disadvantages of using VQ or DQ alone but does not provide a provable positive result for their mixed use, even in a simple toy model.", "other_comments_or_suggestions": "I have no other comments.", "questions_for_authors": "Is there any hope of strengthening ex-post Nash incentive compatibility (i.e., truthful bidding is an ex-post Nash equilibrium) into dominant strategy incentive compatibility (i.e., truthful bidding is a dominant strategy), possibly under certain assumptions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YXZlaryRuj", "reviewer": "Reviewer_6y6Q", "summary": "This paper focuses on iterative combinatorial auctions (ICAs), aiming to tackle the issue of exponential bundle space growth in combinatorial auctions. The authors introduce a machine learning (ML) algorithm that utilizes information from both demand queries (DQs) and value queries (VQs) and present the ML-powered Hybrid Combinatorial Auction (MLHCA).\nMLHCA combines the advantages of DQs and VQs. DQs are more effective in the early auction stage as they are easier for bidders to answer and can provide global information about bidder preferences. VQs are more beneficial in the later rounds as they can precisely capture bidder values. By starting with DQs and then transitioning to VQs, MLHCA can achieve better learning performance.\nThe paper provides a theoretical framework for combining DQs and VQs, analyzes their advantages and limitations, and presents an algorithm. Experimental results show that MLHCA outperforms previous sota mechanisms in terms of efficiency and speed of convergence. Additionally, MLHCA is compatible with various payment and activity rules and can detect inconsistent misreports.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback! If you have any additional questions, please let us know. \n\n“I am concerned about the complexity of the MLHCA algorithm”:\n\nIn terms of theoretical time complexity, our ML-CCA, as every other ICA - including the CCA and all ML-powered auctions discussed - are NP-hard. That is because they need to solve the winner determination problem, which is an NP-hard combinatorial optimization problem.\nHowever, in practice the computational costs are very manageable, as discussed in Appendix G.4. Even in MRVM, the most computationally intensive and realistically-sized domain, the total time required to run all 100 rounds using 16 GB of RAM and 8 physical cores (clocked at 2.20GHz) was approximately 7 days, so all the necessary computations for 1 round take below 2 hours. This is not an issue, given that in the real-world, at most 2 clock rounds happen per day. For a real-world instance, just like for MRVM, the total computational cost in a paid cluster service for running our mechanism would be below 5 USD. Our efficiency improvements suggest that the welfare gains of doing so, compared to the CCA, would be approximately 100 million USD. For the other domains the computational costs are even lower. For the experimental results presented in this paper, we had to incur over 100 times the computational costs of a real-world instance. \nWith that being said, we did put effort into reducing the computational cost of our algorithm. For example, we have empirically observed that our mixed query training algorithm needs approximately 10 times more epochs to converge than the DQ-only training algorithm from [Soumalias et al., 2024c]. From an applied spectrum-auction perspective, increasing the computational costs by a factor 10 does not matter, because this can easily be parallelized. However, for our academic budget when running hundreds of auctions a factor of 10 matters a lot. This is why we had to come up with the technique described in Remark E.1, to reduce computational time approximately by a factor 10.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. No issues have been found so far.", "experimental_designs_or_analyses": "Yes. No issues have been found so far.", "relation_to_broader_scientific_literature": "The paper's key contributions significantly advance the fields of combinatorial auctions and machine learning. It improves upon traditional iterative combinatorial auctions (ICAs) like CCA, offering a more efficient and less cognitively burdensome alternative in MLHCA. In preference elicitation, the combination of DQs and VQs provides a new approach, enhancing learning performance. Regarding machine learning in auctions, the use of MVNNs and the mixed training algorithm add to the existing knowledge.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "1. High Efficiency: MLHCA significantly outperforms previous SOTA mechanisms, achieving high efficiency with fewer queries.\n2. Reduced Cognitive Load: Combining DQs and VQs lessens bidders' cognitive load.\n3. Theoretical and Practical Support: It has a solid theoretical framework and is compatible with practical rules.\n4. Smooth Transition between DQs and VQs: I particularly appreciate the transition from DQs to VQs in MLHCA, which effectively combines the two types of queries, leveraging the benefits of each. The bridge bid, a specialized VQ, ensures a seamless transition, preventing potential efficiency drops and enabling the auction to maintain high performance throughout the process. This well-designed transition plays a crucial role here.", "other_comments_or_suggestions": "No.", "questions_for_authors": "As a reviewer, I'm concerned about the complexity of the MLHCA algorithm. However, I didn't find relevant analysis in the paper and its appendices. There are suspicions that some steps in the algorithm may have relatively high complexity. I hope the authors can offer a simple analysis of the algorithm's time and space complexity in the rebuttal, considering real-world scenarios to show its impact on practical performance.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper makes a strong contribution to the literature on ML-based auction design. The paper introduces a novel method to the mixing demand and value queries in combinatorial auctions, which induces in practice a very natural transition between the two. The reviewers appreciated the theoretical and empirical contributions of the work, and all were supportive of acceptance. That said, the reviewers had a number of valuable suggestions on the paper, including on the overall perspective, that the authors should incorporate in any revision.
Decision: Accept (oral)