CPS 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 •Dutchauction:– 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•xbequals 1 if bid b is accepted, 0 if it is not maximize Σbvbxb subject to for each item j, Σb: j in bxb≤ 1•If each xbcan 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 vbfor 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 itemv() = $500bid 1v() = $700bid 2v() = $300bid 3• 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 {maxivi(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 in polynomial time if it exists [Conitzer, Derryberry, Sandholm 04]• More generally, WDP can also be solved in polynomial time for graphs of bounded treewidth[Conitzer, Derryberry, Sandholm 04]– Even further generalization given by [Gottlob, Greco 07]Maximum weighted matching(not necessarily on bipartite graphs)• Choose subset of the edges with maximum total weight,• Constraint: no two edges can share a vertex• Still solvable in polynomial time12343245Bids 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 matchingproblem – 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
View Full Document
Unlocking...