Improved Approximation of Weighted MMS Fairness for Indivisible Chores
Authors: Fangxiao Wang, Bo Li, Pinyan Lu
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we first design a simple sequential picking algorithm that solely relies on the agents ordinal rankings of the items, which achieves an approximation ratio of O(log n). Then, for the case involving two agents, we improve the approximation ratio to 2 1.366, and prove that it is optimal. We also consider an online setting when the items arrive one after another and design an O( n)-competitive online algorithm given the valuations are normalized. |
| Researcher Affiliation | Academia | 1Department of Computing, The Hong Kong Polytechnic University 2 Institute for Theoretical Computer Science, Shanghai University of Finance and Economics 3 Key Laboratory of Interdisciplinary Research of Computation and Economics (Shanghai University of Finance and Economics), Ministry of Education |
| Pseudocode | Yes | Algorithm 1 fractional allocation integral allocation Input: A fractional allocation x = (x1, . . . , xn) for ordered instance I = (M, N, w, v). Output: An integral allocation A = (A1, . . . , An). 1: Initialize that Ai = for ai N. 2: for j = 1 to m do 3: Choose one agent ai for whom |Ai| < Pj k=1 xik. 4: Ai Ai {oj}. 5: end for 6: return A = (A1, . . . , An). |
| Open Source Code | No | The paper does not provide any specific links to source code repositories or explicit statements about the release of code for the described methodology. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and proofs for fair allocation problems. It does not use or refer to specific datasets that would be publicly available for training models. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments involving training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware specifications used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |