Pith. sign in

REVIEW 3 minor 2 cited by

Exact and approximate maximin share allocations in multi-graphs

T0 review · 0 major / 3 minor · reviewed 2026-05-19 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read In graph-based valuations where items are edges valued only by endpoints, exact MMS allocations exist for additive cases but approximations are needed for XOS and subadditive valuations.

desk verdict This extends the 2023 graphical fair division results to multi-graphs and adds PMMS alongside MMS for additive, XOS, and subadditive valuations. read the letter →

arxiv 2506.20317 v2 submitted 2025-06-25 cs.GT

George Christodoulou , Symeon Mastrakoulis This is my paper · ORCID
classification cs.GT
keywords maximinsharegraphicalvaluationsfairallocationindivisibleitemsadditivesubadditivePMMS
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 examines fair allocation of indivisible items under a graphical valuation model in which items correspond to edges and agents to vertices, so that an item affects value only for its two incident agents. It delivers positive results on the existence of exact or approximate maximin share allocations for additive, XOS, and subadditive valuations, together with negative results that establish limits on the best possible approximation factors. The same pattern of results is shown for pair-wise maximin share fairness. A sympathetic reader cares because the model captures settings with local interactions, such as network resources or matching problems, where global valuations would be unrealistic.

What carries the argument

The graphical valuation model, in which each edge-item has non-zero marginal value only for its two incident vertices-agents, reducing the allocation problem to local graph structure.

What would settle it

A concrete multi-graph with subadditive valuations on which no allocation meets the approximation ratio claimed for MMS.

Watch

Extended reading notes

Core claim

Under the graphical valuation model, additive valuations always admit an exact MMS allocation, while XOS and subadditive valuations admit constant-factor approximate MMS allocations whose factors are shown to be tight by matching negative examples; analogous positive and negative results hold for approximate PMMS.

Load-bearing premise

Each item has value only to its two endpoint agents and zero value to all other agents.

Editorial extensions

If this is right

  • Exact MMS allocations can be produced for any additive instance without approximation.
  • For XOS valuations a fixed approximation factor suffices and cannot be improved in the worst case.
  • Subadditive valuations require approximation but still guarantee a constant factor for MMS.
  • The same approximation landscape applies to pair-wise maximin share fairness.

Reading between the lines

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

  • The model may be used to design local fairness protocols in communication networks where agents value only adjacent links.
  • Negative results imply that dense or high-degree graphs may force algorithms to search for allocations rather than use simple greedy methods.
  • The framework could be extended to dynamic graphs where edges arrive over time to test whether the same guarantees survive online arrival.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 3 minor

Summary. The manuscript studies (approximate) maximin share (MMS) and pairwise maximin share (PMMS) allocations of indivisible items in the graphical valuation model, where the input is a multi-graph with agents as vertices and items as edges that have nonzero marginal value only for their incident vertices. It considers additive, XOS, and subadditive valuations and presents both positive results (existence or algorithmic guarantees for exact or approximate fairness) and negative results (impossibility or lower-bound constructions) for MMS and PMMS.

Significance. If the stated positive and negative results hold, the paper makes a useful contribution by extending the graphical fair-division model of Christodoulou et al. (EC 2023) to multi-graphs and by systematically treating both MMS and PMMS across three standard valuation classes. The combination of existence/approximation algorithms with matching impossibility results helps delineate the feasible fairness guarantees in this structured setting.

minor comments (3)
  1. [Abstract and §1] The abstract and introduction would benefit from explicitly stating the approximation factors achieved for MMS and PMMS under each valuation class (e.g., 1/2-MMS for additive, etc.), rather than only describing the existence of positive and negative results.
  2. [§2] Notation for multi-edges is introduced but not always used consistently when stating the valuation functions; a short clarifying paragraph or table in the model section would help readers distinguish the multi-graph case from the simple-graph case of prior work.
  3. [Figures 1–3] Several figures illustrating the graph model and sample allocations are present but lack explicit value labels on edges; adding these would make the examples easier to follow without referring back to the text.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work, the assessment of its significance in extending the graphical fair-division model to multi-graphs, and the recommendation for minor revision. We are pleased that the combination of positive and negative results for MMS and PMMS across valuation classes is viewed as delineating feasible fairness guarantees. Below we provide point-by-point responses; since the report lists no specific major comments under that heading, our responses focus on the overall feedback provided.

Circularity Check

0 steps flagged · score 2.0 of 10

Minor self-citation to model definition; results independent

full rationale

The paper cites prior work by overlapping authors (Christodoulou et al., EC 2023) solely to define the graphical valuation model where items are edges and agents are vertices. This sets up the input without serving as a load-bearing justification for the new positive/negative results on MMS and PMMS fairness under additive, XOS, and subadditive valuations. No equations, reductions, fitted parameters renamed as predictions, or self-referential derivations appear in the abstract or model. The central claims are independent contributions building on the cited setting, making the paper self-contained against external fair-division benchmarks.

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

