pith. sign in

arxiv: 2606.13057 · v1 · pith:U4U5SHHInew · submitted 2026-06-11 · 💻 cs.GT

Approximate Maximin Share with Subjective Divisibility: Beating the 1/2 Barrier

Xiaohui Bei , Ke Ding , Bo Li , Fangxiao Wang This is my paper

Pith reviewed 2026-06-27 05:25 UTC · model grok-4.3

classification 💻 cs.GT
keywords maximin sharesubjective divisibilityfair allocationapproximation algorithmsunary valuationsgame theory
0
0 comments X

The pith

Subjective divisibility limits maximin share fairness to a 2/3 approximation even when all items have equal value.

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

This paper studies maximin share fairness when agents hold different perceptions of whether goods can be divided. It proves that 2/3 is the best possible approximation ratio even in the simple unary setting where every item has the same value to every agent. The authors then give new algorithms that raise the guarantee for the general case of heterogeneous valuations from 1/2 to 5/9. For four or fewer agents they supply polynomial-time procedures that achieve the tight 2/3 ratio. These bounds are shown to be optimal.

Core claim

The paper proves that the optimal approximation ratio for MMS under subjective divisibility is 2/3 even for unary valuations, develops algorithms achieving 5/9 in the general heterogeneous case, and computes 2/3-approximate allocations in polynomial time for up to four agents, with all bounds tight.

What carries the argument

New algorithmic techniques that overcome the constraints of subjective divisibility to construct allocations meeting the stated MMS ratios.

If this is right

  • A 5/9-approximate MMS allocation is guaranteed to exist for any number of agents under subjective divisibility.
  • No allocation better than 2/3-approximate MMS is possible even when all items have identical value.
  • For at most four agents, a 2/3-approximate MMS allocation can be found in polynomial time.
  • The 2/3 ratio is tight for the unary case and for small numbers of agents.

Where Pith is reading between the lines

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

  • The gap between the 2/3 unary bound and the higher ratios known for objective divisibility suggests that subjective perceptions impose a qualitatively stricter limit.
  • The techniques for small numbers of agents may combine with existing methods to raise the general-case guarantee above 5/9 for moderate agent counts.
  • Similar model extensions could be tested for other fairness concepts such as proportionality or envy-freeness.

Load-bearing premise

The subjective divisibility model permits allocations at these ratios without adding computational hardness beyond what is already present.

What would settle it

An explicit instance with five or more agents for which no 5/9-approximate MMS allocation exists under subjective divisibility.

Figures

Figures reproduced from arXiv: 2606.13057 by Bo Li, Fangxiao Wang, Ke Ding, Xiaohui Bei.

