Research map / Learning theory and algorithms / Submodular and game algorithms
Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict the item graph to a path or star, with additive valuations | Finding a Pareto-optimal connected allocation · Connected allocation | computational complexity | Helped |
| Allow tree item graphs, even with binary additive valuations | Finding a Pareto-optimal connected allocation · Connected allocation on trees | computational complexity | Hurt |
| Require Pareto-optimality together with MMS | Finding an allocation on a path · Path; binary additive valuations | computational complexity | Hurt |
| Require Pareto-optimality together with EF1 | Finding an allocation on a path · Path; binary additive valuations | computational complexity | Hurt |
| Require EF1 alongside Pareto-optimality | Connected allocation on a path · Path; binary additive valuations | existence | Hurt |
| Restrict valuations to binary additive approvals on non-nested intervals | Finding an MMS connected allocation that maximizes utilitarian welfare · Path | computational complexity | Helped |
| Use 2-additive valuations instead of additive valuations | Finding a Pareto-optimal connected allocation · Path or star | computational complexity | Hurt |
| Use identical additive valuations | Finding a connected allocation satisfying both EF1 and Pareto-optimality · Path | existence and computational complexity | Helped |
| Allow identical but non-additive subadditive valuations | Finding a connected allocation satisfying both EF1 and Pareto-optimality · Path | existence | Hurt |
| Allow nested approval intervals in the moving-knife setting | The proposed moving-knife algorithm · Path; binary additive valuations | Pareto-optimality and MMS | Hurt |
Closest papers by meaning
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.91)
- Maxileximin Envy Allocations and Connected Goods (AAAI 2024 · similarity 0.90)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.90)
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (AAAI 2024 · similarity 0.90)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.90)
- Fair and Efficient Completion of Indivisible Goods (AAAI 2025 · similarity 0.89)
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.