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].
Asymptotic Analysis of Weighted Fair Division
Authors: Pasin Manurangsi, Warut Suksompong, Tomohiko Yokoyama
IJCAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We analyze weighted fair division from an asymptotic perspective: if m items are divided among n agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that m = โฆ(n log n/ log log n), generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of m = n/(1 ยต) for the transition from non-existence to existence, where ยต (0, 1) denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if m = ฯ( r), where r denotes the ratio between the two weights. The paper contains several lemmas and theorems, focusing on theoretical proofs and asymptotic analysis rather than empirical evaluation with datasets. |
| Researcher Affiliation | Collaboration | 1Google Research, Thailand 2National University of Singapore, Singapore 3The University of Tokyo, Japan |
| Pseudocode | Yes | Algorithm 1 Weighted Picking Sequence Algorithm Algorithm 2 Matching-Based Algorithm for WPROP |
| Open Source Code | No | The paper does not explicitly state that source code for the described methodology is released. It mentions 'Co RR, abs/2504.21728, 2025.' which appears to be a preprint archive reference, not a code repository. |
| Open Datasets | No | Each agent s utility for each item is drawn independently from a non-atomic distribution D over [0, 1]. The paper describes a theoretical framework where utilities are sampled from a probability distribution, rather than using or providing access to a specific, pre-existing public dataset. |
| Dataset Splits | No | The paper does not use any specific dataset for experiments, but rather relies on theoretical analysis of utilities drawn from a probability distribution. Therefore, there are no dataset splits mentioned. |
| Hardware Specification | No | The paper focuses on theoretical analysis and algorithms. There is no mention of specific hardware (like GPU or CPU models) used for running any experiments, as no empirical experiments are described. |
| Software Dependencies | No | The paper describes theoretical algorithms and proofs. It does not mention any specific software dependencies or versions (e.g., programming languages, libraries, or solvers with version numbers) that would be needed to replicate experimental results. |
| Experiment Setup | No | The paper presents theoretical results and algorithms without detailing any empirical experiments. Consequently, there is no mention of specific experimental setup details, hyperparameters, or training configurations. |