The Price of Connectivity in Fair Division
Authors: Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, Warut Suksompong5151-5158
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. ... We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. ... From a technical point of view, our work makes extensive use of tools and concepts from graph theory, including vertex connectivity, linkedness, ear decomposition, and bipolar ordering. We believe that establishing these connections enriches the growing literature and lays the groundwork for fruitful collaborations between researchers across the two well-established fields. Furthermore, we remark that with the exception of Theorem 3.11, all of our guarantees are constructive. In particular, we exhibit polynomial-time algorithms that produce allocations satisfying the guarantees. |
| Researcher Affiliation | Academia | Xiaohui Bei,1 Ayumi Igarashi,2 Xinhang Lu,1 Warut Suksompong3 1 School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 2 Principles of Informatics Research Division, National Institute of Informatics, Japan 3 School of Computing, National University of Singapore, Singapore |
| Pseudocode | No | The paper mentions that its guarantees are constructive and that they "exhibit polynomial-time algorithms" (Section 1.1) but does not provide any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention making its source code openly available or provide links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not use datasets for validation. |
| Hardware Specification | No | The paper is theoretical and does not report on experimental hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |