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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Dynamic Fair Division Problem with General Valuations
Authors: Bo Li, Wenyang Li, Yingkai Li
IJCAI 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we focus on how to dynamically allocate a divisible resource fairly among n players who arrive and depart over time. The players may have general heterogeneous valuations over the resource. It is known that exact envy-free and proportional allocations may not exist in the dynamic setting [Walsh, 2011]. Thus, we will study to what extent we can guarantee the fairness in the dynamic setting. We ο¬rst design two algorithms which are O(log n)-proportional and O(n)-envy-free for the setting with general valuations. Then by constructing the adversary instances such that all dynamic algorithms must be at least β¦(1)-proportional and β¦( n log n)-envy-free, we show that the bounds are tight up to a logarithmic factor. Moreover, we introduce a setting where the players valuations are uniform on the resource but with different demands, which generalizes the setting of [Friedman et al., 2015]. We prove an O(log n) upper bound and a tight lower bound for this case. |
| Researcher Affiliation | Academia | Bo Li1, Wenyang Li2, Yingkai Li3 1 Stony Brook University 2 Melbourne University 3 Northwestern University EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 1-Recallable Algorithm A1 DF D Algorithm 2 1-Recallable Algorithm AS UD(d, c, Ξ·) Algorithm 3 1-Recallable Algorithm AUD |
| Open Source Code | No | The paper does not provide any statements about releasing source code or links to repositories for the described methodology. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and proofs; it does not involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe the hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup or hyperparameters. |