From multi-allocations to allocations, with subadditive valuations

Uriel Feige

REVIEW 2 major objections 4 minor 15 references

From multi-allocations to allocations, with subadditive valuations

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that every d-multi-allocation with subadditive valuations converts to a real allocation in which each agent keeps at least a 1/d-share of her original value, and derives an Ω(1/log log n)-MMS guarantee.

desk verdict Potentially important conversion theorem for subadditive MMS, but the proof as written has a load-bearing gap and a false advertised corollary; worth refereeing, not yet citable. read the letter →

arxiv 2506.21493 v1 pith:GCVLIT26 submitted 2025-06-26 cs.GT

Uriel Feige This is my paper

classification cs.GT MSC 91B32

keywords fairallocationmaximinsharesubadditivevaluationsmulti-allocationMMSapproximationalternatingpickinggamegraphicalinstance

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves a deterministic conversion theorem: from a $d$-multi-allocation (each item may be given to up to $d$ agents) with monotone subadditive valuations, one can always pass to a proper allocation in which every agent $i$ keeps at least $v_i(A_i)/d - (d-1)\delta_i/d$, where $\delta_i$ is the largest value $i$ assigns to a single item in her bundle. This makes multi-allocations a workable relaxation in fair division: anything one can prove about approximate maximin-share (MMS) multi-allocations automatically upgrades to a statement about actual allocations, losing only a factor proportional to $d$. The paper packages this as a 'subadditive MMS sampling lemma' and applies it to the known $\frac12$-MMS $d$-multi-allocation guarantee from [SS25], obtaining $\Omega(1/\log\log n)$-MMS allocations for all subadditive valuations. That improves the previous $\Omega(1/(\log\log n)^2)$ bound and, for constant $d$, reduces the search for constant-factor MMS allocations to the search for constant-factor MMS multi-allocations.

What carries the argument

The central object is the alternating-picking value $\omega(S,M,v)$ of a two-player zero-sum game with a fixed picking sequence $S$; $\omega(S_q,M,v)$ is the value that player $p$ can guarantee when the other player picks first. For subadditive $v$ with maximum item value $\delta$, Corollary 11 gives $\omega(S_p,M,v) \ge \frac12 v(M)$ and $\omega(S_q,M,v) \ge \frac12(v(M)-\delta)$. The proof of the $d=2$ case embeds these two-player values in a token-walking game on a multi-graph: whenever the token first reaches an agent by walking, that agent is treated as playing an alternating sequence in which other agents' picks outside her item set are dummy moves. The induction for general powers of two copies each item, applies the $d=2$ result to the copies, and then recursively resolves the resulting smaller multi-allocation.

What would settle it

