pith. sign in

arxiv: 2606.11494 · v1 · pith:N6LMWCDPnew · submitted 2026-06-09 · 🧮 math.OC · econ.TH

Epistemic fair division of independence structures

Marcin Anholcer , Maciej Bartkowiak , Bart{\l}omiej Bosek , Jaros{\l}aw Grytczuk This is my paper

Pith reviewed 2026-06-27 11:59 UTC · model grok-4.3

classification 🧮 math.OC econ.TH
keywords fair divisionindependence structuresEF1epistemic fairnessmatroidsacyclic bundlesarboricity
0
0 comments X

The pith

For any downward-closed independence structure, epistemic EF1 partitions into admissible bundles always exist.

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

The paper establishes that when indivisible goods must be split into bundles that each form an independent set in a prescribed downward-closed family, fair allocations remain possible. For agents with identical additive valuations, ordinary EF1 allocations exist whenever the number of agents meets or exceeds the arboricity of the structure. For agents with arbitrary additive valuations, the weaker epistemic EF1 condition is always satisfied: each agent receives an independent set such that some completion of the remaining goods into independent sets leaves the agent envy-free up to one good. The claim is proved first for abstract independence structures and then specialized to graphs and matroids, with explicit algorithms supplied for both the identical-valuation and general cases.

Core claim

For any independence structure on a ground set of goods and any collection of additive agent valuations, epistemic EF1 partitions always exist. Each agent is assigned an independent set for which there is a partition of the remaining goods into independent sets such that the agent does not envy any other bundle by more than one good.

What carries the argument

An independence structure: a family of subsets of goods that is closed under taking subsets and defines the admissible bundles each agent may receive.

If this is right

  • When all agents share the same valuation, ordinary EF1 partitions exist once the number of agents is at least the arboricity.
  • Two polynomial-time algorithms compute the required epistemic EF1 partitions for the general case and the identical-valuation case.
  • Any Hamiltonian matroid that can be partitioned into two independent sets admits an EF1 bipartition under a common monotone valuation.
  • The same existence result applies directly to the problem of partitioning the edges of a graph into acyclic subgraphs.

Where Pith is reading between the lines

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

  • The epistemic relaxation may allow fair division results to survive under other combinatorial constraints that block ordinary EF1.
  • Similar existence statements could be checked for proportionality or maximin share fairness inside the same class of independence structures.
  • The proof technique might extend to weighted or matroid-intersection constraints without requiring identical valuations.

Load-bearing premise

The collection of admissible bundles must be downward-closed, so that every subset of an admissible bundle remains admissible.

What would settle it

An explicit independence structure together with additive valuations for which no assignment of independent sets satisfies the epistemic EF1 condition for every agent.

read the original abstract

We study the problem of fair division of indivisible goods with constraints imposed by a prescribed independence structure, that is, a family of subsets of goods closed under taking subsets. As a motivating example, imagine that the goods to be divided are the available connections in a logistic, financial, or social network. The admissible bundle of goods for each agent must correspond to an acyclic set of edges, corresponding to a basic feasible solution to a linear network problem to be solved. Suppose that all agents assign the same value to each good (in the example, the network connections are equally important for every agent) and evaluate each bundle by summing the values of its goods. Is there a fair partition of the goods into such acyclic bundles? Surprisingly, the answer is yes, provided that the number of agents is at least the arboricity of $G$, and the fairness requirement is envy-freeness up to one good (EF1). The situation becomes more mysterious when agents have arbitrary additive valuations. Our main result guarantees that, in this case, epistemic EF1 partitions always exist, which means that each agent receives an acyclic bundle for which there exists a feasible partition of the remaining goods into acyclic bundles that they do not envy up to one good. We derive this conclusion from a general result for abstract independence structures defined on the sets of goods. We also discuss connections with several conjectures concerning matroids. In particular, we prove that any Hamiltonian matroid partitionable into two independent sets admits an EF1 bipartition with respect to a common monotone valuation. We complement our results with a constructive perspective: we present explicitly two algorithms for computing the fair allocations described above. Finally, we provide illustrative examples to demonstrate these algorithms on specific instances.

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

2 major / 2 minor

Summary. The paper studies fair division of indivisible goods under a downward-closed independence structure constraint (e.g., acyclic bundles in a network). For identical additive valuations it proves EF1 partitions exist when the number of agents is at least the arboricity; for arbitrary additive valuations it claims that epistemic EF1 partitions always exist via a general theorem on abstract independence structures, proves an EF1 bipartition result for Hamiltonian matroids partitionable into two independent sets, and supplies two explicit algorithms together with illustrative examples.

Significance. If the central existence claims hold, the work supplies a general existence theorem for a relaxed fairness notion in constrained fair-division settings and connects it to matroid partition questions, which is of interest to algorithmic game theory and combinatorial optimization. The provision of explicit algorithms is a positive feature.

