When Do Envy-Free Allocations Exist?
Authors: Pasin Manurangsi, Warut Suksompong2109-2116
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that, surprisingly, there is in fact no universal point of transition instead, the transition is governed by the divisibility relation between m and n. On the one hand, if m is divisible by n, an envy-free allocation exists with high probability as long as m 2n. On the other hand, if m is not almost divisible by n, an envy-free allocation is unlikely to exist even when m = Θ(n log n/ log log n). |
| Researcher Affiliation | Academia | Pasin Manurangsi Department of EECS UC Berkeley Warut Suksompong Department of Computer Science University of Oxford |
| Pseudocode | Yes | Algorithm 1 Simplified Algorithm for r 3 |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper does not use a specific, named public dataset for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not specify any hardware used for running experiments. |
| Software Dependencies | No | The paper does not specify software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |