Report

Approximating optimal combinatorial auctions for complements using restricted welfare maximization Pingzhong Tang and Tuomas Sandholm Computer Science Department Carnegie Mellon University High-level contributions • New approach to mechanism design: “Social welfare with holes” – I.e., curtail the set of allocations based on agents’ reports (e.g., bids), and use welfare maximization within remaining set – Unlike maximum-in-range approach [Nisan and Ronen 07], where the allocation set is curtailed ex ante – Completely general (e.g., remove all but one allocation) – Trickier because not all report-based ways of curtailing are incentive compatible (paper contains an example) – We present the first (non-trivial) such curtailing that maintains incentive compatibility – Hopefully, a fruitful avenue going forward • New, general form of reserve pricing for combinatorial auctions – Any efficient mechanism can be arbitrarily far from optimal revenue, while our reserves avoid this downside Background • Optimal (i.e., expected revenue maximizing) auctions known for: – Single item [Myerson 81] – Multiple identical units [Maskin and Riley 89] – Multiple items with complementarities in a 1-dimensional setting [Levin 97] • These are all based on virtual welfare maximization – Requires prior information – Complex and unintuitive – Inefficient • Welfare maximizing allocation rule, but with reserve prices – Symmetric (1-item) setting: Identical to Myerson – Asymmetric (1-parameter) setting: 2-approximation [Hartline and Roughgarden EC-09] Our technical contributions • We approximate Levin's optimal auction for complements using welfare maximization with a form of reserve pricing for combinatorial auctions – Reserve prices restrict allocations based on bids – In Levin's setting, we use a specific form: Monopoly reserves – We obtain a 2-approximation to optimal revenue • And a 6-approximation using anonymous reserves • Why are we doing this? – More efficient than Levin’s auction • Any efficient mechanism has arbitrarily low revenue (e.g., in the paper) – Requires less info to verify correct execution of the mechanism (given the reserves) – Simpler, easier to understand – Better starting points for automated mechanism design (than, e.g., VCG) Myerson's setting • Seller has 1 indivisible item for sale, which he values at 0 • Set of bidders 1,…,n – Bidder i’s valuation, vi , is private knowledge – Distribution Fi and regular density fi, according to which vi is drawn, are common knowledge – Quasi-linearity: ui = vi – paymenti • Two constraints: – (Ex interim) incentive compatibility – (Ex interim) individual rationality • Objective: Maximize seller's expected revenue Myerson's solution • Asymmetric case: fi’s are different – Virtual valuation: – Allocation rule: Give the item to the bidder with the highest virtual valuation, if it is positive and retain the item otherwise – Payment rule: The lowest bid by i that would have won – Interpretation: Run second price auction on the virtual valuations, with reserve price 0 • Symmetric case: fi = fj – Optimal auction is a 2nd-price auction with monopoly reserve price – Monopoly reserve price: vri such that More about asymmetric case… • 2nd-price auction with monopoly reserve prices (one per bidder) is a 2-approximation of Myerson's optimal auction [Hartline and Roughgarden EC-09] • A key step: Myerson's Lemma [1981] – Lemma: For any truthful 1-item auction, expected payment from a bidder equals his expected virtual valuation Levin's setting: Complements with 1-dimensional type • Seller has 2 items for sale, which he values at 0 – All his results (and ours) extend to m items • Set of bidders 1,…,n – Bidder i’s type θi is private knowledge – Distribution Fi and regular density fi, according to which θi is drawn, are common knowledge – Bidder i 's valuation function is v – Quasi-linearity: ui() = vi() - paymenti • Two constraints: – (Ex interim) incentive compatibility – (Ex interim) individual rationality • Objective: Maximize seller's expected revenue Levin's solution • Virtual valuation: • Allocation Rule: Maximize virtual social welfare, among all the positive virtual valuations • Payment rule: Case I: Agent i wins item 1 first: Pay 0, get nothing Pay vi1(θ0), get item 1 θ0 Pay additional vi2(θ1)+ vi3(θ1), get both items θ1 Case II: Agent i wins item 2 first: Pay 0, get nothing Pay vi2(θ0), get item 2 θ0 Pay additional vi1(θ1)+ vi3(θ1), get both items θ1 Approximating Levin's auction • Why difficult? – Multiple definitions of reserve prices in combinatorial settings • One fake bidder, two fake bidders, bidder-specific... • What are monopoly reserves in combinatorial settings? – Myerson's Lemma in this setting? – [Hartline and Roughgarden EC-09] approach doesn't apply Our allocation-curtailing approach applied to Levin's setting • Idea – Preclude bidder-bundle pairs that have negative virtual valuations – Preclude bidder-bundle pairs where removing some item(s) from a bidder gives that bidder higher virtual value • Theorem – Together with welfare-maximization allocation rule and Levin's payment rule, the preclusions above constitute an auction that • is incentive compatible (in weakly dominant strategies), • is individually rational, and • 2-approximates Levin's revenue Desirable properties of our auction • Incentive compatible, individually rational, 2-approximation – Important step for proving this is allocation monotonicity: Fixing others' reports, a bidder's set of allocated items is expanding in his report • More efficient than Levin – Less restriction of the allocation space – Welfare maximizing in this less restricted space • Requires less information, e.g., to verify correct execution – 5 numbers versus distribution function • Easier to understand • A bidder in his lowest type gets zero payoff • For any allocation, a bidder's payment plus his virtual valuation is no less than his real valuation – We use this in 2-approximation proof Extending Myerson's Lemma to this setting • Myerson's Lemma: Bidder’s expected payment equals his expected virtual value • Our conditions: – 1. Truthful – 2. Allocation monotonic – 3. Lowest type gets zero payoff • Our auction satisfies 1, 2 and 3 • Levin's conditions: – a. Truthful – b. Revenue-maximizing – c. Utility functions satisfy the requirements of envelope theorem Proof of 2-approximation • Let M be the social welfare maximizing mechanism under monopoly reserves (i.e, our auction) • Step 1. By definition, M maximizes restricted social welfare • Step 2. By Myerson’s lemma extended to this setting, expected revenue of M = expected sum of bidders’ virtual valuations in M • Step 3. As we prove, in M, a bidder's payment plus his virtual valuation is no less than his real valuation • Step 4. By Steps 2 and 3, 2 * [Expect revenue of M] ≥ social welfare of M • Step 5. By Steps 1 and 4, 2 * [Expect revenue of M] ≥ social welfare of Levin • Step 6. By individual rationality, social welfare of Levin ≥ revenue of Levin QED 6-approximation of Levin’s optimal revenue using anonymous reserves • Now, usual definition of reserve price: – Seller pretends to have valuation a for 1st item, b for 2nd item, and c for bundle • Auction L: Levin's optimal auction on original set of bidders • Auction D: Duplicate each bidder. Then apply welfare-maximizing allocation rule and Levin payment rule • Step 1. Auction D 3-approximates Auction L • Step 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 • Step 3. Step 2 trivially yields a 2-approximation of D. Hence, a 6approximation of L QED • In contrast to 4-approximation for 1-item setting [Hartline & Roughgarden EC-09] Conclusions • New general approach to mechanism design: Social welfare with holes • New general form of reserve pricing under welfare maximization in combinatorial auctions • Application of this idea to Levin's setting of 1-D complements: – 2-approximation to revenue • 6-approximation with anonymous reserves – – – – More efficient than Levin Requires less info to verify correct execution (given reserves) Easier to understand Extended Myerson’s lemma to this setting Future work • Characterizing truthful restrictions – 1-item setting: Equivalent to allocation monotonicity – Levin's setting: • In our follow-on work we have found a necessary condition (e.g., can go from nothing to winning Item 1 to winning Item 2 to winning both) • Plan to search for optimal auctions under this condition • Application to other settings • Application to automated mechanism design