We study online fair allocation of T sequentially arriving items among n agents with heterogeneous preferences, with the objective of maximizing generalized-mean welfare, defined as the p-mean of agents' time-averaged utilities, with p∈(−∞,1). We first consider the i.i.d. arrival model and show that the pure greedy algorithm -- which myopically chooses the welfare-maximizing integral allocation -- achieves O(1/T) average regret. Importantly, in contrast to prior work, our algorithm does not require distributional knowledge and achieves the optimal regret rate using only the online samples. We then go beyond i.i.d. arrivals and investigate a nonstationary model with time-varying independent distributions. In the absence of additional data about the distributions, it is known that every online algorithm must suffer Ω(1) average regret. We show that only a single historical sample from each distribution is sufficient to recover the optimal O(1/T) average regret rate, even in the face of arbitrary non-stationarity. Our algorithms are based on the re-solving paradigm: they assume that the remaining items will be the ones seen historically in those periods and solve the resulting welfare-maximization problem to determine the decision in every period. Finally, we also account for distribution shifts that may distort the fidelity of historical samples and show that the performance of our re-solving algorithms is robust to such shifts.
Figures & tables
Figure 1: Different generalized-mean welfare functions, parametrized by different values of p .
Re-solving program, solved by the algorithm at step t .
Wt−1†
(vt(o),vt+1:T(h)) : the true item t , followed by historical sample
Pt(c),Dt(c)
Coupling program constructed for analysis.
Wt†
vt+1:T(c)={vt+1:T(o),jointly sampled with vt+1:T(o),\lx@crefcreftypecaprefnumsection: re-solve-3,\lx@crefcreftypecaprefnumsec: robust.
Table 3: Re-solving and coupling programs.
Figure 2: Simulations of the greedy algorithm and the re-solving algorithm on the Instagram notification dataset (left) and the MovieLens dataset (right) with the Nash welfare objective (p=0) , under three inputs models: i.i.d. (top) , periodic (middle) , and true temporal (bottom) .
Instagram (n=4)
MovieLens (n=10)
Time per item (ms)
27.6
29.6
Table 4: Time per allocated item of the re-solving algorithm when T=10,000 . Single-thread execution. Device: Intel Core i5-14600KF CPU ( 5.3 GHz) with 32 GB of RAM, under Ubuntu 24.04 with Python 3.12 and NumPy 2.4.
Figure 3: Simulations of infrequent dual re-solving with re-solving interval τ∈{1,10,50,500} on the Instagram notification dataset (left) and the MovieLens dataset (right) with the Nash welfare objective (p=0) , under three inputs models: i.i.d. (top) , periodic (middle) , and true temporal (bottom) . The dashed curve τ=1 is the standard dual re-solving algorithm.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Simulations of the greedy algorithm and the re-solving algorithm on the Instagram notification dataset (left) and the MovieLens dataset (right) with the p=−1 in the objective, under three inputs models: i.i.d. (top) , periodic (middle) , and true temporal (bottom) .
Figure 5: Simulations of the greedy algorithm and the re-solving algorithm on the Instagram notification dataset (left) and the MovieLens dataset (right) with the p=0.5 in the objective, under three inputs models: i.i.d. (top) , periodic (middle) , and true temporal (bottom) .
We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited capacities. We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement, which ensures that similar agents arriving in the same batch receive similar expected outcomes. We first analyze the offline problem, proving that the value of the optimal fair allocation is at least an Ω(1/γ) fraction of the optimal unfair allocation, where γ is the fairness coefficient, thereby bounding the price of fairness. For the online setting, we propose an algorithm based on dual mirror descent that enforces fairness constraints within batches while estimating optimal dual variables. We prove that this algorithm achieves sublinear regret relative to the optimal offline fluid benchmark. Finally, we validate our theoretical results using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and examining the trade-offs between welfare maximization and fairness enforcement.
Christopher En, Yuri Faenza, Andrea Lodi +1
Columbia University, IEOR Department · Cornell Tech · Universidad de Chile
This paper considers a novel variant of the online fair division problem involving multiple agents in which a learner sequentially observes an indivisible item that must be irrevocably allocated to one of the agents to achieve a desired balance between fairness and efficiency. Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs from noisy observed utilities. However, this assumption may not hold in many real-life applications, e.g., an online platform with a large number of users (items) who use the platform's service providers (agents) only a few times (a few copies of items), making it difficult to accurately estimate utilities for all item-agent pairs. To address this limitation, we assume utility is an unknown function of item-agent features. We propose algorithms that model online fair division as a contextual bandit problem and achieve provable sublinear regret. Our experimental results further validate the effectiveness of the proposed algorithms.
Arun Verma, Indrajit Saha, Makoto Yokoo +1
Singapore-MIT Alliance for Research and Technology, Republic of Singapore · Faculty of ISEE, Kyushu University, Japan · Department of Computer Science, National University of Singapore, Republic of Singapore
We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.
Saar Cohen, Nicholas Teh, Paul W. Goldberg +1
Department of Computer Science, University of Oxford, UK