Research map / Learning theory and algorithms / Submodular and game algorithms
Temporal Fair Division
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 temporal fair division (goods arriving over days, with full knowledge upfront) and charts which combinations of per-day and up-to-each-day/overall fairness (EF1, SD-EF1, PROP1) can be guaranteed or are impossible across general, two-agent, identical-ordering, and identical-day settings.
Problem
Fair division of goods arriving over multiple days when agents' valuations over all goods are known upfront; asks how fair allocations can be simultaneously per day and over time (overall or up to each day).
Approach
Model temporal fairness at three scales (per day, overall, up to each day), reduce identical-ordering instances to cardinality-constrained EF1 via an identical-ordering transformation with a PROP1 analysis, and use an envy-balancing lemma that alternates two cancelling per-day allocations to get EF1 up to each day for two agents.
Key results
- Polynomial-time algorithm gives SD-EF1 per day and PROP1 overall for general additive preferences.
- For two agents, SD-EF1 per day and EF1 up to each day is achievable via envy balancing; SD-EF1 up to each day is impossible.
- With identical orderings, SD-EF1 per day and SD-EF1 overall is achievable; with identical days, SD-PROP1 overall is achievable with SD-EF1 per day.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the temporal fair-division algorithm for arbitrary preferences | Temporal fair division · General setting | fairness guarantee | Helped |
| restrict the instance to two agents | Temporal fair division · Two agents | fairness guarantee | Helped |
| require SD-EF1 up to each day for two agents | Temporal fair division · Two agents | feasibility | Hurt |
| require EF1 per day alongside SD-EF1 overall for two agents | Temporal fair division · Two agents | feasibility | Hurt |
| add the identical-days restriction | Temporal fair division · Two agents | fairness guarantee | Helped |
| require identical preferences | Temporal fair division · Identical preferences | fairness guarantee | Helped |
| add both identical-days and identical-preferences restrictions | Temporal fair division · Identical days and identical preferences | feasibility | Hurt |
| add the identical-days restriction | Temporal fair division · Identical days | overall fairness guarantee | Helped |
| use envy balancing to select between cancelling daily allocations | Two-agent temporal fair division · Up to each day | fairness guarantee | Helped |
| use cancelling EFX allocations for each day | Two-agent temporal fair division · Per day and up to each day | fairness guarantee | Helped |
| use cancelling EF1+PO allocations for each day | Two-agent temporal fair division · Per day and up to each day | fairness guarantee | Helped |
Surprising findings
- SD-EF1 up to each day is impossible even for two agents, and EF1 per day with SD-EF1 overall is impossible for two agents.
- EF1 per day together with up-to-each-day EF1 and PO is impossible for two agents (reported by concurrent work).
Limitations
- Some stronger per-day guarantees (EFX, EF1+PO) with EF1 up to each day rely on non-polynomial partition constructions
- Results are theoretical with no empirical evaluation
- Several combinations remain open (e.g., identical orderings with up-to-each-day EF1)
Experimental setup
Metrics: envy-freeness proportionality
Builds on: EF1 with cardinality constraints (Barman, Biswas, Krishnamurthy, Narahari) informed online fair division repeated fair division bihierarchy framework
Closest papers by meaning
- Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.90)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.89)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.89)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.89)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.88)
- Reachability of Fair Allocations via Sequential Exchanges (AAAI 2024 · similarity 0.88)
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.