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 StructureCombinatorial AuctionsLog(m)-approximation for CF auctionsAn incentive compatible O(m1/2)-approximation of CF auctions using value queries.2-approximation for XOS auctionsA lower bound of e/(e-1)- for XOS auctions3Combinatorial AuctionsA set M of items for sale. |M|=m.n bidders, each bidder i has a valuation function vi:2M->R+.Common assumptions:Normalization: vi()=0Free disposal: ST  vi(T) ≥ vi(S)Goal: find a partition S1,…,Sn such that social welfare vi(Si) is maximized4Combinatorial AuctionsProblem 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 AuctionsWe 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 ModelsCommon 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)-jSpj.General: any possible type of query (the comunication model).Demand queries are strictly more powerful than value queries (Blumrosen-Nisan, Dobzinski-Schapira)8Known ResultsFinding an optimal solution requires exponential communication. Nisan-SegalFinding 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 ValuationsComplement-Free: v(ST) ≤ v(S) + v(T).XOS: XOR of ORs of singletonsExample: (A:2 OR B:2) XOR (A:3)Submodular: v(ST) + v(ST) ≤ v(S) + v(T).2-approximation by LLN.GS: (Gross) Substitutes, OXS: OR of XORs of singletonsSolvable in polynomial time (LP and Maximum Weighted Matching respectively)OXS  GS  SM  XOS  CFLehmann, Lehmann, Nisan10Talk StructureCombinatorial AuctionsLog(m)-approximation for CF auctionsAn incentive compatible O(m1/2)-approximation CF auctions using value queries.2-approximation for XOS auctionsA lower bound of e/(e-1)- for XOS auctions11IntuitionWe 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 1Solve the linear relaxation of the problem:Maximize: i,Sxi,Svi(S)Subject To: For each item j: i,S|jSxi,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 2Use 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 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.15The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B D16The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B DS11 = {A,B,D}17The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B DC EA D18The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.C EA DS21 = {C,E}S22 = {A,D}19The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B DC EA DC EA20The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.C EAS32 = {C,E}S33 = {A}21The Algorithm – Step 3For each bidder i, partition Si into a disjoint union Si = Si1.. Sik such that for each1≤i<i’≤ n, 1≤t≤t’≤ k, SitSi’t’=.A B DC EA DC EABD22The Algorithm – Step 3For each bidder i, partition Si into a