Approximating Optimal Combinatorial Auctions for Complements Using Restricted Welfare Maximization

1 Introduction

Combinatorial auctions (CAs) are a key method for resource (and task) allocation in multiagent systems. One of the most important open problems in CAs, and mechanism design at large, is to design revenue-maximizing (aka optimal) auctions. Specifically, the problem is, for the seller, to design an auction/mechanism that maximizes her expected revenue, given the information about bidders' valuation distributions but not the actual values. Despite the problem's importance and the simplicity of stating it, the problem has eluded researchers for decades. It is open even for the simplest settings such as those with two distinct items for sale and bidders having general two-dimensional private valuation (type) spaces. In fact, designing an optimal CA is NP-hard (even in the one-agent setting) [Conitzer & Sandholm, 2004]. This is in contrast to the one-item setting, where a well-known concise characterization of the optimal auction, called Myerson's auction, exists [Myerson, 1981]. This was later generalized to multiple copies of one item [Maskin & Riley, 1989]. Over the last 30 years, a few optimal auctions in other special settings have been designed, including Levin's auction for complements [Levin, 1997], which is also the focus of this paper, multi-item auctions for settings where the bidders' valuations can take on either of only two values [Armstrong, 2000; Avery & Hendershott, 2000], a 1-item auction for financially constrained bidders [Pai & Vohra, 2008], sponsored search auctions [Iyengar & Kumar, 2006], and a procurement auction where both costs and capacities are private information [Iyengar & Kumar, 2008].

∗This material is based upon work supported by the National Science Foundation under IIS grants 0905390 and 0964579. This work is also partially supported by HK RGC GRF 616909.

