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; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Improved Regret Bounds for Online Fair Division with Bandit Learning
Authors: Benjamin Schiffer, Shirley Zhang
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is that, when player values are normalized, an algorithm can achieve O(T) regret while satisfying proportionality in expectation constraints at every time step with high probability (Theorem 1). This is an improvement on the Ω(T 2/3) regret of the explore-then-commit algorithm in (Procaccia, Schiffer, and Zhang 2024). The algorithm that achieves our result (Algorithm 1) uses a variant of upper confidence bound (UCB) logic with two rounds of linear program optimization. ... Theorem 2 shows that an equivalent result to Theorem 1 does not hold for envy-freeness in expectation, and in fact the best regret possible while maintaining envy-freeness in expectation is Ω(T 2/3). |
| Researcher Affiliation | Academia | Benjamin Schiffer, Shirley Zhang Harvard University |
| Pseudocode | Yes | Algorithm 1: UCB Online Fair Division |
| Open Source Code | No | The paper does not provide any information about open-source code for the methodology described. |
| Open Datasets | No | We study online fair division when there are a finite number of item types and the player values for the items are drawn randomly from distributions with unknown means. ... The paper does not use any specific publicly available datasets for experimental evaluation. |
| Dataset Splits | No | The paper does not describe any experiments using datasets, and therefore no dataset splits are provided. |
| Hardware Specification | No | The paper presents theoretical results and algorithms but does not describe any experimental setup or hardware used. |
| Software Dependencies | No | The paper presents theoretical results and algorithms but does not describe any experimental setup or software dependencies. |
| Experiment Setup | No | The paper presents theoretical results and algorithms but does not describe any experimental setup details such as hyperparameters or system-level training settings. |