Monotone-Value Neural Networks: Exploiting Preference Monotonicity in Combinatorial Assignment

1 Introduction

Many important economic problems involve the combinatorial assignment of multiple indivisible items to multiple agents. In domains with money

combinatorial auctions (CAs) and combinatorial exchanges (CEs). In CAs, heterogeneous items are allocated amongst a set of bidders, e.g. for the sale of spectrum licenses [Cramton, 2013]. In CEs, a set of items is allocated between multiple agents who can be sellers and buyers at the same time, e.g. for the reallocation of catch shares [Bichler et al., 2019]. In domains without money, a popular example is combinatorial course allocation, where course seats are allocated to students at large business schools [Budish, 2011].

* Full paper including appendix available at arXiv: https://arxiv. org/abs/2109.15117.

† These authors contributed equally to this paper.

What all of these domains have in common is that the agents can report their values on bundles of items rather than only on individual items. This allows them to express more complex preferences, i.e., an agent's valuation of a bundle is not simply the sum of each individual item's value, but it can be more (complementarity) or less (substitutability). However, since the bundle space grows exponentially in the number of items, agents cannot report values for all bundles in settings with more than a modest number of items. Thus, parsimonious preference elicitation is key for the design of practical combinatorial assignment mechanisms.

In this paper, we present a new machine learning approach that exploits prior (structural) knowledge about agents' preferences and can be integrated well into iterative market mechanisms. Our contribution applies to any combinatorial assignment problem. However, we present our algorithms in the context of a CA specifically, to simplify the notation and because there exist well-studied preference generators for CAs that we can use for our experimental evaluation.

For CAs with general valuations, Nisan and Segal [2006] have shown that exponential communication in the number of items is needed in the worst case to find an optimal allocation of items to bidders, i.e., to ensure full efficiency. Thus, for general valuations, practical CAs cannot provide efficiency guarantees in large domains. In practice, iterative combinatorial auctions (ICAs) are employed, where the auctioneer interacts with bidders over multiple rounds, eliciting a limited amount of information, aiming to find a highly efficient allocation. ICAs are widely used; e.g., for the sale of licenses to build offshore wind farms [Ausubel and Cramton, 2011]. The provision of spectrum licenses via the combinatorial clock auction (CCA) [Ausubel et al., 2006] has generated more than $20 billion in total revenue [Ausubel and Baranov, 2017]. Therefore, increasing the efficiency of such real-world ICAs by only 1% point translates into monetary gains of hundreds of millions of dollars.

1.1 ML-based Auction Design

In recent years, researchers have successfully integrated machine learning (ML) algorithms into the design of CAs to improve their performance. D¨utting et al. [2019] and Rahme et al. [2021] used neural networks (NNs) to learn entire auction mechanisms from data, following the automated mechanism design paradigm. Brero et al. [2019] studied a Bayesian ICA using probabilistic price updates to achieve faster convergence to an efficient allocation.

Most related to this paper is the work by Brero et al. [2018; 2021], who developed a value-query-based ICA that achieves even higher efficiency than the widely used CCA. In followup work, Weissteiner and Seuken [2020] extended their work by integrating Neural Networks (NN) in their mechanisms and could further increase the efficiency. Finally, Weissteiner et al. [2022] used Fourier transforms (FTs) to leverage different notions of sparsity of value functions in preference elicitation. However, despite these advances, it remains a challenging problem to find the efficient allocation while keeping the elicitation cost for bidders low. Even state-of-the-art approaches suffer from significant efficiency losses, highlighting the need for better preference elicitation algorithms.

We show in this paper that these limitations can be partially explained due to the usage of poor, non-informative ML-algorithms, which either do not include important prior domain knowledge or make too restrictive assumptions about the bidders' value functions. Brero et al. [2018; 2021] used support vector regressions (SVRs) with quadratic kernels which can only learn up to two way interactions between items and do not account for an important monotonicity property of bidders' value functions. While the fully-connected feed-forward NNs used by Weissteiner and Seuken [2020] are more expressive, they also do not account for this monotonicity property. In particular when operating with only a small number of data points (which is the standard in market mechanisms, because preference elicitation is costly), this can cause significant efficiency losses.

