Online Fair Allocation of Uncertain Supply to Flexible Agents

We study the fair allocation of a divisible resource such as electricity, whose supply is revealed over time, among agents who each need a certain amount within a window of consecutive periods. While envy-freeness and maximum welfare are compatible when the supply is known in advance, and maximum welfare is achievable online when fairness is not required, we show that the best competitive ratio of envy-free online algorithms is exactly 1-1/e with equal demands and 1/2 in general; the latter improves to 1-1/e if envy is measured relative to demands. This ratio depends precisely on the flexibility of the agents: it is 1 when all agents share a deadline and, with equal demands, 1-(1-1/K)^K when all agents start together and there are K distinct deadlines. Moreover, making agents more flexible can reduce the welfare achievable under envy-freeness by a factor approaching 1-1/e without benefiting anyone, and with equal demands, among agents who start together, those with earlier deadlines are never better off. On the positive side, splitting the supply of each period equally is strategyproof and attains the best possible ratio both for general demands and for equal demands with windows of at most two periods. Simulations of household electricity use illustrate our findings.