Online Fair Division With Subsidy: When Do Envy-Free Allocations Exist, and at What Cost?

We study the problem of fairly allocating m indivisible items arriving online, among n (offline) agents. Although envy-freeness has emerged as the archetypal fairness notion, envy-free (EF) allocations need not exist with indivisible items. To bypass this, a prominent line of research demonstrates that there exist allocations that can be made envy-free by allowing a subsidy. Extensive work in the offline setting has focused on finding such envy-freeable allocations with bounded subsidy. We extend this literature to an online setting where items arrive one at a time and must be immediately and irrevocably allocated. Our contributions are two-fold: ·Maintaining EF Online: We show that envy-freeability cannot always be preserved online when the valuations are submodular or supermodular, even with binary marginals. In contrast, we design online algorithms that maintain envy-freeability at every step for the class of additive valuations, and for its superclasses including k-demand valuations and SPLC valuations.·Ensuring Low Subsidy: We investigate the quantity of subsidy required to guarantee envy-freeness online. Surprisingly, even for additive valuations, the minimum subsidy may be as large as Ω(mn), in contrast to the offline setting, where the bound is O(n). On the positive side, we identify valuation classes where the minimum subsidy is small (i.e., does not depend on m), including k-valued, rank-one, restricted additive, and identical valuations, and we obtain (mostly) tight subsidy bounds for these classes.