Online Fair Allocation of Perishable Resources

A team of researchers from Cornell University has tackled a critical optimization problem in resource distribution with their paper 'Online Fair Allocation of Perishable Resources.' The work addresses a scenario where a decision-maker must allocate a budget of resources that expire (like food, vaccines, or compute credits) over a fixed number of rounds, with a random number of arrivals each round. The goal is to create a sequence of allocations that is both envy-free (no individual prefers another's allocation) and efficient, despite the added complexity of items perishing. The researchers first established strong theoretical lower bounds, proving a decision-maker's capabilities are fundamentally limited compared to a non-perishing setting.

To navigate this constraint, they designed a novel, two-part algorithm. It requires two inputs: a prediction of the order in which resources will perish and a desired upper bound on envy. In each period, the algorithm uses forecasts of future demand and perishing to adaptively choose between two carefully constructed 'guardrail' quantities, balancing immediate fairness with future availability. The paper demonstrates the algorithm's 'strong numerical performance' through simulations calibrated to a real-world dataset, showing it achieves the theoretical lower bounds. Crucially, it highlights the inefficacy of existing state-of-the-art algorithms that ignore perishing, underscoring the necessity of this new approach for practical, time-sensitive allocation systems.