Efficient Interdependent Value Combinatorial Auctions with Single Minded Bidders

1 Introduction

Auction design is an important topic of research in artificial intelligence. Auctions involve the allocation of a set of resources among strategic agents, each of which has a private signal regarding the value of a subset of the resources being sold. In this paper, we consider settings in which the bidders' valuations are interdependent, i.e. they depend not only on their own signal, but also on the signals of other agents.

Such auctions often occur in practice. Consider, for example, the allocation of the right to show a series of ad impressions to consumers in online advertising. Several advertisers have different signals about the likelihood of these consumers clicking on these slots and following through their clicks with purchases. In this setting, the value of an advertiser for obtaining a set of impressions may also depend on the signals of other bidders. This is because some advertisers may have The aim of this work is to study such auctions in combinatorial settings with single minded bidders (=desiring exactly one bundle of items) and placing contingent bids. In contingent bid auctions, agents are not required to describe others' signals, but are only asked to submit conditional bids of the form: "If Agent 1 bids $x for bundle B1, then I will bid $y for bundle B2". For this setting, Dasgupta and Maskin [2000] design an efficient auction, in which allocation is computed based on the fixed point of the vector of bids. They also show this auction can be implemented in an ex-post equilibrium, subject to the agent's valuations satisfying single crossing condition (SCC). However, Dasgupta and Maskin do not provide practical instantiations of valuation domains that satisfy SCC. Yet, we argue that describing actual negotiation domains is a crucial step in order to apply these importance insights in practice. Towards this end, the work of Ito and Parkes [2006] (which our work builds on), provides an instantiation of Dasgupta and Maskin's model, by identifying a linear valuation model in which the fixed point convergence and single crossing conditions are satisfied. However, the results in Ito and Parkes allow the implementation of the efficient auction only in the single item case. For single minded combinatorial auctions (CAs), they propose an alternative method using greedy allocation, which is truthful, but not efficient. The main contribution of this work is to fill this gap, and describe domains in which the efficient auction proposed by Dasgupta and Maskin [2000] can be truthfully implemented in single minded combinatorial domains.

In more detail, our analysis will consider both combinatorial settings (where exactly one copy is available of each item) and combinatorial multi-item settings (involving multiple copies of some of the items). We derive constraints on the linear contingency weights and the structure of bundles demanded, such that the required single crossing condition holds and, thus, the efficient allocation can be truthfully implemented. In the second part of the paper, we consider domains in which the single crossing condition fails, due to the fact that a large number of bidders have values contingent on the private signals of a few "expert" bidders. For this setting,

Takayuki Ito

Nagoya Institute of Technology ito.takayuki@nitech.ac.jp we provide an alternative to the greedy method discussed in Ito and Parkes [2006], that aims to exploit the structure of interdependencies between the agents. Specifically, we propose a two-stage mechanism that involves pre-allocating the expert agents in the first stage, followed by an efficient allocation for the remaining agents. The paper concludes with a discussion.

2 Related work

There have been several works that consider interdependent valuations, reporting both positive and negative results. For single-dimensional signals, where the private information of a bidder can be captured by a single number, ex post efficient auctions exist (Dasgupta and Maskin [2000]; Krishna [2009]). For multi-dimensional signals, there are strong negative results about the ability to truthfully implement efficient outcomes (Dasgupta and Maskin [2000]; Jehiel and Moldovanu [2001]).

Other works have considered interdependent value auctions in more specific settings. One proposed alternative is to design mechanisms where values are contingent directly on the signals (an approach taken in previous work of Dash et al. [2005]; Ito et al. [2004], among others), in which each agent explicitly is asked to provide a valuation function based on all signals. However, such approaches assume domain knowledge, such as a common language to describe the private signals advertisers have about ad impressions.

