Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Fair and Efficient Allocations of Chores under Bivalued Preferences
Authors: Jugal Garg, Aniket Murhekar, John Qin5043-5050
AAAI 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of fair and efficient allocation of a set of indivisible chores to agents with additive cost functions. We consider the popular fairness notion of envy-freeness up to one good (EF1) with the efficiency notion of Paretooptimality (PO). While it is known that an EF1+PO allocation exists and can be computed in pseudo-polynomial time in the case of goods, the same problem is open for chores. Our first result is a strongly polynomial-time algorithm for computing an EF1+PO allocation for bivalued instances, where agents have (at most) two disutility values for the chores. To the best of our knowledge, this is the first nontrivial class of indivisible chores to admit an EF1+PO allocation and an efficient algorithm for its computation. We also study the problem of computing an envy-free (EF) and PO allocation for the case of divisible chores. While the existence of EF+PO allocation is known via competitive equilibrium with equal incomes, its efficient computation is open. Our second result shows that for bivalued instances, an EF+PO allocation can be computed in strongly polynomialtime. |
| Researcher Affiliation | Academia | University of Illinois, Urbana-Champaign EMAIL |
| Pseudocode | Yes | Algorithm 1: Make Init Groups |
| Open Source Code | No | The paper does not provide any link to open-source code or state that code is released. |
| Open Datasets | No | This is a theoretical paper that focuses on algorithm design and proofs, and therefore does not involve training on datasets. |
| Dataset Splits | No | This is a theoretical paper and does not mention using datasets or validation splits. |
| Hardware Specification | No | This is a theoretical paper and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not mention specific software dependencies or versions for experimental setup. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or training configurations. |