Over the last decade, major successes in ML were made by specialized NN architectures (e.g. Convolutional Neural Networks) that incorporate domain-specific prior knowledge to improve generalization [Bronstein et al., 2017]. With this paper, we follow the same paradigm by incorporating prior knowledge about monotone preferences into a NN architecture to improve generalization, which is key for a wellfunctioning preference elicitation algorithm.

Several other approaches for incorporating monotonicity into NNs have previously been proposed. However, for these architectures, it is not known how the NN-based winner determination problem (WDP) could be solved quickly or they have other limitations. Sill [1998] proposes only a shallow architecture which violates the normalization property. You et al. [2017] proposes a non-standard architecture, where it is unknown if the corresponding MILP formulation of the WDP is computationally feasible. Wehenkel and Louppe [2019] implement monotonicity by representing the target function as an integral of a NN and thus the WDP would result in a computationally infeasible MILP. Liu et al. [2020] train NNs with successively higher regularization until a MILP based verification procedure guarantees monotonicity. The repeated retraining and verification lead to high computational cost.

In contrast, our approach is particularly well suited for combinatorial assignment, because (i) our NN-based WDP

can be formulated as a succinct MILP and thus solved quickly and (ii) we propose a generic fully-connected feed-forward architecture with arbitrary number of hidden layers which can be trained efficiently.

1.2 Our Contribution

We make the following contributions:

1. We introduce monotone-value neural networks (MVNNs), a new class of NNs with a carefully chosen activation function (bReLU) and enforced constraints on the parameters such that they are normalized and fulfill a monotonicity property (Section 3). These MVNNs are specifically suited to model monotone (combinatorial) value functions in economic settings.
2. On a technical level, we provide the following two theorems (Section 3.1): First, we prove that MVNNs are universal in the class of monotone and normalized combinatorial value functions, i.e., one can represent any value function with arbitrarily complex substitutabilities and complementarities exactly as an MVNN. Second, we show how to formulate the MVNN-based WDP as a MILP, which is key to efficiently calculate optimal allocations.
3. We experimentally evaluate the learning performance of MVNNs vs. NNs in four different spectrum CA domains and show that MVNNs are significantly better at modelling bidders' combinatorial value functions (Section 4).
4. Finally, we experimentally investigate the performance of MVNNs vs. plain NNs when integrated into an existing ML-based ICA (MLCA) and compare them also to the FT-based method by Weissteiner et al. [2022]. We show that MVNNs lead to substantially smaller efficiency losses than existing state-of-the-art mechanisms (Section 5).

2 Preliminaries

In this section, we present our formal model and review the ML-based ICA by Brero et al. [2021].

2.1 Formal Model for ICAs

We consider a CA with n bidders and m indivisible items. Let N = {1, . . . , n} and M = {1, . . . ,m} denote the set of bidders and items, respectively. We denote with x ∈ X = {0, 1}m a bundle of items represented as an indicator vector, where xj = 1 iff item j ∈ M is contained in x. Bidders' true preferences over bundles are represented by their (private) value functions vi : X → R+, i ∈ N, i.e., vi(x) represents bidder i's true value for bundle x.

By a = (a1, . . . , an) ∈ X n we denote an allocation of bundles to bidders, where ai is the bundle bidder i obtains. We denote the set of feasible allocations by F = {a ∈ X n : ∑i∈N aij ≤ 1, ∀j ∈M }. We assume that bidders' have quasilinear utilities ui, i.e., for payments p ∈ Rn+, ui(a, p) = vi(ai)-pi. This implies that the (true) social welfare V (a) of an allocation a is equal to the sum of all bidders' values, i.e., V (a) = ∑i∈N ui(ai, pi) + uauctioneer(p) = ∑i∈N vi(ai) - pi + ∑i∈N pi = ∑i∈N vi(ai). We let a∗ ∈ argmaxa∈F V (a) be a social-welfare maximizing, i.e., efficient, allocation. The efficiency of any allocation a ∈ F is measured as V (a)/V (a∗ ).

