{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T11:31:06Z","timestamp":1782127866423,"version":"3.54.5"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>We consider fair allocation of indivisible items under an additional constraint: there is an undirected graph describing the relationship between the items, and each agent's share must form a connected subgraph of this graph. This framework captures, e.g., fair allocation of land plots, where the graph describes the accessibility relation among the plots. We focus on agents that have additive utilities for the items, and consider several common fair division solution concepts, such as proportionality, envy-freeness and maximin share guarantee. While finding good allocations according to these solution concepts is computationally hard in general, we design efficient algorithms for special cases wherethe underlying graph has simple structure, and\/or the number of agents---or, less restrictively, the number of agent types---is small. In particular, despite non-existence results in the general case, we prove that for acyclic graphs a maximin share allocation always exists and can be found efficiently.<\/jats:p>","DOI":"10.24963\/ijcai.2017\/20","type":"proceedings-article","created":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T09:14:07Z","timestamp":1501233247000},"page":"135-141","source":"Crossref","is-referenced-by-count":39,"title":["Fair Division of a Graph"],"prefix":"10.24963","author":[{"given":"Sylvain","family":"Bouveret","sequence":"first","affiliation":[{"name":"Grenoble INP, LIG, Universit\u00e9 Grenoble-Alpes"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katar\u00edna","family":"Cechl\u00e1rov\u00e1","sequence":"additional","affiliation":[{"name":"P.J. \u0160af\u00e1rik University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edith","family":"Elkind","sequence":"additional","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ayumi","family":"Igarashi","sequence":"additional","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dominik","family":"Peters","sequence":"additional","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Twenty-Sixth International Joint Conference on Artificial Intelligence","theme":"Artificial Intelligence","location":"Melbourne, Australia","acronym":"IJCAI-2017","number":"26","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)","University of Technology Sydney (UTS)","Australian Computer Society (ACS)"],"start":{"date-parts":[[2017,8,19]]},"end":{"date-parts":[[2017,8,26]]}},"container-title":["Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T11:51:51Z","timestamp":1501242711000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2017\/20"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2017\/20","relation":{},"subject":[],"published":{"date-parts":[[2017,8]]}}}