Approximation Algorithms for�Combinatorial Auctions with Complement-Free Bidders

Speaker: Shahar Dobzinski

Joint work with Noam Nisan & Michael Schapira

Talk Structure

• 🡺Combinatorial Auctions
• Log(m)-approximation for CF auctions
• An incentive compatible O(m^1/2)-approximation CF auctions
• A lower bound of 2-ε for CF auctions
• 2-approximation for XOS auctions
• A lower bound of e/(e-1)-ε for XOS auctions

2

Combinatorial Auctions

• m items for sale.
• n bidders, each bidder i has a valuation function v_i:2^M->R⁺.

Common assumptions:

• Normalization: v_i(∅)=0
• Free disposal: S⊆T 🡺 v_i(T) ≥ v_i(S)
• Goal: find a partition S₁,…,S_n such that social welfare Σv_i(S_i) is maximized.

​

• Problem 1: finding an optimal allocation is NP-hard.
• Problem 2: valuation length is exponential in n and m.

3

Access Models

• One possibility: bidding languages.
• In this talk: each bidder is represented by an oracle which can answer only a specific type of queries.
• Common types of queries:
• Value: given a bundle S, return v(S).
• Demand: given a vector of prices p, return the bundle S that maximizes v(S)-Σp_i.
• General: any type of possible query.
• Demand queries are more powerful than value queries (Blumrosen-Nisan)

4

Known Results

• Finding an exact solution requires exponential communication. Nisan-Segal
• Finding an O(m^1/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(m^1/2) exists (Blumrosen-Nisan).

​

• Better results might be obtained by using restricted classes of valuations.

5

The 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
• Solvable in polynomial time
• OXS: OR of XORs of singletons

6

OXS ⊂ GS ⊂ SM ⊂ XOS ⊂ CF

Lehmann, Lehmann, Nisan

Talk Structure

• Combinatorial Auctions
• 🡺Log(m)-approximation for CF auctions
• An incentive compatible O(m^1/2)-approximation CF auctions
• A lower bound of 2-ε for CF auctions
• 2-approximation for XOS auctions
• A lower bound of e/(e-1)-ε for XOS auctions

7

Intuition

• 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 approximate solution to the original auction, based on the k-duplicates allocation.

​

8

The Algorithm – Step 1

• Solve the linear relaxation of the problem:

Maximize: Σ_i,Sx_i,Sv_i(S)

Subject To:

• For each item j: Σ_i,S|j∈Sx_i,S ≤ 1
• For each bidder i: Σ_Sx_i,S ≤ 1
• For each i,S: x_i,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,Sx_i,Sv_i(S) is an upper bound for the value of the optimal integral allocation.

​

9

The Algorithm – Step 2

• Use randomized rounding to build a “pre-allocation” S₁,..,S_n:
• Each item j appears at most k=O(log(m)) times in {S_i}_i.
• Σ_iv_i(S_i) ≥ OPT*/2.

​

• Randomized Rounding: For each bidder i, let S_i be the bundle S with probability x_i,S, and the empty set with probability 1-Σ_Sx_i,S.
• The expected value of v_i(S_i) is Σ_Sx_i,Sv_i(S)
• We use the Chernoff bound to show that such “pre-allocation” is built with high probability.

10

The Algorithm – Step 3

• For each bidder i, partition S_i into a disjoint union S_i = S_i¹∪.. ∪S_i^k such that for each�1≤i<i’≤ n, 1≤t≤t’≤ k, S_i^t∩S_i’^t’=∅.

11

The Algorithm – Step 3

• For each bidder i, partition S_i into a disjoint union S_i = S_i¹∪.. ∪S_i^k such that for each�1≤i<i’≤ n, 1≤t≤t’≤ k, S_i^t∩S_i’^t’=∅.

12

The Algorithm – Step 3

• For each bidder i, partition S_i into a disjoint union S_i = S_i¹∪.. ∪S_i^k such that for each�1≤i<i’≤ n, 1≤t≤t’≤ k, S_i^t∩S_i’^t’=∅.

13

S₁¹ = {A,B,D}

The Algorithm – Step 3

• For each bidder i, partition S_i into a disjoint union S_i = S_i¹∪.. ∪S_i^k such that for each�1≤i<i’≤ n, 1≤t≤t’≤ k, S_i^t∩S_i’^t’=∅.

14

The Algorithm – Step 3

• For each bidder i, partition S_i into a disjoint union S_i = S_i¹∪.. ∪S_i^k such that for each�1≤i<i’≤ n, 1≤t≤t’≤ k, S_i^t∩S_i’^t’=∅.

15

S₂¹ = {C,E}

S₂² = {A,D}

The Algorithm – Step 3

• For each bidder i, partition S_i into a disjoint union S_i = S_i¹∪.. ∪S_i^k such that for each�1≤i<i’≤ n, 1≤t≤t’≤ k, S_i^t∩S_i’^t’=∅.

16

The Algorithm – Step 3

• For each bidder i, partition S_i into a disjoint union S_i = S_i¹∪.. ∪S_i^k such that for each�1≤i<i’≤ n, 1≤t≤t’≤ k, S_i^t∩S_i’^t’=∅.

17

S₃² = {C,E}

S₃³ = {A}

The Algorithm – Step 3

• For each bidder i, partition S_i into a disjoint union S_i = S_i¹∪.. ∪S_i^k such that for each�1≤i<i’≤ n, 1≤t≤t’≤ k, S_i^t∩S_i’^t’=∅.

18

The Algorithm – Step 3

• For each bidder i, partition S_i into a disjoint union S_i = S_i¹∪.. ∪S_i^k such that for each�1≤i<i’≤ n, 1≤t≤t’≤ k, S_i^t∩S_i’^t’=∅.

19

The Algorithm – Step 4

• Find the t maximizes Σ_iv_i(S_i^t)
• Return the allocation (S₁^t,...,S_n^t).

​

• All valuations are CF so:

Σ_tΣ_iv_i(S_i^t) = Σ_iΣ_tv_i(S_i^t) ≥ Σ_iv_i(S_i) ≥ OPT*/2

🡺 For the t that maximizes Σ_iv_i(S_i^t), it holds that: � Σ_iv_i(S_i^t) ≥ OPT*/2k = OPT*/O(log(m)).

​

20

Talk Structure

• Combinatorial Auctions
• Log(m)-approximation for CF auctions
• 🡺An incentive compatible O(m^1/2)-approximation CF auctions
• A lower bound of 2-ε for CF auctions
• 2-approximation for XOS auctions
• A lower bound of e/(e-1)-ε for XOS auctions

21

Incentive Compatibility & VCG Prices

• VCG is the only general technique known for making auctions incentive compatible (if bidders are not single-minded):
• Each bidder i pays: Σ_k≠iv_i(Oⁱ) - Σ_k≠iv_i(O^-i)

Oⁱ is the optimal allocation, O^-i the optimal allocation of the auction without the i’th bidder.

• VCG requires an optimal allocation.
• Finding an optimal allocation requires exponential communication and is computationally intractable.
• Approximations do not suffice (Nisan-Ronen, Lehmann-O’Callaghan-Shoham).

22

VCG on a Subset of the Range

• Our solution: limit the set of possible allocations.
• We will let each bidder to get at most one item, or we’ll allocate all items to a single bidder.
• Optimal solution in the set can be found in polynomial time 🡺 VCG prices can be computed 🡺 incentive compatibility.
• We still need to prove that we achieve an approximation.

23

The Algorithm

• Ask each bidder i for v_i(M), and for v_i(j), for each item j.

(We have used only value queries)

• Construct a bipartite graph and find the maximum weighted matching P.

​

​

​

​

​

​

• can be done in polynomial time (Tarjan).

24

1

2

3

A

B

Items

Bidders

v₁(A)

v₃(B)

The Algorithm (Cont.)

• Let i be the bidder that maximizes v_i(M).
• If v_i(M)>|P|
• Allocate all items to i.
• else
• Allocate according to P.
• Let each bidder pay his VCG price (in respect to the restricted set).

​

25

Proof of the Approximation Ratio

Theorem: If all valuations are CF, the algorithm provides an O(m^1/2)-approximation.

Proof: Let OPT=(T₁,..,T_k,Q₁,...,Q_l), where for each T_i, |T_i|>m^1/2, and for each Q_i, |Q_i|≤m^1/2. |OPT|= Σ_iv_i(T_i) + Σ_iv_i(Q_i)

26

Case 1: Σ_iv_i(T_i) > Σ_iv_i(Q_i)

(“large” bundles contribute most of the social welfare)

🡺 Σ_iv_i(Q_i) > |OPT|/2

At most m^1/2 bidders get at least m^1/2 items in OPT.

🡺 For the bidder i the bidder i that maximizes v_i(M), �v_i(M) > |OPT|/2m^1/2.

Case 2: Σ_iv_i(Q_i) ≥ Σ_iv_i(T_i)

(“small” bundles contribute most of the social welfare)

🡺 Σ_iv_i(Q_i) ≥ |OPT|/2

For each bidder i, there is an item c_i, such that: v_i(c_i) > v_i(Q_i) / m^1/2.

(The CF property ensures that the sum of the values is larger than the value of the whole bundle)

{c_i}_i is an allocation with at most one item to each bidder: �|P| ≥ Σ_ic_i ≥ |OPT|/2m^1/2.

Talk Structure

• Combinatorial Auctions
• Log(m)-approximation for CF auctions
• An incentive compatible O(m^1/2)-approximation CF auctions
• 🡺A lower bound of 2-ε for CF auctions
• 2-approximation for XOS auctions
• A lower bound of e/(e-1)-ε for XOS auctions

27

A Lower Bound of 2-ε

• Nisan & Segal exhibit a set of 0/1 valuations, such that distinguishing between the following cases requires exponential communication:
• There is an allocation in which v_i(S_i)=1, for all i.
• In all allocations, at most one bidder gets a value of 1.

28

A Lower Bound of 2-ε (Cont.)

• Add 1 to all valuations in Nisan-Segal Auction:
• v’_i(S)=v_i(S)+1.
• The valuations are now CF.
• It requires exponential communication to distinguish between the following cases:
• There is an allocation in which v’_i(S_i)=2, for all i.
• In all allocations, at most one bidder gets a value of 2. The rest of the bidders get a value of at most 1.
• 🡺 Any approximation better than 2n/(n+1) requires exponential communication.

29

Talk Structure

• Combinatorial Auctions
• Log(m)-approximation for CF auctions
• An incentive compatible O(m^1/2)-approximation CF auction
• A lower bound of 2-ε for CF auctions
• 🡺2-approximation for XOS auctions
• A lower bound of e/(e-1)-ε for XOS auctions

30

Definition of XOS

• XOS: XOR of ORs of Singletons.
• Singleton valuation (x:p)
• v(S) = p x∈S

0 otherwise

• Example: (A:2 OR B:2) XOR (A:3)
• This is a XOR of additive valuations.

31

XOS Properties

• The strongest bidding language syntactically restricted to represent only complement-free valuations.
• Can describe all submodular valuations (and also some non-submodular valuations)

32

Supporting Prices

• p₁,…,p_m supports the bundle S if:
• v(S) = Σ_j∈Sp_j
• v(T) ≥ Σ_j∈Tp_j for all T ⊆ S
• Claim: a valuation is XOS iff every bundle S has supporting prices.
• Proof:
• 🡺 There is a clause that maximizes the value of a bundle S. The prices in this clause are the supporting prices.
• 🡸 Take the prices of each bundle, and build a clause.

33

The Algorithm

• Input: n bidders, each represented a demand oracle and a supporting price oracle.

​

• Init: p₁=…=p_m=0.
• For each bidder i=1..n
• Let S_i be the demand of the i’th bidder at prices p₁,…,p_m.
• For all i’ < i take away from S_i’ any items from S_i.
• Let q₁,…,q_m be the supporting prices for S_i in v_i.
• For all j ∈ S_i update p_j = q_j.

34

Example

35

Items: {A, B, C, D, E}. 3 bidders.

• Price vector: p₀=(0,0,0,0,0) �v₁: (A:1 OR B:1 OR C:1) XOR (C:2)�Bidder 1 gets his demand: {A,B,C}.
• Price vector: p₁=(1,1,1,0,0) �v₂: (A:1 OR B:1 OR C:9) XOR (D:2 OR E:2)�Bidder 2 gets his demand: {C}
• Price vector: p₂=(1,1,9,0,0) �v₃: (C:10 OR D:1 OR E:2)�Bidder 3 gets his demand: {C,D,E}

Final allocation: {A,B} to bidder 1, {C,D,E} to bidder 3.

Proof

• For proving the approximation ratio, we will need these two simple lemmas:

Lemma: The total social welfare generated by the algorithm is at least Σp_i.

Lemma: The optimal social welfare is at most 2Σp_i.

36

Proof – Lemma 1

Lemma: The total social welfare generated by the algorithm is at least Σp_i.

​

Proof:

• Each bidder i got a bundle T_i at stage i.
• At the end of the algorithm, he holds A_i ⊆ T_i.
• The supporting prices guarantee that: � v_i(A_i) ≥ Σ_j∈Aip_j

​

37

Proof – Lemma 2

Lemma: The optimal social welfare is at most 2Σp_i.

​

Proof:

• Let O₁,...,O_n be the optimal allocation. Let p_i,j be the price of the j’th item at the i’th stage.
• Each bidder i ask for the bundle that maximizes his demand at the i’th stage:

v_i(O_i)-Σ_j∈Oi p_i,j ≤ Σ_j p_i,j – Σ_j p_(i-1),j

• Since the prices are non-decreasing:

v_i (O_i )-Σ_j∈Oi p_n,j ≤ Σ_j p_i,j – Σ_j p_(i-1),j

• Summing up on both sides:

Σ_i v_i(O_i )-Σ_iΣ_j∈Oi p_n,j ≤ Σ_i (S_j p_i,j – Σ_j p_(i-1),j)

Σ_i v_i(O_i )-Σ_j p_n,j ≤ Σ_j p_n,j

Σ_i v_i(O_i ) ≤ 2Σ_j p_n,j

​

38

Talk Structure

• Combinatorial Auctions
• Log(m)-approximation for CF auctions
• An incentive compatible O(m^1/2)-approximation CF auctions
• A lower bound of 2-ε for CF auctions
• 2-approximation for XOS auctions
• 🡺 A lower bound of e/(e-1)-ε for XOS auctions

39

k-Set Cover

• We will show a polynomial time reduction from k-Set-Cover.
• k-Set-Cover definition:
• Input: a set of |M|=m items, t subsets S_i ⊆ M, an integer k.
• Goal: Find k subsets such that the number of item in their union, |∪_1≤i≤kS_i|, is maximized.
• Theorem: approximating k-Set-Cover within a better factor than e/(e-1) is NP-hard (feige).

40

The Reduction

• Every solution to k-Set-Cover implies an allocation with the same value.
• Every allocation implies a solution to k-Set-Cover with at least that value.
• 🡺 Same approximation lower bound.
• A communication lower bound can also be proven by reducing from the communication of this version (Nisan).

41

A

B

C

D

E

F

v₁: (A:1 OR D:1) XOR (A:1 OR D:1) � XOR (D:1 OR E:1 OR F:1)

v_k: (A:1 OR D:1) XOR (A:1 OR D:1) � XOR (D:1 OR E:1 OR F:1)

k-Set-Cover Instance

XOS Auction with k bidders