On Optimal Tradeoffs between EFX and Nash Welfare
Authors: Michal Feldman, Simon Mauras, Tomasz Ponitka
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | For additive valuations, we show that for any α [0, 1], there exists a partial allocation that is α-EFX and 1 α+1-MNW. This tradeoff turns out to be tight (for every α) as demonstrated by an impossibility result that we give. We also show that for α [0, φ 1 0.618] these partial allocations can be turned into complete allocations where all items are assigned. Furthermore, for any α [0, 1/2], we show that the tight tradeoff of α-EFX and 1 α+1-MNW with complete allocations holds for the more general setting of subadditive valuations. Our results improve upon the current state of the art, for both additive and subadditive valuations, and match the best-known approximations of EFX under complete allocations, regardless of Nash welfare guarantees. Notably, our constructions for additive valuations also provide EF1 and constant approximations for maximin share guarantees. |
| Researcher Affiliation | Collaboration | Michal Feldman1,2, Simon Mauras1, Tomasz Ponitka1, 1Tel Aviv University, 2Microsoft ILDC |
| Pseudocode | Yes | Algorithm 1: Additive valuations. Input (X1, . . . , Xn) is a complete MNW allocation. Output (M1, . . . , Mn) is a partial α-EFX and 1 α+1-MNW allocation. 1: match i to J means Mi J 2: unmatch Zi means Mu if there is u matched to Zi 3: procedure ALG 4: Z (X1, . . . , Xn) 5: M ( , . . . , ) 6: while there is an agent i with Mi = do 7: i any agent with Mi = 8: if (vi (Zi ) α vi (Zj g) for all j and g Zj 9: and Zi = Xi ) or 10: (vi (Zi ) vi (Zj g) for all j and g Zj 11: and Zi = Xi ) then 12: unmatch Zi 13: match i to Zi 14: else 15: j , g any j and g Zj 16: that maximize vi (Zj g) 17: unmatch Zj 18: change Zj to Zj g 19: match i to Zj 20: end if 21: end while 22: return (M1, . . . , Mn) 23: end procedure |
| Open Source Code | No | The paper cites a CoRR preprint for the full version ('Feldman, M.; Mauras, S.; and Ponitka, T. 2023. On Optimal Tradeoffs between EFX and Nash Welfare. Co RR, abs/2302.09633.') but does not explicitly state that source code for their methodology is available or provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper describes algorithms theoretically but does not specify any software dependencies with version numbers (e.g., programming languages, libraries, or solvers) required for replication. |
| Experiment Setup | No | The paper is theoretical and does not include empirical experiments, thus no experimental setup details such as hyperparameters are provided. |