Nearly Equitable Allocations beyond Additivity and Monotonicity
Authors: Siddharth Barman, Umang Bhaskar, Yeshwant Pandit, Soumyajit Pyne
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study both the existence and efficient computation of EQx allocations. (1) For monotone valuations (not necessarily additive), we show that EQx allocations always exist. Also, for the large class of weakly well-layered valuations, EQx allocations can be found in polynomial time. Further, we prove that approximately EQx allocations can be computed efficiently under general monotone valuations. (2) For non-monotone valuations, we show that an EQx allocation may not exist, even for two agents with additive valuations. Under some special cases, however, we show existence and efficient computability of EQx allocations. This includes the case of two agents with additive valuations where each item is either a good or a chore, and there are no mixed items. |
| Researcher Affiliation | Academia | 1 Indian Institute of Science, Bangalore 2 Tata Institute of Fundamental Research, Mumbai |
| Pseudocode | Yes | Algorithm 1: Greedy Add-and-Fix; Algorithm 2: Two-Way Greedy Algorithm; Algorithm 3: ++ comparison operator; Algorithm 4: Algorithm to compute an EQx allocation |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., a link or explicit statement of release) for source code. |
| Open Datasets | No | The paper is theoretical and focuses on existence and computability of allocations, not empirical evaluation on datasets. Therefore, no dataset is used or made available. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with training, validation, or test sets. Therefore, no dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not involve experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and describes algorithms and proofs. It does not mention any specific software dependencies or versions required for implementation or experiments. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and proofs for existence and computability. It does not describe an empirical experimental setup, including hyperparameters or system-level training settings. |