Fair Allocation of Indivisible Goods: Improvement and Generalization

1.2.2 Submodular, XOS, and Subadditive Agents

• The results extend to submodular, fractionally subadditive, and subadditive valuations, with constant guarantees for submodular and XOS agents and a 1/10⌈log m⌉-MMS guarantee for subadditive agents.For non-additive settings, valuation access is via query oracles, and the allocation methods use polynomially many queries.Source: §1 · p. 3, §1.2 · p. 4

1.1 Relation to other Fundamental Problems

• Related work treats welfare maximization [41], max-min allocation [17], and Santa Claus [3] as distinct resource-allocation objectives.These variants optimize welfare, the least value received, or allocations under restricted item valuations, respectively.Source: §1.1 · p. 4

1.2 Our Results and Techniques

• The paper’s overall results improve the 2/3-MMS additive guarantee to 3/4 and provide analogous guarantees for submodular, fractionally subadditive, and subadditive agents, with polynomial-time algorithms.The guarantees and algorithms depend on the valuation class.Source: §1.2 · p. 4

1.2.1 Additive Setting

• Additive agents always admit a 3/4-MMS allocation, and a (3/4 −ϵ)-MMS allocation can be found in polynomial time, improving earlier results [2].The authors answer the open question of whether the 2/3 guarantee could be improved.Source: §1.2.1 · pp. 4–5
• The paper’s additive algorithm clusters agents into three groups, refines two groups, and uses matching allocation to assign high-value items while controlling their value to unassigned agents.Matching structure supports agent selection for the first two clusters and item merging.Source: §1.2.1 · pp. 6–7
• Reducibility reduces the existence proof to irreducible instances; cycle-envy-freeness preserves fairness in clustering and prioritizes agent order during the second allocation phase.For agents whose item values are bounded by αMMS, bag filling guarantees (1 −α)-MMS by assigning a bag whenever its value reaches that threshold.Source: §1.2.1 · pp. 5–7
• With four additive agents, the algorithm achieves 4/5-MMS (4/5 −ϵ in polynomial time), improving on 3/4-MMS; prior work shows 7/8-MMS is possible for three agents [2].These restricted-case results suggest stronger guarantees may be possible for additive agents.Source: §1.2.1 · p. 7

1.2.2 Submodular, XOS, and Subadditive Agents

• For submodular agents, a 1/3-MMS allocation exists and, with query-oracle access, can be found in polynomial time; the paper also shows 3/4-MMS is the best guarantee possible in this setting.Theorem 4.7 is only an existential proof; the algorithm uses a combinatorial trick to guess unknown MMS values without incurring an additional factor to the guarantee.Source: §1.2.2 · p. 9
• No allocation can exceed 3/4-MMS for some submodular instances, even with arbitrarily many agents.The counterexample has n agents and 2n items; the first n−1 agents share a valuation, while the last has a slightly different one.Source: §1.2.2 · pp. 9–10
• XOS agents always admit a 1/5-MMS allocation, while some instances with arbitrarily many agents admit no allocation better than 1/2-MMS.The existence proof uses bounded welfare: for an under-served agent, reallocating a suitable set of items increases welfare unless the allocation already meets the 1/5-MMS guarantee.Source: §1.2.2 · p. 10
• With demand and XOS oracles, a 1/8-MMS allocation for XOS agents can be found in polynomial time.The algorithm guesses MMS values and uses oracle-derived item contributions and demand queries to find reallocations that increase bounded welfare.Source: §1.2.2 · pp. 10–11
• The maxmin value can be approximated within factors 1/3 for submodular functions and 1/8 for XOS functions.Given the specified query, demand, and XOS oracles, the elements can be partitioned into n disjoint subsets with the corresponding factor.Source: §1.2.2 · p. 11
• The subadditive setting admits a 1/(10⌈log m⌉)-MMS allocation, proved by reducing to the XOS setting.The reduction uses an XOS function g satisfying g(S) ≤ f(S) for every set S.Source: §1.2.2 · p. 11

2 Preliminaries

