pith. sign in

arxiv: 2606.18921 · v1 · pith:UQGF6JDVnew · submitted 2026-06-17 · 💻 cs.GT

Epistemic Pairwise Maximin Share

Michal Feldman , Amos Fiat , Yael Nissan , Tomasz Ponitka This is my paper

Pith reviewed 2026-06-26 18:55 UTC · model grok-4.3

classification 💻 cs.GT
keywords fair divisionindivisible goodsepistemic fairnesspairwise maximin shareadditive valuationsbivalued valuationsEFX
0
0 comments X

The pith

An epistemic relaxation of pairwise maximin share guarantees 4/5-EPMMS allocations for additive valuations of indivisible goods.

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

The paper defines EPMMS as the epistemic relaxation of PMMS, a fairness notion stronger than EFX in the division of indivisible goods. It proves that 4/5-EPMMS allocations exist and can be computed efficiently when agents have additive valuations. For bivalued valuations the paper shows that full EPMMS allocations exist and can be computed, and in fact the stronger EGMMS guarantee holds. The same relaxation yields EPMMS allocations in two families of instances where MMS allocations are known not to exist: three additive agents, or agents of two distinct additive types.

Core claim

EPMMS allocations exist and are efficiently computable for additive valuations at the 4/5 level; for bivalued valuations full EPMMS allocations exist and the stronger EGMMS guarantee also holds. These positive results extend to instances with three additive agents and instances with two types of additive agents, both of which are settings in which MMS allocations need not exist.

What carries the argument

Epistemic pairwise maximin share (EPMMS), the epistemic relaxation of PMMS under which each agent believes there exists an allocation satisfying the pairwise maximin condition.

If this is right

  • 4/5-EPMMS allocations can be found in polynomial time for additive valuations.
  • Full EPMMS (and EGMMS) allocations can be found in polynomial time for bivalued valuations.
  • EPMMS allocations exist for every instance with three additive agents.
  • EPMMS allocations exist for every instance with two distinct additive valuation types.

Where Pith is reading between the lines

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

  • The same epistemic lens may be applied to other fairness notions whose existence is open for wider valuation classes.
  • Efficient algorithms for EPMMS may serve as building blocks for approximation algorithms for stricter notions such as PMMS itself.
  • The gap between EPMMS and MMS in the two-type and three-agent settings suggests that epistemic relaxations can recover existence precisely where deterministic maximin guarantees fail.

Load-bearing premise

The specific definition of the epistemic relaxation permits the existence and computation arguments to succeed for additive and bivalued valuations.

What would settle it

An explicit instance with additive valuations in which no allocation satisfies 4/5-EPMMS for every agent.

Figures

Figures reproduced from arXiv: 2606.18921 by Amos Fiat, Michal Feldman, Tomasz Ponitka, Yael Nissan.

Figure 1
Figure 1. Figure 1: Implications between fairness notions under non-degenerate additive valuations. Most [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of the relationships between the valuation classes derived in Appendix C. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the swapping argument used in the proof of Theorem 2. The bundles [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The two cases in the proof of Theorem 3. [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The weight function w used in the proof of Proposition C.8. Edges represent pairs with weight 1; all omitted pairs have weight 0. Proof. (OXS ⇏ PMMS-feasibility) Let M = {a, b, c, d} denote the set of items, and let X = {1, 2}. Define the weight function w : M × X → R≥0 by setting w(a, 1) = w(b, 1) = w(c, 2) = w(d, 2) = 1 and w(i, j) = 0 for all remaining pairs; see [PITH_FULL_IMAGE:figures/full_fig_p033_5.png] view at source ↗
read the original abstract

We introduce epistemic pairwise maximin share (EPMMS), a new fairness notion for fair division of indivisible goods. Two fundamental notions in this setting are envy-freeness up to any item (EFX) and pairwise maximin share (PMMS), with PMMS being stronger than EFX. While EFX has been extensively studied, far less is known about PMMS. Recent work shows that relaxing EFX via an epistemic perspective leads to substantial progress on the EFX problem, raising the question of whether a similar approach can advance our understanding of PMMS. Motivated by this, we initiate the study of EPMMS, the epistemic relaxation of PMMS. EPMMS is more challenging than EEFX: the key approaches underlying recent progress on epistemic EFX inherently fail to extend to EPMMS. We establish the following results. (1) For additive valuations, $4/5$-EPMMS allocations exist and can be efficiently computed. (2) For bivalued valuations, EPMMS allocations exist and can be efficiently computed; in fact, we obtain the stronger guarantee of epistemic groupwise maximin share (EGMMS), which also strengthens the existence of MMS allocations for this setting. (3) We prove that EPMMS allocations exist in two settings where MMS allocations need not exist: instances with three additive agents or two types of additive agents.

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 introduces epistemic pairwise maximin share (EPMMS), an epistemic relaxation of pairwise maximin share (PMMS) for allocating indivisible goods. It proves that 4/5-EPMMS allocations exist and can be efficiently computed for additive valuations; that EPMMS allocations (in fact the stronger epistemic groupwise maximin share, EGMMS) exist and can be efficiently computed for bivalued valuations; and that EPMMS allocations exist in two settings with additive valuations (three agents, or two agent types) where MMS allocations need not exist.

Significance. If the stated existence and algorithmic results hold, the work meaningfully advances the study of PMMS by demonstrating that its epistemic relaxation yields existence guarantees (with efficient computation) in valuation classes and agent settings where MMS itself fails. The observation that standard EEFX techniques do not carry over to EPMMS is a useful negative result that clarifies the distinct technical challenges. The strengthening to EGMMS for bivalued valuations is a notable additional contribution.

minor comments (2)
  1. [Abstract] Abstract: the claim that 'standard EEFX techniques do not carry over' is stated without a forward reference to the section containing the argument; adding a pointer would improve readability.
  2. The manuscript would benefit from an explicit comparison (perhaps as a table in the introduction) of the strength ordering and known existence results among MMS, PMMS, EFX, EEFX, EPMMS, and EGMMS.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive evaluation of our work. We are glad that the contribution of EPMMS as an epistemic relaxation of PMMS, along with the existence and algorithmic results for additive and bivalued valuations, is viewed as advancing the literature. Since the report contains no specific major comments or requested changes, we have no points to address point-by-point.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper defines a new epistemic fairness notion EPMMS and establishes existence plus efficient algorithms for additive valuations (4/5-EPMMS), bivalued valuations (full EPMMS and stronger EGMMS), and two MMS-impossible settings. These results rest on direct constructive proofs that exploit the specific structure of the newly introduced definition together with the given valuation classes; no step reduces by construction to a fitted parameter, self-citation chain, or renamed input, and the derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only abstract available; no free parameters, axioms, or invented entities can be identified from the provided text.

pith-pipeline@v0.9.1-grok · 5781 in / 969 out tokens · 22936 ms · 2026-06-26T18:55:57.969294+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

58 extracted references · 1 linked inside Pith

  1. [1]

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

    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

    2022

  2. [2]

    Epistemic EFX allocations exist for monotone valuations

    Hannaneh Akrami and Nidhi Rathi. Epistemic EFX allocations exist for monotone valuations. InAAAI, pages 13520–13528. AAAI Press, 2025

    2025

  3. [3]

    Achieving maximin share and EFX/EF1 guarantees simultaneously

    Hannaneh Akrami and Nidhi Rathi. Achieving maximin share and EFX/EF1 guarantees simultaneously. InAAAI, pages 13529–13537. AAAI Press, 2025

    2025

  4. [4]

    EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number.Oper

    Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number.Oper. Res., 73(2):738–751, 2025

    2025

  5. [5]

    Achieving EF1 and epistemic EFX guarantees simultaneously.CoRR, abs/2602.11732, 2026

    Hannaneh Akrami, Ryoga Mahara, Kurt Mehlhorn, and Nidhi Rathi. Achieving EF1 and epistemic EFX guarantees simultaneously.CoRR, abs/2602.11732, 2026

    arXiv 2026

  6. [6]

    A counterexample to efx;n≥ 3agents, m≥n + 5items, monotone valuations; via sat-solving.CoRR, abs/2604.18216, 2026

    Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, and Christoph Weidenbach. A counterexample to efx;n≥ 3agents, m≥n + 5items, monotone valuations; via sat-solving.CoRR, abs/2604.18216, 2026. 19

    Pith/arXiv arXiv 2026

  7. [7]

    Approximation algorithms for computing maximin share allocations.ACM Trans

    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

  8. [8]

    Comparing approximate relaxations of envy-freeness

    Georgios Amanatidis, Georgios Birmpas, and Vangelis Markakis. Comparing approximate relaxations of envy-freeness. InIJCAI, pages 42–48. ijcai.org, 2018

    2018

  9. [9]

    Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.Theor

    Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.Theor. Comput. Sci., 841:94–109, 2020

    2020

  10. [10]

    Voudouris

    Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris. Maximum nash welfare and other stories about EFX.Theor. Comput. Sci., 863:69–85, 2021

    2021

  11. [11]

    Voudouris, and Xiaowei Wu

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

    2023

  12. [12]

    EF2X exists for four agents

    Arash Ashuri, Vasilis Gkatzelis, and Alkmini Sgouritsa. EF2X exists for four agents. In AAAI, pages 13555–13563. AAAI Press, 2025

    2025

  13. [13]

    Knowl- edge, fairness, and social constraints

    Haris Aziz, Sylvain Bouveret, Ioannis Caragiannis, Ira Giagkousi, and Jérôme Lang. Knowl- edge, fairness, and social constraints. InAAAI, pages 4638–4645. AAAI Press, 2018

    2018

  14. [14]

    Near-optimal best-of-both-worlds fairness for few agents

    Moshe Babaioff and Gefen Frosh. Near-optimal best-of-both-worlds fairness for few agents. CoRR, abs/2602.14668, 2026

    arXiv 2026

  15. [15]

    Approximating nash social welfare under binary XOS and binary subadditive valuations

    Siddharth Barman and Paritosh Verma. Approximating nash social welfare under binary XOS and binary subadditive valuations. InWINE, Lecture Notes in Computer Science, pages 373–390. Springer, 2021

    2021

  16. [16]

    Groupwise maximin fair allocation of indivisible goods

    Siddharth Barman, Arpita Biswas, Sanath Kumar Krishna Murthy, and Yadati Narahari. Groupwise maximin fair allocation of indivisible goods. InAAAI, pages 917–924. AAAI Press, 2018

    2018

  17. [17]

    Fairness towards groups of agents in the allocation of indivisible items

    Nawal Benabbou, Mithun Chakraborty, Edith Elkind, and Yair Zick. Fairness towards groups of agents in the allocation of indivisible items. InIJCAI, pages 95–101. ijcai.org, 2019

    2019

  18. [18]

    Finding fair and efficient allocations when valuations don’t add up

    Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding fair and efficient allocations when valuations don’t add up. InSAGT, Lecture Notes in Computer Science, pages 32–46. Springer, 2020

    2020

  19. [19]

    Almost full EFX exists for four agents

    Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost full EFX exists for four agents. InAAAI, pages 4826–4833. AAAI Press, 2022

    2022

  20. [20]

    Characterizing conflicts in fair division of indivisible goods using a scale of criteria.Auton

    Sylvain Bouveret and Michel Lemaître. Characterizing conflicts in fair division of indivisible goods using a scale of criteria.Auton. Agents Multi Agent Syst., 30(2):259–290, 2016

    2016

  21. [21]

    The combinatorial assignment problem: approximate competitive equilibrium from equal incomes

    Eric Budish. The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. InBQGT, page 74:1. ACM, 2010. 20

    2010

  22. [22]

    Probing EFX via PMMS: (non- )existence results in discrete fair division

    Jaroslaw Byrka, Franciszek Malinka, and Tomasz Ponitka. Probing EFX via PMMS: (non- )existence results in discrete fair division. InAAAI, pages 16735–16742. AAAI Press, 2026

    2026

  23. [23]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Hervé 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

  24. [24]

    New fairness concepts for allocating indivisible items

    Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, and Giovanna Varricchio. New fairness concepts for allocating indivisible items. InIJCAI, pages 2554–2562. ijcai.org, 2023

    2023

  25. [25]

    A little charity guarantees almost envy-freeness.SIAM J

    Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness.SIAM J. Comput., 50(4):1336–1358, 2021

    2021

  26. [26]

    EFX exists for three agents.J

    Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents.J. ACM, 71(1):4:1–4:27, 2024

    2024

  27. [27]

    Exact and approximate maximin share allocations in multi-graphs

    George Christodoulou and Symeon Mastrakoulis. Exact and approximate maximin share allocations in multi-graphs. InAAAI, pages 16761–16769. AAAI Press, 2026

    2026

  28. [28]

    The existence and efficiency of PMMS allocations.Theor

    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

  29. [29]

    Maximin fair allocations with two item values.Preprint, 2022

    Uriel Feige. Maximin fair allocations with two item values.Preprint, 2022. Version: February 22, 2022. Available athttps://www.wisdom.weizmann.ac.il/~feige/mypapers/ MMSab.pdf

    2022

  30. [30]

    A tight negative example for MMS fair allocations

    Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for MMS fair allocations. InWINE, Lecture Notes in Computer Science, pages 355–372. Springer, 2021

    2021

  31. [31]

    On optimal tradeoffs between EFX and nash welfare

    Michal Feldman, Simon Mauras, and Tomasz Ponitka. On optimal tradeoffs between EFX and nash welfare. InAAAI, pages 9688–9695. AAAI Press, 2024

    2024

  32. [32]

    Exploring relations among fairness notions in discrete fair division.CoRR, abs/2502.02815, 2025

    Jugal Garg and Eklavya Sharma. Exploring relations among fairness notions in discrete fair division.CoRR, abs/2502.02815, 2025

    arXiv 2025

  33. [33]

    (almost full) EFX for three (and more) types of agents

    Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar, and Nithin Varma. (almost full) EFX for three (and more) types of agents. InAAAI, pages 13889–13896. AAAI Press, 2025

    2025

  34. [34]

    Ordinal maximin share approximation for goods.J

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

    2022

  35. [35]

    Maximin shares in hereditary set systems.ACM Trans

    Halvard Hummel. Maximin shares in hereditary set systems.ACM Trans. Economics and Comput., 13(3):12:1–12:33, 2025

    2025

  36. [36]

    Maximin shares under cardinality constraints

    Halvard Hummel and Magnus Lie Hetland. Maximin shares under cardinality constraints. Auton. Agents Multi Agent Syst., 40(1):9, 2026

    2026

  37. [37]

    EFX exists for three types of agents

    Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma. EFX exists for three types of agents. InEC, pages 101–128. ACM, 2025

    2025

  38. [38]

    On pareto-optimal and fair allocations with personalized bi-valued utilities.CoRR, abs/2507.18251, 2025

    Jiarong Jin and Biaoshuai Tao. On pareto-optimal and fair allocations with personalized bi-valued utilities.CoRR, abs/2507.18251, 2025. 21

    arXiv 2025

  39. [39]

    H. W. Kuhn. On games of fair division. In Martin Shubik, editor,Essays in Mathemati- cal Economics in Honor of Oskar Morgenstern, pages 29–37. Princeton University Press, Princeton, NJ, 1967

    1967

  40. [40]

    PhD thesis, Carnegie Mellon University, 2017

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

    2017

  41. [41]

    Procaccia, and Junxing Wang

    David Kurokawa, Ariel D. Procaccia, and Junxing Wang. When can the maximin share guarantee be guaranteed? InAAAI, pages 523–529. AAAI Press, 2016

    2016

  42. [42]

    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

  43. [43]

    Combinatorial auctions with decreasing marginal utilities.Games Econ

    Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities.Games Econ. Behav., 55(2):270–296, 2006

    2006

  44. [44]

    Gross substitutability: An algorithmic survey.Games Econ

    Renato Paes Leme. Gross substitutability: An algorithmic survey.Games Econ. Behav., 106:294–316, 2017

    2017

  45. [45]

    The conference paper assignment problem: Using order weighted averages to assign indivisible goods

    Jing Wu Lian, Nicholas Mattei, Renee Noble, and Toby Walsh. The conference paper assignment problem: Using order weighted averages to assign indivisible goods. InAAAI, pages 1138–1145. AAAI Press, 2018

    2018

  46. [46]

    Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

    Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approxi- mately fair allocations of indivisible goods. InEC, pages 125–131. ACM, 2004

    2004

  47. [47]

    Existence of EFX for two additive valuations.Discret

    Ryoga Mahara. Existence of EFX for two additive valuations.Discret. Appl. Math., 340: 115–122, 2023

    2023

  48. [48]

    Almost envy-freeness with general valuations.SIAM J

    Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations.SIAM J. Discret. Math., 34(2):1039–1068, 2020

    2020

  49. [49]

    Harvard University Press, Cambridge, MA, 1971

    John Rawls.A Theory of Justice. Harvard University Press, Cambridge, MA, 1971

    1971

  50. [50]

    The problem of fair division.Econometrica, 16(1):101–104, 1948

    Hugo Steinhaus. The problem of fair division.Econometrica, 16(1):101–104, 1948. A Separations between EPMMS and EEFX A.1 PMMS Is Not Preserved Under Envy-Cycle Elimination We begin by highlighting a fundamental difference between PMMS and EFX. The central operation of the Envy-Cycle Elimination algorithm (Algorithm 1) is the envy-cycle elimination step (L...

    1948

  51. [51]

    Without loss of generality, suppose this holds forX′

  52. [52]

    Hence agent2PMMS-envies agent1, a contradiction

    Then µ(2, X′ 1 ∪X ′ 2)≥µ(2,{3,3,3,3} ∪ {5,5}) = 11 = min{5 + 3 + 3,5 + 3 + 3}. Hence agent2PMMS-envies agent1, a contradiction. We conclude that MMS does not imply EPMMS. We now show that EPMMS is incomparable to EFX. 26 Observation A.8.Neither EPMMS nor EFX implies the other, even when agents have identical bivalued valuations (a special case of additive...

  53. [53]

    , ˆXn)for the identical rankings instance ˆI

    Base Allocation:Compute the target allocation ˆX = ( ˆX1, . . . , ˆXn)for the identical rankings instance ˆI

  54. [54]

    , am)such that ak = i if the k-th item in the identical ranking is assigned to agentiinˆX

    Picking Sequence:Define the sequence L = (a1, a2, . . . , am)such that ak = i if the k-th item in the identical ranking is assigned to agentiinˆX

  55. [55]

    Let X be the resulting allocation

    Actual Allocation:Execute thePick( I, L)routine: in each step k, agent ak picks their favorite remaining item according to their original valuationvi. Let X be the resulting allocation. To analyze how values shift when translatingˆX to X, we rely on a structural lemma introduced by Caragiannis et al [24]. Lemma E.5(Lemma 2 in [24]).For every agent i∈ [n],...

  56. [56]

    Agent1is unenvied before this assignment since her bundle is empty

    Agent1receives item g1. Agent1is unenvied before this assignment since her bundle is empty

  57. [57]

    Agent2receives items g2 and g3. Agent2is unenvied before each of these assignments: initially her bundle is empty, and after receivingg2, agent1values {g2} at2(equal to her own bundle) and agent3values{g 2}at0, so neither envies agent2

  58. [58]

    Before each assignment, agent3is unenvied since agents1and2value any subset of {g4, g5, g6} at no more than their own bundles (2and4, respectively)

    Agent3receives items g4, g5, and g6. Before each assignment, agent3is unenvied since agents1and2value any subset of {g4, g5, g6} at no more than their own bundles (2and4, respectively). At this point, the envy graph, whose nodes are the agents and which contains an edgei→j wheneverv i(Xj)> v i(Xi), is as follows: 1 23 No agent has in-degree0, so the algor...