Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.03238 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917460818526208 |
|---|---|
| author | Viswanathan, Vignesh |
| author_facet | Viswanathan, Vignesh |
| contents | We consider the problem of partitioning an undirected graph (representing a social network) over $n$ nodes and max degree $Δ$ into $k$ equally sized parts. Each node in the graph, representing an agent, derives utility proportional to the number of their neighbors in their assigned part. Our goal is to find a balanced partitioning that is fair. The two notions of fairness we consider are the core and envy-freeness. A partition is envy-free if no node gains utility from moving to a different part, and a partition is in the core if no set of $n/k$ nodes can deviate to form a new part with all nodes gaining in utility.
We show that there exists a balanced partition which is both $O(\max\{\sqrtΔ, k^2\} \ln n)$-approximately envy-free and in the $(k + o(k))$-approximate core. Taken separately, these two guarantees are comparable to (and in some cases, better than) the best known envy-freeness and core guarantees for this problem. Moreover, we show that these desirable partitions can be computed efficiently if we slightly relax the balancedness constraint. In addition, when $k = 2$, we show that a $(1.618 + o(1))$-core exists, and a $(2 + \varepsilon)$-core can be computed in polynomial time. The last two results make progress on two open questions from Li et al. [AAAI, 2023]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03238 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Some Improved Results on Fair and Balanced Graph Partitions Viswanathan, Vignesh Computer Science and Game Theory We consider the problem of partitioning an undirected graph (representing a social network) over $n$ nodes and max degree $Δ$ into $k$ equally sized parts. Each node in the graph, representing an agent, derives utility proportional to the number of their neighbors in their assigned part. Our goal is to find a balanced partitioning that is fair. The two notions of fairness we consider are the core and envy-freeness. A partition is envy-free if no node gains utility from moving to a different part, and a partition is in the core if no set of $n/k$ nodes can deviate to form a new part with all nodes gaining in utility. We show that there exists a balanced partition which is both $O(\max\{\sqrtΔ, k^2\} \ln n)$-approximately envy-free and in the $(k + o(k))$-approximate core. Taken separately, these two guarantees are comparable to (and in some cases, better than) the best known envy-freeness and core guarantees for this problem. Moreover, we show that these desirable partitions can be computed efficiently if we slightly relax the balancedness constraint. In addition, when $k = 2$, we show that a $(1.618 + o(1))$-core exists, and a $(2 + \varepsilon)$-core can be computed in polynomial time. The last two results make progress on two open questions from Li et al. [AAAI, 2023]. |
| title | Some Improved Results on Fair and Balanced Graph Partitions |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2605.03238 |