arxiv: 2605.08859 · v1 · submitted 2026-05-09 · 💻 cs.GT

Recognition: 2 theorem links

· Lean Theorem

On MMS, APS and XOS

Uriel Feige, Vadim Grinberg

Authors on Pith no claims yet

Pith reviewed 2026-05-12 02:13 UTC · model grok-4.3

classification 💻 cs.GT

keywords MMSAPSXOS valuationsfair divisionindivisible goodsapproximation algorithmslarge n

0 comments

The pith

For sufficiently large numbers of agents, XOS valuations admit allocations exceeding a 1/4 approximation to both the maximin share and anyprice share.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper attempts to break the 1/4 approximation barrier for the maximin share in fair allocations of indivisible goods to agents with XOS valuations. It first solves the identical-valuation case by designing an algorithm that delivers more than 11/40 of the anyprice share to each agent. The authors then adapt this algorithm for agents with differing valuations and establish that the resulting allocation exceeds 1/4 of both the maximin share and anyprice share once the number of agents surpasses some finite threshold. A reader would care because prior work had only approached 1/4 from below, with the best general ratio at 4/17.

Core claim

The central discovery is that a modified allocation algorithm, inspired by the identical-valuation case where it achieves more than 11/40 of the APS, can be extended to heterogeneous XOS valuations to guarantee more than 1/4 of the MMS (and APS) for all sufficiently large numbers of agents n.

What carries the argument

A modified allocation algorithm that first guarantees more than 11/40 of the anyprice share for identical XOS valuations and is then adapted to heterogeneous valuations.

If this is right

Better than 1/4 approximations become possible for both MMS and APS when n is large.
The anyprice share serves as a stronger benchmark that can be used to prove MMS guarantees in the identical-valuation case.
Separating the identical and heterogeneous cases allows incremental improvement of the ratio over prior work.
The result applies uniformly to all n at or above some finite n0.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The result implies that any hardness results establishing 1/4 as a tight bound must be restricted to bounded n.
Similar algorithmic modifications could potentially improve bounds for neighboring valuation classes such as subadditive functions.
Computing an explicit value for the threshold n0 would allow direct verification of the guarantee on moderate-sized instances.

Load-bearing premise

The assumption that the modified algorithm preserves an approximation ratio strictly greater than 1/4 when moving from identical to different XOS valuations.

What would settle it

A specific instance with a fixed n larger than n0, m goods, and XOS valuations for which the best possible allocation gives some agent at most 1/4 of their MMS.

Figures

Figures reproduced from arXiv: 2605.08859 by Uriel Feige, Vadim Grinberg.