Interestingly, for symmetric settings where valuation distributions are identical across bidders, Myerson's auction coincides with the second-price auction [Vickrey, 1961] with an appropriately set reserve price. Hartline and Roughgarden [2009] further show that, even if the distributions are asymmetric, a Vickrey auction with appropriately set bidderspecific reserve prices can 2-approximate Myerson's optimal revenue. The generalization of the Vickrey auction to multiple items is the Vickrey-Clarke-Groves (VCG) mechanism [Groves, 1973; Clarke, 1971]. It is the gold standard for CAs. Likhodedov and Sandholm [2005] give a logarithmic approximation of optimal multi-item auctions with a variation of the VCG, for two classes of settings: (1) additive valuations (where each bidder's valuation for a bundle is the sum of his valuations for the items in the bundle), and (2) unlimited supply (such as in digital music stores).

These kinds of results are interesting as they shed light on the tradeoff between revenue and simplicity of the auction. This is because it is generally agreed that optimal auctions like Myerson's are more complicated and usually impractical. They also tend to require more information about the bidders'

valuation distributions than the VCG-style mechanisms. We will see that in this paper also.

In this paper, we explore further how far the idea of approximating optimal auctions with variations of the VCG can go, by looking at a different setting, namely Levin's setting for selling complementary items [Levin, 1997]. Levin gives an auction that generalizes Myerson's auction to a CA setting where bidders' valuations exhibit complementarity, but each bidder's valuations are parameterized by a single privateinformation variable (aka the bidder's type). This setting captures a variety of real-world domains where the seller knows the bidders' preference structure (for example, she may know that bidder i always values one item twice as much as another), but not the magnitude of the preferences (which may, in practice, depend on the bidder's income, budget, and other factors unknown to the seller).

Although the setting of this paper deals with onedimensional type spaces, it should not be confused with the widely-studied, but simpler, single-parameter environment (cf. [Nisan et al., 2007, Chapter 9]). That environment includes a set of bidders and a specified set of feasible sets of bidders. Each feasible set denotes a set of bidders that can be served simultaneously. Each bidder has a single number representing his valuation of being served, and his valuation is zero if not served. Examples include 1-item auctions (where each singleton bidder is a feasible set) and auctions for multiple identical units with unit-demand bidders (where each size k set of bidders is a feasible set, where k is the number of units). Thus, a bidder i can only end up with one of two "outcomes": (1) get served/allocated and enjoy utility vi, or (2) not get served and obtain utility 0. In contrast, even in a 2item Levin environment, the bidder can win item 1, item 2, or both, and can have a different valuation for each of these three bundles (and valuation zero for winning nothing).

This paper makes the following contributions. We introduce a new research avenue for increasing revenue where we poke holes in the allocation space-based on the bidsand then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the first step down this avenue, we introduce a new form of "reserve pricing" into CAs. Prior methods have involved inserting an artificial bidder into the CA. Variants of that idea have included ones where the artificial bidder submits bids on items [Likhodedov & Sandholm, 2005], on bundles [Likhodedov & Sandholm, 2004; 2005; Jehiel, Meyer-Ter-Vehn, & Moldovanu, 2007], or on entire allocations [Likhodedov & Sandholm, 2005; Jehiel, Meyer-Ter-Vehn, &Moldovanu, 2007]. This idea has also been analyzed with two artificial bidders [Guruswami et al., 2005]. In contrast, we introduce "reserve pricing" by precluding allocations that do not meet pre-defined criteria. For Levin's setting we prove that monopoly reserve prices followed by welfare-maximizing allocation and Levin's payment rule 2-approximate optimal revenue. Our mechanism is close to the gold standard (VCG) and thus arguably easier to adopt than Levin's. It also requires less information about the prior over the bidders' types, and is more (or equally) efficient (Equation 1). We proceed to prove that a 6-approximation can be achieved using anonymous reserve prices followed by welfare-maximizing allocation and Levin's payment rule. As an important lemma with potential other applications as well, we show in Levin's setting that the expected revenue from any truthful allocation-monotonic auction equals its expected virtual valuation. This generalizes Myerson's lemma from the single-parameter environment.

2 Setting

We study the setting introduced by Levin [1997]. There is one seller with indivisible items for sale. While Levin points out that his results apply to any finite number of items for sale, he derives his results in the 2-item setting. We do the same. Our results, too, apply to any finite number of items since our proofs do not make particular use of the number of items. 1

There are a set of N = {1, 2, . . . , n} bidders. Each bidder i ∈ N has valuation vi1(θi) for the first item, vi2(θi) for the second, and vi1(θi) + vi2(θi) + vi3(θi) for the bundle that includes both items. Here, θi is bidder i's type and vi3(θi) captures complementarity, that is, i's additional satisfaction from obtaining the bundle. The seller has zero valuation for any set of items, so her utility equals the revenue, i.e., the sum of payments collected from the bidders.

An allocation is denoted by a vector ⃗xi = (xi1, xi2) for each bidder i, where xij = 1 if item j is allocated to bidder i, and xij = 0 otherwise. Bidder i's utility function is

where pi is the amount bidder i has to pay. We use the standard model of Bayesian mechanism design: (1) for each bidder i, θi is distributed on [θi, θi] according to a cumulative density function Fi, which admits a positive, bounded density function fi, (2) each bidder i knows his type θi, but others, including the seller, do not, (3) the distributions Fi are common knowledge, and (4) the seller and the bidders are risk neutral: each agent tries to maximize his own expected utility.

In order to derive an optimal mechanism for this setting, Levin makes the following three additional standard assumptions, which we also adopt:

• Assumption 1. For all i ∈ N, j ∈ {1, 2, 3}, the valuation functions vij are non-negative and differentiable, and they are increasing in θi at a decreasing rate. Formally, v′i1 , v′i2 > 0, v′i3 ≥ 0 and v′′ i1 , v′′ i2 , v′′ i3 ≤ 0.
• Assumption 2. We also require the usual monotone hazard rate condition on the distributions. Formally, defining h(θi) = 1-Fi(θi) fi(θi) , we assume dh(θi) dθi ≤ 0 for each bidder i. 2 Commonly seen distributions, such as the normal, uniform, exponential, and logistic distributions, satisfy this condition.
• Assumption 3. For all i and θi, vi3(θi)-h(θi)v′i3 (θi) ≥ 0. As we shall see in the beginning of the next section

1 Moving beyond two items, Assumptions 1-2, below, do not change, and Assumption 3 still has to hold for all complementarity parameters, and now there are more of them. For example, in a 3-item auction, there is one such parameter for every pair of items.

2 As Levin points out, Assumption 2 is actually stronger than necessary. Together with the other assumptions here, it yields an easy sufficient condition for certain derived distributions to be regular, which is really the condition that is needed.

where we define virtual valuations, this means that we assume that the virtual valuation for complementarity is non-negative, regardless of θi.

3 Levin's optimal auction for complements

To describe Levin's optimal auction in this setting, define virtual valuation for i ∈ N, j ∈ {1, 2, 3} as

The seller is treated as an additional bidder 0 with virtual valuation ˜ v01 = ˜ v02 = ˜ v03 = 0.

By the revelation principle, Levin (and we) can focus only on mechanisms where each bidder is asked to report his type. For each type profile, Levin chooses the allocation ⃗xi = (xi1, xi2) that maximizes the virtual social welfare

Levin's payment rule is as follows.

• Bidders who receive nothing pay nothing.
• For a bidder i who wins only one item, say item j, let θ0 i be the lowest type he could have reported in order to win that item. He pays vij(θ0 i ).
• For a bidder i who wins both items, let θ1 i be the lowest type he could have reported in order to win both items and θ0 i be the lowest type with which he would have won one item. He pays vi1(θ0 i ) + vi2(θ1 i ) + vi3(θ1 i ) if θ0 i corresponds to item 1 and vi1(θ1 i )+vi2(θ0 i )+vi3(θ1 i ) if θ0 i corresponds to item 2.

A mechanism is (weakly) dominant strategy truthful if misreporting one's type cannot yield a higher utility for the bidder, no matter what other bidders report. A mechanism is ex-post individually rational if participation yields a nonnegative utility, no matter what other bidders report.

Theorem 1 ([Levin, 1997]) For the Levin setting, the auction above is optimal, among all mechanisms that are ex-post individually rational and weakly dominant strategy truthful. 3

4 A new form of "reserve pricing": Poking holes in the allocation space based on revealed types

Welfare-maximizing mechanisms choose an allocation that maximizes the sum of the agents' valuations (as opposed to Levin's virtual welfare-maximizing allocation). The most famous such mechanism is the Vickrey-Clarke-Groves mechanism (VCG) [Vickrey, 1961; Clarke, 1971; Groves, 1973], where each bidder i has to pay the sum of the others' valuations had i not participated minus the sum of the others' actual valuations. Any welfare-maximizing mechanism can yield expected revenue arbitrarily far from optimal:

3 Myerson's auction for a single item is simply a Levin's auction where vi2 = 0 and vi3 = 0 for all i, as if item 2 did not exist.

Example 4.1 This is easy to see even in a 1-item 2-bidder setting. Say that bidder 1's valuations is δ, 0 < δ < 1, and bidder 2's valuation is 1 with probability 1-ϵ and with probability ϵ, it is uniformly drawn between 0 and 1. In this setting, no mechanism that always maximizes social welfare can yield revenue more than δ. On the other hand, a mechanism that uses a reserve price just below 1 will generate expected revenue (1-ϵ) · 1. Letting δ and ϵ approach zero, we see that the welfare-maximizing mechanism can yield an arbitrarily small fraction of the available expected revenue.

As discussed in the introduction, prior "reserve pricing" approaches to increasing revenue in the VCG and its generalizations have been based on inserting one or more artificial bidders into the auction. In contrast, we introduce a different "reserve pricing", where allocations are precluded if they do not meet some criteria.

When applied to a welfare-maximizing mechanism, we call this template social welfare with holes because it "pokes holes" in the allocation space by precluding some allocations, and then maximizes welfare over the remaining allocation space. Poking holes is in contrast to the prior more restricted approach of using artificial bidder(s), which removes allocations from consideration in a more uniform, rigid manner.

In the rest of this paper, we restrict attention to mechanisms where the criteria are such that they can be applied to each bundle-agent pair (including 1-item bundles) 〈b, i〉 separately, and if the criterion for that 〈b, i〉 is not met, then all allocations that give exactly bundle b to bidder i are precluded. One such criterion is whether the virtual valuation for 〈b, i〉 exceeds some constant. One can also include further preclusion criteria. For example, in the next section we preclude 〈b, i〉 pairs where a subset of b would give higher virtual value for i than b does.

We have to be careful, though, because some instantiations of the new reserve pricing make the mechanism non-truthful:

Example 4.2 This can be shown already in the 2-item setting with just two bidders, i and j, even if both bidders have additive valuations (i.e., vi3 = vj3 = 0 for all types). Let bidder j have only one type and his valuations for the two items be 1 and 4, respectively. We consider three of bidder i's types: (vi1(θ1 i ) = 1, vi2(θ1 i ) = 4), (vi1(θ2 i ) = 5, vi2(θ2 i ) = 5), and (vi1(θ3 i ) = 6, vi2(θ3 i ) = 6). Let θ1 i be i's lowest type. (One can construct continuous valuation functions vi1 and vi2 (i.e., continuous functions of θi) that include these three points and satisfy all the conditions of the Levin model.) Say the mechanism precludes allocating the bundle of both items to bidder i in θ2 i and precludes allocating the bundle or item 1 to bidder i in θ3 i . We now calculate bidder i's Levin payment. At θ2 i , he gets item 1 and pays 1 because θ1 i is the lowest type with which he gets item 1. At θ3 i , he gets item 2 because of the preclusions and pays 6 because θ3 i is the lowest type with which he gets item 2. Thus, his payoff is 6-6=0. So, if his true type is θ3 i , he has an incentive to lie and report θ2 i instead because he would obtain utility 6-1=5 instead of 0.

Nisan and Ronen [2007] show that if one removes ex ante some allocations, and then maximizes welfare over the remaining space, and prices using the VCG, the resulting mechanism is truthful. Our approach is much more general because we allow the removal of allocations to depend on the bidders' reported types. As the above example shows, this increased generality comes at the risk of losing truthfulness.

Of course, used to the extreme, our generality allows any allocation rule, A, to be exactly simulated by one in our new class by having, for each type vector, all but the allocation prescribed by A precluded. However, we will not be using the generality to any extreme extent.

Another difference between our work and that of Nisan and Ronen is that we use Levin pricing while they use VCG pricing. Those two pricing rules are not the same even in the 1-item setting because Levin makes sure that if a bidder wins the item, he pays at least his valuation corresponding to his lowest winning type. The VCG does not have this "reserve price". The difference between the two pricing rules seems minor, however, because they coincide under a mild assumption on the valuation distributions:

Proposition 4.1 In the Levin setting, under a welfaremaximizing allocation rule, VCG prices and Levin prices coincide if vij(θi) = 0 for all i, j.

Proof:

• When bidder i receives nothing, the Levin price and the VCG price both equal 0.
• Now consider the situation where bidder i receives exactly one item. Without loss of generality, say this is item 1. Because valuations are nonnegative in the Levin setting, some bidder receives item 2; say, without loss of generality, this is bidder j. There are two cases:
• Case 1. Without i, the bundle would go to j (throughout the proof, j can be a bidder or the auctioneer). One can show that i's VCG payment is vj1(θj) + vj3(θj). Now define θ0 i such that vi1(θ0 i ) = vj1(θj) + vj3(θj). For bidder i, when his type θi > θ0 i , we have vi1(θi) + vj2(θj) ≥ vi1(θ0 i ) + vj2(θj) = vj1(θj) + vj2(θj) + vj3(θj). Thus, i gets item 1. Similarly, when his type θi ≤ θ0 i , i loses item 1. Therefore, θ0 i is exactly the lowest type with which i gets item 1. Thus the Levin price equals the VCG price.
• Case 2. Without i, item 1 would go to bidder k ̸= j and item 2 would still go to bidder j. Define θ0 i such that vi1(θ0 i ) = vk1(θk). Following a similar argument as Case 1, we still have that θ0 i is the lowest type with which i gets item 1.
• Now consider the situation where bidder i receives both items. Let θ1 i be the lowest type with which he wins both items, and θ0 i be the lowest type with which he wins one item, say item 1. There are two cases:
• Case 1. Without i, item 1 would go to bidder j and item 2 would go to bidder k. The VCG payment is vj1(θj) + vk2(θk). According to the welfaremaximizing allocation rule, we have vi1(θ0 i ) = vj1(θj ) and vi1(θ1 i )+vi2(θ1 i )+vi3(θ1 i ) = vi1(θ1 i )+ vk2(θk). Thus vk2(θk) = vi2(θ1 i ) + vi3(θ1 i ). Thus, vi1(θ0 i )+vj1(θj) = vi1(θ0 i )+vi2(θ1 i )+vi3(θ1 i ). In other words, the Levin price equals the VCG price.
• Case 2. Without i, the bundle of both items would go to some bidder j. The VCG payment is vj1(θj) + vj2(θj) + vj3(θj). There are two subcases:
• ∗ Subcase 1. The welfare of the second-best allocation is vj1(θj) + vj2(θj) + vj3(θj). Then we have vi1(θ1 i ) + vi2(θ1 i ) + vi3(θ1 i ) = vj1(θj) + vj2(θj) + vj3(θj). We now prove that θ0 i = θ1 i in this case. Suppose, for contradiction, θ0 i < θ1 i (of course, we cannot have θ0 i > θ1 i ). Then there exist a k such that vi1(θ0 i )+vk2(θk) = vj1(θj)+ vj2(θj) + vj3(θj). Since vi1 is increasing in θi, it must be the case that vi1(θ1 i ) + vk2(θk) > vj1(θj) + vj2(θj) + vj3(θj). Then the secondbest allocation would not be vj1(θj)+vj2(θj)+ vj3(θj). Contradiction.
• ∗ Subcase 2. The welfare of the second-best allocation is vi1(θi)+vk2(θk). We can use vi1(θ1 i )+ vi2(θ1 i ) + vi3(θ1 i ) = vi1(θ1 i ) + vk2(θk) to derive vk2(θk). Substituting that vk2(θk) into the equation vi1(θ0 i ) + vk2(θk) = vj1(θj) + vj2(θj) + vj3(θj) gives us an equality where the left hand side is the Levin price and the right hand side is the VCG price.

While we showed in Example 4.2 that some instantiations of our new hole poking method cause loss of truthfulness, we now show that a certain natural set of criteria for precluding allocations yields a mechanism that is truthful. Here the preclusions depend on the types, so this is quite different from the Nisan-Ronen approach. We also show that this instantiation of our new "reserve pricing" scheme yields a 2approximation of optimal revenue.

5 Monopoly reserves in welfare maximization

In this section we use a welfare-maximizing allocation rule, but we preprocess the allocation space to preclude 〈b, i〉 pairs that have negative virtual value, and we also preclude 〈b, i〉 pairs where a subset of b would give higher virtual value for i than b does. The motivation is that this will increase revenue over the vanilla welfare maximization because we know from Theorem 1 that revenue maximization is accomplished by maximizing the sum of virtual valuations.

We observe that another way to see this preprocessing is to realize that it is the optimal mechanism for the setting where each bidder, in turn, would be the only bidder. Optimal pricing schemes for one-bidder settings have been called "monopoly reserves" [Hartline & Roughgarden, 2009].

In this section, we describe the social welfare maximization with monopoly reserve prices (SWMR):

• Step 1. "Poke holes". For each bidder i, the seller defines 5 monopoly reserve types ˜ v-1 i1 (0), ˜ v-1 i2 (0) and (∑3j=1 ˜ vij)-1 (0), (˜ vi1 + ˜ vi3)-1 (0), (˜ vi2 + ˜ vi3)-1 (0). She asks bidders to report their types.

For each bidder i, if vi1(θi) < ˜ v-1 i1 (0), or equivalently ˜ vi1(θi) < 0, we delete all allocations in which i is awarded item 1 only.

Similarly, whenever ˜ vi2(θi) < 0, we delete all allocation in which i is awarded item 2 only.

Finally, we delete all allocation in which i is awarded both items if ˜ vi1(θi)+˜ vi2(θi)+˜ vi3(θi) < 0, or ˜ vi1(θi)+ ˜ vi3(θi) < 0, or ˜ vi2(θi) + ˜ vi3(θi) < 0.

• Step 2. Choose the welfare-maximizing allocation among the remaining allocations (ties can be broken arbitrarily). Use the Levin payment rule.

In this mechanism, for someone (e.g., a bidder) to verify that a correct allocation and payments were reached, all he needs to know about the prior are the five "reserve" numbers from Step 1. (Of course, he also needs to know the bids.) For example, the auctioneer can send those five numbers and the bids to each bidder. In contrast, in Levin's auction, one needs to know everyone's exact distribution functions in order to calculate the virtual social welfare, which determines the allocation and payments.

5.1 Truthfulness and individual rationality

Theorem 2 SWMR is (weakly) dominant strategy truthful and ex-post individually rational.

Proof: Ex-post individual rationality follows from the facts that (1) a bidder who wins nothing pays nothing, and (2) a bidder who wins something has a type that is no lower than the types used to determine what he has to pay.

We prove truthfulness via the following lemmas. A mechanism is allocation monotonic if fixing other bidders' reports, if a bidder i reporting θ0 i receives some item, he receives that item (and possibly others) for any report greater than θ0 i .

Lemma 5.1 SWMR is allocation monotonic.

Proof: Case 1. i receives exactly one item, say item 1, by reporting θ0 i . Let j be the agent that wins item 2. According to the allocation rule of SWMR, we know i values item 1 the most among all the bidders who meet their reserve conditions for item 1 (i.e., those whose virtual valuations for item 1 are nonnegative): vi1(θ0 i ) ≥ vk1(θk).We also have

≥ maximum social welfare given that i receives nothing.

Now we change θ0 i to any θi > θ0 i . Since v′i1 ≥ 0, the above equations continue to hold except for one case, where the maximum-welfare allocation changes to the one where i receives the bundle. This leads to the conclusion that i cannot end up with nothing by reporting a higher type.

We also need to show that i cannot end up with item 2 instead of item 1. Suppose he did. Then there is some θ1 i > θ0 i such that θ1 i meets i's reserve type for item 2 and k ̸= i such that vk1(θk) + vi2(θ1 i ) ≥ vi1(θ1 i ) + vi2(θ1 i ) + vi3(θ1 i ).4 The inequality above is equivalent to vk1(θk) ≥ vi1(θ1 i ) + vi3(θ1 i ). Since we know vi3(θ1 i ) ≥ 0 by complementarity, we have vk1(θk) ≥ vi1(θ1 i ) > vi1(θ0 i ). This contradicts the assumption that i values item 1 the most.

4 θ1 i exceeds i's reserve type for item 1 because θ1 i > θ0 i and θ0 i has already met or exceeded the reserve type. It must be the case that θ1 i meets or exceeds i's reserve types for the bundle because ˜ vi3(θ) ≥ 0 by Assumption 3 in Section 2. The reasoning above ensures that vi1(θ1 i ) + vi2(θ1 i ) + vi3(θ1 i ) is a valid social welfare.

Case 2. i receives both items by reporting θ0 i . According to the allocation rule, vi1(θ0 i ) + vi2(θ0 i ) + vi3(θ0 i ) is the maximum of social welfare. Since all three terms in the equation above are increasing in θi, vi1(θi) + vi2(θi) + vi3(θi) will maximize welfare for all θi ≥ θ0 i . Thus, the two items will still be allocated to bidder i.

Given Lemma 5.1, truthfulness of SWMR follows from the following three lemmas.

Lemma 5.2 A bidder who wins nothing when telling the truth cannot benefit from lying.

Proof: By reporting truthfully, he gets zero utility. If he under-reports, he still wins nothing, pays nothing, and gets zero utility. Now consider over-reporting. If he still wins nothing, then he still gets zero utility. If he wins one item, say item 1, he pays v1i(θ0 i ), where θ0 i is greater than his true type θi, so he gets negative utility v1i(θi)-v1i(θ0 i ). The case where he wins two items is similar.

Lemma 5.3 A bidder who wins exactly one item when telling the truth cannot benefit from lying.

Proof: Say, without loss of generality, that the item he wins is item 1. By reporting truthfully he gets utility vi1(θi) - vi1(θ0 i ) ≥ 0, with θi ≥ θ0 i . By under-reporting, he wins nothing with zero utility or still gets item 1 with unchanged utility. By over-reporting, he still wins item 1 with unchanged utility or wins both with reduced utility vi1(θi) + vi2(θi) + vi3(θi) - vi1(θ0 i ) - vi2(θ1 i ) - vi3(θ1 i ), with θ1 i ≥ θi ≥ θ0 i .

Lemma 5.4 A bidder who wins two items when telling the truth cannot benefit from lying.

Proof: Say, without loss of generality, that if he wins exactly one item, he wins item 1. His utility when telling the truth and winning both items is vi1(θi)+vi2(θi)+vi3(θi)-vi1(θ0 i )- vi2(θ1 i ) - vi3(θ1 i ), with θi ≥ θ1 i ≥ θ0 i . By under-reporting, if he still gets two items, the utility is unchanged. If he gets item 1 only, he get reduced utility vi1(θi)-vi1(θ0 i ). If hewins nothing, he gets zero utility, which is even worse. By overreporting, he still wins both items with unchanged utility.

This completes of the proof of truthfulness of SWMR.

5.2 SWMR 2-approximates optimal revenue

Theorem 3 SWMR 2-approximates the optimal revenue.

We prove this starting with a sequence of lemmas.

The famous Myerson's lemma [1981] shows that in any truthful single-item auction, the expected payment from any bidder i equals i's expected virtual valuation. We now give a similar result in our more general setting.

Lemma 5.5 For any auction that satisfies (a) truthfulness, (b) allocation monotonicity and (c) bidders with lowest type always get zero utility, we have that

Proof: Fixing other bidders' reports, allocation monotonicity tells us there are two cutoff types θ0 i ≤ θ1 i for bidder i. When his type is below θ0 i , he receives nothing; when his type is between θ0 i and θ1 i , he receives one item; and when his type is above θ1 i , he receives both items.

Truthfulness tells us that the cutoffs θ0 i and θ1 i cannot depend on i's own report Truthfulness also tells us that i's payment for each possible allocation to him is fixed (does not depend on his report) and his utility increases continuously as his allocation changes as his type increases.

Condition (c) then guarantees that bidder i pays exactly vi1(θ0 i ) when he receives one item and vi2(θ1 i )+vi3(θ1 i ) more for receiving the second item. So, conditions (a),(b), and (c) uniquely define Levin's payment rule.

Suppose bidder i receives item 1 first. His expected payment (again, conditional on fixing the others' bids) is

His expected virtual valuation is

We complete the proof of Lemma 5.5 by taking expectations Eθ-i of the first line and the last line of this equation sequence (which assumed the types of the other bidders, θ-i, were given), and then we sum both sides over all bidders.

It is easy to see that both welfare maximization with Levin's payment rule and SWMR satisfy (a), (b), and (c).

Lemma 5.6 For any bidder i and allocation (xi1, xi2), i's payment plus virtual valuation is no less than i's valuation:

Proof: If i receives nothing, the above holds with equality.

If i receives one item, say item 1, let θ0 i be the lowest type with which i would have won item 1 and θ1 i be the type when ˜ vi1(θ1 i ) = 0. Clearly, θi ≥ θ0 i ≥ θ1 i . Thus,

The last inequality follows from h(θi)v′i1 (θi) being weakly decreasing in θi.

If i receives two items, let θ1 i be the lowest type with which he would have won both and θ0 i be the lowest type withwhich he would have won one item, say item 1. We must have θi ≥ θ1 i ≥ θ0 i . Let θ2 i be the type such that ˜ vi1(θ2 i ) = 0 and θ3 i be the type such that ˜ vi2(θ3 i ) + ˜ vi3(θ3 i ) = 0. According to the Step 1 of SWMR we have θ0 i ≥ θ2 i and θ1 i ≥ θ3 i . Thus,

Again, the last inequality follows from h(θi)v′i1 (θi) being weakly decreasing in θi.

We are now ready to prove Theorem 3.

Proof: Let ⃗x be the allocation rule of SWMR and ⃗xL be that of Levin's optimal auction. Note that Levin's auction has all the allocation restrictions that ours has (and possibly more) and SWMR maximizes welfare in this restricted set. Therefore, our efficiency is greater (or equal) to that of Levin's. Formally, for any θ,

According to Lemma 5.5, we have

According to Lemma 5.6, we have

Combining (2) and (3), we have

Combining (1) and (4), we have

The last inequality follows from the individual rationality of Levin's auction.

We conjecture that the approximation bound of 2 is tight.

6 Anonymous "reserve prices" in welfare maximization

In many applications, the seller does not have the freedom to use bidder-specific reserve prices. Instead, she is constrained to treating every bidder symmetrically, i.e., the reserve prices must be anonymous. Recall that in symmetric (that is, with i.i.d bidders) single-item settings, the secondprice auction-which maximizes welfare-with a monopoly reserve price is optimal [Myerson, 1981]. Without the i.i.d assumption, a Vickrey auction with some anonymous reserve price 4-approximates optimal revenue [Hartline & Roughgarden, 2009]. How well does a welfare-maximizing mechanism with anonymous reserves do in our more general setting?

Definition 6.1 (SWAR mechanism) In SWAR, we pretend the seller has valuation a for the first item, b for the second item, and c for the bundle. Then, a welfare-maximizing allocation rule is used, followed by the Levin payment rule.

Theorem 4 SWAR 6-approximates Levin's optimal revenue.

We prove the theorem through two lemmas as follows.

Lemma 6.1 Auction 1 below 3-approximates Auction 2:

1. For each bidder i (not including the seller), introduce a new bidder whose type is drawn i.i.d from the same distribution as i's, and whose valuation function is also the same as i's. Then run welfare maximization with the Levin payment rule on this enlarged set of bidders.
2. Levin's optimal auction on the original set of bidders (not including the seller).

Given Lemma 6.1, Theorem 4 follows Lemma 6.2.

Lemma 6.2 Let a, b, and c be random variables that simulate maxi{vi1}, maxi{vi2} and maxi{vi1 + vi2 + vi3}, respectively, in the original bidder set. SWAR with (a, b, c) is then a 2-approximation of Auction 1 of Lemma 6.1.

Proof: For expected revenue, the reserve prices (a, b, c) simulate (and thus can replace) all the duplicated bidders.

7 Conclusions and future research

We introduced a new research avenue for increasing revenue where we poke holes in the allocation space-based on the bids (revealed types)-and then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the first step down this avenue, we introduced a new form of "reserve pricing" into CAs. We showed that the optimal revenue for complements can be 2-approximated by using "monopoly reserve prices" to curtail the allocation set, followed by welfare-maximizing allocation and Levin's payment rule. A key lemma of potential independent interest is that the expected revenue from any truthful allocationmonotonic mechanism equals the expected virtual valuation; this generalizes Myerson's lemma [1981] from the singleparameter environment. Like the VCG, our mechanism uses welfare-maximization as the allocation rule. Under a mild assumption on valuation distributions, the payment rules also coincide. So, being close to the gold standard of CAs (VCG), our mechanisms are likely easier to adopt than Levin's. Our mechanisms also require much less information about the priors, for example, in order to verify correct execution of the mechanism. Our mechanism is also more efficient than Levin's. Finally, we showed that the optimal revenue can be 6-approximated even if the "reserve pricing" is required to be symmetric across bidders.

Future work includes studying the tightness of our approximation bounds. Second, are there other interesting instantiations of our new "reserve pricing" framework (beyond our monopoly pricing) that are truthful, individually rational, and have some other desirable properties? Future research also includes extending our "reserve pricing" method-or our hole-poking approach more generally-to other environments, such as those with multi-dimensional type spaces.