2021/11/14 by Yasushi Kawase, Kawase, Yasushi, Hanna Sumita +1
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2111.07235
openalex publication_date 2021/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study an online version of the max-min fair allocation problem for indivisible items. In this problem, items arrive one by one, and each item must be allocated irrevocably on arrival to one of n agents, who have additive valuations for the items. Our goal is to make the least happy agent as happy as possible. In research on the topic of online allocation, this is a fundamental and natural problem. Our main result is to reveal the asymptotic competitive ratios of the problem for both the adversarial and i.i.d. input models. We design a polynomial-time deterministic algorithm that is asymptotically 1/n-competitive for the adversarial model, and we show that this guarantee is optimal. To this end, we present a randomized algorithm with the same competitive ratio first and then derandomize it. A natural derandomization fails to achieve the competitive ratio of 1/n. We instead build the algorithm by introducing a novel technique. When the items are drawn from an unknown identical and independent distribution, we construct a simple polynomial-time deterministic algorithm that outputs a nearly optimal allocation. We analyze the strict competitive ratio and show almost tight bounds for the solution. We further mention some implications of our results on variants of the problem.