Weighted Maxmin Fair Share Allocation of Indivisible Chores
Authors: Haris Aziz, Hau Chan, Bo Li
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate the study of indivisible chore allocation for agents with asymmetric shares. The fairness concept we focus on is the weighted natural generalization of maxmin share: WMMS fairness and OWMMS fairness. We first highlight the fact that commonly-used algorithms that work well for the allocation of goods to asymmetric agents, and even for chores to symmetric agents do not provide good approximations for allocation of chores to asymmetric agents under WMMS. As a consequence, we present a novel polynomial-time constant-approximation algorithm, via linear program, for OWMMS. For two special cases: the binary valuation case and the 2-agent case, we provide exact or better constant-approximation algorithms. |
| Researcher Affiliation | Academia | Haris Aziz1 , Hau Chan2 and Bo Li3 1UNSW Sydney and Data61 CSIRO, Australia 2Department of Computer Science and Engineering, University of Nebraska-Lincoln, USA 3Department of Computer Science, Stony Brook University, USA |
| Pseudocode | Yes | Algorithm 1 Egal Greedy An Algorithm for Identical Valuations |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the described methodology, nor does it provide any links to a code repository. |
| Open Datasets | No | This paper is theoretical, focusing on algorithm design and proofs for fair allocation. It does not conduct experiments on datasets, thus no dataset is mentioned as publicly available for training. |
| Dataset Splits | No | This paper is theoretical, focusing on algorithm design and proofs for fair allocation. It does not conduct experiments on datasets, and therefore no training, validation, or test splits are discussed. |
| Hardware Specification | No | The paper is theoretical in nature, focusing on algorithm design and mathematical proofs. It does not describe any computational experiments or their hardware requirements. |
| Software Dependencies | No | The paper is theoretical and discusses algorithms and proofs without detailing their practical implementation environment. It does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithm design and proofs. It does not describe an experimental setup with hyperparameters or specific training configurations. |