An ICA mechanism defines how the bidders interact with the auctioneer and how the final allocation and payments are determined. We denote a bidder's (possibly untruthful) reported value function by ˆ vi : X → R+. In this paper, we consider ICAs that ask bidders to iteratively report their values ˆ vi(x) for particular bundles x selected by the mechanism. A set of L ∈ N reported bundle-value pairs of bidder i is denoted as Ri = {(x(l) , ˆ vi(x(l) ))}Ll=1 , x(l) ∈ X. Let R = (R1, . . . ,Rn) denote the tuple of reported bundlevalue pairs obtained from all bidders. We define the reported social welfare of an allocation a given R as ̂ V (a|R) := ∑i∈N: (ai,ˆ vi(ai))∈Ri ˆ vi(ai), where (ai, ˆ vi(ai)) ∈ Ri ensures that only values for reported bundles contribute. The final optimal allocation a∗R ∈ F and payments p(R) ∈ Rn+ are computed based on the elicited reports R only. More formally, the optimal allocation a∗R ∈ F given the reports R is defined as

As the auctioneer can generally only query each bidder i a limited number of bundles |Ri| ≤ Qmax (e.g., Qmax = 100), the mechanism needs a sophisticated preference elicitation algorithm, with the goal of finding a highly efficient final allocation a∗R with a limited number of value queries.

2.2 AMachine Learning-powered ICA

We now review the machine learning-powered combinatorial auction (MLCA) by Brero et al. [2021]. Interested readers are referred to Appendix A, where we present MLCA in detail.

MLCA proceeds in rounds until a maximum number of value queries per bidder Qmax is reached. In each round, a generic ML algorithm Ai is trained for every bidder i ∈ N on the bidder's reports Ri. Next, MLCA generates new value queries qnew = (qnew i )ni=1 with qnew i ∈ X \ Ri by solving a ML-based WDP qnew ∈ argmax a∈F ∑ i∈N Ai(ai).

The idea is the following: if Ai are good surrogate models of the bidders' true value functions then qnew should be a good proxy of the efficient allocation a∗ and thus provide the auctioneer with valuable information. Additionally, in a realworld MLCA, bidders' are always allowed to report values of further bundles that they deem potentially useful ("push"- bids). This mitigates the risk of bidders not getting asked the right queries. In our experiments, MLCA achieves already state-of-the-art results without making use of any "push"-bids (mathematically additional "push"-bids can only improve the results further).

At the end of each round, MLCA receives reports Rnew from all bidders for the newly generated queries qnew , and updates the overall elicited reports R. When Qmax is reached, MLCA computes an allocation a∗R that maximizes the reported social welfare (see Equation (1)) and determines VCG payments p(R) based on the reported values (see Appendix Definition B.1).

Remark 1 (IR, No-Deficit, and Incentives of MLCA). Brero et al. [2021] showed that MLCA satisfies individual rationality (IR) and no-deficit, with any ML algorithm Ai. Furthermore, they studied the incentive properties of MLCA; this is important, given that opportunities for manipulations might lower efficiency. Like all deployed spectrum auctions (including the CCA [Ausubel and Baranov, 2017]) MLCA is not strategyproof. However, Brero et al. [2021] argued that it has good incentives in practice; and given two additional assumptions, bidding truthfully is an ex-post Nash equilibrium in MLCA. Their analyses apply to MLCA using any ML algorithm, and therefore also to an MVNN-based MLCA. We present a more detailed summary of their incentive analysis in Appendix B.

3 Monotone-Value Neural Networks

In combinatorial assignment problems, value functions are used to model each agent's (reported) value for a bundle of items (ˆ vi : {0, 1}m → R+). However, while the bundle space grows exponentially with the number of items, the agents' value functions often exhibit useful structure that can be exploited. A common assumption is monotonicity:

This property is satisfied in many market domains. For example, in many CAs, bidders can freely dispose of unwanted items; in combinatorial course allocation, students can just drop courses they have been assigned. However, prior work on ML-based market design [Weissteiner and Seuken, 2020; Weissteiner et al., 2022; Brero et al., 2021] has not taken this property into account, which negatively affects the performance (see Sections 4 and 5).

For ease of exposition, we additionally assume that the value functions are normalized:

Note that this property is not required by our method and can be easily adapted to be any other fixed value, or to be a learned parameter. In the following, we denote with

the set of all value functions, that satisfy the normalization and monotonicity property. Next, we introduce MonotoneValue Neural Networks (MVNNs) and show that they span the entire set V. Thus, MVNNs are specifically suited to all applications with monotone value functions.