**Figure 1.** Figure 1: The function pt depends on the value of ρ, and also has a weak dependency on the value on n. Hence, the above plot applies for specific values of ρ and n, but its general form is the same for all ρ and large n. For a plot of pt when no item has value larger than ρ = 0.25 and n = 100, see [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

**Figure 2.** Figure 2: Numerical computation of values γ n n Values of n ≤ 10 were checked umerically by running a simple calculation program (see [PITH_FULL_IMAGE:figures/full_fig_p031_2.png] view at source ↗

**Figure 3.** Figure 3: Numerical computation of values γ n n The values n ≤ 100 were checked directly via a computer program in [PITH_FULL_IMAGE:figures/full_fig_p032_3.png] view at source ↗

read the original abstract

We consider allocations of a set of $m$ indivisible goods to $n$ agents of equal entitlements that have valuations from the class XOS. A previous sequence of works showed allocations that obtain an $\alpha$-approximation for the maximin share (MMS), for values of $\alpha$ that gradually approach $\frac{1}{4}$ from below (the currently known ratio is $\frac{4}{17}$). In this work we attempt to obtain ratios better than $\frac{1}{4}$, and manage to do so for sufficiently large $n$. Our methodology is to first investigate the gap between the anyprice share (APS) and the MMS when all agents have the same XOS valuations, for which we design an allocation algorithm and prove that each agent receives at least $\alpha > \frac{11}{40}$ times the APS. Then, we derive inspiration from this algorithm, and modify it so that it applies also when agents have different XOS valuations. Using this modified version, we show that for some sufficiently large $n_0$, there is an $\alpha$-MMS allocation (in fact, an $\alpha$-APS allocation) for every $n \geq n_0$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Feige and Grinberg get past the 1/4 MMS threshold for XOS valuations, but only for large n via an APS intermediate step.

read the letter

Feige and Grinberg get past the 1/4 MMS threshold for XOS valuations when the number of agents is large enough. They route through the anyprice share and first solve the identical-valuation case before adapting the algorithm for heterogeneous valuations. The result is an explicit improvement over the prior 4/17 bound, though it remains asymptotic in n. The paper does well by isolating the identical case and giving a concrete algorithm that achieves better than 11/40 of APS there. That part feels like a clean, self-contained contribution that builds directly on the sequence of MMS papers without circularity. The modification for different valuations keeps the same algorithmic skeleton, which makes the argument coherent and avoids inventing new machinery. The soft spot is the lack of an explicit n0 or a uniform ratio that works for all n. The heterogeneous step absorbs some loss for large n, but readers get no numerical sense of how large n needs to be or how much the ratio degrades in the transition. The abstract leaves the error analysis and exact construction details to the body, so the strength of the >1/4 claim rests on how tightly those bounds are proved. This paper is for people already following the MMS and XOS literature in algorithmic game theory. Anyone tracking approximation ratios for fair division of indivisible goods will want to see the APS detour and whether it can be made non-asymptotic. It deserves a serious referee. The claims are specific, the methodology is transparent, and the result addresses a concrete gap left by earlier work even if it does not close the problem for small n.

Referee Report

2 major / 2 minor

Summary. The paper claims to design an explicit allocation algorithm achieving an α-APS allocation with α > 11/40 when all agents have identical XOS valuations. It then modifies this algorithm to handle heterogeneous XOS valuations, proving that for all sufficiently large n there exists an α-APS (hence α-MMS) allocation with α > 1/4, improving on the prior best ratio of 4/17.

Significance. If the proofs hold, the result is significant: it is the first explicit super-1/4 approximation for MMS/APS under XOS valuations (for large n), obtained via a clean separation into identical and heterogeneous cases that uses APS as an intermediate benchmark. The explicit algorithm for the identical case and the asymptotic extension constitute a methodological advance that could extend to other subadditive classes.

major comments (2)

[§5] §5 (heterogeneous extension): the argument that the ratio loss from the identical-case algorithm (>11/40) can be absorbed to still exceed 1/4 for all n ≥ n0 is load-bearing for the main theorem, yet the manuscript provides no explicit scaling of the loss with n or a concrete lower bound on n0; without this the existence claim remains non-constructive and hard to compare with prior constant-ratio results.
[§3] §3, Theorem 2 (identical XOS algorithm): the charging scheme that yields α > 11/40 relies on a specific decomposition of XOS valuations into additive functions; the manuscript should explicitly state the numerical value of α obtained (rather than only the inequality) and verify that it is strictly larger than 11/40 by a margin sufficient to survive the heterogeneous modification.

minor comments (2)

[Introduction] The abstract and introduction should include a short table comparing the new ratios (11/40 and >1/4) against all previously published constants (4/17, 1/3, etc.) for both MMS and APS.
Notation for the modified algorithm in the heterogeneous case re-uses several symbols from the identical case without re-definition; a short nomenclature table would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the major comments point by point below.

read point-by-point responses

Referee: [§5] §5 (heterogeneous extension): the argument that the ratio loss from the identical-case algorithm (>11/40) can be absorbed to still exceed 1/4 for all n ≥ n0 is load-bearing for the main theorem, yet the manuscript provides no explicit scaling of the loss with n or a concrete lower bound on n0; without this the existence claim remains non-constructive and hard to compare with prior constant-ratio results.

Authors: We agree that an explicit scaling and concrete n0 would make the result more constructive and easier to compare with prior work. The heterogeneous proof implicitly bounds the loss from the identical-case ratio, but does not quantify it. In the revision we will derive an explicit O(1/n) bound on the loss term from the approximation error between the identical and heterogeneous cases, and state a concrete n0 (obtained by solving for when the loss drops below the margin above 1/4) such that the ratio exceeds 1/4 for all n ≥ n0. revision: yes
Referee: [§3] §3, Theorem 2 (identical XOS algorithm): the charging scheme that yields α > 11/40 relies on a specific decomposition of XOS valuations into additive functions; the manuscript should explicitly state the numerical value of α obtained (rather than only the inequality) and verify that it is strictly larger than 11/40 by a margin sufficient to survive the heterogeneous modification.

Authors: We will revise Theorem 2 and its proof to state the exact numerical value of α produced by the charging scheme (rather than only the inequality α > 11/40). The scheme yields a concrete constant strictly larger than 11/40; we will report this value and explicitly verify that the margin above 11/40 is sufficient to absorb the heterogeneous loss for all sufficiently large n, as required by the main theorem. revision: yes

Circularity Check

0 steps flagged

Derivation is self-contained; no circular steps identified

full rationale

The paper presents two distinct algorithmic constructions. First, an explicit algorithm is designed and analyzed for identical XOS valuations, directly proving an APS guarantee strictly above 11/40. Second, this algorithm is modified for heterogeneous valuations, with a separate argument showing that the resulting APS (hence MMS) ratio exceeds 1/4 for all sufficiently large n. Neither step reduces to a fitted parameter, self-definition, or load-bearing self-citation; both rest on explicit algorithmic analysis whose correctness is independent of the final claim. The existence of a finite n0 is a standard asymptotic statement and does not create circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard properties of the XOS valuation class and the relationship between APS and MMS; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption XOS valuations admit an APS that is at least as large as MMS and can be used to guide allocation construction
Invoked when moving from the identical-valuation APS guarantee to the heterogeneous MMS guarantee.

pith-pipeline@v0.9.0 · 5509 in / 1208 out tokens · 59835 ms · 2026-05-12T02:13:05.014460+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel (J uniqueness) unclear
We propose to use a greedy algorithm... define β(S) = ∑_B λ_B · v(B ∩ S)... Observation 2.1... p_t bounds via LP (Proposition 2.1)
IndisputableMonolith/Foundation/AlphaDerivationExplicit.lean alphaProvenanceCert unclear
Theorem 1.1... α > 11/40 for n ≥ n_α... asymptotic solution to 2(12α−3)ln(3α)=(1−3α)(3ln3−4)

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

[1]

there are at mostm+ 1bundles in the support of{(S,λS)}S∈S

work page
[2]

for everyS∈Swithλ S >0,v(S) = 1, andv(S) =v S(S)for some linear functionv S defined only on the items fromS

work page
[3]

efficient

every “minimal” bundle (one in which removing any item decreases its value) is a sub- bundle of someS∈S; Proof.For 1), consider the linear program representation of the APS-definition. For a value z≥0, letS z denote allS∈2M such thatv(S)≥z. We seek for the maximal value ofz such that the following LP has a feasible solution: the variables areλ S≥0 forS∈Sz...

work page
[4]

iftis even, there existt/2sub-bundlesB 1,...,Bt/2 ⊆Ssuch that for anyk∈[t/2], v(Bk∩M′)≥α, and for everyj∈S, itemjis contained inat most onesub-bundleB k. 21

work page
[5]

unify” them, replacinge,e′inSwith a combined item{e,e′}of value vS({e}∩M′) +v S({e′}∩M′) and treating bothe,e ′like a single item. This is a “virtual

iftis odd, there existtsub-bundlesB 1,...,Bt⊆Ssuch that for anyk∈[t],v(Bk∩M′)≥ α, and for everyj∈S, itemjis contained inat most twoof sub-bundlesB k. Proof.For a given setS, perform the following procedure: if two itemse,e ′have combined value vS({e,e′}∩M′)<α, we “unify” them, replacinge,e′inSwith a combined item{e,e′}of value vS({e}∩M′) +v S({e′}∩M′) and...

work page
[6]

ifS∈Si α, no sub-bundles of it contribute toµi (i.eB i α=∅)

work page
[7]

ifS∈Si 2α, thenS i∈Bi and it contributes exactly λS Λi toµi

work page
[8]

ifS∈Si 3α, then sub-bundles ofS i are inB i 3αand in total contribute exactly 3 2·λS Λi toµi

work page
[9]

As a result, ∑ B∈Bi µi B = ∑ B∈Biα µi B + ∑ B∈Bi 2α µi B + ∑ B∈Bi 3α µi B + ∑ B∈Bi 1 µi B = 1 Λi ( 0·Λi α+ 1·Λi 2α+ 3 2·Λi 3α+ 2·Λi 1 ) = 1

ifS∈Si 1, then sub-bundles ofS i are inB i 1 and in total contribute exactly 2·λS Λi toµi. As a result, ∑ B∈Bi µi B = ∑ B∈Biα µi B + ∑ B∈Bi 2α µi B + ∑ B∈Bi 3α µi B + ∑ B∈Bi 1 µi B = 1 Λi ( 0·Λi α+ 1·Λi 2α+ 3 2·Λi 3α+ 2·Λi 1 ) = 1. Next, lete∈Mbe some item. It is clear that ∑ B∈Bi B∋e µi B = ∑ B∈Bi α B∋e µi B + ∑ B∈Bi 2α B∋e µi B + ∑ B∈Bi 3α B∋e µi B + ∑ ...

work page
[10]

ifB∈Bi α, its parent bundleScontributes 0 to the sum above

work page
[11]

ifB∈Bi 2α, its parent bundleScontributes exactly λS Λi to the sum above, as there is only one sub-bundle ofS(setS i itself) containingeinB i

work page
[12]

ifB∈Bi 3α, its parent bundleScontributes exactly 2·λS 2Λi to the sum above, aseis contained in only two out of tree sub-bundles ofS i that belong toB i

work page
[13]

As a result ∑ B∈Bi B∋e µi B = ∑ S∈Si α S∋e 0 + ∑ S∈Si 2α S∋e λS Λi + ∑ S∈Si 3α S∋e 2·λS 2Λi + ∑ S∈Si 1 S∋e λS Λi≤1 Λi ∑ S∈S S∋e λS≤1 nΛi

ifB∈Bi 1, its parent bundleScontributes exactly λS Λi to the sum above, as there is only one out of two sub-bundles ofS i containingeinB i. As a result ∑ B∈Bi B∋e µi B = ∑ S∈Si α S∋e 0 + ∑ S∈Si 2α S∋e λS Λi + ∑ S∈Si 3α S∋e 2·λS 2Λi + ∑ S∈Si 1 S∋e λS Λi≤1 Λi ∑ S∈S S∋e λS≤1 nΛi. The claim follows. 24 A.2 Bounding the probability As shown inCorollaryA.1, for...

work page
[14]

ifα≤3/11, then βi+1≥ ( 1− 1−α 2(β−α)n ) ·βi

work page
[15]

ifα≥3/11andβ≥3α, then βi+1≥ ( 1− 2(1−3α) (β−12α+ 3)n ) ·βi

work page
[16]

(Whenα= 3/11, the three bounds coincide.) Proof.As shown inCorollaryA.1, for everyi∈[n] it holds thatβ i+1≥(1−1 nΛi )·βi

ifα≥3/11andβ <3α, then βi+1≥ ( 1− 4α 3(β−α)n ) ·βi. (Whenα= 3/11, the three bounds coincide.) Proof.As shown inCorollaryA.1, for everyi∈[n] it holds thatβ i+1≥(1−1 nΛi )·βi. In addition, inClaimA.2 we showed that Λ i≥Wi β, whereW β i is the optimal value for OPT i β. Hence, it holds that for everyi∈[n] we haveβi+1≥(1−1 nWi β )·βi. Consider the optimizatio...

work page
[17]

Sincew α+w 1 = 1, we can express β≤αwα+ (1−wα) =⇒wα≤1−β 1−α

ifα≤3/11, thenw2α=w 3α= 0 andβ≤αwα+w 1. Sincew α+w 1 = 1, we can express β≤αwα+ (1−wα) =⇒wα≤1−β 1−α. Therefore, Wi β= 2w1 = 2(1−wα)≥2(β−α) 1−α

work page
[18]

Sincew 3α+w 1 = 1, we can express β≤3αw3α+ (1−w3α) =⇒w3α≤1−β 1−3α

ifα≥3/11 andβ≥3α, thenwα=w 2α= 0 andβ≤3αw3α+w 1. Sincew 3α+w 1 = 1, we can express β≤3αw3α+ (1−w3α) =⇒w3α≤1−β 1−3α. Therefore, Wi β= 3 2w3α+ 2w1 = 2−1 2w3α≥2−1−β 2(1−3α)= β−12α+ 3 2(1−3α)

work page
[19]

Sincew α+w 3α= 1, we can express β≤αwα+ 3α(1−wα) =⇒wα≤3α−β 2α

ifα≥3/11 andβ <3α, thenw2α=w 1 = 0 andβ≤αwα+ 3αw3α. Sincew α+w 3α= 1, we can express β≤αwα+ 3α(1−wα) =⇒wα≤3α−β 2α . Therefore, Wi β= 3 2w3α= 3 2−3 2wα≥3 2−9α−3β 4α = 3(β−α) 4α . As mentioned earlier, fromCorollaryA.1 andClaimA.2,β i+1≥(1−1 nΛi )βi≥(1−1 nWi β )βi. Applying the lower bounds forW i βobtained above for different cases finishes the proof. 28 A...

work page
[20]

For any0≤ρ<1and any integerk, the number of steps ofγ i n to reach valueρis in(ρ) =tn ( ⌈ρk⌉ k ,⌈ρk⌉ k −ρ ) + k−1∑ r=⌈ρk⌉ tn (r+ 1 k , 1 k ) −(k−⌈ρk⌉)

work page
[21]

For any0≤δ≤γ <1such thatγ >α+δ, the numbertn(γ,δ)of steps of the processγi n after the iterationi n(γ)for the value to go belowγ−δsatisfies tn(γ,δ)>2δ(γ−δ−α)n γ(1−α)=:l n(γ,δ)

work page
[22]

doubling

For anyα≤ρ<1and any integerk, it holds thatβn≥γn n≥ρif k−1∑ r=⌈ρk⌉ ln (r+ 1 k , 1 k ) −(k−⌈ρk⌉)≥n. 29 We prove this lemma in Section E (LemmaE.1). We applyLemmaA.8 and combine all epoch lower bounds together to obtain a sufficient condition on the values ofρ,nguaranteeing thatγn n≥ρ. Then, we explore the limiting behavior ofρandnin the sufficient conditio...

work page
[23]

Proof.The proof is analogous toTheoremA.2

Thenβn, the remaining value afternsteps of Algorithm 2 fornagents, satisfiesβ n≥αfor alln≥54. Proof.The proof is analogous toTheoremA.2. Forα= 11 40 + 1 1000, the valueρfor which 3(3α−ρ−αln(3α)+αlnρ) 4α + 1−3α+(12α−3) ln(3α) 2(1−3α) = 1 isρ≥0.30861. Then, byCorollaryF.1, the gap betweenγn n≥ρandαwill be at least 0.03261, so we can takeδ= 0.03261 and haveγ...

work page
[24]

ifα≤3/11, thenp:= 1−α 2(β−α)n

work page
[25]

ifα≥3/11andβ≥3α, thenp:=2(1−3α) (β−12α+3)n

work page
[26]

dangerous

ifα≥3/11andβ <3α, thenp:= 4α 3(β−α)n. Proof.We useLemmaA.3 on valuationv i and partitionS k i to distribute all bundlesS k i ∈Sk i into classesS k i (tα) fort≥1 as follows: bundleSk i belongs toS k i (tα) if (t−1)α≤vi(Sk i )<tα. As α≤1/3, and byLemmaA.2 there are no sets of value greater than 1, we will only have bundles of classesS k i (α),Sk i (2α),Sk i...

work page
[27]

Sincejis picked after iterationk,B j⊆Sk+1 j,r andB i∩Bj⊆Bi∩Sk+1 j,r =∅

ifr≤Tk j , by constructionS k+1 j,r =S k j,r\Bi. Sincejis picked after iterationk,B j⊆Sk+1 j,r andB i∩Bj⊆Bi∩Sk+1 j,r =∅. In this case, agentidoes not lose any value from agentj

work page
[28]

expected

ifr >T k j , then by constructionS k+1 j,r =S k j,r, so agentimay lose some value from agentj, as filtering procedure does not remove items ofB i fromS k j,r. Suppose thatr > Tk j . Then, for every 1≤t≤Tk j it holds thatv i(Bi∩Sk j,r)≤vi(Bi∩Sk j,t). Therefore, vi(Bi∩Sk j,r)· Tk j∑ t=1 λj(Sj,t)≤ Tk j∑ t=1 λj(Sj,t)·vi(Bi∩Sk j,t)≤ ∑ Sj∈Sj λj(Sj)·vi(Sj∩Bi). O...

work page
[29]

There are partitions(U 1,U 2)ofUand(W 1,W 2)ofWwith the following properties: (a)|U1|=|W1|, and(U1,W 1)form a perfect matching which is maximal inG; (b) for every vertexu∈U2 we have|N(u)|≤n−3|U2|

work page
[30]

Proof.We will show that if items 1), 2), 3) do not hold, then 4) must hold

There are partitions(U 1,U 2,U 3)ofUand(W 1,W 2,W 3)ofWwith the following properties: (a)|U1|=|W1|, and(U1,W 1)form a perfect matching; (b) there are no edges betweenU 2 andW 3 and betweenU 3 andW 2∪W3; (c)(1−60ε)n≤|W2|<|U2|; (d) for every subsetU ′ 2⊆U2 of size|W2|there is a perfect matching betweenU′ 2 andW 2. Proof.We will show that if items 1), 2), 3)...

work page
[31]

Since every vertex inU′ 0 has at least (1−6ε)nneighbors inW0, we have|W′ 0|≥(1−6ε)nand|U′ 0|≥(1−6ε)n

satisfies|U′ 0|>|W′ 0|. Since every vertex inU′ 0 has at least (1−6ε)nneighbors inW0, we have|W′ 0|≥(1−6ε)nand|U′ 0|≥(1−6ε)n. LetU′ 0 :=U 0\U′ 0, andW′ 0 :=W 0\W′

work page
[32]

pretend” that some of these small allocated items were actually “big

We go over all verticesu∈U′ 0 in arbitrary order, and ifN(u)\W 1 is nonempty, takew∈N(u)\W1 and match (u,w) together, addingutoU 1 andw toW 1. Similar to what we did before, in the end of this procedure all unmatched vertices of U′ 0 have no edges intoW\W 1, and we add them toU 3. At the same time, all unmatched vertices of W′ 0 have no edges intoU\U 1, a...

