Constrained Fair and Efficient Allocations
Authors: Benjamin Cookson, Soroush Ebadian, Nisarg Shah
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is that MNW allocations are 1 2-envy-free up to one good (EF1) and Pareto optimal under the broad family of (arbitrary) matroid constraints. We extend these guarantees to complete MNW allocations for base-orderable matroid constraints, and to a family of non-matroid constraints (which includes balancedness). We establish tightness of our results by providing counterexamples for the satisfiability of certain stronger desiderata, but show an improved result for the special case of goods with copies (Gafni et al. 2023). Finally, we also establish novel best-of-both-worlds guarantees for goods with copies and balancedness. |
| Researcher Affiliation | Academia | University of Toronto EMAIL |
| Pseudocode | Yes | Algorithm 1 CE Lottery for goods-with-copies 1: x a competitive (fractional) allocation of Theorem 7 due to Echenique, Miralles, and Zhang (2021) 2: For all i N and t [m], let Qi,t P j [t] xi,σi(j) be the total fraction of i s top-t goods allocated to her (σi(j) denotes agent i s j-th most preferred good). 3: Define two sets of constraints for an integral allocation y (see full version for an explanation of this): H1 = Qi,t X j [t] yi,σi(j) Qi,t | i N, t [m] , i N yi,g qg | g M . 4: Decompose x = PL ℓ=1 λℓ yℓinto L integral allocations using the algorithm of Budish et al. (2013) (see their Appendix B) with input x and H1, H2 5: return the randomized allocation PL ℓ=1 λℓ yℓ |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating the provision of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve experiments that use specific datasets. Therefore, no information regarding open datasets or their access is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe any experimental setup involving datasets or their splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper mentions 'CPLEX' as a tool for computation in the discussion section, but does not specify a version number or indicate it as a software dependency for the authors' own work. No other specific software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical properties and proofs, rather than empirical experiments. Therefore, no specific experimental setup details, hyperparameters, or training configurations are provided. |