Definition 1 (MVNN). A MVNN N θ i : X → R+ for bidder i ∈ N is defined as

• Ki ∈ N is the number of layers (Ki - 2 hidden layers),
• ϕ0,t is our MVNN-specific activation function with cutoff t > 0, which we call bounded ReLU (bReLU): 2

1 We slightly abused the notation here by using sets instead of their corresponding indicator vectors as arguments of ˆ vi .

2 bReLUs have also been used in visual pattern recognition problems to enhance training stability (see Liew et al. [2016]).

• W i := (W i,k )Ki k=1 with W i,k ≥ 0 and bi := (bi,k )Ki k=1 with bi,k ≤ 0 denote a tuple of non-negative weights and non-positive biases of dimensions di,k ×di,k-1 and di,k , whose parameters are stored in θ = (W i , bi ). 3

For implementation details of MVNNs we refer to Appendix C.6. Unless explicitly stated, we consider from now on a cutoff of t = 1 for the bReLU, i.e., ϕ(z) := ϕ0,1(z) = min(1, max(0, z)). Next, we discuss the choice of bReLU.

Choice of bReLU (i) The constraints on theweights and biases enforce monotonicity of MVNNs (in fact for any monotone activation). (ii) For universality (see Theorem1) we need a bounded monotone non-constant activation, i.e., with ReLUs and our constraints one cannot express substitutabilities. (iii) for the MILP (see Theorem 2), we need a piecewise linear activation (e.g., with sigmoids we could not formulate a MILP). Taking all together, bReLU is the simplest bounded, monotone, non-constant, piecewise-linear activation (see Appendix Remarks C.2 and C.3 for a detailed discussion).

Remark 2. For applications where value functions are expected to be "almost" (but not completely) monotone, one can adapt MVNNs to only have soft monotonicity constraints by implementing the constraints on the weights and biases via regularization, e.g., ∑i,k,j,l max(0, -W i,k j,l ). This results in soft-MVNNs that can model non-monotone changes in some items if the data evidence is strong.

3.1 Theoretical Analysis andMILP-Formulation

Next, we provide a theoretical analysis of MVNNs and present a MILP formulation of the MVNN-based WDP.

Lemma 1. Let N θ i : X →R+ be aMVNN fromDefinition 1. Then it holds that N (W i ,bi ) i ∈ V for all W i ≥ 0 and bi ≤ 0.

We provide the proof for Lemma 1 in Appendix C.1. Next, we state our main theorem about MVNNs.

Theorem 1 (Universality). Any value function ˆ vi : X →R+ that satisfies (N) and (M) can be represented exactly as a MVNN N θ i fromDefinition 1, i.e.,

We present a constructive proof for Theorem 1 in Appendix C.3. In the proof, we consider an arbitrary (ˆ vi(x))x∈X ∈ V for which we construct a two hidden layer MVNN N θ i of dimensions [m, 2m - 1, 2m - 1, 1] with parameters θ = (W iˆ vi , biˆ vi ) such that N θ i (x) = ˆ vi(x) ∀x ∈ X .

Note that for q queries, it is always possible to construct MVNN of size [m, q, q, 1] that perfectly fits through the q data-points (see Appendix Corollary C.1). Thus, the worstcase required architecture size grows only linearly with the number of queries. In our experiments we already achieve very good performance with even smaller architectures. Example C.1 in the Appendix nicely illustrates how exactly MVNNs capture complementarities, substitutabilities and independent items.

3 We apply a linear readout map to the last hidden layer, i.e, no ϕ0,t and bi,Ki := 0. By setting bi,Ki ̸= 0 with trainable=False, the MVNN can model any other value than zero in the normalization property. By not restricting bi,k ≤ 0 and setting bi,Ki ̸= 0 with trainable=True one can also learn the value for the empty bundle.

A key step in combinatorial assignment mechanisms is finding the social welfare-maximizing allocation, i.e., solving the Winner Determination Problem (WDP). To use MVNNs in such mechanisms, we need to be able to efficiently solve MVNN-based WDPs. To this end, we present a MILP formulation of the MVNN-based WDP. The key idea is to rewrite the bReLU ϕ(z) as -max(-1, -max(0, z)) and encode for each bidder i, hidden layer k and neuron j both max(·, ·) operators with two binary decision variables yi,k j , µi,k j . First, we show how to encode one single hidden layer of an MVNN as multiple linear constraints. We provide the proof in Appendix C.4.