• The analysis restricts valuations to additive, submodular, XOS (fractionally subadditive), and subadditive functions because unrestricted valuations can preclude any approximation guarantee.The motivating example has two agents and four items, with no allocation giving both agents a bundle of positive value.Source: §2 · p. 12
• The oracle model gives additive item values explicitly, uses query oracles for submodular functions, and uses XOS and demand oracles for XOS and subadditive functions.An XOS oracle returns an additive representation maximizing the value of a queried set; the demand oracle finds a set maximizing value minus item prices.Source: §2 · p. 12
• MMS is an agent’s value for its least-valued bundle in an optimal partition into n bundles; an allocation is α-MMS when each agent receives at least α times their MMS.The allocation partitions all items into disjoint bundles, one for each agent.Source: §2 · p. 13
• An α-reducible instance can set aside agents and items so the selected agents receive α times their MMS and the remaining items preserve MMS for the others; it suffices to prove the guarantee for α-irreducible instances.The paper uses reducibility in both existence proofs and algorithms, exploiting properties of irreducible instances to improve guarantees across valuation classes.Source: §2 · p. 13

3 Additive Agents5

• The paper proves a 3/4-MMS allocation for additive agents, improving on Procaccia and Wang’s 2/3-MMS guarantee.Given an α-approximation algorithm for computing MMS, the construction finds a 3/(4α)-MMS allocation in polynomial time; using the PTAS of Epstein and Levin yields a 3/(4+ϵ)-MMS allocation in polynomial time.Source: §3 · pp. 13–14

3.2 General Definitions and Observations

• For the existential proof, the section normalizes every agent’s MMS to 1; computing additive MMS is NP-hard, but the later algorithm accounts for this with an additional 1 + ϵ factor.The normalization is without loss of generality for existence because valuations can be scaled.Source: §3 · p. 14

3.1 A Brief Overview of the Algorithm

• The 3/4-MMS algorithm assumes a 3/4-irreducible instance, builds and refines three agent clusters, allocates heavy items, then bag-fills the remaining items.Irreducibility ensures the remaining items are light; bag-filling priorities depend on cluster membership and cycle-envy-freeness.Source: §3 · p. 14, §3.1 · p. 15
• Extending the algorithm beyond three clusters may yield a (1 −ϵ)-MMS allocation, but requires generalized lemmas and hypergraph bounds.A further challenge is proving that the second cluster is empty at the end of the algorithm.Source: §3.1 · p. 16

3.2.1 Consequences of Irreducibility

• Irreducibility reduces the proof to 3/4-irreducible instances, where no item alone satisfies any agent; this item-value bound also holds for monotone valuations beyond additive ones.The related two-item observations require additive valuations and do not extend to more general settings.Source: §3.2.1 · p. 17

3.2.2 Modeling the Problem with Bipartite Graphs

• The value graph represents item-agent values as edge weights, while threshold filtering removes low-weight edges; maximum-matching structure identifies item and agent subsets used in clustering.The defined FH set has no edges to the relevant unmatched-agent region, and its neighbors can be matched to saturate them.Source: §3.2.2 · p. 18

3.2.3 Cycle-envy-freeness and MCMWM

• Agents receive two item sets whose combined value is at least 3/4; cycle-envy-freeness requires every nonempty subset of semi-satisfied agents to contain a winner and loser.The representation graph of a cycle-envy-free set is a DAG, so its agents admit a topological ordering.Source: §3.2.3 · pp. 19–20
• A maximum-cardinality maximum-weight matching (MCMWM) has winner and loser properties that ensure its assigned agents form a cycle-envy-free set for clustering.The matching also ensures each matched agent’s assigned item is valued at least as highly as any adjacent unmatched item.Source: §3.2.3 · p. 20

3.3.1 Cluster C1

• C1 comprises agents in the neighborhood of the unmatched vertices of a 1/2-filtered maximum-cardinality matching, and matched items are allocated to saturated vertices.Items in W1 are worth less than 1/2 to agents outside C1.Source: §3.3.1 · p. 21

3.3.2 Cluster C1 Refinement