Compute $\omega(S_q,M,v)$ and $MMS(M,v,2)$ on additive valuation instances, since additive valuations are subadditive; a single instance with $\omega(S_q,M,v) < MMS(M,v,2)$ would refute the 'moreover' clause of Corollary 11 that Theorem 13 relies on. Alternatively, simulate the token-walking construction on a small multi-graph and check whether every agent whose first visit is by walk receives at least $(v_i(M)-\delta_i)/2$; one violation would refute the base case of Theorem 1.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for every $d \ge 2$ that is a perfect power of 2, every $d$-multi-allocation $A$ with subadditive valuations admits an allocation $A'$ with $A'_i \subseteq A_i$ and $v_i(A'_i) \ge v_i(A_i)/d - (d-1)\delta_i/d$ for all $i$. The proof starts with the $d=2$ case, proved through a token-walking allocation game on multi-graphs, and then lifts to $d = 2^k$ by splitting each item into $2^{k-1}$ copies, applying the binary case, and recursing. The paper's headline application is the subadditive MMS sampling lemma: a $\rho$-MMS $d$-multi-allocation guarantee (for $d$ a non-decreasing function of $n$) implies a $\rho/(2\hat d - 1)$-MMS allocation guarantee, where $\hat d$ is $d$ rounded up to a power of two. Plugging in the $\frac12$-MMS $d$-multi-allocations of [SS25] gives $\rho_{SA} \ge \Omega(1/\log\log n)$, and the paper also derives corollaries for multi-graphical instances, namely that each agent can receive at least $\frac12 MMS(M,v_i,2)$.

Load-bearing premise

The load-bearing premise is that when the token-walking game first reaches an agent through a walk, that agent can treat the rest of the game as the two-player alternating picking sequence $S_q$ with every other agent's pick outside her item set acting as a harmless dummy move; the proof asserts this equivalence rather than deriving it.

Editorial extensions

If this is right

Any $\rho$-MMS $d$-multi-allocation existence result for subadditive valuations automatically becomes a $\rho/(2\hat d -1)$-MMS allocation result, without requiring the multi-allocation to have extra structural properties.
Combining the sampling lemma with the $\frac12$-MMS $d$-multi-allocations of [SS25] yields a $\frac{1}{8\log\log n}$-MMS allocation for every $n \ge 4$, improving the previous $\Omega(1/(\log\log n)^2)$ bound.
For $n \le 8$, the lemma gives a $\frac16$-MMS allocation by splitting the agents into two groups of four and treating the combined allocation as a 2-multi-allocation.
In multi-graphical instances, every agent $i$ can be guaranteed $\frac12 MMS(M,v_i,2)$, which is at least as strong as the earlier $\frac12 MMS(M,v_i,n)$ guarantee for that class.
The conversion extends to per-agent capacities $d_i$ (Theorem 18) and, for arbitrary entitlements, to $\frac12$-APS allocations (Theorem 20).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Inference — Since Lemma 3 rounds $d$ up to a power of two, any proof of Theorem 1 for all integer $d$ would improve the final guarantee from $\rho/(2\hat d -1)$ to $\rho/(2d -1)$; the paper leaves whether such a proof exists open, but its own induction suggests the power-of-two restriction is technical rather than inherent.
Inference — The conversion is a black box in the sense that the multi-allocation needs no additional properties; therefore, proving that $\frac12$-MMS 2-multi-allocations always exist would immediately give $\frac16$-MMS allocations, and would determine $\rho_{SA}$ up to a constant factor.
Inference — The proof assumes that an agent first reached by a walk in the token game can play exactly the two-player alternating strategy, ignoring later jumps; this assumption is the natural place to test the proof, since subadditive valuations are known to break simpler monotonicity properties of alternating-picking values.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Feige's paper gives a new conversion from d-multi-allocations to allocations for subadditive valuations, losing only a factor d, with no concentration requirements. That is genuinely new: prior conversions via random sampling needed d to grow with n. If the main theorem holds, the immediate corollary is the current best MMS lower bound Omega(1/log log n), improving the [SS25] bound by a log log n factor. The high-level structure is clean: a two-player alternating-picking lemma, an extension to multi-graphs via a token game, and an induction on powers of 2.

The paper does several things well. The induction from 2-multi-allocations to d=2^k is clear and parameter-free. The MMS sampling lemma is a useful tool, and the comparison with random sampling is honest. Proposition 8 and Proposition 10 are solid.

The soft spots are in the two-player/graph section. Corollary 11 contains a 'moreover' claim that is false even for additive valuations: with item values 10,1,1,1, MMS(M,v,2)=3 but omega(Sq,M,v)=2. That invalidates Corollary 2 and the second half of Corollary 14, which are advertised contributions, though it does not feed into the proof of Theorem 1. More serious: in Theorem 13, case 2, the proof asserts 'vi(U)+omega(Sp,Y,v^U_i) >= omega(Sq,M_i,v_i)' without derivation. This inequality is load-bearing for the base case of Theorem 1. The token game's interruptions (jumps) change turn parity and the set of items consumed by others, and the text does not explain why the accumulated U plus a fresh-phase guarantee on Y dominates the uninterrupted alternating game. This is not a merely presentational gap; it is the hinge of the proof. It might be fixable, but it needs a real argument.

There is also a minor typo in Remark 9: 'XOS is a strict subclass of additive' should be 'subadditive'.

Verdict: this is a serious paper by a serious researcher, and the main idea deserves engagement. But the current version is not rigorous: one false claim, one unproven load-bearing inequality. I would send it to a strong referee, but I would not cite the main theorem as proven yet. If the author fills the gap and removes the false moreover, the paper becomes an important contribution.

Referee Report

2 major / 4 minor

Summary. The paper studies the conversion of a d-multi-allocation into a proper allocation under monotone subadditive valuations. The main theorem (Theorem 1) states that for d a power of 2, any d-multi-allocation A can be converted into an allocation A' with vi(A'_i) >= vi(A_i)/d - (d-1)/d * delta_i, where delta_i is the maximum value of a single item in A_i. The proof develops a two-player alternating-picking game (Section 2.1), a token-walking allocation game on multi-graphs for the base case d=2 (Section 2.2), and an induction on powers of two (Section 2.3). The paper then derives a subadditive MMS sampling lemma (Lemma 3) and uses a result of Seddighin and Seddighin to conclude that rho_SA >= Omega(1/log log n) for subadditive valuations (Corollary 6).

Significance. If the proof is completed, the conversion theorem would be a clean, parameter-free reduction from multi-allocations to allocations, avoiding submodular concentration arguments and improving the state of the art for subadditive MMS allocations. The MMS sampling lemma is a very useful black-box tool: it shows that any rho-MMS d-multi-allocation existence result translates into an allocation existence result with only a factor O(d) loss. The paper also explicitly identifies that constant d would suffice for a constant rho_SA. However, the current manuscript contains a false claim in the two-player analysis and a load-bearing unproved inequality in the token-walking proof, so the central result is not yet fully established.

major comments (2)

[§2.2, Theorem 13, case 2] The final displayed inequality in case 2, namely vi(U) + omega(Sq, Y, v^U_i) >= omega(Sq, Mi, vi), is asserted without proof. This is exactly the step that reduces the token-walking game to the two-player alternating game Sq on Mi after a jump into agent i. The inequality is not immediate: the marginal valuation v^U_i is not shown to satisfy the properties used elsewhere, and dummy picks by other agents outside Mi could, in principle, change the turn count or the set of available items when the token next reaches i. Since Theorem 13 is the base case of Theorem 1 and hence feeds Lemma 3 and Corollary 6, this gap is load-bearing. Please provide a formal strategy-stealing argument, a proof of the inequality, or a corrected reduction for this step.
[§2.1, Corollary 11] The 'moreover' claim that omega(Sq, M, v) >= MMS(M, v, 2) is false even for additive valuations, which are subadditive. Let M have item values 10, 9, 8, 1 and let Sq be the sequence q, p, q, p. In the worst case q first takes 10, after which p obtains 9 and 1, so omega(Sq, M, v) = 10. The two-agent maximin share is 11, realized by the partition {10,1} and {9,8}. The proof's assertion that M' necessarily contains one of the bundles of an MMS partition is false because q's first pick may remove the unique item that makes a bundle reach the MMS value. This invalidates the derivation of the 'Moreover' part of Corollary 14 and of Corollary 2 as stated; the main induction does not use this particular claim, but the surrounding two-player analysis needs correction.

minor comments (4)

[§1.1] The word 'geneal' in the paragraph after Corollary 2 should be 'general'.
[§2.4, Remark 4] Remark 4 says that if d is not an integer then \hat d = c⌈d⌉, but the constant c is not defined and the equality appears to be a typo; the definition of \hat d from the start of Section 2.4 already covers non-integer d.
[§2.2, Corollary 14] In the statement of Corollary 14, 'the value received it at least' should be 'the value received is at least'.
[§3, Theorem 20] Theorem 20 is stated without proof, with only the remark that the proof is similar to that of Theorem 2. For a journal publication, either include the proof or explicitly mark the result as a conjecture.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 1 and Lemma 3 are derived from scratch, and the load-bearing external input is [SS25]; the flagged weaknesses are proof gaps, not definitional circularity.

full rationale

