**Unformatted text preview:**

Approximation Algorithms for Combinatorial Auctions with Complement-Free BiddersTalk StructureCombinatorial AuctionsSlide 4Slide 5Access ModelsSlide 7Known ResultsThe Hierarchy of CF ValuationsSlide 10IntuitionThe Algorithm – Step 1The Algorithm – Step 2The Algorithm – Step 3Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22The Algorithm – Step 4A Communication Lower Bound of 2-e for CF ValuationsSlide 25Incentive Compatibility & VCG PricesSlide 27VCG on a Subset of the RangeThe AlgorithmThe Algorithm (Cont.)Proof of the Approximation RatioSlide 32Definition of XOSXOS PropertiesSupporting PricesAlgorithm-ExampleSlide 37Slide 38Slide 39ProofProof – Lemma 1Proof – Lemma 2Slide 43XOS Lower Bounds:Max-k-CoverThe ReductionOpen Questions – Narrowing the GapsApproximation Algorithms forCombinatorial Auctions with Complement-Free BiddersSpeaker: Michael SchapiraJoint work with Shahar Dobzinski & Noam Nisan2Talk StructureCombinatorial AuctionsLog(m)-approximation for CF auctionsAn incentive compatible O(m1/2)-approximation of CF auctions using value queries.2-approximation for XOS auctionsA lower bound of e/(e-1)- for XOS auctions3Combinatorial AuctionsA set M of items for sale. |M|=m.n bidders, each bidder i has a valuation function vi:2M->R+.Common assumptions:Normalization: vi()=0Free disposal: ST vi(T) ≥ vi(S)Goal: find a partition S1,…,Sn such that social welfare vi(Si) is maximized4Combinatorial AuctionsProblem 1: finding an optimal allocation is NP-hard.Problem 2: valuation length is exponential in m.Problem 3: how can we be certain that the bidders do not lie ? (incentive compatibility)5Combinatorial AuctionsWe are interested in algorithms that based on the reported valuations {vi }i output an allocation which is an approximation to the optimal social welfare.We require the algorithms to be polynomial in m and n. That is, the algorithms must run in sub-linear (polylogarithmic) time.We explore the achievable approximation factors.6Access ModelsHow can we access the input ?One possibility: bidding languages.The “black box” approach: each bidder is represented by an oracle which can answer certain queries.7Access ModelsCommon types of queries:Value: given a bundle S, return v(S).Demand: given a vector of prices (p1,…, pm) return the bundle S that maximizes v(S)-jSpj.General: any possible type of query (the comunication model).Demand queries are strictly more powerful than value queries (Blumrosen-Nisan, Dobzinski-Schapira)8Known ResultsFinding an optimal solution requires exponential communication. Nisan-SegalFinding an O(m1/2-)-approximation requires exponential communication. Nisan-Segal. (this result holds for every possible type of oracle)Using demand oracles, a matching upper bound of O(m1/2) exists (Blumrosen-Nisan).Better results might be obtained by restricting the classes of valuations.9The Hierarchy of CF ValuationsComplement-Free: v(ST) ≤ v(S) + v(T).XOS: XOR of ORs of singletonsExample: (A:2 OR B:2) XOR (A:3)Submodular: v(ST) + v(ST) ≤ v(S) + v(T).2-approximation by LLN.GS: (Gross) Substitutes, OXS: OR of XORs of singletonsSolvable in polynomial time (LP and Maximum Weighted Matching respectively)OXS GS SM XOS CFLehmann, Lehmann, Nisan10Talk StructureCombinatorial AuctionsLog(m)-approximation for CF auctionsAn incentive compatible O(m1/2)-approximation CF auctions using value queries.2-approximation for XOS auctionsA lower bound of e/(e-1)- for XOS auctions11IntuitionWe will allow the auctioneer to allocate k duplicates from each item.Each bidder is still interested in at most one copy of each item (so valuations are kept the same).Using the assumption that all valuations are CF, we will find an approximation to the original auction, based on the k-duplicates allocation.12The Algorithm – Step 1Solve the linear relaxation of the problem:Maximize: i,Sxi,Svi(S)Subject To: For each item j: i,S|jSxi,S ≤ 1 For each bidder i: Sxi,S ≤ 1 For each i,S: xi,S ≥ 0 Despite the exponential number of variables, the LP relaxation may still be solved in polynomial time using demand oracles.(Nisan-Segal). OPT*=i,Sxi,Svi(S) is an upper bound for the value of the optimal integral allocation.13The Algorithm – Step 2Use randomized rounding to build a “pre-allocation” S1,..,Sn:Each item j appears at most k=O(log(m)) times in {Si}i.ivi(Si) ≥ OPT*/2.Randomized Rounding: For each bidder i, let Si be the bundle S with probability xi,S, and the empty set with probability 1-Sxi,S.The expected value of vi(Si) is Sxi,Svi(S)We use the Chernoff bound to show that such “pre-allocation” is built with high probability.14The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.15The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B D16The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B DS11 = {A,B,D}17The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B DC EA D18The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.C EA DS21 = {C,E}S22 = {A,D}19The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B DC EA DC EA20The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.C EAS32 = {C,E}S33 = {A}21The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B DC EA DC EABD22The Algorithm – Step 3For each bidder i, partition Si into a