Sequential Fair Resource Allocation under a Markov Decision Process Framework

The supplier aims to allocate the resource efficiently, i.e., with minimal leftover at the end of horizon $T$, and in a fair manner maximizing NSW. The NSW objective is defined as $\prod_{i=1}^{N}u({A}_{i},\mathbf{X}_{i})^{w_{i}}$, where $w_{i}\in\mathbb{R}_{+}$ reflects the weight assigned to agent $i$ by the supplier. NSW is a balanced compromise between the utilitarian welfare objective, which maximizes the utility of a larger number of agents, and the egalitarian welfare objective, which maximizes the utility of the worst-off agent. Since

the logarithm of NSW is often used as the objective function in allocation problems, such as in the Eisenberg-Gale program Eisenberg and Gale (1959). We refer to this as the log-NSW objective.

In the sequential setting, it is not guaranteed that there always exists an allocation that is simultaneously Pareto-efficient, envy-free, and proportional (Sinclair et al., 2020, Lemma 2.3). Motivated by the properties of the NSW objective in the offline setting, and the fact that our repeated setting can be viewed as multiple draws of the offline setting, we use a modified NSW objective for the sequential setting. Our goal in the sequential setting is to find an allocation that maximizes the log-NSW in expectation. Specifically,

With the goal of measuring the performance of an allocation in the sequential setting, Sinclair et al. (2020) introduces approximate fairness metrics $\Delta\mathbf{A}^{\text{max}}$ and $\Delta\mathbf{A}^{\text{mean}}$. Let $\mathbf{A}_{i}^{\text{online}}$ denote the allocation vector of agent $i$ given by an online algorithm subject to latent demands, and let $\mathbf{A}_{i}^{\text{hindsight}}$ denote the allocation vector in hindsight after all demands are revealed, defined as (13) in Sec. 3. The expected difference between the overall allocations for each agent can be used to measure the fairness of the online algorithm. Let $\Delta A_{i}\coloneqq\Big{|}\sum_{t=1}^{T}{A}_{i}^{t,\text{hindsight}}-\sum_{t=1}^{T}{A}_{i}^{t,\text{online}}\Big{|}$. Then,

are concerned with the worst-off agent and average agent in terms of cumulative allocations in hindsight, respectively¹¹1$\Delta\mathbf{A}$ is defined for the additive utility function in (1), and may need to be redefined for alternative utilities.. While our optimization objective is not to minimize $\Delta\mathbf{A}^{\text{max}}$ or $\Delta\mathbf{A}^{\text{mean}}$, we use these metrics to evaluate the fairness of online allocation algorithms in the experiments in Sec. 6.

Determining the optimal allocations under the NSW objective is a sequential decision-making problem as the allocation in one step affects the budget and allocations in future steps. We formulate the problem as a finite-horizon total-reward Markov Decision Process (MDP) modeled as a tuple $<\{\mathcal{S}_{t},\mathcal{A}_{t},P_{t},R_{t}\}_{t=1,\dots,T}>$. $\mathcal{S}_{t}$ denotes the underlying time-dependent state space, $\mathcal{A}_{t}$ is the action space, $P_{t}:\mathcal{S}_{t}\times\mathcal{A}_{t}\times\mathcal{S}_{t+1}\rightarrow\mathbb{R}_{\geq 0}$ describes the state transition dynamics conditioned upon the previous state and action, $R_{t}:\mathcal{S}_{t}\times\mathcal{A}_{t}\rightarrow\mathbb{R}_{\geq 0}$ is a non-negative reward function, and $T$ is the horizon over which the resource is allocated. The goal of the supplier is to find an allocation policy $\pi=\{\pi_{1},\dots,\pi_{T}\mid\pi_{t}:\mathcal{S}_{t}\rightarrow\mathcal{A}_{t}\}$ mapping the state to an action, in order to maximize the expected sum of rewards $\mathbb{E}[\sum_{t=1}^{T}R_{t}(s_{t},\pi_{t}(s_{t}))]$. Next, we describe the components of the MDP in details.

SAFFE is based on the simple principle of substituting unobserved future requests with their expectations. By doing so, we convert the sequential decision-making problem into solving the offline problem at each time step. With the algorithm formally stated in Algorithm 2, at time step $t$ we use the expected future demands to determine the total resources we expect to allocate to each agent by time $T$. This allows us to reserve a portion of the available budget for future demands. Specifically, at $t=1,\dots,T$, we solve the following problem

The indicator function $\mathbbm{1}\{{Y}_{i}^{t}>0\}$ ensures that we do not consider absent agents, i.e., those with no current or expected future demands⁴⁴4With a slight abuse of notation, in the objective function, we assume $0\times-\infty=0$ to ensure that an agent without demand is not included, and gets no allocation.. ${C}_{i}^{t}$ denotes the total allocation for agent $i$ over the period $t,\dots,T$, if the future demands would arrive exactly as their expectations. In other words, ${C}_{i}^{t}$ consists of the allocation in the current time step and the reserved allocations for the future. Then, the current allocation $A_{i}^{t}$ is a fraction of $C_{i}^{t}$ computed as

Similar to the hindsight problem (12), we can efficiently solve (14) using a variant of the water-filling algorithm given in Algorithm 3 in Appendix C. As illustrated in Fig. 1(b), at time step $t$, the water-level $\mu_{t}$ is calculated while accounting for all previous agent allocations and all expected future demands.

While SAFFE is simple and easy to interpret, it is sub-optimal. In fact, SAFFE maximizes an upper bound of the optimal Q-values of the MDP defined in Sec. 2.2. This implies that SAFFE overestimates the expected reward gain from the future and reserves the budget excessively for future demands. To correct the over-reservation, we propose SAFFE-Discounted (SAFFE-D), which penalizes uncertain future requests by their standard deviations. At every step $t$, the algorithm computes

