Research map / Learning theory and algorithms / Submodular and game algorithms
Reachability of Fair Allocations via Sequential Exchanges
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.
Studies whether EF1 allocations are reachable from one another via single good exchanges while keeping every intermediate allocation EF1, giving positive results for identical/binary utilities and hardness results otherwise.
Problem
Reachability of EF1 allocations through sequences of pairwise good exchanges where all intermediate allocations must also be EF1; also whether optimal (shortest) such exchange paths exist.
Approach
Introduces the EF1 exchange graph (subgraph of allocation exchange graph induced by EF1 allocations) and analyzes its connectivity and optimality of paths across utility classes; shows distance between allocations equals m minus max cycle partition in an item graph, and reduces hardness from directed triangle partition, perfect matching reconfiguration, and partition.
Key results
- Two agents: EF1 exchange graph can be disconnected and optimal EF1 exchange paths may not exist in general; both are guaranteed for identical or binary utilities with polynomial-time paths.
- Deciding existence of an EF1 exchange path between two EF1 allocations is PSPACE-complete for general utilities with three or more agents.
- Finding the distance between two allocations (even ignoring EF1) is NP-hard; deciding existence of an optimal EF1 exchange path is NP-hard even for four agents with identical utilities.
- For identical binary utilities with any number of agents, the EF1 exchange graph is connected and paths are computable in polynomial time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict utilities to identical utilities for 2 agents | EF1 exchange reachability · EF1 exchange graph, 2 agents | connectivity | Helped |
| Restrict utilities to binary utilities for 2 agents | EF1 exchange reachability · EF1 exchange graph, 2 agents | connectivity | Helped |
| Restrict utilities to identical utilities for 2 agents | Optimal EF1 exchange path · EF1 exchange graph, 2 agents | optimal EF1 path existence | Helped |
| Restrict utilities to binary utilities for 2 agents | Optimal EF1 exchange path · EF1 exchange graph, 2 agents | optimal EF1 path existence | Helped |
| Increase the number of agents to 3 or more while allowing general utilities | EF1 exchange reachability · EF1 exchange graph, 3 or more agents | connectivity | Hurt |
| Require utilities to be both identical and binary | EF1 exchange reachability · EF1 exchange graph, 3 or more agents | connectivity | Helped |
| Use identical utilities alone rather than identical binary utilities for 3 or more agents | EF1 exchange reachability · EF1 exchange graph, 3 or more agents | connectivity | Hurt |
| Use binary utilities alone rather than identical binary utilities for 3 or more agents | EF1 exchange reachability · EF1 exchange graph, 3 or more agents | connectivity | Hurt |
| Increase the number of agents to 3 or more under identical binary utilities | Optimal EF1 exchange path · EF1 exchange graph, 3 or more agents | optimal EF1 path existence | Hurt |
| Allow transfers in addition to exchanges for 2 agents with identical utilities | EF1 exchange-and-transfer reachability · EF1 exchange-and-transfer graph, 2 agents | connectivity | Helped |
| Allow transfers in addition to exchanges for 2 agents with binary utilities | EF1 exchange-and-transfer reachability · EF1 exchange-and-transfer graph, 2 agents | connectivity | Helped |
| Allow transfers in addition to exchanges for any number of agents with identical binary utilities | EF1 exchange-and-transfer reachability · EF1 exchange-and-transfer graph, 2 or more agents | connectivity | Helped |
Surprising findings
- Even with two agents, two EF1 allocations may be unreachable from each other via EF1 exchanges.
- Optimal EF1 exchange paths may fail to exist even under identical binary utilities with three or more agents.
Limitations
- Negative results for general utilities and three or more agents show limited tractability.
- Analysis is restricted to exchange operations and additive utilities; transfers only treated in appendix.
Experimental setup
Builds on: envy-freeness up to one good perfect matching reconfiguration directed triangle partition
Closest papers by meaning
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.92)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.91)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.91)
- Fair and Efficient Completion of Indivisible Goods (AAAI 2025 · similarity 0.91)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.90)
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (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.