Fair and Efficient Completion of Indivisible Goods
Authors: Vishwa Prakash HV, Ayumi Igarashi, Rohit Vaish
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of the completion problem for prominent fairness and efficiency notions such as envy-freeness up to one good (EF1), proportionality up to one good (Prop1), maximin share (MMS), and Pareto optimality (PO), and focus on the class of additive valuations as well as its subclasses such as binary additive and lexicographic valuations. We find that while the completion problem is significantly harder than the standard fair division problem (wherein the initial partial allocation is empty), the consideration of restricted preferences facilitates positive algorithmic results for threshold-based fairness notions (Prop1 and MMS). On the other hand, the completion problem remains computationally intractable for envy-based notions such as EF1 and EF1+PO even under restricted preferences. Our results, summarized in Table 1, span the well-studied class of additive valuations as well as its subclasses such as binary additive and lexicographic valuations. Some of the technical highlights of our work are: For binary additive valuations, we show that achieving an EF1 completion is computationally intractable even with the restrictiveness of preferences. This highlights a stark contrast with the standard setting, where an EF1 allocation can be computed efficiently (Lipton et al. 2004; Conitzer, Freeman, and Shah 2017). |
| Researcher Affiliation | Academia | Vishwa Prakash HV1, Ayumi Igarashi2, Rohit Vaish3 1Chennai Mathematical Institute, India 2University of Tokyo, Japan 3Indian Institute of Technology Delhi, India EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper describes algorithms and computational procedures, for example, in the proof sketch for Theorem 2 regarding a maximum flow approach. However, these are described in natural language and are not formatted as distinct, labeled pseudocode or algorithm blocks. There are no figures or sections explicitly labeled 'Pseudocode' or 'Algorithm'. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the methodology described. There are no links to code repositories or mentions of code being available in supplementary materials. |
| Open Datasets | No | The paper focuses on theoretical computational complexity results and does not involve empirical experiments using datasets. Therefore, it does not provide access information for any open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets. Consequently, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes theoretical results regarding computational complexity and algorithms. It does not present any experimental results that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is focused on theoretical work, including computational complexity analysis and algorithm design. It does not describe any practical implementation or experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical analysis of computational complexity and properties of fairness notions. It does not describe any empirical experiments, and therefore, no experimental setup details, hyperparameters, or training configurations are provided. |