Research map / Learning theory and algorithms / Submodular and game algorithms
Towards Optimal Subsidy Bounds for Envy-Freeable 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.
Improves subsidy bounds for making fair allocations envy-free with subsidies: from an EF1 allocation, an envy-free allocation with per-agent subsidy at most n-1 and total at most n(n-1)/2 is computed in polynomial time, and for monotone valuations with n≥3 the bounds are tightened to n-1.5 and (n²-n-1)/2.
Problem
Minimizing the maximum and total monetary subsidies needed to make an indivisible-item allocation envy-free, under bounded marginal valuations (absolute marginal values at most 1), including non-monotone valuations.
Approach
Show that the minimum envy-eliminating subsidy vector is bounded by longest paths in an envy graph whose edge weights are at most 1 for EF1 allocations, yielding r-th largest subsidy at most n-r; for monotone valuations, a modification of the EF1 allocation (moving an item and permuting bundles via matching) reduces the bound to n-1.5 and a total of (n²-n-1)/2.
Key results
- Given an EF1 allocation, an envy-free allocation with subsidy at most n-1 per agent and total at most n(n-1)/2 is computable in polynomial time.
- For monotone valuations with n≥3, the bounds improve to n-1.5 per agent and (n²-n-1)/2 in total.
- The n-1 per-agent and n(n-1)/2 total bounds are tight for arbitrary EF1 allocations, as shown by an example.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed EF1-to-envy-free construction instead of the prior subsidy bound | EF1 allocations with doubly monotone valuations or two agents · EF1 allocations; doubly monotone valuations or n=2 | maximum subsidy per agent: 2(n-1) -> n-1 | Helped |
| Use the proposed EF1-to-envy-free construction instead of the prior subsidy bound | EF1 allocations with doubly monotone valuations or two agents · EF1 allocations; doubly monotone valuations or n=2 | total subsidy: 2(n-1)^2 -> n(n-1)/2 | Helped |
| Modify the EF1 allocation's bundles before computing subsidies | EF1 allocations with monotone valuations, n>=3 · EF1 allocations; monotone valuations, n>=3 | maximum subsidy per agent: n-1 -> n-1.5 | Helped |
| Modify the EF1 allocation's bundles before computing subsidies | EF1 allocations with monotone valuations, n>=3 · EF1 allocations; monotone valuations, n>=3 | total subsidy: n(n-1)/2 -> (n^2-n-1)/2 | Helped |
| Convert an EFk allocation to an envy-free allocation with subsidies | General valuations · EFk allocations; general valuations | maximum subsidy per agent: k(n-1) | Helped |
| Convert an EFk allocation to an envy-free allocation with subsidies | General valuations · EFk allocations; general valuations | total subsidy: k·n(n-1)/2 | Helped |
Surprising findings
- The per-agent and total subsidy bounds for arbitrary EF1 allocations cannot be improved, so improvement for monotone valuations requires modifying the allocation.
Limitations
- For n=2 the tight bound is only shown for the existence of a subsidy of 1; general EF1 existence beyond doubly monotone valuations or n=2 is not covered.
- Monotone improvement applies only for n≥3 and relies on a modification argument specific to monotone valuations.
Experimental setup
Metrics: maximum subsidy per agent total subsidy
Baselines: Brustle et al. bounds 2(n-1) and 2(n-1)^2
Builds on: envy-cycles algorithm Brustle et al. subsidy bounds for monotone valuations Halpern and Shah characterization of envy-freeable allocations
Closest papers by meaning
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.92)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.92)
- Weighted Envy-Freeness for Submodular Valuations (AAAI 2024 · similarity 0.91)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.90)
- Envy-Free House Allocation under Uncertain Preferences (AAAI 2024 · similarity 0.90)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · 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.