REU Project

We study the problem of online fair allocation of indivisible goods when sharing goods among a limited number of agents is permitted. In this problem, the goods arrive sequentially one by one and must be allocated irrevocably before the future good sequence is revealed. Existing literature shows that even under normalized additive valuations (the value of all items for a particular agent is known beforehand), no deterministic online algorithm can avoid an arbitrarily bad maximin share (MMS) approximation for three agents, when each good is allocated to only one agent. We focus on the smallest nontrivial setting of three agents and 2-sharing. First, we show that normalization is necessary: without normalized valuations, no deterministic online algorithm can guarantee any positive constant-factor MMS approximation. Under normalized additive valuations, we present a deterministic online algorithm that guarantees every agent at least a (1-C)-fraction of her MMS, where C is the sharing-cost. Finally, we establish that exact MMS remains impossible for the online 2-sharing setting when C > 1/2, even for normalized identical valuations with three agents.