Fair division of a graph

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 t...

Ausführliche Beschreibung

Bibliographische Detailangaben
Hauptverfasser: Bouveret, S, Cechlárová, K, Elkind, E, Igarashi, A, Peters, D
Format: Conference item
Veröffentlicht: AAAI Press / International Joint Conferences on Artificial Intelligence 2017
_version_ 1826298307143532544
author Bouveret, S
Cechlárová, K
Elkind, E
Igarashi, A
Peters, D
author_facet Bouveret, S
Cechlárová, K
Elkind, E
Igarashi, A
Peters, D
author_sort Bouveret, S
collection OXFORD
description 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 where the 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.
first_indexed 2024-03-07T04:44:50Z
format Conference item
id oxford-uuid:d2e20786-3f41-4e4c-b420-cfcf24cc41d5
institution University of Oxford
last_indexed 2024-03-07T04:44:50Z
publishDate 2017
publisher AAAI Press / International Joint Conferences on Artificial Intelligence
record_format dspace
spelling oxford-uuid:d2e20786-3f41-4e4c-b420-cfcf24cc41d52022-03-27T08:07:20ZFair division of a graphConference itemhttp://purl.org/coar/resource_type/c_5794uuid:d2e20786-3f41-4e4c-b420-cfcf24cc41d5Symplectic Elements at OxfordAAAI Press / International Joint Conferences on Artificial Intelligence2017Bouveret, SCechlárová, KElkind, EIgarashi, APeters, DWe 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 where the 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.
spellingShingle Bouveret, S
Cechlárová, K
Elkind, E
Igarashi, A
Peters, D
Fair division of a graph
title Fair division of a graph
title_full Fair division of a graph
title_fullStr Fair division of a graph
title_full_unstemmed Fair division of a graph
title_short Fair division of a graph
title_sort fair division of a graph
work_keys_str_mv AT bouverets fairdivisionofagraph
AT cechlarovak fairdivisionofagraph
AT elkinde fairdivisionofagraph
AT igarashia fairdivisionofagraph
AT petersd fairdivisionofagraph