The derivation chain is not circular. Theorem 1 is proved directly in Sections 2.1-2.3: the two-player inequalities (Propositions 8 and 10, Corollary 11) are proved inside the paper; Theorem 13 supplies the d=2 base case via the token-walking game; and induction on powers of two completes the proof. Lemma 3 is a parameter-free reduction: it takes the assumed existence of a rho-MMS d-multi-allocation as an input, removes agents with overly large singleton values, and applies Theorem 1; no fitted parameter is renamed as a prediction and no definition presupposes the conclusion. Corollary 6 combines Lemma 3 with Lemma 15, which is an external result of Seddighin and Seddighin [SS25], not a self-citation. The paper's own prior work ([Fei09], [Fei25], [FH25], [FG25]) appears in related-work comparisons or in the optional background sketch of Lemma 15, but it is not the load-bearing justification for the main theorem. The reader-flagged weaknesses - the asserted 'dummy move' reduction in Theorem 13 and the false 'moreover' claim in Corollary 11 - are mathematical gaps or errors, not cases where a conclusion is equivalent to its input by construction. The omitted proof of Theorem 20 is also a completeness concern, not a circular one. Hence the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

This is a pure mathematical proof with no fitted constants, no new entities, and no empirical claims. The free parameter list is empty. The axioms are standard game-theoretic facts, the problem's valuation assumptions, an external theorem from [SS25] used for the headline corollary, and an implicit modeling assumption about copied items.

assumptions (5)

standard math Finite zero-sum games of perfect information have deterministic maximin strategies.
Used in Proposition 8 and Theorem 13 to treat guaranteed values as deterministic.
domain assumption Valuations are normalized, monotone, and subadditive.
The problem setting in Section 1 restricts to this class; the theorems are stated for it.
standard math Removing an agent and an item cannot decrease the MMS of the remaining agents.
Invoked in the proof of Lemma 3 as a known MMS property without proof.
domain assumption Lemma 15 from Seddighin and Seddighin [SS25]: every instance with n < n_d agents has a 1/2-MMS d-multi-allocation.
External input for Corollary 6; not re-proved in this paper, only sketched.
ad hoc to paper Copies of items inherit valuations, so a set of copies of distinct originals has the same value as the set of originals.
The induction step of Theorem 1 creates copies but never formally defines agent valuations over copies or sets of copies.

how reviews work

0 comments

Cite this review

Pith. "Pith review of From multi-allocations to allocations, with subadditive valuations." pith.science (2026). https://pith.science/paper/GCVLIT26

@misc{pith2026250621493,
  author       = {Pith},
  title        = {Pith review of: From multi-allocations to allocations, with subadditive valuations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GCVLIT26}},
  note         = {Machine review of arXiv:2506.21493}
}

abstract

We consider the problem of fair allocation of $m$ indivisible items to $n$ agents with monotone subadditive valuations. For integer $d \ge 2$, a $d$-multi-allocation is an allocation in which each item is allocated to at most $d$ different agents. We show that $d$-multi-allocations can be transformed into allocations, while not losing much more than a factor of $d$ in the value that each agent receives. One consequence of this result is that for allocation instances with equal entitlements and subadditive valuations, if $\rho$-MMS $d$-multi-allocations exist, then so do $\frac{\rho}{4d}$-MMS allocations. Combined with recent results of Seddighin and Seddighin [EC 2025], this implies the existence of $\Omega(\frac{1}{\log\log n})$-MMS allocations.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 9 canonical work pages

[1]

EFX allocations and orientations on bipartite multi-graphs: A complete picture

[ADK+24] Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. EFX allocations and orientations on bipartite multi-graphs: A complete picture. CoRR, abs/2410.17002,

arXiv
[4]

Fair-share allocations for agents with arbitrary entitlements

[BEF21] Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair-share allocations for agents with arbitrary entitlements. In EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021 , page

work page 2021
[7]

On fair allocation of indivisible goods to submodular agents

[BUF23] Gilad Ben-Uziahu and Uriel Feige. On fair allocation of indivisible goods to submodular agents. CoRR, abs/2303.12444,

arXiv
[9]

Fair allocation in graphs

[CFKS23] George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023 , pages 473–488. ACM,

work page 2023
[10]

Exact and ap- proximate maximin share allocations in multi-graphs

[CM25] George Christodoulou and Symeon Mastrakoulis. Exact and ap- proximate maximin share allocations in multi-graphs. CoRR, abs/2506.20317,

arXiv
[12]

Fair allocations with subadditive and XOS valuations

[FG25] Uriel Feige and Vadim Grinberg. Fair allocations with subadditive and xos valuations. CoRR, abs/2503.10513,

work page Pith review arXiv
[13]

Concentration and maximin fair allocations for subadditive valuations

