Dynamic Fair Division Problem with General Valuations
Authors: Bo Li, Wenyang Li, Yingkai Li
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | 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 first 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 boli2@cs.stonybrook.edu, wenl6@student.unimelb.edu.au, yingkai.li@u.northwestern.edu |
| 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. |