Research map / Graph learning / Graph algorithms and clustering
The Price of Connectivity in Fair Division
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 |
|---|---|---|---|
| Require connected bundles on a graph with vertex connectivity 1 | Two-agent MMS allocation · Graphs with vertex connectivity 1 | PoC: PoC(G,2) = k; k is at least 2 | Hurt |
| Use a biconnected graph rather than a graph with a cut vertex | Two-agent MMS allocation · Biconnected graphs | PoC: ≤ 4/3; vertex connectivity 1 has PoC at least 2 | Helped |
| Require connected bundles on a graph that is not (2,k)-linked | Two-agent MMS allocation · Graphs that are not (2,k)-linked | PoC: ≥ 2k/(2k-1) | Hurt |
| Remove a nonempty matching from a complete graph, excluding L5 | Two-agent MMS allocation · Complete graphs with a nonempty matching removed | PoC: (2m-4)/(2m-5) | Hurt |
| Require connected bundles on an arbitrary graph | MMS allocation for n agents · Any graph, m ≥ n | MMS fraction guaranteed: 1/(m-n+1) | Hurt |
| Use a star graph with connected bundles | MMS allocation for n agents · Star, m ≥ n | PoC: m-n+1 | Hurt |
| Use a path graph with connected bundles | MMS allocation for n agents · Path, m ≥ 2n-1 | PoC: n | Hurt |
| Use a path graph with connected bundles | MMS allocation for n agents · Path, n ≤ m < 2n-1 | PoC: m-n+1 | Hurt |
| Use indivisible proportional share (IPS) for connected allocation on a path | MMS allocation for n agents · Path | MMS fraction guaranteed: IPS(n,m) = 1/n if m ≥ 2n-1; 1/(m-n+1) if n ≤ m < 2n-1 | Helped |
| Require connected bundles on a non-complete graph | Two-agent EFX allocation · Any non-complete graph | EFX existence | Hurt |
| Use a tree other than a path or a star with three edges | Three-agent EF1 allocation · Trees | EF1 existence | Hurt |
| Allocate the two sides of a complete bipartite graph in opposite round-robin orders | Additive allocation for n agents · Complete bipartite graph K_{a,b}, a,b ≥ n | EF relaxation | Helped |
Closest papers by meaning
- The Complexity of Computing Maximin Share Allocations on Graphs (AAAI 2020 · similarity 0.93)
- Maxileximin Envy Allocations and Connected Goods (AAAI 2024 · similarity 0.90)
- The Price of Opportunity Fairness in Matroid Allocation Problems (NeurIPS 2025 · similarity 0.88)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.87)
- Reachability of Fair Allocations via Sequential Exchanges (AAAI 2024 · similarity 0.87)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.87)
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.