• A matching saturating every W1 vertex assigns its item to a C1 agent without envy from unsaturated neighbors; afterward, remaining items cannot satisfy any remaining C1 agent.The matching is in an auxiliary graph joining W1 items to C1 agents who value them at least ε_i.Source: §3.3.2 · p. 22
• For C1 agents satisfied during refinement, each allocated singleton item is worth less than 1/2 to every agent in C2 or C3.The paper establishes this bound for both f_j and g_j.Source: §3.3.2 · p. 22

3.3.3 Cluster C2

• Cluster C2 is formed after merging desirable item pairs to augment the matching; each merged pair is worth less than 3/4 to any agent and less than 2ε to C1 agents.The merging process stops when no desirable pair remains for agents outside the matching neighborhood or that set is empty.Source: §3.3.3 · p. 23

3.3.4 Cluster C2 Refinement

• C2 refinement processes agents in topological order, allocating an eligible remaining item; afterward, remaining unmerged items cannot satisfy any C2 agent.Items allocated in this refinement are worth less than ε_j to C1 agents and less than 1/2 to C3 agents.Source: §3.3.4 · pp. 24–25

3.3.5 Cluster C3.

• Every borrower agent in C3 has ε_i ≤ 1/4.Source: §3.3.5 · p. 26
• For each C3 agent, every pair of remaining items is worth less than 1/2, so at most one remaining item is worth at least 1/4 individually.The pairwise bound follows because no pair of vertices is desirable for C3 agents at the end of Algorithm 1.Source: §3.3.5 · p. 26

3.4.1 An Overview on the State of the Algorithm

• Free items are worth < ε_i individually to each C1 and C2 agent, while each C3 agent has at most one free item worth ≥1/4, enabling bag filling.The algorithm therefore applies a process similar to bag filling to allocate the free items.Source: §3.4.1 · pp. 26–27

3.4.2 Second Phase: bag filling

• The second phase repeatedly finds a minimum-size feasible subset of free items and assigns it to the lowest-priority eligible agent until no agent can feasibly receive the remaining items.The process runs in rounds with two steps: find the subset, then select its recipient from the agents for whom it is feasible.Source: §3.4.2 · p. 28
• Each round either satisfies an agent or makes an agent in Cf3 semi-satisfied, while C1, C2, and Cs3 remain cycle-envy-free throughout.The cycle-envy-free property is maintained during the second phase.Source: §3.4.2 · pp. 28–29
• For an agent satisfied in the second phase, every C3 agent values that agent’s allocation at <1/2; accompanying lemmas bound its value to agents in other clusters.The section summarizes these value lemmas in Table 5.Source: §3.4.2 · p. 29

3.5 The Algorithm Finds a 3/4-MMS Allocation

• At termination, C3 is empty: in either case considered, the remaining items make F feasible for an agent in C3.The proof considers an agent in Cs_3 or Cb_3, or an agent in Cf_3; in both cases feasibility contradicts termination.Source: §3.5 · p. 30
• At termination, C1 is empty: coloring items and double counting show a winner's value for F is at least ϵ_i, making F feasible.This contradicts termination and implies all agents in C1 are satisfied.Source: §3.5 · p. 30
• At termination, C2 is empty: for ϵ_i ≥ 1/8 the proof uses the C3-style argument, and for ϵ_i < 1/8 it uses four-coloring and double counting.Both cases show F feasible for a winner of C2, so every agent in C2 is satisfied.Source: §3.5 · p. 30
• All agents are satisfied before termination, so each receives a subset worth at least 3/4 to that agent.This establishes the algorithm's 3/4-MMS guarantee.Source: §3.5 · pp. 30–31

3.6 Algorithm

• For any ϵ > 0, a polynomial-time algorithm finds a (3/4 −ϵ)-MMS allocation.The method extends to all instances by repeatedly reducing reducible instances.Source: §3.6 · p. 31

3.6.1 The Clustering Phase

• The clustering phase is polynomial-time: it uses maximum-cardinality maximum-weight matchings, depth-first search for reachable vertices, and minimum-cost maximum flow to find the required matching.The same procedures compute Clusters C1 and C2; remaining agents go in C3.Source: §3.6.1 · pp. 31–32

3.6.2 The bag filling Phase

