{"ID":2845882,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.03629","arxiv_id":"2511.03629","title":"Non-Monotonicity in Fair Division of Graphs","abstract":"We consider the problem of fairly allocating the vertices of a graph among $n$ agents, where the value of a bundle is determined by its cut value -- the number of edges with exactly one endpoint in the bundle. This model naturally captures applications such as team formation and network partitioning, where valuations are inherently non-monotonic: the marginal values may be positive, negative, or zero depending on the composition of the bundle. We focus on the fairness notion of envy-freeness up to one item (EF1) and explore its compatibility with several efficiency concepts such as Transfer Stability (TS) that prohibits single-item transfers that benefit one agent without making the other worse-off. For general graphs, our results uncover a non-monotonic relationship between the number of agents $n$ and the existence of allocations satisfying EF1 and transfer stability (TS): such allocations always exist for $n=2$, may fail to exist for $n=3$, but exist again for all $n\\geq 4$. We further show that existence can be guaranteed for any $n$ by slightly weakening the efficiency requirement or by restricting the graph to forests. All of our positive results are achieved via efficient algorithms.","short_abstract":"We consider the problem of fairly allocating the vertices of a graph among $n$ agents, where the value of a bundle is determined by its cut value -- the number of edges with exactly one endpoint in the bundle. This model naturally captures applications such as team formation and network partitioning, where valuations a...","url_abs":"https://arxiv.org/abs/2511.03629","url_pdf":"https://arxiv.org/pdf/2511.03629v1","authors":"[\"Hadi Hosseini\",\"Shraddha Pathak\",\"Yu Zhou\"]","published":"2025-11-05T16:48:52Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.DS\"]","methods":"[]","has_code":false}