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

CREATORDaniel Halpern, Alexandros Psomas, Paritosh Verma, Daniel Xie
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE131 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-14624

Browse the full library · About the Tower of Babel