Fair Division of a Graph
Authors: Sylvain Bouveret, Katarína Cechlárová, Edith Elkind, Ayumi Igarashi, Dominik Peters
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we introduce and study a formal model for such scenarios. Specifically, we consider the problem of fair allocation of indivisible items in settings where there is a graph capturing the dependency relation between items, and each agent s share has to be connected in this graph. We prove a strong positive result for our setting: an MMS allocation always exists if the underlying graph is a tree, and can be computed efficiently. Our algorithm is an adaptation of the classic last-diminisher procedure for the divisible case. In contrast, we provide an example where the underlying graph is a cycle of length 8 and there is no MMS allocation. |
| Researcher Affiliation | Academia | Sylvain Bouveret LIG Grenoble INP, France sylvain.bouveret@imag.fr Katarína Cechlárová P.J. Šafárik University, Slovakia katarina.cechlarova@upjs.sk Edith Elkind University of Oxford, UK elkind@cs.ox.ac.uk Ayumi Igarashi University of Oxford, UK ayumi.igarashi@cs.ox.ac.uk Dominik Peters University of Oxford, UK dominik.peters@cs.ox.ac.uk |
| Pseudocode | Yes | Algorithm 1: A(I , (qi)i N ) input :I = (G , N , U ) and (qi)i N where G is a subtree of G, N is a subset of N, and u i = ui|V for all i N output :A valid allocation π such that ui(π(i)) qi for all i N |
| Open Source Code | No | The paper does not provide any statements about releasing source code for the described methodology or links to a code repository. |
| Open Datasets | No | The paper describes theoretical work and does not use datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |