Evaluating Fairness of Sequential Resource Allocation Policies: A Computational Study

We mainly focus on two objectives related to fairness of allocations, which are called ex-ante and ex-post fairness by Manshadi et al. [3]. For the ex-post objective, the aim is to maximize the expected minimum fill rate of all clients, i.e., maximize

In contrast to maximizing the expected minimum fill rate, ex-ante fairness maximizes the minimum expected fill rate of all clients, i.e.,

When only a single allocation run is performed, only one realization of the demands is observed. Then, the ex-post objective (2) may be the most appropriate objective, as this ensures that for this single realization the minimum fill rate is maximum, in expectation. However, when allocations are repeated, then (2) may yield too conservative allocations while higher fill rates can be achieved. In this case, ex-ante fairness (3) may be more desirable to achieve, both from the perspective of the policy designer, as well as from the perspective of the client, as their expected fill rate over the repeated allocations is maximized. The existing methods in the literature focus mainly on ex-post fairness. In the computational analysis that we perform in Section 4, we will evaluate the existing policies as well as our new policy on both the ex-post and ex-ante fairness objectives.

Given full knowledge of the demand distributions of the clients, a policy that maximizes the expected minimum fill rate, i.e., ex-post fairness, can be described by the following recursive relation from Lien et al. [2]. Let $Z^i(s_i,{\phi }_{i-1}^{\text{min}},d_i)$ denote the maximum expected minimum fill rate for visiting all clients $1,\mathrm{\dots },n$, given that the visited clients $1,\mathrm{\dots },i-1$ have a minimum fill rate ${\phi }_{i-1}^{\text{min}}$ and supply $s_i$ is remaining when arriving at client $i$ with demand $d_i$. The optimal allocation policy can then be determined by solving the following optimality equation, for any $i\in [n-1]$:

For the last node $n$ in the sequence, we have

Then, the optimum expected minimum fill rate over the full sequence is given by

This can be solved by dynamic programming, starting at the last client in the sequence working in reverse order to the first client, filling a table $Z$ with entries $Z^i(s_i,{\phi }_{i-1}^{\text{min}},d_i)$ for every $i\in [n]$, $s_i\in [s]$, $d_i$ in the support of $D_i$, and every possible fill rate ${\phi }_{i-1}^{\text{min}}$.

To apply this policy, the full table needs to be retained to look up the allocation for every client during the allocation process, using the current history of allocations to previous clients. In addition, it is necessary that the demand distribution as well as the allocations are discrete, and the magnitude of the demand and supply levels directly influence the time and space needed to compute the optimal policy. The amount of space needed to store the table is of order $𝒪(n\cdot s\cdot {\mathrm{\ell }}^3\cdot D_{\text{max}})$, while the computational time is $𝒪(n\cdot s\cdot {\mathrm{\ell }}^3\cdot D_{\text{max}}^2)$, where $\mathrm{\ell }$ is (maximum) number of demand levels of a client and $D_{\text{max}}$ is the maximum demand of any client. In many cases, these complexities (in particular the space complexit) are so high that the optimal policy can only be computed for small instances. Because of this, several alternative policies are proposed that sacrifice optimality for improved time and space complexity.

An alternative approach to designing a policy for the SRA problem is as follows. When arriving at client $i$, we design a policy that maximizes the minimum fill rate of the clients $i,\mathrm{\dots },n$, i.e., we do not take the fill rates of the already visited clients $1,\mathrm{\dots },i-1$ into account. This is also called the forward objective. The problem where the forward objective is maximized can be solved optimally using a similar approach as for finding the optimal expected minimum fill rate in Section 3.1. When arriving at a client, the policy optimizing the forward objective maximizes the expected fill rate over the current and future clients, i.e., the fill rates of the already visited clients is not taken into consideration. The optimality equation is, for $i=1,\mathrm{\dots },n-1$

with for the last node $n$ in the sequence