The central claims rest on the graphical valuation model (edges valued only by incident vertices) and standard MMS/PMMS definitions from prior literature; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

assumptions (1)
  • domain assumption Valuations are monotone and defined only on incident edges in the multi-graph.
    Directly stated in the abstract as the graphical valuation model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exact and approximate maximin share allocations in multi-graphs." pith.science (2026). https://pith.science/paper/2506.20317

@misc{pith2026250620317,
  author       = {Pith},
  title        = {Pith review of: Exact and approximate maximin share allocations in multi-graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2506.20317}},
  note         = {Machine review of arXiv:2506.20317}
}
read the original abstract

We study the problem of (approximate) maximin share (MMS) allocation of indivisible items among a set of agents. We focus on the graphical valuation model, previously studied by Christodolou, Fiat, Koutsoupias, and Sgouritsa ("Fair allocation in graphs", EC 2023), where the input is given by a graph where edges correspond to items, and vertices correspond to agents. An edge may have non-zero marginal value only for its incident vertices. We study additive, XOS and subadditive valuations and we present positive and negative results for (approximate) MMS fairness, and also for (approximate) pair-wise maximin share (PMMS) fairness.

Figures

Figures reproduced from arXiv: 2506.20317 by the authors.

Figure 1
Figure 1. Common edges E1,2 (a), E1,3 (b) and E2,3 (c). In each set Ei,j rows represent the bundles Bi,t of agent i and columns represent the bundles Bj,t of agent j. Cell (ki, kj ) represents the intersection Bi,ki ∩ Bj,kj . The figure illustrates the frugal orientation X = (B1,1 ∩(B2,1 ∪B2,2), B2,3 \B3,1, B3,1) of the base case with d = 3. With blue, red and green being the bundles allocated to agent 1, 2 and 3 respectively… view at source ↗
Figure 2
Figure 2. Common edges E1,2 (a), E1,3 (b) and E2,3 (c). In each set Ei,j rows represent the bundles Bi,t of agent i and columns represent the bundles Bj,t of agent j. Cell (ki, kj ) represents the intersection Bi,ki ∩ Bj,kj . The figure illustrates the frugal orientation X = (B1,1 \ (B2,3 ∪ B3,2), B2,3 \ B3,2, B3,2) of the induction step k = 1, with d = 3 and i ∗ = 3. With blue, red and green being the bundles allocated to ag… view at source ↗
Figure 3
Figure 3. Common edges E1,k+1 (a), E2,k+1 (b) and Ek,k+1 (c). In each set Ei,j rows represent the bundles Bi,ki of agent i and columns represent the bundles Bj,kj of agent j. Cell (ki, kj ) represents the intersection Bi,ki ∩ Bj,kj . The figure illustrates the partition of Bk+1,1 bundles as follows:  Bk+1,1 ∩ X (k+1), Bk+1,1 ∩ X ′(k+1), Bk+1,1 \  X (k+1) ∪ X ′(k+1). X (k+1) is a 2/3-MMS frugal orientation with X (k+1) i ⊆… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Common edges Ei,j where the rows correspond to the bundles Bi,ki . In each set Ei,j rows represent the bundles Bi,ki of agent i and columns represent the bundles Bj,kj of agent j. Cell (ki, kj ) represents the intersection Bi,ki ∩ Bj,kj . The figure focus on agents i, …
Figure 5
Figure 5. Figure 5: The figure represents bundles Si,ki via a graph. Each part Vi corresponds to an agent i, with vertices representing her bundles. An edge between two vertices vi,ki , vj,kj exists if and only if the corresponding bundles Si,ki , Sj,kj may intersect. Finding an independe…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division

    cs.GT 2025-07 reject novelty 7.0 of 10

    The paper proves a three-agent EFX/PMMS separation and claims PMMS existence for binary-valued and pair-demand valuations, plus EFX for personalized bivalued valuations.

  2. From multi-allocations to allocations, with subadditive valuations

    cs.GT 2025-06 conditional novelty 7.0 of 10

    A d-multi-allocation with subadditive valuations can be converted to an allocation losing only a factor of about d, yielding an Omega(1/log log n)-MMS guarantee.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages · cited by 2 Pith papers

  1. [1]

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

    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, 2024

    work page arXiv 2024

  2. [2]

    Envy-free matchings in bipartite graphs and their applications to fair division

    Elad Aigner-Horev and Erel Segal-Halevi. Envy-free matchings in bipartite graphs and their applications to fair division. Inf. Sci., 587:164–187, 2022

    work page 2022

  3. [3]

    Breaking the 3/4 barrier for approximate maximin share

    Hannaneh Akrami and Jugal Garg. Breaking the 3/4 barrier for approximate maximin share. CoRR, abs/2307.07304, 2023

    work page arXiv 2023

  4. [4]

    Simplification and improvement of MMS approximation

    Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki. Simplification and improvement of MMS approximation. CoRR, abs/2303.16788, 2023

    work page arXiv 2023

  5. [5]

    Improving approximation guarantees for maximin share.CoRR, abs/2307.12916, 2023

    Hannaneh Akrami, Jugal Garg, and Setareh Taki. Improving approximation guarantees for maximin share.CoRR, abs/2307.12916, 2023

    work page arXiv 2023

  6. [6]

    Randomized and determin- istic maximin-share approximations for fractionally subadditive valuations

    Hannaneh Akrami, Masoud Seddighin, Kurt Mehlhorn, and Golnoosh Shahkarami. Randomized and determin- istic maximin-share approximations for fractionally subadditive valuations. CoRR, abs/2308.14545, 2023

    work page arXiv 2023

  7. [7]

    V oudouris, and Xiaowei Wu

    Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Herv ´e Moulin, Alexandros A. V oudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artif. Intell., 322:103965, 2023

    work page 2023

  8. [8]

    Comparing Approximate Relaxations of Envy-Freeness

    Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. Comparing approximate relaxations of envy- freeness. CoRR, abs/1806.03114, 2018

    work page Pith review arXiv 2018