[FH25] Uriel Feige and Shengyu Huang. Concentration and maximin fair allocations for subadditive valuations. CoRR, abs/2502.13541,

work page Pith review arXiv
[14]

Maximin share allocations for assignment valuations

[KKM23] Pooja Kulkarni, Rucha Kulkarni, and Ruta Mehta. Maximin share allocations for assignment valuations. In Proceedings of the 2023 In- ternational Conference on Autonomous Agents and Multiagent Sys- tems, AAMAS 2023 , pages 2875–2876. ACM,

work page 2023

Show all 15 references

[15]

Beating the logarith- mic barrier for the subadditive maximin share problem

[SS25] Masoud Seddighin and Saeed Seddighin. Beating the logarith- mic barrier for the subadditive maximin share problem. CoRR, abs/2506.05613,

arXiv
[2009]

The residual maximin share

[Fei25] Uriel Feige. The residual maximin share. CoRR, abs/2505.19961,

arXiv
[2021]

On best-of-both- worlds fair-share allocations

[BEF22] Moshe Babaioff, Tomer Ezra, and Uriel Feige. On best-of-both- worlds fair-share allocations. In Web and Internet Economics - 18th International Conference, WINE 2022, Proceedings , volume 13778, pages 237–255,

2022
[2022]

Share-based fairness for arbitrary entitlements

[BF24] Moshe Babaioff and Uriel Feige. Share-based fairness for arbitrary entitlements. CoRR, abs/2405.14575,

arXiv
[2023]

Maximin share guarantees for few agents with subadditive valuations

[CCMS25] George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, and Alkmini Sgouritsa. Maximin share guarantees for few agents with subadditive valuations. CoRR, abs/2502.05141,

arXiv
[2024]

Fair division via resource augmentation

[AEF+25] Hannaneh Akrami, Alon Eden, Michal Feldman, Amos Fiat, and Yoav Gal-Tzur. Fair division via resource augmentation. CoRR, abs/2502.09377,
[2025]

Breaking the 3/4 barrier for approximate maximin share

14 [AG24] Hannaneh Akrami and Jugal Garg. Breaking the 3/4 barrier for approximate maximin share. In Proceedings of the 2024 ACM- SIAM Symposium on Discrete Algorithms, SODA 2024, pages 74–91. SIAM,

2024

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

EFX allocations and orientations on bipartite multi-graphs: A complete picture

[ADK+24] Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. EFX allocations and orientations on bipartite multi-graphs: A complete picture. CoRR, abs/2410.17002,

arXiv

[2] [4]

Fair-share allocations for agents with arbitrary entitlements

[BEF21] Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair-share allocations for agents with arbitrary entitlements. In EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021 , page

work page 2021

[3] [7]

On fair allocation of indivisible goods to submodular agents

[BUF23] Gilad Ben-Uziahu and Uriel Feige. On fair allocation of indivisible goods to submodular agents. CoRR, abs/2303.12444,

arXiv

[4] [9]

Fair allocation in graphs

[CFKS23] George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023 , pages 473–488. ACM,

work page 2023

[5] [10]

Exact and ap- proximate maximin share allocations in multi-graphs

[CM25] George Christodoulou and Symeon Mastrakoulis. Exact and ap- proximate maximin share allocations in multi-graphs. CoRR, abs/2506.20317,

arXiv

[6] [12]

Fair allocations with subadditive and XOS valuations

[FG25] Uriel Feige and Vadim Grinberg. Fair allocations with subadditive and xos valuations. CoRR, abs/2503.10513,

work page Pith review arXiv

[7] [13]

Concentration and maximin fair allocations for subadditive valuations

[FH25] Uriel Feige and Shengyu Huang. Concentration and maximin fair allocations for subadditive valuations. CoRR, abs/2502.13541,

work page Pith review arXiv

[8] [14]

Maximin share allocations for assignment valuations

[KKM23] Pooja Kulkarni, Rucha Kulkarni, and Ruta Mehta. Maximin share allocations for assignment valuations. In Proceedings of the 2023 In- ternational Conference on Autonomous Agents and Multiagent Sys- tems, AAMAS 2023 , pages 2875–2876. ACM,

work page 2023