This can also be solved by dynamic programming, where the table entries of $Z_f$ are filled in reverse client order. Since the minimum fill rate for the previous clients is no longer a parameter, this table can be stored in $𝒪(n\cdot s\cdot \mathrm{\ell }\cdot D_{\text{max}})$ and filled in $𝒪(n\cdot s\cdot \mathrm{\ell }\cdot D_{\text{max}}^2)$ time. Compared to the policy in Section 3.1, this policy requires significantly less time and space.

The two-node decomposition (TND) heuristic as proposed in the literature by Lien et al. [2] is designed to maximize the expected minimum fill rate. At every client $i\in [n]$, the allocation is heuristically determined in two steps. First, the available supply is split in an allotment ${\widehat{s}}_i$ that is available to solve the allocation problem for the current and next client in the sequence, while the remaining supply is reserved for clients further in the sequence. The allotment is proportional to the mean demand of the first two clients in the sequence relative to the total mean demand of all unvisited clients, i.e.

Second, the allotment is then used to determine an allocation for client $i$, based on its observed demand $d_i$ and the distributional knowledge of the demand of client $i+1$. The allocation is equal to

where ${\widehat{H}}_i({\widehat{s}}_i,d_i)$ is an approximation of the optimal allocation in case there would only be two clients $i$ and $i+1$ left. It is defined as

with

where ${\tilde{m}}_i$ and ${\sigma }_i$ denote the median and standard deviation of the demand of client $i$, respectively. For the last client $n$ in the sequence, the allocation is simply $x_n=\min \{s_n,d_n\}$. For more details, we refer to the original paper of Lien et al. [2].

Manshadi et al. [3] introduce the projected proportional allocation (PPA) heuristic. This policy is designed to maximize ex-post fairness, and is based on the following idea. Suppose that in an offline variant of the problem all demand realizations of all clients are known a-priori. Then, the optimal (offline) allocation for every client $i$ is

In the online setting, the future demand is unknown. The PPA allocation rule substitutes the mean future demand as a heuristic policy, allocating

In this work, we introduce a new, alternative, allocation policy using an LP-based approach. The objective is to maximize ex-post fairness by maximizing the expected minimum fill rate. The policy pre-assigns a single allocation value for each client, in order to keep the policy compact. This can be modeled with the following program:

Here, $p_{d_1,\mathrm{\dots },d_n}$ is the probability that the scenario occurs that the $n$ clients realize the demands $d_1,\mathrm{\dots },d_n$. Note that the objective (as a sum of minima) is a concave function. It can be modeled as a linear program, by introducing variables $f_{d_1,\mathrm{\dots },d_n}$ for every “demand scenario” that corresponds to each term in the objective. This yields the LP

Note that the number of variables depends largely on the number of scenarios, which can be large when the number of clients and/or the number of demand realizations of the clients is large. This is also the case for the optimal dynamic programming model. However, this model can handle continuous allocations, i.e., allocations that are not limited to a discrete set of values, and furthermore it is not sensitive to the magnitude of supply and demand values. More importantly, this policy can incorporate group fairness. Indeed, when clients with identical demand distributions are regarded as groups, this policy will allocate the same amount of resource to each client in a group. Thus, there is an optimal solution to this model where all clients from the same group will have an identical allocations.

An informal argument for this property is as follows. Suppose that there is an optimal solution $x$ where two clients $i,j\in [n]$ with the same demand distribution have different allocations in an optimal solution. Without loss of generality, assume that $x_i>x_j$. Then, we can construct another solution $x^{\prime }$ where $x_i^{\prime }=x_j^{\prime }=x_j$, and $x_k^{\prime }=x_k$ for all $k\in [n]$, $k\ne i$ and $k\ne j$ which will have the same objective value, as the minimum fill rate will be identical for allocation $x$ and $x^{\prime }$ in any demand realization. This allows for aggregation of these clients in the model, ensuring faster computation times.

Suppose there are $m$ groups (or types) of clients ${\theta }_1,\mathrm{\dots },{\theta }_m$ with $n_1,\mathrm{\dots },n_m$ number of clients, respectively. Then the aggregated model is as follows.

This makes the model significantly smaller when the number of groups is small, achieving group fairness efficiently.

In addition, the allocation procedure is now simple: there is a single predetermined allocation for every client, which is not only easily implemented when allocations take place, but it is also explainable and easily communicated to clients.

The policy introduced in Section 3.5 can also be used as an adaptive policy by re-computing the LP for the future clients after observing the demand of the current client. Thus, after arriving at client $i$, the observed demand is $d_i$ and the LP model is now adapted to only include the current client with a deterministic demand $d_i$ and all future clients with their demand distribution, with the remaining supply $s_i$. The new solution yields an allocation $x_i$ for the current client. Upon visiting the next client, the model is re-computed analogously.

The adaptive nature of this policy makes it more comparable to the other existing policies, which are all also adaptive in nature. Note that this policy also violates group fairness. This policy is expected to score higher on ex-ante individual fairness, as it can account for uncertainty in the demand realizations throughout the client sequence. Furthermore, it requires solving a linear program throughout the allocation process.

We follow the general structure of generated instances used by Lien et al. [2]. We generate instances with the following parameters.

• $\mathrm{■}$

  The number of groups of clients of identical demand distribution is an element of $\{2,3,4\}$.

• $\mathrm{■}$

  The total number of clients $n$, which is either small or large. Small instances have a total number of clients of $14$, $15$, and $16$ for $2$, $3$, and $4$ groups of identical clients, respectively. Large instances have $20$ clients for $2$ and $4$ groups, and $21$ clients for $3$ groups.

• $\mathrm{■}$

  The ordering of the groups of clients is specified under the Sequences column in Table 1. The symbol ${\text{CV}}^{\nearrow }$ (${\text{CV}}^{\searrow }$, ${\text{CV}}^{\sim }$) refers to a setting where the coefficient of variation (CV) is uniformly increasing (decreasing, alternating) with the position of the clients in the sequence. A similar explanation applies to ${\mu }^{\nearrow }$, ${\mu }^{\searrow }$, ${\mu }^{\sim }$. The coefficient of variation is defined as the ratio of the standard deviation $\sigma$ to the mean $\mu$, i.e., $\text{CV}=\sigma /\mu$. For the last two rows, the mean and coefficient of variation are matched as follows: clients with the $k$-th largest $\mu$ have the $k$-th largest CV for any $k$, and vice versa. Each row in Table 1 therefore corresponds to $3$ instances.

• $\mathrm{■}$

  The interleaving of the groups, which is either separated or repeating. For example, in an instance with $9$ clients in 3 groups $a$, $b$, and $c$, the separated interleaving yields the sequence $aaabbbccc$, while the repeating interleaving yields $abcabcabc$.

• $\mathrm{■}$

  The initial supply scarcity $R\in \{0.5,0.75,1,1.25,1.5\}$, which is the fraction of the total expected demand ${\sum }_{i=1}^n{\mu }_i$ that is available as initial supply of the resource.

The total number of instances that follows from this setup equals $3\cdot 2\cdot 30\cdot 2\cdot 5=1800$. For each of these instances, 250 simulations are performed on which every allocation method is evaluated. The demand distributions of all clients follow a discretized gamma distribution with mean ${\mu }_i$ and coefficient of variation CV, of which the domains are specified in Table 1. The number of demand levels, i.e., the size of the support of the demand distribution, is fixed to be $21$.

For the adaptive version of the LP-based method we only evaluate instances with $n=14$ or $n=15$ clients, due to computational limitations.

