CPS 296.1 Auctions & Combinatorial AuctionsA few different 1-item auction mechanismsComplementarity and substitutabilityInefficiency of sequential auctionsCombinatorial auctionsThe winner determination problem (WDP)WDP examplePrice-based argument for optimalityPrice-based argument does not always give matching upper boundAn integer program formulationPrice-based argument does always work for partially acceptable bidsWeighted independent setThe winner determination problem as a weighted independent set problemDynamic programming approach to WDP [Rothkopf et al. 98]Bids on connected sets of items in a treeMaximum weighted matching (not necessarily on bipartite graphs)Bids with few items [Rothkopf et al. 98]Variants [Sandholm et al. 2002]: combinatorial reverse auctionWDP example (as CRA)Variants: multi-unit CAs/CRAsMulti-unit WDP example (as CA/CRA)Variants: (multi-unit) combinatorial exchangesCE WDP exampleVariants: no free disposal(back to 1-unit CAs) Expressing valuation functions using bundle bidsAlternative approach: report entire valuation functionExponentially many bundlesBidding languagesXORsWDP and bidding languagesCPS 296.1Auctions & Combinatorial AuctionsVincent Conitzer [email protected] few different 1-item auction mechanisms•English auction:–Each bid must be higher than previous bid–Last bidder wins, pays last bid•Japanese auction:–Price rises, bidders drop out when price is too high–Last bidder wins at price of last dropout •Dutch auction:–Price drops until someone takes the item at that price•Sealed-bid auctions (direct revelation mechanisms):–Each bidder submits a bid in an envelope–Auctioneer opens the envelopes, highest bid wins•First-price sealed-bid auction: winner pays own bid•Second-price sealed bid (or Vickrey) auction: winner pays second-highest bidComplementarity 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, …The winner determination problem (WDP)•Choose a subset A (the accepted bids) of the bids B, •to maximize Σb in Avb, •under the constraint that every item occurs at most once in A–This is assuming free disposal, i.e., not everything needs to be allocatedWDP example•Items A, B, C, D, E•Bids:•({A, C, D}, 7)•({B, E}, 7)•({C}, 3)•({A, B, C, E}, 9)•({D}, 4)•({A, B, C}, 5)•({B, D}, 5)•What’s an optimal solution?•How can we prove it is optimal?Price-based argument for optimality•Items A, B, C, D, E•Bids:•({A, C, D}, 7)•({B, E}, 7)•({C}, 3)•({A, B, C, E}, 9)•({D}, 4)•({A, B, C}, 5)•({B, D}, 5)•Suppose we create the following “prices” for the items:•p(A) = 0, p(B) = 7, p(C) = 3, p(D) = 4, p(E) = 0•Every bid bids at most the sum of the prices of its items, so we can’t expect to get more than 14.Price-based argument does not always give matching upper bound•Items A, B, C•Bids:•({A, B}, 2)•({B, C}, 2)•({A, C}, 2)•Clearly can get at most 2•If we want to set prices that sum to 2, there must exist two items whose prices sum to < 2•But then there is a bid on those two items of value 2–(Can set prices that sum to 3, so that’s an upper bound)Should not be surprising, since it’s an NP-hard problem and we don’t expect short proofs for negative answers to NP-hard problems (we don’t expect NP = coNP)An 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 bundlePrice-based argument does always work for partially acceptable bids•Items A, B, C•Bids:•({A, B}, 2)•({B, C}, 2)•({A, C}, 2)•Now can get 3, by accepting half of each bid•Put a price of 1 on each itemGeneral proof that with partially acceptable bids, prices always exist to give a matching upper bound is based on linear programming dualityWeighted independent set•Choose subset of the vertices with maximum total weight,•Constraint: no two vertices can have an edge between them•NP-hard (generalizes regular independent set)2234324The winner determination problem as a weighted independent set problem•Each bid is a vertex•Draw an edge between two vertices if they share an item•Optimal allocation = maximum weight independent set•Can model any weighted independent set instance as a CA winner determination problem (1 item per edge (or clique))•Weighted independent set is NP-hard, even to solve approximately [Håstad 96] - hence, so is WDP–[Sandholm 02] noted that this inapproximability applies to the WDPDynamic 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’)}•Requires exponential timeBids on connected sets of items in a tree•Suppose items are organized in a treeitem Aitem Bitem Citem Ditem Eitem Fitem Gitem H•Suppose each bid is on a connected set of items–E.g. {A, B, C, G}, but not {A, B, G}•Then the WDP can be solved in polynomial time (using dynamic programming) [Sandholm & Suri 03]•Tree does not need to be given: can be constructed from the bids