• The bag-filling phase is polynomial-time: reverse bag filling removes items while feasibility is preserved, leaving a minimally feasible subset for allocation.Each round allocates that subset to the agent with lowest priority in Φ(S).Source: §3.6.2 · p. 32

3.6.3 Reducibility

• Reducibility is handled by checking the required irreducibility consequences in polynomial time and reducing instances when Lemma C.1’s condition fails.Each reduction satisfies at least one agent with their matched item and decreases the agent count, so at most n polynomial-time reductions are needed.Source: §3.6.3 · p. 32

4 Submodular Agents

• Submodular valuations capture settings such as k-demand, where an agent is indifferent to receiving more than k items, beyond the additive valuations studied previously [2].The paper motivates submodular valuations as a model for more complex real-world preferences.Source: §4 · p. 33

4.1 Upper Bound

• For every n ≥ 2, some submodular-agent instance has no allocation better than 3/4-MMS; for XOS and subadditive agents, the upper bound is 1/2-MMS.The submodular counterexample is generic across agent counts, and its allocation argument shows that some agent receives value at most 3/2.Source: §4.1 · pp. 33–34

4.2 Existential Proof

• The ceiling function f_x preserves submodularity, XOS, and subadditivity, supporting the paper’s capped-value approach to fair allocation.For a set S, f_x(S) equals f(S) when f(S) ≤ x and x otherwise.Source: §4.2 · p. 34
• A 1/3-MMS allocation always exists for submodular agents, and the proof reduces to 1/3-irreducible instances and maximizes a capped-value objective.The ceiling operation preserves submodularity, XOS, and subadditivity; the existence theorem is for submodular agents.Source: §4.2 · pp. 34–35

4.3 Algorithm

• With valuation query-oracle access, a 1/3-MMS allocation for submodular agents can be found in polynomial time.The algorithm assumes each agent’s MMS is provided, although computing MMS for a submodular function is NP-hard; it also yields a polynomial-time 3-approximation to the maxmin value.Source: §4 · p. 33, §4.3 · pp. 36–37

5.1 Existential Proof

• Every fair-allocation instance with XOS valuations admits a 1/5-MMS allocation.The proof considers 1/5-irreducible instances and uses an allocation maximizing ex2/5; reducibility extends the result to all instances. XOS functions form a superclass of submodular functions.Source: §5 · p. 37, §5.1 · p. 38

5.2.1 Executing Command 9 in Polynomial Time

• A demand-oracle procedure executes Command 9 by finding items whose reassignment increases ex1/4(A) by at least 1/10n.It selects items from a set worth at least 1/4 to the lowest-valued agent; the selected items are worth at most 3/8 to that agent.Source: §5.2.1 · p. 41

5.2.2 Running Algorithm 5 in Polynomial Time

• If estimated maxmin values prevent Command 9 from executing, the blocked agent’s estimate is at least (1 + 1/10n) times its true maxmin value.The algorithm maintains estimates at least as large as the true values, so its returned allocation remains 1/8-MMS; estimate reductions yield polynomial running time for inputs represented with poly(n) bits.Source: §5.2.2 · pp. 42–43

5.2 Algorithm

• A polynomial-time algorithm finds a 1/8-MMS allocation for XOS agents using demand and XOS oracles, without requiring the maxmin values as input.Each iteration increases ex1/4(A) by at least 1/12n, so the algorithm terminates within 3n2 steps.Source: §5.2 · p. 40, §5.2.2 · p. 43

5.2.2 Running Algorithm 5 in Polynomial Time

• The XOS-oracle algorithm also gives an 8-approximation in polynomial time for computing the maxmin value with r partitions.It constructs an allocation instance with r agents sharing the same valuation function and reports the minimum value received.Source: §5.2.2 · p. 43

6 Subadditive Agents

• For every subadditive f and number of agents n, the section constructs a dominated XOS valuation whose maxmin value is within a logarithmic factor of f's.It approximates f on each of n disjoint sets with an additive function, then takes the maximum of those functions.Source: §6 · pp. 43, 45
• An LP for the best additive function dominated by f has an optimum at least a logarithmic fraction of f(ground(f)).The proof uses the dual and randomized set sampling, bounding marginal increases by subadditivity.Source: §6 · pp. 43–45
• Subadditive agents always admit a 1/(10 ceil(log m))-MMS allocation.The guarantee follows from Theorem 5.4 and Lemma 6.2.Source: §6 · p. 45

7 Acknoledgment

• The authors thank the anonymous reviewers for thoughtful comments and direction.Source: §7 · p. 45

A A 4/5-MMS Allocation for Four Agents

• The proof reduces to 4/5-irreducible instances with each agent’s MMS normalized to 1, so every item is worth less than 4/5 to any agent.It builds on minimal satisfying cores and the bound that such a core is worth less than 8/5 to its agent.Source: A A 4/5-MMS Allocation for Four Agents · p. 49
• Lemma A.4 guarantees a 4/5-MMS allocation of three bundles to three agents, which the proof uses to allocate remaining items in a difficult case.The proof also considers which bundles satisfy a3 or a4 to determine how to allocate the four bundles.Source: A A 4/5-MMS Allocation for Four Agents · pp. 50, 52
• A 4/5-MMS allocation for n = 4 is possible in the additive setting.Theorem A.6 establishes the section’s main guarantee.Source: A A 4/5-MMS Allocation for Four Agents · p. 51
• The algorithm starts from a1’s optimal four-way partition, then uses a2 to repartition three bundles into three bundles that each satisfy him.Lemma A.5 guarantees this repartitioning; at least one resulting bundle still satisfies a1.Source: A A 4/5-MMS Allocation for Four Agents · pp. 50, 52

Lemma 3.1

• Removing any item preserves an agent’s MMS value of at least 1 across n−1 partitions; α-irreducibility then rules out the stated allocation of an item worth at least α.The proof argues that removing one item can diminish at most one partition in an optimal n-partitioning.Source: B Omitted Proofs of Section 3.2 · p. 52

Lemma 3.2

• Allocating a pair worth at most 1 to every other agent gives the recipient value at least 3/4 and makes the instance 3/4-reducible, contradicting irreducibility.Removing the pair leaves n−1 partitions of value at least 1 for each other agent.Source: B Omitted Proofs of Section 3.2 · p. 52

Lemma 3.3

• Applying the pair-removal argument |T| times preserves an outside agent’s MMS across n−1 partitions, while condition (II) lets the pairs satisfy agents in T and reduce the instance.The proof concludes that this reduction contradicts irreducibility.Source: B Omitted Proofs of Section 3.2 · pp. 52–53

Lemma 3.6

• For a set T intersecting an alternating path from Ŷ1 to Ŷ2, the proof uses saturation and an unmatched neighbor to obtain |N(T)| > |T|.It first establishes |N(T)| ≥ |T|, then shows the path supplies a neighbor outside the vertices matched to T.Source: B Omitted Proofs of Section 3.2 · p. 53

Lemma 3.7

• The proof establishes that FH(M, X̂) is empty exactly when every subset T of X̂ has |N(T)| > |T|.If FH is nonempty, choosing it as T contradicts the strict inequality; the reverse direction follows from Lemma 3.6.Source: B Omitted Proofs of Section 3.2 · p. 53

Lemma 3.13

• For the first condition, if no desired winner exists, a directed cycle permits reassigning matching edges to increase weight, contradicting maximality.The auxiliary graph directs an edge toward a strictly higher-weight alternative; cycling those alternatives preserves matching cardinality while increasing weight.Source: B Omitted Proofs of Section 3.2 · p. 54
• For the second condition, absence of a desired loser creates a directed cycle whose reassignment contradicts maximality; the third follows by replacing a lower-weight matched edge.Source: B Omitted Proofs of Section 3.2 · p. 54

C Omitted Proofs of Section 3.3