Lemma 2. Fix bidder i ∈ N, let k ∈ {2, . . . , Ki-1} and denote the pre-activated output of the kth hidden layer as oi,k := W i,k-1 zi,k-1 + bi,k-1 with W i,k-1 ∈ Rdik×dik-1 , bi,k-1 ∈ Rdik. Then the output of the kth hidden layer zi,k := ϕ(oi,k ) = min(1, max(0, oi,k )) = -max(-1, -ηi,k ), with ηi,k := max(0, oi,k ) can be equivalently expressed by the following linear constraints:

where Li,k 1 ,Li,k 2 ,Li,k 3 ,Li,k 4 ∈ R+ are large enough constants for the respective big-M constraints. 4

Finally, we formulate the MVNN-based WDP as a MILP.

Theorem 2 (MILP). The MVNN-based WDP max a∈F ∑i∈N N (W i ,bi ) i (ai) can be equivalently formulated as the following MILP: 5

s.t. for i ∈ N and k ∈ {2, . . . ,Ki - 1}

4 To account for a general cutoff t ̸= 1 in the bReLU, one needs to adjust (9) by replacing the left- and rightmost 1 with t.

5 To account for a general cutoff t ̸= 1 in the bReLU, one needs to adjust (17) by replacing the left- and rightmost 1 with t.

Proof. The proof follows by iteratively applying Lemma 2 for each bidder and all her respective hidden MVNN layers.

Fact 1. One can significantly reduce the solve time for the MILP by tightening the bounds of each neuron. In Appendix C.5, we present bound tightening via interval arithmetic (IA) [Tjeng et al., 2019] for MVNNs. For a plain ReLU NN, these IA bounds are not tight and calculating tighter bounds in a computationally efficient manner is very challenging. In contrast, the MVNN-IA bounds are always perfectly tight, because of their encoded monotonicity property. The upper and lower bound of a neuron is the value the neuron outputs for the input (1, . . . , 1) and (0, . . . , 0). This is a big advantage of MVNNs compared to plain (ReLU) NNs.

Remark 3 (MVNNs as Preference Generator). To experimentally evaluate a new mechanism one needs to generate many different possible value functions. Preference generators like the Spectrum Auction Test Suite [Weiss et al., 2017] are carefully designed to capture the essential properties of spectrum auctions, but they are not available for every application. Instead of using such a domain-specific preference generator, one can also use MVNNs with randomly initialized weights to generate possible value functions. An advantage of random MVNNs is that they are universal (see Theorem 1) and hence come with a diversity rich enough to sample any possible monotone value function with arbitrarily complex substitutabilities and complementarities (the distribution of supplements and complements can be controlled via the cutoff t, where the smaller/larger t the more substitutabilities/complementarities). These types of generative test beds become increasingly important to avoid overfitting on specific simulation engines and/or real data sets [Osband et al., 2021].

4 Prediction Performance of MVNNs

In this section, we show that in all considered CA domains, MVNNs are significantly better at capturing bidders' complex value functions than plain (ReLU) NNs, which allows them to extrapolate much better in the bundle space.

4.1 Experimental Setup - Prediction Performance

CA Domains In our experiments we use simulated data from the Spectrum Auction Test Suite (SATS) version 0.7.0 [Weiss et al., 2017]. We consider the following four domains:

• Global Synergy Value Model (GSVM) [Goeree and Holt, 2010] has 18 items, 6 regional and 1 national bidder.
• Local Synergy Value Model (LSVM) [Scheffel et al., 2012] has 18 items, 5 regional and 1 national bidder. Complementarities arise from spatial proximity of items.
• Single-Region Value Model (SRVM) [Weiss et al., 2017] has 29 items and 7 bidders (categorized as local, high frequency regional, or national) and models large UK 4G spectrum auctions.
• Multi-Region Value Model (MRVM) [Weiss et al., 2017] has 98 items and 10 bidders (local, regional, or national) and models large Canadian 4G spectrum auctions.

