Combinatorial Auctions via Machine Learning-based Preference Elicitation

1 Introduction

Combinatorial auctions (CAs) are used to allocate multiple items among bidders who may view these items as complements or substitutes. Specifically, they allow bidders to submit bids on bundles of items to express their complex preferences. CAs have found widespread real-world applications, including for the sale of spectrum licenses [Cramton, 2013] and the allocation of TV-ads slots [Goetzendorf et al., 2015].

One of the main challenges when conducting CAs in practice is that the bundle space grows exponentially in the number of items, which typically makes it impossible for the bidders to report their full value function. Practical CA designs address this problem by allowing bidders to report a limited number of bids which are treated as "all-or-nothing" bundle bids by the auctioneer (see, e.g., Ausubel and Baranov [2017]). This number can be very small compared to the total number of bundles. For example, in the 2014 Canadian spectrum auction [Industry Canada, 2013], bidders were only allowed to bid on 500 out of the 298 possible bundles.

1.1 Selecting Bundles to bid on in CAs

To help bidders select which bundles to bid on, most fielded CAs (such as the Combinatorial Clock Auction (CCA) [Ausubel and Baranov, 2017]), include an iterative elicitation phase where prices are used to coordinate the bidding process: as each ask price is quoted, bidders are asked to respond to a demand query, i.e., to state their profit-maximizing bundle at the quoted prices. However, multiple experimental studies have shown that bidders may not be able to accurately respond to this type of query as this may require full exploration of their exponentially-sized value space. In particular, Scheffel et al. [2012] and Bichler et al. [2013] have shown that bidders tend to focus on a limited search space consisting of some bundles of items selected prior to the auction, and that this can cause significant inefficiencies. Furthermore, most auctions (e.g., the CCA) use anonymous linear prices for their elicitation, but to guarantee efficiency, the auction may require an exponential number of personalized bundle prices [Nisan and Segal, 2006]. Notionally, one can view the mechanism we propose as similar to the CCA. However, while in the CCA prices do the job of coordinating bidders towards finding an efficient allocation, in our approach, a machine learning-based elicitation algorithm serves this role.

1.2 Machine Learning to the Rescue

Accordingly, our first contribution in this paper is a new elicitation paradigm that uses machine learning (ML) to identify which values to query from the bidders. As our elicitation algorithm asks bidders to only explore a very small part of their value space, we cannot provide efficiency guarantees upon termination. However, our elicitation approach achieves high average efficiency in our experimental evaluation.

Since values are bidders' private information, we must also incentivize bidders to truthfully reveal enough of these values to determine an efficient allocation. When bidders can report their complete valuations, this can be achieved by using the well-known VCG mechanism [Vickrey, 1961; Clarke, 1971; Groves, 1973]. VCG is strategyproof, i.e., under VCG, bidders have a dominant strategy to report their true valuations. Unfortunately, the attractive incentive properties of VCG cannot be extended straightforwardly to scenarios where values are iteratively elicited and where bidders can (indirectly) affect which values are asked from the others. To address this, and inspired by an elicitation technique based on multiple price trajectories (see, e.g., Ausubel [2006]), we design a mechanism that invokes our elicitation algorithm multiple times to derive payments that are closely related to VCG payments. We refer to this mechanism as the pseudo-VCG mechanism (PVM). While PVM is not strategyproof, we prove that it aligns bidders' incentives with allocative efficiency.

Elicitation approaches based on ML date back to the early 2000s. Using techniques from computational learning theory, Lahaie and Parkes [2004] and Blum et al. [2004] identified classes of valuations for which effective elicitation methods exist that lead to an efficient allocation. Elicitation approaches based on ML for generic valuations were introduced by Lahaie [2011] and further developed by Lahaie and Lubin [2017]. These approaches are based on using ML to find effective ask prices that properly coordinate bidders towards efficient allocations. Similarly, Brero and Lahaie [2018] proposed an elicitation approach based on Bayesian principles that integrates prior knowledge about bidders' values to speed up the search for these ask prices.

In contrast to the pre-dominant research agenda in this field, we previously used ML to directly reason about bidders' valuations [Brero et al., 2017]. In that paper, we specified an allocation rule based on predicted social welfare, but we did not consider incentives or payments. The present paper is closely related in that we also do not use ask prices and instead employ value queries. However, in this work, we only use the ML algorithm to guide our elicitation algorithm, aiming to elicit the most useful information from the bidders. In contrast to our prior work [Brero et al., 2017], we do not compute the final allocation based on predicted valuations. While subtle, this difference turns out to have important incentive implications. Finally, in many domains, the process of valuing even a single bundle can be a costly exercise for bidders (see, e.g., Parkes [2006]). To address this, we also show how our elicitation paradigm can be used effectively in scenarios where, instead of reporting their exact values, bidders only report upper and lower bounds on values.

2 Formal Model

In a combinatorial auction (CA), there is a set of m indivisible items being auctioned off to n bidders. We refer to the set of items together with the set of bidders as the setting of the CA. We use notation [n] = {1, ..., n}, so that [n] and [m] denote the index sets of the bidders and the items, respectively. A bundle is a subset of the set of items. We associate each bundle with its indicator vector and denote the set of bundles as X = {0, 1}m. We represent the preferences of each bidder i with a value function vi : X → R≥0 that is private knowledge of the bidder. Thus, for each bundle x ∈ X , vi(x) represents the true value that bidder i has for obtaining x.

In this paper, we design a CA that ask bidders to report their value for particular bundles (i.e., we use value queries). Based on the reported values, our CA determines an allocation and charges payments. An allocation is a vector of bundles a = (a1, . . . , an), with ai being the bundle that bidder i obtains. An allocation is feasible if each item is allocated to at most one bidder. We denote the set of feasible allocations by F. Payments are defined as a vector p = (p1, ..., pn) ∈ Rn , with pi denoting the amount charged to bidder i.

We assume that bidders have quasi-linear utilities, i.e., bidder i's utility for bundle x at price pi is vi(x)-pi. We let v = (v1, . . . , vn) denote the vector of bidders' value functions and v-i = (v1, . . . , vi-1, vi+1, . . . , vn) the corresponding vector where bidder i is excluded. The social welfare of an allocation a is the sum of the the bidders' values for a, V (a) = ∑i∈[n] vi(ai). The social welfare-maximizing (i.e., efficient) allocation is denoted as a∗v ∈ arg maxa∈F V (a). We measure the efficiency of any allocation a as V (a)/V (a∗v ).

In the present work, we do not ask bidders to reveal their whole value function vi(·). Instead, we ask bidders to report values for a small subset of the bundles. 1 We let ˆ vi(x) denote bidder i's (possibly non-truthful) report on bundle x. We let ˆ ϑi denote a generic set of such bundle-value pairs (which we also refer to as value reports) reported by bidder i. For notational simplicity, we say that x ∈ ˆ ϑi if (x, ˆ vi(x)) ∈ ˆ ϑi. We let ˆ ϑ = (ˆ ϑ1, . . . , ˆ ϑn) denote the vector of these sets. Given two vectors ˆ ϑ and ˆ ϑ′ , we say that ˆ ϑ ⊆ ˆ ϑ′ if, for each i ∈ [n], ˆ ϑi ⊆ ˆ ϑ′i . Given a set of reports ˆ ϑ, we define the reported social welfare in an allocation a as ˆ V (a; ˆ ϑ) = ∑i∈[n]:ai∈ˆ ϑi ˆ vi(ai). The optimal allocation with respect to ˆ ϑ is denoted a∗ˆ ϑ ∈ argmaxa∈F ˆ V (a; ˆ ϑ). Note that, without loss of generality, we can always assume that a∗ˆ ϑ consists of bundles contained in ˆ ϑ. Furthermore, for any ˆ ϑ ⊆ ˆ ϑ′ , we have that ˆ V (a∗ˆ ϑ ; ˆ ϑ) ≤ ˆ V (a∗ˆ ϑ′ ; ˆ ϑ′ ). Finally, we let M denote a generic CA mechanism, consisting of (1) a procedure to determine an allocation and (2) a payment rule.

3 Machine Learning-based Elicitation

The key innovation of the auction design we propose in this paper is the use of an elicitation method (querying values from the bidders) that is powered by a machine learning algorithm. An elicitation method is a (possibly iterative) procedure to obtain a vector of reports ˆ ϑ from the bidders. In a mechanism one may use multiple runs of different parameterizations of an elicitation method. We will make use of this technique in the design of our mechanism in Section 4.1.

As the elicitation method of our CA, we now introduce our ML-based elicitation algorithm. This algorithm is parametrized by an ML algorithm A that, given a vector of bundle-value pairs ˆ ϑ, outputs a function ˜ V = A(ˆ ϑ), which provides us with an estimate of the social welfare ˜ V (a) for each allocation a. In Section 5, we will instantiate A via support vector regression algorithms.

We present our elicitation algorithm in Algorithm 1. We start from a vector ˆ ϑ0 of values reported by the bidders (Line 1). Each set of initial values ˆ ϑ0i can either be selected by the algorithm or by bidder i. At each round t, the algorithm applies A to the bundle-value pairs ˆ ϑt-1 to obtain the inferred social welfare function ˜ V t (Line 4), and then it computes the corresponding optimal allocation at (Line 5). If all values for

1 We ensure that a bidder never reports a value for a given bundle twice.

Parameter: Machine learning algorithm A 1 ˆ ϑ0 = initial vector of values, t = 0 2 do 3 t ← t + 1 4 Infer social welfare function ˜ V t = A(ˆ ϑt-1 ) 5 Determine allocation at ∈ argmaxa∈F ˜ V t (a; ˆ ϑt-1 ) 6 for each bidder i do 7 if ati /∈ ˆ ϑt-1 i then 8 Query value ˆ vi(ati ) 9 ˆ ϑti = ˆ ϑt-1 i ∪ (ati , ˆ vi(ati )) 10 else 11 ˆ ϑti = ˆ ϑt-1 i 12 end 13 end 14 while ∃i ∈ [n] : ati /∈ ˆ ϑt-1 i 15 Output final set of bundle-value pairs ˆ ϑT , where T = t

the bundles in at have already been queried and are thus contained in ˆ ϑt-1 , then the elicitation stops (Line 14). Otherwise, the algorithm queries these values (Line 8), and iterates.

Note that Algorithm 1 is agnostic to the ML algorithm A used in Line 4. However, it is intuitive that the higher the accuracy of A the higher the efficiency of the allocation determined by the elicitation algorithm. Proposition 1 formalizes this relationship between the inference error of the inferred social welfare function ˜ V t at any round t and the efficiency of the allocation determined by the elicitation algorithm:

Proposition 1. Assume that bidders report their true values. Then, for any t, the following holds:

Proof. By the end of round t, the values of all bundles in at will have been queried by the algorithm and thus will be contained in ˆ ϑt by construction. We then have that ˆ V (at ; ˆ ϑt ) ≤ ˆ V (a∗ˆ ϑt ; ˆ ϑt ). Furthermore, as ˆ ϑt ⊆ ˆ ϑT , we have that ˆ V (a∗ˆ ϑt ; ˆ ϑt ) ≤ ˆ V (a∗ˆ ϑT ; ˆ ϑT ). Putting the two inequalities together, we obtain ˆ V (at ; ˆ ϑt ) ≤ ˆ V (a∗ˆ ϑT ; ˆ ϑT ). Under the assumption that bidders report their true values, we can replace ˆ V (at ; ˆ ϑt ) with V (at ) and ˆ V (a∗ˆ ϑT ; ˆ ϑT ) with V (a∗ˆ ϑT ) to obtain

Next, because ˜ V t (·) is optimal at at , some algebra yields:

Inequality (1) follows from inequalities (2) and (3).

In words, Proposition 1 shows that the efficiency loss attributable to the ML algorithm A is bounded by the sum of the inference errors at at and a∗v at any round t.

We can gain additional insight about the possible efficiency loss by considering the special case when the ML algorithm A is always accurate at the reported bundle-value pairs (i.e., the ML algorithm has no in-sample error). When Algorithm 1 terminates, the values for aT will be contained in ˆ ϑT-1 . With the assumption that we have no in-sample error, we can now argue that ˜ V T (aT ) - V (aT ) = 0. We can now use Proposition 1 to obtain V (a∗v ) - V (a∗ˆ

V T (a∗v ) is guaranteed to be less than or equal to V (a∗v ) because the left-hand-side of the inequality is always positive. Thus, at termination, any efficiency loss in the outcome is bounded by the underestimation of V (a∗v ) by the ML algorithm at time T .

ϑT ) ≤ V (a∗v ) - ˜ V T (a∗v ). Note that ˜

Remark 1. Note that Algorithm 1 corresponds to the elicitation approach we presented in our prior work [Brero et al., 2017, Algorithm 2], except for one small generalization. Algorithm 2 of the earlier work enforced the inferred social welfare to be constructed as the sum of n independent value functions, i.e. ˜ V t = ∑i ˜ vt i , while we do not require this for Algorithm 1. If the same structure were imposed on Algorithm 1, then both algorithms would query the same values.

4 The Combinatorial AuctionMechanism

In this section, we describe our CA mechanism. We show how our ML-based elicitation algorithm can be used as a subroutine to design a mechanism that aligns bidders' incentives with allocative efficiency. This means that, for each bidder i, a strategy that maximizes bidder i's utility also maximizes the social welfare with respect to her true valuation and the other bidders' (possibly non-truthful) reports.

More formally, we assume that, under a generic auction mechanismM, each bidder i reports her values according to a strategy σi. Let σ = (σ1, .., σn) denote the vector of these strategies. We use aM = aMσ and pM = pMσ to denote the allocation and the payments determined by M under strategies σ, respectively. For each bidder i, we let uMi = uMi,σ be the bidder's utility under σ. With this, we can define:

Definition 1 (Incentive Alignment). A mechanismMaligns bidders' incentives with allocative efficiency if, for each i ∈ [n], and for every configuration of strategies σ-i for the bidders other than i, the following holds:

VCG achieves incentive alignment by letting bidders report their values in one shot. Given reports ˆ ϑ, VCG allocates items according to avcg = a∗ˆ ϑ , and charges each bidder i payment pvcg i = ∑j̸=i ˆ vj (a∗ˆ ϑ-i )- ∑j̸=i ˆ vj(avcg ). Thus, the utility of bidder i under VCG is:

As bidder i cannot affect the third term, i.e., ∑j̸=i ˆ vj (a∗ˆ ϑ-i ), her optimal strategy must maximize the first two terms, thus satisfying incentive alignment. In addition to aligning incentives, VCG is also strategyproof, i.e., every bidder maximizes her utility by reporting all of her true values, independent of the other bidders' behavior.

Algorithm 2: Pseudo-VCG Mechanism (PVM)

• 1 Run Algorithm1 n+1 times to get ˆ ϑ(-∅), ˆ ϑ(-1), ..., ˆ ϑ(-n).
• 2 Let ˆ ϑ⋆ = ∪i∈[n] ˆ ϑ(-i) ∪ ˆ ϑ(-∅) .
• 3 Determine allocations a(-∅) , a(-1) ,. . . , a(-n) .
• 4 Allocate items according to

. 5 Charge each bidder i according to:

However, when we use an iterative elicitation process, the good incentive properties of VCG cannot be extended straightforwardly because each bidder i can (indirectly) affect which values are queried from the other bidders. Thus, if we want incentive alignment, we need to be more careful about elicitation and about computing allocations and payments.

4.1 Pseudo-VCGMechanism

We now introduce the Pseudo-VCG Mechanism (PVM). The key idea is to use several runs of our ML-based elicitation algorithm to construct a mechanism that exhibits incentive alignment. The approach is closely related to VCG, but to remove the indirect effect that each bidder i might have on the term ∑j̸=i ˆ vj (a∗ˆ ϑ-i ), PVM computes each such term via a separate run of the elicitation algorithm.

See Algorithm 2 for the details of PVM. In Step 1, PVM runs the elicitation algorithm (Algorithm 1) n+1 times, once in the setting including all bidders (resulting in reports ˆ ϑ(-∅) ), and once in each of the n settings where one of the bidders has been excluded, resulting in ˆ ϑ(-i) . 2 In Step 2, PVM computes ˆ ϑ⋆ , i.e., the union of the reports from all n + 1 elicitation runs. In Step 3, PVM computes the optimal allocations for each run based on the corresponding reports, i.e., a(-∅) based on ˆ ϑ(-∅) , a(-1) based on ˆ ϑ(-1) , and so on. In Step 4, PVM chooses the final allocation apvm from among those allocations to maximize the reported social welfare based on ˆ ϑ⋆ . In Step 5, payments are calculated according to Equation (7).

4.2 Incentive Analysis

We have the following Proposition:

Proposition 2. Under PVM, bidders' incentives are aligned with allocative efficiency.

Proof. The utility of bidder i under PVM is

2 We use the "(-i)" notation in ˆ ϑ(-i) and a(-i) to denote the reports and allocations that result from a separate run of our elicitation algorithm. Note the difference from the standard subscript "-i" notation (e.g., ˆ ϑ-i) which denotes exclusion of bidder i from a vector.

As bidder i's reports cannot affect ∑j̸=i ˆ vj(a(-i) ), she maximizes her utility by maximizing vi(apvm) + ∑j̸=i ˆ vj (apvm), which is aligned with allocative efficiency.

However, PVM is not strategyproof. A bidder may be able to increase her utility by misreporting her values to increase ∑j̸=i ˆ vj(apvm). This is illustrated in the following example:

Example 1. Consider a setting with n = m = 2, and suppose we use an ML algorithm A that infers the social welfare as ˜ V = ˜ v1 + ˜ v2. Additionally, assume that each ˜ vi is derived from the reported values via 2d linear regression. Assume that bidder 1's true values are v1(1, 0) = v1(0, 1) = v1(1, 1) = 0.5, and that bidder 2's true values are v2(1, 0) = 0 and v2(0, 1) = v2(1, 1) = 2. Assume that bidder 2 reports truthfully. Suppose that the mechanism first queries bundle (1, 1) from bidder 2 receiving report ˆ v2(1, 1) = 2, thus inferring values ˜ v2(1, 0) = ˜ v2(0, 1) = 1. If now bidder 1 reports any of her true values, PVM allocates bundle (1, 1) to bidder 2 and the utility of bidder 1 is 0. In contrast, if bidder 1 instead reports a value of 1.1 for the bundle (1, 0), then the mechanism next queries bidder 2's value for (0, 1) (i.e., the optimal allocation according to ˜ V ) and determines a final allocation where 1 wins (1, 0) and 2 wins (0, 1). Thus, as her utility is now 0.5 (because her PVM payment would be 0), bidder 1 has benefited from her misreport.

Observe that the reason for the beneficial misreport for bidder 1 is that the ML algorithm does not accurately infer bidder 2's values. Informally, this generalizes as: the better the ML algorithm, the smaller the incentive for bidders to manipulate. To formalize this idea, we introduce the following concepts: we say that a bidder has complete information when she knows all other bidders' values and their strategies. A bidder has perfect information when she knows exactly all of the rules governing the execution of the mechanism (including all random numbers that will be used).

Proposition 3. Let ˜ V t be the social welfare function inferred by PVM at round t of the elicitation run in the setting including all bidders, and let at be its corresponding optimal allocation. If the other bidders report their true values, then the ex post regret r under complete and perfect information of any bidder reporting truthfully satisfies

Proof. Let τ be any configuration of strategies where all bidders are reporting truthfully. From Equation (8) we have that the utility of any bidder i under this configuration of strategies is V (apvm τ ) - ∑j̸=i ˆ vj (a(-i) τ-i ), where a(-i) τ-i is the allocation determined by the elicitation run excluding bidder i. Since the other bidders are truthful, the maximum utility achievable by bidder i cannot be greater than V (a∗v ) - ∑j̸=i ˆ vj (a(-i) τ-i ). Thus, under any kind of information setting, the ex post regret r of any bidder reporting truthfully satisfies r ≤ V (a∗v ) - V (apvm τ ). From the definition of apvm τ we have that V (a∗v ) - V (apvm τ ) ≤ V (a∗v ) - V (a(-∅) τ ). Since all bidders report their true values, we can apply Proposition 1 to bound V (a∗v ) - V (a(-∅) τ ), which concludes the proof.

In words, Proposition 3 says that, the better the performance of the ML algorithm, the lower the regret for reporting truthfully. Moreover, recall from our discussion of Proposition 1 that, when the elicitation run terminates, the values for aT are contained in ˆ ϑT-1 . Thus, if A has no in-sample error, then the regret bound simplifies to r ≤ V (a∗v )- ˜ V T (a∗v ). Then, any regret from reporting truthfully is bounded by the underestimation of V (a∗v ) in round T (in the setting including all bidders).

Remark 2. Note that the regret is bounded in terms of social welfare and not in terms of bidders' individual values, which makes the bound relatively weak in practice. However, also note that we derived Proposition 3 for the complete and perfect information setting. The manipulation in Example 1 also relies on bidders being fully informed about the auction process. In practice, one can make the auction more robust against manipulations by limiting information sharing. For example, one can isolate the bidders during the auction by performing all n + 1 elicitation runs in parallel and communicating to each bidder only the set of bundles that she should evaluate at each step.

4.3 Individual Rationality

A mechanism is individually rational if each bidder's payment is less than or equal than this bidder's reported value for her final allocation. We can show:

Proposition 4. PVM satisfies individual rationality.

Proof. We show that, for each i: ˆ vi(apvm)-ppvm i ≥ 0. From the definition of the PVM payment rule this is equivalent to ∑j∈[n] ˆ vj(apvm)- ∑j̸=i ˆ vj(a(-i) ) ≥ 0. This holds because apvm is chosen from a(-∅) , a(-1) , ..., a(-n) so as to maximize the reported social welfare (Equation 6).

4.4 No Deficit

Ideally, a mechanism stipulating transfers between its participants and the center should not run at a deficit. Unfortunately, PVM does not guarantees the no deficit property, without further alteration. From Equation (7) we note that each payment ppvm i is expected to be positive because the allocation a(-i) is derived as an optimal allocation for the setting excluding bidder i. However, it may be the case that the allocation apvm happens to achieve higher reported social welfare with respect to the setting excluding bidder i than a(-i) . When this happens, our mechanism may run a deficit. Although formally possible, these violations are extremely rare in practice, and we do not observe any in the experiments we describe in Section 6. Further, one can always enforce no deficit by setting a lower bound to payments, albeit at the consequence of slightly relaxing the incentive alignment property of PVM.

4.5 PVMwith Partitions

One drawback of PVM is that the number of elicitation runs (i.e., n+ 1), and thus the total number of queries, scales linearly in the number of bidders. For large auctions (e.g., with 100s of bidders), this may lead to too many queries. For this reason, we now present a modified version of PVM that requires fewer queries. The approach is very similar to Algorithm 2, but instead of excluding a single bidder at a time, the bidders are first partitioned into k groups, with k < n. We then perform k+1 elicitation runs, once in the setting including all bidders and once in each of the k settings where the corresponding group of bidders is excluded. We consequently call the approach PVM with partitions (PVMp).

PVMp is also incentive aligned. To see this, note that, for Proposition 2, we only need to guarantee that bidder i cannot affect the other bidders' values for a(-i) in Equation (7). Thus, we can replace a(-i) with an allocation obtained after running the ML-based elicitation algorithm on a setting excluding a group of bidders containing i. However, there is one caveat: if the exclusion of a group of bidders leads to a significantly less efficient allocation a(-i) in Equation (7), then the payments may become negative. Thus, bad groupings of bidders can lead to low revenue and/or deficit violations. We will discuss this again in Section 6.3.

Remark 3. At this point, we would like to emphasize the main difference between PVM and the mechanism we proposed in [Brero et al., 2017, Algorithm 2]. In our previous work, the ML-based inferred valuations were not just used to guide the elicitation, but also to compute the final allocation (and payments). In the present work, the ML algorithm is only used for elicitation, and the final allocation and payments are based only on the reported bundle-value pairs. This change is subtle, but it has profound effects for incentives. The good incentive properties of PVM crucially rely on the fact that the final allocation maximizes social welfare in reported values, and the payments are also computed based on reported values. If, as in our earlier framework, we would optimize the final allocation on inferred valuations, then this would either break individual rationality or the regret bound, unless an expressive (i.e., no in-sample error) ML algorithm were used. However, the expressive ML algorithms we studied in our prior work are computationally prohibitive to use in very large domains. Because PVM does not rely on expressiveness, we can use significantly faster, non-expressive ML algorithms, which enables us to scale to larger domains (e.g., with 98 goods), which was not possible using the earlier approach.

5 Instantiating the Mechanism via SVRs

So far, our presentation of PVM has been agnostic regarding which particular ML algorithm to use in the preference elicitation algorithm. However, this choice is very important because it determines the computational complexity of the overall mechanism. To determine which values to query at round t, we need to find a feasible allocation at that maximizes the inferred social welfare ˜ V t . In general, determining such an allocation may require examining all nm allocations, which is not tractable. However, if the ML algorithm exhibits useful structure, we can exploit that structure when searching for the social welfare-maximizing allocation. To design a computationally practical mechanism we closely follow the approach taken in our earlier work [Brero et al., 2017], where we specified ˜ V as the sum of n value functions ˜ vi inferred from the sets of value reports ˆ ϑi. To infer the individual value functions ˜ vi we use support vector regression (SVR).

5.1 Support Vector Regression

In this sub-section, we review the basics of SVRs (for an introduction, see Smola and Sch¨olkopf [2004]). To determine ˜ vi(x) from a set of ℓ reported values ˆ ϑi = {(xik, ˆ vik)}ℓk=1 , where ˆ vik = ˆ vi(xik), the SVR algorithm projects bundle x into a high dimensional feature space via a mapping function ϕ(x) and determines a linear model w in this feature space so that ˜ vi(x) = w · ϕ(x). To determine the weights w, the method simultaneously minimizes the error on the reported values and prevents overfitting through the regularization term w · w. Formally, w is the solution of:

where C determines the trade-off between accuracy in the reported values and the regularization, each eik represents the interpolation error at xik, and L(eik) is the loss due to this error. Traditionally, SVR uses the ε-insensitive loss with

Once the SVR has been trained (by solving the optimization problem in Equation (10)), values can be predicted as

where the αik are the solution to the dual of Problem (10), and κ(x, x′ ) = ϕ(x) · ϕ(x′ ) is a kernel function. The kernel function implicitly computes the scalar product of x and x′ in the feature space and establishes a measure of similarity between these bundles. By employing a kernel, a linear regressor in the feature space can produce a non-linear regressor in the untransformed value space. As we have shown in Brero et al. [2017], for a large family of kernel functions the optimization problem that determines at can be tailored to the representation in Equation (12) and encoded as a succinct integer program. Thus, if we instantiate the ML algorithmA as an SVR with a suitably chosen kernel, we can construct computationally practical mechanisms.

5.2 Linear and Quadratic Kernels

In this paper, we focus on two classes of kernel called linear and quadratic kernels. Given a non-negative parameter λ, a quadratic kernel is defined as κ(x, x′ ) = x · x′ + λ(x · x′ )2 . Linear kernels are the special case where λ = 0. Note that the SVRs we consider are thus characterized by three meta-parameters: the interpolationweight C, the insensitivity threshold ε, and the kernel parameter λ. In our experiments we tune these meta-parameters on a hold-out data set.

6 Experimental Evaluation

In this section, we present the experimental evaluation of our new approach. First, we introduce our experiment set-up. Then we evaluate the performance of our ML-based elicitation algorithm on its own, before we finally evaluate the performance of our Pseudo-VCG Mechanism (PVM).

6.1 Experiment Set-up

Domains. Because spectrum auctions are a very important application for CAs, we perform our evaluations in this context. We use the Spectrum Auction Test Suite (SATS) version 0.5.2 [Weiss et al., 2017] for our experiments, which allows us to easily generate thousands of auction instances on demand. SATS gives us access to each bidder's true values across the full 2m value space, and it enables us to compute an efficient allocation with respect to these full value profiles in a fast way (using succinct IP formulations). We tested our approach on three of the value models provided by SATS:

• The Global Synergy Value Model (GSVM) [Goeree and Holt, 2008], which generates medium-sized instances with 18 items and 7 bidders. GSVM models the items (spectrum licenses) as being arranged in two circles. Depending on her type, a bidder may be interested in licenses from different circles and has a value that depends on the total number of licenses of interest.
• The Local Synergy Value Model (LSVM) [Scheffel et al., 2012], which generates medium-sized instances with 18 items and 6 bidders. LSVM is more complex than GSVM: it places the items on a two-dimensional grid, and a bidder's value depends on a sigmoid function of the number of contiguous licenses.
• The Multi-Region Value Model (MRVM) [Weiss et al., 2017], which generates large instances with 98 items and 10 bidders. MRVM is the most complex model and captures large US and Canadian auctions by modeling the licenses as being arranged in multiple regions and bands. Bidders' values are affected by both geography and frequency dimensions of the licenses. Depending on the type and on the number of licenses of interest, bidders are categorized as national, regional or local.

Algorithm and Mechanism Set-up. Each elicitation run starts with an initial set of value reports ˆ ϑ0 , where each ˆ ϑ0i consists of c0 bundles drawn uniformly at random from the bundle space without replacement. Most deployed CAs impose a cap on the number of bundles for which bidders can specify a value, enabling the auctioneer to trade off allocative efficiency against computational efficiency. We adopt a similar approach by capping the number of queries in any elicitation run, and we denote this cap as ce. As PVM invokes our elicitation algorithm n + 1 times, and as the initial set of queried values ˆ ϑ0 is the same for all runs, the cap cpvm on the total number of queries that can be asked from each bidder is

To achieve a total number of queries comparable to that found in real-world auctions, we used ce = 50 for GSVM and LSVM, and ce = 100 in MRVM. In each domain, the optimal c0 under cap ce was selected using hold-out data, resulting in c∗0 = 40 for GSVM and LSVM and c∗0 = 30 for MRVM.

As discussed in Section 5, we use SVRs with linear and quadratic kernels as the ML algorithm. The meta-parameters of the SVR were tuned using hold-out data. While linear kernels have much lower computational costs, quadratic kernels lead to more accurate predictions and thus require fewer queries to achieve high efficiency. In our experiments, we found that, for the same number of queries, quadratic kernels provided about a 2% gain in efficiency in MRVM, and a 10% gain in GSVM and LSVM. Accordingly, we present results for quadratic kernels; results for linear kernels are qualitatively similar at a correspondingly lower efficiency.

The integer programs (IPs) used to find the allocations at were solved with CPLEX Studio (version 1261). We set a time limit of 1h for solving each IP and, when the time limit was reached, adopted the best solution found so far. We conducted our experiments on machines with Intel Xeon E5-2650 v4 2.20GHz processors with 40 logical cores. The n+1 elicitation runs in PVM were run in parallel. Since n = 10 in our largest models, we had up to 11 elicitations running in parallel, and thus allocated 3 logical cores to CPLEX for each elicitation run, such that we never requested more than the available number of cores on a single machine.

6.2 Evaluation of ML-based Elicitation

In this section, we evaluate our ML-based elicitation algorithm (i.e., a single run of Algorithm 1). We compare it against three baselines. First, we consider No Elicitation, which does not query any values and allocates each item to a bidder selected uniformly at random. We include this "degenerate" elicitation method as a baseline to obtain a lower bound on efficiency that can trivially be achieved without any elicitation. Next, we consider Random Query, which asks each bidder her values for a pre-specified number of bundles, whereby the bundles are selected uniformly at random in the bundle space without replacement. The allocation is then selected by solving the winner determination problem based on those reported values. This baseline represents the performance of uninformed sampling from the bundle space without any MLbased elicitation. Lastly, we include Full Elicitation, which leverages the special capability of SATS to directly encode value functions in a winner determination MIP so that a full value profile can be implicitly evaluated without requiring an otherwise infeasible enumeration of, e.g., 298 goods. This represents an upper bound on efficiency because full elicitation is generally infeasible in practice.

Table 1 presents the results from running these baselines as well as our ML-based elicitation algorithm. Despite only querying a small number of values from each bidder, our ML-based elicitation algorithm achieves more than 98% efficiency in the GSVM domain, and more than 93% efficiency in the more complex LSVM domain and in the highly realistic MRVM domain. The No Elicitation results show that all domains exhibit complex value structures such that high efficiency cannot be achieved by simply assigning items at random. The Random Query baseline results show that the ML algorithm used in our elicitation has a huge effect on efficiency. In MRVM, this effect translates into an average efficiency increase of more than 40% points.

ElicitationwithUpper andLowerBounds. It is often easier for bidders to specify bounds on bundle values, rather than determine such values precisely. We have therefore developed a modification of Algorithm 1 that works when bidders report upper and lower bounds instead of exact values.

To adapt Algorithm 1 to handle bounds, the key step to modify is Step 4 of the algorithm, i.e., how to apply ML algorithm A on reports consisting of bounds. This works particularly well when SVRs are used as the ML algorithm. Specifically, we can then leverage the particular structure of the ε-insensitive loss function used in standard SVR, presented in Equation (11). Note that this loss function does not penalize any linear model w for which w · ϕ(xik) ∈ [ˆ vik - ε, ˆ vik + ε]. This means that we can employ the following trick: we consider any report consisting of an upper bound ˆ vu ik and a lower bound ˆ vℓ ik as if the bidder had reported value ˆ vik = (ˆ vu ik + ˆ vℓ ik )/2. As long as we also measure the interpolation error in this sample via an insensitivity loss with εik = (ˆ vu ik - ˆ vℓ ik )/2, we guarantee that the semantics of the bidding bounds are maintained. Thus, this trick allows us to compute the inferred social welfare function in Step 4 of the algorithm with bounds as inputs. The remainder of Algorithm 1 remains the same (except that we operate on bounds instead of exact values), and the algorithm terminates in round T when bidders have specified at least one upper and lower bound for all bundles they are allocated in aT .

