Sequential Fair Allocation of Limited Resources under Stochastic Demands


Sinclair SR, Jain G, Banerjee S, Yu CL. Sequential Fair Allocation of Limited Resources under Stochastic Demands, in AI for Social Good Workshop. ; 2020.


Our work here is motivated by a problem faced by our lo- cal food-bank (Food Bank for the Southern Tier of New York (FBST)) in operating their mobile food pantry program. Every day, FBST uses a truck to deliver food supplies directly to distribution sites (soup kitchens/pantries/etc.). When the truck arrives at a site, the operator observes the demand there and chooses how much to allocate before moving to the next site. The number of people assembling at each site changes from day to day, and the operator typically does not know the demand of later sites (but has a sense of the demand distribution based on previous visits). Finally, the amount of food in the truck is usually insufficient to meet the total demand, and so the operator must under-allocate at each site, while trying to be fair across all sites. The question is: What is a fair allocation here, and how can it be computed? In offline problems, where demands (more generally, utility functions) for all agents are known to the principal, there are many well-studied notions of fair allocation of limited re- sources. A relevant notion in our context is that a fair allocation is one satisfying two desiderata: pareto-efficiency (for any agent to benefit, another must be hurt) and envy-freeness (no agent prefers an allocation received by another). This definition draws its importance from the fact that in many al- location settings, it is both known to be achievable, and also to encompass other natural desiderata (in particular, proportionality, wherein each agent’s utility is at least that achieved under equal allocation). In particular, when goods are divisible, then for a large class of utility functions, an allocation satisfying both is easily computed (via a convex optimization program) by maximizing the Nash Social Welfare (NSW) objective subject to allocation constraints. Many settings, much like the FBST operating their mo- bile food pantry, have principals make decisions online, with incomplete knowledge on the demands for agents to come. However, these principals have access to historical data al- lowing them to generate demand histograms for each agent. Designing allocation algorithms in this setting necessitates utilizing the Bayesian information of the demand distribution to ensure equitable access to the resource, while adapting to the online realization of demands as it unfolds. Guaranteeing pareto-efficiency and envy-freeness simultaneously is impossible in this setting. However, it is important to develop algorithms which achieve probabilistic version of fairness by utilizing the distributional knowledge to develop algorithms that are approximately fair.

Back to AI for Social Good event

Last updated on 07/01/2021