Temporal Fair Division of Indivisible Goods with Scheduling
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911628747866112 |
|---|---|
| author | Choi, Kui-Wang Li, Minming |
| author_facet | Choi, Kui-Wang Li, Minming |
| contents | We study temporal fair division, where agents receive goods over multiple rounds and cumulative fairness is required. We investigate Temporal Envy-Freeness Up to One Good (TEF1) and Up to Any Good (TEFX), its approximation $α$-TEFX, and Temporal Maximin Share (TMMS). Motivated by known impossibilities in standard settings, we consider the model in various restricted settings and extend it by introducing scheduling.
Our main contributions draw the boundary between possibility and impossibility. First, regarding temporal fair division without scheduling, we prove that while constant-factor $α$-TEFX is impossible in general, a $1/2$-approximation is achievable for generalized binary valuations and identical days with two agents. Second, regarding temporal fair division with scheduling, we demonstrate that a scheduling buffer of size at least $n/2$ enables TEF1 for identical days. However, we establish that TEFX and TMMS remain largely impossible even with scheduling or restricted domains. These results highlight the inherent difficulty of strict temporal fairness and quantify the trade-offs required to achieve approximation guarantees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_12835 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Temporal Fair Division of Indivisible Goods with Scheduling Choi, Kui-Wang Li, Minming Computer Science and Game Theory We study temporal fair division, where agents receive goods over multiple rounds and cumulative fairness is required. We investigate Temporal Envy-Freeness Up to One Good (TEF1) and Up to Any Good (TEFX), its approximation $α$-TEFX, and Temporal Maximin Share (TMMS). Motivated by known impossibilities in standard settings, we consider the model in various restricted settings and extend it by introducing scheduling. Our main contributions draw the boundary between possibility and impossibility. First, regarding temporal fair division without scheduling, we prove that while constant-factor $α$-TEFX is impossible in general, a $1/2$-approximation is achievable for generalized binary valuations and identical days with two agents. Second, regarding temporal fair division with scheduling, we demonstrate that a scheduling buffer of size at least $n/2$ enables TEF1 for identical days. However, we establish that TEFX and TMMS remain largely impossible even with scheduling or restricted domains. These results highlight the inherent difficulty of strict temporal fairness and quantify the trade-offs required to achieve approximation guarantees. |
| title | Temporal Fair Division of Indivisible Goods with Scheduling |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2601.12835 |