Show all 46 references
  1. [9]

    Approximation algorithms for computing maximin share allocations

    Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms, 13(4):52:1–52:28, 2017

    2017

  2. [10]

    Competitive equilibrium with indivisible goods and generic budgets

    Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen. Competitive equilibrium with indivisible goods and generic budgets. Math. Oper. Res., 46(1):382–403, 2021

    2021

  3. [11]

    Approximation algorithms for maximin fair division.ACM Trans

    Siddharth Barman and Sanath Kumar Krishnamurthy. Approximation algorithms for maximin fair division.ACM Trans. Economics and Comput., 8(1):5:1–5:28, 2020

    2020

  4. [12]

    Existence and computation of maximin fair allocations under matroid- rank valuations

    Siddharth Barman and Paritosh Verma. Existence and computation of maximin fair allocations under matroid- rank valuations. CoRR, abs/2012.12710, 2020

    2012

  5. [13]

    On fair allocation of indivisible goods to submodular agents

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

    2023

  6. [14]

    EFX allocations on some multi-graph classes

    Umang Bhaskar and Yeshwant Pandit. EFX allocations on some multi-graph classes. CoRR, abs/2412.06513, 2024

    2024

  7. [15]

    The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes

    Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061–1103, 2011

    2011

  8. [16]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Herv ´e Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Trans. Economics and Comput., 7(3):12:1–12:32, 2019

    2019

  9. [17]

    1/2 approximate MMS allocation for separable piecewise linear concave valuations

    Chandra Chekuri, Pooja Kulkarni, Rucha Kulkarni, and Ruta Mehta. 1/2 approximate MMS allocation for separable piecewise linear concave valuations. CoRR, abs/2312.08504, 2023

    2023

  10. [18]

    Fair and truthful allocations under leveled valuations

    George Christodoulou and Vasilis Christoforidis. Fair and truthful allocations under leveled valuations. CoRR, abs/2407.05891, 2024. 22

    2024

  11. [19]

    Maximin share guarantees for few agents with subadditive valuations, 2025

    George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, and Alkmini Sgouritsa. Maximin share guarantees for few agents with subadditive valuations, 2025

    2025

  12. [20]

    Fair allocation in graphs

    George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. Fair allocation in graphs. In EC, pages 473–488. ACM, 2023

    2023

  13. [21]

    Truthful allocation in graphs and hyper- graphs

    George Christodoulou, Elias Koutsoupias, and Annam ´aria Kov ´acs. Truthful allocation in graphs and hyper- graphs. CoRR, abs/2106.03724, 2021

    2021

  14. [22]

    The existence and efficiency of PMMS allocations

    Sijia Dai, Xinru Guo, Huahua Miao, Guichen Gao, Yicheng Xu, and Yong Zhang. The existence and efficiency of PMMS allocations. Theor. Comput. Sci., 989:114388, 2024

    2024

  15. [23]

    Ef1 and efx orientations, 2024

    Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, and Viktoriia Korchemna. Ef1 and efx orientations, 2024

    2024

  16. [24]

    Graph balancing: A special case of scheduling unrelated parallel machines

    Tom ´as Ebenlendr, Marek Krc´al, and Jir´ı Sgall. Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica, 68(1):62–80, 2014

    2014

  17. [25]

    Fair allocations with subadditive and xos valuations, 2025

    Uriel Feige and Vadim Grinberg. Fair allocations with subadditive and xos valuations, 2025

    2025

  18. [26]

    Concentration and maximin fair allocations for subadditive valuations, 2025

    Uriel Feige and Shengyu Huang. Concentration and maximin fair allocations for subadditive valuations, 2025

    2025

  19. [27]

    A tight negative example for MMS fair allocations

    Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for MMS fair allocations. CoRR, abs/2104.04977, 2021

    2021

  20. [28]

    An improved approximation algorithm for maximin shares

    Jugal Garg and Setareh Taki. An improved approximation algorithm for maximin shares. Artif. Intell. , 300:103547, 2021

    2021

  21. [29]

    Fair allocation of indivisible goods: Improvement

    Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvement. Math. Oper. Res., 46(3):1038–1053, 2021

    2021

  22. [30]

    Fair allocation of indivisible goods: Beyond additive valuations

    Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Beyond additive valuations. Artif. Intell., 303:103633, 2022

    2022

  23. [31]

    Haxell and Tibor Szab ´o

    Penny E. Haxell and Tibor Szab ´o. Odd independent transversals are odd. Comb. Probab. Comput., 15(1-2):193– 211, 2006

    2006

  24. [32]

    Guaranteeing maximin shares: Some agents left behind

    Hadi Hosseini and Andrew Searns. Guaranteeing maximin shares: Some agents left behind. CoRR, abs/2105.09383, 2021

    2021

  25. [33]

    Ordinal maximin share approximation for goods

    Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi. Ordinal maximin share approximation for goods. J. Artif. Intell. Res., 74, 2022

    2022

  26. [34]

    EFX orientations of multigraphs

    Kevin Hsu. EFX orientations of multigraphs. CoRR, abs/2410.12039, 2024

    2024

  27. [35]

    Maximin shares in hereditary set systems

    Halvard Hummel. Maximin shares in hereditary set systems. CoRR, abs/2404.11582, 2024

    2024

  28. [36]

    Maximin share allocations for assignment valuations

    Pooja Kulkarni, Rucha Kulkarni, and Ruta Mehta. Maximin share allocations for assignment valuations. In AAMAS, pages 2875–2876. ACM, 2023

    2023

  29. [37]

    Fair Division in Game theoretic Settings

    David Kurokawa. Fair Division in Game theoretic Settings. PhD thesis, Carnegie Mellon University, 2017

    2017

  30. [38]

    Procaccia, and Junxing Wang

    David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. J. ACM, 65(2):8:1–8:27, 2018

    2018

  31. [39]

    Envy-free and efficient allocations for graphical valuations

    Neeldhara Misra and Aditi Sethia. Envy-free and efficient allocations for graphical valuations. CoRR, abs/2410.14272, 2024. 23

    2024

  32. [40]

    Improved maximin guarantees for subadditive and fractionally subad- ditive fair allocation problem

    Masoud Seddighin and Saeed Seddighin. Improved maximin guarantees for subadditive and fractionally subad- ditive fair allocation problem. Artif. Intell., 327:104049, 2024

    2024

  33. [41]

    On the existence of efx allocations in multigraphs, 2025

    Alkmini Sgouritsa and Minas Marios Sotiriou. On the existence of efx allocations in multigraphs, 2025

    2025

  34. [42]

    Extremal problems for transversals in graphs with bounded degree

    Tibor Szab ´o and G ´abor Tardos. Extremal problems for transversals in graphs with bounded degree. Comb., 26(3):333–351, 2006

    2006

  35. [43]

    On the configuration-lp for scheduling on unrelated machines

    Jos ´e Verschae and Andreas Wiese. On the configuration-lp for scheduling on unrelated machines. CoRR, abs/1011.4957, 2010

    2010 arXiv

  36. [44]

    Wanless and David R

    Ian M. Wanless and David R. Wood. A general framework for hypergraph coloring. SIAM Journal on Discrete Mathematics, 36(3):1663–1677, 2022

    2022

  37. [45]

    On the structure of envy-free orientations on graphs

    Jinghan A Zeng and Ruta Mehta. On the structure of envy-free orientations on graphs. CoRR, abs/2404.13527, 2024

    2024

  38. [46]

    A complete landscape of EFX allocations on graphs: Goods, chores and mixed manna

    Yu Zhou, Tianze Wei, Minming Li, and Bo Li. A complete landscape of EFX allocations on graphs: Goods, chores and mixed manna. In IJCAI, pages 3049–3056. ijcai.org, 2024. 24

    2024

Pith tools

Reviewed May 19, 2026 · model on record in the stance chip above.