Source-linked AI summary
Constrained Fair Allocations via Partition Matroid Reductions
Benjamin Cookson, Nisarg Shah
TL;DR
The paper asks whether complete feasible EF1 allocations always exist under matroid constraints beyond the known partition-matroid case. It develops partition matroid reductions and proves the result for three agents under laminar matroids, while extending guarantees to transversal, graphic, and gammoid matroids under varying assumptions. The four-agent laminar case is reduced to unresolved finite problems.
Problem
Whether every matroid admitting a complete feasible allocation also admits a complete feasible EF1 allocation remains open beyond partition matroids.
Method
The paper reduces complex matroids to simpler partition or finite-sized key laminar matroids, then uses EF1 constructions and existing partition-matroid algorithms.
Results
Three-agent laminar matroids always admit complete feasible EF1 allocations when complete feasibility holds; the guarantee also holds for transversal matroids, with conditional results for graphic matroids and gammoids.
Takeaways & Limitations
Partition matroid reductions establish EF1 existence for laminar matroids with three agents and for broader matroid classes under the stated feasibility or colorability conditions.
Takeaways & Limitations
The four-agent laminar base cases remain unresolved, and graphic matroids and gammoids require stronger colorability assumptions than the full conjecture.
Abstract
from arXiv · showhide
We study fair allocation of indivisible goods under additive valuations and matroid constraints. A challenging open question is whether a complete and feasible envy-free up to one good (EF1) allocation exists under every matroid that admits a complete and feasible allocation. The state-of-the-art result by Biswas and Barman [2018] positively resolves this question for partition matroids. Our first result positively resolves it for laminar matroids, which generalize partition matroids, when there are three agents. Our technique reduces this general existence question to finding an EF1 allocation satisfying a mild additional condition under a single finite-sized key laminar matroid, and we establish the required allocation by case analysis. We show that our technique somewhat extends to four agents, reducing the analogous problem to finding EF1 allocations under two finite-sized laminar matroids, although we are unable to establish their existence. We also use recent matroid decomposition results to establish EF1 existence under broader classes of matroids. Specifically, we show that EF1 allocations always exist under transversal matroids whenever a complete allocation is feasible, and obtain existence results for graphic matroids and gammoids under stronger assumptions.
1 Introduction
The paper addresses whether complete feasible EF1 allocations always exist under matroid constraints, extending known partition-matroid results to laminar matroids and broader classes. It proves the three-agent laminar case, reduces the four-agent case to unresolved finite problems, and establishes guarantees for transversal, graphic, and gammoid matroids under stated assumptions.
- Open problem: EF1 existence under matroid constraints remains unresolved despite its flexibility and prior guarantees alongside other fairness and efficiency properties.The open question asks whether every matroid admitting a complete feasible allocation also admits a complete feasible EF1 allocation.
- Approach: The paper’s common technique reduces complex matroids to simpler matroids where EF1 is known or easier to prove.The reductions can target partition matroids or finite key laminar matroids.
- Laminar matroids: Three agents under laminar constraints always admit a complete feasible EF1 allocation whenever a complete feasible allocation exists.The result also gives a polynomial-time solution by combining the key-matroid argument with the partition-matroid algorithm.
- Laminar matroids: For four agents, the technique reduces the problem to EF1 allocations with an ordered no-envy condition under two finite-sized laminar matroids, but those base cases remain unresolved.The three-agent key-matroid techniques are insufficient for n = 4.
- Broader matroid classes: EF1 exists for transversal matroids whenever a complete allocation is feasible, while graphic matroids and gammoids require stronger colorability assumptions.The required partitions have n independent sets for transversal matroids, ⌊(n + 1)/2⌋ for graphic matroids, and ⌊(n + 2)/2⌋ for gammoids.
2 Preliminaries
The preliminaries formalize additive valuations, complete and feasible allocations, matroid constraints, EF1, and the principal matroid families used throughout the paper. Feasibility of a complete allocation to n agents is equivalent to n-colorability of the matroid.
- Allocations and valuations: Each agent values a bundle additively, so the value of a set equals the sum of values of its individual goods.An allocation assigns disjoint bundles to agents, and an allocation is complete when all goods are assigned.
- Matroid constraints: A matroid-constrained allocation is feasible when every agent’s bundle is an independent set of the provided matroid.Matroids satisfy the empty-set, hereditary, and exchange properties.
- Matroid constraints: A complete feasible allocation to n agents exists if and only if the matroid is n-colorable.Here, k-colorability means partitioning the ground set into k independent sets.
- Matroid families: Uniform matroids impose cardinality limits, partition matroids impose category capacities, and laminar matroids impose capacities over nested or disjoint sets.Partition matroids are direct sums of uniform matroids, while laminar families allow richer hierarchical constraints.
- Matroid families: Transversal matroids are defined by subsets coverable through matchings, whereas gammoids are defined by vertex-disjoint paths to terminal sets; graphic matroids use forests.These families support the broader constraint classes studied later.
- Fairness: EF1 requires that, for every agent pair, removing some good from the other agent’s bundle eliminates envy, with an empty bundle treated separately.This is the fairness criterion used for all constrained allocation problems in the paper.
3 Laminar Matroids With 3 Agents
The paper reduces three-agent EF1 allocation under laminar matroids to structured finite components, then solves those components constructively in polynomial time. This yields a complete and feasible EF1 allocation whenever a complete feasible allocation exists.
- Main result: Theorem 1 establishes complete and feasible EF1 allocations for three agents with additive valuations under laminar matroid constraints whenever complete feasibility holds.The allocation can be computed in polynomial time.
- Reduction framework: Feasibility-preserving operations retain laminarity, n-colorability, and independent-set containment while simplifying the original matroid.The four-stage proof begins by packing the laminar matroid and repeatedly applying feasibility-preserving simplifications.
- Stage 3: Decomposition: After simplification, every connected component is either a uniform matroid or a six-good key matroid.This structural characterization follows when splitting, child pruning, parent pruning, and partition extraction are no longer applicable.
- Stage 4: Solving the Key Matroid: The key matroid always admits a complete feasible EF1 allocation satisfying the required ordered no-envy condition for three agents.Lemma 8 provides this allocation for any additive valuations and any agent ordering.
- Final Algorithm: The final algorithm allocates components sequentially, using round-robin for uniform components and the key-matroid subroutine for key components.Envy-cycle elimination restores the no-envy order after each component, while reversed envy orders preserve EF1 when allocations are combined.
- Final Algorithm: The algorithm allocates every good and terminates after at most O(|M|^3) simplification iterations.Key-matroid and round-robin procedures assign all goods, and envy-cycle elimination only transfers bundles between agents.
4 Matroids With More Agents
The paper reduces several matroid-constrained EF1 existence questions to partition matroids, obtaining unconditional results for transversal matroids and conditional results for graphic matroids and gammoids.
- Limits of decomposition: The decomposition cannot generally continue to uniform matroids while preserving 3-colorability and Independent Set Shrinkage for the key laminar matroid.Thus, the partition-matroid algorithm cannot simply be applied after a complete decomposition.
- Reduction framework: A partition matroid reduction preserves feasibility strongly enough that EF1 under the reduced matroid yields EF1 under the original matroid.The reduced independence family is a subset of the original one, so every feasible bundle remains feasible.
- Transversal matroids: n-colorable transversal matroids always admit complete and feasible EF1 allocations for n agents.The reduction uses k = n colors in the transversal case.
- Graphic matroids: ⌊(n + 1)/2⌋-colorable graphic matroids admit complete and feasible EF1 allocations for n agents.The graphic reduction uses k = 2n′ − 1 with n′ = ⌊(n + 1)/2⌋.
- Gammoids: ⌊(n + 2)/2⌋-colorable gammoids admit complete and feasible EF1 allocations for n agents.For n′ ≥ 2, the gammoid reduction uses k = 2n′ − 2; the one-agent case is the free matroid.
5 Discussion
The discussion identifies stronger ordered-no-envy requirements as an unresolved obstacle and describes open directions for four agents and broader matroid decompositions.
- EF1 with ordered no-envy: Ordered no-envy requires each connected component’s EF1 allocation to have a directed acyclic envy graph with a prescribed reverse topological order.This is stronger than ordinary EF1 existence under matroid constraints.
- Resolving the case of four agents: Four-agent laminar instances reduce to EF1 allocations with ordered no-envy in two finite-sized laminar matroids, but the required base cases remain unresolved.Computer-aided efforts to resolve this missing piece were unfruitful.
- Matroid decompositions: Improving the partition-decomposition bounds is not a viable strengthening route because those bounds are tight; broader feasibility-preserving operations remain a proposed direction.The discussion specifically asks whether such operations can be designed beyond laminar matroids.
A.1 Omitted Proofs from Section 3.1
For laminar matroids, n-colorability is characterized exactly by lower bounds on every laminar-set capacity, with sufficiency obtained through balanced hypergraph colorings.
- Colorability characterization: A laminar matroid is n-colorable if and only if u(S) ≥ ⌈|S|/n⌉ for every S ∈ L.The condition is necessary because partitioning S among n color classes forces one class to contain at least ⌈|S|/n⌉ elements.
- Colorability characterization: Sufficiency follows by representing the laminar family as a totally unimodular hypergraph and applying a balanced vertex-partition theorem with k = n.Each hyperedge receives at most ⌈|S|/n⌉ vertices in any color class.
B Four Agents
For four agents, the decomposition extends to two finite key laminar matroids, but the three-agent solution technique does not establish the needed allocations.
- Key matroids: The size-8 key matroid has three partition sets of sizes 3, 3, and 2, each with upper bound 1.
- Key matroids: The size-12 key matroid has four disjoint partition sets of size 3, each with upper bound 1.
- Structural cases: The reduction leaves only size-12 components with four size-3 children or size-8 components with child sizes (3, 3, 2).These are the only remaining configurations after applying the stated packing, pruning, and splitting arguments.
- Unresolved allocation problem: Solving the four-agent problem would require EF1 allocations with no ordered envy for both key matroids, but such existence is not established.For the size-8 matroid, a valid allocation can fail to place an agent’s top-ranked goods in distinct bundles.
- Unresolved allocation problem: A size-8 counterexample shows that agent 4’s and agent 3’s favorite-good constraints can make g3 impossible to place in any bundle.Agent 4’s top goods are {g1, g2, g5, g6}, while agent 3’s are {g3, g5, g6}.