On Fair and Efficient Allocations of Indivisible Goods
Authors: Aniket Murhekar, Jugal Garg5595-5602
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a pseudo-polynomial time algorithm to compute an EF1+f PO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+f PO allocation always exists when the values are positive, and that it can be computed in pseudo-polynomial time. We also consider the class of k-ary instances where k is a constant, i.e., each agent has at most k different values for the goods. We show that for such instances an EF1+f PO allocation can be computed in polynomial time. When all values are positive, we show that an EQ1+f PO allocation for such instances can be computed in polynomial time. Next, we consider instances where the number of agents is constant, and show that an EF1+PO (also EQ1+PO) allocation can be computed in polynomial time. These results significantly extend the polynomial-time computability beyond the known cases of binary or identical valuations. Further, we show that the problem of computing an EF1+PO allocation polynomial-time reduces to a problem in the complexity class PLS. We also design a polynomial-time algorithm that computes Nash welfare maximizing allocations when there are constantly many agents with constant many different values for the goods. |
| Researcher Affiliation | Academia | Aniket Murhekar, Jugal Garg University of Illinois, Urbana-Champaign {aniket2, jugal}@illinois.edu |
| Pseudocode | Yes | Algorithm 1 Computing an EF1+f PO allocation of goods; Algorithm 2 Computing an EQ1+f PO allocation of goods |
| Open Source Code | No | The paper does not provide any specific links or statements about releasing the source code. |
| Open Datasets | No | The paper is theoretical and focuses on algorithms and complexity analysis. It does not use datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithms and complexity analysis. It does not use datasets or specify data splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe running experiments; therefore, it does not specify any hardware used. |
| Software Dependencies | No | The paper is theoretical and does not describe running experiments; therefore, it does not list any software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe any experimental setup details such as hyperparameters or training configurations. |