Figure 1
Figure 1. Figure 1: The structure of Nc and M in Case 2 of Theorem 1 Proof of Claim 1. We prove the claim by induction. When i = 1, item g 1 is divisible for four agents, namely, a 1 1 , a1 2 , and two agents in N3 who think g 1 is divisible. Thus the removal of any two agents in N1 2 ∪ N3 still admits a match between two remaining agents and g 1 . Assume the claim is true for i = 1, . . . , k − 1 and we consider the k-th rou… view at source ↗
Figure 2
Figure 2. Figure 2: The allocation of medium items of ai Combining all cases, and noting that only bundles under Inequality (3) may exceed value 1, we obtain X aj∈(X\X′)∪(Y \Y ′)∪Z vi(Aj ) + X aj∈X′∪Y ′ vi(Bj ) ≤ 10 9 · j u 3 k + 17 18 · (u − 1 − j u 3 k ) = 17 18 (u − 1) + 3 18 · j u 3 k ≤ u − 1 + 1 18 . Hence, after the removal of u − 1 agents, agent ai values the remaining items at least 17 18 , which suffices. We next con… view at source ↗
Figure 3
Figure 3. Figure 3: The MMS partition of ai in the instance with u + qi agents still applies, which gives X aj∈(X\X′)∪(Y \Y ′)∪Z vi(Aj ) + X aj∈X′∪Y ′ vi(Bj ) ≤ u − 1 + 1 18 . We omit the details here. Now suppose hind > u. In Step 3, items {g ind 2u−hind+1, . . . , gind hind } are assigned in bundles of two (see [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗
read the original abstract

Maximin share (MMS) stands out as a central notion in fair resource allocation. It is known that exact MMS fairness is not always attainable, especially when agents differ along two dimensions: their valuations and their perceptions of the divisibility of resources. The former case with heterogeneous valuations has been widely studied in the literature. The latter, referred to as subjective divisibility by Bei et al., [Games Econ. Behav. 2025], remains much less explored. We study MMS approximation under subjective divisibility. First, we prove that even in the unary valuation setting, where all items have equal value, the optimal approximation ratio is 2/3. This result is somewhat surprising since in the objective setting, even when agents have heterogeneous valuations, the best possible approximation ratio is at least 7/9 [Huang and Zhou, 2025]. We then address the general case with both valuation heterogeneity and subjective divisibility. Previous work shows the existence of a 1/2-approximate MMS allocation. In this paper, we develop new algorithmic techniques that overcome the difficulties posed by subjective divisibility, and improve the approximation guarantee to 5/9. Finally, we complement this result with small-agent cases. For up to four agents, we give polynomial-time algorithms that compute 2/3-approximate MMS fair allocations. These bounds are tight. Our results deepen the understanding of MMS fairness under heterogeneous valuations and subjective divisibility, and provide a new perspective for this emerging model.

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 / 2 minor

Summary. The paper studies maximin share (MMS) fairness under subjective divisibility. It proves a tight 2/3 approximation ratio is optimal even for unary valuations (where all items have equal value to an agent). For the general case with heterogeneous valuations, new algorithmic techniques improve the guarantee from the prior 1/2 to 5/9. For n ≤ 4 agents, it supplies polynomial-time algorithms achieving the 2/3 ratio, with matching lower bounds.

Significance. If the stated proofs, algorithms, and tightness arguments hold, the work meaningfully advances the subjective-divisibility model introduced by Bei et al. The 2/3 unary bound is surprising relative to the 7/9 objective-setting guarantee and demonstrates that subjective divisibility imposes a genuine additional constraint. The 5/9 general-case improvement and explicit poly-time procedures for small n supply both theoretical progress and concrete algorithmic tools. The self-contained constructions noted in the stress-test strengthen the contribution.

minor comments (2)
  1. [Abstract] Abstract: the sentence 'These bounds are tight' would be clearer if it explicitly identified the two separate tightness results (unary 2/3 and n≤4 2/3).
  2. [Introduction] The manuscript should include a short table or paragraph contrasting the new ratios with the objective-setting bounds of Huang and Zhou (2025) to highlight the effect of subjective divisibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their thorough reading and positive evaluation of the manuscript. We are grateful for the recommendation to accept and for highlighting the tightness of the 2/3 unary bound, the 5/9 general-case improvement, and the explicit polynomial-time algorithms for n≤4 as meaningful advances over prior work in the subjective-divisibility model.

Circularity Check

0 steps flagged

No significant circularity; minor self-citation to model definition only

full rationale

The paper's central results consist of new lower-bound constructions establishing 2/3 as tight even for unary valuations, a new algorithmic technique achieving 5/9 in the general case, and explicit poly-time procedures for n≤4. These rely on direct incorporation of subjective-divisibility constraints into the proofs and algorithms rather than any reduction to fitted parameters, self-definitions, or load-bearing self-citations. The sole citation to Bei et al. (2025) defines the model being studied and is not invoked to justify the approximation ratios themselves; each bound is supported by independent, self-contained arguments supplied in the manuscript.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard mathematical assumptions from algorithmic game theory and the subjective divisibility model from prior cited work; no free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (1)
  • domain assumption Additive valuations and the MMS definition as standard in fair division literature
    Invoked throughout the abstract as the baseline for approximation ratios.

pith-pipeline@v0.9.1-grok · 5812 in / 1235 out tokens · 24661 ms · 2026-06-27T05:25:23.971775+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

49 extracted references · 5 canonical work pages

  1. [1]

    Hannaneh Akrami and Jugal Garg. 2024. Breaking the 3/4 Barrier for Approximate Max- imin Share. InSODA. SIAM, 74–91

    2024

  2. [2]

    Moshe Babaioff and Uriel Feige. 2022. Fair Shares: Feasibility, Domination and Incentives. InEC. ACM, 435

    2022

  3. [3]

    Siddharth Barman and Sanath Kumar Krishnamurthy. 2020. Approximation Algorithms for Maximin Fair Division.ACM Trans. Economics and Comput.8, 1 (2020), 5:1–5:28

    2020

  4. [4]

    Xiaohui Bei, Zihao Li, Jinyan Liu, Shengxin Liu, and Xinhang Lu. 2021. Fair division of mixed divisible and indivisible goods.Artif. Intell.293 (2021), 103436

    2021

  5. [5]

    Xiaohui Bei, Shengxin Liu, and Xinhang Lu. 2025. Fair division with subjective divisibility. Games Econ. Behav.151, 127–147

    2025

  6. [6]

    Xiaohui Bei, Shengxin Liu, Xinhang Lu, and Hongao Wang. 2021. Maximin fairness with mixed divisible and indivisible goods.Auton. Agents Multi Agent Syst.35, 2 (2021), 34

    2021

  7. [7]

    Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. 2021. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. InAPPROX-RANDOM (LIPIcs, Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 1:1–1:23

    2021

  8. [8]

    Xiaolin Bu, Zihao Li, Shengxin Liu, Xinhang Lu, and Biaoshuai Tao. 2024. Best-of-Both- Worlds Fair Allocation of Indivisible and Mixed Goods.CoRRabs/2410.06877 (2024)

    work page arXiv 2024

  9. [9]

    Eric Budish. 2011. The combinatorial assignment problem: Approximate competitive equi- librium from equal incomes.Journal of Political Economy119, 6, 1061–1103

    2011

  10. [10]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Herv´ e Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The Unreasonable Fairness of Maximum Nash Welfare.ACM Trans. Economics and Comput.7, 3 (2019), 12:1–12:32

    2019

  11. [11]

    Uriel Feige and Alexey Norkin. 2022. Improved maximin fair allocation of indivisible items to three agents.CoRRabs/2205.05363 (2022)

    work page arXiv 2022

  12. [12]

    Uriel Feige, Ariel Sapir, and Laliv Tauber. 2021. A Tight Negative Example for MMS Fair Allocations. InWINE (Lecture Notes in Computer Science, Vol. 13112). Springer, 355–372

    2021

  13. [13]

    1958.Puzzle-Math

    George Gamow and Marvin Stern. 1958.Puzzle-Math. Viking press

    1958

  14. [14]

    Jugal Garg, Peter McGlaughlin, and Setareh Taki. 2019. Approximating Maximin Share Allocations. InSOSA (OASIcs, Vol. 69). Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Infor- matik, 20:1–20:11. 18

    2019

  15. [15]

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

    2021

  16. [16]

    Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. 2018. Fair Allocation of Indivisible Goods: Improvements and Generaliza- tions. InEC. ACM, 539–556

    2018

  17. [17]

    Ehsan Heidari, Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei

  18. [18]

    Improved Maximin Share Guarantee for Additive Valuations.CoRRabs/2510.10423 (2025)

    work page arXiv 2025

  19. [19]

    Xin Huang and Shengwei Zhou. 2025. An FPTAS for 7/9-Approximation to Maximin Share Allocations.CoRRabs/2511.13056 (2025)

    work page arXiv 2025

  20. [20]

    Procaccia, and Junxing Wang

    David Kurokawa, Ariel D. Procaccia, and Junxing Wang. 2018. Fair Enough: Guaranteeing Approximate Maximin Shares.J. ACM65, 2 (2018), 8:1–8:27

    2018

  21. [21]

    Bo Li, Zihao Li, Shengxin Liu, and Zekai Wu. 2024. Allocating Mixed Goods with Cus- tomized Fairness and Indivisibility Ratio. InIJCAI. ijcai.org, 2868–2876

    2024

  22. [22]

    Zihao Li, Shengxin Liu, Xinhang Lu, and Biaoshuai Tao. 2023. Truthful Fair Mechanisms for Allocating Mixed Divisible and Indivisible Goods. InIJCAI. ijcai.org, 2808–2816

    2023

  23. [23]

    Claudia Lindner and J¨ org Rothe. 2016. Cake-Cutting: Fair Division of Divisible Goods. InEconomics and Computation, J¨ org Rothe (Ed.). Springer, Chapter 7, 395–491

    2016

  24. [24]

    Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On ap- proximately fair allocations of indivisible goods. InProceedings of the 5th ACM Conference on Electronic Commerce. 125–131

    2004

  25. [25]

    Shengxin Liu, Xinhang Lu, Mashbat Suzuki, and Toby Walsh. 2024. Mixed Fair Division: A Survey.J. Artif. Intell. Res.80 (2024), 1373–1406

    2024

  26. [26]

    2003.Fair division and collective welfare

    Herv´ e Moulin. 2003.Fair division and collective welfare. MIT Press

    2003

  27. [27]

    Koichi Nishimura and Hanna Sumita. 2023. Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods.CoRRabs/2302.13342 (2023)

    work page arXiv 2023

  28. [28]

    Procaccia

    Ariel D. Procaccia. 2016. Cake Cutting Algorithms. InHandbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J´ erˆ ome Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, Chapter 13, 311–330

    2016

  29. [29]

    Hugo Steinhaus. 1949. Sur la division pragmatique.Econometrica: Journal of the Econo- metric Society(1949), 315–319

    1949

  30. [30]

    Hal R. Varian. 1974. Equity, Envy and Efficiency.Journal of Economic Theory9 (1974), 63–91. 19 Appendix A Tight Approximation for Three and Four Agents In this section, we prove Theorems 3 and 4. A.1 Additional Notations We begin by normalizing the instances, which ensures that our algorithms run in polynomial time, and introduce some preliminary techniqu...

    1974

  31. [31]

    For agenta 2, since she selects the better one betweenBandB ′, her value is at least 1 2 ·v 2(M)≥ 1 2 · 4 3 = 2

    Thus, no matter which bundle is left to her, agenta 1 is satisfied regarding 2 3 ·MMS 1. For agenta 2, since she selects the better one betweenBandB ′, her value is at least 1 2 ·v 2(M)≥ 1 2 · 4 3 = 2

  32. [32]

    By Lemma 5, if we are able to find a nice bundle when the original instance contains more than two agents, then we directly obtain a 2 3-MMS allocation

    So (A 1, A2) yields a 2 3-MMS allocation. By Lemma 5, if we are able to find a nice bundle when the original instance contains more than two agents, then we directly obtain a 2 3-MMS allocation. Hence, we have the following corollary, which was proved in [5]. The correctness of Algorithm 5 for two agents is established from Lemma 5. We state it here with ...

  33. [33]

    Hence,v j(Aj)≥ 2 3 ≥ 2 3 MMSj

    After that, we allocateBto agenta j asA j and remove them from the instance. Hence,v j(Aj)≥ 2 3 ≥ 2 3 MMSj. Lemma 7.If there exista i ∈Nandg∈G 1 such thatv i(G2)≥ 2 3 −v i(g), then the set of items Bselected in Line 7-9 is a nice bundle. Proof.Given that every agent inNvalues any item inG 1 less than 2 3, and any item inG 2 no more than 1 3, no agent inN\...

  34. [34]

    In either way a 2 3-MMS allocation is finally achieved. Lemma 9.Ifv i(G2)< 2 3 −v i(g)for eacha i ∈Nandg∈G 1, and|G 1| ≥6, we can find a set of agentsN ′ and their allocation(A i)ai∈N ′ by Algorithm 7 with the following two properties hold: (i) Every agenta i inN ′ are allocated two items{g 1, g2}fromG 1 thatv i(g1)> 1 3 andv i(g2)> 1 3; (ii) Every agenta...

  35. [35]

    For the remaining agents inN ′ and items inG 1, we can allocate each agenta i ∈N ′ two itemsg 1, g2 inG 1 such thatv i(g1)> 1 3 andv i(g2)> 1

    In addition, there is no subsetB ′ ofN ′ and the set of itemsS ′ ={g∈G 1|∃ai ∈B ′, vi(g)> 1 3 }such that|S ′|<2|B ′|even|B ′|= 1. For the remaining agents inN ′ and items inG 1, we can allocate each agenta i ∈N ′ two itemsg 1, g2 inG 1 such thatv i(g1)> 1 3 andv i(g2)> 1

  36. [36]

    Hence, the lemma is proved

    For every agenta j ∈N\N ′, vj(S ai∈N ′ Ai)≤ 2 3 |N ′|. Hence, the lemma is proved. In the following part, we focus on two cases when|G 1|= 5: there exists an agent that has at least four indivisible goods inG 1, or each agent has at most three indivisible goods inG 1. Before that, we want to find some properties for Cases 3 and 4. 23 ALGORITHM 7:Reduction...

  37. [37]

    Based on Observation 3, every item inG 1 is medium to each agent in Cases 3 and 4

    Thus, property (ii) and (iii) are implied. Based on Observation 3, every item inG 1 is medium to each agent in Cases 3 and 4. For Case 3 wherev i(G2)< 2 3 −vi(g) for eacha i ∈Nandg∈G 1,|G 1|= 5 and there exist two agentsa j, ak who share the same divisible itemg d ∈G 1, we arbitrarily choose two items from G1 \ {gd}, denoted byg 1 andg 2. Via the modified...

  38. [38]

    Therefore, v3(M\ {g 1, gd, g2})≥3−2 = 1 and we get a 2 3-MMS allocation

    For the remaining agenta 3, we havev 3({g1, gd, g2})≤3∗ 2 3 = 2. Therefore, v3(M\ {g 1, gd, g2})≥3−2 = 1 and we get a 2 3-MMS allocation. 24 For Case 4 wherev i(G2)< 2 3 −v i(g) for eacha i ∈Nandg∈G 1,|G 1|= 5 and there exists an agenta j who has at least four indivisible items inG 1, the algorithm allocatesa j with a set of items max g∈G1 vi(g)∪G 2 asA j...

  39. [39]

    Therefore, she values all the remaining items by at least 5

  40. [40]

    Based on that, we add the sixth condition for further analysis: •(6) Each agent considers at least one item in ˆG1 divisible

    Hence,g 1, g2 satisfy the definition of a nice bundle for the reduced instance anda j is the corresponding agent. Based on that, we add the sixth condition for further analysis: •(6) Each agent considers at least one item in ˆG1 divisible. Claim 6.If one remaining agent inN r values the temporary bundleA 4 by no more than 2 3, Condition (1) or (2) cannot ...

  41. [41]

    We now consider the situation when we reduce the instance with 4 agents by giving one single itemgto one agent who values it by no less than 2

    Hence, vi( ˆG2 ∪ {g})≥v i( ˆG1 ∪ ˆG2)−v i( ˆG1 \ {g})≥4− 2 3 − 8 3 = 2 3 , contradicting to Condition (2). We now consider the situation when we reduce the instance with 4 agents by giving one single itemgto one agent who values it by no less than 2

  42. [42]

    Ifgis divisible for agenta i,gis allocated partially and the value of the allocated fraction ofgfor her is no larger than 2

    For any agenta i inN r, ifgis indivisible, the maximin share of her does not decrease. Ifgis divisible for agenta i,gis allocated partially and the value of the allocated fraction ofgfor her is no larger than 2

  43. [43]

    Hence we have an additional condition: •(7) At least two items are removed

    By Claim 6, Condition (1) or (2) must be broken and Algorithm 6 can still work. Hence we have an additional condition: •(7) At least two items are removed. Lemma 19.After the removal ofa 4 andA 4 with Conditions (1)-(7) satisfied, we withdraw the agenta 4 and the temporary bundleA 4. A new reduction can be found in polynomial time such that the new reduce...

  44. [44]

    After this reduction, agenta 1 inN ′ r thinks the items inG 1 are all indivisible, which breaks Condition (6)

    If there is an agenta i inN\ {a 1}who valuesBno less than 2 3, allocateBto this agent and remove them. After this reduction, agenta 1 inN ′ r thinks the items inG 1 are all indivisible, which breaks Condition (6). Otherwise, there are three agents who value Bless than 2

  45. [45]

    Based on Claim 6, the new instance does not satisfy Conditions (2) and (3) at the same time

    We allocateBto agenta 1 asN 1 and remove them to get a new instance with 3 agents. Based on Claim 6, the new instance does not satisfy Conditions (2) and (3) at the same time. •Subsubcase 1.1.2:There are two agents who share a divisible item inG 1. Let the two agents and the item bea 1, a2 andg 1, respectively.g 1 is firstly added into bagBand then items ...

  46. [46]

    After this reduction, the reduced instance violates Condition (6)

    If one agent inN\{a 1, a2}valuesBno less than 2 3, allocateBto the agent and remove them. After this reduction, the reduced instance violates Condition (6). Otherwise, choose the agent in{a 1, a2}whoever valuesB\ {g 1}plus part ofg 1 by 2 3 with a smaller fraction of g1. Assume that agent isa 1. We allocateB\ {g 1} ∪ {len1(g1, 2 3)}to agenta 1 asA 1 and r...

  47. [47]

    Subcase 2:|G 1| ≥7

    Considering the proof of Subcase 1.1, Conditions (2), (3), and (6) must not simultaneously hold. Subcase 2:|G 1| ≥7. DenoteG 1 ={g 1, g2, . . . , g7, . . .}. Assume the item inA 4 ∩G 1 isg 6 and those in ˆG1 are{g 1, . . . , g5}. Since itemg 7 is not removed, onlya 4 thinksg 7 is medium. Similar to the discussion of Subcase 1.1, we withdrawA 4 anda 4.g 6 ...

  48. [48]

    Since Condition (4) shows any item in ˆG1 is medium for any agent inN r, there are 6 items{g 1,

    If there is one agent inN r who valuesBby no less than 2 3, allocateBto her and remove them. Since Condition (4) shows any item in ˆG1 is medium for any agent inN r, there are 6 items{g 1, . . . , g6}which are medium for at least one agent inN ′ r, breaking Condition (3). Otherwise, the three agents consider the value ofBis less than 2

  49. [49]

    Case 2:v i(G2)< 2 3 −v i(g0) for eacha i ∈N, g 0 ∈G 1;|G 1| ≥8

    By Claim 6, Condition (1) or (2) is broken. Case 2:v i(G2)< 2 3 −v i(g0) for eacha i ∈N, g 0 ∈G 1;|G 1| ≥8. In this case, if we find a temporary bundle, only one agent and two goods inG 1 are removed. As mentioned in Lemma 9, the value of the temporary bundle for the remaining agents is less than 2 3, which breaks Condition (1) or (2) by Claim 6. Since tw...