Sequential Fair Resource Allocation under a Markov Decision Process Framework

We study the sequential decision-making problem of allocating a divisible resource to agents that reveal their stochastic demands on arrival over a finite horizon. Our goal is to design fair allocation algorithms that exhaust the available resource budget. This is challenging in sequential settings where information on future demands is not available at the time of decision-making. We formulate the problem in the framework of a discrete time Markov decision process (MDP). We propose a new algorithm, SAFFE, that makes fair allocations with respect to all demands revealed over the horizon by accounting for expected future demands at each arrival time. Using the MDP formulation, we show that the allocation made by SAFFE optimizes an upper bound of the Nash Social Welfare fairness objective. We further introduce SAFFE-D, which improves SAFFE by more carefully balancing the trade-off between the current revealed demands and the future potential demands based on the uncertainty in agents’ future demands. We bound its gap to optimality using concentration bounds on total future demands. On synthetic and real data, we compare SAFFE-D against a set of baseline approaches, and show that it leads to more fair and efficient allocations and achieves close-to-optimal performance.