Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909617755258880 |
|---|---|
| author | Halpern, Daniel Psomas, Alexandros Verma, Paritosh Xie, Daniel |
| author_facet | Halpern, Daniel Psomas, Alexandros Verma, Paritosh Xie, Daniel |
| contents | We consider the fundamental problem of allocating $T$ indivisible items that arrive over time to $n$ agents with additive preferences, with the goal of minimizing envy. This problem is tightly connected to online multicolor discrepancy: vectors $v_1, \dots, v_T \in \mathbb{R}^d$ with $\| v_i \|_2 \leq 1$ arrive over time and must be, immediately and irrevocably, assigned to one of $n$ colors to minimize $\max_{i,j \in [n]} \| \sum_{v \in S_i} v - \sum_{v \in S_j} v \|_{\infty}$ at each step, where $S_\ell$ is the set of vectors that are assigned color $\ell$. The special case of $n = 2$ is called online vector balancing. Any bound for multicolor discrepancy implies the same bound for envy minimization. Against an adaptive adversary, both problems have the same optimal bound, $Θ(\sqrt{T})$, but whether this holds for weaker adversaries is unknown.
Against an oblivious adversary, Alweiss et al. give a $O(\log T)$ bound, with high probability, for multicolor discrepancy. Kulkarni et al. improve this to $O(\sqrt{\log T})$ for vector balancing and give a matching lower bound. Whether a $O(\sqrt{\log T})$ bound holds for multicolor discrepancy remains open. These results imply the best-known upper bounds for envy minimization (for an oblivious adversary) for $n$ and two agents, respectively; whether better bounds exist is open.
In this paper, we resolve all aforementioned open problems. We prove that online envy minimization and multicolor discrepancy are equivalent against an oblivious adversary: we give a $O(\sqrt{\log T})$ upper bound for multicolor discrepancy, and a $Ω(\sqrt{\log T})$ lower bound for envy minimization. For a weaker, i.i.d. adversary, we prove a separation: For online vector balancing, we give a $Ω\left(\sqrt{\frac{\log T}{\log \log T}}\right)$ lower bound, while for envy minimization, we give an algorithm that guarantees a constant upper bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14624 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations Halpern, Daniel Psomas, Alexandros Verma, Paritosh Xie, Daniel Computer Science and Game Theory Data Structures and Algorithms We consider the fundamental problem of allocating $T$ indivisible items that arrive over time to $n$ agents with additive preferences, with the goal of minimizing envy. This problem is tightly connected to online multicolor discrepancy: vectors $v_1, \dots, v_T \in \mathbb{R}^d$ with $\| v_i \|_2 \leq 1$ arrive over time and must be, immediately and irrevocably, assigned to one of $n$ colors to minimize $\max_{i,j \in [n]} \| \sum_{v \in S_i} v - \sum_{v \in S_j} v \|_{\infty}$ at each step, where $S_\ell$ is the set of vectors that are assigned color $\ell$. The special case of $n = 2$ is called online vector balancing. Any bound for multicolor discrepancy implies the same bound for envy minimization. Against an adaptive adversary, both problems have the same optimal bound, $Θ(\sqrt{T})$, but whether this holds for weaker adversaries is unknown. Against an oblivious adversary, Alweiss et al. give a $O(\log T)$ bound, with high probability, for multicolor discrepancy. Kulkarni et al. improve this to $O(\sqrt{\log T})$ for vector balancing and give a matching lower bound. Whether a $O(\sqrt{\log T})$ bound holds for multicolor discrepancy remains open. These results imply the best-known upper bounds for envy minimization (for an oblivious adversary) for $n$ and two agents, respectively; whether better bounds exist is open. In this paper, we resolve all aforementioned open problems. We prove that online envy minimization and multicolor discrepancy are equivalent against an oblivious adversary: we give a $O(\sqrt{\log T})$ upper bound for multicolor discrepancy, and a $Ω(\sqrt{\log T})$ lower bound for envy minimization. For a weaker, i.i.d. adversary, we prove a separation: For online vector balancing, we give a $Ω\left(\sqrt{\frac{\log T}{\log \log T}}\right)$ lower bound, while for envy minimization, we give an algorithm that guarantees a constant upper bound. |
| title | Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.14624 |