• Lemma 3.14 uses graph nonadjacency and the filtered-agent threshold to obtain value bounds below 1/2; Lemma 3.16 likewise derives Vi(gj) < 1/2 from Observation 3.2.Source: C Omitted Proofs of Section 3.3 · pp. 54–56
• Irreducibility guarantees a matching in G1 that saturates W1: if the required condition failed, a constructed agent-item set would make the instance reducible.The contradiction uses a maximum matching and the conditions of Lemma 3.3.Source: C Omitted Proofs of Section 3.3 · p. 55
• Among maximum matchings, minimizing topological positions yields the Lemma 3.15 matching, whose unmatched neighbors do not envy their matched agents.The proof uses that C1 is cycle-envy-free and replaces an edge if an unmatched neighbor envies the matched agent.Source: C Omitted Proofs of Section 3.3 · pp. 55–56
• Lemma 3.22 maintains that all vertices in X′1/2 remain saturated by M′ as Algorithm 1 adds vertices, yielding the stated matching-neighborhood inequalities.Source: C Omitted Proofs of Section 3.3 · p. 57
• Lemma 3.23 identifies C3 as agents not selected for C1 and C2 and derives that C2 items are worth less than 1/2 to the described agents.Source: C Omitted Proofs of Section 3.3 · p. 57
• Lemmas 3.24 and 3.25 bound refined residual items below ϵj for C1 agents and below 1/2 for agents outside C1 ∪ C2.The proof notes that each gi for agents in Sr2 is a single item in the residual item set.Source: C Omitted Proofs of Section 3.3 · pp. 57–58
• Lemma 3.26 concludes that each C3 agent values any pair of items in the specified residual set at less than 1/2 when Algorithm 1 terminates.Termination means no pair is desirable for those agents.Source: C Omitted Proofs of Section 3.3 · p. 58

D Omitted Proofs of Section 3.4

• 3/4: Lemma 3.28 shows each bundle of at most two items is valued below 3/4 by every other agent, using separate singleton and merged-pair arguments.The singleton case invokes Lemma 3.1; the merged-pair case invokes Lemmas 3.19 and 3.20.Source: D Omitted Proofs of Section 3.4 · p. 58
• 2ε_j: Lemma 3.32 derives V_j(f_i) < 2ε_j for the relevant agents by using pairwise F-value below 1/2 and minimality to rule out feasible pieces.It first concludes that f_i contains at least three items, then considers an arbitrary item b_k and the remaining bundle.Source: D Omitted Proofs of Section 3.4 · p. 58
• Lemma 3.33 shows removing agents from C_1 or C_2 preserves cycle-envy-freeness, and adding an agent to C_s^3 preserves it by contradiction using the winner-and-loser condition.The contradiction uses Lemma 3.32 and the fact that every subset of the prior C_s^3 set contains at least one winner and one loser.Source: D Omitted Proofs of Section 3.4 · p. 58
• ε_j or 2ε_j: Lemma 3.34 bounds V_j(g_i) below ε_j when a_j precedes a_i in priority, and below 2ε_j otherwise.For the latter case, it splits off an arbitrary item and applies minimality and Observations 3.3 and 3.4.Source: D Omitted Proofs of Section 3.4 · p. 59
• 1/2: Lemma 3.35 establishes V_j(g_i) < 1/2, using priority when a_j is in C_f^3 and bundle-size cases when a_j is in C_s^3 ∪ C_b^3.For bundles larger than two items, the proof removes the item of minimum value to a_j, bounded below 1/4, and uses ε_j ≤ 1/4 for the remainder.Source: D Omitted Proofs of Section 3.4 · p. 59

E Omitted Proofs of Section 3.5

