Combinatorial auctionsComplementarity and substitutabilityInefficiency of sequential auctionsSlide 4Exponentially many bundlesBidding languagesXORsThe winner determination problem (WDP)WDP and bidding languagesDynamic programming approach to WDP [Rothkopf et al. 98]The winner determination problem as a weighted independent set problemAn integer program formulationBids with few items [Rothkopf et al. 98]Bids on connected sets of items in a treeGeneralized Vickrey Auction (GVA) (= VCG applied to combinatorial auctions)Variants [Sandholm et al. 2002]Combinatorial auctionsVincent Conitzer [email protected]() = $500v() = $700Complementarity and substitutability •How valuable one item is to a bidder may depend on whether the bidder possesses another item•Items a and b are complementary if v({a, b}) > v({a}) + v({b})•E.g.•Items a and b are substitutes if v({a, b}) < v({a}) + v({b})•E.g.Inefficiency of sequential auctions •Suppose your valuation function is v( ) = $200, v( ) = $100, v( ) = $500•Now suppose that there are two (say, Vickrey) auctions, the first one for and the second one for•What should you bid in the first auction (for )?•If you bid $200, you may lose to a bidder who bids $250, only to find out that you could have won for $200•If you bid anything higher, you may pay more than $200, only to find out that sells for $1000•Sequential (and parallel) auctions are inefficientCombinatorial auctionsv() = $500v() = $700v() = $300Simultaneously for sale: , , bid 1bid 2bid 3used in truckload transportation, industrial procurement, radio spectrum allocation, …Exponentially many bundles•In general, in a combinatorial auction with set of items I (|I| = m) for sale, a bidder could have a different valuation for every subset S of I–Implicit assumption: no externalities (bidder does not care what the other bidders win)•Must a bidder communicate 2m values?–Impractical–Also difficult for the bidder to evaluate every bundle•Could require vi(Ø) = 0–Does not help much•Could require: if S is a superset of S’, v(S) ≥ v(S’) (free disposal)–Does not help in terms of number of valuesBidding languages•Bidding language = a language for expressing valuation functions•A good bidding language allows bidders to concisely express natural valuation functions•Example: the OR bidding language [Rothkopf et al. 98, DeMartini et al. 99]•Bundle-value pairs are ORed together, auctioneer may accept any number of these pairs (assuming no overlap in items)•E.g. ({a}, 3) OR ({b, c}, 4) OR ({c, d}, 4) implies–A value of 3 for {a}–A value of 4 for {b, c, d}–A value of 7 for {a, b, c}•Can we express the valuation function v({a, b}) = v({a}) = v{b} = 1 using the OR bidding language?•OR language is good for expressing complementarity, bad for expressing substitutabilityXORs•If we use XOR instead of OR, that means that only one of the bundle-value pairs can be accepted•Can express any valuation function (simply XOR together all bundles)•E.g. ({a}, 3) XOR ({b, c}, 4) XOR ({c, d}, 4) implies–A value of 3 for {a}–A value of 4 for {b, c, d}–A value of 4 for {a, b, c}•Sometimes not very concise•E.g. suppose that for any S, v(S) = Σs in Sv({s})–How can this be expressed in the OR language?–What about the XOR language?•Can also combine ORs and XORs to get benefits of both [Nisan 00, Sandholm 02]•E.g. (({a}, 3) XOR ({b, c}, 4)) OR ({c, d}, 4) implies–A value of 4 for {a, b, c}–A value of 4 for {b, c, d}–A value of 7 for {a, c, d}The winner determination problem (WDP)•Allocate a subset Si of I to each bidder i to maximize Σivi(Si) (under the constraint that for i≠j, Si ∩ Sj = Ø)–This is assuming free disposal, i.e. not everything needs to be allocated•Complexity of the winner determination problem depends on the bidding languageWDP and bidding languages•Single-minded bidders bid on only one bundle–Valuation is x for any subset including that bundle, 0 otherwise•If we can solve the WDP for single-minded bidders, we can also solve it for the OR language–Simply pretend that each bundle-value pair comes from a different bidder•We can even use the same algorithm when XORs are added, using the following trick:–For bundle-value pairs that are XORed together, add a dummy item to them [Fujishima et al 99, Nisan 00]–E.g. ({a}, 3) XOR ({b, c}, 4) becomes ({a, dummy1}, 3) OR ({b, c, dummy1}, 4)•So, we will focus on single-minded bidsDynamic programming approach to WDP [Rothkopf et al. 98]•For every subset S of I, compute w(S) = the maximum total value that can be obtained when allocating only items in S•Then, w(S) = max {maxi vi(S), maxS’: S’ is a subset of S, and there exists a bid on S’ w(S’) + w(S \ S’)}•Runs in O(n3m) timeThe winner determination problem as a weighted independent set problem•Each (single-minded) bid is a vertex•Draw an edge between two vertices if they share an item•Optimal allocation = maximum weight independent set•Can model each weighted independent set instance as a CA winner determination problem (1 item per edge (or clique))•But weighted independent set cannot be approximated to k = n1-ε unless NP = ZPP [Håstad 96] –[Sandholm 02] noted that this inapproximability applies to the WDPAn integer program formulation•xb equals 1 if bid b is accepted, 0 if it is notmaximize Σb vbxbsubject tofor each item j, Σb: j in b xb ≤ 1•If each xb can take any value in [0, 1], we say that bids can be partially accepted•In this case, this is a linear program that can be solved in polynomial time•This requires that–each item can be divided into fractions–if a bidder gets a fraction f of each of the items in his bundle, then this is worth the same fraction f of his value vb for the bundle•Under certain conditions, the optimal solution to the linear program will be integralBids with few items [Rothkopf et al. 98]•If each bid is on a bundle of at most two items, then the winner determination problem can be solved in polynomial time as a maximum weighted matching problem –3-item example:item Aitem Bitem CA’s dummyB’s dummyC’s dummyValue of highest bid on {A}Value of highest bid on {B}Value of highest bid on {C}Value of highest bid on {A, B}Value of highest bid on {A, C}Value of highest bid on {B, C}•If each bid is on a bundle of three items, then the winner determination problem is NP-hard again (can reduce from