Fair Division of a Graph into Compact Bundles
Authors: Jayakrishnan Madathil
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of fair division of indivisible items in an enriched model: there is an underlying graph on the set of items. And we have to allocate the items (i.e., the vertices of the graph) to a set of agents in such a way that (a) the allocation is fair (for appropriate notions of fairness) and (b) each agent receives a bundle of items (i.e., a subset of vertices) that induces a subgraph with a speciļ¬c nice structure. This model has previously been studied in the literature with the nice structure being a connected subgraph. In this paper, we propose an alternative for connectivity in fair division. We introduce compact graphs, and look for fair allocations in which each agent receives a compact bundle of items. Through compactness, we attempt to capture the idea that every agent must receive a bundle of closely related items. We prove a host of hardness and tractability results with respect to fairness concepts such as proportionality, envy-freeness and maximin share guarantee. |
| Researcher Affiliation | Academia | Jayakrishnan Madathil University of Glasgow, UK jayakrishnan.madathil@glasgow.ac.uk |
| Pseudocode | No | The paper describes algorithms and their properties (e.g., dynamic programming, FPT, XP) but does not provide a formal pseudocode block or algorithm listing. |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not involve empirical evaluation on datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation or data splitting for validation. |
| Hardware Specification | No | The paper is theoretical and does not specify any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers for an implementation. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, hyperparameters, or training configurations. |