major comments (2)
  1. [Abstract / main general theorem] Abstract and the statement of the main general theorem (presumably §3 or §4): the claim that epistemic EF1 partitions 'always exist' for arbitrary additive valuations is not qualified by the requirement that the ground set admit a partition into n independent sets. In the motivating network example, when n is strictly less than the arboricity no such partition of the remaining goods exists, so the epistemic condition cannot hold; the downward-closed property alone does not guarantee n-partitionability. This hypothesis must be stated explicitly or the 'always' quantifier restricted, as it is load-bearing for the central claim.
  2. [Matroid section] The matroid result (the Hamiltonian-matroid EF1 bipartition theorem): the statement assumes the matroid is partitionable into two independent sets, yet the surrounding discussion of conjectures does not clarify how this assumption interacts with the general independence-structure theorem or whether it can be relaxed.
minor comments (2)
  1. [Preliminaries] The definition of 'epistemic EF1' is introduced only informally in the abstract; a formal definition with precise quantifiers should appear in the preliminaries.
  2. [Throughout] Notation for the independence structure (e.g., the family Σ) and the valuation functions should be introduced once and used consistently; several passages repeat the downward-closed property without cross-reference.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and valuable comments. We agree that the hypotheses in the main results require explicit statement and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract / main general theorem] Abstract and the statement of the main general theorem (presumably §3 or §4): the claim that epistemic EF1 partitions 'always exist' for arbitrary additive valuations is not qualified by the requirement that the ground set admit a partition into n independent sets. In the motivating network example, when n is strictly less than the arboricity no such partition of the remaining goods exists, so the epistemic condition cannot hold; the downward-closed property alone does not guarantee n-partitionability. This hypothesis must be stated explicitly or the 'always' quantifier restricted, as it is load-bearing for the central claim.

    Authors: We agree. The definition of an epistemic EF1 partition requires the existence of a feasible partition of the remaining goods into n-1 independent sets (so that the envy comparison is well-defined). The general theorem on abstract independence structures therefore assumes n-partitionability of the ground set. This assumption is implicit in the motivating examples and in the epistemic definition but is not stated explicitly in the abstract or theorem statement. We will revise both to include the explicit hypothesis that the independence structure admits a partition into n independent sets, thereby restricting the 'always' quantifier appropriately. revision: yes

  2. Referee: [Matroid section] The matroid result (the Hamiltonian-matroid EF1 bipartition theorem): the statement assumes the matroid is partitionable into two independent sets, yet the surrounding discussion of conjectures does not clarify how this assumption interacts with the general independence-structure theorem or whether it can be relaxed.

    Authors: The general independence-structure theorem yields epistemic EF1 precisely when the structure is n-partitionable. The Hamiltonian-matroid result is a strengthening that obtains (non-epistemic) EF1 for n=2 under the additional Hamiltonian assumption; the two-independent-set partitionability hypothesis is required for the same reason as in the general case. We will insert a short clarifying paragraph relating the two results and noting that relaxing partitionability would necessitate a different fairness concept outside the present scope. revision: partial

Circularity Check

0 steps flagged

No circularity; existence result derived independently from general theorem.

full rationale

The paper claims an existence result for epistemic EF1 partitions derived from a general theorem on downward-closed independence structures. No self-citations, fitted parameters renamed as predictions, self-definitional steps, or reductions by construction appear in the provided abstract or claims. The derivation is presented as a mathematical proof on abstract structures, with the network and matroid cases as applications rather than inputs that force the result. This is a standard non-circular theoretical paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, invented entities, or non-standard axioms are identifiable from the abstract; the result rests on the standard definition of independence structures and additive valuations.

pith-pipeline@v0.9.1-grok · 5861 in / 976 out tokens · 11530 ms · 2026-06-27T11:59:56.632841+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

