Approximately EFX and fPO Allocations for Bivalued Chores
Authors: Zehan Lin, Xiaowei Wu, Shengwei Zhou
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we improve the approximation ratio to (2 1/k), while preserving the fractional Pareto optimality. Instead of rounding fractional equilibrium, our algorithm starts with the integral EF1 equilibrium for bi-valued chores and reallocates items until approximate EFX is achieved. We further improve our result for the case when k = 2 and devise an algorithm that computes EFX and f PO allocations. ... Result 1 (Theorem 3.14). For {1, k}-instances of indivisible chores, there exists an algorithm that computes (2 1/k)-EFX and f PO allocations in polynomial time. ... Result 2 (Theorem 4.1). For {1, 2}-instances of indivisible chores, there exists an algorithm that computes EFX and f PO allocations in polynomial time. |
| Researcher Affiliation | Academia | IOTSC, University of Macau EMAIL, |
| Pseudocode | Yes | Algorithm 1: Computation of (2 1/k)-EFX and f PO allocations for {1, k}-instances |
| Open Source Code | No | The paper does not provide any explicit statement about open-source code availability, nor does it include links to code repositories. |
| Open Datasets | No | The paper focuses on theoretical 'bi-valued instances' or '{1, k}-instances' for chores and does not refer to any specific real-world or synthetic datasets used in experiments, nor does it provide access information for any dataset. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on datasets, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper focuses on theoretical algorithm design and analysis. It does not describe any experimental hardware used. |
| Software Dependencies | No | The paper describes algorithms and their theoretical properties. It does not mention any specific software dependencies or version numbers needed to replicate experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis, rather than empirical experiments. Therefore, no experimental setup details such as hyperparameters or training configurations are provided. |