work page
[33]

observant

For every agentj∈U2, there exists an APS-partition{(ˆSj, ˆλj( ˆSj)}ˆSj∈ˆSj ofonlyitemsW 3 among|U2|−|W2|agents such that its valueˆβj := ˆβj( ˆSj)satisfies ˆβj = ∑ ˆSj∈ˆSj ˆλj( ˆSi)·vj( ˆSj)≥1. 57 Proof.By construction, every iteme∈W2 is small for every agenti∈U3. Therefore, by deleting efrom every bundleS i∈Si the agent loses at most ∑ Si∈Si:Si∋eλi(Si)·α...

work page
[34]

every agenti∈U3 receives a bundleQ |U3| i satisfyingv i(Q|U3| i )≥α−2 ln6n4√n4

work page
[35]

Given this theorem, we then can do similar trick as inTheoremC.4 andTheoremC.6: run Algorithm 5 w.r.t valueα′=α+ (ρ−α)/2

remaining APS-values ˆβ|U3| j := ∑ ˆSj∈ˆSj ˆλj( ˆSj)·vj( ˆS|U3| j )for agentsj∈U2 satisfy 1 |U2| ∑ j∈U2 ˆβ|U3| j ≥1− 16αε4 3(1−ε4)(ρ−α). Given this theorem, we then can do similar trick as inTheoremC.4 andTheoremC.6: run Algorithm 5 w.r.t valueα′=α+ (ρ−α)/2. Since every agenti∈U3 has only items of value less thanα < α′in their APS partition, these APS par...

work page
[36]

every agenti∈U3 receives a bundleQ i satisfyingv i(Qi)≥α; 58 Algorithm 5Algorithm for agentsU 3 in case 4) ofLemmaD.1 Input:AgentsU 3 with APS partitions{(Si,λi(Si)}Si∈Si, agentsU 2 with APS partitions {(ˆSj, ˆλj( ˆSj)}ˆSj∈ˆSj fromClaimD.2 satisfyingLemmaA.2, parametersC,D >0. 1:LetA k be the set of active agents at iterationk, initiallyA 1 :=U 3 2:Forj∈U...

work page
[37]

values ˆβ|U3| j := ∑ ˆSj∈ˆSj ˆλj( ˆSj)·vj( ˆSj\⋃ i∈U3Qi)for agentsj∈U2 satisfy 1 |U2| ∑ j∈U2 ˆβ|U3| j ≥1−16(ρ+α)ε4 3(1−ε4)(ρ−α). Proof ofTheoremD.1.Fork∈[|U3|], letik denote the agent that was picked at iterationkof Algorithm 5, and letp ik be the smallest possible number such that for every iteme∈W2∪W3, µk ik(e)≤pik. Once again, for everyj∈U3 we consider...

work page
[38]

For any0≤ρ<1and any integerd, the minimum number of steps ofγ k n to reachρis kn(ρ)≥ d−1∑ r=⌈ρd/β⌉ tn ( β(r+ 1) d ,β d ) −(d−⌈ρd/β⌉)

work page
[39]

For any0≤τ≤γ <1such thatγ >α+τ+ε, the numbertn(γ,τ)of steps of the process γk n after the iterationk n(γ)for the value to go belowγ−τsatisfies tn(γ,τ)>2τ(γ−τ−ε−α)n γ(1−α) =:l n(γ,τ)

work page
[40]

Proof.To prove 1), first assume thatρd/βis an integer

For anyα+ε≤ρ<1and any integerd, it holds thatγn0 n ≥ρif d−1∑ r=⌈ρd/β⌉ ln ( β(r+ 1) d ,β d ) ≥n0 + (d−⌈ρd/β⌉). Proof.To prove 1), first assume thatρd/βis an integer. Divide the segment [ρ,β] into (1−ρ/β)d smaller sub-segments of the form [βr/d,β(r+1)/d] whereρd≤r≤d−1. Note that by definition, for any 0≤τ≤γ <1 it holdskn(γ) =kn(γ+τ) +tn(γ+τ,τ)−1. In particu...

work page
[41]

Taking this value ofdwithε,δ n→∞ −−−→0 whenn0 =nmakes the righthand side of Eq

Sinceρ<1, bothρdandd(1−ρ) are of order Θ(d), and taking any integerd= Θ(√n) in d(1−ρ) n + 3(3−ρ+ 1/d) 2ρ(ρd+ 1)+ 3(1−(3α+ε)) 2(3α+ε)((3α+ε)d+ 1)+ 3(1/d+ 4α) 4(3α+ε)αd+ 4−δ−ε−12α 2d(1−3α) makes the expression into a decreasing function ofn, specifically of order Θ(n −1/2). Taking this value ofdwithε,δ n→∞ −−−→0 whenn0 =nmakes the righthand side of Eq. (11)...

work page