pith. sign in

arxiv: 2506.20317 · v2 · submitted 2025-06-25 · 💻 cs.GT

Exact and approximate maximin share allocations in multi-graphs

George Christodoulou , Symeon Mastrakoulis This is my paper

Pith reviewed 2026-05-19 08:27 UTC · model grok-4.3

classification 💻 cs.GT
keywords maximin sharegraphical valuationsfair allocationindivisible itemsadditive valuationssubadditive valuationsPMMS
0
0 comments X

The pith

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.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

Load-bearing premise

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

What would settle it

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

Figures

Figures reproduced from arXiv: 2506.20317 by George Christodoulou, Symeon Mastrakoulis.

Figure 1
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 re… view at source ↗
Figure 2
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 alloc… view at source ↗
Figure 3
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… view at source ↗
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, j of an overconstrained set. With blue are the bundles Si,ki = Bi,ki ∩  X (i) ∪ X ′(i)  with X (i) j ⊆ Bj,1 and X ′(i) j ⊆ Bj,2. With red … view at source ↗
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 independent transversal set ensures an allocation of bundles Si,ki . In the case where |P| = 4, no such independent set guarantee to exist, as shown … view at source ↗
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.

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.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 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.

axioms (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.

pith-pipeline@v0.9.0 · 5646 in / 1235 out tokens · 37355 ms · 2026-05-19T08:27:21.659591+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages · 2 internal anchors

  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 internal anchor Pith review Pith/arXiv arXiv 2018

  9. [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

    work page 2017

  10. [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

    work page 2021

  11. [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

    work page 2020

  12. [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

    work page arXiv 2012

  13. [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

    work page arXiv 2023

  14. [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

    work page arXiv 2024

  15. [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

    work page 2011

  16. [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

    work page 2019

  17. [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

    work page arXiv 2023

  18. [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

    work page arXiv 2024

  19. [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

    work page 2025

  20. [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

    work page 2023

  21. [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

    work page arXiv 2021

  22. [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

    work page 2024

  23. [23]

    Ef1 and efx orientations, 2024

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

    work page 2024

  24. [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

    work page 2014

  25. [25]

    Fair allocations with subadditive and xos valuations, 2025

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

    work page 2025

  26. [26]

    Concentration and maximin fair allocations for subadditive valuations, 2025

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

    work page 2025

  27. [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

    work page arXiv 2021

  28. [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

    work page 2021

  29. [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

    work page 2021

  30. [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

    work page 2022

  31. [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

    work page 2006

  32. [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

    work page arXiv 2021

  33. [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

    work page 2022

  34. [34]

    EFX orientations of multigraphs

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

    work page arXiv 2024

  35. [35]

    Maximin shares in hereditary set systems

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

    work page arXiv 2024

  36. [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

    work page 2023

  37. [37]

    Fair Division in Game theoretic Settings

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

    work page 2017

  38. [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

    work page 2018

  39. [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

    work page arXiv 2024

  40. [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

    work page 2024

  41. [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

    work page 2025

  42. [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

    work page 2006

  43. [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

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  44. [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

    work page 2022

  45. [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

    work page arXiv 2024

  46. [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

    work page 2024