Research map / Learning theory and algorithms / Submodular and game algorithms
Fair Allocation of Items in Multiple Regions
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.
Initiates fair allocation of divisible or indivisible items spread across multiple regions where each agent may only receive items from one region, giving hardness results, inapproximability, and algorithms for EF/EF1/EFX/PROP variants.
Problem
Fair allocation of items distributed across multiple regions, where each agent can obtain items from only one region; studies envy-based (EF, EF1, EFX) and share-based (PROP, PROP1, PROPX) fairness under divisible and indivisible items.
Approach
Integrates region assignment with item allocation: agents must choose one region, so existence and approximation of fair allocations are studied jointly. Proposes algorithms (About-To-Envy-Satisfied, Sequential Envy-Satisfied, Sequential Envy-Graph-Satisfied, Adapted Perfect Partition, Adapted Round-Robin) that output partial allocations with bounded charity or approximate fairness.
Key results
- Deciding whether an EF (divisible) or EF1/EFX (indivisible) allocation exists in the diverse-region setting is NP-complete.
- Under piecewise constant valuations, the About-To-Envy-Satisfied Algorithm computes an EF-with-bounded-charity allocation in polynomial time; in the equal-region setting, a 1/2-EF allocation is achieved and 1/2 is shown tight for EF and PROP.
- The Sequential Envy-Graph-Satisfied Algorithm computes an EF1-with-bounded-charity allocation in polynomial time, and the Adapted Round-Robin Algorithm computes a 1/2-PROP1 allocation in polynomial time in the equal-region setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| allow bounded charity | About-To-Envy-Satisfied Algorithm · Divisible items, diverse-region | EF | Helped |
| use the Adapted Perfect Partition Algorithm | Divisible items, equal-region · Divisible items, equal-region | EF approximation ratio: 1/2-EF | Helped |
| allow partial allocation with bounded charity | Divisible-item allocations · Divisible items, diverse-region | EF | Helped |
| allocate unallocated divisible parts to agents in their respective regions | About-To-Envy-Satisfied Algorithm · Divisible items, equal-region | EF approximation ratio: 1/2-EF | Helped |
| allow bounded charity | Sequential Envy-Satisfied Algorithm · Indivisible items, diverse-region | EFX | Helped |
| allow bounded charity | Sequential Envy-Graph-Satisfied Algorithm · Indivisible items, diverse-region | EF1 | Helped |
| allow partial allocation with bounded charity | Indivisible-item allocations · Indivisible items, diverse-region | EF1, EFX, PROP1, and PROPX | Helped |
| allocate unallocated items to agents in their respective regions | Sequential Envy-Satisfied Algorithm or Sequential Envy-Graph-Satisfied Algorithm · Indivisible items, equal-region | EF1 approximation ratio: 1/2-EF1 | Helped |
| use the Adapted Round-Robin Algorithm | Indivisible-item allocations · Indivisible items, equal-region | PROP1 approximation ratio: 1/2-PROP1 | Helped |
| require EFX or PROPX in the equal-region setting | Indivisible-item allocations · Indivisible items, equal-region | EFX and PROPX approximation | Hurt |
Surprising findings
- EF and PROP allocations may not exist at all in the diverse-region divisible setting, and no bounded approximation is possible.
Limitations
- Mixed divisible and indivisible items per region are left to future work
- EFX existence with bounded charity is only pseudo-polynomial; polynomial algorithm is open
- Several guarantees hold only under piecewise constant valuations or with partial (charity) allocations
Experimental setup
Metrics: approximation ratio
Builds on: Envy-Cycles Procedure Round-Robin algorithm perfect partition EFX-with-charity (Chaudhury et al. 2021)
Closest papers by meaning
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.92)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.91)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.90)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.90)
- Reachability of Fair Allocations via Sequential Exchanges (AAAI 2024 · similarity 0.90)
- Constrained Fair and Efficient Allocations (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.