Research map / Learning theory and algorithms / Submodular and game algorithms
Weighted Envy-Freeness for Submodular Valuations
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.
Proposes two weighted envy-freeness families (TWEF and WMEF) for submodular valuations, shows picking sequences, max weighted Nash welfare, a transfer algorithm, and max weighted harmonic welfare satisfy them under matroid-rank or general submodular valuations.
Problem
Fair allocation of indivisible goods to weighted agents with non-additive (submodular, especially matroid-rank) valuations, where existing weighted envy-based notions such as WEF1 admit no complete allocation.
Approach
Two new envy notions: TWEF(x,y) excuses envy when the agent's own value cannot increase even if the other's bundle is transferred to her; WMEF(x,y) replaces the value of the other's bundle with the marginal value of the bundle added to her own. Also introduces harmonic-number welfare (MWHW_x) whose maximizers satisfy TWEF for matroid-rank valuations.
Key results
- Picking sequences with highest-marginal-gain picks satisfy WMEF(x,1-x) for submodular valuations; round-robin yields complete MEF1 allocations in the unweighted submodular case.
- MWNW allocations satisfy WWMEF1 and Pareto optimality under submodular valuations.
- A clean MWHW_x allocation satisfies TWEF(x,1-x) for matroid-rank valuations, and the transfer algorithm returns a clean TWEF(x,1-x) allocation maximizing utilitarian welfare in polynomial time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a picking sequence that assigns turns by the weighted ratio and has agents pick the highest-marginal-gain good | Picking sequences · Submodular valuations | WMEF(x,1-x) guarantee | Helped |
| Use highest-marginal-gain picks in round-robin | Round-robin · Unweighted submodular valuations | MEF1 guarantee | Helped |
| Maximize weighted Nash welfare | MWNW · Submodular valuations | WWMEF1 guarantee | Helped |
| Use the weighted transfer algorithm with parameter x | Transfer algorithm · Matroid-rank valuations | TWEF(x,1-x) guarantee | Helped |
| Maximize modified weighted harmonic welfare and require a clean allocation | MWHW_x · Matroid-rank valuations | TWEF(x,1-x) guarantee | Helped |
| Replace MWNW with clean MWHW_x | Weighted welfare rules · Matroid-rank valuations | TWEF(x,1-x) guarantee | Helped |
| Remove the cleanness requirement from MWHW_x (ablation) | MWHW_x · Matroid-rank valuations | TWEF(x,1-x) guarantee | Hurt |
| Use maximum harmonic welfare with integer-valued additive valuations | MHW · Equal-weight additive valuations with integer good values | EF1 guarantee | Helped |
| Extend harmonic numbers to real-valued utilities | MHW with extended harmonic numbers · Equal-weight additive valuations | EF1 guarantee | Hurt |
| Try to strengthen the round-robin MEF1 guarantee to EF1 | Round-robin · Matroid-rank valuations | EF1 guarantee | Hurt |
Surprising findings
- Under matroid-rank valuations, MWNW does not imply WEF(x,1-x) for any x, whereas maximum weighted harmonic welfare does satisfy TWEF.
- In the unweighted submodular setting, round-robin with marginal-gain picks gives MEF1 but not EF1, even with matroid-rank valuations.
Limitations
- TWEF can be too demanding for general submodular valuations, where a complete allocation may not exist.
- Potential-function argument for the transfer algorithm does not directly give polynomial bounds with unequal weights, requiring a refined argument.
- Harmonic welfare is not scale-invariant and is only well-defined for integer utilities in the additive case.
Experimental setup
Baselines: WEF(x,1-x) WEF1 WWEF1 MWNW round-robin
Builds on: WEF(x,1-x) MEF1 round-robin algorithm maximum Nash welfare transfer algorithm
Closest papers by meaning
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.91)
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (AAAI 2024 · similarity 0.91)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.91)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.90)
- Fair Division with Market Values (AAAI 2025 · similarity 0.89)
- Fair and Efficient Completion of Indivisible Goods (AAAI 2025 · similarity 0.89)
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.