Research map / Multi-agent systems and games / Games and equilibria
Balanced and Fair Partitioning of Friends
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.
Generalizes the fair partitioning of friends model to non-binary, asymmetric, non-additive-friendly utilities, studies fairness notions (EF, EFX0, EFX, EF1, PROP, MMS) with existence results and a near-complete complexity landscape.
Problem
Partitioning agents on a friendship graph into k balanced groups so that the partition is fair (no agent envies another group's members), under generalized utilities; existence and complexity of various fairness notions are unclear.
Approach
Extends the friendship-partition model beyond binary, symmetric and additive utilities, adapts fair-division fairness notions (EF, EFX0, EFX, EF1, PROP, MMS) to it, and maps their existence and computational/parameterized complexity across graph classes.
Key results
- EF1 partitions can fail to exist even for k=2 with binary utilities; MMS partitions need not exist for any k>=2 even with binary utilities.
- EF, EFX0 and PROP existence is NP-complete and W[1]-hard parameterized by k even on paths with objective utilities; EF, PROP, EFX0, EFX are NP-complete on bipartite graphs with vertex cover number 2 and k=2.
- With binary utilities, existence for every studied fairness notion is FPT parameterized by vertex cover number.
Surprising findings
- MMS partitions may not exist for any k>=2 even with binary utilities, and EF1 partitions may fail to exist even for k=2.
- Verifying MMS-share is NP-complete even for k=2 and symmetric utilities, although for binary utilities it is computable in linear time.
Limitations
- Many fairness notions are intractable even in simple graph classes such as paths or bipartite graphs with vertex cover 2.
- Positive results are restricted to tree-like graphs, constant k, or binary utilities.
Experimental setup
Builds on: fair partitioning of friends (Bullinger et al.) envy-freeness up to any good (EFX) EF1 for indivisible goods
Closest papers by meaning
- A Little Charity Guarantees Fair Connected Graph Partitioning (AAAI 2022 · similarity 0.92)
- Partitioning Friends Fairly (AAAI 2023 · similarity 0.92)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.87)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.86)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.86)
- Maxileximin Envy Allocations and Connected Goods (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.