Contents
1 Introduction 3
1.1 Our Results 4
1.2 Technical Overview 6
1.3 Other Related Works 9
1.4 Roadmap 10
2 Preliminaries 10
3 Max-min allocation 11
3.1 The configuration setting 11
3.2 The rounding algorithm 12
3.3 Analysis of the failure probability 14
3.4 Applications to additive and submodular valuations 16
3.5 Additive lower bounds for subadditive valuations 19
3.6 Subadditive rounding with at most 128 n 2 128n^2 128 n 2
3.7 Sampling and rounding tools 25
3.8 Subadditive rounding with arbitrarily many items 28
4 Weighted Nash social welfare 33
4.1 The configuration setting 33
4.2 The rounding algorithm 34
4.3 Singleton matching 36
4.4 Rounding the tails 38
4.5 Analysis of the rounding algorithm 43
4.6 Computing configurations and applying rounding 48
4.7 The integrality gap for prescribed weights 50
AI Disclosure 52
Acknowledgment 52
References 53
A Computing configuration solution for max-min allocation 59
B Restriction and exact value evaluation via ordinary demand queries 62
C Finite implementation of NSW rounding 62
C.1 Approximate sampling and rational calibration 63
C.2 Stability of the rounding guarantee 64
D Computing a configuration solution for Nash social welfare 66
E Computational conventions 67
E.1 Encoding 67
E.2 Sampling from explicit rational distributions 67
Introduction
We study the problem of allocating a set M M M m m m N N N n n n i ∈ N i \in N i ∈ N v i : 2 M → R ≥ 0 v_i: 2^M \to\mathbb{R}_{\ge0} v i : 2 M → R ≥ 0 1 A = ( A i ) i ∈ N A = (A_i)_{i\in N} A = ( A i ) i ∈ N A i ⊆ M A_i \subseteq M A i ⊆ M M M M
Santa Claus , where we aim to maximize the value received by the worst-off agent min i ∈ N v i ( A i ) \min_{i\in N} v_i(A_i) min i ∈ N v i ( A i )
Weighted Nash social welfare (NSW) , where, given positive weights ( w i ) i ∈ N (w_i)_{i\in N} ( w i ) i ∈ N ∑ i ∈ N w i = 1 \sum_{i\in N} w_i = 1 ∑ i ∈ N w i = 1 NSW w ( A ) : = ∏ i ∈ N v i ( A i ) w i \operatorname{NSW}_w(A) := \prod_{i\in N} v_i(A_i)^{w_i} NSW w ( A ) := ∏ i ∈ N v i ( A i ) w i
With equal weights, this objective reduces to the usual Nash social welfare, the geometric mean of the agents’ values. This unweighted objective has axiomatic foundations in the bargaining work of Nash [55 ] and the social welfare framework of Kaneko and Nakamura [48 ] . Unequal weights allow agents to have different entitlements, for example when they represent groups of different sizes. For any fixed weights, multiplying an agent’s valuation by a positive constant leaves the ranking of allocations unchanged, so the choice of an optimal allocation does not depend on the units used to measure the agents’ values.
We focus on subadditive valuations, which satisfy v i ( S ∪ T ) ≤ v i ( S ) + v i ( T ) v_i(S \cup T) \le v_i(S) + v_i(T) v i ( S ∪ T ) ≤ v i ( S ) + v i ( T ) S , T ⊆ M S,T \subseteq M S , T ⊆ M [3 Section 5] proved that, for every fixed 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 O ( n 1 − ε ) O(n^{1-\varepsilon}) O ( n 1 − ε ) [16 ] . For the special cases of additive and submodular valuations, simpler algorithms are possible, and they may use different oracles; see § 2 .
Max-min allocation. For additive valuations, Bansal and Sviridenko [18 ] showed that the configuration LP has an integrality gap of Ω ( n ) \Omega(\sqrt{n}) Ω ( n ) n n n [2 ] rounded the configuration LP to obtain an O ( n log 3 n ) O(\sqrt{n}\log^3 n) O ( n log 3 n ) [57 ] improved the ratio to O ( n log n ) O(\sqrt{n}\log n) O ( n log n ) [21 ] gave an O ( m ε ) O(m^\varepsilon) O ( m ε ) m O ( 1 / ε ) m^{O(1/\varepsilon)} m O ( 1/ ε ) ε > 0 \varepsilon> 0 ε > 0 m m m [15 ] obtained the corresponding guarantees for submodular valuations with value queries.2 [36 ] obtained an earlier bound for submodular valuations by approximating each valuation by the square root of an additive function. Khot and Ponnuswami [49 ] gave a ( 2 n − 1 ) (2n-1) ( 2 n − 1 ) [3 Theorem 9] obtained an O ( n ) O(n) O ( n ) p p p
On the negative side, Bezáková and Dani [5 ] proved that approximating max-min allocation within any constant factor better than 2 2 2 [26 ] also implies that any such approximation with success probability at least 2 / 3 2/3 2/3 2 Ω ( m ) 2^{\Omega(\sqrt{m})} 2 Ω ( m )
When all agents share the same valuation function, the Santa Claus optimum equals their common maximin share (MMS) [20 ] , the largest value an agent can guarantee by partitioning the items into n n n [64 ] gave a polynomial-time approximation scheme. For identical submodular valuations, Boehmer [17 ] gave a polynomial-time 5 / 2 5/2 5/2 [19 ] gave a polynomial-time 40-approximation using demand queries, which also applies to identical XOS valuations.
Weighted Nash social welfare. With equal weights, constant-factor approximations are known for additive [22 , 13 ] , submodular [53 , 37 , 9 ] , and subadditive valuations [23 ] , the last result uses demand queries. For XOS valuations and equal weights, Kulkarni, Murhekar, Rivkin, and Khuller [47 ] gave an O ( 1 ) O(1) O ( 1 ) [14 ] gave a 5 exp ( 2 D K L ( w ∥ u ) ) 5\exp(2D_{\mathrm{KL}}(w \mathbin{\|} u)) 5 exp ( 2 D KL ( w ∥ u )) u u u N N N n n n [34 ] then gave an ( e 1 / e + ε ) (e^{1/e}+\varepsilon) ( e 1/ e + ε ) [33 ] gave the first polynomial-time constant-factor approximation. Bei, Feng, Hu, Li, and Zhang [9 ] improved the ratio from 233 + ε +\varepsilon + ε + ε +\varepsilon + ε [3 ] gave an O ( n ) O(n) O ( n )
On the hardness side, Lee [51 ] proved that maximizing NSW is APX-hard even for additive valuations and equal weights. Garg, Kulkarni, and Kulkarni [38 Theorem 4.1] proved that approximating NSW within any constant factor better than e / ( e − 1 ) e/(e-1) e / ( e − 1 ) e / ( e − 1 ) e/(e-1) e / ( e − 1 ) [26 ] also applies to NSW, even for two agents with equal weights.
Our Results
All our algorithms are based on Configuration LP techniques. We use the configuration LP for max-min allocation [18 ] and the logarithmic configuration LP used for weighted Nash social welfare with additive [34 ] and submodular [33 ] valuations. Both assign each agent a probability distribution over bundles, called configurations , with total mass at most one on the configurations containing any given item. Table 1 summarizes our results. For max-min allocation, we obtain the following.
Theorem 1.1. There are randomized polynomial-time O ( n ) O(\sqrt{n}) O ( n )
(i) additive valuations,
(ii) submodular valuations using value queries, and
(iii) subadditive valuations using demand queries.
The approximation ratios do not depend on the number m m m [18 ] showed that the configuration LP has an integrality gap of Ω ( n ) \Omega(\sqrt{n}) Ω ( n ) [18 ] , our approximation is optimal up to a constant factor.
For subadditive valuations, Theorem 1.1 improves the previous ratio of 2 n − 1 2n-1 2 n − 1 [49 ] . For additive valuations, our algorithm removes the remaining log n \sqrt{\log n} log n [57 ] . For additive and submodular valuations, the O ( m ε ) O(m^\varepsilon) O ( m ε ) [21 , 15 ] give better guarantees when m m m n n n ε \varepsilon ε m m m n n n m ε m^\varepsilon m ε n \sqrt{n} n ε > 0 \varepsilon> 0 ε > 0
For the weighted Nash social welfare problem, our ratio depends on the entropy H ( w ) = − ∑ i ∈ N w i ln w i H(w)=-\sum_{i\in N}w_i\ln w_i H ( w ) = − ∑ i ∈ N w i ln w i 3
Γ ( w ) : = ∏ i ∈ N ( n w i ) w i / 2 = exp ( ln n − H ( w ) 2 ) . \Gamma(w) := \prod_{i\in N}(nw_i)^{w_i/2}=\exp\left(\frac{\ln n-H(w)}{2}\right). Γ ( w ) := i ∈ N ∏ ( n w i ) w i /2 = exp ( 2 ln n − H ( w ) ) . Theorem 1.2. For subadditive valuations and positive rational weights w w w ∑ i ∈ N w i = 1 \sum_{i\in N}w_i=1 ∑ i ∈ N w i = 1 A A A
E [ NSW w ( A ) ] ≥ OPT N S W O ( Γ ( w ) ) , \mathbb{E}[\operatorname{NSW}_w(A)] \ge\frac{\operatorname{OPT}_{\mathrm{NSW}}}{O(\Gamma(w))}, E [ NSW w ( A )] ≥ O ( Γ ( w )) OPT NSW , where OPT N S W \operatorname{OPT}_{\mathrm{NSW}} OPT NSW
Since 0 ≤ H ( w ) ≤ ln n 0\le H(w)\le\ln n 0 ≤ H ( w ) ≤ ln n 1 ≤ Γ ( w ) ≤ n 1\le\Gamma(w)\le\sqrt{n} 1 ≤ Γ ( w ) ≤ n Γ ( w ) ≤ n max i w i \Gamma(w)\le\sqrt{n\max_i w_i} Γ ( w ) ≤ n max i w i 1 n \frac{1}{n} n 1 Γ ( w ) = 1 \Gamma(w)=1 Γ ( w ) = 1 Theorem 1.2 gives a constant-factor approximation for subadditive valuations with demand queries, as in [23 ] . More generally, the ratio is constant whenever H ( w ) ≥ ln n − O ( 1 ) H(w)\ge\ln n-O(1) H ( w ) ≥ ln n − O ( 1 ) 1 / n 1/n 1/ n Γ ( w ) = exp ( D K L ( w ∥ u ) / 2 ) \Gamma(w)=\exp(D_{\mathrm{KL}}(w\mathbin\Vert u)/2) Γ ( w ) = exp ( D KL ( w ∥ u ) /2 ) 5 exp ( 2 D K L ( w ∥ u ) ) 5\exp(2D_{\mathrm{KL}}(w\mathbin\Vert u)) 5 exp ( 2 D KL ( w ∥ u )) [14 ] obtained for additive valuations.
Our algorithm also compares with the configuration LP, which maximizes the weighted logarithmic value L ( y ) = ∑ i , S w i y i , S ln v i ( S ) L(y)=\sum_{i,S}w_i y_{i,S}\ln v_i(S) L ( y ) = ∑ i , S w i y i , S ln v i ( S ) § 4.6 . The dependence on the weights is necessary for this LP:
Theorem 1.3. Let L L P L_{\mathrm{LP}} L LP w w w e L L P / OPT N S W e^{L_{\mathrm{LP}}}/\operatorname{OPT}_{\mathrm{NSW}} e L LP / OPT NSW Θ ( Γ ( w ) ) \Theta(\Gamma(w)) Θ ( Γ ( w ))
Thus Theorem 1.2 is best possible up to a constant factor among algorithms that compare with the configuration LP, for every weight vector. In particular, the integrality gap can be as large as Ω ( n ) \Omega(\sqrt{n}) Ω ( n ) 1 − 1 / n 1-1/n 1 − 1/ n 1 / ( n ( n − 1 ) ) 1/(n(n-1)) 1/ ( n ( n − 1 )) Γ ( w ) = ( n − 1 ) 1 / 2 − 1 / n ≥ n − 1 / 2 \Gamma(w)=(n-1)^{1/2-1/n}\ge\sqrt{n-1}/2 Γ ( w ) = ( n − 1 ) 1/2 − 1/ n ≥ n − 1 /2 Θ ( n ) \Theta(\sqrt{n}) Θ ( n ) O ( n ) O(\sqrt{n}) O ( n ) 3.45 3.45 3.45 Θ ( n ) \Theta(\sqrt{n}) Θ ( n )
caption: Our results and prior approximation guarantees. The oracle column describes our algorithms.
:::
Both subadditive objectives admit prior O ( n ) O(n) O ( n ) [3 ] . For max-min allocation with additive and submodular valuations, the O ( m ε ) O(m^{\varepsilon}) O ( m ε ) [21 , 15 ] hold in time m O ( 1 / ε ) m^{O(1/\varepsilon)} m O ( 1/ ε ) ε > 0 \varepsilon> 0 ε > 0 [18 ] for max-min allocation, already with additive valuations, and to Theorem 4.11 for weighted Nash social welfare, already with XOS valuations; the upper bounds follow from our algorithms. Since Γ ( w ) ≤ n \Gamma(w) \le\sqrt{n} Γ ( w ) ≤ n Θ ( n ) \Theta(\sqrt{n}) Θ ( n ) [34 , 33 , 9 ] .
Technical Overview
Our basic rounding procedures first assign individual items to agents through a random matching and then allocate bundles that exclude the matched items. Both steps are guided by a configuration-LP solution, where y i , S y_{i,S} y i , S S S S i i i [2 ] and Saha and Srinivasan [57 ] in separating configurations that can satisfy an agent with one large item from those that require a bundle of small items. For weighted Nash social welfare, we follow Feng, Hu, Li, and Zhang [33 ] in selecting a most valuable singleton from each configuration as its head and treating the remaining items as its tail (see (23) ). The matching assigns the designated singletons with their LP marginals (§ 3.2 and § 4.3 ).
Allocating bundles requires resolving overlaps between configurations while preserving their value. For subadditive valuations, we use a conditional form of Feige’s guiding-tree rounding [28 ] (Lemma 3.10). After scaling the configuration masses by a constant factor and adding empty configurations, each run selects a configuration for every agent and produces disjoint subbundles. Conditional on any selected configuration, an agent receives a constant fraction of its value with constant probability. Following Feige and Huang [32 ] , we combine independent runs by assigning random colors to items and retaining each item only in the run corresponding to its color. This gives agents repeated opportunities to obtain valuable bundles while preserving feasibility. The color probabilities reflect the objective: the subadditive max-min algorithm uses uniform probabilities to reach a common value threshold (Lemma 3.11), whereas the NSW algorithm uses geometrically decreasing probabilities to control expected logarithmic welfare (Lemma 4.4 ).
The analysis exploits the capacity constraint linking singleton assignments to the remaining configurations. Let b j b_j b j j j j f j = 1 − b j f_j = 1-b_j f j = 1 − b j j j j f j f_j f j (5) and (25) , respectively). Thus, an item that is likely to be matched can occur in only a small amount of residual configuration mass. Charging b j / f j b_j/f_j b j / f j b j b_j b j ∑ j b j ≤ n \sum_j b_j \le n ∑ j b j ≤ n (14) for max-min and (44) for NSW); positive-mass occurrences necessarily have f j > 0 f_j > 0 f j > 0 Lemma 4.6 ). For max-min allocation, it controls the sum of conditional failure probabilities weighted by the LP masses (see (7) ). We first develop the rounding lemma that makes this latter guarantee precise.
Max-min allocation: the rounding lemma. Suppose every configuration S S S i i i a i , S : 2 S → R ≥ 0 a^{i,S}:2^S \to\mathbb{R}_{\ge0} a i , S : 2 S → R ≥ 0 v i v_i v i a i , S a^{i,S} a i , S τ \tau τ a i , S a^{i,S} a i , S τ \tau τ τ \tau τ 3 / 4 3/4 3/4
∑ i ∈ N ∑ S small y i , S min { 1 , ( 32 τ μ i , S ) 3 } ≤ 1 4 , where μ i , S = ∑ j ∈ S a j i , S f j . \sum_{i \in N}\sum_{S\text{ small}} y_{i,S}\min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}\le\frac{1}{4}, \qquad\text{where }\mu_{i,S}=\sum_{j\in S}a_j^{i,S}f_j. i ∈ N ∑ S small ∑ y i , S min { 1 , ( μ i , S 32 τ ) 3 } ≤ 4 1 , where μ i , S = j ∈ S ∑ a j i , S f j . The baseline μ i , S \mu_{i,S} μ i , S a i , S a^{i,S} a i , S S S S [39 ] ) and its same-side negative correlation ([57 ] ) to couple the assignment of large items with configuration selection. After the matching, the agents that select other configurations share the surviving items equally, and Shmoys–Tardos rounding ([60 ] ) makes the allocation integral. Saha and Srinivasan [57 Section 4.1] also use a large-item matching followed by an additive rounding step, but discard items with low survival probability or high realized congestion and scale the remaining fractional allocation by a common factor. Writing the large-item threshold as T / λ T/\lambda T / λ η \eta η η = O ( λ / n ) \eta=O(\lambda/n) η = O ( λ / n ) η λ = Ω ( log n ) \eta\lambda=\Omega(\log n) η λ = Ω ( log n ) λ = Θ ( n log n ) \lambda=\Theta(\sqrt{n\log n}) λ = Θ ( n log n ) Θ ( T / n log n ) \Theta(T/\sqrt{n\log n}) Θ ( T / n log n ) S S S min { 1 , ( 32 τ / μ i , S ) 3 } \min\{1,(32\tau/\mu_{i,S})^3\} min { 1 , ( 32 τ / μ i , S ) 3 } (10) ). The key analytical difference is that we bound the total failure probability after weighting these conditional bounds by the LP marginals. Thus, configurations with small surviving baseline may have large conditional failure probabilities, provided that their total LP mass is small. For submodular valuations, the marginal-value construction of Dobzinski, Nisan, and Schapira [24 ] gives an additive lower bound that is tight on each configuration (§ 3.4 ). For supporting clauses scaled to total T T T μ i , S ≥ T / ( 1 + P ( S ) / ( 128 n ) ) \mu_{i,S}\ge T/(1+P(S)/(128\sqrt{n})) μ i , S ≥ T / ( 1 + P ( S ) / ( 128 n )) P ( S ) = ∑ j ∈ S b j / f j P(S)=\sum_{j\in S}b_j/f_j P ( S ) = ∑ j ∈ S b j / f j § 3.4 ). Using the penalty budget above, the threshold τ = T / ( 128 n ) \tau=T/(128\sqrt{n}) τ = T / ( 128 n ) T / n T/\sqrt{n} T / n log n \sqrt{\log n} log n [57 ] . This gives the ratio O ( n ) O(\sqrt{n}) O ( n ) Theorem 3.5 ).
Max-min allocation: extending to subadditive valuations. We extend the preceding approach using the same rounding lemma; the new task is to construct additive lower bounds whose baselines satisfy its budget condition. A subadditive valuation need not have additive lower bound that is tight on a given configuration. Dobzinski [25 ] obtained additive lower bounds for subadditive valuations from demand queries, losing a logarithmic factor. We compute such a bound on each configuration using the geometric price grid of Balcan, Blum, and Mansour [4 ] (Lemma 3.6). Applying the preceding argument to these lower bounds gives only an O ( n log m ) O(\sqrt{n}\log m) O ( n log m ) j j j 1 / f j 1/f_j 1/ f j Lemma 3.7 ). The resulting baseline satisfies (15) , which has a logarithmic term and a square-root term. Either the logarithmic term gives a sufficiently large baseline, or the square-root term forces a large penalty; the cubic failure bound and penalty budget handle these two cases. These bounds verify the budget condition of Lemma 3.1 and give an O ( n ) O(\sqrt{n}) O ( n ) m ≤ 128 n 2 m \le128n^2 m ≤ 128 n 2
For larger m m m 128 n 2 128n^2 128 n 2 128 n 128n 128 n § 3.8 ). Agents whose backup item is valuable take it, and every other agent values each item outside the core at most O ( T / n ) O(T/\sqrt{n}) O ( T / n ) Theorem 3.12 ).
Weighted Nash social welfare. We round a solution of the configuration LP, which maximizes L ( y ) = ∑ i , S w i y i , S ln v i ( S ) L(y)=\sum_{i,S} w_i y_{i,S}\ln v_i(S) L ( y ) = ∑ i , S w i y i , S ln v i ( S ) Lemma 4.9 ). We match every agent to a head, then we realize the LP head marginals as a limit of Gibbs matching distributions, using the maximum-entropy formulation [61 ] , and prove the reference-set coupling in Lemma 4.2 . Independently, we allocate the tails using the repeated rounding described above, with geometrically decreasing color probabilities. We then remove the matched heads from the tail bundles. Let B B B D i , S = v i ( head of S ) + v i ( T i , S ∖ B ) D_{i,S}=v_i(\text{head of }S)+v_i(T_{i,S}\setminus B) D i , S = v i ( head of S ) + v i ( T i , S ∖ B ) S S S B B B ∑ i , S y i , S E [ ( v i ( S ) / D i , S ) 2 ] ≤ 196 n \sum_{i,S}y_{i,S}\mathbb{E}\left[(v_i(S)/D_{i,S})^2\right]\le196n ∑ i , S y i , S E [ ( v i ( S ) / D i , S ) 2 ] ≤ 196 n Lemma 4.6 ), by the capacity budget above. Second, the actual allocation achieves E [ ln NSW w ( A ) ] ≥ ∑ i , S w i y i , S E [ ln D i , S ] − O ( 1 ) \mathbb{E}[\ln\operatorname{NSW}_w(A)]\ge\sum_{i,S}w_i y_{i,S}\mathbb{E}[\ln D_{i,S}]-O(1) E [ ln NSW w ( A )] ≥ ∑ i , S w i y i , S E [ ln D i , S ] − O ( 1 ) Lemma 4.7 ). The weight-dependent loss arises when we combine the two estimates. We sample ( i , S ) (i,S) ( i , S ) w i y i , S w_i y_{i,S} w i y i , S (47) ):
L ( y ) − ∑ i , S w i y i , S E [ ln D i , S ] = 1 2 ( E [ ln v i ( S ) 2 w i D i , S 2 ] − H ( w ) ) ≤ 1 2 ( ln ( 196 n ) − H ( w ) ) = ln Γ ( w ) + O ( 1 ) . L(y)-\sum_{i,S}w_i y_{i,S}\mathbb{E}[\ln D_{i,S}]=\frac{1}{2}\left(\mathbb{E}\left[\ln\frac{v_i(S)^2}{w_iD_{i,S}^2}\right]-H(w)\right)\le\frac{1}{2}\left(\ln(196n)-H(w)\right)=\ln\Gamma(w)+O(1). L ( y ) − i , S ∑ w i y i , S E [ ln D i , S ] = 2 1 ( E [ ln w i D i , S 2 v i ( S ) 2 ] − H ( w ) ) ≤ 2 1 ( ln ( 196 n ) − H ( w ) ) = ln Γ ( w ) + O ( 1 ) . The factor 1 / w i 1/w_i 1/ w i w i w_i w i 196 n 196n 196 n
The integrality gap. Our lower bound in Theorem 4.11 adapts the group of unit-demand agents in the submodular gap construction of Bei, Feng, Hu, Li, and Zhang [9 ] , described in their full version [8 ] , Section 6, fig:4 . We give the competing agent an XOS valuation and choose the group sizes as a function of the prescribed weights. A special agent has ℓ \ell ℓ ℓ \ell ℓ ℓ \ell ℓ ℓ − 1 \ell-1 ℓ − 1 1 / ℓ 1/\ell 1/ ℓ ℓ ≈ n w i \ell\approx\sqrt{nw_i} ℓ ≈ n w i i i i Γ ( w ) / 8 \Gamma(w)/\sqrt{8} Γ ( w ) / 8 1 − 1 / n 1-1/n 1 − 1/ n ℓ ≈ n / 2 \ell\approx\sqrt{n/2} ℓ ≈ n /2 Ω ( n ) \Omega(\sqrt{n}) Ω ( n )
Other Related Works
Restricted max-min allocation. In the restricted assignment case with additive valuations, every item j j j p j p_j p j p j p_j p j [18 ] gave an O ( log log n / log log log n ) O(\log\log n/\log\log\log n) O ( log log n / log log log n ) [27 ] proved a constant integrality gap for the configuration LP. Haeupler, Saha, and Srinivasan [42 ] made the local lemma argument constructive to obtain a randomized constant-factor approximation. Annamalai, Kalaitzis, and Svensson [1 ] later gave a combinatorial constant-factor approximation. Bamas, Garg, and Rohwedder [11 ] extended this setting to a common monotone submodular valuation v v v Γ i ⊆ M \Gamma_i \subseteq M Γ i ⊆ M v i ( S ) = v ( S ∩ Γ i ) v_i(S)=v(S\cap\Gamma_i) v i ( S ) = v ( S ∩ Γ i ) O ( log log m ) O(\log\log m) O ( log log m ) [10 Appendix B.1] .
Utilitarian welfare. The utilitarian objective maximizes the total value ∑ i ∈ N v i ( A i ) \sum_{i\in N}v_i(A_i) ∑ i ∈ N v i ( A i ) [28 ] rounded the configuration LP to obtain a randomized 2-approximation. Our algorithms adapt his guiding-tree rounding procedure. Feige also showed that the integrality gap can approach 2 and that it is NP-hard to approximate the problem within any constant factor better than 2, even when all agents have the same valuation. Feige and Vondrák [35 ] showed that for every fixed 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 ( 2 − ε ) (2-\varepsilon) ( 2 − ε ) O ε ( 1 ) O_\varepsilon(1) O ε ( 1 ) [26 ] showed that even for two agents, any fixed improvement over the factor of 2 requires 2 Ω ( m ) 2^{\Omega(\sqrt{m})} 2 Ω ( m ) [56 ] gave an O ( m / log m ) O(\sqrt{m}/\log m) O ( m / log m ) [24 ] .
Maximin shares. For agents with different valuations, an α \alpha α α \alpha α [50 ] showed that exact MMS allocations need not exist, but 2 / 3 2/3 2/3 [41 ] gave a strongly polynomial-time algorithm for 3 / 4 3/4 3/4 [43 ] obtained ( 7 / 9 − ε ) (7/9-\varepsilon) ( 7/9 − ε ) ε > 0 \varepsilon>0 ε > 0 n n n m m m 1 / ε 1/\varepsilon 1/ ε [7 ] gave a polynomial-time algorithm for 10 / 27 10/27 10/27 [30 ] proved the existence of 4 / 17 4/17 4/17 [31 ] proves the existence of α \alpha α α > 11 / 40 \alpha>11/40 α > 11/40 n n n
For subadditive valuations, Seddighin and Seddighin [58 ] proved the existence of Ω ( 1 / ( log n log log n ) ) \Omega(1/(\log n\log\log n)) Ω ( 1/ ( log n log log n )) [32 ] improved this guarantee to 1 / ( 14 log 2 n ) 1/(14\log_2 n) 1/ ( 14 log 2 n ) § 3.7 . Seddighin and Seddighin [59 ] subsequently obtained an Ω ( 1 / ( log log n ) 2 ) \Omega(1/(\log\log n)^2) Ω ( 1/ ( log log n ) 2 ) [29 ] improved to Ω ( 1 / log log n ) \Omega(1/\log\log n) Ω ( 1/ log log n )
Roadmap
§ 2 defines the model, the oracles, and the configuration LPs for both problems. § 3 presents our max-min algorithms: the rounding lemma and its proof (§ 3.1 to § 3.3 ), the algorithms for valuations with supporting clauses (§ 3.4 ), and the algorithm for subadditive valuations (§ 3.6 to § 3.8 ). § 4 presents our algorithm for weighted Nash social welfare and the integrality gap of its configuration LP. The appendix contains the computation of the configuration solutions and the finite implementation of the Nash social welfare rounding.
Preliminaries
We are given a set N N N n n n M M M m m m i i i v i : 2 M → R ≥ 0 v_i:2^M \to\mathbb{R}_{\ge0} v i : 2 M → R ≥ 0 v i ( ∅ ) = 0 v_i(\emptyset)=0 v i ( ∅ ) = 0 v i ( S ) ≤ v i ( S ′ ) v_i(S) \le v_i(S') v i ( S ) ≤ v i ( S ′ ) S ⊆ S ′ S \subseteq S' S ⊆ S ′ ( A i ) i ∈ N (A_i)_{i\in N} ( A i ) i ∈ N A i ⊆ M A_i \subseteq M A i ⊆ M M M M
The goal of max-min allocation is to maximize min i ∈ N v i ( A i ) \min_{i\in N} v_i(A_i) min i ∈ N v i ( A i ) O P T M M \mathrm{OPT}_{\mathrm{MM}} OPT MM
In the weighted Nash social welfare problem, each agent i ∈ N i \in N i ∈ N w i w_i w i ∑ i ∈ N w i = 1 \sum_{i\in N} w_i = 1 ∑ i ∈ N w i = 1 A = ( A i ) i ∈ N A=(A_i)_{i\in N} A = ( A i ) i ∈ N
N S W w ( A ) = ∏ i ∈ N v i ( A i ) w i . (1) \mathrm{NSW}_w(A)=\prod_{i\in N}v_i(A_i)^{w_i}. \tag*{(1)} NSW w ( A ) = i ∈ N ∏ v i ( A i ) w i . (1) The goal is to maximize this objective, and we denote its optimal value by O P T N S W \mathrm{OPT}_{\mathrm{NSW}} OPT NSW w i = 1 / n w_i=1/n w i = 1/ n
Valuations and oracles. A valuation v v v additive if v ( S ) = ∑ j ∈ S v ( { j } ) v(S)=\sum_{j\in S}v(\{j\}) v ( S ) = ∑ j ∈ S v ({ j }) S ⊆ M S \subseteq M S ⊆ M submodular if v ( S ∪ { j } ) − v ( S ) ≥ v ( S ′ ∪ { j } ) − v ( S ′ ) v(S\cup\{j\})-v(S) \ge v(S'\cup\{j\})-v(S') v ( S ∪ { j }) − v ( S ) ≥ v ( S ′ ∪ { j }) − v ( S ′ ) S ⊆ S ′ S \subseteq S' S ⊆ S ′ j ∉ S ′ j \notin S' j ∈ / S ′ clauses . It is subadditive if v ( S ∪ S ′ ) ≤ v ( S ) + v ( S ′ ) v(S\cup S') \le v(S)+v(S') v ( S ∪ S ′ ) ≤ v ( S ) + v ( S ′ ) S , S ′ ⊆ M S,S' \subseteq M S , S ′ ⊆ M [52 ] .
A value query for a set S S S v i ( S ) v_i(S) v i ( S ) p ∈ R ≥ 0 M p \in\mathbb{R}_{\ge0}^M p ∈ R ≥ 0 M demand query returns a set D D D v i ( D ) − ∑ j ∈ D p j v_i(D)-\sum_{j\in D}p_j v i ( D ) − ∑ j ∈ D p j restricted demand query also specifies a set S S S S S S
For running-time bounds, we assume that valuation values are rational with a known polynomial bound on their encoding length, and that oracle-returned additive coefficients have polynomial encoding length. Blumrosen and Nisan [16 ] showed how to simulate value queries by demand queries, Appendix § 9 gives the implementation of value and restricted demand queries under this convention.
Configuration LPs. A configuration for agent i i i S ⊆ M S \subseteq M S ⊆ M C i ⊆ 2 M \mathcal{C}_i \subseteq2^M C i ⊆ 2 M feasible configuration solution assigns nonnegative masses y i , S y_{i,S} y i , S
∑ S ∈ C i y i , S = 1 ∀ i ∈ N , (2) \sum_{S\in\mathcal{C}_i} y_{i,S}=1 \qquad\forall i\in N, \tag*{(2)} S ∈ C i ∑ y i , S = 1 ∀ i ∈ N , (2) ∑ i ∈ N ∑ S ∈ C i : j ∈ S y i , S ≤ 1 ∀ j ∈ M . (3) \sum_{i\in N}\sum_{S\in\mathcal{C}_i:j\in S} y_{i,S}\le1 \qquad\forall j\in M. \tag*{(3)} i ∈ N ∑ S ∈ C i : j ∈ S ∑ y i , S ≤ 1 ∀ j ∈ M . (3) Thus, each agent’s masses form a probability distribution over configurations, and the total mass on each item is at most one. A solution is explicit if its positive masses are rational and are given together with their configurations as a list of triples ( i , S , y i , S ) (i,S,y_{i,S}) ( i , S , y i , S )
For max-min allocation, we use the target-based configuration LP of Bansal and Sviridenko [18 ] , replacing the additive value of a configuration by v i ( S ) v_i(S) v i ( S ) t ≥ 0 t \ge0 t ≥ 0 C i ( t ) = { S ⊆ M : v i ( S ) ≥ t } C_i(t)=\{S\subseteq M:v_i(S)\ge t\} C i ( t ) = { S ⊆ M : v i ( S ) ≥ t } C i = C i ( t ) C_i=C_i(t) C i = C i ( t ) configuration solution with objective value t t t T L P T_{\mathrm{LP}} T LP
For Nash social welfare, Feng and Li [34 ] introduced the logarithmic configuration LP for additive valuations, and Feng, Hu, Li, and Zhang [33 ] used it for submodular valuations. For O P T N S W > 0 \mathrm{OPT}_{\mathrm{NSW}}>0 OPT NSW > 0 C i = { S ⊆ M : v i ( S ) > 0 } C_i=\{S\subseteq M:v_i(S)>0\} C i = { S ⊆ M : v i ( S ) > 0 } (2) and (3) , the LP maximizes
L ( y ) : = ∑ i , S w i y i , S ln v i ( S ) . (4) L(y):=\sum_{i,S}w_i y_{i,S}\ln v_i(S). \tag*{(4)} L ( y ) := i , S ∑ w i y i , S ln v i ( S ) . (4) Here the sum ranges over i ∈ N i\in N i ∈ N S ∈ C i S\in C_i S ∈ C i L ( y ) L(y) L ( y ) L L P L_{\mathrm{LP}} L LP [9 ] , gives the same optimum: any slack can be filled by adding the item to suitable configurations, splitting their masses if necessary, without changing other item marginals or decreasing the objective.
Max-min allocation
In this section, we present O ( n ) O(\sqrt{n}) O ( n )
The configuration setting
Asadpour and Saberi [2 ] and Saha and Srinivasan [57 ] separate large singleton configurations from bundles of small items in the additive case. We use this separation with additive coefficients that may depend on the configuration. Let N N N n ≥ 1 n\ge1 n ≥ 1 M M M m m m ( C i , y i , S ) i ∈ N (C_i,y_{i,S})_{i\in N} ( C i , y i , S ) i ∈ N § 2 , with zero-mass configurations omitted.
Moreover, for every agent i i i S ∈ C i S\in C_i S ∈ C i a j i , S ≥ 0 a_j^{i,S}\ge0 a j i , S ≥ 0 j ∈ S j\in S j ∈ S
a i , S ( Q ) : = ∑ j ∈ Q a j i , S ∀ Q ⊆ S . a^{i,S}(Q):=\sum_{j\in Q}a_j^{i,S}\qquad\forall Q\subseteq S. a i , S ( Q ) := j ∈ Q ∑ a j i , S ∀ Q ⊆ S . It is possible that a j i , S ≠ a j i , S ′ a_j^{i,S}\ne a_j^{i,S'} a j i , S = a j i , S ′ S , S ′ ∈ C i S,S'\in C_i S , S ′ ∈ C i j j j
Let τ > 0 \tau>0 τ > 0 i i i C i = L i ∪ ˙ S i C_i=\mathcal{L}_i\mathbin{\dot\cup}\mathcal{S}_i C i = L i ∪ ˙ S i
every S ∈ L i S\in\mathcal{L}_i S ∈ L i a i , S ( S ) ≥ τ a^{i,S}(S)\ge\tau a i , S ( S ) ≥ τ
every S ∈ S i S\in\mathcal{S}_i S ∈ S i a j i , S < τ a_j^{i,S}<\tau a j i , S < τ
We say configurations in L i \mathcal{L}_i L i S i \mathcal{S}_i S i j ∈ M j \in M j ∈ M
b j = ∑ i ∈ N : { j } ∈ L i y i , { j } , f j = 1 − b j ≥ ∑ i ∈ N , S ∈ S i : j ∈ S y i , S . (5) b_j=\sum_{i\in N:\{j\}\in\mathcal{L}_i}y_{i,\{j\}},\qquad f_j=1-b_j\geq\sum_{i\in N,S\in\mathcal{S}_i:j\in S}y_{i,S}. \tag*{(5)} b j = i ∈ N : { j } ∈ L i ∑ y i , { j } , f j = 1 − b j ≥ i ∈ N , S ∈ S i : j ∈ S ∑ y i , S . (5) The inequality follows from the capacity constraint (3) . For a small configuration S ∈ S i S\in\mathcal{S}_i S ∈ S i baseline value
μ i , S : = ∑ j ∈ S a j i , S f j . (6) \mu_{i,S}:=\sum_{j\in S}a_j^{i,S}f_j. \tag*{(6)} μ i , S := j ∈ S ∑ a j i , S f j . (6) Lemma 3.1. In the setting above, suppose that
∑ i ∈ N ∑ S ∈ S i y i , S min { 1 , ( 32 τ μ i , S ) 3 } ≤ 1 4 . (7) \sum_{i\in N}\sum_{S\in\mathcal{S}_i}y_{i,S}\min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}\leq\frac{1}{4}. \tag*{(7)} i ∈ N ∑ S ∈ S i ∑ y i , S min { 1 , ( μ i , S 32 τ ) 3 } ≤ 4 1 . (7) Here and below, we interpret min { 1 , ( 32 τ / μ i , S ) 3 } \min\{1,(32\tau/\mu_{i,S})^3\} min { 1 , ( 32 τ / μ i , S ) 3 } μ i , S = 0 \mu_{i,S}=0 μ i , S = 0 S i ∈ C i S_i\in\mathcal{C}_i S i ∈ C i i ∈ N i\in N i ∈ N A i ⊆ S i A_i\subseteq S_i A i ⊆ S i 3 / 4 3/4 3/4
a i , S i ( A i ) ≥ τ ∀ i ∈ N . a^{i,S_i}(A_i)\geq\tau\qquad\forall i\in N. a i , S i ( A i ) ≥ τ ∀ i ∈ N . Moreover, for every i ∈ N i\in N i ∈ N S ∈ C i S\in\mathcal{C}_i S ∈ C i Pr [ S i = S ] = y i , S \Pr[S_i=S]=y_{i,S} Pr [ S i = S ] = y i , S
The rounding algorithm
In this subsection, we describe the algorithm for Lemma 3.1 and establish the properties needed for its analysis.
Singleton matching and configuration selection. We construct a bipartite graph with the agents in N N N j ∈ M j\in M j ∈ M b j > 0 b_j>0 b j > 0 u i , S u_{i,S} u i , S i ∈ N i\in N i ∈ N S ∈ S i S\in\mathcal{S}_i S ∈ S i { j } ∈ L i \{j\}\in\mathcal{L}_i { j } ∈ L i ( i , j ) (i,j) ( i , j ) y i , { j } y_{i,\{j\}} y i , { j } u i , S u_{i,S} u i , S ( i , u i , S ) (i,u_{i,S}) ( i , u i , S ) y i , S y_{i,S} y i , S (2) and (3) , every left vertex has fractional degree 1, and every right vertex has fractional degree at most 1.
We apply the bipartite dependent rounding of Gandhi, Khuller, Parthasarathy, and Srinivasan [39 ] . Its degree-preservation and edge-marginal properties give a matching that covers every agent and includes each edge with probability equal to its initial mass. The private vertices place configuration choices and reserved items on the same side of the graph, so the negative correlation of matched vertices proved by Saha and Srinivasan [57 ] applies to both.
Lemma 3.2. For every right vertex v v v χ v ∈ { 0 , 1 } \chi_v\in\{0,1\} χ v ∈ { 0 , 1 } v v v d v d_v d v Pr [ χ v = 1 ] = d v \Pr[\chi_v=1]=d_v Pr [ χ v = 1 ] = d v v v v Q Q Q u ∉ Q u\notin Q u ∈ / Q d u > 0 d_u>0 d u > 0
E [ ∏ v ∈ Q χ v ] ≤ ∏ v ∈ Q d v , E [ ∏ v ∈ Q χ v ∣ χ u = 1 ] ≤ ∏ v ∈ Q d v . (8) \mathbb{E}\left[\prod_{v\in Q}\chi_v\right]\leq\prod_{v\in Q}d_v,\qquad
\mathbb{E}\left[\left.\prod_{v\in Q}\chi_v\right|\chi_u=1\right]\leq\prod_{v\in Q}d_v. \tag*{(8)} E v ∈ Q ∏ χ v ≤ v ∈ Q ∏ d v , E v ∈ Q ∏ χ v χ u = 1 ≤ v ∈ Q ∏ d v . (8) Proof. Summing the marginals of the mutually exclusive edges incident to v v v Pr [ χ v = 1 ] = d v \Pr[\chi_v = 1] = d_v Pr [ χ v = 1 ] = d v [57 Theorem 4.4] applied to the right vertices in Q Q Q
For the second inequality, we have Pr [ χ u = 1 ] = d u \Pr[\chi_u = 1] = d_u Pr [ χ u = 1 ] = d u Q ∪ { u } Q \cup\{u\} Q ∪ { u }
E [ ∏ v ∈ Q χ v ∣ χ u = 1 ] = E [ ∏ v ∈ Q ∪ { u } χ v ] d u ≤ ∏ v ∈ Q d v . \mathbb{E}\left[\left.\prod_{v\in Q}\chi_v\right|\chi_u=1\right] = \frac{\mathbb{E}\left[\prod_{v\in Q\cup\{u\}}\chi_v\right]}{d_u} \leq\prod_{v\in Q}d_v. E v ∈ Q ∏ χ v χ u = 1 = d u E [ ∏ v ∈ Q ∪ { u } χ v ] ≤ v ∈ Q ∏ d v . □ \square □
An agent i i i j j j S i : = { j } S_i := \{j\} S i := { j } A i : = { j } A_i := \{j\} A i := { j } a j i , { j } ≥ τ a_j^{i,\{j\}} \geq\tau a j i , { j } ≥ τ i i i i i i j j j i i i u i , S u_{i,S} u i , S S i : = S S_i := S S i := S Pr [ S i = S ] = y i , S \Pr[S_i = S] = y_{i,S} Pr [ S i = S ] = y i , S i ∈ N i \in N i ∈ N S ∈ C i S \in C_i S ∈ C i
Fractional assignment of remaining items. Let F j ∈ { 0 , 1 } F_j \in\{0,1\} F j ∈ { 0 , 1 } j j j E [ F j ] = 1 − b j = f j \mathbb{E}[F_j] = 1-b_j = f_j E [ F j ] = 1 − b j = f j C j C_j C j i i i j ∈ S i j \in S_i j ∈ S i j j j F j = 1 F_j = 1 F j = 1 C j > 0 C_j > 0 C j > 0 1 / C j 1/C_j 1/ C j j j j j j j i i i
X i : = ∑ j ∈ S i a j i , S i F j C j . X_i := \sum_{j\in S_i} a_j^{i,S_i}\frac{F_j}{C_j}. X i := j ∈ S i ∑ a j i , S i C j F j . Integral assignment via Shmoys–Tardos rounding. Bezáková and Dani [5 ] bounded the additive loss per agent in max-min allocation by the value of one item. We use the slot construction of Shmoys and Tardos [60 ] on the support of the fractional assignment. For each unhappy agent i i i a j i , S i a_j^{i,S_i} a j i , S i A i ⊆ S i A_i \subseteq S_i A i ⊆ S i j j j F j = 1 F_j = 1 F j = 1 τ \tau τ
a i , S i ( A i ) ≥ X i − τ for every unhappy agent i . (9) a^{i,S_i}(A_i) \geq X_i - \tau\qquad\text{for every unhappy agent } i. \tag*{(9)} a i , S i ( A i ) ≥ X i − τ for every unhappy agent i . (9) This completes the description of the rounding algorithm.
In the applications below, configurations may be replaced by subsets before rounding, and equal resulting sets are merged by adding their masses. After rounding, the proportional rule recovers an original configuration for each agent, choosing among those mapped to its selected set with probability proportional to their masses; this preserves the original marginals and does not change the allocation.
Analysis of the failure probability
In this subsection, we analyze the failure probability of the algorithm. Fix an agent i ∈ N i \in N i ∈ N S ∈ S i S \in\mathcal{S}_i S ∈ S i Pr S [ ⋅ ] \Pr_S[\cdot] Pr S [ ⋅ ] E S [ ⋅ ] \mathbb{E}_S[\cdot] E S [ ⋅ ] S i = S S_i = S S i = S a j = a j i , S a_j = a_j^{i,S} a j = a j i , S a ( Q ) = a i , S ( Q ) a(Q) = a^{i,S}(Q) a ( Q ) = a i , S ( Q ) μ = μ i , S \mu= \mu_{i,S} μ = μ i , S X = X i X = X_i X = X i
Z = ∑ j ∈ S a j F j , Z = \sum_{j \in S} a_j F_j, Z = j ∈ S ∑ a j F j , since E [ F j ] = f j \mathbb{E}[F_j] = f_j E [ F j ] = f j Z Z Z E [ Z ] = ∑ j ∈ S a j f j = μ \mathbb{E}[Z] = \sum_{j \in S} a_j f_j = \mu E [ Z ] = ∑ j ∈ S a j f j = μ
Lemma 3.3. For every agent i ∈ N i \in N i ∈ N S ∈ S i S \in\mathcal{S}_i S ∈ S i
Pr S [ a i , S ( A i ) < τ ] ≤ Pr S [ X i < 2 τ ] ≤ min { 1 , ( 32 τ μ i , S ) 3 } . (10) \Pr_S[a^{i,S}(A_i) < \tau] \le\Pr_S[X_i < 2\tau] \le\min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}. \tag*{(10)} S Pr [ a i , S ( A i ) < τ ] ≤ S Pr [ X i < 2 τ ] ≤ min { 1 , ( μ i , S 32 τ ) 3 } . (10) Proof. The first inequality follows from (9) . The second inequality is trivial when 0 ≤ μ ≤ 32 τ 0 \le\mu\le32\tau 0 ≤ μ ≤ 32 τ μ > 32 τ \mu> 32\tau μ > 32 τ Pr S [ X < 2 τ ] \Pr_S[X < 2\tau] Pr S [ X < 2 τ ] Z Z Z
We first show that Z Z Z μ / 2 \mu/2 μ /2 Pr S \Pr_S Pr S S i = S S_i = S S i = S χ u i , S = 1 \chi_{u_i,S} = 1 χ u i , S = 1 u i , S u_{i,S} u i , S y i , S > 0 y_{i,S} > 0 y i , S > 0 j j j b j > 0 b_j > 0 b j > 0 1 − F j = χ j 1 - F_j = \chi_j 1 − F j = χ j b j b_j b j b j = 0 b_j = 0 b j = 0 1 − F j = 0 1 - F_j = 0 1 − F j = 0
E S [ ∏ j ∈ J ( 1 − F j ) ] ≤ ∏ j ∈ J b j for every J ⊆ S . \mathbb{E}_S\left[\prod_{j \in J}(1-F_j)\right] \le\prod_{j \in J} b_j \qquad\text{for every } J \subseteq S. E S j ∈ J ∏ ( 1 − F j ) ≤ j ∈ J ∏ b j for every J ⊆ S . Since F j ∈ { 0 , 1 } F_j \in\{0,1\} F j ∈ { 0 , 1 } 2 − a j F j / τ = 2 − a j / τ + ( 1 − 2 − a j / τ ) ( 1 − F j ) 2^{-a_jF_j/\tau} = 2^{-a_j/\tau} + (1-2^{-a_j/\tau})(1-F_j) 2 − a j F j / τ = 2 − a j / τ + ( 1 − 2 − a j / τ ) ( 1 − F j )
E S [ 2 − Z / τ ] = E S [ ∏ j ∈ S ( 2 − a j / τ + ( 1 − 2 − a j / τ ) ( 1 − F j ) ) ] ≤ ∏ j ∈ S ( 2 − a j / τ + b j ( 1 − 2 − a j / τ ) ) = ∏ j ∈ S ( 1 − f j ( 1 − 2 − a j / τ ) ) ≤ exp ( − ∑ j ∈ S f j ( 1 − 2 − a j / τ ) ) ≤ e − μ / ( 2 τ ) . \begin{aligned}
\mathbb{E}_S[2^{-Z/\tau}] = \mathbb{E}_S\left[\prod_{j \in S}\left(2^{-a_j/\tau} + (1-2^{-a_j/\tau})(1-F_j)\right)\right] \le\prod_{j \in S}\left(2^{-a_j/\tau} + b_j(1-2^{-a_j/\tau})\right) \\
&= \prod_{j \in S}\left(1-f_j(1-2^{-a_j/\tau})\right) \le\exp\left(-\sum_{j \in S}f_j(1-2^{-a_j/\tau})\right) \le e^{-\mu/(2\tau)}.
\end{aligned} E S [ 2 − Z / τ ] = E S j ∈ S ∏ ( 2 − a j / τ + ( 1 − 2 − a j / τ ) ( 1 − F j ) ) ≤ j ∈ S ∏ ( 2 − a j / τ + b j ( 1 − 2 − a j / τ ) ) = j ∈ S ∏ ( 1 − f j ( 1 − 2 − a j / τ ) ) ≤ exp − j ∈ S ∑ f j ( 1 − 2 − a j / τ ) ≤ e − μ / ( 2 τ ) . The last two inequalities use 1 − x ≤ e − x 1-x \le e^{-x} 1 − x ≤ e − x 1 − 2 − q ≥ q / 2 1-2^{-q} \ge q/2 1 − 2 − q ≥ q /2 q ∈ [ 0 , 1 ] q \in[0,1] q ∈ [ 0 , 1 ] 0 ≤ a j ≤ τ 0 \le a_j \le\tau 0 ≤ a j ≤ τ 2 − Z / τ 2^{-Z/\tau} 2 − Z / τ
Pr S [ Z < μ / 2 ] = Pr S [ 2 − Z / τ > 2 − μ / ( 2 τ ) ] ≤ 2 μ / ( 2 τ ) E S [ 2 − Z / τ ] ≤ exp ( − ( 1 − ln 2 ) μ 2 τ ) ≤ e − μ / ( 8 τ ) , (11) \begin{aligned}
\Pr_S[Z < \mu/2] = \Pr_S\left[2^{-Z/\tau} > 2^{-\mu/(2\tau)}\right] \le2^{\mu/(2\tau)}\mathbb{E}_S[2^{-Z/\tau}] \\
&\le\exp\left(-\frac{(1-\ln2)\mu}{2\tau}\right) \le e^{-\mu/(8\tau)}, \tag*{(11)}
\end{aligned} S Pr [ Z < μ /2 ] = S Pr [ 2 − Z / τ > 2 − μ / ( 2 τ ) ] ≤ 2 μ / ( 2 τ ) E S [ 2 − Z / τ ] ≤ exp ( − 2 τ ( 1 − ln 2 ) μ ) ≤ e − μ / ( 8 τ ) , (11) where the last inequality uses ln 2 < 3 / 4 \ln2 < 3/4 ln 2 < 3/4
We next consider the case Z ≥ μ / 2 Z \ge\mu/2 Z ≥ μ /2 i ′ ≠ i i' \ne i i ′ = i S ′ ∈ S i ′ S' \in\mathcal{S}_{i'} S ′ ∈ S i ′ I i ′ , S ′ I_{i',S'} I i ′ , S ′ i ′ i' i ′ S ′ S' S ′ ( i ′ , S ′ ) (i',S') ( i ′ , S ′ ) S i = S S_i = S S i = S i i i C j C_j C j j ∈ S j \in S j ∈ S C j ≥ 1 C_j \ge1 C j ≥ 1
C j − 1 = ∑ i ′ , S ′ : j ∈ S ′ I i ′ , S ′ ∀ j ∈ S . C_j - 1 = \sum_{i',S':\,j \in S'} I_{i',S'} \qquad\forall j \in S. C j − 1 = i ′ , S ′ : j ∈ S ′ ∑ I i ′ , S ′ ∀ j ∈ S . Define
D = ∑ j ∈ S a j F j ( C j − 1 ) , D=\sum_{j\in S}a_jF_j(C_j-1), D = j ∈ S ∑ a j F j ( C j − 1 ) , thus D D D Z + D = ∑ j ∈ S a j F j C j Z+D=\sum_{j\in S}a_jF_jC_j Z + D = ∑ j ∈ S a j F j C j
Z 2 = ( ∑ j ∈ S a j F j C j a j F j C j ) 2 ≤ ( ∑ j ∈ S a j F j C j ) ( ∑ j ∈ S a j F j C j ) = X ( Z + D ) . \begin{aligned}
Z^2=\left(\sum_{j\in S}\sqrt{\frac{a_jF_j}{C_j}}\sqrt{a_jF_jC_j}\right)^2 \\
&\leq\left(\sum_{j\in S}\frac{a_jF_j}{C_j}\right)\left(\sum_{j\in S}a_jF_jC_j\right)=X(Z+D).
\end{aligned} Z 2 = j ∈ S ∑ C j a j F j a j F j C j 2 ≤ j ∈ S ∑ C j a j F j j ∈ S ∑ a j F j C j = X ( Z + D ) . To control D / Z D/Z D / Z Z ≥ μ / 2 Z\geq\mu/2 Z ≥ μ /2
c i , S ′ = min { 1 , 2 a ( S ∩ S ′ ) μ } , Y = ∑ i ′ , S ′ c i ′ , S ′ I i ′ , S ′ . c_{i,S'}=\min\left\{1,\frac{2a(S\cap S')}{\mu}\right\},\qquad Y=\sum_{i',S'}c_{i',S'}I_{i',S'}. c i , S ′ = min { 1 , μ 2 a ( S ∩ S ′ ) } , Y = i ′ , S ′ ∑ c i ′ , S ′ I i ′ , S ′ . The coefficients c i ′ , S ′ c_{i',S'} c i ′ , S ′ [ 0 , 1 ] [0,1] [ 0 , 1 ] ( i ′ , S ′ ) (i',S') ( i ′ , S ′ ) S ∩ S ′ S\cap S' S ∩ S ′ ∑ j ∈ S ∩ S ′ a j F j \sum_{j\in S\cap S'}a_jF_j ∑ j ∈ S ∩ S ′ a j F j Z Z Z S ∩ S ′ ⊆ S S\cap S'\subseteq S S ∩ S ′ ⊆ S a ( S ∩ S ′ ) a(S\cap S') a ( S ∩ S ′ ) F j ≤ 1 F_j\leq1 F j ≤ 1 Z ≥ μ / 2 > 0 Z\geq\mu/2>0 Z ≥ μ /2 > 0
1 Z ∑ j ∈ S ∩ S ′ a j F j ≤ min { 1 , a ( S ∩ S ′ ) Z } ≤ c i ′ , S ′ . \frac{1}{Z}\sum_{j\in S\cap S'}a_jF_j\leq\min\left\{1,\frac{a(S\cap S')}{Z}\right\}\leq c_{i',S'}. Z 1 j ∈ S ∩ S ′ ∑ a j F j ≤ min { 1 , Z a ( S ∩ S ′ ) } ≤ c i ′ , S ′ . Multiplying by I i ′ , S ′ I_{i',S'} I i ′ , S ′
D Z = ∑ i ′ , S ′ I i ′ , S ′ 1 Z ∑ j ∈ S ∩ S ′ a j F j ≤ Y . \frac{D}{Z}=\sum_{i',S'}I_{i',S'}\frac{1}{Z}\sum_{j\in S\cap S'}a_jF_j\leq Y. Z D = i ′ , S ′ ∑ I i ′ , S ′ Z 1 j ∈ S ∩ S ′ ∑ a j F j ≤ Y . Combining this with the bound from Cauchy–Schwarz yields
X ≥ Z 2 Z + D ≥ Z 1 + Y ≥ μ 2 ( 1 + Y ) . X\geq\frac{Z^2}{Z+D}\geq\frac{Z}{1+Y}\geq\frac{\mu}{2(1+Y)}. X ≥ Z + D Z 2 ≥ 1 + Y Z ≥ 2 ( 1 + Y ) μ . In particular, if X < 2 τ X<2\tau X < 2 τ Z ≥ μ / 2 Z\geq\mu/2 Z ≥ μ /2
Y > μ 4 τ − 1 > μ 8 τ , Y>\frac{\mu}{4\tau}-1>\frac{\mu}{8\tau}, Y > 4 τ μ − 1 > 8 τ μ , where the last inequality follows from μ > 32 τ \mu>32\tau μ > 32 τ Y > μ / ( 8 τ ) Y>\mu/(8\tau) Y > μ / ( 8 τ ) Y Y Y Pr S \Pr_S Pr S
ρ : = E [ Y ] = ∑ i ′ , S ′ c i ′ , S ′ y i ′ , S ′ . \rho:=\mathbb{E}[Y]=\sum_{i',S'}c_{i',S'}y_{i',S'}. ρ := E [ Y ] = i ′ , S ′ ∑ c i ′ , S ′ y i ′ , S ′ . Using c i ′ , S ′ ≤ 2 a ( S ∩ S ′ ) / μ c_{i',S'}\leq2a(S\cap S')/\mu c i ′ , S ′ ≤ 2 a ( S ∩ S ′ ) / μ (5) , we have
ρ ≤ 2 μ ∑ i ′ , S ′ a ( S ∩ S ′ ) y i ′ , S ′ = 2 μ ∑ j ∈ S a j ∑ i ′ , S ′ : j ∈ S ′ y i ′ , S ′ ≤ 2 μ ∑ j ∈ S a j f j = 2. \rho\leq\frac{2}{\mu}\sum_{i',S'}a(S\cap S')y_{i',S'}=\frac{2}{\mu}\sum_{j\in S}a_j\sum_{i',S':j\in S'}y_{i',S'}\leq\frac{2}{\mu}\sum_{j\in S}a_jf_j=2. ρ ≤ μ 2 i ′ , S ′ ∑ a ( S ∩ S ′ ) y i ′ , S ′ = μ 2 j ∈ S ∑ a j i ′ , S ′ : j ∈ S ′ ∑ y i ′ , S ′ ≤ μ 2 j ∈ S ∑ a j f j = 2. For brevity, let α , β , γ \alpha,\beta,\gamma α , β , γ ( i ′ , S ′ ) (i',S') ( i ′ , S ′ ) i ′ ≠ i i' \ne i i ′ = i S ′ ∈ S i ′ S' \in S_{i'} S ′ ∈ S i ′ Y 3 Y^3 Y 3 I α 2 = I α I_\alpha^2=I_\alpha I α 2 = I α
E S [ Y 3 ] = ∑ α c α 3 E S [ I α ] + 3 ∑ α ≠ β c α 2 c β E S [ I α I β ] + ∑ α , β , γ d i s t i n c t c α c β c γ E S [ I α I β I γ ] ≤ ∑ α c α 3 y α + 3 ∑ α ≠ β c α 2 c β y α y β + ∑ α , β , γ d i s t i n c t c α c β c γ y α y β y γ ≤ ∑ α c α y α + 3 ∑ α , β ( c α y α ) ( c β y β ) + ∑ α , β , γ ( c α y α ) ( c β y β ) ( c γ y γ ) = ρ + 3 ρ 2 + ρ 3 ≤ 2 + 3 ⋅ 2 2 + 2 3 = 22. (12) \begin{aligned}
\mathbb{E}_S[Y^3] &= \sum_\alpha c_\alpha^3\mathbb{E}_S[I_\alpha] + 3\sum_{\alpha\ne\beta}c_\alpha^2c_\beta\mathbb{E}_S[I_\alpha I_\beta] + \sum_{\alpha,\beta,\gamma\ \mathrm{distinct}}c_\alpha c_\beta c_\gamma\mathbb{E}_S[I_\alpha I_\beta I_\gamma]\\
&\le\sum_\alpha c_\alpha^3y_\alpha+ 3\sum_{\alpha\ne\beta}c_\alpha^2c_\beta y_\alpha y_\beta+ \sum_{\alpha,\beta,\gamma\ \mathrm{distinct}}c_\alpha c_\beta c_\gamma y_\alpha y_\beta y_\gamma\\
&\le\sum_\alpha c_\alpha y_\alpha+ 3\sum_{\alpha,\beta}(c_\alpha y_\alpha)(c_\beta y_\beta) + \sum_{\alpha,\beta,\gamma}(c_\alpha y_\alpha)(c_\beta y_\beta)(c_\gamma y_\gamma)\\
&= \rho+3\rho^2+\rho^3\le2+3\cdot2^2+2^3=22. \tag*{(12)}
\end{aligned} E S [ Y 3 ] = α ∑ c α 3 E S [ I α ] + 3 α = β ∑ c α 2 c β E S [ I α I β ] + α , β , γ distinct ∑ c α c β c γ E S [ I α I β I γ ] ≤ α ∑ c α 3 y α + 3 α = β ∑ c α 2 c β y α y β + α , β , γ distinct ∑ c α c β c γ y α y β y γ ≤ α ∑ c α y α + 3 α , β ∑ ( c α y α ) ( c β y β ) + α , β , γ ∑ ( c α y α ) ( c β y β ) ( c γ y γ ) = ρ + 3 ρ 2 + ρ 3 ≤ 2 + 3 ⋅ 2 2 + 2 3 = 22. (12) The first inequality follows from the conditional product bound in Lemma 3.2, since I i ′ , S ′ = χ u i ′ , S ′ I_{i',S'}=\chi_{u_{i',S'}} I i ′ , S ′ = χ u i ′ , S ′ u i , S u_{i,S} u i , S 0 ≤ c α ≤ 1 0\le c_\alpha\le1 0 ≤ c α ≤ 1 ρ ≤ 2 \rho\le2 ρ ≤ 2
We have shown that X < 2 τ X<2\tau X < 2 τ Z < μ / 2 Z<\mu/2 Z < μ /2 Y > μ / ( 8 τ ) Y>\mu/(8\tau) Y > μ / ( 8 τ ) (11) with the union bound and Markov’s inequality applied to Y 3 Y^3 Y 3
Pr S [ X < 2 τ ] ≤ Pr S [ Z < μ / 2 ] + Pr S [ Y > μ / ( 8 τ ) ] ≤ e − μ / ( 8 τ ) + E S [ Y 3 ] ( μ / ( 8 τ ) ) 3 ≤ e − μ / ( 8 τ ) + 22 ( 8 τ / μ ) 3 ≤ 28 ( 8 τ / μ ) 3 ≤ ( 32 τ / μ ) 3 . \begin{aligned}
\Pr_S[X<2\tau]\le\Pr_S[Z<\mu/2]+\Pr_S[Y>\mu/(8\tau)]\le e^{-\mu/(8\tau)}+\frac{\mathbb{E}_S[Y^3]}{(\mu/(8\tau))^3} \\
&\le e^{-\mu/(8\tau)}+22(8\tau/\mu)^3\le28(8\tau/\mu)^3\le(32\tau/\mu)^3.
\end{aligned} S Pr [ X < 2 τ ] ≤ S Pr [ Z < μ /2 ] + S Pr [ Y > μ / ( 8 τ )] ≤ e − μ / ( 8 τ ) + ( μ / ( 8 τ ) ) 3 E S [ Y 3 ] ≤ e − μ / ( 8 τ ) + 22 ( 8 τ / μ ) 3 ≤ 28 ( 8 τ / μ ) 3 ≤ ( 32 τ / μ ) 3 . Here the third inequality uses (12) , and the fourth uses e − q ≤ 6 / q 3 e^{-q}\le6/q^3 e − q ≤ 6/ q 3 q = μ / ( 8 τ ) > 4 q=\mu/(8\tau)>4 q = μ / ( 8 τ ) > 4 (10) , and hence Lemma 3.3 . □
We now combine the bounds for individual agents to prove Lemma 3.1.
Proof of Lemma 3.1. Fix an agent i ∈ N i\in N i ∈ N S i ∈ L i S_i\in L_i S i ∈ L i a i , S i ( A i ) ≥ τ a^{i,S_i}(A_i)\ge\tau a i , S i ( A i ) ≥ τ Pr [ S i = S ] = y i , S \Pr[S_i=S]=y_{i,S} Pr [ S i = S ] = y i , S Lemma 3.3 , we obtain
Pr [ a i , S i ( A i ) < τ ] = ∑ S ∈ S i y i , S Pr [ a i , S ( A i ) < τ ] ≤ ∑ S ∈ S i y i , S min { 1 , ( 32 τ μ i , S ) 3 } . \begin{aligned}
\Pr[a^{i,S_i}(A_i)<\tau]=\sum_{S\in\mathcal{S}_i}y_{i,S}\Pr[a^{i,S}(A_i)<\tau] \\
&\le\sum_{S\in\mathcal{S}_i}y_{i,S}\min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}.
\end{aligned} Pr [ a i , S i ( A i ) < τ ] = S ∈ S i ∑ y i , S Pr [ a i , S ( A i ) < τ ] ≤ S ∈ S i ∑ y i , S min { 1 , ( μ i , S 32 τ ) 3 } . The union bound over all agents, together with (7) , shows that the algorithm fails with probability at most 1 / 4 1/4 1/4
Applications to additive and submodular valuations
In this subsection, we apply Lemma 3.1 to additive and submodular valuations. The configuration LP has exponentially many variables, so we do not solve it exactly. Since we only aim for an O ( n ) O(\sqrt{n}) O ( n ) § 8 proves the following lemma by combining ellipsoid feasibility and primal recovery [40 ] with the submodular knapsack algorithm of Sviridenko [63 ] or the demand-query algorithm of Badanidiyuru, Dobzinski, and Oren [6 ] , according to the valuation class.
Lemma 3.4. There is a polynomial-time algorithm that either detects that T L P = 0 T_{\mathrm{LP}}=0 T LP = 0 T T T T > T L P / 6 T>T_{\mathrm{LP}}/6 T > T LP /6
We apply Lemma 3.4 to obtain a configuration solution with objective value T > T L P / 6 T>T_{\mathrm{LP}}/6 T > T LP /6 4 ( i , S ) (i,S) ( i , S ) w i , S ∈ R ≥ 0 S w^{i,S}\in\mathbb{R}_{\geq0}^{S} w i , S ∈ R ≥ 0 S
w i , S ( Q ) ≤ v i ( Q ) ( Q ⊆ S ) , w i , S ( S ) = v i ( S ) . (13) w^{i,S}(Q)\leq v_i(Q)\quad(Q\subseteq S),\qquad w^{i,S}(S)=v_i(S). \tag*{(13)} w i , S ( Q ) ≤ v i ( Q ) ( Q ⊆ S ) , w i , S ( S ) = v i ( S ) . (13) To apply Lemma 3.1, we first assume we are given supporting clauses for all pairs ( i , S ) (i,S) ( i , S ) Theorem 3.5 , we show how to obtain these clauses for each valuation class.
Preparing the configuration solution. Normalize the clause coefficients and set the rounding threshold by
a j i , S = T w j i , S v i ( S ) , τ = T 128 ⌈ n ⌉ . a_j^{i,S}=\frac{T w_j^{i,S}}{v_i(S)},\qquad\tau=\frac{T}{128\lceil\sqrt{n}\rceil}. a j i , S = v i ( S ) T w j i , S , τ = 128 ⌈ n ⌉ T . Since v i ( S ) ≥ T v_i(S)\geq T v i ( S ) ≥ T a i , S ( Q ) ≤ v i ( Q ) a^{i,S}(Q)\leq v_i(Q) a i , S ( Q ) ≤ v i ( Q ) Q ⊆ S Q\subseteq S Q ⊆ S a i , S ( S ) = T a^{i,S}(S)=T a i , S ( S ) = T S S S j j j a j i , S ≥ τ a_j^{i,S}\geq\tau a j i , S ≥ τ S S S { j } \{j\} { j } a j i , S a_j^{i,S} a j i , S (2) and cannot increase the total mass on any item. We continue to write y i , S y_{i,S} y i , S
The resulting singletons form the large configurations L i L_i L i T T T τ \tau τ S i S_i S i τ < T \tau<T τ < T (7) .
Bounding the baseline values. Define b j b_j b j f j = 1 − b j f_j=1-b_j f j = 1 − b j (5) for the resulting configuration solution. For every small configuration S S S
P ( S ) = ∑ j ∈ S b j f j . P(S)=\sum_{j\in S}\frac{b_j}{f_j}. P ( S ) = j ∈ S ∑ f j b j . This penalty is well defined: every item in S S S S S S (5) implies f j > 0 f_j>0 f j > 0 (5) , we obtain
∑ i ∑ S ∈ S i y i , S P ( S ) = ∑ j : f j > 0 b j f j ∑ i ∑ S ∈ S i j ∈ S y i , S ≤ ∑ j b j ≤ n . (14) \sum_i\sum_{S\in S_i}y_{i,S}P(S)
=\sum_{j:f_j>0}\frac{b_j}{f_j}\sum_i\sum_{\substack{S\in S_i\\j\in S}}y_{i,S}
\leq\sum_j b_j\leq n. \tag*{(14)} i ∑ S ∈ S i ∑ y i , S P ( S ) = j : f j > 0 ∑ f j b j i ∑ S ∈ S i j ∈ S ∑ y i , S ≤ j ∑ b j ≤ n . (14) The last inequality follows from (2) , since ∑ j b j \sum_j b_j ∑ j b j S ∈ S i S\in S_i S ∈ S i T T T
T 2 ≤ ( ∑ j ∈ S f j a j i , S ) ( ∑ j ∈ S a j i , S f j ) = μ i , S ∑ j ∈ S a j i , S f j . T^2\leq\left(\sum_{j\in S}f_j a_j^{i,S}\right)\left(\sum_{j\in S}\frac{a_j^{i,S}}{f_j}\right)=\mu_{i,S}\sum_{j\in S}\frac{a_j^{i,S}}{f_j}. T 2 ≤ j ∈ S ∑ f j a j i , S j ∈ S ∑ f j a j i , S = μ i , S j ∈ S ∑ f j a j i , S . Using f j = 1 − b j f_j=1-b_j f j = 1 − b j a j i , S ≤ τ a_j^{i,S}\le\tau a j i , S ≤ τ
∑ j ∈ S a j i , S f j = T + ∑ j ∈ S a j i , S b j f j ≤ T + τ P ( S ) = T ( 1 + P ( S ) 128 ⌈ n ⌉ ) . \sum_{j\in S}\frac{a_j^{i,S}}{f_j}=T+\sum_{j\in S}a_j^{i,S}\frac{b_j}{f_j}\le T+\tau P(S)=T\left(1+\frac{P(S)}{128\lceil\sqrt{n}\rceil}\right). j ∈ S ∑ f j a j i , S = T + j ∈ S ∑ a j i , S f j b j ≤ T + τ P ( S ) = T ( 1 + 128 ⌈ n ⌉ P ( S ) ) . Combining these inequalities yields
μ i , S ≥ T 1 + P ( S ) 128 ⌈ n ⌉ . \mu_{i,S}\ge\frac{T}{1+\frac{P(S)}{128\lceil\sqrt{n}\rceil}}. μ i , S ≥ 1 + 128 ⌈ n ⌉ P ( S ) T . Verifying the budget condition. The baseline bound and the choice of τ \tau τ
32 τ μ i , S ≤ 32 128 ⌈ n ⌉ ( 1 + P ( S ) 128 ⌈ n ⌉ ) . \frac{32\tau}{\mu_{i,S}}\le\frac{32}{128\lceil\sqrt{n}\rceil}\left(1+\frac{P(S)}{128\lceil\sqrt{n}\rceil}\right). μ i , S 32 τ ≤ 128 ⌈ n ⌉ 32 ( 1 + 128 ⌈ n ⌉ P ( S ) ) . We consider two cases according to the value of P ( S ) P(S) P ( S )
If P ( S ) ≤ 128 ⌈ n ⌉ P(S)\le128\lceil\sqrt{n}\rceil P ( S ) ≤ 128 ⌈ n ⌉
min { 1 , ( 32 τ μ i , S ) 3 } ≤ ( 64 128 ⌈ n ⌉ ) 3 ≤ 1 8 n 3 / 2 . \min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}\le\left(\frac{64}{128\lceil\sqrt{n}\rceil}\right)^3\le\frac{1}{8n^{3/2}}. min { 1 , ( μ i , S 32 τ ) 3 } ≤ ( 128 ⌈ n ⌉ 64 ) 3 ≤ 8 n 3/2 1 . If P ( S ) > 128 ⌈ n ⌉ P(S)>128\lceil\sqrt{n}\rceil P ( S ) > 128 ⌈ n ⌉ 1 + P ( S ) / ( 128 ⌈ n ⌉ ) ≤ 2 P ( S ) / ( 128 ⌈ n ⌉ ) 1+P(S)/(128\lceil\sqrt{n}\rceil)\le2P(S)/(128\lceil\sqrt{n}\rceil) 1 + P ( S ) / ( 128 ⌈ n ⌉) ≤ 2 P ( S ) / ( 128 ⌈ n ⌉)
min { 1 , ( 32 τ μ i , S ) 3 } ≤ min { 1 , ( 64 P ( S ) ( 128 ⌈ n ⌉ ) 2 ) 3 } ≤ 64 P ( S ) ( 128 ⌈ n ⌉ ) 2 ≤ P ( S ) 256 n , \min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}\le\min\left\{1,\left(\frac{64P(S)}{(128\lceil\sqrt{n}\rceil)^2}\right)^3\right\}\le\frac{64P(S)}{(128\lceil\sqrt{n}\rceil)^2}\le\frac{P(S)}{256n}, min { 1 , ( μ i , S 32 τ ) 3 } ≤ min { 1 , ( ( 128 ⌈ n ⌉ ) 2 64 P ( S ) ) 3 } ≤ ( 128 ⌈ n ⌉ ) 2 64 P ( S ) ≤ 256 n P ( S ) , where the second inequality uses min { 1 , u 3 } ≤ u \min\{1,u^3\}\le u min { 1 , u 3 } ≤ u u ≥ 0 u\ge0 u ≥ 0
Applying these bounds in their respective cases and extending both sums to all small configurations, we obtain
∑ i ∑ S ∈ S i y i , S min { 1 , ( 32 τ μ i , S ) 3 } ≤ 1 8 n 3 / 2 ∑ i ∑ S ∈ S i y i , S + 1 256 n ∑ i ∑ S ∈ S i y i , S P ( S ) ≤ n 1 8 n 3 / 2 + n 1 256 n ≤ 1 8 + 1 256 < 1 4 . \begin{aligned}
\sum_i\sum_{S\in\mathcal{S}_i}y_{i,S}\min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}
\le\frac{1}{8n^{3/2}}\sum_i\sum_{S\in\mathcal{S}_i}y_{i,S}+\frac{1}{256n}\sum_i\sum_{S\in\mathcal{S}_i}y_{i,S}P(S) \\
&\le n\frac{1}{8n^{3/2}}+n\frac{1}{256n}\le\frac{1}{8}+\frac{1}{256}<\frac{1}{4}.
\end{aligned} i ∑ S ∈ S i ∑ y i , S min { 1 , ( μ i , S 32 τ ) 3 } ≤ 8 n 3/2 1 i ∑ S ∈ S i ∑ y i , S + 256 n 1 i ∑ S ∈ S i ∑ y i , S P ( S ) ≤ n 8 n 3/2 1 + n 256 n 1 ≤ 8 1 + 256 1 < 4 1 . Here we used (2) to bound the total mass of small configurations by n n n (14) to bound their weighted penalty. This verifies (7) and gives the following theorem.
Theorem 3.5. Given a feasible configuration solution with objective value T T T T / ( 128 ⌈ n ⌉ ) T/(128\lceil\sqrt{n}\rceil) T / ( 128 ⌈ n ⌉) 3 / 4 3/4 3/4
Proof. If T = 0 T=0 T = 0 T > 0 T>0 T > 0 (7) . Thus, with probability at least 3 / 4 3/4 3/4 i i i A i A_i A i a i , S i ( A i ) ≥ τ a^{i,S_i}(A_i)\ge\tau a i , S i ( A i ) ≥ τ v i ( A i ) ≥ τ v_i(A_i)\ge\tau v i ( A i ) ≥ τ
Now we discuss how to construct the supporting clauses for different valuation functions.
Additive valuations. For additive valuations v i ( Q ) = ∑ j ∈ Q v i j v_i(Q) = \sum_{j\in Q} v_{ij} v i ( Q ) = ∑ j ∈ Q v ij w j i , S = v i j w_j^{i,S} = v_{ij} w j i , S = v ij (13) . Given a feasible configuration solution with objective value T T T Theorem 3.5 yields an allocation giving every agent value at least T / ( 128 n ) T/(128\sqrt{n}) T / ( 128 n ) 3 / 4 3/4 3/4 v i j v_{ij} v ij Lemma 3.4 produces a configuration solution with objective value T > T L P / 6 T > T_{\mathrm{LP}}/6 T > T LP /6 O ( n ) O(\sqrt{n}) O ( n )
Submodular valuations. Dobzinski, Nisan, and Schapira [24 ] construct a supporting clause by ordering the items in S S S (13) and require O ( ∣ S ∣ ) O(|S|) O ( ∣ S ∣ ) Lemma 3.4 produces a configuration solution with objective value T > T L P / 6 T > T_{\mathrm{LP}}/6 T > T LP /6 Theorem 3.5 yields an O ( n ) O(\sqrt{n}) O ( n )
Additive lower bounds for subadditive valuations
The supporting clauses required by Theorem 3.5 may not exist for subadditive valuations. We instead construct nonnegative additive coefficients satisfying a i , S ( Q ) ≤ v i ( Q ) a^{i,S}(Q) \leq v_i(Q) a i , S ( Q ) ≤ v i ( Q ) Q ⊆ S Q \subseteq S Q ⊆ S a i , S ( S ) = v i ( S ) a^{i,S}(S) = v_i(S) a i , S ( S ) = v i ( S ) μ i , S = ∑ j ∈ S a j i , S f j \mu_{i,S} = \sum_{j\in S} a_j^{i,S} f_j μ i , S = ∑ j ∈ S a j i , S f j
Dobzinski [25 ] showed that demand queries suffice to find prices supporting a subadditive valuation on a given set within a logarithmic factor. In Lemma 3.6 we use a geometric grid of uniform prices, as in the single-buyer revenue bound of Balcan, Blum, and Mansour [4 ] , and derive the quantitative bound that we extend below. Lemma 3.7 extends this construction by scaling item prices by 1 / f j 1/f_j 1/ f j μ i , S \mu_{i,S} μ i , S
Lemma 3.6. Let v v v S S S O ( 1 + log ∣ S ∣ ) O(1+\log|S|) O ( 1 + log ∣ S ∣ ) O ( ∣ S ∣ ) O(|S|) O ( ∣ S ∣ ) a ( Q ) = ∑ j ∈ Q a j a(Q) = \sum_{j\in Q} a_j a ( Q ) = ∑ j ∈ Q a j
a ( Q ) ≤ v ( Q ) ( Q ⊆ S ) , a ( S ) ≥ v ( S ) 2 ⌈ log 2 ( 2 ∣ S ∣ ) ⌉ . a(Q) \leq v(Q) \quad(Q \subseteq S), \qquad a(S) \geq\frac{v(S)}{2\lceil\log_2(2|S|)\rceil}. a ( Q ) ≤ v ( Q ) ( Q ⊆ S ) , a ( S ) ≥ 2 ⌈ log 2 ( 2∣ S ∣ )⌉ v ( S ) . Proof. Let W = v ( S ) W = v(S) W = v ( S ) s = ∣ S ∣ s = |S| s = ∣ S ∣ W = 0 W = 0 W = 0 W > 0 W > 0 W > 0 ν = max j ∈ S v ( { j } ) \nu= \max_{j\in S} v(\{j\}) ν = max j ∈ S v ({ j }) 0 < ν ≤ W ≤ s ν 0 < \nu\leq W \leq s\nu 0 < ν ≤ W ≤ s ν
For a uniform item price t > 0 t > 0 t > 0 D t ⊆ S D_t \subseteq S D t ⊆ S S S S
a j ( t ) = t 1 { j ∈ D t } . a_j^{(t)} = t\mathbf{1}_{\{j\in D_t\}}. a j ( t ) = t 1 { j ∈ D t } . We first show that these coefficients give an additive lower bound. For any Q ⊆ S Q \subseteq S Q ⊆ S D t D_t D t
v ( D t ) − t ∣ D t ∣ ≥ v ( D t ∖ Q ) − t ∣ D t ∖ Q ∣ . v(D_t) - t|D_t| \geq v(D_t \setminus Q) - t|D_t \setminus Q|. v ( D t ) − t ∣ D t ∣ ≥ v ( D t ∖ Q ) − t ∣ D t ∖ Q ∣. Rearranging and then applying subadditivity and monotonicity, we obtain
a ( t ) ( Q ) = t ∣ D t ∩ Q ∣ ≤ v ( D t ) − v ( D t ∖ Q ) ≤ v ( D t ∩ Q ) ≤ v ( Q ) . a^{(t)}(Q) = t|D_t \cap Q| \leq v(D_t) - v(D_t \setminus Q) \leq v(D_t \cap Q) \leq v(Q). a ( t ) ( Q ) = t ∣ D t ∩ Q ∣ ≤ v ( D t ) − v ( D t ∖ Q ) ≤ v ( D t ∩ Q ) ≤ v ( Q ) . We now choose a price for which the additive total is sufficiently large. Set
L = ⌈ log 2 2 s ν W ⌉ , t ℓ = ν 2 − ℓ ( 0 ≤ ℓ ≤ L ) . L=\left\lceil\log_{2}\frac{2s\nu}{W}\right\rceil,\qquad t_{\ell}=\nu2^{-\ell}\quad(0\le\ell\le L). L = ⌈ log 2 W 2 s ν ⌉ , t ℓ = ν 2 − ℓ ( 0 ≤ ℓ ≤ L ) . The bounds on W W W 1 ≤ L ≤ ⌈ log 2 ( 2 s ) ⌉ 1\le L\le\lceil\log_{2}(2s)\rceil 1 ≤ L ≤ ⌈ log 2 ( 2 s )⌉ t 1 , … , t L t_{1},\ldots,t_{L} t 1 , … , t L a ( t ℓ ) a^{(t_{\ell})} a ( t ℓ ) S S S a a a
To analyze this choice, define the maximum utility at price t t t
U ( t ) = max D ⊆ S { v ( D ) − t ∣ D ∣ } . U(t)=\max_{D\subseteq S}\{v(D)-t|D|\}. U ( t ) = D ⊆ S max { v ( D ) − t ∣ D ∣ } . At the initial price t 0 = ν t_{0}=\nu t 0 = ν v ( D ) ≤ ∑ j ∈ D v ( { j } ) ≤ ν ∣ D ∣ v(D)\le\sum_{j\in D}v(\{j\})\le\nu|D| v ( D ) ≤ ∑ j ∈ D v ({ j }) ≤ ν ∣ D ∣ D ⊆ S D\subseteq S D ⊆ S U ( t 0 ) = 0 U(t_{0})=0 U ( t 0 ) = 0 L L L t L ≤ W / ( 2 s ) t_{L}\le W/(2s) t L ≤ W / ( 2 s ) S S S
U ( t L ) ≥ v ( S ) − t L ∣ S ∣ ≥ W / 2. U(t_{L})\ge v(S)-t_{L}|S|\ge W/2. U ( t L ) ≥ v ( S ) − t L ∣ S ∣ ≥ W /2. For each ℓ = 1 , … , L \ell=1,\ldots,L ℓ = 1 , … , L D t ℓ D_{t_{\ell}} D t ℓ t ℓ − 1 = 2 t ℓ t_{\ell-1}=2t_{\ell} t ℓ − 1 = 2 t ℓ
U ( t ℓ − 1 ) ≥ v ( D t ℓ ) − 2 t ℓ ∣ D t ℓ ∣ = U ( t ℓ ) − t ℓ ∣ D t ℓ ∣ . U(t_{\ell-1})\ge v(D_{t_{\ell}})-2t_{\ell}|D_{t_{\ell}}|=U(t_{\ell})-t_{\ell}|D_{t_{\ell}}|. U ( t ℓ − 1 ) ≥ v ( D t ℓ ) − 2 t ℓ ∣ D t ℓ ∣ = U ( t ℓ ) − t ℓ ∣ D t ℓ ∣. Equivalently, the increase in maximum utility when the price is halved satisfies
U ( t ℓ ) − U ( t ℓ − 1 ) ≤ t ℓ ∣ D t ℓ ∣ = a ( t ℓ ) ( S ) . U(t_{\ell})-U(t_{\ell-1})\le t_{\ell}|D_{t_{\ell}}|=a^{(t_{\ell})}(S). U ( t ℓ ) − U ( t ℓ − 1 ) ≤ t ℓ ∣ D t ℓ ∣ = a ( t ℓ ) ( S ) . Summing over the price levels gives
W 2 ≤ U ( t L ) − U ( t 0 ) ≤ ∑ ℓ = 1 L a ( t ℓ ) ( S ) . \frac{W}{2}\le U(t_{L})-U(t_{0})\le\sum_{\ell=1}^{L}a^{(t_{\ell})}(S). 2 W ≤ U ( t L ) − U ( t 0 ) ≤ ℓ = 1 ∑ L a ( t ℓ ) ( S ) . Since we return the candidate with the largest total, its value is at least the average of these totals. Therefore,
a ( S ) ≥ 1 L ∑ ℓ = 1 L a ( t ℓ ) ( S ) ≥ W 2 L ≥ v ( S ) 2 ⌈ log 2 ( 2 ∣ S ∣ ) ⌉ . a(S)\ge\frac{1}{L}\sum_{\ell=1}^{L}a^{(t_{\ell})}(S)\ge\frac{W}{2L}\ge\frac{v(S)}{2\lceil\log_{2}(2|S|)\rceil}. a ( S ) ≥ L 1 ℓ = 1 ∑ L a ( t ℓ ) ( S ) ≥ 2 L W ≥ 2 ⌈ log 2 ( 2∣ S ∣ )⌉ v ( S ) . Computing W W W ν \nu ν s + 1 = O ( ∣ S ∣ ) s+1=O(|S|) s + 1 = O ( ∣ S ∣ ) L = O ( 1 + log ∣ S ∣ ) L=O(1+\log|S|) L = O ( 1 + log ∣ S ∣ ) t ℓ ∣ D t ℓ ∣ t_{\ell}|D_{t_{\ell}}| t ℓ ∣ D t ℓ ∣
Using these additive lower bounds in the proof of Theorem 3.5 yields only an O ( n ( 1 + log m ) ) O(\sqrt{n}(1+\log m)) O ( n ( 1 + log m )) j j j f j f_j f j (7) directly.
Lemma 3.7. Let v v v v ( S ) = W > 0 v(S)=W>0 v ( S ) = W > 0 ν = max j ∈ S v ( { j } ) \nu=\max_{j\in S}v(\{j\}) ν = max j ∈ S v ({ j }) 0 < f j ≤ 1 0<f_j\le1 0 < f j ≤ 1 j ∈ S j\in S j ∈ S P = ∑ j ∈ S ( 1 − f j ) / f j P=\sum_{j\in S}(1-f_j)/f_j P = ∑ j ∈ S ( 1 − f j ) / f j s = ∣ S ∣ s=|S| s = ∣ S ∣ a ∈ [ 0 , ν ] S a\in[0,\nu]^S a ∈ [ 0 , ν ] S μ = ∑ j ∈ S f j a j \mu=\sum_{j\in S}f_ja_j μ = ∑ j ∈ S f j a j
3 W 4 ≤ μ [ 2 + log 2 s ν μ ] + 4 ν P μ . (15) \frac{3W}{4}\le\mu\left[2+\log_{2}\frac{s\nu}{\mu}\right]+4\sqrt{\nu P\mu}. \tag*{(15)} 4 3 W ≤ μ [ 2 + log 2 μ s ν ] + 4 ν P μ . (15) Proof. Monotonicity and subadditivity give 0 < ν ≤ W ≤ s ν 0 < \nu\le W \le s\nu 0 < ν ≤ W ≤ s ν t ℓ = ν 2 − ℓ t_\ell=\nu2^{-\ell} t ℓ = ν 2 − ℓ L L L t L ( s + P ) ≤ W / 4 t_L(s+P)\le W/4 t L ( s + P ) ≤ W /4 ℓ = 0 , … , L \ell=0,\ldots,L ℓ = 0 , … , L S S S t ℓ / f j t_\ell/f_j t ℓ / f j D ℓ D_\ell D ℓ
a j ( ℓ ) = t ℓ f j 1 { j ∈ D ℓ } , μ ℓ = ∑ j ∈ S f j a j ( ℓ ) = t ℓ ∣ D ℓ ∣ . a_j^{(\ell)}=\frac{t_\ell}{f_j}\mathbf{1}_{\{j\in D_\ell\}},\qquad\mu_\ell=\sum_{j\in S}f_j a_j^{(\ell)}=t_\ell|D_\ell|. a j ( ℓ ) = f j t ℓ 1 { j ∈ D ℓ } , μ ℓ = j ∈ S ∑ f j a j ( ℓ ) = t ℓ ∣ D ℓ ∣. As in the proof of Lemma 3.6, comparing the utilities of D ℓ D_\ell D ℓ D ℓ ∖ Q D_\ell\setminus Q D ℓ ∖ Q Q ⊆ S Q\subseteq S Q ⊆ S
a ( ℓ ) ( Q ) = t ℓ ∑ j ∈ D ℓ ∩ Q 1 f j ≤ v ( D ℓ ) − v ( D ℓ ∖ Q ) ≤ v ( D ℓ ∩ Q ) ≤ v ( Q ) . a^{(\ell)}(Q)=t_\ell\sum_{j\in D_\ell\cap Q}\frac{1}{f_j}\le v(D_\ell)-v(D_\ell\setminus Q)\le v(D_\ell\cap Q)\le v(Q). a ( ℓ ) ( Q ) = t ℓ j ∈ D ℓ ∩ Q ∑ f j 1 ≤ v ( D ℓ ) − v ( D ℓ ∖ Q ) ≤ v ( D ℓ ∩ Q ) ≤ v ( Q ) . Thus, every candidate is an additive lower bound. Taking Q = { j } Q=\{j\} Q = { j } a j ( ℓ ) ≤ v ( { j } ) ≤ ν a_j^{(\ell)}\le v(\{j\})\le\nu a j ( ℓ ) ≤ v ({ j }) ≤ ν μ ℓ \mu_\ell μ ℓ a a a μ = ∑ j ∈ S f j a j \mu=\sum_{j\in S}f_j a_j μ = ∑ j ∈ S f j a j
To analyze μ \mu μ t t t
U ( t ) = max D ⊆ S { v ( D ) − t ∑ j ∈ D 1 f j } . U(t)=\max_{D\subseteq S}\left\{v(D)-t\sum_{j\in D}\frac{1}{f_j}\right\}. U ( t ) = D ⊆ S max ⎩ ⎨ ⎧ v ( D ) − t j ∈ D ∑ f j 1 ⎭ ⎬ ⎫ . Since v ( D ) ≤ ν ∣ D ∣ v(D)\le\nu|D| v ( D ) ≤ ν ∣ D ∣ f j ≤ 1 f_j\le1 f j ≤ 1 t 0 = ν t_0=\nu t 0 = ν U ( t 0 ) = 0 U(t_0)=0 U ( t 0 ) = 0 ∑ j ∈ S f j − 1 = s + P \sum_{j\in S}f_j^{-1}=s+P ∑ j ∈ S f j − 1 = s + P t L ( s + P ) ≤ W / 4 t_L(s+P)\le W/4 t L ( s + P ) ≤ W /4
U ( t L ) ≥ v ( S ) − t L ∑ j ∈ S 1 f j = W − t L ( s + P ) ≥ 3 W 4 . U(t_L)\ge v(S)-t_L\sum_{j\in S}\frac{1}{f_j}=W-t_L(s+P)\ge\frac{3W}{4}. U ( t L ) ≥ v ( S ) − t L j ∈ S ∑ f j 1 = W − t L ( s + P ) ≥ 4 3 W . In particular, D L D_L D L μ ≥ μ L > 0 \mu\ge\mu_L>0 μ ≥ μ L > 0 f j ≤ 1 f_j\le1 f j ≤ 1 μ ≤ s ν \mu\le s\nu μ ≤ s ν
As in Lemma 3.6, we compare a demanded set at two consecutive prices. For 1 ≤ ℓ ≤ L 1\le\ell\le L 1 ≤ ℓ ≤ L D ℓ D_\ell D ℓ t ℓ − 1 = 2 t ℓ t_{\ell-1}=2t_\ell t ℓ − 1 = 2 t ℓ
U ( t ℓ − 1 ) ≥ v ( D ℓ ) − 2 t ℓ ∑ j ∈ D ℓ 1 f j = U ( t ℓ ) − t ℓ ∑ j ∈ D ℓ 1 f j . U(t_{\ell-1})\ge v(D_\ell)-2t_\ell\sum_{j\in D_\ell}\frac{1}{f_j}=U(t_\ell)-t_\ell\sum_{j\in D_\ell}\frac{1}{f_j}. U ( t ℓ − 1 ) ≥ v ( D ℓ ) − 2 t ℓ j ∈ D ℓ ∑ f j 1 = U ( t ℓ ) − t ℓ j ∈ D ℓ ∑ f j 1 . Therefore,
U ( t ℓ ) − U ( t ℓ − 1 ) ≤ t ℓ ∑ j ∈ D ℓ 1 f j = t ℓ ∣ D ℓ ∣ + t ℓ ∑ j ∈ D ℓ 1 − f j f j . U(t_\ell)-U(t_{\ell-1})\le t_\ell\sum_{j\in D_\ell}\frac{1}{f_j}=t_\ell|D_\ell|+t_\ell\sum_{j\in D_\ell}\frac{1-f_j}{f_j}. U ( t ℓ ) − U ( t ℓ − 1 ) ≤ t ℓ j ∈ D ℓ ∑ f j 1 = t ℓ ∣ D ℓ ∣ + t ℓ j ∈ D ℓ ∑ f j 1 − f j . Summing over ℓ = 1 , … , L \ell=1,\ldots,L ℓ = 1 , … , L
3 W 4 ≤ U ( t L ) − U ( t 0 ) ≤ A + B , \frac{3W}{4}\le U(t_L)-U(t_0)\le A+B, 4 3 W ≤ U ( t L ) − U ( t 0 ) ≤ A + B , where
A = ∑ ℓ = 1 L t ℓ ∣ D ℓ ∣ , B = ∑ ℓ = 1 L t ℓ ∑ j ∈ D ℓ 1 − f j f j . A=\sum_{\ell=1}^{L}t_\ell|D_\ell|,\qquad B=\sum_{\ell=1}^{L}t_\ell\sum_{j\in D_\ell}\frac{1-f_j}{f_j}. A = ℓ = 1 ∑ L t ℓ ∣ D ℓ ∣ , B = ℓ = 1 ∑ L t ℓ j ∈ D ℓ ∑ f j 1 − f j . We bound these two sums separately. Each term of A A A μ \mu μ s ν 2 − ℓ s\nu2^{-\ell} s ν 2 − ℓ ∣ D ℓ ∣ ≤ s |D_\ell|\le s ∣ D ℓ ∣ ≤ s k = ⌊ log 2 ( s ν / μ ) ⌋ ≥ 0 k=\lfloor\log_2(s\nu/\mu)\rfloor\ge0 k = ⌊ log 2 ( s ν / μ )⌋ ≥ 0
A ≤ ∑ ℓ ≥ 1 min { μ , s ν 2 − ℓ } ≤ k μ + ∑ ℓ = k + 1 ∞ s ν 2 − ℓ = k μ + s ν 2 − k ≤ μ [ 2 + log 2 s ν μ ] . A\le\sum_{\ell\ge1}\min\{\mu,s\nu2^{-\ell}\}\le k\mu+\sum_{\ell=k+1}^{\infty}s\nu2^{-\ell}=k\mu+s\nu2^{-k}\le\mu\left[2+\log_2\frac{s\nu}{\mu}\right]. A ≤ ℓ ≥ 1 ∑ min { μ , s ν 2 − ℓ } ≤ k μ + ℓ = k + 1 ∑ ∞ s ν 2 − ℓ = k μ + s ν 2 − k ≤ μ [ 2 + log 2 μ s ν ] . where the last inequality uses k ≤ log 2 ( s ν / μ ) k \le\log_{2}(s\nu/\mu) k ≤ log 2 ( s ν / μ ) s ν 2 − k < 2 μ s\nu2^{-k} < 2\mu s ν 2 − k < 2 μ
It remains to bound B B B P = 0 P=0 P = 0 B = 0 B=0 B = 0 P > 0 P>0 P > 0 t ∗ > 0 t^{*}>0 t ∗ > 0 t ℓ ≤ t ∗ t_{\ell}\le t^{*} t ℓ ≤ t ∗ B B B t ℓ P t_{\ell}P t ℓ P t ℓ > t ∗ t_{\ell}>t^{*} t ℓ > t ∗ a j ( ℓ ) ≤ ν a_{j}^{(\ell)}\le\nu a j ( ℓ ) ≤ ν t ℓ / f j ≤ ν t_{\ell}/f_{j}\le\nu t ℓ / f j ≤ ν j ∈ D ℓ j\in D_{\ell} j ∈ D ℓ
t ℓ ∑ j ∈ D ℓ 1 − f j f j ≤ ν ∣ D ℓ ∣ ≤ ν μ t ℓ . t_{\ell}\sum_{j\in D_{\ell}}\frac{1-f_{j}}{f_{j}}\le\nu|D_{\ell}|\le\frac{\nu\mu}{t_{\ell}}. t ℓ j ∈ D ℓ ∑ f j 1 − f j ≤ ν ∣ D ℓ ∣ ≤ t ℓ ν μ . Since the price is halved at each step, the corresponding geometric sums satisfy
∑ 1 ≤ ℓ ≤ L t ℓ ≤ t ∗ t ℓ ≤ 2 t ∗ , ∑ 1 ≤ ℓ ≤ L t ℓ > t ∗ 1 t ℓ ≤ 2 t ∗ . \sum_{\substack{1\le\ell\le L\\t_{\ell}\le t^{*}}}t_{\ell}\le2t^{*},\qquad
\sum_{\substack{1\le\ell\le L\\t_{\ell}>t^{*}}}\frac{1}{t_{\ell}}\le\frac{2}{t^{*}}. 1 ≤ ℓ ≤ L t ℓ ≤ t ∗ ∑ t ℓ ≤ 2 t ∗ , 1 ≤ ℓ ≤ L t ℓ > t ∗ ∑ t ℓ 1 ≤ t ∗ 2 . Combining the bounds for the two groups of levels gives
B ≤ 2 t ∗ P + 2 ν μ t ∗ . B\le2t^{*}P+\frac{2\nu\mu}{t^{*}}. B ≤ 2 t ∗ P + t ∗ 2 ν μ . Choosing t ∗ = ν μ / P t^{*}=\sqrt{\nu\mu/P} t ∗ = ν μ / P B ≤ 4 ν P μ B\le4\sqrt{\nu P\mu} B ≤ 4 ν P μ P = 0 P=0 P = 0 A A A 3 W / 4 ≤ A + B 3W/4\le A+B 3 W /4 ≤ A + B (15) .
Finally, the number of price levels satisfies
L = ⌈ log 2 4 ν ( s + P ) W ⌉ ≤ ⌈ log 2 ( 4 ( s + P ) ) ⌉ . L=\left\lceil\log_{2}\frac{4\nu(s+P)}{W}\right\rceil\le\left\lceil\log_{2}\bigl(4(s+P)\bigr)\right\rceil. L = ⌈ log 2 W 4 ν ( s + P ) ⌉ ≤ ⌈ log 2 ( 4 ( s + P ) ) ⌉ . Thus, the number of queries and the encodings of the prices are polynomial in the encodings of the values and weights. By the value-evaluation reduction in Appendix § 9 , we can compute W W W ν \nu ν μ ℓ = t ℓ ∣ D ℓ ∣ \mu_{\ell}=t_{\ell}|D_{\ell}| μ ℓ = t ℓ ∣ D ℓ ∣
Lemma 3.7 gives the baseline bound needed for rounding. In § 3.6 , we use it to verify (7) and obtain an O ( n ) O(\sqrt{n}) O ( n ) 128 n 2 128n^{2} 128 n 2
Subadditive rounding with at most 128 n 2 128n^{2} 128 n 2
In this subsection, we consider subadditive instances with m ≤ 128 n 2 m\le128n^{2} m ≤ 128 n 2 O ( n ) O(\sqrt{n}) O ( n ) § 3.8 .
Preparing the configuration solution. Given a feasible configuration solution with objective value T T T
κ = 2 20 ⌈ n ⌉ , τ = T / κ . \kappa=2^{20}\lceil\sqrt{n}\rceil,\qquad\tau=T/\kappa. κ = 2 20 ⌈ n ⌉ , τ = T / κ . When T = 0 T=0 T = 0 T > 0 T>0 T > 0 τ \tau τ
For each original configuration ( i , S ) (i,S) ( i , S ) u i , S ( Q ) = T v i ( Q ) / v i ( S ) u^{i,S}(Q)=Tv_{i}(Q)/v_{i}(S) u i , S ( Q ) = T v i ( Q ) / v i ( S ) Q ⊆ S Q\subseteq S Q ⊆ S v i ( S ) ≥ T v_{i}(S)\ge T v i ( S ) ≥ T u i , S ( S ) = T u^{i,S}(S)=T u i , S ( S ) = T u i , S ( Q ) ≤ v i ( Q ) u^{i,S}(Q)\le v_{i}(Q) u i , S ( Q ) ≤ v i ( Q ) Q ⊆ S Q\subseteq S Q ⊆ S u i , S u^{i,S} u i , S u i , S u^{i,S} u i , S p j p_{j} p j v i v_{i} v i S S S v i ( S ) p j / T v_{i}(S)p_{j}/T v i ( S ) p j / T § 3.4 , using u i , S ( { j } ) u^{i,S}(\{j\}) u i , S ({ j }) τ \tau τ L i L_i L i S i S_i S i y i , S y_{i,S} y i , S S ∈ S i S \in S_i S ∈ S i u i , S ( { j } ) < τ u^{i,S}(\{j\}) < \tau u i , S ({ j }) < τ j ∈ S j \in S j ∈ S
Define b j b_j b j f j = 1 − b j f_j = 1-b_j f j = 1 − b j (5) for the resulting solution. For each small configuration ( i , S ) (i,S) ( i , S ) j ∈ S j \in S j ∈ S (5) gives f j ≥ y i , S > 0 f_j \ge y_{i,S} > 0 f j ≥ y i , S > 0 Lemma 3.7 to u i , S u^{i,S} u i , S ( f j ) j ∈ S (f_j)_{j\in S} ( f j ) j ∈ S a i , S a^{i,S} a i , S μ i , S \mu_{i,S} μ i , S a i , S ( Q ) ≤ u i , S ( Q ) ≤ v i ( Q ) a^{i,S}(Q) \le u^{i,S}(Q) \le v_i(Q) a i , S ( Q ) ≤ u i , S ( Q ) ≤ v i ( Q ) Q ⊆ S Q \subseteq S Q ⊆ S a j i , S ≤ u i , S ( { j } ) < τ a_j^{i,S} \le u^{i,S}(\{j\}) < \tau a j i , S ≤ u i , S ({ j }) < τ
Bounding the contribution of a small configuration. Set H = 4 + ⌈ log 2 ( m + 1 ) ⌉ H = 4 + \lceil\log_2(m+1)\rceil H = 4 + ⌈ log 2 ( m + 1 )⌉ ( i , S ) (i,S) ( i , S )
q = μ i , S T , P ( S ) = ∑ j ∈ S b j f j = ∑ j ∈ S 1 − f j f j . q = \frac{\mu_{i,S}}{T}, \qquad P(S) = \sum_{j\in S}\frac{b_j}{f_j} = \sum_{j\in S}\frac{1-f_j}{f_j}. q = T μ i , S , P ( S ) = j ∈ S ∑ f j b j = j ∈ S ∑ f j 1 − f j . Lemma 3.7 gives μ i , S > 0 \mu_{i,S} > 0 μ i , S > 0 μ i , S ≤ a i , S ( S ) ≤ u i , S ( S ) = T \mu_{i,S} \le a^{i,S}(S) \le u^{i,S}(S) = T μ i , S ≤ a i , S ( S ) ≤ u i , S ( S ) = T 0 < q ≤ 1 0 < q \le1 0 < q ≤ 1 (15) with W = T W = T W = T s = ∣ S ∣ ≤ m s = |S| \le m s = ∣ S ∣ ≤ m ν = max j ∈ S u i , S ( { j } ) < T / κ \nu= \max_{j\in S}u^{i,S}(\{j\}) < T/\kappa ν = max j ∈ S u i , S ({ j }) < T / κ T T T
3 4 ≤ q [ 2 + log 2 s ν T q ] + 4 ν P ( S ) q T ≤ q [ 2 + log 2 m q ] + 4 P ( S ) q κ . \frac{3}{4} \le q\left[2+\log_2\frac{s\nu}{Tq}\right]+4\sqrt{\frac{\nu P(S)q}{T}} \le q\left[2+\log_2\frac{m}{q}\right]+4\sqrt{\frac{P(S)q}{\kappa}}. 4 3 ≤ q [ 2 + log 2 T q s ν ] + 4 T ν P ( S ) q ≤ q [ 2 + log 2 q m ] + 4 κ P ( S ) q . The second inequality uses ν / T < 1 / κ ≤ 1 \nu/T < 1/\kappa\le1 ν / T < 1/ κ ≤ 1 (7) , we consider two cases according to the value of q q q
Case 1: q ≥ 1 / ( 16 H ) q \ge1/(16H) q ≥ 1/ ( 16 H ) Since τ = T / κ \tau= T/\kappa τ = T / κ μ i , S = T q \mu_{i,S} = Tq μ i , S = T q
min { 1 , ( 32 τ μ i , S ) 3 } = min { 1 , ( 32 κ q ) 3 } ≤ ( 512 H κ ) 3 . \min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}
= \min\left\{1,\left(\frac{32}{\kappa q}\right)^3\right\}
\le\left(\frac{512H}{\kappa}\right)^3. min { 1 , ( μ i , S 32 τ ) 3 } = min { 1 , ( κ q 32 ) 3 } ≤ ( κ 512 H ) 3 . Case 2: q < 1 / ( 16 H ) q < 1/(16H) q < 1/ ( 16 H ) The expression q [ 2 + log 2 ( m / q ) ] q[2+\log_2(m/q)] q [ 2 + log 2 ( m / q )] q q q ( 0 , 1 ] (0,1] ( 0 , 1 ] log 2 m ≤ H − 4 \log_2 m \le H-4 log 2 m ≤ H − 4 log 2 H ≤ H \log_2 H \le H log 2 H ≤ H
q [ 2 + log 2 m q ] < 6 + log 2 m + log 2 H 16 H ≤ 2 H + 2 16 H < 3 8 . q\left[2+\log_2\frac{m}{q}\right]
< \frac{6+\log_2 m+\log_2 H}{16H}
\le\frac{2H+2}{16H}
< \frac{3}{8}. q [ 2 + log 2 q m ] < 16 H 6 + log 2 m + log 2 H ≤ 16 H 2 H + 2 < 8 3 . Consequently, 4 P ( S ) q / κ ≥ 3 / 8 4\sqrt{P(S)q/\kappa} \ge3/8 4 P ( S ) q / κ ≥ 3/8 P ( S ) > 0 P(S) > 0 P ( S ) > 0
q ≥ 9 κ 1024 P ( S ) . q \ge\frac{9\kappa}{1024P(S)}. q ≥ 1024 P ( S ) 9 κ . It follows that
min { 1 , ( 32 τ μ i , S ) 3 } = min { 1 , ( 32 κ q ) 3 } ≤ min { 1 , ( 32768 P ( S ) 9 κ 2 ) 3 } ≤ 32768 P ( S ) 9 κ 2 , \min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}
= \min\left\{1,\left(\frac{32}{\kappa q}\right)^3\right\}
\le\min\left\{1,\left(\frac{32768P(S)}{9\kappa^2}\right)^3\right\}
\le\frac{32768P(S)}{9\kappa^2}, min { 1 , ( μ i , S 32 τ ) 3 } = min { 1 , ( κ q 32 ) 3 } ≤ min { 1 , ( 9 κ 2 32768 P ( S ) ) 3 } ≤ 9 κ 2 32768 P ( S ) , where the last inequality uses min { 1 , x 3 } ≤ x \min\{1,x^3\} \le x min { 1 , x 3 } ≤ x x ≥ 0 x \ge0 x ≥ 0
Verifying the budget condition. By (2) , the total mass of small configurations is at most n n n (14) uses only (2) and (3) , so it also applies to the present solution. Thus,
∑ i ∑ S ∈ S i y i , S ≤ n , ∑ i ∑ S ∈ S i y i , S P ( S ) ≤ n . \sum_i \sum_{S\in S_i} y_{i,S} \le n,\qquad\sum_i \sum_{S\in S_i} y_{i,S}P(S) \le n. i ∑ S ∈ S i ∑ y i , S ≤ n , i ∑ S ∈ S i ∑ y i , S P ( S ) ≤ n . We apply the appropriate bound from the two cases to each small configuration and sum with weights y i , S y_{i,S} y i , S
∑ i ∑ S ∈ S i y i , S min { 1 , ( 32 τ μ i , S ) 3 } ≤ ( 512 H κ ) 3 ∑ i ∑ S ∈ S i y i , S + 32768 9 κ 2 ∑ i ∑ S ∈ S i y i , S P ( S ) ≤ n ( 512 H / κ ) 3 + 32768 n 9 κ 2 . (16) \begin{aligned}
\sum_i \sum_{S\in S_i} y_{i,S}\min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}
\le\left(\frac{512H}{\kappa}\right)^3\sum_i\sum_{S\in S_i}y_{i,S}
+\frac{32768}{9\kappa^2}\sum_i\sum_{S\in S_i}y_{i,S}P(S) \\
&\le n(512H/\kappa)^3+\frac{32768n}{9\kappa^2}. \tag*{(16)}
\end{aligned} i ∑ S ∈ S i ∑ y i , S min { 1 , ( μ i , S 32 τ ) 3 } ≤ ( κ 512 H ) 3 i ∑ S ∈ S i ∑ y i , S + 9 κ 2 32768 i ∑ S ∈ S i ∑ y i , S P ( S ) ≤ n ( 512 H / κ ) 3 + 9 κ 2 32768 n . (16) Since m ≤ 128 n 2 m\le128n^2 m ≤ 128 n 2 H ≤ 13 + 2 log 2 n ≤ 32 n 1 / 6 H\le13+2\log_2 n\le32n^{1/6} H ≤ 13 + 2 log 2 n ≤ 32 n 1/6 κ ≥ 2 20 n \kappa\ge2^{20}\sqrt{n} κ ≥ 2 20 n
n ( 512 H / κ ) 3 + 32768 n 9 κ 2 ≤ 2 − 18 + 1 9 ⋅ 2 25 < 1 128 . n(512H/\kappa)^3+\frac{32768n}{9\kappa^2}\le2^{-18}+\frac{1}{9\cdot2^{25}}<\frac{1}{128}. n ( 512 H / κ ) 3 + 9 κ 2 32768 n ≤ 2 − 18 + 9 ⋅ 2 25 1 < 128 1 . Thus (7) holds with 1 / 128 1/128 1/128 1 / 4 1/4 1/4 § 3.8 , as stated in Corollary 3.8 below.
Empty configurations. § 3.8 applies the following corollary to configuration solutions in which agents may have the empty configuration, so we first extend Lemma 3.1 to such solutions. We treat ∅ \emptyset ∅ u i , ∅ u_{i,\emptyset} u i , ∅ a i , ∅ a_{i,\emptyset} a i , ∅ (7) , and require a i S i ( A i ) ≥ τ a_i^{S_i}(A_i)\ge\tau a i S i ( A i ) ≥ τ S i ≠ ∅ S_i\ne\emptyset S i = ∅
The matching construction represents ∅ \emptyset ∅ u i , ∅ u_{i,\emptyset} u i , ∅ S i = ∅ S_i=\emptyset S i = ∅ A i = ∅ A_i=\emptyset A i = ∅ i i i C j C_j C j Lemma 3.3 for a nonempty small configuration S S S a ( S ∩ ∅ ) = 0 a(S\cap\emptyset)=0 a ( S ∩ ∅ ) = 0 c i , ∅ ′ = 0 c_{i,\emptyset}'=0 c i , ∅ ′ = 0 Y Y Y
Although μ i , ∅ = 0 \mu_{i,\emptyset}=0 μ i , ∅ = 0 ∅ \emptyset ∅
Pr [ ∃ i ∈ N : S i ≠ ∅ and a i S i ( A i ) < τ ] ≤ ∑ i ∈ N ∑ S ∈ S i S ≠ ∅ y i , S min { 1 , ( 32 τ μ i , S ) 3 } . \Pr\left[\exists i\in N:S_i\ne\emptyset\text{ and }a_i^{S_i}(A_i)<\tau\right]
\le\sum_{i\in N}\sum_{\substack{S\in S_i\\S\ne\emptyset}}y_{i,S}\min\left\{1,\left(\frac{32\tau}{\mu_{i,S}}\right)^3\right\}. Pr [ ∃ i ∈ N : S i = ∅ and a i S i ( A i ) < τ ] ≤ i ∈ N ∑ S ∈ S i S = ∅ ∑ y i , S min { 1 , ( μ i , S 32 τ ) 3 } . which is the left side of (7) with the empty configurations omitted.
Corollary 3.8. Suppose m ≤ 128 n 2 m\le128n^2 m ≤ 128 n 2 T T T 127 / 128 127/128 127/128 T / κ T/\kappa T / κ
Proof. Apply the rounding procedure of Lemma 3.1 to the solution constructed above, and recover the original configurations using the proportional rule of § 3.2 . This preserves their prescribed marginals without changing the allocation.
Since the constructed coefficients are dominated by the valuations, (10) , (16) , and the union bound imply that the probability of any agent receiving value less than T / κ T/\kappa T / κ 1 / 128 1/128 1/128
When empty configurations are present, the extension above leaves the estimates for nonempty configurations unchanged, and the union bound includes only nonempty configurations.
Sampling and rounding tools
In this subsection and the next one, we design the O ( n ) O(\sqrt{n}) O ( n ) § 3.8 . Lemma 3.9 gives a value guarantee for independent item sampling when singleton values are sufficiently small. Lemma 3.10 provides a conditional version of Feige’s guiding-tree rounding [28 ] . Lemma 3.11 combines independent runs of the rounding procedure in Lemma 3.10 with a random coloring of the items to obtain an exponential bound on each agent’s failure probability.
Feige and Huang [32 ] , building on Seddighin and Seddighin [58 ] , combined independent trials of Feige’s welfare rounding [28 ] with random per-item contention resolution for maximin shares. We use their independent-sampling bound and adapt the repeated rounding to arbitrary feasible configuration solutions. We condition on the configuration chosen by each agent and assign each item to a random trial. This gives a failure bound that depends on the agent’s total nonempty configuration mass.
Independent sampling. Let v v v ν \nu ν Q Q Q ξ = v ( Q ) \xi= v(Q) ξ = v ( Q ) [32 Lemma 3.1] holds with constant ν \nu ν a a a
Pr [ ξ > 2 a + k ν ] Pr [ ξ ≤ a ] 2 ≤ 2 − k ( a > 0 , k ∈ Z ≥ 0 ) . (17) \Pr[\xi> 2a + k\nu]\Pr[\xi\le a]^2 \le2^{-k} \qquad(a > 0,\ k \in\mathbb{Z}_{\ge0}). \tag*{(17)} Pr [ ξ > 2 a + k ν ] Pr [ ξ ≤ a ] 2 ≤ 2 − k ( a > 0 , k ∈ Z ≥ 0 ) . (17) Lemma 3.9. Let v v v S S S v ( S ) = W > 0 v(S) = W > 0 v ( S ) = W > 0 h ≥ 1 h \ge1 h ≥ 1 v ( { j } ) ≤ W / ( 8 h ) v(\{j\}) \le W/(8h) v ({ j }) ≤ W / ( 8 h ) j ∈ S j \in S j ∈ S Q ⊆ S Q \subseteq S Q ⊆ S 1 / h 1/h 1/ h
Pr [ v ( Q ) ≥ W 4 h ] ≥ 1 2 . \Pr\left[v(Q) \ge\frac{W}{4h}\right] \ge\frac{1}{2}. Pr [ v ( Q ) ≥ 4 h W ] ≥ 2 1 . Proof. Apply Feige and Huang [32 Lemma 2.2] with t = h t = h t = h 8 W / ( 23 h ) 8W/(23h) 8 W / ( 23 h ) W / ( 8 h ) W/(8h) W / ( 8 h ) 1 / 2 1/2 1/2 8 W / ( 23 h ) ≥ W / ( 4 h ) 8W/(23h) \ge W/(4h) 8 W / ( 23 h ) ≥ W / ( 4 h )
Conditional guiding-tree rounding. Feige [28 ] orients the components of a randomly labeled guiding graph and compares the bundles at the two endpoints of an edge with a fixed label. We apply this endpoint argument on a tree. The item-mass bound of 1 / 2 1/2 1/2
Lemma 3.10. Let ( v i ) i ∈ N (v_i)_{i\in N} ( v i ) i ∈ N i i i S S S y i , S y_{i,S} y i , S
∑ i ∈ N ∑ S ∋ j y i , S ≤ 1 2 ( j ∈ M ) . \sum_{i\in N}\sum_{S\ni j} y_{i,S} \le\frac{1}{2} \qquad(j \in M). i ∈ N ∑ S ∋ j ∑ y i , S ≤ 2 1 ( j ∈ M ) . Then there is a randomized guiding-tree rounding procedure that selects configurations S i S_i S i Pr [ S i = S ] = y i , S \Pr[S_i = S] = y_{i,S} Pr [ S i = S ] = y i , S G G G G i ⊆ S i G_i \subseteq S_i G i ⊆ S i i ∈ N i \in N i ∈ N S S S y i , S > 0 y_{i,S} > 0 y i , S > 0
Pr [ v i ( G i ) ≥ v i ( S ) / 2 ∣ S i = S ] ≥ 1 / 4. \Pr[v_i(G_i) \ge v_i(S)/2 \mid S_i = S] \ge1/4. Pr [ v i ( G i ) ≥ v i ( S ) /2 ∣ S i = S ] ≥ 1/4. The procedure uses no valuation queries and requires only polynomially many combinatorial operations and sampling calls.
Proof. If there is only one agent, sample its configuration and assign it all items in that configuration. The claim then holds with probability 1, henceforth assume n ≥ 2 n \ge2 n ≥ 2 1 / 2 1/2 1/2
The labeled tree. Consider an infinite tree in which every vertex has exactly one incident edge of color i i i i ∈ N i \in N i ∈ N r r r i i i S S S y i , S y_{i,S} y i , S S i S_i S i i i i Pr [ S i = S ] = y i , S \Pr[S_i = S] = y_{i,S} Pr [ S i = S ] = y i , S
For each item j j j j j j i i i ∑ S ∋ j y i , S \sum_{S \ni j} y_{i,S} ∑ S ∋ j y i , S j j j ∑ i ∈ N ∑ S ∋ j y i , S \sum_{i \in N} \sum_{S \ni j} y_{i,S} ∑ i ∈ N ∑ S ∋ j y i , S 1 / 2 1/2 1/2 1 / 2 1/2 1/2 ∑ d ≥ 0 2 − d = 2 \sum_{d \ge0} 2^{-d} = 2 ∑ d ≥ 0 2 − d = 2 r r r j j j
The allocation rule. A finite tree has either a central vertex or a central edge, given by the middle of a longest path. Orient the edges of each retained component away from its center. If the center is an edge, orient that edge in both directions. Every edge then points toward at least one endpoint, and every vertex has at most one incoming edge.
For each vertex w w w i i i i i i w w w j j j G ^ i ( w ) \widehat{G}_i(w) G i ( w ) j j j w w w j j j w w w w w w i i i S i S_i S i G ^ i ( r ) ⊆ S i \widehat{G}_i(r) \subseteq S_i G i ( r ) ⊆ S i G ^ i ( r ) \widehat{G}_i(r) G i ( r )
The allocation rule and the endpoint comparison below are illustrated in Figure 1 .
Figure 1. Guiding-tree rounding and the endpoint argument in Lemma 3.10, following Feige [28 ] . Vertices are auxiliary tree positions; edge colors identify agents. (a) For a fixed item j j j r r r j j j S i = S S_i = S S i = S i i i S S S r r r
The conditional value guarantee. Fix an agent i i i S S S y i , S > 0 y_{i,S} > 0 y i , S > 0 S i = S S_i = S S i = S r i r_i r i i i i j ∈ S j \in S j ∈ S r r r r i r_i r i G ^ i ( r ) ∪ G ^ i ( r i ) = S \widehat{G}_i(r) \cup\widehat{G}_i(r_i) = S G i ( r ) ∪ G i ( r i ) = S
v i ( G ^ i ( r ) ) + v i ( G ^ i ( r i ) ) ≥ v i ( S ) . v_i(\widehat{G}_i(r)) + v_i(\widehat{G}_i(r_i)) \ge v_i(S). v i ( G i ( r )) + v i ( G i ( r i )) ≥ v i ( S ) . Hence at least one of these two bundles has value at least v i ( S ) / 2 v_i(S)/2 v i ( S ) /2
The two sides of the edge { r , r i } \{r,r_i\} { r , r i } r r r r i r_i r i S S S G ^ i ( r ) \widehat{G}_i(r) G i ( r ) G ^ i ( r i ) \widehat{G}_i(r_i) G i ( r i ) v i ( S ) / 2 v_i(S)/2 v i ( S ) /2
Pr [ v i ( G ^ i ( r ) ) ≥ v i ( S ) / 2 ∣ S i = S ] ≥ 1 / 2. \Pr[v_i(\widehat{G}_i(r)) \ge v_i(S)/2 \mid S_i = S] \ge1/2. Pr [ v i ( G i ( r )) ≥ v i ( S ) /2 ∣ S i = S ] ≥ 1/2. Bounding the number of operations. We first sample the labels of all edges incident to the root r r r j j j r r r
We count both combinatorial operations and sampling calls. Conditional on S i = S S_i = S S i = S { r , r i } \{r,r_i\} { r , r i } j ∈ S j \in S j ∈ S r r r j ∉ S j \notin S j ∈ / S r r r
Over all m m m 4 m 4m 4 m n n n ω \omega ω i i i S S S y i , S > 0 y_{i,S} > 0 y i , S > 0
We stop the exploration after 4 ω 4\omega 4 ω G i = ∅ G_i = \varnothing G i = ∅ S i S_i S i G i = G ^ i ( r ) G_i = \widehat{G}_i(r) G i = G i ( r ) 1 / 4 1/4 1/4 1 / 2 1/2 1/2
Pr [ v i ( G i ) ≥ v i ( S ) / 2 ∣ S i = S ] ≥ 1 2 − 1 4 = 1 4 . \Pr[v_i(G_i) \ge v_i(S)/2 \mid S_i = S] \ge\frac{1}{2} - \frac{1}{4} = \frac{1}{4}. Pr [ v i ( G i ) ≥ v i ( S ) /2 ∣ S i = S ] ≥ 2 1 − 4 1 = 4 1 . Lemma 3.11. Let V > 0 V > 0 V > 0 h ≥ 1 h \ge1 h ≥ 1 i i i r i r_i r i
with the remaining mass 1 − r i 1-r_i 1 − r i i i i S S S i i i v i ( S ) ≥ V v_i(S) \ge V v i ( S ) ≥ V v i ( { j } ) ≤ V / ( 16 h ) v_i(\{j\}) \le V/(16h) v i ({ j }) ≤ V / ( 16 h ) j ∈ S j \in S j ∈ S G ˉ \bar{G} G ˉ i ∈ N i \in N i ∈ N
Pr [ v i ( G ˉ i ) < V / ( 8 h ) ] ≤ e − h r i / 16 . \Pr[v_i(\bar{G}_i) < V/(8h)] \le e^{-hr_i/16}. Pr [ v i ( G ˉ i ) < V / ( 8 h )] ≤ e − h r i /16 . Proof. Constructing the allocation. We halve the mass of every configuration and add mass 1 / 2 1/2 1/2 1 1 1 1 / 2 1/2 1/2 h h h G 1 , … , G h G^1,\ldots,G^h G 1 , … , G h
Independently of these runs, assign each item an independent uniformly random color in { 1 , … , h } \{1,\ldots,h\} { 1 , … , h } M ℓ M_\ell M ℓ ℓ \ell ℓ i i i G ˉ i = ⋃ ℓ = 1 h ( G i ℓ ∩ M ℓ ) \bar{G}_i=\bigcup_{\ell=1}^{h}(G_i^\ell\cap M_\ell) G ˉ i = ⋃ ℓ = 1 h ( G i ℓ ∩ M ℓ ) G ℓ G^\ell G ℓ G ˉ \bar{G} G ˉ
Success in one run. Fix an agent i i i ℓ \ell ℓ i i i r i / 2 r_i/2 r i /2 V V V v i ( G i ℓ ) ≥ V / 2 v_i(G_i^\ell) \ge V/2 v i ( G i ℓ ) ≥ V /2 ( r i / 2 ) ( 1 / 4 ) = r i / 8 (r_i/2)(1/4)=r_i/8 ( r i /2 ) ( 1/4 ) = r i /8
Now fix an output with W = v i ( G i ℓ ) ≥ V / 2 W=v_i(G_i^\ell) \ge V/2 W = v i ( G i ℓ ) ≥ V /2 G i ℓ G_i^\ell G i ℓ V / ( 16 h ) ≤ W / ( 8 h ) V/(16h) \le W/(8h) V / ( 16 h ) ≤ W / ( 8 h ) M ℓ M_\ell M ℓ 1 / h 1/h 1/ h 1 / 2 1/2 1/2 v i ( G i ℓ ∩ M ℓ ) ≥ W / ( 4 h ) ≥ V / ( 8 h ) v_i(G_i^\ell\cap M_\ell) \ge W/(4h) \ge V/(8h) v i ( G i ℓ ∩ M ℓ ) ≥ W / ( 4 h ) ≥ V / ( 8 h )
Pr [ v i ( G i ℓ ∩ M ℓ ) ≥ V / ( 8 h ) ] ≥ r i 8 ⋅ 1 2 = r i 16 . \Pr[v_i(G_i^\ell\cap M_\ell) \ge V/(8h)] \ge\frac{r_i}{8}\cdot\frac{1}{2}=\frac{r_i}{16}. Pr [ v i ( G i ℓ ∩ M ℓ ) ≥ V / ( 8 h )] ≥ 8 r i ⋅ 2 1 = 16 r i . Combining the runs. Let g ℓ g_\ell g ℓ v i ( G i ℓ ∩ M ℓ ) < V / ( 8 h ) v_i(G_i^\ell\cap M_\ell) < V/(8h) v i ( G i ℓ ∩ M ℓ ) < V / ( 8 h ) E [ g ℓ ] ≤ 1 − r i / 16 \mathbb{E}[g_\ell] \le1-r_i/16 E [ g ℓ ] ≤ 1 − r i /16 E [ ∏ ℓ = 1 h g ℓ ] ≤ ∏ ℓ = 1 h E [ g ℓ ] \mathbb{E}[\prod_{\ell=1}^{h}g_\ell] \le\prod_{\ell=1}^{h}\mathbb{E}[g_\ell] E [ ∏ ℓ = 1 h g ℓ ] ≤ ∏ ℓ = 1 h E [ g ℓ ]
Fix G 1 , … , G h G^1,\ldots,G^h G 1 , … , G h j j j ( 1 { j ∈ M ℓ } ) ℓ = 1 h (\mathbf{1}_{\{j\in M_\ell\}})_{\ell=1}^{h} ( 1 { j ∈ M ℓ } ) ℓ = 1 h [44 ] . Each g ℓ g_\ell g ℓ ℓ \ell ℓ g ℓ g_\ell g ℓ
E [ ∏ ℓ = 1 h g ℓ | G 1 , … , G h ] ≤ ∏ ℓ = 1 h E [ g ℓ ∣ G ℓ ] . \mathbb{E}\left[\prod_{\ell=1}^{h}g_\ell\,\middle|\, G^1,\ldots,G^h\right]
\le\prod_{\ell=1}^{h}\mathbb{E}[g_\ell\mid G^\ell]. E [ ℓ = 1 ∏ h g ℓ G 1 , … , G h ] ≤ ℓ = 1 ∏ h E [ g ℓ ∣ G ℓ ] . Each factor on the right depends only on G ℓ G^\ell G ℓ E [ ∏ ℓ = 1 h g ℓ ] ≤ ∏ ℓ = 1 h E [ g ℓ ] \mathbb{E}[\prod_{\ell=1}^{h}g_\ell] \le\prod_{\ell=1}^{h}\mathbb{E}[g_\ell] E [ ∏ ℓ = 1 h g ℓ ] ≤ ∏ ℓ = 1 h E [ g ℓ ]
Finally, G ˉ i \bar{G}_i G ˉ i G i ℓ ∩ M ℓ G_i^\ell\cap M_\ell G i ℓ ∩ M ℓ ℓ \ell ℓ v i ( G ˉ i ) < V / ( 8 h ) v_i(\bar{G}_i) < V/(8h) v i ( G ˉ i ) < V / ( 8 h )
Pr [ v i ( G ˉ i ) < V / ( 8 h ) ] ≤ E [ ∏ ℓ = 1 h g ℓ ] ≤ ∏ ℓ = 1 h E [ g ℓ ] ≤ ( 1 − r i / 16 ) h ≤ e − h r i / 16 . \Pr[v_i(\bar{G}_i) < V/(8h)]
\le\mathbb{E}\left[\prod_{\ell=1}^{h}g_\ell\right]
\le\prod_{\ell=1}^{h}\mathbb{E}[g_\ell]
\le(1-r_i/16)^h
\le e^{-hr_i/16}. Pr [ v i ( G ˉ i ) < V / ( 8 h )] ≤ E [ ℓ = 1 ∏ h g ℓ ] ≤ ℓ = 1 ∏ h E [ g ℓ ] ≤ ( 1 − r i /16 ) h ≤ e − h r i /16 . Subadditive rounding with arbitrarily many items
We now extend Corollary 3.8 to an arbitrary number of items and prove Theorem 3.12 . For larger instances, we construct a core K K K 128 n 2 128n^2 128 n 2 K K K K K K § 3.7 . The other part is reserved for the few agents whose allocation outside K K K
Core construction and backup selection. By Lemma 3.4 , we obtain a configuration solution with objective value T > T L P / 6 T > T_{\mathrm{LP}}/6 T > T LP /6 κ = 2 20 ⌈ n ⌉ \kappa= 2^{20}\lceil\sqrt{n}\rceil κ = 2 20 ⌈ n ⌉ m < 128 n 2 m < 128n^2 m < 128 n 2 m ≥ 128 n 2 m \ge128n^2 m ≥ 128 n 2
We construct the core in 128 n 128n 128 n K t K_t K t n n n t t t
K = ⋃ t = 1 128 n K t , K ‾ = M ∖ K . K = \bigcup_{t=1}^{128n} K_t,\qquad\overline{K} = M \setminus K. K = t = 1 ⋃ 128 n K t , K = M ∖ K . Since no item is chosen twice, we have ∣ K ∣ = 128 n 2 |K| = 128n^2 ∣ K ∣ = 128 n 2
Choose J J J { 1 , … , 128 n } \{1,\ldots,128n\} { 1 , … , 128 n } B = K J B = K_J B = K J i i i j i j_i j i J J J K ‾ \overline{K} K i i i j i j_i j i
v i ( { j i } ) ≥ max j ∈ K ‾ v i ( { j } ) . (18) v_i(\{j_i\}) \ge\max_{j\in\overline{K}} v_i(\{j\}). \tag*{(18)} v i ({ j i }) ≥ j ∈ K max v i ({ j }) . (18) For any fixed agent i i i S ⊆ M S \subseteq M S ⊆ M
Pr [ v i ( S ∖ B ) < v i ( S ) / 2 ] ≤ 1 / ( 128 n ) . (19) \Pr[v_i(S \setminus B) < v_i(S)/2] \le1/(128n). \tag*{(19)} Pr [ v i ( S ∖ B ) < v i ( S ) /2 ] ≤ 1/ ( 128 n ) . (19) To see this, consider two distinct rounds s s s t t t K s K_s K s K t K_t K t ( S ∖ K s ) ∪ ( S ∖ K t ) = S (S \setminus K_s)\cup(S \setminus K_t) = S ( S ∖ K s ) ∪ ( S ∖ K t ) = S
v i ( S ) ≤ v i ( S ∖ K s ) + v i ( S ∖ K t ) . v_i(S) \le v_i(S \setminus K_s) + v_i(S \setminus K_t). v i ( S ) ≤ v i ( S ∖ K s ) + v i ( S ∖ K t ) . Thus, at most one round t t t v i ( S ∖ K t ) < v i ( S ) / 2 v_i(S \setminus K_t) < v_i(S)/2 v i ( S ∖ K t ) < v i ( S ) /2 J J J 128 n 128n 128 n
The allocation algorithm. We set
τ = T 4096 κ , V = T 64 = 64 κ τ , N 0 = { i : v i ( { j i } ) < τ } . \tau= \frac{T}{4096\kappa},\qquad V = \frac{T}{64} = 64\kappa\tau,\qquad N_0 = \{i : v_i(\{j_i\}) < \tau\}. τ = 4096 κ T , V = 64 T = 64 κ τ , N 0 = { i : v i ({ j i }) < τ } . Here, N 0 N_0 N 0 τ \tau τ K ‾ \overline{K} K τ \tau τ N 0 N_0 N 0 B B B K ∖ B K \setminus B K ∖ B R 1 R_1 R 1 R 2 R_2 R 2 R 1 R_1 R 1 R 2 R_2 R 2 K ‾ \overline{K} K
Every agent i ∉ N 0 i \notin N_0 i ∈ / N 0 j i j_i j i
For each original configuration ( i , S ) (i,S) ( i , S ) i ∈ N 0 i \in N_0 i ∈ N 0 S K = S ∩ K S_K = S \cap K S K = S ∩ K S K ‾ = S ∩ K ‾ S_{\overline{K}} = S \cap\overline{K} S K = S ∩ K ( i , S ) (i,S) ( i , S ) v i ( S K ) ≥ T / 2 v_i(S_K) \ge T/2 v i ( S K ) ≥ T /2 v i ( S K ‾ ) > T / 2 v_i(S_{\overline{K}}) > T/2 v i ( S K ) > T /2 r i r_i r i i i i
We construct a configuration solution on K ∖ B K \setminus B K ∖ B i ∈ N 0 i \in N_0 i ∈ N 0 S S S S K ∖ B S_{K} \setminus B S K ∖ B v i ( S K ∖ B ) ≥ v i ( S K ) / 2 v_i(S_{K} \setminus B) \ge v_i(S_{K})/2 v i ( S K ∖ B ) ≥ v i ( S K ) /2 N 0 N_0 N 0 § 3.2 .
We run the rounding procedure of Corollary 3.8 once on this solution with objective value T / 4 T/4 T /4 K ∖ B K \setminus B K ∖ B i i i S i S_i S i i ∈ N 0 i \in N_0 i ∈ N 0 S i S_i S i S i S_i S i
We independently assign each item of K ‾ \overline{K} K R 1 R_1 R 1 R 2 R_2 R 2 1 / 2 1/2 1/2 R 1 R_1 R 1 ( i , S ) (i,S) ( i , S ) i ∈ N 0 i \in N_0 i ∈ N 0 S ∩ R 1 S \cap R_1 S ∩ R 1 v i ( S ∩ R 1 ) ≥ V v_i(S \cap R_1) \ge V v i ( S ∩ R 1 ) ≥ V
Using randomness independent of that used in Step 4, we apply Lemma 3.11 to the solution from Step 5 with h = κ h = \kappa h = κ G ‾ \overline{G} G R 1 R_1 R 1 i ∈ N 0 i \in N_0 i ∈ N 0 S i S_i S i v i ( G ‾ i ) ≥ τ v_i(\overline{G}_i) \ge\tau v i ( G i ) ≥ τ i i i G ‾ i \overline{G}_i G i i i i Q Q Q ∣ Q ∣ ≤ κ |Q| \le\kappa ∣ Q ∣ ≤ κ R 2 R_2 R 2
We combine the bundles assigned in Steps 1, 4 and 6, including those supplied by the reserve repair. If every agent receives value at least τ \tau τ
Bounding the queue and allocating the reserve. For every fixed B B B i ∈ N 0 i \in N_0 i ∈ N 0 r i r_i r i N 0 N_0 N 0
Fix an original configuration ( i , S ) (i,S) ( i , S ) v i ( S ∩ K ) ≥ T / 2 v_i(S \cap K) \ge T/2 v i ( S ∩ K ) ≥ T /2 i ∈ N 0 i \in N_0 i ∈ N 0 v i ( ( S ∩ K ) ∖ B ) < v i ( S ∩ K ) / 2 v_i((S \cap K) \setminus B) < v_i(S \cap K)/2 v i (( S ∩ K ) ∖ B ) < v i ( S ∩ K ) /2 (19) , the probability of this event over the choice of B B B 1 / ( 128 n ) 1/(128n) 1/ ( 128 n ) Pr [ S i = S ∣ B ] = y i , S \Pr[S_i = S \mid B] = y_{i,S} Pr [ S i = S ∣ B ] = y i , S B B B i ∈ N 0 i \in N_0 i ∈ N 0 y i , S / ( 128 n ) y_{i,S}/(128n) y i , S / ( 128 n )
1 128 n ∑ i ∈ N ∑ S y i , S = 1 128 . \frac{1}{128n}\sum_{i\in N}\sum_{S} y_{i,S}=\frac{1}{128}. 128 n 1 i ∈ N ∑ S ∑ y i , S = 128 1 . Here, we extended the sum to all original configurations and used (2) .
We next analyze the random partition. Fix B B B N 0 N_0 N 0 K ‾ \overline{K} K τ \tau τ N 0 N_0 N 0 i ∈ N 0 i \in N_0 i ∈ N 0 r i ′ ≤ r i r'_i \le r_i r i ′ ≤ r i
Δ = ∑ i ∈ N 0 ( r i − r i ′ ) , ϵ s = 2 1 − 32 κ . \Delta=\sum_{i\in N_0}(r_i-r'_i),\qquad\epsilon_s=2^{1-32\kappa}. Δ = i ∈ N 0 ∑ ( r i − r i ′ ) , ϵ s = 2 1 − 32 κ . Thus, Δ \Delta Δ R 1 R_1 R 1 V V V R 2 R_2 R 2 V V V
E [ Δ ∣ B ] ≤ n ϵ s , Pr [ ∃ i ∈ N 0 : r i > 0 , v i ( R 2 ) < V ∣ B ] ≤ n ϵ s . (20) \mathbb{E}[\Delta\mid B] \le n\epsilon_s,\qquad\Pr[\exists i \in N_0 : r_i > 0,\ v_i(R_2) < V \mid B] \le n\epsilon_s. \tag*{(20)} E [ Δ ∣ B ] ≤ n ϵ s , Pr [ ∃ i ∈ N 0 : r i > 0 , v i ( R 2 ) < V ∣ B ] ≤ n ϵ s . (20) To establish both bounds, fix i ∈ N 0 i \in N_0 i ∈ N 0 Q ⊆ K ‾ Q \subseteq\overline{K} Q ⊆ K v i ( Q ) = W > T / 2 v_i(Q) = W > T/2 v i ( Q ) = W > T /2
v i ( Q ∩ R 1 ) + v i ( Q ∩ R 2 ) ≥ W . v_i(Q \cap R_1) + v_i(Q \cap R_2) \ge W. v i ( Q ∩ R 1 ) + v i ( Q ∩ R 2 ) ≥ W . At least one of the two values is therefore at least W / 2 W/2 W /2 W / 2 W/2 W /2 1 / 2 1/2 1/2 ℓ ∈ { 1 , 2 } \ell\in\{1,2\} ℓ ∈ { 1 , 2 } ξ = v i ( Q ∩ R ℓ ) \xi= v_i(Q \cap R_\ell) ξ = v i ( Q ∩ R ℓ ) (17) with a = V = T / 64 a = V = T/64 a = V = T /64 k = 64 κ k = 64\kappa k = 64 κ τ \tau τ
Pr [ ξ > 2 V + 64 κ τ ∣ B ] Pr [ ξ ≤ V ∣ B ] 2 ≤ 2 − 64 κ . \Pr[\xi> 2V + 64\kappa\tau\mid B]\Pr[\xi\le V \mid B]^2 \le2^{-64\kappa}. Pr [ ξ > 2 V + 64 κ τ ∣ B ] Pr [ ξ ≤ V ∣ B ] 2 ≤ 2 − 64 κ . Since 2 V + 64 κ τ = 3 T / 64 < W / 2 2V + 64\kappa\tau= 3T/64 < W/2 2 V + 64 κ τ = 3 T /64 < W /2 1 / 2 1/2 1/2
Pr [ v i ( Q ∩ R ℓ ) < V ∣ B ] ≤ 2 2 − 32 κ ≤ ϵ s ( ℓ = 1 , 2 ) . \Pr[v_i(Q \cap R_\ell) < V \mid B] \le\sqrt{2}2^{-32\kappa} \le\epsilon_s \qquad(\ell= 1,2). Pr [ v i ( Q ∩ R ℓ ) < V ∣ B ] ≤ 2 2 − 32 κ ≤ ϵ s ( ℓ = 1 , 2 ) . For the first bound in (20) , apply this estimate to Q = S K ‾ Q = S_{\overline{K}} Q = S K ( i , S ) (i,S) ( i , S ) S ∩ R 1 = S K ‾ ∩ R 1 S \cap R_1 = S_{\overline{K}} \cap R_1 S ∩ R 1 = S K ∩ R 1
E [ r i − r i ′ ∣ B ] = ∑ S : ( i , S ) is residual-type y i , S Pr [ v i ( S ∩ R 1 ) < V ∣ B ] ≤ r i ϵ s ≤ ϵ s . \mathbb{E}[r_i-r'_i \mid B]
=
\sum_{S:\ (i,S)\ \text{is residual-type}} y_{i,S}\Pr[v_i(S \cap R_1) < V \mid B]
\le r_i\epsilon_s \le\epsilon_s. E [ r i − r i ′ ∣ B ] = S : ( i , S ) is residual-type ∑ y i , S Pr [ v i ( S ∩ R 1 ) < V ∣ B ] ≤ r i ϵ s ≤ ϵ s . Summing over i ∈ N 0 i \in N_0 i ∈ N 0 E [ Δ ∣ B ] ≤ n ϵ s \mathbb{E}[\Delta\mid B] \le n\epsilon_s E [ Δ ∣ B ] ≤ n ϵ s r i > 0 r_i > 0 r i > 0 i i i v i ( K ‾ ) > T / 2 v_i(\overline{K}) > T/2 v i ( K ) > T /2 Q = K ‾ Q = \overline{K} Q = K ℓ = 2 \ell= 2 ℓ = 2
We now bound the number of agents entering the queue. To do so, we first check that Lemma 3.11 applies in Step 6. The solution constructed in Step 5 is feasible: replacing configurations by subsets preserves (2) and cannot increase the total mass on any item, and merging identical sets preserves both. Every nonempty configuration has value at least V V V τ = V / ( 64 κ ) < V / ( 16 κ ) \tau= V/(64\kappa) < V/(16\kappa) τ = V / ( 64 κ ) < V / ( 16 κ ) h = κ h = \kappa h = κ r i ′ r'_i r i ′ i i i V / ( 8 κ ) = 8 τ V/(8\kappa) = 8\tau V / ( 8 κ ) = 8 τ
Pr [ v i ( G ‾ i ) < τ ∣ B , R 1 , R 2 ] ≤ e − κ r i ′ / 16 . \Pr[v_i(\overline{G}_i) < \tau\mid B,R_1,R_2] \le e^{-\kappa r'_i/16}. Pr [ v i ( G i ) < τ ∣ B , R 1 , R 2 ] ≤ e − κ r i ′ /16 . An agent i ∈ N 0 i \in N_0 i ∈ N 0 Q Q Q S i S_i S i v i ( G ‾ i ) < τ v_i(\overline{G}_i) < \tau v i ( G i ) < τ ( B , R 1 , R 2 ) (B,R_1,R_2) ( B , R 1 , R 2 ) r i r_i r i
E [ ∣ Q ∣ ∣ B , R 1 , R 2 ] = ∑ i ∈ N 0 r i Pr [ v i ( G ‾ i ) < τ ∣ B , R 1 , R 2 ] ≤ ∑ i ∈ N 0 r i e − κ r i ′ / 16 ≤ ∑ i ∈ N 0 r i ′ e − κ r i ′ / 16 + Δ ≤ 16 n e κ + Δ . \begin{aligned}
\mathbb{E}[|Q| \mid B,R_1,R_2]
=
\sum_{i \in N_0} r_i\Pr[v_i(\overline{G}_i) < \tau\mid B,R_1,R_2]
\le
\sum_{i \in N_0} r_i e^{-\kappa r'_i/16} \\
&\le\sum_{i \in N_0} r'_i e^{-\kappa r'_i/16}+\Delta
\le\frac{16n}{e\kappa}+\Delta.
\end{aligned} E [ ∣ Q ∣ ∣ B , R 1 , R 2 ] = i ∈ N 0 ∑ r i Pr [ v i ( G i ) < τ ∣ B , R 1 , R 2 ] ≤ i ∈ N 0 ∑ r i e − κ r i ′ /16 ≤ i ∈ N 0 ∑ r i ′ e − κ r i ′ /16 + Δ ≤ e κ 16 n + Δ. The second inequality uses r i = r i ′ + ( r i − r i ′ ) r_i = r'_i+(r_i-r'_i) r i = r i ′ + ( r i − r i ′ ) e − κ r i ′ / 16 ≤ 1 e^{-\kappa r'_i/16} \le1 e − κ r i ′ /16 ≤ 1 t e − κ t / 16 ≤ 16 / ( e κ ) te^{-\kappa t/16} \le16/(e\kappa) t e − κ t /16 ≤ 16/ ( e κ ) t ≥ 0 t \ge0 t ≥ 0 t = 16 / κ t = 16/\kappa t = 16/ κ
Averaging over the partition and then over B B B (20) , gives E [ ∣ Q ∣ ] ≤ 16 n / ( e κ ) + n ϵ s \mathbb{E}[|Q|] \le16n/(e\kappa) + n\epsilon_s E [ ∣ Q ∣ ] ≤ 16 n / ( e κ ) + n ϵ s
Markov’s inequality now yields
Pr [ ∣ Q ∣ > κ ] ≤ E [ ∣ Q ∣ ] κ ≤ 16 n e κ 2 + n ϵ s κ < 1 128 . \Pr[|Q| > \kappa] \le\frac{\mathbb{E}[|Q|]}{\kappa} \le\frac{16n}{e\kappa^2} + \frac{n\epsilon_s}{\kappa} < \frac{1}{128}. Pr [ ∣ Q ∣ > κ ] ≤ κ E [ ∣ Q ∣ ] ≤ e κ 2 16 n + κ n ϵ s < 128 1 . where the final inequality uses κ = 2 20 ⌈ n ⌉ \kappa= 2^{20}\lceil\sqrt{n}\rceil κ = 2 20 ⌈ n ⌉ ϵ s = 2 1 − 32 κ \epsilon_s = 2^{1-32\kappa} ϵ s = 2 1 − 32 κ
Finally, we describe the deterministic reserve repair and prove that it succeeds whenever ∣ Q ∣ ≤ κ |Q| \le\kappa ∣ Q ∣ ≤ κ v i ( R 2 ) ≥ V v_i(R_2) \ge V v i ( R 2 ) ≥ V i ∈ Q i \in Q i ∈ Q r i > 0 r_i > 0 r i > 0 (20) .
Scan the items of R 2 R_2 R 2 τ \tau τ τ \tau τ τ \tau τ 2 τ 2\tau 2 τ
To see that the procedure can continue until the queue is empty, suppose that t t t P 1 , … , P t P_1,\ldots,P_t P 1 , … , P t U = R 2 ∖ ⋃ ℓ = 1 t P ℓ U = R_2 \setminus\bigcup_{\ell=1}^{t} P_\ell U = R 2 ∖ ⋃ ℓ = 1 t P ℓ i i i t ≤ κ − 1 t \le\kappa- 1 t ≤ κ − 1
v i ( U ) ≥ v i ( R 2 ) − ∑ ℓ = 1 t v i ( P ℓ ) ≥ V − 2 t τ ≥ 64 κ τ − 2 ( κ − 1 ) τ > τ . v_i(U) \ge v_i(R_2) - \sum_{\ell=1}^{t} v_i(P_\ell) \ge V - 2t\tau\ge64\kappa\tau- 2(\kappa- 1)\tau> \tau. v i ( U ) ≥ v i ( R 2 ) − ℓ = 1 ∑ t v i ( P ℓ ) ≥ V − 2 t τ ≥ 64 κ τ − 2 ( κ − 1 ) τ > τ . Thus, scanning U U U τ \tau τ n n n O ( n ∣ R 2 ∣ ) O(n|R_2|) O ( n ∣ R 2 ∣ )
Theorem 3.12. For normalized monotone subadditive valuations and any number of items, there is a randomized polynomial-time O ( n ) O(\sqrt{n}) O ( n ) 3 / 4 3/4 3/4
Proof. We first consider m ≥ 128 n 2 m \ge128n^2 m ≥ 128 n 2 B B B ( i , S ) (i,S) ( i , S )
v i ( ( S ∩ K ) ∖ B ) ≥ 1 2 v i ( S ∩ K ) ≥ T 4 . v_i((S \cap K) \setminus B) \ge\frac{1}{2}v_i(S \cap K) \ge\frac{T}{4}. v i (( S ∩ K ) ∖ B ) ≥ 2 1 v i ( S ∩ K ) ≥ 4 T . Thus, the solution constructed in Step 3 is a feasible configuration solution with objective value T / 4 T/4 T /4 128 n 2 128n^2 128 n 2 T / ( 4 κ ) T/(4\kappa) T / ( 4 κ ) 1 / 128 1/128 1/128 B B B B B B
If an agent i ∈ N 0 i \in N_0 i ∈ N 0 S i S_i S i A i A_i A i
v i ( A i ) ≥ T 4 κ = 1024 τ > τ . v_i(A_i) \ge\frac{T}{4\kappa} = 1024\tau> \tau. v i ( A i ) ≥ 4 κ T = 1024 τ > τ . In particular, the guarantee applies simultaneously to all agents with retained core-type sources. The preceding analysis bounds three other failure events. The probability that some agent in N 0 N_0 N 0 1 / 128 1/128 1/128 (20) , after averaging over B B B v i ( R 2 ) < V v_i(R_2) < V v i ( R 2 ) < V i ∈ N 0 i \in N_0 i ∈ N 0 r i > 0 r_i > 0 r i > 0 n ϵ s < 1 / 128 n\epsilon_s < 1/128 n ϵ s < 1/128 Pr [ ∣ Q ∣ > κ ] < 1 / 128 \Pr[|Q| > \kappa] < 1/128 Pr [ ∣ Q ∣ > κ ] < 1/128
If none of these four events occurs, every agent receives value at least τ \tau τ N 0 N_0 N 0 τ \tau τ N 0 N_0 N 0 G ‾ i \overline{G}_i G i τ \tau τ Q Q Q r i > 0 r_i > 0 r i > 0 V V V ∣ Q ∣ ≤ κ |Q| \le\kappa ∣ Q ∣ ≤ κ B B B K ∖ B K \setminus B K ∖ B R 1 R_1 R 1 R 2 R_2 R 2
A union bound therefore gives success probability at least 1 − 4 / 128 = 31 / 32 1 - 4/128 = 31/32 1 − 4/128 = 31/32 T > T L P / 6 ≥ O P T M M / 6 T > T_{\mathrm{LP}}/6 \ge\mathrm{OPT}_{\mathrm{MM}}/6 T > T LP /6 ≥ OPT MM /6
min i v i ( A i ) ≥ τ > O P T M M 24576 κ = O P T M M O ( n ) . \min_i v_i(A_i) \ge\tau> \frac{\mathrm{OPT}_{\mathrm{MM}}}{24576\kappa} = \frac{\mathrm{OPT}_{\mathrm{MM}}}{O(\sqrt{n})}. i min v i ( A i ) ≥ τ > 24576 κ OPT MM = O ( n ) OPT MM . For m < 128 n 2 m < 128n^2 m < 128 n 2 T / κ T/\kappa T / κ 127 / 128 127/128 127/128
It remains to obtain a worst-case polynomial-time implementation. The limits on tree exploration are already included in Lemma 3.10. All other combinatorial operations and the number of sampling calls are polynomially bounded. As explained in Appendix § 12 .§ 2 , we can cap the rational samplers so that the total abort probability is at most 1 / 16 1/16 1/16 1 / 16 1/16 1/16 31 / 32 − 1 / 16 > 3 / 4 31/32 - 1/16 > 3/4 31/32 − 1/16 > 3/4 § 9 .
Finally, we repeat the entire algorithm independently and keep the returned allocation with the largest minimum agent value. After q q q 4 − q 4^{-q} 4 − q
Proof of Theorem 1.1 . If Lemma 3.4 detects T L P = 0 T_{\mathrm{LP}} = 0 T LP = 0 Theorem 3.5 , applied to the configuration solution of Lemma 3.4 with the supporting clauses constructed in § 3.4 . With probability at least 3 / 4 3/4 3/4 T / ( 128 ⌈ n ⌉ ) > O P T M M / ( 768 ⌈ n ⌉ ) T/(128\lceil\sqrt{n}\rceil) > \mathrm{OPT}_{\mathrm{MM}}/(768\lceil\sqrt{n}\rceil) T / ( 128 ⌈ n ⌉) > OPT MM / ( 768 ⌈ n ⌉) Theorem 3.12 .
Weighted Nash social welfare
In this section, we present an approximation algorithm for weighted Nash social welfare with subadditive valuations using ordinary demand queries. The approximation factor depends on the entropy of the agents’ weights but not on the number of items. We first prove a rounding theorem for an explicit configuration solution and then show how to construct such a solution using demand queries.
The configuration setting
We use the weighted Nash social welfare objective and notation of § 2 and assume throughout this section that the valuations are subadditive. We define the entropy of the weight vector and the associated approximation factor by
H ( w ) = − ∑ i ∈ N w i ln w i , Γ ( w ) = ∏ i ∈ N ( n w i ) w i / 2 = exp ( ln n − H ( w ) 2 ) . (21) H(w) = -\sum_{i\in N} w_i \ln w_i,\qquad\Gamma(w) = \prod_{i\in N}(nw_i)^{w_i/2} = \exp\left(\frac{\ln n - H(w)}{2}\right). \tag*{(21)} H ( w ) = − i ∈ N ∑ w i ln w i , Γ ( w ) = i ∈ N ∏ ( n w i ) w i /2 = exp ( 2 ln n − H ( w ) ) . (21) Since 0 ≤ H ( w ) ≤ ln n 0 \le H(w) \le\ln n 0 ≤ H ( w ) ≤ ln n 1 ≤ Γ ( w ) ≤ n 1 \le\Gamma(w) \le\sqrt{n} 1 ≤ Γ ( w ) ≤ n Γ ( w ) = 1 \Gamma(w) = 1 Γ ( w ) = 1
Consider an explicit configuration solution ( C i , y i , S ) i ∈ N (C_i,y_{i,S})_{i\in N} ( C i , y i , S ) i ∈ N (2) and (3) . We assume that v i ( S ) > 0 v_i(S)>0 v i ( S ) > 0 S ∈ C i S\in C_i S ∈ C i ( i , S ) (i,S) ( i , S ) i ∈ N i\in N i ∈ N S ∈ C i S\in C_i S ∈ C i (2) and the normalization of the weights imply
∑ i , S y i , S = n , ∑ i , S w i y i , S = 1. \sum_{i,S} y_{i,S}=n,\qquad\sum_{i,S} w_i y_{i,S}=1. i , S ∑ y i , S = n , i , S ∑ w i y i , S = 1. We use L ( y ) L(y) L ( y ) (4) as the logarithmic benchmark of this solution.
Theorem 4.1. Given an explicit positive configuration solution as above, there is a randomized polynomial-time algorithm that returns a feasible allocation A A A v i ( A i ) > 0 v_i(A_i)>0 v i ( A i ) > 0
E ln NSW w ( A ) ≥ L ( y ) − ln Γ ( w ) − C , (22) \mathbb{E}\ln\operatorname{NSW}_w(A)\ge L(y)-\ln\Gamma(w)-C, \tag*{(22)} E ln NSW w ( A ) ≥ L ( y ) − ln Γ ( w ) − C , (22) where C C C
For instances with positive optimum, § 4.6 constructs a positive feasible configuration solution whose benchmark is within an additive constant of ln OPT N S W \ln\operatorname{OPT}_{\mathrm{NSW}} ln OPT NSW O ( Γ ( w ) ) O(\Gamma(w)) O ( Γ ( w ))
Throughout this section, C C C
The rounding algorithm
If n = 1 n=1 n = 1 n ≥ 2 n\ge2 n ≥ 2
Reserving one singleton from each configuration. Following the large-item rule of Feng, Hu, Li, and Zhang [33 ] for submodular valuations, we reserve one item per configuration. For each ( i , S ) (i,S) ( i , S )
g i , S ∈ arg max j ∈ S v i ( { j } ) , ν i , S = v i ( { g i , S } ) , T i , S = S ∖ { g i , S } . (23) g_{i,S}\in\underset{j\in S}{\arg\max}\ v_i(\{j\}),\qquad\nu_{i,S}=v_i(\{g_{i,S}\}),\qquad T_{i,S}=S\setminus\{g_{i,S}\}. \tag*{(23)} g i , S ∈ j ∈ S arg max v i ({ j }) , ν i , S = v i ({ g i , S }) , T i , S = S ∖ { g i , S } . (23) We call g i , S g_{i,S} g i , S head of the configuration and T i , S T_{i,S} T i , S tail . Since v i ( S ) > 0 v_i(S)>0 v i ( S ) > 0 ν i , S > 0 \nu_{i,S}>0 ν i , S > 0 T i , S T_{i,S} T i , S ν i , S \nu_{i,S} ν i , S
For each agent i i i j j j x i j x_{ij} x ij i i i j j j
x i j = ∑ S : g i , S = j y i , S , b j = ∑ i ∈ N x i j , f j = 1 − b j . (24) x_{ij}=\sum_{S:g_{i,S}=j}y_{i,S},\qquad b_j=\sum_{i\in N}x_{ij},\qquad f_j=1-b_j. \tag*{(24)} x ij = S : g i , S = j ∑ y i , S , b j = i ∈ N ∑ x ij , f j = 1 − b j . (24) The quantities b j b_j b j f j f_j f j § 3.1 . The configuration constraints imply that every row of x x x ∑ j ∈ M b j = n \sum_{j\in M}b_j=n ∑ j ∈ M b j = n
For each item j j j j j j b j b_j b j j j j j j j
∑ i , S : j ∈ T i , S y i , S ≤ f j = 1 − b j ( j ∈ M ) . (25) \sum_{i,S:j\in T_{i,S}}y_{i,S}\le f_j=1-b_j\qquad(j\in M). \tag*{(25)} i , S : j ∈ T i , S ∑ y i , S ≤ f j = 1 − b j ( j ∈ M ) . (25) In the analysis, we use this inequality and ∑ j ∈ M b j = n \sum_{j\in M}b_j=n ∑ j ∈ M b j = n
Matching the heads and allocating the tails. We first sample a covering matching π : N → M \pi:N\to M π : N → M i i i π ( i ) \pi(i) π ( i ) x i , π ( i ) > 0 x_{i,\pi(i)}>0 x i , π ( i ) > 0 Lemma 4.2 , which has edge marginals Pr [ π ( i ) = j ] = x i j \Pr[\pi(i)=j]=x_{ij} Pr [ π ( i ) = j ] = x ij
B = { π ( i ) : i ∈ N } B=\{\pi(i):i\in N\} B = { π ( i ) : i ∈ N } be the set of matched items.
Dobzinski, Li, Rubinstein, and Vondrák [23 ] used repeated welfare rounding and random filtering for unweighted subadditive NSW. Feige and Huang [32 ] used independent runs of Feige’s rounding [28 ] with uniform contention resolution for maximin shares. Here we allocate the tails independently of the head matching, using the conditional version of guiding-tree rounding from Lemma 3.10 and geometrically decreasing retention probabilities. As in the proof of Lemma 3.11, we first halve each tail mass and add mass 1 / 2 1/2 1/2 1 / 2 1/2 1/2
k = 0 , … , K , K = ⌈ log 2 ( m + 1 ) ⌉ , k=0,\ldots,K,\qquad K=\left\lceil\log_{2}(m+1)\right\rceil, k = 0 , … , K , K = ⌈ log 2 ( m + 1 ) ⌉ , and denote the allocation from run k k k G k G^{k} G k k k k 2 − k − 1 2^{-k-1} 2 − k − 1 M k M_{k} M k k k k
Z i = ⋃ k = 0 K ( G i k ∩ M k ) . (26) Z_{i}=\bigcup_{k=0}^{K}\left(G_{i}^{k}\cap M_{k}\right). \tag*{(26)} Z i = k = 0 ⋃ K ( G i k ∩ M k ) . (26) Finally, we remove the matched items from the tail bundles and give each agent its matched head together with the remaining tail items:
A i = { π ( i ) } ∪ ( Z i ∖ B ) . (27) A_{i}=\{\pi(i)\}\cup\left(Z_{i}\setminus B\right). \tag*{(27)} A i = { π ( i )} ∪ ( Z i ∖ B ) . (27) Each G k G^{k} G k Z Z Z B B B A A A
Following the maximum-entropy approach to prescribed marginals of Singh and Vishnoi [61 ] , we use product-weight (Gibbs) distributions on matchings. § 4.3 obtains exact edge marginals x i j x_{ij} x ij x x x [45 ] to sample a covering matching. Appendix § 10 establishes the required guarantees for this implementation and shows that one calibration can be reused across repeated trials.
Overview of the analysis. We now outline how to compare the configuration benchmark L ( y ) L(y) L ( y ) ( i , S ) (i,S) ( i , S ) buffered residual value by
D i , S ( B ) = v i , S + v i ( T i , S ∖ B ) . (28) D_{i,S}(B)=v_{i,S}+v_{i}(T_{i,S}\setminus B). \tag*{(28)} D i , S ( B ) = v i , S + v i ( T i , S ∖ B ) . (28) This quantity adds the value of the configuration’s head to the value remaining in its tail after removing B B B i i i D i , S ( B ) D_{i,S}(B) D i , S ( B ) v i ( S ) v_{i}(S) v i ( S ) E B \mathbb{E}_{B} E B
First, we bound how much the configuration values can exceed these auxiliary values, in aggregate:
∑ i , S y i , S E B ( v i ( S ) D i , S ( B ) ) 2 ≤ C n . (29) \sum_{i,S} y_{i,S}\mathbb{E}_{B}\left(\frac{v_i(S)}{D_{i,S}(B)}\right)^2 \le Cn. \tag*{(29)} i , S ∑ y i , S E B ( D i , S ( B ) v i ( S ) ) 2 ≤ C n . (29) Second, we show that the expected logarithmic welfare of A A A ln D i , S ( B ) \ln D_{i,S}(B) ln D i , S ( B )
E ln NSW w ( A ) ≥ ∑ i , S w i y i , S E B ln D i , S ( B ) − C . (30) \mathbb{E}\ln\operatorname{NSW}_{w}(A) \ge\sum_{i,S} w_i y_{i,S}\mathbb{E}_{B}\ln D_{i,S}(B)-C. \tag*{(30)} E ln NSW w ( A ) ≥ i , S ∑ w i y i , S E B ln D i , S ( B ) − C . (30) The first estimate and Jensen’s inequality show that this weighted average is at least L ( y ) − ln Γ ( w ) − O ( 1 ) L(y)-\ln\Gamma(w)-O(1) L ( y ) − ln Γ ( w ) − O ( 1 ) Theorem 4.1 .
Singleton matching
Lemma 4.2. Let x x x (24) . There exists a random covering matching π : N → M \pi:N\to M π : N → M ( i , j ) (i,j) ( i , j ) x i j > 0 x_{ij}>0 x ij > 0 B = { π ( i ) : i ∈ N } B=\{\pi(i):i\in N\} B = { π ( i ) : i ∈ N }
(i) For every i ∈ N i\in N i ∈ N j ∈ M j\in M j ∈ M Pr [ π ( i ) = j ] = x i j \Pr[\pi(i)=j]=x_{ij} Pr [ π ( i ) = j ] = x ij Pr [ j ∈ B ] = b j \Pr[j\in B]=b_j Pr [ j ∈ B ] = b j j ∈ M j\in M j ∈ M
(ii) For every set of items J ⊆ M J\subseteq M J ⊆ M
Pr [ J ⊆ B ] ≤ ∏ j ∈ J b j . (31) \Pr[J\subseteq B]\le\prod_{j\in J}b_j. \tag*{(31)} Pr [ J ⊆ B ] ≤ j ∈ J ∏ b j . (31) (iii) For each fixed agent i i i π \pi π B ^ i ⊆ M \widehat{B}_i\subseteq M B i ⊆ M B B B π ( i ) \pi(i) π ( i )
∣ B ∖ B ^ i ∣ ≤ 1 , ∣ B ^ i ∖ B ∣ ≤ 1. (32) |B\setminus\widehat{B}_i|\le1,\qquad|\widehat{B}_i\setminus B|\le1. \tag*{(32)} ∣ B ∖ B i ∣ ≤ 1 , ∣ B i ∖ B ∣ ≤ 1. (32) These couplings are used only in the analysis and may be chosen separately for different agents.
Proof. We first prove the negative-correlation and coupling properties for any positive choice of edge weights. We then choose weights whose edge marginals approach x x x
Gibbs distributions. Give each edge ( i , j ) (i,j) ( i , j ) x i j > 0 x_{ij}>0 x ij > 0 λ i j \lambda_{ij} λ ij M \mathcal{M} M x x x M \mathcal{M} M
μ λ ( P ) = ∏ ( i , j ) ∈ P λ i j Z λ , Z λ = ∑ P ∈ M ∏ ( i , j ) ∈ P λ i j . (33) \mu_{\lambda}(P)=\frac{\prod_{(i,j)\in P}\lambda_{ij}}{Z_{\lambda}},\qquad Z_{\lambda}=\sum_{P\in\mathcal{M}}\prod_{(i,j)\in P}\lambda_{ij}. \tag*{(33)} μ λ ( P ) = Z λ ∏ ( i , j ) ∈ P λ ij , Z λ = P ∈ M ∑ ( i , j ) ∈ P ∏ λ ij . (33) The reference coupling. Fix an agent i i i p i j p_{ij} p ij μ λ \mu_{\lambda} μ λ j j j i i i j j j p i j > 0 p_{ij}>0 p ij > 0 j j j i i i μ λ \mu_{\lambda} μ λ j j j
Draw P P P μ λ \mu_{\lambda} μ λ P P P Q Q Q μ λ \mu_{\lambda} μ λ ( i , j ) (i,j) ( i , j ) P △ Q P\mathbin{\triangle}Q P △ Q P P P ( i , j ) (i,j) ( i , j ) C = ∅ C=\varnothing C = ∅ C C C i i i
( P , Q ) ⟼ ( P ∗ , Q ∗ ) = ( Q △ C , P △ C ) . (34) (P,Q)\longmapsto(P^*,Q^*)=(Q\mathbin{\triangle}C,P\mathbin{\triangle}C). \tag*{(34)} ( P , Q ) ⟼ ( P ∗ , Q ∗ ) = ( Q △ C , P △ C ) . (34) Thus P ∗ P^* P ∗ P P P C C C Q Q Q C C C Q ∗ Q^* Q ∗ Q Q Q C C C P P P C C C
We claim that this switch preserves the joint distribution of ( P , Q ) (P,Q) ( P , Q ) ( i , j ) (i,j) ( i , j ) ( P , Q ) (P,Q) ( P , Q ) C = ∅ C=\emptyset C = ∅ P P P Q Q Q ( i , j ) (i,j) ( i , j ) ( i , j ) (i,j) ( i , j ) C = ∅ C=\emptyset C = ∅ ( P , Q ) (P,Q) ( P , Q )
Suppose now that C ≠ ∅ C\ne\emptyset C = ∅ ( i , j ) (i,j) ( i , j ) C C C Q Q Q P P P C C C Q ∗ Q^* Q ∗ P ∗ P^* P ∗
P ∗ △ Q ∗ = ( Q △ C ) △ ( P △ C ) = P △ Q . P^* \mathbin{\triangle} Q^*=(Q\mathbin{\triangle} C)\mathbin{\triangle}(P\mathbin{\triangle} C)=P\mathbin{\triangle} Q. P ∗ △ Q ∗ = ( Q △ C ) △ ( P △ C ) = P △ Q . When the rule is applied to ( P ∗ , Q ∗ ) (P^*,Q^*) ( P ∗ , Q ∗ ) i i i C C C
( Q ∗ △ C , P ∗ △ C ) = ( P , Q ) . (Q^*\mathbin{\triangle} C,P^*\mathbin{\triangle} C)=(P,Q). ( Q ∗ △ C , P ∗ △ C ) = ( P , Q ) . Thus, in both cases, Q ∗ Q^* Q ∗ ( i , j ) (i,j) ( i , j ) ( P , Q ) (P,Q) ( P , Q ) ( P , Q ) (P,Q) ( P , Q ) ( i , j ) ∈ Q (i,j)\in Q ( i , j ) ∈ Q
Second, we compare the probability of a fixed outcome before and after the switch. Fix R , T ∈ M R,T\in\mathcal{M} R , T ∈ M ( i , j ) ∈ T (i,j)\in T ( i , j ) ∈ T ( R ′ , T ′ ) (R',T') ( R ′ , T ′ ) ( i , j ) ∈ T ′ (i,j)\in T' ( i , j ) ∈ T ′ ( R , T ) (R,T) ( R , T ) ( R , T ) (R,T) ( R , T ) ( R ′ , T ′ ) (R',T') ( R ′ , T ′ )
The switch does not change the total number of occurrences of any edge in the two matchings. By the definition of μ λ \mu_\lambda μ λ
μ λ ( R ′ ) μ λ ( T ′ ) = μ λ ( R ) μ λ ( T ) . \mu_\lambda(R')\mu_\lambda(T')=\mu_\lambda(R)\mu_\lambda(T). μ λ ( R ′ ) μ λ ( T ′ ) = μ λ ( R ) μ λ ( T ) . Using the sampling rule, we obtain
Pr [ P ∗ = R , Q ∗ = T ] = Pr [ P = R ′ , Q = T ′ ] = μ λ ( R ′ ) μ λ ( T ′ ) p i j = μ λ ( R ) μ λ ( T ) p i j = Pr [ P = R , Q = T ] . \begin{aligned}
\Pr[P^*=R,Q^*=T]&=\Pr[P=R',Q=T']\\
&=\frac{\mu_\lambda(R')\mu_\lambda(T')}{p_{ij}}\\
&=\frac{\mu_\lambda(R)\mu_\lambda(T)}{p_{ij}}\\
&=\Pr[P=R,Q=T].
\end{aligned} Pr [ P ∗ = R , Q ∗ = T ] = Pr [ P = R ′ , Q = T ′ ] = p ij μ λ ( R ′ ) μ λ ( T ′ ) = p ij μ λ ( R ) μ λ ( T ) = Pr [ P = R , Q = T ] . This equality holds for every such pair ( R , T ) (R,T) ( R , T ) ( P ∗ , Q ∗ ) (P^*,Q^*) ( P ∗ , Q ∗ ) ( P , Q ) (P,Q) ( P , Q ) P ∗ P^* P ∗ μ λ \mu_\lambda μ λ
For a matching R R R B ( R ) B(R) B ( R ) P ∗ P^* P ∗ Q Q Q C C C C C C B ( P ∗ ) = B ( Q ) B(P^*)=B(Q) B ( P ∗ ) = B ( Q ) C C C
∣ B ( P ∗ ) ∖ B ( Q ) ∣ ≤ 1 , ∣ B ( Q ) ∖ B ( P ∗ ) ∣ ≤ 1. \lvert B(P^*)\setminus B(Q)\rvert\le1,\qquad\lvert B(Q)\setminus B(P^*)\rvert\le1. ∣ B ( P ∗ ) ∖ B ( Q )∣ ≤ 1 , ∣ B ( Q ) ∖ B ( P ∗ )∣ ≤ 1. So far, the construction has been carried out for a fixed item j j j j j j p i j p_{ij} p ij p i j p_{ij} p ij j j j i i i μ λ \mu_\lambda μ λ Q Q Q μ λ \mu_\lambda μ λ j j j P ∗ P^* P ∗ μ λ \mu_\lambda μ λ P ∗ P^* P ∗ B ( P ∗ ) B(P^*) B ( P ∗ ) j = Q ( i ) j=Q(i) j = Q ( i )
Set π = Q \pi= Q π = Q B ^ i = B ( P ∗ ) \widehat{B}_i = B(P^*) B i = B ( P ∗ ) P ∗ P^* P ∗ Q Q Q μ λ \mu_\lambda μ λ B ^ i \widehat{B}_i B i π ( i ) \pi(i) π ( i )
Negative correlation. We apply Mészáros’s conditional BK inequality for product-weight bipartite matchings [Més23, Theorem 1.4]. The random vertex set in that theorem contains the unmatched agents and the matched items. Requiring this set to contain no agent is therefore equivalent to requiring the matching to cover every agent. Under this conditioning, the matching has distribution μ λ \mu_\lambda μ λ B B B
Let U , V ⊆ M U,V \subseteq M U , V ⊆ M U ⊆ B U \subseteq B U ⊆ B V ⊆ B V \subseteq B V ⊆ B U U U V V V
Pr [ U ∪ V ⊆ B ] ≤ Pr [ U ⊆ B ] Pr [ V ⊆ B ] . \Pr[U \cup V \subseteq B] \le\Pr[U \subseteq B]\Pr[V \subseteq B]. Pr [ U ∪ V ⊆ B ] ≤ Pr [ U ⊆ B ] Pr [ V ⊆ B ] . For any nonempty J ⊆ M J \subseteq M J ⊆ M j ∈ J j \in J j ∈ J U = J ∖ { j } U = J \setminus\{j\} U = J ∖ { j } V = { j } V = \{j\} V = { j }
Pr [ J ⊆ B ] ≤ Pr [ J ∖ { j } ⊆ B ] Pr [ j ∈ B ] . \Pr[J \subseteq B] \le\Pr[J \setminus\{j\} \subseteq B]\Pr[j \in B]. Pr [ J ⊆ B ] ≤ Pr [ J ∖ { j } ⊆ B ] Pr [ j ∈ B ] . Induction on ∣ J ∣ |J| ∣ J ∣
Pr [ J ⊆ B ] ≤ ∏ j ∈ J Pr [ j ∈ B ] . \Pr[J \subseteq B] \le\prod_{j \in J} \Pr[j \in B]. Pr [ J ⊆ B ] ≤ j ∈ J ∏ Pr [ j ∈ B ] . Obtaining the prescribed marginals. By Lemma C.1 in Appendix § 10 , for every η > 0 \eta> 0 η > 0 x ′ x' x ′ ∥ x ′ − x ∥ 1 ≤ η \lVert x' - x \rVert_1 \le\eta ∥ x ′ − x ∥ 1 ≤ η M M M M M M x x x Pr [ j ∈ B ] = b j \Pr[j \in B] = b_j Pr [ j ∈ B ] = b j
To obtain Property (iii), consider the couplings of the matching and its reference set constructed above for each Gibbs distribution in this subsequence. There are finitely many matchings, reference sets, and agents. We can therefore choose a further subsequence along which all joint probabilities converge for every agent. Each limiting coupling has the matching distribution obtained above.
For every U ⊆ M U \subseteq M U ⊆ M j ∈ M j \in M j ∈ M Pr [ B ^ i = U ] = Pr [ B = U ] \Pr[\widehat{B}_i = U] = \Pr[B = U] Pr [ B i = U ] = Pr [ B = U ] Pr [ B ^ i = U , π ( i ) = j ] = Pr [ B ^ i = U ] Pr [ π ( i ) = j ] \Pr[\widehat{B}_i = U, \pi(i) = j] = \Pr[\widehat{B}_i = U]\Pr[\pi(i) = j] Pr [ B i = U , π ( i ) = j ] = Pr [ B i = U ] Pr [ π ( i ) = j ] B B B π ( i ) \pi(i) π ( i )
Finally, every coupling in the sequence assigns probability zero to outcomes violating either set-difference bound. Those outcomes still have probability zero in the limit, so both bounds continue to hold. This proves Property (iii) and completes the proof.
Rounding the tails
In this subsection, we analyze the tail allocation described in § 4.2 . The construction combines independent runs of the guiding-tree rounding procedure of Lemma 3.10 with geometrically decreasing color probabilities. The main estimate, proved in Lemma 4.4 , is used together with singleton matching to bound each agent’s expected logarithmic value.
Tail configurations and rounding runs. We use the tail sets T i , s T_{i,s} T i , s ν i , s \nu_{i,s} ν i , s (23) . For each agent, we halve the mass of every tail configuration and add an empty configuration of mass 1 / 2 1/2 1/2 ⊥ \perp ⊥
y ˉ i , S = y i , S 2 ( S ∈ C i ) , y ˉ i , ⊥ = 1 2 , T i , ⊥ = ∅ , ν i , ⊥ = 0. \bar{y}_{i,S} = \frac{y_{i,S}}{2}\quad(S \in\mathcal{C}_i),\qquad\bar{y}_{i,\perp} = \frac{1}{2},\qquad T_{i,\perp} = \emptyset,\qquad\nu_{i,\perp} = 0. y ˉ i , S = 2 y i , S ( S ∈ C i ) , y ˉ i , ⊥ = 2 1 , T i , ⊥ = ∅ , ν i , ⊥ = 0. The modified masses sum to one for each agent, and the total mass on each item is at most 1 / 2 1/2 1/2 (25) . Thus these indexed sets satisfy the load condition of Lemma 3.10.
As in § 4.2 , run the procedure independently for k = 0 , … , K k=0,\ldots,K k = 0 , … , K K = ⌈ log 2 ( m + 1 ) ⌉ K=\lceil\log_2(m+1)\rceil K = ⌈ log 2 ( m + 1 )⌉ S i k S_i^k S i k i i i k k k G k G^k G k
Pr [ S i k = S ] = y ˉ i , S , G i k ⊆ T i , S i k . \Pr[S_i^k=S]=\bar{y}_{i,S},\qquad G_i^k\subseteq T_{i,S_i^k}. Pr [ S i k = S ] = y ˉ i , S , G i k ⊆ T i , S i k . Independently of these runs, each item receives color k k k p k = 2 − k − 1 p_k=2^{-k-1} p k = 2 − k − 1 M k M_k M k k k k Z i = ⋃ k = 0 K ( G i k ∩ M k ) Z_i=\bigcup_{k=0}^{K}(G_i^k\cap M_k) Z i = ⋃ k = 0 K ( G i k ∩ M k ) (26) .
Guiding-tree rounding after a fixed deletion. Fix one run of the guiding-tree rounding procedure, let G G G S i S_i S i i i i D ⊆ M D\subseteq M D ⊆ M i i i S S S y ˉ i , S > 0 \bar{y}_{i,S}>0 y ˉ i , S > 0
Pr [ v i ( G i ∖ D ) ≥ 1 2 v i ( T i , S ∖ D ) ∣ S i = S ] ≥ 1 4 . (35) \Pr\left[v_i(G_i\setminus D)\geq\frac{1}{2}v_i(T_{i,S}\setminus D)\mid S_i=S\right]\geq\frac{1}{4}. \tag*{(35)} Pr [ v i ( G i ∖ D ) ≥ 2 1 v i ( T i , S ∖ D ) ∣ S i = S ] ≥ 4 1 . (35) Indeed, replace each valuation v i v_i v i Q ↦ v i ( Q ∖ D ) Q\mapsto v_i(Q\setminus D) Q ↦ v i ( Q ∖ D ) (35) . The claim also includes the empty index, for which both values in the inequality are zero.
Combining the rounding runs. The rounding runs are independent, but the color classes are not. The following lemma extends the joint-failure bound used in Lemma 3.11 to the unequal probabilities p k p_k p k
Lemma 4.3. Fix an agent, for each k = 0 , … , K k=0,\ldots,K k = 0 , … , K F k F_k F k k k k M k M_k M k F k F_k F k M k M_k M k
Pr [ ⋂ k = 0 K F k ] ≤ ∏ k = 0 K Pr [ F k ] . (36) \Pr\left[\bigcap_{k=0}^{K}F_k\right]\leq\prod_{k=0}^{K}\Pr[F_k]. \tag*{(36)} Pr [ k = 0 ⋂ K F k ] ≤ k = 0 ∏ K Pr [ F k ] . (36) If the deleted set D D D D D D
Proof. We use the argument in the Combining the runs part of the proof of Lemma 3.11. That argument also applies to unequal color probabilities and to items that remain uncolored. To see this, regard being uncolored as an additional color. Each item’s color indicators still have a multinomial distribution with one trial and hence are negatively associated [44 ] . Since different items are colored independently, the same negative-association argument applies to all the color indicators. Fix the random choices made in all rounding runs, and let g k g_k g k F k F_k F k g k g_k g k M k M_k M k
E c o l [ ∏ k = 0 K g k ] ≤ ∏ k = 0 K E c o l [ g k ] , \mathbb{E}_{\mathrm{col}}\left[\prod_{k=0}^{K}g_k\right]\leq\prod_{k=0}^{K}\mathbb{E}_{\mathrm{col}}[g_k], E col [ k = 0 ∏ K g k ] ≤ k = 0 ∏ K E col [ g k ] , where E c o l \mathbb{E}_{\mathrm{col}} E col k k k
Pr [ ⋂ k = 0 K F k ] = E [ ∏ k = 0 K g k ] ≤ ∏ k = 0 K E [ g k ] = ∏ k = 0 K Pr [ F k ] , \Pr\left[\bigcap_{k=0}^{K}F_k\right]=\mathbb{E}\left[\prod_{k=0}^{K}g_k\right]\leq\prod_{k=0}^{K}\mathbb{E}[g_k]=\prod_{k=0}^{K}\Pr[F_k], Pr [ k = 0 ⋂ K F k ] = E [ k = 0 ∏ K g k ] ≤ k = 0 ∏ K E [ g k ] = k = 0 ∏ K Pr [ F k ] , proving (36) .
If D D D D D D D D D
Bounding the expected logarithmic value. For agent i i i k k k G i k G_i^k G i k k k k G i k ∩ M k G_i^k\cap M_k G i k ∩ M k D D D ν i , S k \nu_{i,S_k} ν i , S k ν i , S k \nu_{i,S_k} ν i , S k z z z [ z ] + = max { 0 , z } [z]_+=\max\{0,z\} [ z ] + = max { 0 , z }
Lemma 4.4. Fix an agent i i i D ⊆ M D\subseteq M D ⊆ M S ∈ C i S\in C_i S ∈ C i W S = v i ( T i , S ∖ D ) W_S=v_i(T_{i,S}\setminus D) W S = v i ( T i , S ∖ D ) S ∈ C i S\in C_i S ∈ C i y i , S y_{i,S} y i , S H = ν i , S > 0 H=\nu_{i,S}>0 H = ν i , S > 0
Z ∗ = ln max { H , max 0 ≤ k ≤ K [ v i ( ( G i k ∩ M k ) ∖ D ) − ν i , S k ] + } . (37) Z^*=\ln\max\left\{H,\ \max_{0\leq k\leq K}\left[v_i\left((G_i^k\cap M_k)\setminus D\right)-\nu_{i,S_k}\right]_+\right\}. \tag*{(37)} Z ∗ = ln max { H , 0 ≤ k ≤ K max [ v i ( ( G i k ∩ M k ) ∖ D ) − ν i , S k ] + } . (37) Then
E Z ∗ ≥ ∑ S ∈ C i y i , S ln ( ν i , S + W S ) − C 0 , C 0 = ln 33 + 16 ln 2. (38) \mathbb{E}Z^*\geq\sum_{S\in C_i}y_{i,S}\ln(\nu_{i,S}+W_S)-C_0,\qquad C_0=\ln33+16\ln2. \tag*{(38)} E Z ∗ ≥ S ∈ C i ∑ y i , S ln ( ν i , S + W S ) − C 0 , C 0 = ln 33 + 16 ln 2. (38) Proof. For each run, abbreviate its contribution to the maximum in (37) by
R k = [ v i ( ( G i k ∩ M k ) ∖ D ) − ν i , S k ] + . R_k=\left[v_i\left((G_i^k\cap M_k)\setminus D\right)-\nu_{i,S_k}\right]_+. R k = [ v i ( ( G i k ∩ M k ) ∖ D ) − ν i , S k ] + . Thus Z ∗ = ln max { H , R 0 , … , R K } Z^*=\ln\max\{H,R_0,\ldots,R_K\} Z ∗ = ln max { H , R 0 , … , R K }
A bound for one run. Fix k k k h = 2 k + 1 h=2^{k+1} h = 2 k + 1 M k M_k M k 1 / h 1/h 1/ h S S S y i , S > 0 y_{i,S}>0 y i , S > 0 W S > 16 h ν i , S W_S>16h\nu_{i,S} W S > 16 h ν i , S (35) , with conditional probability at least 1 / 4 1/4 1/4 Q = G i k ∖ D Q=G_i^k\setminus D Q = G i k ∖ D v i ( Q ) ≥ W S / 2 v_i(Q)\geq W_S/2 v i ( Q ) ≥ W S /2 j ∈ Q j\in Q j ∈ Q
v i ( { j } ) ≤ ν i , S < W S 16 h ≤ v i ( Q ) 8 h . v_i(\{j\})\leq\nu_{i,S}<\frac{W_S}{16h}\leq\frac{v_i(Q)}{8h}. v i ({ j }) ≤ ν i , S < 16 h W S ≤ 8 h v i ( Q ) . The coloring is independent of the rounding history. Applying Lemma 3.9 to Q Q Q 1 / 2 1/2 1/2
v i ( Q ∩ M k ) ≥ v i ( Q ) 4 h ≥ W S 8 h . v_i(Q\cap M_k)\geq\frac{v_i(Q)}{4h}\geq\frac{W_S}{8h}. v i ( Q ∩ M k ) ≥ 4 h v i ( Q ) ≥ 8 h W S . On this event,
R k ≥ W S 8 h − ν i , S > W S 16 h = W S 32 ⋅ 2 k . R_k \ge\frac{W_S}{8h}-\nu_{i,S} > \frac{W_S}{16h}=\frac{W_S}{32\cdot2^k}. R k ≥ 8 h W S − ν i , S > 16 h W S = 32 ⋅ 2 k W S . Since the probability of selecting S S S y ˉ i , S = y i , S / 2 \bar{y}_{i,S}=y_{i,S}/2 y ˉ i , S = y i , S /2
y i , S 2 ⋅ 1 4 ⋅ 1 2 = y i , S 16 . \frac{y_{i,S}}{2}\cdot\frac{1}{4}\cdot\frac{1}{2}=\frac{y_{i,S}}{16}. 2 y i , S ⋅ 4 1 ⋅ 2 1 = 16 y i , S . To express this estimate in terms of the original configuration distribution, draw an auxiliary index S ∈ C i S\in C_i S ∈ C i y i , S y_{i,S} y i , S
U = ln max { ν i , S , W S / 32 } , V = ln ν i , S . U=\ln\max\{\nu_{i,S},W_S/32\},\qquad V=\ln\nu_{i,S}. U = ln max { ν i , S , W S /32 } , V = ln ν i , S . These variables are used only for the comparison. For any real t t t U > max { V , t } + k ln 2 U>\max\{V,t\}+k\ln2 U > max { V , t } + k ln 2
W S > 32 ⋅ 2 k max { ν i , S , e t } . W_S>32\cdot2^k\max\{\nu_{i,S},e^t\}. W S > 32 ⋅ 2 k max { ν i , S , e t } . It therefore ensures both W S > 16 h ν i , S W_S>16h\nu_{i,S} W S > 16 h ν i , S W S / ( 32 ⋅ 2 k ) > e t W_S/(32\cdot2^k)>e^t W S / ( 32 ⋅ 2 k ) > e t
Pr [ R k > e t ] ≥ 1 16 Pr [ U > max { V , t } + k ln 2 ] . (39) \Pr[R_k>e^t]\ge\frac{1}{16}\Pr[U>\max\{V,t\}+k\ln2]. \tag*{(39)} Pr [ R k > e t ] ≥ 16 1 Pr [ U > max { V , t } + k ln 2 ] . (39) Combining the bounds across runs. Define
ϕ ( t ) = E [ U − max { V , t } ] + , λ = 1 16 ln 2 . \phi(t)=\mathbb{E}[U-\max\{V,t\}]_+,\qquad\lambda=\frac{1}{16\ln2}. ϕ ( t ) = E [ U − max { V , t } ] + , λ = 16 ln 2 1 . For a fixed auxiliary index, put d = [ U − max { V , t } ] + d=[U-\max\{V,t\}]_+ d = [ U − max { V , t } ] + ⌈ d / ln 2 ⌉ \lceil d/\ln2\rceil ⌈ d / ln 2 ⌉ k k k k ln 2 < d k\ln2<d k ln 2 < d d / ln 2 d/\ln2 d / ln 2 K K K T i , S ∖ D T_{i,S}\setminus D T i , S ∖ D m m m ν i , S \nu_{i,S} ν i , S W S ≤ m ν i , S W_S\le m\nu_{i,S} W S ≤ m ν i , S
d ≤ U − V = ln max { 1 , W S 32 ν i , S } ≤ ln m < K ln 2. d\le U-V=\ln\max\left\{1,\frac{W_S}{32\nu_{i,S}}\right\}\le\ln m<K\ln2. d ≤ U − V = ln max { 1 , 32 ν i , S W S } ≤ ln m < K ln 2. Taking the expectation of this count and summing (39) over k k k
∑ k = 0 K Pr [ R k > e t ] ≥ 1 16 E [ # { 0 ≤ k ≤ K : k ln 2 < d } ] ≥ E d 16 ln 2 = λ ϕ ( t ) . \begin{aligned}
\sum_{k=0}^{K}\Pr[R_k>e^t]
&\ge\frac{1}{16}\mathbb{E}[\#\{0\le k\le K:k\ln2<d\}]\\
&\ge\frac{\mathbb{E}d}{16\ln2}=\lambda\phi(t).
\end{aligned} k = 0 ∑ K Pr [ R k > e t ] ≥ 16 1 E [ # { 0 ≤ k ≤ K : k ln 2 < d }] ≥ 16 ln 2 E d = λ ϕ ( t ) . For any random variable Y Y Y F Y ( t ) = Pr [ Y ≤ t ] F_Y(t)=\Pr[Y\le t] F Y ( t ) = Pr [ Y ≤ t ] R k ≤ e t R_k\le e^t R k ≤ e t k k k ν i , S k \nu_{i,S_k} ν i , S k M k M_k M k R k R_k R k Lemma 4.3 applies to these events. Also, H H H ln H \ln H ln H V V V
Consequently,
F Z ∗ ( t ) = F V ( t ) Pr [ ⋂ k = 0 K { R k ≤ e t } ] ≤ F V ( t ) ∏ k = 0 K ( 1 − Pr [ R k > e t ] ) ≤ F V ( t ) exp ( − ∑ k = 0 K Pr [ R k > e t ] ) ≤ F V ( t ) e − λ ϕ ( t ) . (40) \begin{aligned}
F_{Z^*}(t)=F_V(t)\Pr\left[\bigcap_{k=0}^{K}\{R_k\le e^t\}\right] \\
&\le F_V(t)\prod_{k=0}^{K}\left(1-\Pr[R_k>e^t]\right) \\
&\le F_V(t)\exp\left(-\sum_{k=0}^{K}\Pr[R_k>e^t]\right)\le F_V(t)e^{-\lambda\phi(t)}. \tag*{(40)}
\end{aligned} F Z ∗ ( t ) = F V ( t ) Pr [ k = 0 ⋂ K { R k ≤ e t } ] ≤ F V ( t ) k = 0 ∏ K ( 1 − Pr [ R k > e t ] ) ≤ F V ( t ) exp ( − k = 0 ∑ K Pr [ R k > e t ] ) ≤ F V ( t ) e − λ ϕ ( t ) . (40) From distribution functions to expectations. Fix values U = u U=u U = u V = v V=v V = v u ≥ v u\ge v u ≥ v
[ u − max { v , t } ] + = { u − v , t ≤ v , u − t , v < t < u , 0 , t ≥ u . [u-\max\{v,t\}]_+=
\begin{cases}
u-v, & t\le v,\\
u-t, & v<t<u,\\
0, & t\ge u.
\end{cases} [ u − max { v , t } ] + = ⎩ ⎨ ⎧ u − v , u − t , 0 , t ≤ v , v < t < u , t ≥ u . Its derivative with respect to t t t − 1 -1 − 1 v < t < u v<t<u v < t < u 0 0 0 t = u t=u t = u t = v t=v t = v
The expectation defining ϕ ( t ) \phi(t) ϕ ( t ) U U U V V V
− ϕ ′ ( t ) = Pr [ V ≤ t < U ] = F V ( t ) − F U ( t ) -\phi'(t)=\Pr[V\le t<U]=F_V(t)-F_U(t) − ϕ ′ ( t ) = Pr [ V ≤ t < U ] = F V ( t ) − F U ( t ) for almost every $t.
The last equality follows because U ≥ V U\ge V U ≥ V Pr [ U ≤ t ] \Pr[U\le t] Pr [ U ≤ t ] Pr [ V ≤ t ] \Pr[V\le t] Pr [ V ≤ t ] Pr [ V ≤ t < U ] \Pr[V\le t<U] Pr [ V ≤ t < U ]
lim t → − ∞ ϕ ( t ) = E ( U − V ) , lim t → ∞ ϕ ( t ) = 0. \lim_{t\to-\infty}\phi(t)=\mathbb{E}(U-V),\qquad\lim_{t\to\infty}\phi(t)=0. t → − ∞ lim ϕ ( t ) = E ( U − V ) , t → ∞ lim ϕ ( t ) = 0. The variables U U U V V V Z ∗ Z^* Z ∗ H H H (40) ,
E U − E Z ∗ = ∫ R ( F Z ∗ ( t ) − F U ( t ) ) d t ≤ ∫ R ( F V ( t ) e − λ ϕ ( t ) − F U ( t ) ) d t ≤ ∫ R ( F V ( t ) − F U ( t ) ) e − λ ϕ ( t ) d t . \begin{aligned}
\mathbb{E}U-\mathbb{E}Z^*=\int_{\mathbb{R}}\left(F_{Z^*}(t)-F_U(t)\right)\,dt \\
&\le\int_{\mathbb{R}}\left(F_V(t)e^{-\lambda\phi(t)}-F_U(t)\right)\,dt \\
&\le\int_{\mathbb{R}}\left(F_V(t)-F_U(t)\right)e^{-\lambda\phi(t)}\,dt.
\end{aligned} E U − E Z ∗ = ∫ R ( F Z ∗ ( t ) − F U ( t ) ) d t ≤ ∫ R ( F V ( t ) e − λ ϕ ( t ) − F U ( t ) ) d t ≤ ∫ R ( F V ( t ) − F U ( t ) ) e − λ ϕ ( t ) d t . The last inequality uses e − λ ϕ ( t ) ≤ 1 e^{-\lambda\phi(t)}\le1 e − λ ϕ ( t ) ≤ 1
d d t e − λ ϕ ( t ) = λ ( F V ( t ) − F U ( t ) ) e − λ ϕ ( t ) \frac{d}{dt}e^{-\lambda\phi(t)}=\lambda\left(F_V(t)-F_U(t)\right)e^{-\lambda\phi(t)} d t d e − λ ϕ ( t ) = λ ( F V ( t ) − F U ( t ) ) e − λ ϕ ( t ) for almost every $t.
Since ϕ \phi ϕ
∫ R ( F V ( t ) − F U ( t ) ) e − λ ϕ ( t ) d t = 1 − e − λ E ( U − V ) λ ≤ 1 λ = 16 ln 2. \int_{\mathbb{R}}\left(F_V(t)-F_U(t)\right)e^{-\lambda\phi(t)}\,dt
=\frac{1-e^{-\lambda\mathbb{E}(U-V)}}{\lambda}
\le\frac{1}{\lambda}=16\ln2. ∫ R ( F V ( t ) − F U ( t ) ) e − λ ϕ ( t ) d t = λ 1 − e − λ E ( U − V ) ≤ λ 1 = 16 ln 2. Comparing with the configuration values. For every original index S S S
ν i , S + W S ≤ 33 max { ν i , S , W S / 32 } . \nu_{i,S}+W_S\le33\max\{\nu_{i,S},W_S/32\}. ν i , S + W S ≤ 33 max { ν i , S , W S /32 } . Taking logarithms and averaging with probabilities y i , S y_{i,S} y i , S
E U ≥ ∑ S ∈ C i y i , S ln ( v i , S + W S ) − ln 33. \mathbb{E}U \ge\sum_{S\in\mathcal{C}_i} y_{i,S}\ln(v_{i,S}+W_S)-\ln33. E U ≥ S ∈ C i ∑ y i , S ln ( v i , S + W S ) − ln 33. Combining this with E U − E Z ∗ ≤ 16 ln 2 \mathbb{E}U-\mathbb{E}Z^* \le16\ln2 E U − E Z ∗ ≤ 16 ln 2 (38) .
Analysis of the rounding algorithm
Bounding the loss from deleting items. We first bound how much the configuration value v i ( S ) v_i(S) v i ( S ) D i , S ( B ) D_{i,S}(B) D i , S ( B ) T i , S T_{i,S} T i , S
Lemma 4.5. Let v v v Q Q Q W = v ( Q ) > 0 W=v(Q)>0 W = v ( Q ) > 0 v ( { j } ) ≤ ν v(\{j\})\le\nu v ({ j }) ≤ ν j ∈ Q j\in Q j ∈ Q ν > 0 \nu>0 ν > 0 D ⊆ Q D\subseteq Q D ⊆ Q b j ∈ [ 0 , 1 ) b_j\in[0,1) b j ∈ [ 0 , 1 ) j ∈ Q j\in Q j ∈ Q
Pr [ J ⊆ D ] ≤ ∏ j ∈ J b j for every J ⊆ Q . \Pr[J\subseteq D]\le\prod_{j\in J}b_j \qquad\text{for every }J\subseteq Q. Pr [ J ⊆ D ] ≤ j ∈ J ∏ b j for every J ⊆ Q . Let V = v ( Q ∖ D ) V=v(Q\setminus D) V = v ( Q ∖ D ) P = ∑ j ∈ Q b j / ( 1 − b j ) P=\sum_{j\in Q}b_j/(1-b_j) P = ∑ j ∈ Q b j / ( 1 − b j )
E ( W V + ν ) 2 ≤ 48 ( 1 + P ) . (41) \mathbb{E}\left(\frac{W}{V+\nu}\right)^2\le48(1+P). \tag*{(41)} E ( V + ν W ) 2 ≤ 48 ( 1 + P ) . (41) Proof. Dividing all values by ν \nu ν (41) unchanged, so we may assume ν = 1 \nu=1 ν = 1 W < 4 W<4 W < 4 W 2 / ( V + 1 ) 2 < 16 W^2/(V+1)^2<16 W 2 / ( V + 1 ) 2 < 16 P = 0 P=0 P = 0 b j = 0 b_j=0 b j = 0 j ∈ Q j\in Q j ∈ Q D = ∅ D=\varnothing D = ∅ V = W V=W V = W W ≥ 4 W\ge4 W ≥ 4 P > 0 P>0 P > 0
Bounding the probability of a small remaining value. Write q ( t ) = Pr [ V ≤ t ] q(t)=\Pr[V\le t] q ( t ) = Pr [ V ≤ t ] 1 ≤ t ≤ W / 4 1\le t\le W/4 1 ≤ t ≤ W /4 k = ⌊ W / ( 2 t ) ⌋ k=\lfloor W/(2t)\rfloor k = ⌊ W / ( 2 t )⌋ W / ( 2 t ) ≥ 2 W/(2t)\ge2 W / ( 2 t ) ≥ 2
W 4 t ≤ k ≤ W 2 t . \frac{W}{4t}\le k\le\frac{W}{2t}. 4 t W ≤ k ≤ 2 t W . Let D ( 1 ) , … , D ( k ) D^{(1)},\ldots,D^{(k)} D ( 1 ) , … , D ( k ) D D D
R k = ∣ ⋂ r = 1 k D ( r ) ∣ . R_k=\left|\bigcap_{r=1}^{k}D^{(r)}\right|. R k = r = 1 ⋂ k D ( r ) . Thus, R k R_k R k v ( Q ∖ D ( r ) ) ≤ t v(Q\setminus D^{(r)})\le t v ( Q ∖ D ( r ) ) ≤ t r r r Q Q Q
W ≤ ∑ r = 1 k v ( Q ∖ D ( r ) ) + v ( ⋂ r = 1 k D ( r ) ) ≤ k t + R k . W\le\sum_{r=1}^{k}v(Q\setminus D^{(r)})+v\left(\bigcap_{r=1}^{k}D^{(r)}\right)\le kt+R_k. W ≤ r = 1 ∑ k v ( Q ∖ D ( r ) ) + v ( r = 1 ⋂ k D ( r ) ) ≤ k t + R k . Since k t ≤ W / 2 kt\le W/2 k t ≤ W /2 R k ≥ W / 2 R_k\ge W/2 R k ≥ W /2 q ( t ) k q(t)^k q ( t ) k
q ( t ) k ≤ Pr [ R k ≥ W / 2 ] . q(t)^k\le\Pr[R_k\ge W/2]. q ( t ) k ≤ Pr [ R k ≥ W /2 ] . We now bound the probability on the right. Let I j I_j I j j j j R k = ∑ j ∈ Q I j R_k = \sum_{j\in Q} I_j R k = ∑ j ∈ Q I j J ⊆ Q J \subseteq Q J ⊆ Q
E [ ∏ j ∈ J I j ] = ∏ r = 1 k Pr [ J ⊆ D ( r ) ] ≤ ∏ j ∈ J b j k . \mathbb{E}\left[\prod_{j\in J} I_j\right] = \prod_{r=1}^{k} \Pr[J \subseteq D^{(r)}] \le\prod_{j\in J} b_j^k. E j ∈ J ∏ I j = r = 1 ∏ k Pr [ J ⊆ D ( r ) ] ≤ j ∈ J ∏ b j k . For s ≥ 0 s \ge0 s ≥ 0
E e s R k = E ∏ j ∈ Q ( 1 + ( e s − 1 ) I j ) = ∑ J ⊆ Q ( e s − 1 ) ∣ J ∣ E [ ∏ j ∈ J I j ] ≤ ∏ j ∈ Q ( 1 + b j k ( e s − 1 ) ) ≤ exp ( μ k ( e s − 1 ) ) , μ k = ∑ j ∈ Q b j k . \begin{aligned}
\mathbb{E}e^{sR_k} = \mathbb{E}\prod_{j\in Q}\left(1+(e^s-1)I_j\right) \\
&= \sum_{J\subseteq Q}(e^s-1)^{|J|}\mathbb{E}\left[\prod_{j\in J}I_j\right] \\
&\le\prod_{j\in Q}\left(1+b_j^k(e^s-1)\right) \\
&\le\exp\left(\mu_k(e^s-1)\right), \qquad\mu_k=\sum_{j\in Q}b_j^k.
\end{aligned} E e s R k = E j ∈ Q ∏ ( 1 + ( e s − 1 ) I j ) = J ⊆ Q ∑ ( e s − 1 ) ∣ J ∣ E j ∈ J ∏ I j ≤ j ∈ Q ∏ ( 1 + b j k ( e s − 1 ) ) ≤ exp ( μ k ( e s − 1 ) ) , μ k = j ∈ Q ∑ b j k . The last inequality uses 1 + x ≤ e x 1+x\le e^x 1 + x ≤ e x k b k ≤ b + b 2 + ⋯ + b k ≤ b / ( 1 − b ) kb^k\le b+b^2+\cdots+b^k\le b/(1-b) k b k ≤ b + b 2 + ⋯ + b k ≤ b / ( 1 − b ) 0 ≤ b < 1 0\le b<1 0 ≤ b < 1
μ k ≤ 1 k ∑ j ∈ Q b j 1 − b j = P k . \mu_k\le\frac{1}{k}\sum_{j\in Q}\frac{b_j}{1-b_j}=\frac{P}{k}. μ k ≤ k 1 j ∈ Q ∑ 1 − b j b j = k P . If 2 e P / ( W k ) < 1 2eP/(Wk)<1 2 e P / ( W k ) < 1 s = ln ( W k / ( 2 P ) ) > 0 s=\ln(Wk/(2P))>0 s = ln ( W k / ( 2 P )) > 0
q ( t ) k ≤ Pr [ R k ≥ W / 2 ] ≤ exp ( − s W 2 + P k ( e s − 1 ) ) = e − P / k ( 2 e P W k ) W / 2 ≤ ( 2 e P W k ) W / 2 . \begin{aligned}
q(t)^k\le\Pr[R_k\ge W/2] \\
&\le\exp\left(-\frac{sW}{2}+\frac{P}{k}(e^s-1)\right) \\
&= e^{-P/k}\left(\frac{2eP}{Wk}\right)^{W/2} \\
&\le\left(\frac{2eP}{Wk}\right)^{W/2}.
\end{aligned} q ( t ) k ≤ Pr [ R k ≥ W /2 ] ≤ exp ( − 2 s W + k P ( e s − 1 ) ) = e − P / k ( W k 2 e P ) W /2 ≤ ( W k 2 e P ) W /2 . Taking the k k k W / ( 2 k ) ≥ t ≥ 1 W/(2k)\ge t\ge1 W / ( 2 k ) ≥ t ≥ 1
q ( t ) ≤ ( 2 e P W k ) W / ( 2 k ) ≤ 2 e P W k . q(t)\le\left(\frac{2eP}{Wk}\right)^{W/(2k)}\le\frac{2eP}{Wk}. q ( t ) ≤ ( W k 2 e P ) W / ( 2 k ) ≤ W k 2 e P . If 2 e P / ( W k ) ≥ 1 2eP/(Wk)\ge1 2 e P / ( W k ) ≥ 1 q ( t ) ≤ 1 q(t)\le1 q ( t ) ≤ 1 k ≥ W / ( 4 t ) k\ge W/(4t) k ≥ W / ( 4 t ) 8 e < 24 8e<24 8 e < 24
q ( t ) ≤ min { 1 , 24 P t / W 2 } ( 1 ≤ t ≤ W / 4 ) . (42) q(t)\le\min\{1,24Pt/W^2\}\qquad(1\le t\le W/4). \tag*{(42)} q ( t ) ≤ min { 1 , 24 P t / W 2 } ( 1 ≤ t ≤ W /4 ) . (42) For 0 ≤ t < 1 0\le t<1 0 ≤ t < 1 q ( t ) ≤ q ( 1 ) ≤ 24 P / W 2 q(t)\le q(1)\le24P/W^2 q ( t ) ≤ q ( 1 ) ≤ 24 P / W 2
q ( t ) ≤ 24 P ( t + 1 ) W 2 . q(t)\le\frac{24P(t+1)}{W^2}. q ( t ) ≤ W 2 24 P ( t + 1 ) . Bounding the expected squared ratio. Since 0 ≤ V ≤ W 0 \le V \le W 0 ≤ V ≤ W
W 2 ( V + 1 ) 2 = W 2 ( W + 1 ) 2 + ∫ V W 2 W 2 ( t + 1 ) 3 d t . \frac{W^2}{(V+1)^2} = \frac{W^2}{(W+1)^2} + \int_V^W \frac{2W^2}{(t+1)^3}\,\mathrm{d}t. ( V + 1 ) 2 W 2 = ( W + 1 ) 2 W 2 + ∫ V W ( t + 1 ) 3 2 W 2 d t . Taking expectations and using Pr [ V ≤ t ] = q ( t ) \Pr[V \le t] = q(t) Pr [ V ≤ t ] = q ( t )
E W 2 ( V + 1 ) 2 = W 2 ( W + 1 ) 2 + ∫ 0 W 2 W 2 q ( t ) ( t + 1 ) 3 d t . \mathbb{E}\frac{W^2}{(V+1)^2} = \frac{W^2}{(W+1)^2} + \int_0^W \frac{2W^2q(t)}{(t+1)^3}\,\mathrm{d}t. E ( V + 1 ) 2 W 2 = ( W + 1 ) 2 W 2 + ∫ 0 W ( t + 1 ) 3 2 W 2 q ( t ) d t . Split the integral at W / 4 W/4 W /4 W / 4 W/4 W /4 q ( t ) ≤ 1 q(t) \le1 q ( t ) ≤ 1
W 2 ( W + 1 ) 2 + ∫ W / 4 W 2 W 2 q ( t ) ( t + 1 ) 3 d t ≤ W 2 ( W / 4 + 1 ) 2 ≤ 16. \frac{W^2}{(W+1)^2} + \int_{W/4}^W \frac{2W^2q(t)}{(t+1)^3}\,\mathrm{d}t \le\frac{W^2}{(W/4+1)^2} \le16. ( W + 1 ) 2 W 2 + ∫ W /4 W ( t + 1 ) 3 2 W 2 q ( t ) d t ≤ ( W /4 + 1 ) 2 W 2 ≤ 16. For the remaining part, apply the bound q ( t ) ≤ 24 P ( t + 1 ) / W 2 q(t) \le24P(t+1)/W^2 q ( t ) ≤ 24 P ( t + 1 ) / W 2
∫ 0 W / 4 2 W 2 q ( t ) ( t + 1 ) 3 d t ≤ 48 P ∫ 0 W / 4 1 ( t + 1 ) 2 d t ≤ 48 P . \int_0^{W/4} \frac{2W^2q(t)}{(t+1)^3}\,\mathrm{d}t \le48P \int_0^{W/4} \frac{1}{(t+1)^2}\,\mathrm{d}t \le48P. ∫ 0 W /4 ( t + 1 ) 3 2 W 2 q ( t ) d t ≤ 48 P ∫ 0 W /4 ( t + 1 ) 2 1 d t ≤ 48 P . Adding these bounds proves
E W 2 ( V + 1 ) 2 ≤ 16 + 48 P ≤ 48 ( 1 + P ) , \mathbb{E}\frac{W^2}{(V+1)^2} \le16 + 48P \le48(1+P), E ( V + 1 ) 2 W 2 ≤ 16 + 48 P ≤ 48 ( 1 + P ) , as required. □
Bounding the total loss. For the following estimate, let B B B Lemma 4.2 . We use Lemma 4.5 to bound the loss for each configuration. We then multiply each bound by the corresponding mass y i , S y_{i,S} y i , S (25) to obtain a bound proportional to n n n
Lemma 4.6. For D i , S ( B ) D_{i,S}(B) D i , S ( B ) (28) , we have
∑ i , S y i , S E B ( v i ( S ) D i , S ( B ) ) 2 ≤ 196 n . (43) \sum_{i,S} y_{i,S}\mathbb{E}_B\left(\frac{v_i(S)}{D_{i,S}(B)}\right)^2 \le196n. \tag*{(43)} i , S ∑ y i , S E B ( D i , S ( B ) v i ( S ) ) 2 ≤ 196 n . (43) Proof. Configurations with zero mass do not contribute to the sum, so we consider only those with y i , S > 0 y_{i,S} > 0 y i , S > 0 j ∈ T i , S j \in T_{i,S} j ∈ T i , S (25) gives f j ≥ y i , S > 0 f_j \ge y_{i,S} > 0 f j ≥ y i , S > 0
P i , S = ∑ j ∈ T i , S b j f j P_{i,S} = \sum_{j \in T_{i,S}} \frac{b_j}{f_j} P i , S = j ∈ T i , S ∑ f j b j is well defined.
Fix a configuration ( i , S ) (i,S) ( i , S ) v i ( T i , S ) > 0 v_i(T_{i,S}) > 0 v i ( T i , S ) > 0 Lemma 4.5 to the set Q = T i , S Q = T_{i,S} Q = T i , S B ∩ T i , S B \cap T_{i,S} B ∩ T i , S ν i , S \nu_{i,S} ν i , S (31) , and b j < 1 b_j < 1 b j < 1 f j > 0 f_j > 0 f j > 0
D i , S ( B ) = ν i , S + v i ( T i , S ∖ B ) , D_{i,S}(B) = \nu_{i,S} + v_i(T_{i,S} \setminus B), D i , S ( B ) = ν i , S + v i ( T i , S ∖ B ) , the lemma gives
E B ( v i ( T i , S ) D i , S ( B ) ) 2 ≤ 48 ( 1 + P i , S ) . \mathbb{E}_B\left(\frac{v_i(T_{i,S})}{D_{i,S}(B)}\right)^2 \le48(1+P_{i,S}). E B ( D i , S ( B ) v i ( T i , S ) ) 2 ≤ 48 ( 1 + P i , S ) . To obtain a bound for the entire configuration, use subadditivity to write v i ( S ) ≤ v i , S + v i ( T i , S ) v_i(S) \le v_{i,S} + v_i(T_{i,S}) v i ( S ) ≤ v i , S + v i ( T i , S ) D i , S ( B ) ≥ v i , S D_{i,S}(B) \ge v_{i,S} D i , S ( B ) ≥ v i , S
v i ( S ) D i , S ( B ) ≤ 1 + v i ( T i , S ) D i , S ( B ) . \frac{v_i(S)}{D_{i,S}(B)} \le1 + \frac{v_i(T_{i,S})}{D_{i,S}(B)}. D i , S ( B ) v i ( S ) ≤ 1 + D i , S ( B ) v i ( T i , S ) . Applying ( 1 + z ) 2 ≤ 2 + 2 z 2 (1+z)^2 \le2+2z^2 ( 1 + z ) 2 ≤ 2 + 2 z 2
E B ( v i ( S ) D i , S ( B ) ) 2 ≤ 2 + 2 E B ( v i ( T i , S ) D i , S ( B ) ) 2 ≤ 2 + 96 ( 1 + P i , S ) ≤ 98 ( 1 + P i , S ) . \mathbb{E}_B\left(\frac{v_i(S)}{D_{i,S}(B)}\right)^2 \le2 + 2\mathbb{E}_B\left(\frac{v_i(T_{i,S})}{D_{i,S}(B)}\right)^2
\le2 + 96(1+P_{i,S})
\le98(1+P_{i,S}). E B ( D i , S ( B ) v i ( S ) ) 2 ≤ 2 + 2 E B ( D i , S ( B ) v i ( T i , S ) ) 2 ≤ 2 + 96 ( 1 + P i , S ) ≤ 98 ( 1 + P i , S ) . If v i ( T i , S ) = 0 v_i(T_{i,S})=0 v i ( T i , S ) = 0 v i ( S ) = v i , S v_i(S)=v_{i,S} v i ( S ) = v i , S D i , S ( B ) = v i , S D_{i,S}(B)=v_{i,S} D i , S ( B ) = v i , S
It remains to sum these bounds over all configurations. Changing the order of summation and applying (25) , we have
∑ i , S y i , S P i , S = ∑ j : f j > 0 b j f j ∑ i , S : j ∈ T i , S y i , S ≤ ∑ j : f j > 0 b j f j f j ≤ ∑ j ∈ M b j = n . (44) \sum_{i,S} y_{i,S}P_{i,S}
= \sum_{j:f_j>0}\frac{b_j}{f_j}\sum_{i,S:j\in T_{i,S}}y_{i,S}
\le\sum_{j:f_j>0}\frac{b_j}{f_j}f_j
\le\sum_{j\in M}b_j=n. \tag*{(44)} i , S ∑ y i , S P i , S = j : f j > 0 ∑ f j b j i , S : j ∈ T i , S ∑ y i , S ≤ j : f j > 0 ∑ f j b j f j ≤ j ∈ M ∑ b j = n . (44) Therefore, using ∑ i , S y i , S = n \sum_{i,S}y_{i,S}=n ∑ i , S y i , S = n
∑ i , S y i , S E B ( v i ( S ) D i , S ( B ) ) 2 ≤ 98 ( ∑ i , S y i , S + ∑ i , S y i , S P i , S ) ≤ 196 n . \sum_{i,S}y_{i,S}\mathbb{E}_B\left(\frac{v_i(S)}{D_{i,S}(B)}\right)^2
\le98\left(\sum_{i,S}y_{i,S}+\sum_{i,S}y_{i,S}P_{i,S}\right)
\le196n. i , S ∑ y i , S E B ( D i , S ( B ) v i ( S ) ) 2 ≤ 98 i , S ∑ y i , S + i , S ∑ y i , S P i , S ≤ 196 n . Bounding the expected logarithmic welfare. The preceding lemma compares the configuration values v i ( S ) v_i(S) v i ( S ) D i , S ( B ) D_{i,S}(B) D i , S ( B )
Lemma 4.7. Let A A A § 4.2 using the matching distribution of Lemma 4.2 . Then
E ln NSW w ( A ) ≥ ∑ i , S w i y i , S E B ln D i , S ( B ) − C 0 . (45) \mathbb{E}\ln\operatorname{NSW}_{w}(A) \ge\sum_{i,S}w_i y_{i,S}\mathbb{E}_B\ln D_{i,S}(B)-C_0. \tag*{(45)} E ln NSW w ( A ) ≥ i , S ∑ w i y i , S E B ln D i , S ( B ) − C 0 . (45) Here C 0 C_0 C 0 Lemma 4.4 .
Proof. Fix an agent i i i B ^ i \widehat{B}_i B i Lemma 4.2 , it has the same distribution as B B B π ( i ) \pi(i) π ( i ) ∣ B ∖ B ^ i ∣ ≤ 1 |B\setminus\widehat{B}_i|\le1 ∣ B ∖ B i ∣ ≤ 1 ( π , B ^ i ) (\pi,\widehat{B}_i) ( π , B i )
For each run k k k G i k ∩ M k G_i^k\cap M_k G i k ∩ M k B B B B ^ i \widehat{B}_i B i B B B ∣ B ∖ B ^ i ∣ ≤ 1 |B\setminus\widehat{B}_i|\le1 ∣ B ∖ B i ∣ ≤ 1 G i k ⊆ T i , S i k G_i^k\subseteq T_{i,S_i^k} G i k ⊆ T i , S i k v i , S i k v_{i,S_i^k} v i , S i k
v i ( ( G i k ∩ M k ) ∖ B ) ≥ v i ( ( G i k ∩ M k ) ∖ B ^ i ) − v i , S i k . (46) v_i\left((G_i^k\cap M_k)\setminus B\right)
\ge v_i\left((G_i^k\cap M_k)\setminus\widehat{B}_i\right)-v_{i,S_i^k}. \tag*{(46)} v i ( ( G i k ∩ M k ) ∖ B ) ≥ v i ( ( G i k ∩ M k ) ∖ B i ) − v i , S i k . (46) If S i k S_i^k S i k G i k = ∅ G_i^k = \varnothing G i k = ∅ ν i , S i k = 0 \nu_{i,S_i^k} = 0 ν i , S i k = 0
Let H = v i ( { π ( i ) } ) > 0 H = v_i(\{\pi(i)\}) > 0 H = v i ({ π ( i )}) > 0 (27) , A i A_i A i π ( i ) \pi(i) π ( i ) ( G i k ∩ M k ) ∖ B (G_i^k \cap M_k) \setminus B ( G i k ∩ M k ) ∖ B H H H (46) and nonnegativity give, for every k k k
v i ( A i ) ≥ [ v i ( ( G i k ∩ M k ) ∖ B ^ i ) − ν i , S i k ] + . v_i(A_i) \ge\left[v_i((G_i^k \cap M_k) \setminus\widehat{B}_i) - \nu_{i,S_i^k}\right]_+. v i ( A i ) ≥ [ v i (( G i k ∩ M k ) ∖ B i ) − ν i , S i k ] + . Taking the maximum of these lower bounds and then its logarithm gives ln v i ( A i ) ≥ Z ∗ \ln v_i(A_i) \ge Z^* ln v i ( A i ) ≥ Z ∗ Z ∗ Z^* Z ∗ (37) with D = B ^ i D = \widehat{B}_i D = B i H H H
We now check that Lemma 4.4 applies after conditioning on B ^ i \widehat{B}_i B i B ^ i \widehat{B}_i B i π ( i ) \pi(i) π ( i ) (24) give
Pr [ π ( i ) = j ∣ B ^ i ] = x i j = ∑ S : g i , S = j y i , S . \Pr[\pi(i) = j \mid\widehat{B}_i] = x_{ij} = \sum_{S:g_{i,S}=j} y_{i,S}. Pr [ π ( i ) = j ∣ B i ] = x ij = S : g i , S = j ∑ y i , S . Thus H H H ν i , S \nu_{i,S} ν i , S S S S y i , S y_{i,S} y i , S B ^ i \widehat{B}_i B i H H H ( π , B ^ i ) (\pi,\widehat{B}_i) ( π , B i )
E [ ln v i ( A i ) ∣ B ^ i ] ≥ ∑ S ∈ C i y i , S ln ( ν i , S + v i ( T i , S ∖ B ^ i ) ) − C 0 . \mathbb{E}[\ln v_i(A_i) \mid\widehat{B}_i] \ge\sum_{S \in C_i} y_{i,S} \ln\left(\nu_{i,S} + v_i(T_{i,S} \setminus\widehat{B}_i)\right) - C_0. E [ ln v i ( A i ) ∣ B i ] ≥ S ∈ C i ∑ y i , S ln ( ν i , S + v i ( T i , S ∖ B i ) ) − C 0 . Averaging over B ^ i \widehat{B}_i B i B B B
E ln v i ( A i ) ≥ ∑ S ∈ C i y i , S E B ln D i , S ( B ) − C 0 . \mathbb{E}\ln v_i(A_i) \ge\sum_{S \in C_i} y_{i,S}\mathbb{E}_B \ln D_{i,S}(B) - C_0. E ln v i ( A i ) ≥ S ∈ C i ∑ y i , S E B ln D i , S ( B ) − C 0 . Finally, multiply by w i w_i w i ln NSW w ( A ) = ∑ i w i ln v i ( A i ) \ln\operatorname{NSW}_w(A) = \sum_i w_i \ln v_i(A_i) ln NSW w ( A ) = ∑ i w i ln v i ( A i ) ∑ i w i = 1 \sum_i w_i = 1 ∑ i w i = 1 (45) . □
Combining the estimates. We now use Lemmas 4.6 and 4.7 to complete the proof of Theorem 4.1. Applying Jensen’s inequality to the squared-ratio bound gives a logarithmic bound that depends on the entropy of the agents’ weights.
Proof of Theorem 4.1. If n = 1 n = 1 n = 1 n ≥ 2 n \ge2 n ≥ 2 R R R (43) . Lemma 4.6 gives R ≤ 196 n R \le196n R ≤ 196 n
Sample ( i , S ) (i,S) ( i , S ) w i y i , S w_i y_{i,S} w i y i , S B B B
E i , S , B v i ( S ) 2 w i D i , S ( B ) 2 = ∑ i , S y i , S E B v i ( S ) 2 D i , S ( B ) 2 = R . \mathbb{E}_{i,S,B}\frac{v_i(S)^2}{w_iD_{i,S}(B)^2} = \sum_{i,S} y_{i,S}\mathbb{E}_B\frac{v_i(S)^2}{D_{i,S}(B)^2} = R. E i , S , B w i D i , S ( B ) 2 v i ( S ) 2 = i , S ∑ y i , S E B D i , S ( B ) 2 v i ( S ) 2 = R . Using the definitions of L ( y ) L(y) L ( y ) H ( w ) H(w) H ( w )
L ( y ) − ∑ i , S w i y i , S E B ln D i , S ( B ) = 1 2 ( E i , S , B ln v i ( S ) 2 w i D i , S ( B ) 2 − H ( w ) ) ≤ 1 2 ( ln R − H ( w ) ) ≤ ln Γ ( w ) + 1 2 ln 196. (47) \begin{aligned}
L(y) - \sum_{i,S} w_i y_{i,S}\mathbb{E}_B \ln D_{i,S}(B)
= \frac{1}{2}\left(\mathbb{E}_{i,S,B}\ln\frac{v_i(S)^2}{w_iD_{i,S}(B)^2} - H(w)\right) \\
&\le\frac{1}{2}\left(\ln R - H(w)\right) \le\ln\Gamma(w) + \frac{1}{2}\ln196. \tag*{(47)}
\end{aligned} L ( y ) − i , S ∑ w i y i , S E B ln D i , S ( B ) = 2 1 ( E i , S , B ln w i D i , S ( B ) 2 v i ( S ) 2 − H ( w ) ) ≤ 2 1 ( ln R − H ( w ) ) ≤ ln Γ ( w ) + 2 1 ln 196. (47) The last inequality uses R ≤ 196 n R \le196n R ≤ 196 n Γ ( w ) \Gamma(w) Γ ( w ) (21) .
Combining (47) with Lemma 4.7 proves (22) with C = C 0 + 1 2 ln 196 C = C_0 + \frac{1}{2}\ln196 C = C 0 + 2 1 ln 196 Lemma 4.2 .
Appendix § 10 implements the matching step using rational edge weights and approximate sampling, and shows that the two estimates used above remain valid up to absolute constants. This yields the stated polynomial-time algorithm. Choosing the heads is the only step that requires valuation information, the remaining operations use the explicit sets and masses and random sampling.
Computing configurations and applying rounding
We now use ordinary demand queries to construct a positive configuration solution with a near-optimal logarithmic benchmark. We first determine when OPT N S W \operatorname{OPT}_{\mathrm{NSW}} OPT NSW
Lemma 4.8. Consider the bipartite graph with vertex sets N N N M M M ( i , j ) (i,j) ( i , j ) v i ( { j } ) > 0 v_i(\{j\}) > 0 v i ({ j }) > 0 OPT N S W > 0 \operatorname{OPT}_{\mathrm{NSW}} > 0 OPT NSW > 0
Proof. By subadditivity, v i ( S ) ≤ ∑ j ∈ S v i ( { j } ) v_i(S) \le\sum_{j \in S} v_i(\{j\}) v i ( S ) ≤ ∑ j ∈ S v i ({ j }) OPT N S W > 0 \operatorname{OPT}_{\mathrm{NSW}} > 0 OPT NSW > 0
We use the reduction in Appendix § 9 to evaluate the singleton values and then test whether such a matching exists. If no such matching exists, every allocation has zero Nash social welfare. Otherwise, we keep the corresponding singleton allocation as a fallback.
The logarithmic configuration program. We use the configuration LP for weighted Nash social welfare from § 2 , with objective L ( y ) L(y) L ( y ) L L P L_{\mathrm{LP}} L LP z i z_i z i p j p_j p j
minimize U ( z , p ) = ∑ i ∈ N z i + ∑ j ∈ M p j , subject to z i + p ( S ) ≥ w i ln v i ( S ) ( i ∈ N , v i ( S ) > 0 ) , p ≥ 0 , p ( S ) = ∑ j ∈ S p j . (48) \begin{aligned}
\text{minimize}\quad& U(z,p) = \sum_{i \in N} z_i + \sum_{j \in M} p_j,\\
\text{subject to}\quad& z_i + p(S) \ge w_i \ln v_i(S) \qquad(i \in N,\ v_i(S) > 0),\\
& p \ge0,\\
& p(S) = \sum_{j \in S} p_j. \tag*{(48)}
\end{aligned} minimize subject to U ( z , p ) = i ∈ N ∑ z i + j ∈ M ∑ p j , z i + p ( S ) ≥ w i ln v i ( S ) ( i ∈ N , v i ( S ) > 0 ) , p ≥ 0 , p ( S ) = j ∈ S ∑ p j . (48) Lemma 4.9. Suppose OPT N S W > 0 \operatorname{OPT}_{\mathrm{NSW}} > 0 OPT NSW > 0 y y y ( z , p ) (z,p) ( z , p ) (48) . The solution y y y (2) and (3) exactly, and the two solutions satisfy
0 ≤ U ( z , p ) − L ( y ) ≤ 3. (49) 0 \le U(z,p) - L(y) \le3. \tag*{(49)} 0 ≤ U ( z , p ) − L ( y ) ≤ 3. (49) In particular, L ( y ) ≥ L L P − 3 ≥ ln OPT N S W − 3 L(y) \ge L_{\mathrm{LP}} - 3 \ge\ln\operatorname{OPT}_{\mathrm{NSW}} - 3 L ( y ) ≥ L LP − 3 ≥ ln OPT NSW − 3
We prove the lemma in Appendix § 11 , adapting the approximate dual-separation approach used by Feng, Hu, Li, and Zhang [33 ] for submodular valuations. For subadditive valuations, we combine the exact value-evaluation procedure of Appendix § 9 with the budgeted demand-query algorithm of Badanidiyuru, Dobzinski, and Oren [6 ] (Lemma A.2 ). We then use rational dual separation to recover a primal solution supported on finitely many configurations.
As in Appendix § 8 , the resulting solution satisfies (2) and (3) exactly, only the objective is approximated. All oracle calls are ordinary demand queries for the original valuations v i v_i v i
Theorem 4.10. For normalized monotone subadditive valuations and positive rational weights summing to 1, there is a randomized polynomial-time algorithm using ordinary demand queries that achieves an O ( Γ ( w ) ) O(\Gamma(w)) O ( Γ ( w )) OPT N S W > 0 \operatorname{OPT}_{\mathrm{NSW}} > 0 OPT NSW > 0 A A A
E ln NSW w ( A ) ≥ ln OPT N S W − ln Γ ( w ) − C , (50) \mathbb{E}\ln\operatorname{NSW}_{w}(A) \ge\ln\operatorname{OPT}_{\mathrm{NSW}}-\ln\Gamma(w)-C, \tag*{(50)} E ln NSW w ( A ) ≥ ln OPT NSW − ln Γ ( w ) − C , (50) E NSW w ( A ) ≥ OPT N S W C Γ ( w ) . (51) \mathbb{E}\operatorname{NSW}_{w}(A) \ge\frac{\operatorname{OPT}_{\mathrm{NSW}}}{C\Gamma(w)}. \tag*{(51)} E NSW w ( A ) ≥ C Γ ( w ) OPT NSW . (51) Here C > 0 C > 0 C > 0 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) O ( Γ ( w ) ) O(\Gamma(w)) O ( Γ ( w )) 1 − δ 1-\delta 1 − δ
O ( ( 1 + log Γ ( w ) ) log ( 2 / δ ) ) O((1+\log\Gamma(w))\log(2/\delta)) O (( 1 + log Γ ( w )) log ( 2/ δ )) rounding trials. Each trial uses fresh randomness to sample the matching, run guiding-tree rounding, and color the items.
Proof. Lemma 4.8 allows us to identify instances with zero optimum, for which any allocation is optimal. Assume now that OPT N S W > 0 \operatorname{OPT}_{\mathrm{NSW}} > 0 OPT NSW > 0 Lemma 4.9 and round the resulting configuration solution using Theorem 4.1 . Combining the rounding guarantee with (49) gives (50) . Jensen’s inequality for the exponential function then gives (51) , after adjusting the absolute constant.
To obtain success probability at least 1 − δ 1-\delta 1 − δ § 10 and set the calibration failure probability to at most min { η , δ / 2 } \min\{\eta,\delta/2\} min { η , δ /2 } η \eta η Theorem 4.1 with an absolute constant independent of the calibration outcome. Let
D = U ( z , p ) − ln NSW w ( A ) ≥ 0. D = U(z,p)-\ln\operatorname{NSW}_{w}(A) \ge0. D = U ( z , p ) − ln NSW w ( A ) ≥ 0. Dual feasibility gives U ( z , p ) ≥ ln OPT N S W ≥ ln NSW w ( A ) U(z,p) \ge\ln\operatorname{OPT}_{\mathrm{NSW}} \ge\ln\operatorname{NSW}_{w}(A) U ( z , p ) ≥ ln OPT NSW ≥ ln NSW w ( A ) D D D (49) imply E D ≤ a : = ln Γ ( w ) + C \mathbb{E}D \le a := \ln\Gamma(w)+C E D ≤ a := ln Γ ( w ) + C C > 0 C > 0 C > 0
Pr [ D ≤ a + 1 ] ≥ 1 − E D a + 1 ≥ 1 a + 1 . \Pr[D \le a+1] \ge1-\frac{\mathbb{E}D}{a+1} \ge\frac{1}{a+1}. Pr [ D ≤ a + 1 ] ≥ 1 − a + 1 E D ≥ a + 1 1 . Whenever D ≤ a + 1 D \le a+1 D ≤ a + 1
NSW w ( A ) ≥ exp ( U ( z , p ) − a − 1 ) ≥ e − C − 1 OPT N S W Γ ( w ) . \operatorname{NSW}_{w}(A) \ge\exp(U(z,p)-a-1) \ge\frac{e^{-C-1}\operatorname{OPT}_{\mathrm{NSW}}}{\Gamma(w)}. NSW w ( A ) ≥ exp ( U ( z , p ) − a − 1 ) ≥ Γ ( w ) e − C − 1 OPT NSW . Keeping the configuration solution and calibrated matching distribution fixed, perform t t t
( 1 − 1 a + 1 ) t ≤ exp ( − t a + 1 ) . \left(1-\frac{1}{a+1}\right)^t \le\exp\left(-\frac{t}{a+1}\right). ( 1 − a + 1 1 ) t ≤ exp ( − a + 1 t ) . Taking t = O ( ( a + 1 ) log ( 2 / δ ) ) t=O((a+1)\log(2/\delta)) t = O (( a + 1 ) log ( 2/ δ )) δ / 2 \delta/2 δ /2 δ / 2 \delta/2 δ /2 δ \delta δ
Finally, evaluate the utilities of each candidate allocation exactly and compute its logarithmic welfare to a fixed additive accuracy. Return the candidate with the largest computed value. Its logarithmic welfare is within an absolute additive constant of the best trial, so the selection incurs only an absolute multiplicative loss in welfare and preserves the O ( Γ ( w ) ) O(\Gamma(w)) O ( Γ ( w ))
Proof of Theorem 1.2. If O P T N S W = 0 \mathrm{OPT}_{\mathrm{NSW}} = 0 OPT NSW = 0 (51) in Theorem 4.10 .
For equal weights, Γ ( w ) = 1 \Gamma(w) = 1 Γ ( w ) = 1 Γ ( w ) ≤ n \Gamma(w) \le\sqrt{n} Γ ( w ) ≤ n O ( n ) O(\sqrt{n}) O ( n ) O ( log m ) O(\log m) O ( log m ) 1 − δ 1-\delta 1 − δ
The integrality gap for prescribed weights
We show that the dependence on Γ ( w ) \Gamma(w) Γ ( w )
Theorem 4.11. Fix a positive weight vector w w w n n n ∑ i ∈ N w i = 1 \sum_{i\in N} w_i = 1 ∑ i ∈ N w i = 1 e L L P / O P T N S W e^{L_{\mathrm{LP}}}/\mathrm{OPT}_{\mathrm{NSW}} e L LP / OPT NSW Θ ( Γ ( w ) ) \Theta(\Gamma(w)) Θ ( Γ ( w )) Γ ( w ) / 8 \Gamma(w)/\sqrt{8} Γ ( w ) / 8 C Γ ( w ) C\Gamma(w) C Γ ( w ) C C C
Proof. For the upper bound, apply Theorem 4.1 to an optimal basic solution of the configuration LP. The bound on expected logarithmic welfare implies that some allocation has welfare at least e L L P / ( C Γ ( w ) ) e^{L_{\mathrm{LP}}}/(C\Gamma(w)) e L LP / ( C Γ ( w ))
For the lower bound, we adapt the groups of unit-demand agents in the submodular gap construction of Bei, Feng, Hu, Li, and Zhang [9 ] , described in Section 6 of the full version [8 ] . We give the special agent an XOS valuation and choose the group sizes according to the prescribed weights.
We first describe a basic instance. Fix an integer ℓ ≥ 2 \ell\ge2 ℓ ≥ 2 ℓ \ell ℓ R 1 , … , R ℓ R_1,\ldots,R_\ell R 1 , … , R ℓ ℓ \ell ℓ R r R_r R r ℓ − 1 \ell-1 ℓ − 1 blockers , each with valuation 1 { S ∩ R r ≠ ∅ } \mathbf{1}_{\{S\cap R_r\ne\varnothing\}} 1 { S ∩ R r = ∅ }
v ( S ) = 1 ℓ max r ∈ [ ℓ ] ∣ S ∩ R r ∣ . v(S)=\frac{1}{\ell}\max_{r\in[\ell]}|S\cap R_r|. v ( S ) = ℓ 1 r ∈ [ ℓ ] max ∣ S ∩ R r ∣. These valuations are normalized, monotone, and XOS.
For the special agent, assign configuration mass 1 / ℓ 1/\ell 1/ ℓ 1 / ℓ 1/\ell 1/ ℓ 1 / ℓ + ( ℓ − 1 ) / ℓ = 1 1/\ell+(\ell-1)/\ell=1 1/ ℓ + ( ℓ − 1 ) / ℓ = 1 L ( y ) = 0 L(y)=0 L ( y ) = 0 e L L P = 1 e^{L_{\mathrm{LP}}}=1 e L LP = 1
In any allocation of positive welfare, every blocker must receive an item from its row. The blockers therefore use at least ℓ − 1 \ell-1 ℓ − 1 1 / ℓ 1/\ell 1/ ℓ ω \omega ω e − ω e^{-\omega} e − ω
Now consider the prescribed weight vector w w w
I = { i ∈ N : n w i ≥ 8 } , ℓ i = ⌊ n w i / 2 ⌋ ( i ∈ I ) . I=\{i\in N:nw_i\ge8\},\qquad\ell_i=\left\lfloor\sqrt{nw_i/2}\right\rfloor\qquad(i\in I). I = { i ∈ N : n w i ≥ 8 } , ℓ i = ⌊ n w i /2 ⌋ ( i ∈ I ) . For each i ∈ I i\in I i ∈ I ℓ i \ell_i ℓ i i i i ℓ i ( ℓ i − 1 ) \ell_i(\ell_i-1) ℓ i ( ℓ i − 1 ) n / 2 n/2 n /2
∑ i ∈ I ℓ i ( ℓ i − 1 ) ≤ n 2 ∑ i ∈ I w i ≤ n 2 . \sum_{i\in I}\ell_i(\ell_i-1)\le\frac{n}{2}\sum_{i\in I}w_i\le\frac{n}{2}. i ∈ I ∑ ℓ i ( ℓ i − 1 ) ≤ 2 n i ∈ I ∑ w i ≤ 2 n . Also, ∣ I ∣ ≤ n / 8 |I|\le n/8 ∣ I ∣ ≤ n /8 ∣ N ∖ I ∣ ≥ 7 n / 8 ≥ n / 2 |N\setminus I|\ge7n/8\ge n/2 ∣ N ∖ I ∣ ≥ 7 n /8 ≥ n /2 I I I
Combine the configuration solutions of these copies and assign mass one to each unused agent’s private singleton. The resulting instance has e L P P = 1 e^{\mathrm{LPP}}=1 e LPP = 1 ∏ i ∈ I ℓ i − w i \prod_{i\in I}\ell_i^{-w_i} ∏ i ∈ I ℓ i − w i i ∈ I i\in I i ∈ I n w i / 2 ≥ 2 \sqrt{nw_i/2}\ge2 n w i /2 ≥ 2 ℓ i ≥ 1 2 n w i / 2 = n w i / 8 \ell_i\ge\frac{1}{2}\sqrt{nw_i/2}=\sqrt{nw_i}/8 ℓ i ≥ 2 1 n w i /2 = n w i /8 i ∉ I i\notin I i ∈ / I 1 ≥ n w i / 8 1\ge\sqrt{nw_i}/8 1 ≥ n w i /8
∏ i ∈ I ℓ i w i ≥ ∏ i ∈ N ( n w i / 8 ) w i / 2 = Γ ( w ) 8 . \prod_{i\in I}\ell_i^{w_i}\ge\prod_{i\in N}(nw_i/8)^{w_i/2}=\frac{\Gamma(w)}{\sqrt{8}}. i ∈ I ∏ ℓ i w i ≥ i ∈ N ∏ ( n w i /8 ) w i /2 = 8 Γ ( w ) . This also covers I = ∅ I=\varnothing I = ∅
The basic instance also illustrates how an individual agent’s loss affects the logarithmic objective. The special agent has value one in each of its fractional configurations and value 1 / ℓ 1/\ell 1/ ℓ ω ln ℓ \omega\ln\ell ω ln ℓ ( ln ℓ ) / n (\ln\ell)/n ( ln ℓ ) / n Γ ( w ) = 1 \Gamma(w)=1 Γ ( w ) = 1
AI Disclosure
The main algorithmic ideas in this paper were contributed by GPT-5.6, GPT-6, GPT-5.6 Sol, and GPT-6-Astra (OpenAI), referred to below as AI. The human authors’ only direct contribution to the mathematical constructions was a hard instance for the configuration LP with XOS valuations; AI subsequently extended the analysis to subadditive valuations. The authors initially used AI to obtain an O ( n polylog n ) O(\sqrt{n}\operatorname{polylog} n) O ( n polylog n ) O ( n ) O(\sqrt{n}) O ( n )
Acknowledgment
The work of Ruilong Zhang is supported by the National Natural Science Foundation of China (No. 62602540) and City University of Hong Kong (Dongguan) start-up funding (No. R002026G003). The work of Yuhang Chen, Yuda Feng, Weijiang Hu and Shi Li is supported by State Key Laboratory for Novel Software Technology, New Cornerstone Science Foundation, and Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (No.JYB2025XDXM118).
References
Computing configuration solution for max-min allocation
Bansal and Sviridenko [18 ] used knapsack separation for the additive max-min configuration LP. Bamas, Garg, and Rohwedder [11 Theorem 2] used approximate knapsack separation for restricted submodular valuations, as shown in their full version [10 Appendix B.1] . We adapt this argument to agent-specific valuations and an arbitrary budgeted value-maximization routine. The rational item prices let us enforce a strict budget without losing a further constant factor. This gives Lemma 3.4 by using the submodular knapsack algorithm of Sviridenko [63 ] or the subadditive demand-query algorithm of Badanidiyuru, Dobzinski, and Oren [6 ] . In both cases the resulting solution satisfies (2) and (3) exactly.
Lemma A.1. Fix a rational constant β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ] t > 0 t > 0 t > 0 β t \beta t β t t t t v i ( S ) v_i(S) v i ( S ) i i i S ⊆ M S \subseteq M S ⊆ M
Then, for every rational η > 0 \eta> 0 η > 0 T L P = 0 T_{\mathrm{LP}} = 0 T LP = 0
T > β 1 + η T L P . T > \frac{\beta}{1+\eta}T_{\mathrm{LP}}. T > 1 + η β T LP . The running time is polynomial in the input encoding length and 1 / η 1/\eta 1/ η β \beta β
Proof of Lemma A.1 . We first construct a procedure that, for a given target t > 0 t > 0 t > 0 t t t t / β t/\beta t / β
Fix t > 0 t > 0 t > 0 ∑ S y i , S = 1 \sum_{S} y_{i,S} = 1 ∑ S y i , S = 1 i i i ∑ S y i , S ≥ λ \sum_{S} y_{i,S} \ge\lambda ∑ S y i , S ≥ λ λ \lambda λ C i ( t ) = { S ⊆ M : v i ( S ) ≥ t } C_i(t) = \{S \subseteq M : v_i(S) \ge t\} C i ( t ) = { S ⊆ M : v i ( S ) ≥ t }
maximize λ subject to ∑ S ∈ C i ( t ) y i , S ≥ λ ( i ∈ N ) , ∑ i ∈ N ∑ S ∈ C i ( t ) j ∈ S y i , S ≤ 1 ( j ∈ M ) , y ≥ 0 , λ ∈ R . \begin{aligned}
\text{maximize}\quad& \lambda\\
\text{subject to}\quad& \sum_{S \in C_i(t)} y_{i,S} \ge\lambda&& (i \in N),\\
& \sum_{i \in N} \sum_{\substack{S \in C_i(t)\\j\in S}} y_{i,S} \le1 && (j \in M),\\
& y \ge0,\quad\lambda\in\mathbb{R}.
\end{aligned} maximize subject to λ S ∈ C i ( t ) ∑ y i , S ≥ λ i ∈ N ∑ S ∈ C i ( t ) j ∈ S ∑ y i , S ≤ 1 y ≥ 0 , λ ∈ R . ( i ∈ N ) , ( j ∈ M ) , The configuration LP at target t t t 1 1 1 λ ≥ 1 \lambda\ge1 λ ≥ 1 1 1 1
Writing p ( S ) = ∑ j ∈ S p j p(S) = \sum_{j \in S} p_j p ( S ) = ∑ j ∈ S p j
minimize ∑ j ∈ M p j subject to ∑ i ∈ N z i = 1 , p ≥ 0 , z ≥ 0 , p ( S ) ≥ z i ( i ∈ N , S ∈ C i ( t ) ) . (52) \begin{aligned}
\text{minimize}\quad& \sum_{j \in M} p_j \\
\text{subject to}\quad& \sum_{i \in N} z_i = 1,\quad p \ge0,\quad z \ge0,\\
& p(S) \ge z_i && (i \in N,\ S \in C_i(t)). \tag*{(52)}
\end{aligned} minimize subject to j ∈ M ∑ p j i ∈ N ∑ z i = 1 , p ≥ 0 , z ≥ 0 , p ( S ) ≥ z i ( i ∈ N , S ∈ C i ( t )) . (52) We next describe how to test a rational candidate ( z , p ) (z,p) ( z , p ) ∑ i z i = 1 \sum_i z_i = 1 ∑ i z i = 1 p , z ≥ 0 p,z \ge0 p , z ≥ 0 Q Q Q ζ = 1 / Q \zeta= 1/Q ζ = 1/ Q Q Q Q ( z , p ) (z,p) ( z , p ) ζ \zeta ζ
p ( S ) < z i ⟹ p ( S ) ≤ z i − ζ . p(S) < z_i \quad\Longrightarrow\quad p(S) \le z_i - \zeta. p ( S ) < z i ⟹ p ( S ) ≤ z i − ζ . For each agent i i i z i > 0 z_i > 0 z i > 0 p j p_j p j z i − ζ z_i - \zeta z i − ζ t / β t/\beta t / β z i ≥ ζ z_i \ge\zeta z i ≥ ζ D D D v i ( D ) ≥ t v_i(D) \ge t v i ( D ) ≥ t D ∈ C i ( t ) D \in C_i(t) D ∈ C i ( t )
p ( D ) ≤ z i − ζ < z i , p(D) \le z_i - \zeta< z_i, p ( D ) ≤ z i − ζ < z i , so D D D (52) . Suppose that no call returns a set of value at least t t t S ∈ C i ( t / β ) S \in C_i(t/\beta) S ∈ C i ( t / β ) p ( S ) ≥ z i p(S) \ge z_i p ( S ) ≥ z i z i − ζ z_i - \zeta z i − ζ β ( t / β ) = t \beta(t/\beta) = t β ( t / β ) = t z i = 0 z_i = 0 z i = 0 p ≥ 0 p \ge0 p ≥ 0 t t t ( z , p ) (z,p) ( z , p ) t / β t/\beta t / β
To recover an exactly feasible configuration solution, we use a uniform bound on the denominators of optima of finite restricted packing LPs. Set d = n + m + 2 d = n + m + 2 d = n + m + 2 H 0 = 2 d 2 H_0 = 2^{d^2} H 0 = 2 d 2 { − 1 , 0 , 1 } \{-1,0,1\} { − 1 , 0 , 1 } n + m + 1 n + m + 1 n + m + 1 H 0 H_0 H 0 1 1 1 1 − 1 / H 0 1 - 1/H_0 1 − 1/ H 0
Run the rational feasibility algorithm of Grötschel, Lovász, and Schrijver [40 Theorem 6.4.1] , using the explicit dual constraints, the configuration tests above, and the additional bound
∑ j ∈ M p j ≤ 1 − 1 2 H 0 . (53) \sum_{j \in M} p_j \le1 - \frac{1}{2H_0}. \tag*{(53)} j ∈ M ∑ p j ≤ 1 − 2 H 0 1 . (53) These explicit constraints place all coordinates in [ 0 , 1 ] [0,1] [ 0 , 1 ] ∑ i z i = 1 \sum_i z_i = 1 ∑ i z i = 1
If the procedure finds a candidate accepted by all tests, this candidate is feasible for the dual at target t / β t/\beta t / β 1 1 1 1 1 1 t / β t/\beta t / β
Otherwise the feasibility algorithm reports an empty polyhedron. The recorded cuts and the explicit constraints, including (53) , already form an infeasible system. Indeed, every oracle reply in this run strictly separated its query from this subsystem, so the same replies constitute a valid execution of the exact feasibility algorithm for the subsystem. Here and below we test the algorithm’s final candidate as well if it returns one. Consider the restricted packing LP on exactly these configurations, and let λ ∗ \lambda^* λ ∗ 1 − 1 / ( 2 H 0 ) 1 - 1/(2H_0) 1 − 1/ ( 2 H 0 )
λ ∗ > 1 − 1 2 H 0 . \lambda^* > 1 - \frac{1}{2H_0}. λ ∗ > 1 − 2 H 0 1 . The denominator bound rules out λ ∗ < 1 \lambda^* < 1 λ ∗ < 1 λ ∗ ≤ 1 − 1 / H 0 \lambda^* \le1 - 1/H_0 λ ∗ ≤ 1 − 1/ H 0 λ ∗ ≥ 1 \lambda^* \ge1 λ ∗ ≥ 1 t t t t t t
It remains to choose the target. Let σ \sigma σ § 12 .§ 1 , and let U = min i v i ( M ) U = \min_i v_i(M) U = min i v i ( M ) U = 0 U = 0 U = 0 T L P = 0 T_{\mathrm{LP}} = 0 T LP = 0 t = U t = U t = U T = t T = t T = t t / β t/\beta t / β t t t t / ( 1 + η ) t/(1+\eta) t / ( 1 + η ) t ≤ β 2 − σ t \le\beta2^{-\sigma} t ≤ β 2 − σ T L P = 0 T_{\mathrm{LP}} = 0 T LP = 0
Suppose that the first configuration solution is returned with objective value T < U T < U T < U ( 1 + η ) T (1+\eta)T ( 1 + η ) T ( 1 + η ) T / β (1+\eta)T/\beta ( 1 + η ) T / β
T L P ≤ ( 1 + η ) T β , and hence T > β 1 + η T L P . T_{\mathrm{LP}} \le\frac{(1+\eta)T}{\beta},
\qquad\text{and hence}\qquad
T > \frac{\beta}{1+\eta}T_{\mathrm{LP}}. T LP ≤ β ( 1 + η ) T , and hence T > 1 + η β T LP . If the first call returns a solution at T = U T = U T = U T L P ≤ U T_{\mathrm{LP}} \le U T LP ≤ U U > 0 U > 0 U > 0 β / ( 1 + η ) < 1 \beta/(1+\eta) < 1 β / ( 1 + η ) < 1
Finally, the encoding bound in Appendix § 12 .§ 1 implies that every positive valuation is at least 2 − σ 2^{-\sigma} 2 − σ U ≤ 2 σ U \le2^\sigma U ≤ 2 σ T L P > 0 T_{\mathrm{LP}} > 0 T LP > 0 T L P ≥ 2 − σ T_{\mathrm{LP}} \ge2^{-\sigma} T LP ≥ 2 − σ t ≤ β 2 − σ t \le\beta2^{-\sigma} t ≤ β 2 − σ t / β t/\beta t / β t t t T L P = 0 T_{\mathrm{LP}} = 0 T LP = 0 1 + ⌈ log 1 + η ( 2 2 σ / β ) ⌉ 1 + \lceil\log_{1+\eta}(2^{2\sigma}/\beta)\rceil 1 + ⌈ log 1 + η ( 2 2 σ / β )⌉ σ \sigma σ β \beta β 1 / η 1/\eta 1/ η 1 / η 1/\eta 1/ η β \beta β
Submodular valuations. For monotone submodular valuations, Sviridenko [63 Theorem 1] gives a ( 1 − 1 / e ) (1 - 1/e) ( 1 − 1/ e ) 1 − 1 / e > 1 / 3 1 - 1/e > 1/3 1 − 1/ e > 1/3 Lemma A.1 with β = 1 / 3 \beta= 1/3 β = 1/3
Subadditive valuations. For subadditive valuations, we use ordinary demand queries. Under the bit bound, these can also implement restricted demand queries and exact value evaluation; see Appendix § 9 .
Lemma A.2. For normalized monotone subadditive valuations, ordinary demand queries implement the budgeted routine of Lemma A.1 with β = 1 / 3 \beta= 1/3 β = 1/3
Proof. Badanidiyuru, Dobzinski, and Oren [6 ] give a ( 2 + ϵ ) (2+\epsilon) ( 2 + ϵ ) ϵ > 0 \epsilon> 0 ϵ > 0 ϵ = 1 / 2 \epsilon= 1/2 ϵ = 1/2 2 t / 5 2t/5 2 t /5 t t t
Proof of Lemma 3.4 . Apply Lemma A.1 with β = 1 / 3 \beta= 1/3 β = 1/3 η = 1 \eta= 1 η = 1 Lemma A.2 for subadditive valuations. This gives T > T L P / 6 T > T_{\mathrm{LP}}/6 T > T LP /6 Lemma A.1 are value queries for submodular valuations. For subadditive valuations, they are implemented by ordinary demand queries under the bit bound; see Appendix § 9 .
Restriction and exact value evaluation via ordinary demand queries
Blumrosen and Nisan [16 Lemmas 1 and 2] simulate a value query by recovering marginal values from demand queries and summing them. We give the finite prices and precision needed under the encoding convention of Appendix § 12 .§ 1 , with σ \sigma σ
Restricted demand queries. To restrict a query to R ⊆ M R \subseteq M R ⊆ M R R R 2 σ + 1 2^\sigma+ 1 2 σ + 1 v i ( M ) ≤ 2 σ v_i(M) \le2^\sigma v i ( M ) ≤ 2 σ R R R
Exact value evaluation. For j ∈ S j \in S j ∈ S d = v i ( S ) − v i ( S ∖ { j } ) d = v_i(S) - v_i(S \setminus\{j\}) d = v i ( S ) − v i ( S ∖ { j }) S S S j j j t t t S S S j j j d ≥ t d \ge t d ≥ t j j j d ≤ t d \le t d ≤ t
Under our bit bound, 0 ≤ d ≤ 2 σ 0 \le d \le2^\sigma 0 ≤ d ≤ 2 σ d d d 2 2 σ 2^{2\sigma} 2 2 σ 2 2 σ 2^{2\sigma} 2 2 σ 2 − 4 σ 2^{-4\sigma} 2 − 4 σ O ( σ ) O(\sigma) O ( σ ) d d d 2 − 4 σ − 2 2^{-4\sigma-2} 2 − 4 σ − 2 d d d 2 2 σ 2^{2\sigma} 2 2 σ [40 Theorem 5.1.9] . Summing the successive marginal values along any ordering of S S S v i ( S ) v_i(S) v i ( S ) O ( ∣ S ∣ σ ) O(|S|\sigma) O ( ∣ S ∣ σ ) v i ( ∅ ) = 0 v_i(\varnothing) = 0 v i ( ∅ ) = 0
Finite implementation of NSW rounding
The proof in § 4 uses exact matching marginals to simplify the analysis. Here we give a polynomial-time implementation using rational edge weights. We sample weighted matchings using a permanent approximation scheme [45 ] and calibrate their edge weights using the maximum-entropy dual potential studied by Singh and Vishnoi [61 ] . Straszak and Vishnoi [62 Theorem 15] also handle marginal vectors on the boundary of the feasible region, assuming an evaluation oracle for the generating polynomial. In our setting, however, the matching partition function is available only through randomized approximations. We therefore give a rational coordinate-update algorithm and account for the error in its sampling calls.
Lemma C.1. Let x x x η > 0 \eta> 0 η > 0 ρ > 0 \rho> 0 ρ > 0 E = { ( i , j ) : x i j > 0 } E = \{(i,j) : x_{ij} > 0\} E = {( i , j ) : x ij > 0 } 1 − ρ 1 - \rho 1 − ρ x ′ x' x ′
∥ x ′ − x ∥ 1 ≤ η . (54) \lVert x' - x \rVert_1 \le\eta. \tag*{(54)} ∥ x ′ − x ∥ 1 ≤ η . (54) For every weight vector returned by the procedure and every ε > 0 \varepsilon> 0 ε > 0 E E E ε \varepsilon ε 1 / η 1/\eta 1/ η 1 / ε 1/\varepsilon 1/ ε log ( 1 / ρ ) \log(1/\rho) log ( 1/ ρ )
We first analyze the exact Gibbs distribution associated with a fixed weight vector returned by the procedure. We then account for the error introduced by approximate sampling.
Approximate sampling and rational calibration
Sampling a Gibbs matching. We use the nonnegative-permanent approximation scheme of Jerrum, Sinclair, and Vigoda [45 Theorem 1.1] . Given a rational nonnegative matrix, it estimates the permanent to relative error α \alpha α ζ \zeta ζ 1 / α 1/\alpha 1/ α log ( 1 / ζ ) \log(1/\zeta) log ( 1/ ζ ) r r r s s s r ≤ s r \le s r ≤ s s − r s-r s − r ( s − r ) ! (s-r)! ( s − r )!
We adapt the counting-to-generation reduction of Jerrum, Valiant, and Vazirani [46 Theorem 6.3] using weighted residual partition functions. Fix the edge weights and process the agents one at a time. Conditional on the assignments already made, the probability of assigning an available item j j j i i i
λ i j Z r e m a i n i n g r o w s , r e m a i n i n g c o l u m n s ∖ { j } . \lambda_{ij} Z_{\mathrm{remaining\ rows,\ remaining\ columns}\setminus\{j\}}. λ ij Z remaining rows , remaining columns ∖ { j } . A matching computation identifies the choices that can be extended to a covering matching. For each such choice, approximate its positive partition function to relative error ε / ( 32 n ) \varepsilon/(32n) ε / ( 32 n ) ε / ( 8 n ) \varepsilon/(8n) ε / ( 8 n ) ε / 8 \varepsilon/8 ε /8
Choose the failure bounds so that the total failure probability of the polynomially many permanent estimates is at most ε / 4 \varepsilon/4 ε /4 § 12 .§ 2 , with total abort probability at most ε / 4 \varepsilon/4 ε /4 E E E ε \varepsilon ε
Calibrating the marginals. Write d = ∣ E ∣ d = \lvert E\rvert d = ∣ E ∣ 0 < η , ρ < 1 0 < \eta, \rho< 1 0 < η , ρ < 1
γ = η 4 d , T c a l = ⌈ 8 η m γ 2 ⌉ + 1 , s = ⌈ 32 γ 2 ⌉ ⌈ log 2 2 d T c a l ρ ⌉ . (55) \gamma= \frac{\eta}{4d}, \qquad T_{\mathrm{cal}} = \left\lceil\frac{8\eta m}{\gamma^2} \right\rceil+ 1, \qquad s = \left\lceil\frac{32}{\gamma^2} \right\rceil\left\lceil\log_2 \frac{2dT_{\mathrm{cal}}}{\rho} \right\rceil. \tag*{(55)} γ = 4 d η , T cal = ⌈ γ 2 8 η m ⌉ + 1 , s = ⌈ γ 2 32 ⌉ ⌈ log 2 ρ 2 d T cal ⌉ . (55) Initialize λ e = 1 \lambda_e = 1 λ e = 1 T c a l T_{\mathrm{cal}} T cal s s s γ / 8 \gamma/8 γ /8 p ^ e \widehat p_e p e e e e ∣ p ^ e − x e ∣ ≤ γ \lvert\widehat p_e - x_e\rvert\le\gamma ∣ p e − x e ∣ ≤ γ 1 + γ / 2 1+\gamma/2 1 + γ /2 p ^ e < x e \widehat p_e < x_e p e < x e 1 − γ / 2 1-\gamma/2 1 − γ /2 p ^ e > x e \widehat p_e > x_e p e > x e
Let p e p_e p e e e e γ / 8 \gamma/8 γ /8
Pr [ max e ∣ p ^ e − p e ∣ > γ / 4 ] ≤ 2 d exp ( − s γ 2 / 32 ) ≤ ρ / T c a l . \Pr\left[\max_e \lvert\widehat p_e-p_e\rvert> \gamma/4\right] \le2d\exp(-s\gamma^2/32) \le\rho/T_{\mathrm{cal}}. Pr [ e max ∣ p e − p e ∣ > γ /4 ] ≤ 2 d exp ( − s γ 2 /32 ) ≤ ρ / T cal . This bound holds conditional on all preceding iterations. A union bound over the iterations therefore shows that all empirical estimates are accurate to within γ / 4 \gamma/4 γ /4 1 − ρ 1-\rho 1 − ρ
To analyze progress, use the maximum-entropy dual objective [61 ] , evaluated at the logarithms of the edge weights, as the potential
Φ ( λ ) = ln Z λ − ∑ e x e ln λ e \Phi(\lambda) = \ln Z_{\lambda} - \sum_{e} x_e \ln\lambda_e Φ ( λ ) = ln Z λ − e ∑ x e ln λ e By integrality of the bipartite matching polytope, x x x E E E ∑ e x e ln λ e \sum_e x_e \ln\lambda_e ∑ e x e ln λ e ln Z λ \ln Z_\lambda ln Z λ Φ ≥ 0 \Phi\ge0 Φ ≥ 0 Φ ( 1 ) = ln ∣ M ∣ ≤ n ln m ≤ n m \Phi(1) = \ln|\mathcal{M}| \le n \ln m \le nm Φ ( 1 ) = ln ∣ M ∣ ≤ n ln m ≤ nm 1 + u 1+u 1 + u Z λ ( 1 + u p e ) Z_\lambda(1+u p_e) Z λ ( 1 + u p e ) ∣ u ∣ ≤ 1 / 2 |u| \le1/2 ∣ u ∣ ≤ 1/2
Δ Φ = ln ( 1 + u p e ) − x e ln ( 1 + u ) ≤ u ( p e − x e ) + u 2 \Delta\Phi= \ln(1+u p_e) - x_e \ln(1+u) \le u(p_e-x_e) + u^2 ΔΦ = ln ( 1 + u p e ) − x e ln ( 1 + u ) ≤ u ( p e − x e ) + u 2 Suppose the empirical estimates are accurate and the stopping condition is not satisfied. For the chosen edge, p e − x e p_e-x_e p e − x e p ^ e − x e \widehat{p}_e-x_e p e − x e 3 γ / 4 3\gamma/4 3 γ /4 u = ± γ / 2 u=\pm\gamma/2 u = ± γ /2 Φ \Phi Φ γ 2 / 8 \gamma^2/8 γ 2 /8 Φ \Phi Φ n m nm nm T c a l T_{\mathrm{cal}} T cal
∥ p − x ∥ 1 ≤ d ( γ + γ / 4 ) = 5 η / 16 < η . \lVert p-x\rVert_1 \le d(\gamma+\gamma/4) = 5\eta/16 < \eta. ∥ p − x ∥ 1 ≤ d ( γ + γ /4 ) = 5 η /16 < η . Together with the preceding accuracy bound, this proves that calibration succeeds with probability at least 1 − ρ 1-\rho 1 − ρ
Every weight returned by the procedure has the exact rational form
λ e = ( 1 + γ / 2 ) u e ( 1 − γ / 2 ) v e , u e + v e ≤ T c a l . \lambda_e = (1+\gamma/2)^{u_e}(1-\gamma/2)^{v_e}, \qquad u_e+v_e \le T_{\mathrm{cal}}. λ e = ( 1 + γ /2 ) u e ( 1 − γ /2 ) v e , u e + v e ≤ T cal . Its encoding length is polynomial even if some empirical estimates are inaccurate. This proves Lemma C.1 and supplies the finite Gibbs distributions whose marginals converge to x x x Lemma 4.2 .
Stability of the rounding guarantee
Let σ \sigma σ § 12 .§ 1 . For the rounding procedure in § 4.2 , set
η = 1 64 ( σ + 1 ) ( m + 1 ) 3 . (56) \eta= \frac{1}{64(\sigma+1)(m+1)^3}. \tag*{(56)} η = 64 ( σ + 1 ) ( m + 1 ) 3 1 . (56) Use calibration failure bound ρ = η \rho=\eta ρ = η ρ = min { η , δ / 2 } \rho=\min\{\eta,\delta/2\} ρ = min { η , δ /2 } 1 − δ 1-\delta 1 − δ η \eta η
The total squared loss. Fix a successfully calibrated weight vector, and let x ′ x' x ′ b j ′ = ∑ i x i j ′ b'_j=\sum_i x'_{ij} b j ′ = ∑ i x ij ′ f j ′ = 1 − b j ′ f'_j=1-b'_j f j ′ = 1 − b j ′ ∣ b j ′ − b j ∣ ≤ η |b'_j-b_j|\le\eta ∣ b j ′ − b j ∣ ≤ η ∑ j b j ′ = n \sum_j b'_j=n ∑ j b j ′ = n B B B
Call a configuration exceptional if its tail contains an item with f j ′ < 2 η f'_j<2\eta f j ′ < 2 η (25) bounds the total mass of configurations containing it in their tails by f j ′ < 2 η f'_j<2\eta f j ′ < 2 η m m m 2 m η 2m\eta 2 m η v i ( S ) ≤ m v i , S ≤ m D i , S ( B ) v_i(S)\le m v_{i,S}\le mD_{i,S}(B) v i ( S ) ≤ m v i , S ≤ m D i , S ( B )
2 m η ⋅ m 2 = 2 m 3 η ≤ 1. 2m\eta\cdot m^2 = 2m^3\eta\le1. 2 m η ⋅ m 2 = 2 m 3 η ≤ 1. For every item in a nonexceptional tail, we have f j ′ ≥ f j − η ≥ f j / 2 > 0 f'_j \ge f_j-\eta\ge f_j/2 > 0 f j ′ ≥ f j − η ≥ f j /2 > 0 P i , S ′ = ∑ j ∈ T i , S b j ′ / f j ′ P'_{i,S}=\sum_{j\in T_{i,S}} b'_j/f'_j P i , S ′ = ∑ j ∈ T i , S b j ′ / f j ′
∑ ( i , S ) n o n e x c e p t i o n a l y i , S P i , S ′ ≤ ∑ j : f j ≥ 2 η b j ′ f j ′ f j ≤ 2 ∑ j b j ′ = 2 n . \sum_{(i,S)\ \mathrm{nonexceptional}} y_{i,S}P'_{i,S}\le\sum_{j:f_j\ge2\eta}\frac{b'_j}{f'_j}f_j\le2\sum_j b'_j=2n. ( i , S ) nonexceptional ∑ y i , S P i , S ′ ≤ j : f j ≥ 2 η ∑ f j ′ b j ′ f j ≤ 2 j ∑ b j ′ = 2 n . The negative-correlation inequalities hold for this exact Gibbs distribution with item marginals b j ′ b'_j b j ′ Lemma 4.5 to the nonexceptional configurations and sum the resulting bounds as in the proof of Lemma 4.6 . Adding the contribution of the exceptional configurations gives
∑ i , S y i , S E B ( v i ( S ) D i , S ( B ) ) 2 ≤ C n . (57) \sum_{i,S}y_{i,S}\mathbb{E}_{B}\left(\frac{v_i(S)}{D_{i,S}(B)}\right)^2\le Cn. \tag*{(57)} i , S ∑ y i , S E B ( D i , S ( B ) v i ( S ) ) 2 ≤ C n . (57) This distinction is used only in the analysis; the algorithm rounds the full configuration solution.
The singleton buffer. The coupling with a reference set in Lemma 4.2 , including its one-item difference bound, holds for every fixed Gibbs distribution. The proof of Lemma 4.7 therefore still applies, except that agent i i i x i ′ x'_i x i ′ x i x_i x i Z ∗ Z^* Z ∗ (37) lies in [ − σ ln 2 , σ ln 2 ] [-\sigma\ln2,\sigma\ln2] [ − σ ln 2 , σ ln 2 ] x i ′ x'_i x i ′ x i x_i x i Z ∗ Z^* Z ∗ 2 σ ln 2 TV ( x i , x i ′ ) 2\sigma\ln2\operatorname{TV}(x_i,x'_i) 2 σ ln 2 TV ( x i , x i ′ ) x i x_i x i Lemma 4.4 . Since
∑ i w i TV ( x i , x i ′ ) ≤ 1 2 ∥ x − x ′ ∥ 1 ≤ η / 2 , \sum_i w_i\operatorname{TV}(x_i,x'_i)\le\frac{1}{2}\lVert x-x'\rVert_1\le\eta/2, i ∑ w i TV ( x i , x i ′ ) ≤ 2 1 ∥ x − x ′ ∥ 1 ≤ η /2 , applying that lemma and summing over the agents gives
E ln NSW w ( A ) ≥ ∑ i , S w i y i , S E B ln D i , S ( B ) − C 0 − σ ln 2 η . (58) \mathbb{E}\ln\operatorname{NSW}_w(A)\ge\sum_{i,S}w_i y_{i,S}\mathbb{E}_B\ln D_{i,S}(B)-C_0-\sigma\ln2\eta. \tag*{(58)} E ln NSW w ( A ) ≥ i , S ∑ w i y i , S E B ln D i , S ( B ) − C 0 − σ ln 2 η . (58) Combining (57) with the Jensen argument in (47) yields the bound on expected logarithmic welfare for the exact Gibbs distribution of every successfully calibrated weight vector.
Sampling errors and running time. Every output of the implementation gives each agent a head of positive value. Its logarithmic welfare therefore always lies in [ − σ ln 2 , σ ln 2 ] [-\sigma\ln2,\sigma\ln2] [ − σ ln 2 , σ ln 2 ] η \eta η 2 σ ln 2 η 2\sigma\ln2\eta 2 σ ln 2 η ρ ≤ η \rho\le\eta ρ ≤ η 2 σ ln 2 η 2\sigma\ln2\eta 2 σ ln 2 η (58) , these losses total O ( σ η ) = O ( 1 ) O(\sigma\eta)=O(1) O ( σ η ) = O ( 1 )
The limit on tree exploration is already included in Lemma 3.10. We also limit its rational label-sampling calls as in Appendix § 12 .§ 2 , so that the total abort probability across all guiding-tree rounding calls is at most η \eta η O ( σ η ) O(\sigma\eta) O ( σ η ) K + 1 K+1 K + 1
All procedures run in worst-case polynomial time: 1 / η 1/\eta 1/ η σ \sigma σ m m m O ( log m ) O(\log m) O ( log m ) Theorem 4.1 and justifies reusing one calibration across the trials in Theorem 4.10 .
Computing a configuration solution for Nash social welfare
Feng and Li [34 ] used approximate dual separation to solve the logarithmic configuration LP for additive valuations. Feng, Hu, Li, and Zhang [33 ] implemented this approach for submodular valuations using a knapsack approximation. To prove Lemma 4.9 for subadditive valuations, we use the demand-query knapsack routine of Lemma A.2 and the exact value-evaluation procedure in Appendix § 9 . We approximate the logarithmic coefficients by rationals and track the resulting error when recovering feasible primal and dual solutions.
Proof of Lemma 4.9 . Retain the columns corresponding to the positive singleton matching found in Lemma 4.8 . For each agent i i i S S S v i ( S ) > 0 v_i(S)>0 v i ( S ) > 0
∣ ℓ ^ i ( S ) − w i ln v i ( S ) ∣ ≤ w i / 64. \left|\widehat{\ell}_i(S)-w_i\ln v_i(S)\right|\leq w_i/64. ℓ i ( S ) − w i ln v i ( S ) ≤ w i /64. Reuse this approximation whenever the same pair ( i , S ) (i,S) ( i , S ) w i ln v i ( S ) w_i\ln v_i(S) w i ln v i ( S ) ℓ ^ i ( S ) \widehat{\ell}_i(S) ℓ i ( S ) σ \sigma σ
Approximate separation. Consider a rational candidate ( z , p ) (z,p) ( z , p ) p ≥ 0 p\geq0 p ≥ 0 i i i V = 2 k V=2^k V = 2 k − σ ≤ k ≤ σ -\sigma\leq k\leq\sigma − σ ≤ k ≤ σ q q q γ \gamma γ
∣ q − ln ( V / 3 ) ∣ ≤ 1 / 32 , γ = w i q − z i − w i / 16. \left|q-\ln(V/3)\right|\leq1/32,\qquad\gamma=w_iq-z_i-w_i/16. ∣ q − ln ( V /3 ) ∣ ≤ 1/32 , γ = w i q − z i − w i /16. If γ ≥ 0 \gamma\geq0 γ ≥ 0 Lemma A.2 with item costs p p p γ \gamma γ V V V D D D V / 3 V/3 V /3 p ( D ) ≤ γ p(D)\leq\gamma p ( D ) ≤ γ
ℓ ^ i ( D ) − z i − p ( D ) ≥ w i ( 1 16 − 1 32 − 1 64 ) > 0. \widehat{\ell}_i(D)-z_i-p(D)\geq w_i\left(\frac{1}{16}-\frac{1}{32}-\frac{1}{64}\right)>0. ℓ i ( D ) − z i − p ( D ) ≥ w i ( 16 1 − 32 1 − 64 1 ) > 0. Thus, the constraint indexed by ( i , D ) (i,D) ( i , D )
Now suppose that the original dual constraint in (48) for some pair ( i , S ) (i,S) ( i , S ) 2 w i 2w_i 2 w i V = 2 k V=2^k V = 2 k v i ( S ) / 2 < V ≤ v i ( S ) v_i(S)/2<V\leq v_i(S) v i ( S ) /2 < V ≤ v i ( S )
γ − p ( S ) > w i ( 2 − ln 6 − 3 32 ) > 0. \gamma-p(S)>w_i\left(2-\ln6-\frac{3}{32}\right)>0. γ − p ( S ) > w i ( 2 − ln 6 − 32 3 ) > 0. Hence S S S V V V V / 3 V/3 V /3 z i z_i z i z i + 2 w i z_i+2w_i z i + 2 w i
Recovering an exactly feasible primal solution. Include the positive singleton-matching columns in every restricted primal, ensuring that it is feasible and bounded. Its constraint matrix has entries in { − 1 , 0 , 1 } \{-1,0,1\} { − 1 , 0 , 1 }
We perform bisection on the unshifted dual objective level, using the rational feasibility algorithm [40 Theorem 6.4.1] and the recorded-cut argument of Lemma A.1 . At an accepted level, the separator returns a candidate that becomes feasible for the original dual after adding 2 w i 2w_i 2 w i z i z_i z i
We start with the accepted upper level σ + 1 \sigma+ 1 σ + 1 z i = w i ( σ + 1 ) z_i = w_i(\sigma+ 1) z i = w i ( σ + 1 ) p = 0 p = 0 p = 0 − σ − 2 -\sigma- 2 − σ − 2 1 / 64 1/64 1/64
Collect all generated columns and solve the restricted rational primal exactly. Its objective is at least the final rejected level. By the row constraints (2) and ∑ i w i = 1 \sum_i w_i = 1 ∑ i w i = 1 1 / 64 1/64 1/64
0 ≤ U ( z , p ) − L ( y ) ≤ 2 + 2 64 < 3 , 0 \le U(z,p) - L(y) \le2 + \frac{2}{64} < 3, 0 ≤ U ( z , p ) − L ( y ) ≤ 2 + 64 2 < 3 , where ( z , p ) (z,p) ( z , p ) (2) and (3) exactly, as required.
Computational conventions
Encoding
The finite-encoding convention in § 2 gives a known bound σ \sigma σ v i ( S ) v_i(S) v i ( S ) 2 σ 2^\sigma 2 σ [ 2 − σ , 2 σ ] [2^{-\sigma},2^\sigma] [ 2 − σ , 2 σ ] σ \sigma σ
Sampling from explicit rational distributions
In the rounding analyses, we sample exactly from explicitly given rational distributions. We describe how to implement these calls in worst-case polynomial time with an arbitrarily small additional failure probability.
For a distribution whose probabilities have common denominator Q Q Q ⌈ log 2 Q ⌉ \lceil\log_2 Q\rceil ⌈ log 2 Q ⌉ Q Q Q { 0 , … , Q − 1 } \{0,\ldots,Q-1\} { 0 , … , Q − 1 } 1 / 2 1/2 1/2
For a procedure making at most s ≥ 1 s \ge1 s ≥ 1 0 < δ < 1 0 < \delta< 1 0 < δ < 1 ⌈ log 2 ( s / δ ) ⌉ \lceil\log_2(s/\delta)\rceil ⌈ log 2 ( s / δ )⌉ δ \delta δ δ \delta δ O ( 1 + log ( s / δ ) ) O(1+\log(s/\delta)) O ( 1 + log ( s / δ ))