When simulating bidders, we follow prior work (e.g., [Brero et al., 2021]) and assume truthful bidding (i.e., ˆ vi = vi). Details on how we collect the data and the train/val/test split can be found in Appendix D.1.

HPO To efficiently optimize the hyperparameters and fairly compare MVNNs and plain NNs for best generalization across different instances of each SATS domain, we frame the hyperparameter optimization (HPO) problem as an algorithm configuration problem and use the well-established sequential model-based algorithm configuration (SMAC) [Hutter et al., 2011]. SMAC quickly discards hyperparameters which already perform poorly on a few SATS instances and proposes more promising ones via Bayesian optimization. It is flexible enough for the parameterization of NNs as it naturally handles a mixture of categorical, integer and float hyperparameters. Further details on the setting including hyperparameter ranges can be found in Appendix D.2.

4.2 Prediction Performance Results

For ease of exposition, we only present our results for the MVNN-RELU-PROJECTED implementation of our MVNNs (termed MVNN in the following). Results for other MVNN implementations can be found in the Appendix D.3. In Table 1, we compare the prediction performance of the winning models that the HPO found for different amounts of training data (T) on the test data. We see that, compared to plain

0.917 ±0.017 0.847 ±0.010 0.851 ±0.019 0.809 ±0.012

Table 1: Prediction performance measured via R-squared (R2 ) and Kendall tau (KT) with a 95%-CI in four SATS domains with corresponding bidder types: high frequency (H.F.), local (LO), regional (REG) and national (NAT), averaged over 30 auction instances. Both MVNNs and plain NNs are trained on T and evaluated on 209 715 - T random bundles. Winners are marked in grey.

NNs, MVNNs provide both a significantly better fit in terms of R-squared R2 as well as a better Kendall Tau rank correlation KT (i.e., a better ordinal ranking). Thus, enforcing the monotonicity property in MVNNs significantly improves the learning performance.

Figure 1 illustrates our findings by providing a visual comparison of the prediction performance for the highly nonunimodal SRVM. 6 We see that the MVNN fits the training data exactly (blue crosses), although the HPO only optimized generalization performance on the validation data. This is a strong indication that MVNNs correspond to a more realistic prior, since for a realistic prior, it is optimal to exactly fit the training data in noiseless settings [Heiss et al., 2021, Proposition D.2.a]. In contrast, the HPO has selected hyperparameters for the plain NNs that result in a worse fit of the training data (otherwise generalization to unseen data would be even worse). Moreover, the plain NNs show a particularly bad fit on the less frequent lower and higher valued bundles.

5 MVNN-powered Iterative CA

To evaluate the performance of MVNNs when used inside a combinatorial market mechanism, we have integrated MVNNs into MLCA (see Section 2.2), yielding an MVNNpowered Iterative CA. In this section, we compare the economic efficiency of our MVNN-based MLCA against the previously proposed NN-based MLCA. For solving the MVNNbased WDPs in MLCA, we use our MILP from Theorem 2.

5.1 Experimental Setup - MLCA

To generate synthetic CA instances, we use the same four SATS domains as in Section 4. SATS also gives us access to the true optimal allocation a∗ , which we use to measure the efficiency loss, i.e., 1 - V (a∗R)/V (a∗ ) and relative revenue ∑i∈N p(R)i/V (a∗ ) of an allocation a∗R ∈ F and payments p(R) ∈ Rn+ determined by MLCA when eliciting reports R. Due to the long run-time of a single evaluation of MLCA , we perform a restricted HPO, which, for each domain, only uses the winners of the prediction performance experiment (Table 1) for the three amounts of training data T. This is a reasonable choice, because in the prediction performance we optimize the generalization performance for bidders' value functions that is also key in MLCA.

6 We provide corresponding plots for the other domains and bidder types in Appendix D.3; the results are qualitatively similar.

For each domain, we use Qinit = 40 initial random queries and set the query budget to Qmax = 100. We terminate MLCA in an intermediate iteration if it already found an efficient allocation (i.e., with 0 efficiency loss).

5.2 Efficiency Results

In Table 2, we present the efficiency results of MVNN-based MLCA and NN-based MLCA, averaged over 50 auction instances. We focus on efficiency rather than revenue, since spectrum auctions are government-run auctions with a mandate to maximize efficiency and not revenue [Cramton, 2013]. In Appendices E.2 and E.3 we also present and discuss detailed revenue results.

