Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Revisiting Proportional Allocation with Subsidy: Simplification and Improvements
Authors: Xiaowei Wu, Quan Xue, Shengwei Zhou
IJCAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose a much simpler algorithm for the problem, which does not require rounding fractional allocations, and achieves an optimal subsidy guarantee for all values of n. We further show that our algorithm and analysis framework can be extended to the mixture of (subjective) goods and chores, achieving the optimal subsidy guarantee. [...] In the following, we prove the following theorem. Theorem 3.1. Given any instance I = (M, N, u) for the allocation of chores, we can compute in polynomial time a PROP1 allocation X such that in the corresponding PROP outcome, the total subsidy is at most α(n). Our algorithm follows a simple idea: (1) Suppose that we can partition the items into bundles whose utilities are roughly the same for all agents (e.g., differ by at most 1), then we can treat the n bundles as n mega-items ; (2) By sequentially allocating each mega-item to the agent requiring the minimum subsidy on it, we can upper bound the total subsidy utilizing the efficiency of subsidization. |
| Researcher Affiliation | Academia | Xiaowei Wu1 , Quan Xue2 , Shengwei Zhou1 1 IOTSC, University of Macau 2 The University of Hong Kong EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: PROP Outcome for Chores Input: An IDO instance I = (M, N, u) with ui(e1) ui(e2) ui(em) for all i N. 1 Let Ai {ej : j = i + z n for some integer z}, for all i [n] ; 2 Let N N ; 3 for j = 1, 2, . . . , n do 4 Let i argmini N {PROPi ui(Aj)} ; 5 Update Xi Aj and N N \ {i } ; Output: PROP outcome with allocation X. |
| Open Source Code | No | The paper does not contain any explicit statements about open-source code availability, nor does it provide links to code repositories or mention code in supplementary materials. |
| Open Datasets | No | The paper is theoretical, analyzing fair allocation problems with abstract items and agents, and does not involve experimental evaluation on specific datasets. Therefore, it does not provide information about open datasets. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments using datasets, thus it does not include information about dataset splits. |
| Hardware Specification | No | The paper describes theoretical algorithms and proofs, and does not report on any experimental setup or hardware used for computation. |
| Software Dependencies | No | As a theoretical paper focusing on algorithm design and proofs, there is no mention of specific software dependencies or versions used for implementation or experimentation. |
| Experiment Setup | No | The paper is purely theoretical, focusing on algorithmic design and mathematical proofs rather than empirical experimentation. Therefore, no experimental setup details such as hyperparameters or training configurations are provided. |