Fair Division with Social Impact
Authors: Michele Flammini, Gianluigi Greco, Giovanna Varricchio
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we consider the problem of fair division of indivisible goods when the allocation of goods impacts society. Specifically, we introduce a second valuation function for each agent, determining the social impact of allocating a good to the agent. Such impact is considered desirable for the society the higher, the better. Our goal is to understand how to allocate goods fairly from the agents perspective while maintaining society as happy as possible. To this end, we measure the impact on society using the utilitarian social welfare and provide both possibility and impossibility results. Our findings reveal that achieving good approximations, better than linear in the number of agents, is not possible while ensuring fairness to the agents. These impossibility results can be attributed to the fact that agents are completely unconscious of their social impact. Consequently, we explore scenarios where agents are socially aware, by introducing related fairness notions, and demonstrate that an appropriate definition of fairness aligns with the goal of maximizing the social objective. ... We also provide efficient algorithms for computing the corresponding approximately optimal and fair allocations. An overview of our results for n agents is given in Table 1. For all the fairness notions we considered, an approximation better than linear in the number of agents is not possible. |
| Researcher Affiliation | Academia | 1Gran Sasso Science Institute, L Aquila, Italy 2University of Calabria, Rende, Italy EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: Transformation into an EF1 allocation Algorithm 2: O(n)-approx. for MAXUT in Case 2 |
| Open Source Code | No | The paper does not contain any explicit statement about providing source code, nor does it include links to repositories or supplementary materials for code. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical models and algorithms for fair division problems. It does not utilize any specific real-world or synthetic datasets for empirical evaluation. Therefore, there is no mention of publicly available or open datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on datasets. Therefore, it does not provide any training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and proofs. It does not describe any experiments that would require specific hardware, and thus, no hardware specifications are provided. |
| Software Dependencies | No | The paper describes theoretical algorithms and proofs. It does not detail any implementation, programming languages, or specific software libraries with version numbers. |
| Experiment Setup | No | The paper is theoretical, presenting mathematical analysis and algorithms without empirical validation. Consequently, there are no experimental setup details, hyperparameters, or system-level training settings described. |