For each domain, we present results corresponding to the best MVNNs and NNs amongst the three incumbents obtained from the prediction performance experiments. We present results for all three incumbents in Appendix E.2. Overall, we see that the better prediction performance of MVNNs (Table 1) translates to smaller efficiency losses in MLCA. In LSVM and SRVM, MVNNs significantly outperform NNs and have a more than four times lower efficiency loss. In MRVM, MVNN's average efficiency loss is approximately 1% point smaller than the NN's loss. Given that in the 2014 Canadian 4G auction the total revenue was on the order of 5 billion USD [Ausubel and Baranov, 2017], an efficiency loss decrease of 1% point in MRVM can translate to welfare gains on the order of 50 million USD. Finally, in GSVM, the simplest domain, where bidders' value functions have at most two-way interactions between items, both MVNNs and plain NNs incur no efficiency loss. As further baselines, we evaluate the Fourier transform (FT) auction [Weissteiner et al., 2022] using their proposed optimal hyperparameters and random search (RS). We do not compare to SVRs [Brero et al., 2021] since they were already outperformed by plain NNs in [Weissteiner and Seuken, 2020]. We observe that RS incurs efficiency losses of 30-50% illustrating the need for smart preference elicitation. Moreover, we see that MVNNs also significantly outperform FTs in all domains.

In Figure 2, we present the efficiency loss path of MVNNs vs NNs (i.e., the regret curve) corresponding to Table 2. We see that in LSVM and SRVM, MVNNs lead to a smaller (average) efficiency loss for every number of queries. In MRVM, the same holds true for 50 and more queries. In GSVM, both networks have no efficiency loss in every instance after only 56 queries. Since a single query can be very costly in realworld CAs, it makes sense to ask few queries. Figure 2 shows that MVNNs consistently outperform plain NNs also in settings with a small number of queries (i.e., reduced Qmax )

5.3 MILP Runtime Analysis

When integrating MVNNs into MLCA or another iterative combinatorial assignment mechanism, one needs to solve the MVNN-based WDP multiple times in one full run. Thus, the key computational challenge when integrating MVNNs in such mechanisms is to efficiently solve the MVNN-based WDP. In Theorem 2, we have shown how to encode the MVNN-based WDP as a succinct MILP, which can be solved efficiently for moderate architectures sizes. However, due to the bReLU activation function, i.e., the two cutoffs at 0 and t > 0, the MVNN-based MILP has twice the number of binary variables (yi,k and µi,k ) than the MILP encoding of a plain NN with ReLUs [Weissteiner and Seuken, 2020].

Figure 3 presents MILP runtimes of MVNNs vs plain ReLU NNs for selected architectures. We observe two effects: First, even though the MVNN-based MILPs have twice the number of binary variables, they can be solved faster than the plain NN-based MILPs for all architectures. Second, the deeper the architecture or the more neurons, the larger this difference becomes. One possible explanation for both effects is that MVNNs are more regular than plain NNs (due to their monotonicity property) and are thus easier to optimize.

6 Conclusion

In this paper, we have introduced MVNNs, a new class of NNs that is specifically designed to model normalized and monotone value functions in combinatorial assignment problems. We have experimentally evaluated the performance of MVNNs in four combinatorial spectrum auction domains and shown that MVNNs outperform plain NNs with respect to prediction performance, economic efficiency, and runtime. Overall, our experiments suggest that MVNNs are the best currently available model for preference elicitation in combinatorial assignment (also compared to FTs and SVRs). Thus, incorporating important structural knowledge in the ML algorithm plays an important role in combinatorial assignment.

MVNNs enable us to incorporate an informative prior into a market mechanism. Future work could use such informative priors and enhance existing mechanisms (e.g., MLCA) by also using the posterior estimates in a more principled way than just the mean prediction. For example, one could frame an ICA as a (combinatorial) Bayesian optimization task and integrate a well-defined notion of posterior uncertainty to foster exploration [Heiss et al., 2021]. Finally, it would be interesting to also evaluate the performance of MVNNs in other combinatorial assignment problems such as course allocation.

Acknowledgments

We thank the anonymous reviewers for helpful comments. This paper is part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (Grant agreement No. 805542).