Fair and Efficient Allocations under Subadditive Valuations
Authors: Bhaskar Ray Chaudhury, Jugal Garg, Ruta Mehta5269-5276
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design a polynomial-time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieves an O(n) approximation to the Nash welfare. Our result also improves the current best-known approximation of O(n log n) and O(m) to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an O(n) approximation to a family of welfare measures, p-mean of valuations for p ( , 1], thereby also matching asymptotically the current best approximation ratio for special cases like p = while also retaining the remarkable fairness properties. |
| Researcher Affiliation | Academia | 1 Max Planck Institute for Informatics, Saarland Informatics Campus 2 University of Illinois at Urbana-Champaign |
| Pseudocode | Yes | Algorithm 1 Determining an (α, c)-EFX allocation with O(n) approximation on optimum p-mean. |
| Open Source Code | No | The paper does not provide any links or explicit statements about the availability of open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper presenting an algorithm and proofs, not empirical experiments on a specific dataset. Therefore, no information about publicly available datasets is provided. |
| Dataset Splits | No | This is a theoretical paper presenting an algorithm and proofs, not empirical experiments. Therefore, no dataset split information (training/validation/test) is provided. |
| Hardware Specification | No | This is a theoretical paper that designs an algorithm and provides proofs, without reporting on the computational experiments. Thus, no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper that designs an algorithm and provides proofs, without reporting on the computational experiments. Thus, no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | This is a theoretical paper that designs an algorithm and provides proofs, without reporting on the computational experiments. Thus, no experimental setup details like hyperparameters or training settings are provided. |