for some regularization parameter $\lambda\geq 0$ and solves (14). As in SAFFE, the current allocation $A_{i}^{t}$ is split proportionally from $C_{i}^{t}$ according to (16). The regularizer $\lambda$ is a hyper-parameter that can be tuned to provide the optimal trade-off between consuming too much of the budget at the current step and reserving too much for the future. We show in Appendix D, the uncertainty in future demands reduces as we approach $T$, and we expect better performance with a decreasing time-dependent function such as $\lambda(t)=\sqrt{T-t}\,\lambda$ for some $\lambda>0$. Alternatively, $\lambda(t)$ can be learned as a function of time.

In Fig. 2(a), we compare SAFEE-D with the baselines as the supplier’s budget increases from $0.1$ to $1$. We consider the Symmetric setting with $N=50$ agents and $2$ expected arrivals over horizon $T=40$. We observe that SAFFE-D outperforms all other approaches in terms of both $\Delta$Log-NSW and resource utilization across all budgets. The advantage of SAFFE-D in comparison to other algorithms is that it prevents over-reserving for the future, and thus achieves higher utilization and lower $\Delta$Log-NSW. In contrast, SAFFE does not impose the regularization term which potentially results in overestimating future demands. Hope-Guardrail is designed to find a balance between utilization and envy, which does not necessarily mean balance in terms of Log-NSW. Additional experiments showing how the performance of the algorithms scale with the number of agents $N$, time horizon $T$ and the per-agent expected arrivals are provided in Appendix K.1. The results suggest that SAFFE-D, although suboptimal, performs close to Hindsight.

We investigate whether SAFFE-D allocates to agents differently based on their arrival or demand patterns. We consider $N=50$ agents with $2$ expected arrivals over the horizon $T=40$, and Normal demands with $\mu_{i}=50$, and budget size $0.5$. Under the Non-symmetric Arrivals setting, we compare the agents’ allocations for each algorithm with respect to the Hindsight allocations in Fig. 3. In this setting, agents have different likelihoods of arriving over the horizon. We observe that despite being optimized for the log-NSW objective, SAFFE-D outperforms all other algorithms on average, and is more uniform across the three groups compared to SAFFE and Guarded-HOPE which favor the Ask-Late agents. In terms of the worst-case agent, SAFFE outperforms all other methods and has similar $\Delta\mathbf{A}^{max}$ across all three groups. The algorithms are compared under the Non-symmetric Demands setting in Appendix K.2.

We investigate how sensitive the algorithms are to estimation errors by scaling each agent’s mean estimate at each step as $\widehat{\mu}_{i}^{t}=(1+\delta)\mu_{i}^{t}$, where $\delta$ denotes the noise level. Fig. 2(b) shows the change in performance as we vary the noise level $\delta$ from $-0.5$ to $0.5$, for the Symmetric setting with $N=50$ agents, $2$ expected per-agent arrivals, $T=40$, and budget $0.5$. We observe that SAFFE-D is robust to mean estimation noise while all other algorithms are impacted. This results from the discounting term in SAFFE-D, for which the hyper-parameter $\lambda$ can be tuned to the estimation errors. However, when over-estimating the future demands, SAFFE and other methods will be initially more conservative which can lead to lower utilization and less fair allocations due to the leftover budget. When under-estimating the expected demands, they use the budget more greedily earlier on and deplete the budget sooner, resulting in less allocations to agents arriving later (especially in Gaurded-HOPE).

The discounting term in SAFFE-D uses the confidence in estimates to improve the performance of SAFFE by balancing the budget between allocating now vs reserving for future arrivals. In Table 1, we compare the performance of SAFFE-D when using different discounting functions, i.e., constant or decreasing $\lambda$ over the horizon. In both cases, the parameter is tuned to maximize Log-NSW. As expected from Sec. 4.2, the performance of SAFFE-D improves for $\lambda(t)$ decreasing over time. This is because the uncertainty in expected future demands reduces and the supplier can be less conservative when making allocation decisions.

We investigate learning an allocation strategy using RL under the Symmetric setting. We train the RL allocation policy without access to any demand distribution information (e.g., expectation). We consider $N=10$ agents, $T=10$ and varying budget size sampled from $\text{Uniform}(0.4,0.8)$. We use the Soft Actor-Critic (SAC) Haarnoja et al. (2018a); Achiam (2018) method with automatic entropy tuning Haarnoja et al. (2018b) to learn a policy (See Appendix L). The results averaged over $200$ experiment rollouts for five random seeds are reported in Table 2, for two cases where we expect to have $2$ and $4$ per-agent arrivals. We observe that while the RL policy is not able to match the hindsight performance, it outperforms SAFFE-D and other approaches in terms of Log-NSW under sparse ($2$ per-agent) arrivals. With denser ($4$ per-agent) arrivals, the RL policy performs slightly worse than SAFFE-D while still outperforming others. These observations are in line with other experiments illustrating the close-to-optimal performance of SAFFE-D especially in settings with more arrivals.

In contrast to the demand processes considered in previous experiments, in this case, we need to estimate the expected demands and their standard deviations. The efficiency and fairness metrics are reported in Table 3 for budget size $0.5$. We observe that SAFFE-D is optimal, and SAFFE and HOPE-Online perform very close to Hindsight in terms of Utilization and Log-NSW. As shown in Fig. 4(c) in Appendix K.1, we expect that SAFFE-D achieves (close to) hindsight performance for dense agent arrivals as with the daily arrivals in this setting. In order to investigate less dense scenarios, we impose sparsity in the arrivals by erasing each arrival with probability $p$. As observed in Table 3, SAFFE-D is no longer optimal but outperforms all other methods. Additional results are provided in Appendix K.3.