  We consider the problem of dividing limited resources between a set of agents
arriving sequentially with unknown (stochastic) utilities. Our goal is to find
a fair allocation - one that is simultaneously Pareto-efficient and envy-free.
When all utilities are known upfront, the above desiderata are simultaneously
achievable (and efficiently computable) for a large class of utility functions.
In a sequential setting, however, no policy can guarantee these desiderata
simultaneously for all possible utility realizations. A natural online fair
allocation objective is to minimize the deviation of each agent's final
allocation from their fair allocation in hindsight. This translates into
simultaneous guarantees for both Pareto-efficiency and envy-freeness. However,
the resulting dynamic program has state-space which is exponential in the
number of agents. We propose a simple policy, HopeOnline, that instead aims to
`match' the ex-post fair allocation vector using the current available
resources and `predicted' histogram of future utilities. We demonstrate the
effectiveness of our policy compared to other heurstics on a dataset inspired
by mobile food-bank allocations.
