Research map / Learning theory and algorithms / Submodular and game algorithms
Repeated Fair Allocation of Indivisible Items
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.
Introduces a model for repeated fair allocation of indivisible goods and chores and characterizes when envy-free, proportional and Pareto-optimal allocation sequences exist across fixed and variable numbers of rounds.
Problem
Fair and efficient allocation of indivisible goods and chores when the same items are allocated repeatedly over multiple rounds, evaluating fairness overall and per round.
Approach
Models repeated allocation as sequences of allocations evaluated either overall (over the union of bundles across rounds) or per round, and shows existence/non-existence results for EF, PROP, EF1, and PO depending on whether the number of rounds is a multiple of n, is fixed or variable, and whether there are two agents.
Key results
- For n agents and k a multiple of n, a proportional and Pareto-optimal sequence of allocations always exists (computable in O(n^{mk} m) time).
- For two agents and even k, an envy-free and Pareto-optimal sequence exists overall, with per-round weak EF1; for k=n=2 it also achieves per-round EF1.
- For variable number of rounds, an envy-free and Pareto-optimal sequence with per-round PROP[1,1] exists (PROP1 for only goods or only chores).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Choose the number of rounds as a multiple of the number of agents | Repeated allocation with n agents · Fixed number of rounds; k ∈ nℕ | proportionality and Pareto-optimality overall | Helped |
| Use a fixed number of rounds not divisible by the number of agents | Repeated allocation with n agents · Fixed number of rounds; k ∉ nℕ | proportionality overall | Hurt |
| Require both envy-freeness and Pareto-optimality with more than two agents | Repeated allocation with n agents · Fixed number of rounds; n > 2 | envy-freeness and Pareto-optimality overall | Hurt |
| Use an even fixed number of rounds with two agents | Repeated allocation with two agents · Fixed number of rounds; n = 2, k ∈ 2ℕ | envy-freeness and Pareto-optimality overall | Helped |
| Use two rounds with two agents | Repeated allocation with two agents · Fixed number of rounds; n = k = 2 | per-round EF1, with envy-freeness and Pareto-optimality overall | Helped |
| Relax per-round EF1 to per-round weak EF1 | Repeated allocation with two agents · Fixed even number of rounds; n = 2 | per-round fairness, with envy-freeness and Pareto-optimality overall | Helped |
| Require per-round EF1 together with overall envy-freeness and Pareto-optimality for more than two rounds | Repeated allocation with two agents · Fixed number of rounds; n = 2, k > 2 | joint fairness and efficiency guarantee | Hurt |
| Drop the Pareto-optimality requirement | Repeated allocation with two agents · Fixed even number of rounds; n = 2 | envy-freeness overall and per-round EF1 | Helped |
| Allow the number of rounds to be chosen freely | Repeated allocation with rational utilities · Variable number of rounds | envy-freeness and Pareto-optimality overall; per-round PROP[1,1] | Helped |
| Restrict items to goods only or chores only when rounds are variable | Repeated allocation with rational utilities · Variable number of rounds; goods-only or chores-only | per-round proportionality | Helped |
Surprising findings
- Envy-free and Pareto-optimal overall sequences may fail to exist for any fixed number of rounds when n>2 and items are chores.
- Applying Generalized Adjusted Winner separately in each round can yield an overall allocation that is not envy-free.
Limitations
- Existence of envy-free and Pareto-optimal sequences fails for fixed k with n>2 in general.
- Open whether EF and per-round EF1 can be achieved simultaneously for n>2 agents.
- Model is offline with static known additive utilities.
Experimental setup
Metrics: envy-freeness proportionality Pareto-optimality EF1
Baselines: Generalized Adjusted Winner (per-round application)
Builds on: Generalized Adjusted Winner PROP1 EF1 Laminar randomized rounding decomposition for divisible allocation
Closest papers by meaning
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.92)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.92)
- Fair and Efficient Allocations of Chores under Bivalued Preferences (AAAI 2022 · similarity 0.92)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.90)
- Fair and Efficient Completion of Indivisible Goods (AAAI 2025 · similarity 0.90)
- Envy-Free House Allocation under Uncertain Preferences (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.