Research map / Learning theory and algorithms / Submodular and game algorithms
Constrained Fair and Efficient Allocations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows maximum Nash welfare allocations are 1/2-EF1 and PO under matroid, base-orderable complete, partition-with-lower-bounds and goods-with-copies constraints, and gives best-of-both-worlds results for goods with copies and balancedness.
Problem
Existence of fair and efficient (EF1 and Pareto optimal) allocations of indivisible goods with additive valuations under feasibility constraints such as matroids, cardinality/partition constraints, goods with copies, and balancedness.
Approach
Reduce constrained additive instances to unconstrained submodular instances via weighted matroid rank functions to inherit MEF1 of MNW; for non-matroidal constraints, a novel "alternate worlds" lemma combines MNW guarantees across a union of feasible sets, and partition matroids with lower bounds are decomposed into unions of partition matroids for complete allocations.
Key results
- MNW allocations under any matroid constraint are 1/2-EF1 and PO; complete MNW allocations are 1/2-EF1 and PO for base-orderable matroids.
- MNW allocations for goods with copies are 1/2-EF1_WC and PO, a strengthening of EF1 that is the first known approximation of EF1_WC under general additive preferences.
- For any epsilon>0 there are balancedness/partition instances where no MNW allocation is (1/2+epsilon)-EF1, showing tightness of the 1/2 factor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MNW under arbitrary matroid feasibility constraints | Additive-valuation allocation · Arbitrary matroid constraints | EF1 guarantee: \sfrac{1}{2}-EF1 | Helped |
| Use complete MNW under base-orderable matroid constraints | Additive-valuation allocation · Base-orderable matroid constraints | EF1 guarantee: \sfrac{1}{2}-EF1 | Helped |
| Use MNW under partition matroid constraints with lower bounds | Additive-valuation allocation · Partition matroid constraints with lower bounds | EF1 guarantee: \sfrac{1}{2}-EF1 | Helped |
| Use MNW under goods-with-copies constraints | Additive-valuation allocation · Goods with copies | EF1 without commons guarantee: \sfrac{1}{2}-EF1\textsubscript{WC} | Helped |
| Apply the CE lottery decomposition to a CEEI allocation | Randomized allocation for goods with copies · Goods with copies; strictly positive valuations | Ex post guarantees: EF$^1_1$, Prop1, and PO | Helped |
| Add balancedness to the goods-with-copies CE lottery setting | Randomized allocation for goods with copies · Goods with copies with balancedness; strictly positive valuations | Ex post guarantees: Prop1 and PO; EF$^1_1$ guarantee does not hold | Mixed |
| Require an EF1 guarantee stronger than the proven half-EF1 level | MNW · Partition matroid constraints and balancedness | EF1 guarantee: no MNW (or complete MNW) allocation is $(\sfrac{1}{2} + \epsilon)$-EF1 | Hurt |
| Require unconstrained Pareto optimality in addition to approximate EF1 | Feasible allocation · Balancedness constraint | EF1 with PO$^{+}$: impossible to guarantee $\alpha$-EF1 and PO\textsuperscript{+} for any $\alpha \in (0,1]$ | Hurt |
| Impose partition matroid feasibility while requiring SD-EF1 | Feasible allocation · Partition matroid constraints | SD-EF1 existence: SD-EF1 cannot be guaranteed | Hurt |
Surprising findings
- Under partition matroid constraints SD-EF1 cannot be guaranteed, and under balancedness EF1 with PO+ is impossible for any alpha.
- Round robin under balancedness can be Pareto inefficient.
Limitations
- Guarantees are 1/2-EF1 rather than exact EF1 with PO; exact existence remains open for general matroids.
- Complete MNW results for non-base-orderable matroids and non-matroidal constraints beyond partition with lower bounds are not established.
- Non-tight fairness: MNW cannot achieve better than 1/2-EF1 under these constraints.
Experimental setup
Metrics: EF1 approximation factor Pareto optimality
Baselines: round robin EF1 allocation under cardinality constraints
Builds on: maximum Nash welfare marginal envy-freeness up to one good bihierarchy theorem competitive equilibrium from equal incomes
Closest papers by meaning
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.92)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.91)
- Weighted Envy-Freeness for Submodular Valuations (AAAI 2024 · similarity 0.91)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.90)
- Fair and Efficient Completion of Indivisible Goods (AAAI 2025 · similarity 0.90)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.