Research map / Multi-agent systems and games / Games and equilibria
Partitioning Friends Fairly
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 |
|---|---|---|---|
| Choose a minimum-cut balanced 2-partition | Balanced partitioning on an undirected social graph · General graphs, k=2 | (α, β)-core guarantee: (2, 0) | Helped |
| Use local min-cut search instead of requiring an exact minimum cut | Balanced partitioning on an undirected social graph · General graphs, k=2 | (α, β)-core guarantee: (3, 1) | Helped |
| Choose a minimum-cut balanced k-partition | Balanced partitioning on an undirected social graph · n ≥ k² + k | (α, β)-core guarantee: (2k − 1, 0) | Helped |
| Use local min-cut search | Balanced partitioning on an undirected social graph · n ≥ k² + k | (α, β)-core guarantee: (2k − 1, 0) | Helped |
| Use a discrepancy-based coloring that balances neighborhoods and group sizes | Balanced partitioning on an undirected social graph · General graphs, k≥2 | EF-r: EF-O(√(n/k · ln k)) | Helped |
| Construct an imbalanced k-partition | Imbalanced partitioning on an undirected social graph · General graphs, k≥2 | (1, β)-imbalanced core guarantee: (1, k − 2) | Helped |
| Use degree-based thresholds to construct an imbalanced 2-partition | Imbalanced partitioning on an undirected social graph · General graphs, k=2 | EF-r: EF-2 | Helped |
| Require a purely multiplicative core approximation for k≥3 | Balanced partitioning on an undirected social graph · Some graphs, k≥3 | (α, 0)-core guarantee: for any α ≥ 1 | Hurt |
| Require EF1 for balanced groups | Balanced partitioning on an undirected social graph · Some graphs, k=2 | EF-r: EF1 | Hurt |
Closest papers by meaning
- Balanced and Fair Partitioning of Friends (AAAI 2025 · similarity 0.92)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.89)
- Maxileximin Envy Allocations and Connected Goods (AAAI 2024 · similarity 0.87)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.87)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.87)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.86)
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.