30 extracted references · 1 linked inside Pith

  1. [1]

    R. K. Ahuja, T. L. Magnanti, and J. B. Orlin.Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993

    1993

  2. [2]

    Akrami, A

    H. Akrami, A. Mayorov, K. Mehlhorn, S. Srinivas, and C. Weidenbach. A counterexample to efx;𝑛≥3 agents,𝑚≥𝑛+ 5items, monotone valuations; via sat-solving.arXiv preprint arXiv:2604.18216, 2026. Version v2, April 2026

    Pith/arXiv arXiv 2026

  3. [3]

    Akrami, R

    H. Akrami, R. Raj, and L. A. Végh. Matroids are equitable. InProceedings of the 2026 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 5843–5860. SIAM, 2026

    2026

  4. [4]

    Akrami and N

    H. Akrami and N. Rathi. Epistemic efx allocations exist for monotone valuations.Proceedings of the AAAI Conference on Artificial Intelligence, 39(13):13289–13297, 2025

    2025

  5. [5]

    Aleksandrov, H

    M. Aleksandrov, H. Aziz, S. Gaspers, and T. Walsh. Online fair division: Analysing a food bank problem. InIJCAI International Joint Conference on Artificial Intelligence, volume 2015-January, page 2540 – 2546, 2015. Cited by: 92

    2015

  6. [6]

    Amanatidis, H

    G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: Recent progress and open questions.Artificial Intelligence, 322:103965, 2023. 22 MARCIN ANHOLCER, MACIEJ BARTKOWIAK, BARTŁOMIEJ BOSEK, AND JAROSŁA W GRYTCZUK

    2023

  7. [7]

    H. Aziz, S. Bouveret, I. Caragiannis, I. Giagkousi, and J. Lang. Knowledge, fairness, and social con- straints.Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), 2018

    2018

  8. [8]

    X. Bei, A. Igarashi, X. Lu, and W. Suksompong. The price of connectivity in fair division.SIAM Journal on Discrete Mathematics, 36(2):1156–1186, 2022

    2022

  9. [9]

    V. Bilò, I. Caragiannis, M. Flammini, A. Igarashi, G. Monaco, D. Peters, C. Vinci, and W. S. Zwicker. Almostenvy-freeallocationswithconnectedbundles.Games and Economic Behavior, 131:197–221, 2022

    2022

  10. [10]

    Biswas and S

    A. Biswas and S. Barman. Fair division under cardinality constraints.Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pages 91–97, 2018

    2018

  11. [11]

    Biswas, Y

    A. Biswas, Y. Ke, S. Khuller, and Q. C. Liu. Fair allocation of conflicting courses under additive utilities. InProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, volume 2024-May, page 2162 – 2164, 2024. Cited by: 1

    2024

  12. [12]

    S. J. Brams, D. M. Kilgour, and C. Klamler. How to divide things fairly.Mathematics Magazine, 88(5):338–348, 2015

    2015

  13. [13]

    S. J. Brams and A. D. Taylor.Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, New York, 1996

    1996

  14. [14]

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

    2011

  15. [15]

    Caragiannis, J

    I. Caragiannis, J. Garg, N. Rathi, E. Sharma, and G. Varricchio. New fairness concepts for allocat- ing indivisible items. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 2554–2562, 2023

    2023

  16. [16]

    Caragiannis, D

    I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unreasonable fairness of maximum nash welfare.ACM Transactions on Economics and Computation, 7(3), 2019

    2019

  17. [17]

    Christodoulou, A

    G. Christodoulou, A. Fiat, E. Koutsoupias, and A. Sgouritsa. Fair allocation in graphs. InProceedings of the 24th ACM Conference on Economics and Computation, pages 473–488, 2023

    2023

  18. [18]

    Cookson, S

    B. Cookson, S. Ebadian, and N. Shah. Constrained fair and efficient allocations.Proceedings of the AAAI Conference on Artificial Intelligence, 39(13):13383–13391, 2025

    2025

  19. [19]

    A. Dror, M. Feldman, and E. Segal-Halevi. On fair division under heterogeneous matroid constraints. Journal of Artificial Intelligence Research, 76:567–611, 2023

    2023

  20. [20]

    Gupta, S

    A. Gupta, S. J. Nagori, A. Chakraborty, R. Vaish, S. Ranu, P. P. Nadkarni, N. V. Dasararaju, and M. Chelliah. Towards fair allocation in social commerce platforms. InACM Web Conference 2023 - Proceedings of the World Wide Web Conference, WWW 2023, page 3744 – 3754, 2023. Cited by: 6; All Open Access, Green Open Access

    2023

  21. [21]

    Kajitani, S

    Y. Kajitani, S. Ueno, and H. Miyano. Ordering of the elements of a matroid such that its consecutive w elements are independent.Discrete Mathematics, 72(1–3):187–194, 1988

    1988

  22. [22]

    R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. InProceedings of the 5th ACM Conference on Electronic Commerce, pages 125–131, 2004

    2004

  23. [23]

    Moulin.Fair Division and Collective Welfare

    H. Moulin.Fair Division and Collective Welfare. MIT Press, Cambridge, MA, 2003

    2003

  24. [24]

    Plaut and T

    B. Plaut and T. Roughgarden. Almost envy-freeness with general valuations.SIAM Journal on Discrete Mathematics, 34(2):1039–1068, 2020

    2020

  25. [25]

    A. D. Procaccia. Technical perspective: An answer to fair division’s most enigmatic question.Commu- nications of the ACM, 63(4):118, 2020

    2020

  26. [26]

    Steinhaus

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

    1948

  27. [27]

    Suksompong

    W. Suksompong. Constraints in fair division.ACM SIGecom Exchanges, 19(2):46–61, 2021

    2021

  28. [28]

    van den Heuvel and S

    J. van den Heuvel and S. Thomassé. Cyclic orderings and cyclic arboricity of matroids.Journal of Combinatorial Theory Series B, 102(3):638–646, 2012. EPISTEMIC F AIR DIVISION OF INDEPENDENCE STRUCTURES 23

    2012

  29. [29]

    Y. Wang, X. Chen, and Q. Nong. The fairness of maximum nash social welfare under matroid constraints and beyond, 2024

    2024

  30. [30]

    J. A. Zeng and R. Mehta. On the structure of efx orientations on graphs. InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 2309–2316, 2025. Institute of Informatics and Quantitative Economics, Poznań University of Economics and Business, Poznań, Poland Email address:marcin.anholcer@ue.poznan.pl Doctoral ...

    2025