Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio
Authors: Bo Li, Zihao Li, Shengxin Liu, Zekai Wu
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose to study the up to a fraction relaxation of EF and PROP, when a mixture of divisible and indivisible goods are allocated. We show that an EFα allocation may not exist and a PROPα allocation always exists. Thus we would like to understand to what extent EFα needs to be relaxed and PROPα can be strengthened, namely EFf(α) and PROPf(α), so that a fair up to a fraction allocation exists. In Section 3, we study the up to a fraction relaxation of EF, i.e., EFα and EFf(α). We first prove that f(α) = Θ(n)α is necessary and sufficient to satisfy EF by removing f(α) fraction of a good. We find that any EFM allocation is EFnα, and thus an EFnα allocation always exists (by [Bei et al., 2021a]). The guarantee of EFM cannot be improved even when agents have identical valuations. On the other hand, we prove that at least n2 4(n 1)α fraction of the good has to be removed in order to satisfy EF, and thus our results are tight up to a constant. |
| Researcher Affiliation | Academia | 1The Hong Kong Polytechnic University 2Nanyang Technological University 3Harbin Institute of Technology, Shenzhen |
| Pseudocode | Yes | Algorithm 1: Finding a PROPα allocation |
| Open Source Code | No | The paper does not provide any statement about making its source code open or available, nor does it include a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not describe experiments conducted on a dataset, thus no dataset access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any empirical experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include empirical experiments with specific setup details like hyperparameters or training configurations. |