2025/02/20 by Daniel Halpern, Halpern, Daniel, Alexandros Psomas +5 · 2 citations
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face recognition and analysis
paper · pdf · doi:10.48550/arxiv.2502.14624
openalex publication_date 2025/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 v1, …, vT ∈ ℝd with ‖ vi ‖2 ≤ 1 arrive over time and must be, immediately and irrevocably, assigned to one of n colors to minimize maxi,j ∈ [n] ‖ ∑v ∈ Si v - ∑v ∈ Sj v ‖∞ at each step, where S_ℓ is the set of vectors that are assigned color ℓ. 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, Θ(√(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(√(log T)) for vector balancing and give a matching lower bound. Whether a O(√(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(√(log T)) upper bound for multicolor discrepancy, and a Ω(√(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 Ω(√((log T)/(log log T))) lower bound, while for envy minimization, we give an algorithm that guarantees a constant upper bound.