• For a satisfied agent ai in S3, every other agent aj in Cs3 ∪ Cb3 at that round has either Vj(gi) < ϵj or Vj(fi) ≤ 3/4 − ϵj.Source: E Omitted Proofs of Section 3.5 · p. 59
• For any agent ai in C3 during phase two, the total value of items assigned to agents in S3 is less than |S3| + 1/4.The proof shows that for all but at most one agent aj in S3, Vi(fj ∪ gj) < 1; for at most one, it is less than 5/4.Source: E Omitted Proofs of Section 3.5 · pp. 59–60
• The contradiction proof of Lemma 3.36 rules out C3 ≠ ∅ by showing F feasible for a selected agent, contrary to the algorithm’s termination.Source: E Omitted Proofs of Section 3.5 · pp. 60, 62
• The proof of Lemma 3.37 uses a blue/white coloring of assigned items and partition counting, with Lemma E.4 tightening the white-item bound, to rule out C1.It colors singleton fj sets blue, and singleton gj sets blue when their value to ai is at least ϵi; the resulting bound makes F feasible, contradicting termination.Source: E Omitted Proofs of Section 3.5 · pp. 62–64
• When ϵi ≥ 1/8, Lemma E.5 bounds ai’s value for items assigned to satisfied agents by less than |S| + 1/8, supporting the contradiction that F is feasible.This case is considered after Lemmas 3.36 and 3.37 establish C1 = C3 = ∅; the supplied proof then concludes that F’s feasibility contradicts termination.Source: E Omitted Proofs of Section 3.5 · pp. 64–66

• Items are colored blue, red, green, or white; red and green pairs are worth less than 3/4, and white-item sets less than 1/4, to ai.Source: E Omitted Proofs of Section 3.5 · p. 66
• For B00 partitions, the proof bounds 3|B00| − |G(B00)| by 4|B^0_00| + 2|B^1_00| + |B^2_00|.Source: E Omitted Proofs of Section 3.5 · p. 67
• For B10 partitions, it separates cases with exactly one blue item and no green items from the remaining partitions to bound white-item value.Source: E Omitted Proofs of Section 3.5 · pp. 67–68
• For B01 partitions, a graph encodes red-item pairs and blue items as edges and loops, and degree classes R1 and R2 yield bounds on white-item value.Source: E Omitted Proofs of Section 3.5 · pp. 68–69
• The proof derives Vi(F) ≥ 1/4, contradicting that F is feasible for ai.Source: E Omitted Proofs of Section 3.5 · p. 71

Observations F.1–F.2

• The appendix records the bounds fx(S) ≤ x and fx(S) ≤ f(S) for every set S.Source: F Omitted Proofs of Section 4 · p. 71

Lemma 4.4

• Truncation preserves submodularity: the proof checks three cases based on whether f(A) and f(B) reach x.It uses fx(S) ≤ x and fx(S) ≤ f(S) to establish the required inequality in each case.Source: F Omitted Proofs of Section 4 · p. 72
• Truncation preserves the XOS property by constructing additive functions for g and showing g(S) = fx(S) for every set S.The construction scales the maximizing additive function when f(S) > x and leaves its values unchanged when f(S) ≤ x.Source: F Omitted Proofs of Section 4 · pp. 72–73
• Truncation preserves subadditivity by considering whether either input set has value at least x or both have value below x.In the latter case, the proof applies fx(A ∪ B) ≤ f(A ∪ B) and the subadditivity of f.Source: F Omitted Proofs of Section 4 · p. 73

Lemma 4.5

• Lemma 4.5’s proof applies submodularity to successive elements of each Si, then sums the resulting inequalities across i.The argument rewrites the inequalities, adds a term involving |∪Si| − |Si|, and divides the summed inequality by 1/|∪Si|.Source: F Omitted Proofs of Section 4 · pp. 73–74

Lemma 4.6

• Lemma 4.6’s proof uses the same submodular marginal-value argument on Si \ S, under the stated conditions f(S) < 1/3 and f(S ∪ S′i) ≥ 1.It sums the resulting inequalities over i and divides by 1/|∪(Si \ S)|.Source: F Omitted Proofs of Section 4 · p. 74

G Omitted Proofs of Section 5

• For Lemma 5.2, an XOS valuation represented as a finite maximum of additive functions yields f(S \ Si) ≥ β − αi by selecting a maximizing clause and summing its values αi over the sets Si.Here β = Σ αi.Source: G Omitted Proofs of Section 5 · p. 74
• For Lemma 5.3, under 1/5-irreducibility, each MMS bundle valued at least 1 can be split into two disjoint sets each worth at least 2/5 to ai.Using an additive function maximizing the bundle's value, a prefix has value at least 2/5 and less than 3/5; its complement is therefore worth at least 2/5 under that function.Source: G Omitted Proofs of Section 5 · p. 75