As our aim is to evaluate the policies with respect to their performance on the two objectives, we choose to not report computation times, but restrict ourselves to the following general comment. As expected, the optimal dynamic programming policy is the most time-intensive policy – an instance with 21 clients takes roughly 2 hours to solve on 24 threads, which is a significant computation time. Furthermore, this policy requires more than 100 GB of memory space to store the dynamic programming table.

We now discuss the performance of the policies on the two objectives. Tables 2 and 3 summarize average scores on the ex-post and ex-ante objectives for the evaluated policies: the optimal dynamic program (Opt), the optimal forward dynamic program (Fw), the two-node decomposition policy (TND), the projected proportional allocation policy (PPA), our non-adaptive LP-based policy (Non-adaptive) and our adaptive LP-based policy (Adaptive). All instances are grouped by supply scarcity , $R=1$, and $R>1$, as well as by the number of clients $n$. The ex-post fairness performance of the TND heuristic and our non-adaptive policy decreases when the number of clients increases, whereas the other policies retain similar performance for different number of clients. Wile our non-adaptive policy clearly does not perform well on the ex-post fairness objective compared to the other policies, it does perform well on the ex-ante fairness objective, especially with supply scarcity where it outperforms all other methods. The adaptive variant of our policy is competitive with the other allocation policies on both ex-post and ex-ante fairness.

Figure 1 shows for all instances $n=21$ clients and supply scarcity $R=0.5$ and $R=1$ the distribution of the fill rate of each client in the sequence. For each policy, a box plot indicates the maximum and minimum fill rate, as well as the quantiles and the average fill rate, indicated by a green line. It can be observed that the methods vary in variance of fill rates allocated, where the optimal dynamic program has the lowest variance when supply is scarce. Our non-adaptive policy achieves a fill rate of $1$ often for any client in the sequence, however with a high variance between allocation runs. It is also clearly visible that, for the optimal dynamic program, the last client in the sequence will in many cases achieve a high fill rate due to conservative allocation decisions for clients earlier in the sequence. Similar plots for instances with a different number of clients, which are omitted due to space limitations, show an identical trend.

To further evaluate the ex-ante individual fairness objective, we analyze the average fill rate of every client in the sequence and take the minimum. To compare the overall performance of the methods, we summarize the results by grouping the problem instances on number of clients and supply scarcity. Figure 2 displays the average fill rate of each client in the sequence for all instances of $n=15$ clients for supply scarcity $R>1$, $R=1$, and , respectively. Although omitted due to space limitations, the results for $n\in \{14,20,21\}$ show an almost identical trend. In situations where supply is not scarce, i.e., when $R\ge 1$, the non-adaptive policy performs significantly worse on ex-ante individual fairness. However, when , which is often the case for applications for this problem, our method significantly outperforms existing methods on ex-ante individual fairness. Moreover, it can be seen that for all adaptive policies that the average fill rate of a client heavily depends on the place of the client in the sequence, whereas our non-adaptive policy achieves a much more equal fill rate for every client in the sequence. From a fairness perspective, the sequencing of customers should not impact their fill rate and our policy may be beneficial in some applications.

Let us now discuss to what extent the order of the clients impacts the allocation. For the ex-post objective, when the supply is scarce (), all policies perform best when the clients are ordered by decreasing coefficient of variation. This confirms the results by Lien et al. [2], and our computational analysis shows that this also extends to instances with significantly more clients. The TND heuristic, however, performs best on instances where the coefficient of variation is constant and small and where the mean demand of the clients decreases in the order of the sequence. When $R\ge 1$, all policies perform best when the coefficient of variation is constant and small, as in this case a fill rate close to $1$ can be achieved for many clients. For the ex-ante objective when , the forward optimal dynamic program and our policies perform best when the coefficient of variation is high for all clients. The PPA heuristic and the optimal dynamic program perform best when the mean demand is decreasing and the coefficient of variation is high. The TND heuristic performs best on the ex-ante objective when the mean demand is decreasing and the coefficient of variation is low for all clients.