Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations
Daniel Halpern, Alexandros Psomas, Paritosh Verma, Daniel Xie · 2025
Read Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations by Daniel Halpern, Alexandros Psomas, Paritosh Verma, Daniel Xie (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-14624.txt.
Description
Daniel Halpern, Alexandros Psomas, Paritosh Verma, and Daniel Xie settle open questions linking fair division over time with a balancing problem in vector geometry, in a 2025 paper. In the fair division problem, goods arrive one by one and must be handed out at once, keeping envy between agents low. In the geometry twin, vectors arrive and must be colored so the color groups stay close in size.
Any bound for the geometry problem gives the same bound for envy. Against a foe who adapts, both share one best possible answer. What was open is whether this holds against a foe who commits in advance. The authors prove the two problems are fully equivalent in that setting. They give matching upper and lower bounds for the many-color case, closing the gap left by earlier work.
Catalog record
| CREATOR | Daniel Halpern, Alexandros Psomas, Paritosh Verma, Daniel Xie |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 131 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-14624