Note that with this modification, the output of Algorithm 1 now contains bundles and upper/lower bounds (instead of exact values). This is not yet enough information to determine an optimal allocation. Consequently, one needs an additional refinement process that asks the bidders to refine their bounds on the bundles that were elicited by the ML-based algorithm until the optimal allocation can be identified. 3 This refinement process is orthogonal to the ML-based elicitation algorithm we propose in this paper, and thus we leave this to future work. For our experimental evaluation, we simply assume we have access to a generic refinement process which, starting from the output of our modified Algorithm 1, identifies the optimal allocation. Specifically, in our experiments, we use SATS to look up the true value of every bundle on which an upper/lower bound was reported (i.e., "simulating" a flawless refinement process), and we then compute the optimal allocation based on these true values. Thus, we only evaluate the ability of the ML-based elicitation algorithm to identify relevant bundles when bidders report less information, but not the performance of a specific refinement process.

In our experiments, we generate the upper and lower bounds as follows: for any bundle x whose value is queried from bidder i we draw two "error measures" e1 and e2 from a normal distribution with mean 0 and standard deviation µvi(x), where µ is a parameter denoting evaluation uncertainty and vi(x) is the bidder's value. The upper bound is then vi(x)+|e1| and the lower bound is max{v(x)-|e2|, 0}.

We report the results from running the modified elicitation algorithm in Table 2. We see that for GSVM and LSVM there are only slight reductions in efficiency as we increase µ. The same applies for MRVM until µ = 1%. In general, this experiment shows that the assumption that bidders can report their precise values is not critical for the performance of our MLbased elicitation. We defer the design of a full mechanism using such a bounds-based query method to future work.

6.3 Evaluation of PVM

In this section, we evaluate our full PVMmechanism, which uses our ML-based elicitation algorithm as a sub-routine (n+1 times). We evaluate PVM in terms of total number of queries asked per bidder, allocative efficiency, revenue, and deficit, by comparing it against VCG. The results are shown in Table 3.

We see that, despite using a very small number of queries relative to the total number of bundles, PVM achieves more than 94% efficiency in all domains. 4 Turning to revenue, in GSVM, PVM achieves revenue very close to what VCG achieves. In LSVM and MRVM, the revenue under PVM is somewhat lower than under VCG, but still positive. Finally, we did not observe PVM to run a deficit on any instance.

3 This means that the bounds need to be refined until we can identify an allocation with a lower bound on the reported social welfare that is greater or equal than the upper bound on all other allocations [see, e.g., Lubin et al., 2008].

PVMwith Partitions. For MRVM, we also ran PVMwith partitions, using four groups of bidders (PVMp-4). Note that our definition of PVMp in Section 4.5 left open how to partition the bidders. For MRVM, we chose to place one national bidder in each of the first three groups while reserving the fourth group for all of the regional and local bidders. This partitioning is useful in a heterogeneous domain such as MRVM, ensuring that no more than one national bidder is excluded from each elicitation run leading to allocation a(-i) . 5 This avoids a situation where ∑j̸=i ˆ vj(a(-i) ) becomes too small relative to ∑j̸=i ˆ vj(apvm), yielding a small (or even negative) payment by bidder i, thus possibly leading to a deficit. 6

The results for PVMp-4 are presented in Table 3. While PVM has good performance with only a modest number of queries in the MRVM domain, PVMp-4 achieves almost the same efficiency with even fewer queries. Note that, while this reduction in queries is not large in the MRVM domain with 10 bidders, it would become significant in domains with larger number of bidders. Finally, none of the instances in this experiment ran a deficit. In fact, PVMp-4 achieves even higher revenue than PVM. Note that this is not the intended effect of the partitioning and not every partition will lead to a revenue increase. In general, a revenue increase or decrease is possible depending on how exactly bidders are grouped together in the partition.

4 Note that, in each domain, PVM achieves higher efficiency than a single elicitation run (see Table 1). This is expected because PVM performs n+1 elicitation runs. Even though n of those runs exclude one bidder, it is possible that those settings lead to an allocation with higher efficiency than the setting with all bidders.

5 This is possible because we use a "size four" partition and there are only three national bidders in the standard MRVMmodel.

6 We also tested a version of PVMp-3 where at least two national bidders have to be excluded from at least one elicitation at the same time, which often results in a deficit.

7 Conclusion

In this paper, we have introduced PVM, a new iterative combinatorial auction mechanism. At its core, PVM uses a machine learning-based elicitation algorithm to support bidders in selecting which bundles to evaluate (and submit a bid for) during the auction, without having to explore their full value space. We have drawn on principles from VCG to design a payment rule for PVM that aligns bidders' incentives with allocative efficiency. While PVM does not provide efficiency guarantees upon termination, we have shown experimentally that it achieves between 94% and 99% efficiency on average in different spectrum auction domains, even with a small number of queries. Our results give rise to promising directions for future research: First, while we have shown how our elicitation method can be modified, allowing bidders to only report bounds on their values, we have left a full mechanism based on this bounds-based elicitation method to future work. Second, while we have used SVRs to power our elicitation algorithm, future work could explore designs based on alternative ML algorithms (e.g., using deep learning).

Acknowledgments

Part of this research was supported by the SNSF (Swiss National Science Foundation) under grant #156836.