Notice: This website is continuously updated as new conference proceedings and journal volumes are published. Consequently, the figures presented here may differ from those reported in our publications.
A brief overview of our methodology is provided on the Methods page, along with references to publications documenting our approach and links to the code and data used in each study.
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.
Fair and Efficient Allocations of Chores under Bivalued Preferences
Authors: Jugal Garg, Aniket Murhekar, John Qin5043-5050
AAAI 2022 | Venue PDF | LLM Run Details | Input Tokens: 18,884 Total number of tokens sent to the LLM as input for this paper's analysis. | Output Tokens: 2,902 Total number of tokens produced by the LLM (including reasoning/thinking tokens) for this paper's analysis.
| 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. |