The work of Ito et al. [2004] consider settings with a special structure, in which agents are either "experts" (agents whose signals influences others) or "amateurs" (who follow other agents' signals). An alternative class of interdependent value auctions are the so-called execution contingent mechanisms (Ceppi et al. [2011]; Klein et al. [2008]; Mezzetti [2004]). In these mechanisms, the payments are computed in the second stage, after the values are revealed to the agents by the allocation and thus they circumvent the problem of the single crossing condition. However, these two-stage mechanisms have weak incentives in the second stage, and thus have limited applicability.

3 Preliminaries

Denote by M the set of items to be allocated, and N the set of agents (bidders) for these items, where m = |M| and n = |N| are the sizes of these sets (unless otherwise specified, set M may include multiple copies of the same item). A single minded bidder has an interesting (or useful) bundle Wi ⊆ M, and moreover we use ki = |Wi| to denote the sizes of the useful bundles. Each agent's value is described by an interdependent function zi(X, s) ≥ 0 on bundles X ⊆ M, defined in terms of signals s = (s1, . . . , sn) as:

We assume free disposal, that is the agent's value is (weakly) increasing with additional goods. Function zi(s) ≥ 0 defines the agent's value for an interesting bundle, given signals s.

In this work, we use the linear contingent bids model, as first defined in Ito and Parkes [2006]. For combinatorial domains, the model can be defined as follows. Each agent i ∈ N reports an interesting bundle ˆWi (potentially untruthfully), a stand alone value v0 i , and a set of weight bundle pairs

{(αi,1,Xi,1) . . . (αi,n,Xi,n)} for all agents j ̸= i, where αi,j ∈ R≥0 and Xi,j ⊆ M . Taken together, this defines the following contingent value function:

Where vi(X, v-i) denotes agent i's value for bundle X, determined in a fixed point, w.r.t. the values of other agents. The private value v0 i of each agent is a weakly increasing function of its signal (i.e. ∂v0 i /∂si ≥ 0). However, because in this paper we only work with valuations and don't model signal spaces explicitly, we can assume wlog. v0 i = si.

In order for an allocation to be computable in this interdependent value setting, a key requirement is that the set of valuations converge to a single fixed point in RN≥0 . Formally, the valuation equilibrium point is defined as a fixed point of the mapping (v1, . . . vn) ↦→ (v1(v-1), . . . vn(v-n)), where vi(v-i) : 2M ↦→R≥0.

Theorem 1 (Ito and Parkes [2006]) A single minded contingent bid domain has a unique fixed point if ∑j̸=i αi,j < 1, for all i ∈ N.

Note that the existence of a unique fixed point is fully determined by the contingency weights αi,j , and not by the useful bundles Wi that agents demand. Thus, as long as the condition in Theorem 1 holds, the contingent bid system will converge to a fixed point, regardless of the Wi.

The condition in Theorem 1 is sufficient for convergence, but is not also necessary. A tight condition can be derived using determinants of the valuation vectors, which is however difficult to interpret, the condition in Theorem 1 being more useful for this work. In the remainder of this section and in Section 4 we will only focus on domains which satisfy the property in Theorem 1, thus for all results going forward a unique fixed point of the valuations exists.

3.1 An Efficient Contingent Bids Auction

In an interdependent value auction, each agent is required to place a contingent bid function bi(X, b-i), which takes the same form as the value function in Equation 2, and is evaluated by the auction in an analogous way. A bid bi is truthful iff it is truthful for all parts of the report (i.e. contingency weights αi,j , private value v0 i and interesting bundle Wi).

For the contingent bidding model, Dasgupta and Maskin [2000] propose an efficient auction that can be generalized to the multi-item case as follows: (1) Compute the fixed point bids ⃗bfp , as defined by the mapping induced by Equation 2 (but using the space of reported bids); (2) Compute the efficient allocation X∗ = (X∗ 1 , . . . ,X∗n ) = argmaxX∈Γ ∑i∈N bfp i (Xi) to maximize total value (breaking ties at random), where Γ denotes the set of feasible allocations; and (3) computes the payment to each winner i as:

where b∗j (X) = bj(X, (⃗b′i , b∗-i,j )), and ⃗b′i (X) = b′i for X ⊇ ˆWi and 0 otherwise. Here b∗-i denotes the new fixed point in the bid space if agent i would bid b′i for its interesting bundle ˆWi; the intuition being that agent i pays the smallest amount it could have bid and still won, also accounting for the effect of its report on the bids of other agents.

In order for truthful bidding to be an ex-post Nash equilibrium in this efficient auction, the agent's valuation functions must satisfy the property of Generalized Single Crossing Condition (Generalized SCC) Dasgupta and Maskin [2000]).

Definition 1 (Generalized SCC) If, for signals (s1, . . . , sn) there is a pair of allocations X and X′ , tied for value, i.e.: ∑j∈N zj(Xj, s) = ∑j∈N zj(X′j , s) = maxX′′∈Γ ∑j∈N zj (X′′ j , s) then for every agent i such that Xi ̸=X′ i , we require:

Intuitively explained, for any two allocations X and X′ tied for (maximal) value, generalized SCC requires that, whenever the value of agent i for X is improving more quickly than for X′ with respect to its signal, this is also true for the total social welfare of all agents. Conceptually, this is true when the marginal effect of an agent's signal on its own value dominates the marginal effect of its signal on the aggregate economy of agents. The link between truthful implementation in CAs and generalized SCC is given by Theorem 2 1 :

Theorem 2 (Dasgupta and Maskin, Ito and Parkes [2006])

Given an valuation domain with an expressive bidding language, the second-price interdependent value single minded CA auction is efficient in an ex post Nash equilibrium iff the generalized SCC property holds.

Note the theorem requires a preference language expressive enough for the preference domain and, importantly, it only holds for single dimensional signal spaces (which in a CA domain means single minded bidders). But given these assumptions, the theorem guarantees efficient and truthful implementation, as long as generalized SCC holds in the value domain. The focus of Section 4 is on deriving constraints on the weights in the linear contingency model, which assure generalized SCC holds in single minded, combinatorial domains. In the case of a single item auction, the following condition is known to be sufficient for truthfulness:

Theorem 3 (Ito and Parkes [2006]) The second price, interdependent value, single item auction (i.e. |M| = 1), satisfies SCC and is truthful whenever ∑j̸=i αi,j < 1, for ∀i ∈ N.

For single minded CAs this condition is sufficient for assuring we have fixed point bids (cf. Theorem 1), but not for generalized SCC. To see this, consider the example shown in Figure 1, with the contingent valuations:

1 The SCC definition in the initial paper Dasgupta and Maskin [2000] is too strong to be useful in combinatorial domains. This form of the Generalized SCC condition is cited in Ito and Parkes to personal communication with Eric Maskin in October 2005.

If all the bidders place truthful bids (with bi = vi, ∀i ∈ N), then fixed point in the bid space would be: b1(AB) = 8, b2(c) = 6, b3(ABC) = 12.2, b4(A) = 6.6, b5(BC) = 6.6. The mechanism allocates: X1 = {AB},X2 = {C},X3 = X4 = X5 = ∅. Now, suppose an own value v0 1 = 8, which means:

Then, the truthful fixed point bids would be b1(AB) = 11, b2(c) = 6, b3(ABC) = 13.7, b4(A) = 8.7, b5(BC) = 8.7. In this case, allocation would be X′4 = {A},X′5 = {BC}. But then, bidder 1 could easily misreport any ˆ v0 1 < 7 and be allocated instead. The reason is that SCC is broken here for agent 1 and allocations X = 〈{AB}, {C}, ∅, ∅, ∅〉 and X′ = 〈∅, ∅, ∅, {A}, {BC}〉. This is because the signal of agent 1 (s1 = v0 1 ) has a greater marginal influence on the value of the opposing coalition A4, A5 than on A1, A2.

4 Domains with efficient allocation

In this section, we study which restrictions on the contingency weights or interesting bundle structure demanded by each agent ensure truthful implementation of the efficient auction presented in Section 3.1 in a combinatorial domain. Similar to Ito and Parkes [2006], our aim is to identify preference domains defined by universal, anonymous, restrictions on the total contingency weights reported by each agent.

For all the domains we explore, convergence to a unique fixed point is assured by the property in Theorem 1, so in this section we focus on conditions which guarantee that Generalized SCC holds. First, for the proofs we require an additional lemma, which characterizes domains in which the total contingency weight of each agent is bounded by a threshold.

Lemma 1 (Threshold Property) Consider a setting with N agents whose values are interdependent on each other, let τ ∈ (0, 1) be some fixed threshold. Then, if for all agents ∀i ∈ N it holds that ∑j∈N αi,j < τ this implies that ∀j, i ∈ N:

where zj = zj(X) (for some X ⊇ Wi) is the value function of agent j and si is the private signal of agent i.

Intuitively, what the property says is that if all the total weights specified by any agent is less than τ, then the total cumulative dependency of the value of any agent on any other must be less than τ.

Proof 1 The proof is by induction on the maximum degree of the derivative ∂zj/∂si. First, we use the assumption that ∂zi/∂si = 1 for ∀i ∈ N (this follows from our setup in which si = v0 i , the value of an agent w.r.t. its own private signal). For j ̸= i the derivative will be a sum of products of αp,l terms, depending on the derivation paths from j to i.

Denote by D(k) zj/si the n-th degree derivative of zi w.r.t. si, and by R(Dzj/si ) the maximum rank of this derivative, when it become a constant. Formally, R(Dzj/si ) = k iff ∂zj ∂ (k) si > 0 and ∂zj ∂ (k+1) si = 0. Intuitively, this means the maximum derivation path from j to i has exactly k iterations. The proof then follows two steps.

Initialization step: For R(Dzj/si ) = 1, we know:

Induction step: Assuming the property holds for all ∀p ∈ N for which R(Dzp/si ) ≤ k, we show it also holds for all j ∈ N for which R(Dzj/si ) = k + 1:

Since we know, by construction ∂zi ∂si = 1 and ∂zp ∂si < τ < 1 this means:

Thus, if the property also holds for any agent p ∈ N with R(Dzj/si ) ≤ k, it also holds for all agents j ∈ N for which R(Dzj /si ) = k + 1.

Intuitively, if some agent j's value is contingent on the value of other agent(s) k ̸= j, i whose value is, in turn, contingent on si, this cannot lead to a stronger contingency of zj on si than if that contingency was expressed directly. Given this linear contingency model, we are ready to characterize CA domains that satisfy Generalized SCC.

Theorem 4 In a preference domain in which, for all agents ∀i ∈ N it holds that ∑j∈N αi,j < kim (where ki = |Wi|, m = |M|), then Generalized SCC holds.

Proof 2 The proof starts from the generalized SCC condition from Def. 1. Assume, by contradiction, that SCC is violated ⇐⇒ ∃i ∈ N and ∃ two efficient allocations X, X′ s.t.:

In a single minded bidder model, the first equation must mean that: Wi ⊆ Xi, but Wi ⊈ X′ i (i.e. agent i is allocated its useful bundle by allocation X, but not by X′ ). Now, consider the agents that are allocated their useful bundles by allocation X′ , and let us denote their set by Sopp (this is the potential "opposing"' coalition to agent i being allocated). Formally, Sopp = {j ∈ N, s.t. Wj ⊆ X′j } (necessarily i /∈ Sopp ). We can restrict the 2nd term of Eq. 2 as:

This is because, by definition, agents j /∈ Sopp do not derive any value from allocation X′ (as they are not allocated their useful bundle by X′ ). Since there are at most m items available for allocation: ∑j∈Sopp kj ≤ m. Moreover, we have that ∂zi ∂si = 1 and because our starting condition and Lemma 1, for ∀j ̸= i the following holds: ∂zj ∂si < kjm . This means that we get the following inequality:

But, for the allocation X (in which agent i is allocated, i.e. Wi ⊆ Xi), we must have that: ∂ ∂si ∑j∈N zj(Xj, s) ≥ 1, because at least agent i is allocated by X, which gives a contradiction with the assumption in Equation 2.

Note that the bound provided by Theorem 4 gives a tight condition on all agents. Even if the condition fails for one agent but holds for all the others, Generalized SCC can still fail. Consider the the example illustrated in Figure 1, with the same agents and values. If the contingency weights from Agents 4 and 5 are α4,1 = 0.33 (under the threshold of 1/3 given by Theorem 4), but α5,1 = 0.68 (above the threshold of 2/3), the condition fails for only one agent (Agent 5). Yet Generalized SCC still fails for Agent 1.

4.1 Domains with subset/superset constraints

One way to relax the bound on the contingency weights is to impose additional structure on the bundles agents demand, such as having values contingent only on agents whose useful bundles are subsets or supersets of their own. In order for such constraints to work, however, in this section we restrict the analysis only to single unit combinatorial domains, where there is only one unit of each type of item. Hence, no item can be replaced with another in any of the agents' useful bundles.

Theorem 5 Consider a single unit combinatorial domain with single minded bidders, in which agents specifying contingent bids demand only bundles that are subsets, i.e.: αi,j > 0 =⇒ Wi ⊆ Wj , ∀i ∈ N. Generalized SCC holds if ∀i, j ∈ N:

Proof 3 The proof follows the same structure as the proof of Theorem 4. As before, consider two allocations X (in which agent i is allocated its useful bundle) and X′ (in which it is not). We work towards the same contradiction of generalized SCC. As before, consider the set Sopp of opposing agents to i, agents that are allocated by X′ . Formally, we can define Sopp as the set of agents j ∈ N allocated by X′ for which ∂zj (X′j ,s) ∂si ̸= 0 (for these agents αj,i > 0 and Wj ⊆ X′j ). Important to note that, necessarily, for ∀j ∈ Sopp ,Wj ⊈ Xj, because allocation X allocates agent i its target bundle, and due to our assumptions that goods are single unit and Wj ⊆ Wi, it cannot be that both agent i and any of the agents j ∈ Sopp are simultaneously allocated useful bundles. Thus, the agents in the set Sopp should satisfy:

• ∀j ∈ Sopp ,Wj ⊆ Wi. This is due to our starting assumption, as αj,i > 0 for j ∈ Sopp .
• ∀j, l ∈ Sopp ,Wj ∩ Wk = ∅. This is because there is a single unit of each good, and both j, l ∈ Sopp are

allocated their useful bundles by X′ , which would not be possible unless these bundles do not overlap.

This means that the useful bundles of agents j1, j2 . . . j|S| ∈ Sopp represent, at most a disjoint partition of Wi, meaning:

where any pair is mutually disjoint, i.e. Wjl ∩Wjl = ∅. This means ∑j∈Sopp kj ≤ ki. Due to Lemma 1, this means:

Where the last relation is an equality if agent i is actually p, and strict otherwise. This gives the set of inequalities:

The other efficient allocation X (which allocates to i) has: ∂ ∂si ∑j∈N zj(Xj , s) ≥ 1 giving the required contradiction.

In Figure 2 we show an example domain with subset constraints. Edge weights were assigned such that the sum of dependencies from each agent is the maximal allowed in Theorem 5 (decimals were rounded down). The total contingency weight of A2, A2 and A6 (who demand 1 item each) must be bounded by 13 , as they together could form a potential SCCbreaking coalition against A1. However, the weight restriction of A7 on A1 is < 1, as this agent could not form a coalition against A1 with any other agent. Example 1 shows why this logic fails in a domain with multi-unit supply (i.e. why the single unit assumption in Theorem 5 is needed).

Example 1 Consider an example with m = 12 identical items, and n=4 agents: Agent 1 demanding k1 = 7 items (with v0 1 = 4), Agent 2 demanding k2 = 1 item (with v0 1 = 4), and Agents 3 and 4 demanding k3 = k4 = 6 items each. The only 2 value interdependencies are from Agents 3 and 4 on the value of agent 1: α3,1 = 6/7, α4,1 = 6/7 (recall that they satisfy the condition that W3 ⊆ W1 and W4 ⊆ W1, as they demand 6 items out of 7). In this case, agent 1 can misreport ˆ v0 1 = 2 and be allocated, preventing the bids of 3 and 4 from forming a larger blocking coalition Sopp against it.

Next, we study the case of superset constraints.

Theorem 6 In a single-unit supply, combinatorial domain with single minded bidders, if each agent is restricted to specifying contingent demand bids that are supersets, i.e. αi,j > 0 =⇒ Wi ⊇ Wj, ∀i ∈ N, then Generalized SCC holds if ∀i, j ∈ N, ∑j∈N αi,j < 1.

Proof 4 The proof follows the same structure as before, considering two allocations: X, in which agent i is allocated and X′ in which it is not. Define Sopp as the set of agents j ∈ N allocated by X′ for which ∂zj(X′j ,s) ∂si ̸= 0. Due to the superset assumption, there exists at most one such agent, i.e. the cardinality |Sopp | = 1. This can be shown by contradiction. Suppose there are 2 agents j, k ∈ Sopp , j ̸= k. We know that ∃Wi,Wi ̸= ∅ s. t. Wj ⊇ Wi and Wk ⊇ Wi. Since there is only a single unit available of any item, X′ cannot allocate both agents j and k simultaneously. Therefore, Sopp contains a single agent (and it must contain at least one agent, because we assumed agent i was allocated by X, but not by X′ , hence some other agent must have received i's items in X′ ). But from Lemma 1, we know that for ∀j ∈ Sopp , j ̸= i, ∂zj/∂si < 1, hence: ∂ ∂si ∑j∈N zj(X′j , s) < 1 and AND ∂ ∂si ∑j∈N zj (Xj , s) ≥ 1, hence Generalized SCC holds.

Figure 3 shows an example with superset constraints, with edge weights assigned such that the sum of dependencies by each agent is the maximal one allowed in Theorem 6. Note the value of agent A1 has a large influence on the values of other bidders (5 times higher than on its own value). However, there is no problem with Generalized SCC, because all the agents whose valuations depend (even indirectly) A1's value must have demands that include itemA, thus they could never be allocated simultaneously, as a coalition.

This is an interesting result, because it means the constraint for domains with superset demand structure is the same as in the single item case. By comparison, that for subset demands the contingency weight limit needs to be lower for SCC to hold. However, we believe superset type constraints are more natural in practical applications.

5 A truthful auction between experts and amateurs when Generalized SCC fails

In Section 4, we identified several domain restrictions which ensure the Generalized SCC property holds, and the efficient auction can be implemented. These domain restrictions are useful in applications where no bidder's valuation has an "outsize influence" on the rest of the market. Yet, in many real-world settings, the opinion of a few expert agents can drive valuations across the whole market. Real markets are often divided into a few experts (who have an "inside signal" regarding the true value of some items) and a large number of "amateurs". Although the efficient auction from Section 3.1 cannot be applied, we can use the special structure of the value contingencies between agents to develop a two-stage auction tailored specifically for such cases. Informally, first a small number of expert agents are allocated their useful bundle for a fixed price (or, in our case, for free). Their reports are then used to compute the fixed point bids for the remaining agents, who are allocated through the second-price, fixed point bid auction. Formally, first define the influence score of agent i as: Infl(i) = ∑j̸=i αj,i.

Consider the following mechanism which sets threshold level τ for the influence score 2 . Next, the set of available items M is partitioned into two distinct sets: M p (allocated through the "expert pre-allocation stage") and M a (allocated based on received bids). The "experts first" mechanism has two allocation stages (denoted by Xp and Xa ):

1. Pre-allocation of expert agents: All agents i ∈ N with Infl(i ) > τ are allocated their useful bundle (Xp i =Wi) for free and leave the market. Here, we assume that M p is set large enough for all agents with Infl(i) > τ to be allocated, but any items in M p not allocated remain unsold (and unavailable for Stage 2).
2. Allocation based on received bids: Reports from all agents i ∈ N (including the ones pre-allocated in stage 1 that left the market) are used to allocate the remaining M a items, using the fixed point valuations vi:

where Γ(M a ,N) denotes the set of possible ways to allocate M a items among N agents. It is possible that an agent that has been pre-allocated in stage 1 is also allocated by Xa (i.e. Xa i =Xp i =Wi). In this case, the corresponding items remain unsold.

Theorem 7 The "experts first" mechanism is truthful.

Proof(Sketch) First note that the influence score does not depend on the agents' own reports, only on the contingency weights reported by other agents. Thus, no agent can unilaterally determine its "expert" status and allocation in Stage 1. However, an agent can affect the score and ranking of other pre-allocated agents, so the agents participating in Stage 2 must be indifferent which agents are pre-allocated in Stage 1. This holds because, first, the number of items M p available for pre-allocation is fixed (any items left unused are unallocated), there is no way for an agent to increase supply of items M a available in Stage 2. Second, the competition agents face in Stage 2 is the same, as it includes the bids from all agents i ∈ N, even if some were pre-allocated. Thus, both the supply and the competition they face is the same, regardless pre-allocations in Stage 1. And because the mechanism ensures all agents that potentially break SCC are pre-allocated in Stage 1, these agents have no incentive to misreport.

Example 3: Consider an auctioneer who needs to sell 1000 identical items (e.g. 1000 identical bottles of wine). There are 2 agents: A1 and A2 who demand 5 items each, with values v1(W1 = 5) = $20, respectively v2(W2 = 5) = $50. Moreover, there are 101 agents Ac that demand 10 items each, but their valuation being exclusively contingent on that of A1, as: vc(Wc = 10) = 10 ∗ v1(Wc = 10) (i.e. αc,i = 10), and another 101 agents Ai that also demand 10 items each, with independent values vi(Wi = 10) = $10. Thus, in this setting one agent (A1) can be thought of as a wine expert, and a lot of bidders are willing to buy larger quantities and pay more contingent on her opinion. If all bidders are truthful (which means the reported bid vectors are equal to their values ⃗bi = ⃗vi), then the fixed point bids are b1 = $20, b2 = $50, bi = $10 and bc = $200. In this case all 1000 items would be allocated to 100 of the bc bidders (breaking ties at random), who pay $200 for 10 items. The social welfare is then: ∑j∈N|v1 vj = 100∗$200 = $20, 000. However, SCC is clearly broken here for A1 who can simply misreport ˆb1(W1 = 5) = $0.5, leading to the fixed point bids: b1 = $20, b2 = $50, bi = $10 and bc = $5, and the mechanism would allocate 5 items each to A1, A2 and 10 items each to 99 of the Ai agents. This has a much lower social welfare of ∑j∈N|ˆ v1 vj = $1040.5. Consider how this example would work with pre-allocation, where M p = 10 are reserved for pre-allocation and M a = 990 can be allocated using the fixed point bids (with τ = 1). In the preallocation stage, only agent A1 with Infl(A1 ) = 990 > 1 is pre-allocated Xp 1 = 5 items for free, and 5 items remain unsold. As A1 was already allocated, in Stage 2, the report of A1 can be used to compute the truthful fixed point bids: b1 = $20, b2 = $50, bi = $10 and bc = $200. Then 99 of the Ac agents are allocated 10 items each, giving a social welfare of ∑j∈N vj (Xp ∪ Xa ) = 99 ∗ $200 + $20 = $19820.

2 A level of τ = 1 is natural from the perspective of ensuring SCC, though a higher level may be sufficient as well.

Note that the above example is somewhat simplified, as only one agent is an expert. In practice, e.g. in the wine domain, there may be several wine experts whose opinion largescale buyers (e.g. restaurants, merchants) follow. Then, more items may need to be reserved for pre-allocation (e.g. 50 out of 1000), but the intuition remains the same.

6 Conclusions

This paper advances the state of the art in interdependent value auctions by deriving conditions under which the efficient contingent bid auction of Dasgupta and Maskin [2000] can be implemented in combinatorial domains with single minded bidders. Starting from the linear contingency model of Ito and Parkes [2006], we identify domain restrictions on the total weights and bundle structures which lead to preference domains where generalized SCC is satisfied, and hence the efficient auction can be truthfully implemented. We complement these results with a truthful two-stage allocation procedure for domains that do not satisfy Generalized SCC, which involves first pre-allocating to a set of experts, and using their reports to allocate efficiently the remaining items.

There are several issues that could be explored in future work. Previously, Ito and Parkes [2006] proposed a truthful auction for single minded CAs, which uses greedy allocation, where the allocation decision is taken separately for each item. While neither the greedy method, nor the "experts first" method in this paper guarantee efficiency, it would be interesting to compare their average case performance in a practical application, such as the keyword advertising auctions in the introduction. Another relevant question for future research is exploring interdependent value auctions in online settings (such as in Constantin et al. [2007]; Gerding et al. [2011]), where agents arrive in the market over time.