Fair Division with a Secretive Agent
Authors: Eshwar Ram Arunachaleswaran, Siddharth Barman, Nidhi Rathi1732-1739
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We will show that, for all of these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation. For the rent-division setting we prove that well-behaved utilities of n 1 agents suffice to find a rent division among n rooms such that, for every possible room selection of the secretive agent, there exists an allocation (of the remaining n 1 rooms among the n 1 agents) which ensures overall envy freeness (fairness). We complement this existential result by developing a polynomial-time algorithm for the case of quasilinear utilities. In this partial information setting, we also develop efficient algorithms to compute allocations that are envy-free up to one good (EF1) and ε-approximate envy free. |
| Researcher Affiliation | Academia | 1Indian Institute of Science eshwarram.arunachaleswaran@gmail.com, barman@iisc.ac.in, nidhirathi@iisc.ac.in |
| Pseudocode | Yes | Algorithm 1 Secretive Envy-Free Rent Division under Quasilinear Utilities; Algorithm 2 Computation of Secretive EF1 Allocations |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | This paper focuses on theoretical contributions (algorithms, proofs) and does not describe experiments using datasets, thus no information on training data or its public availability is provided. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments with dataset splits. Therefore, no specific dataset split information for validation is provided. |
| Hardware Specification | No | The paper does not describe any specific hardware used for running experiments, which is consistent with its theoretical nature. |
| Software Dependencies | No | The paper describes algorithms and theoretical concepts but does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and proofs. It does not include details on experimental setup such as hyperparameters or system-level training settings. |