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

Pooja Kulkarni, Ruta Mehta, Vishnu V. Narayan, Tomasz PonitkaarXiv 2025 · DOI · arXiv

Abstract

This paper investigates the feasibility and cost of maintaining envy-free allocations in an online setting where items arrive sequentially and subsidies are used to compensate agents. We characterize the conditions under which envy-freeness can be maintained across various valuation classes, including additive, submodular, and $k$-demand valuations. Our results reveal a significant "online tax," where the required subsidy in the online setting often scales linearly with the number of items, contrasting with the bounded subsidies possible in offline scenarios. We provide a comprehensive map of valuation classes that allow for online envy-freeness and identify those where the subsidy remains independent of the item count.

Introduction

Fair division is a fundamental problem in resource allocation, aiming to distribute items among agents such that no agent envies another's bundle—a condition known as envy-freeness (EF). When items are indivisible, EF allocations may not exist. To address this, researchers introduce subsidies (monetary payments) to achieve fairness. While previous literature has extensively studied the offline setting where all items are known in advance, this paper explores the online setting: items arrive one by one and must be allocated immediately and irrevocably.

The research focuses on two primary questions:

  1. Existence: For which valuation classes can envy-freeness be maintained as items arrive?
  2. Cost: What is the subsidy required to ensure fairness, and how does it scale with the number of items?

Methodology

The authors establish that an allocation can be made envy-free with subsidies if and only if it is locally efficient (LE). An allocation is LE if no simple swap or reassignment of existing bundles can increase the total social welfare.

To analyze these properties, the study employs:

  • Envy Graphs: Directed graphs where nodes represent agents and edge weights denote the degree of envy. The minimum required subsidy is derived from the "heaviest paths" in these graphs.
  • Adversarial Constructions: Used to prove impossibility results by designing item sequences that force any online algorithm to lose local efficiency.
  • Greedy Algorithms: Developed for positive results to assign items in a way that preserves LE at every step, often by maintaining specific invariants like sorted bundle values.

The analysis covers several valuation classes, ranging from simple Additive valuations to more complex Submodular, Supermodular, and k-Demand preferences.

Key Results and Insights

The paper provides a comprehensive classification of which valuation types allow for online envy-freeness and the magnitude of the resulting "online tax."

The Welfare-Efficiency Gap and the Online Tax

A key finding is the separation between welfare maximization and local efficiency. For additive valuations, maximizing social welfare online maintains LE. However, for $k$-demand valuations, maximizing welfare online is impossible, yet local efficiency (and thus EF with subsidies) can still be maintained.

Furthermore, the authors identify a significant "online tax." In offline settings, a subsidy of $O(n)$ (where $n$ is the number of agents) suffices for additive valuations. In the online setting, the required subsidy jumps to $\Omega(mn)$, scaling with the number of items $m$.

Mapping Fairness Online

The results are summarized in the following table, which delineates the boundaries of online fair division.

Summary of results for online envy-freeness across different valuation classes.

As shown in the table, envy-freeness can be maintained for Additive, SPLC, and $k$-Demand valuations. Conversely, it is mathematically impossible for more complex classes like Budget-Additive, Submodular, or Supermodular valuations, even with binary marginals.

Small Subsidy Bounds

For certain structured classes, the authors show that the subsidy can remain "small" (independent of $m$):

  • Rank-One and Restricted Additive: $O(n^2)$ total subsidy.
  • Identical Monotone: $O(n)$ total subsidy.
  • k-Demand: $O(kn)$ total subsidy.

Discussion and Future Work

While this work provides a detailed map of online fairness, several avenues remain open. The bounds for "personalized $k$-valued" valuations are likely not tight, presenting an opportunity for refinement. Additionally, while the paper delineates several classes, a single unifying property that determines whether a valuation class allows for online local efficiency has yet to be identified. Finally, extending these results to "chore division" (allocating items with negative value) involves different subsidy dynamics that warrant further investigation.

Summary updated

Abstract

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: 1. 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 and SPLC valuations. 2. 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.
BibTeX
@misc{kulkarni2025online,
  author = {Pooja Kulkarni and Ruta Mehta and Vishnu V. Narayan and Tomasz Ponitka},
  title = {{Online Fair Division With Subsidy: When Do Envy-Free Allocations Exist, and at What Cost?}},
  year = {2025},
  eprint = {2510.13633},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.13633},
}
Figure