# equity_promotion_in_online_resource_allocation__b15382e0.pdf

Equity Promotion in Online Resource Allocation

Pan Xu1, Yifan Xu2

1 Department of Computer Science, New Jersey Institute of Technology, Newark, USA 2 Key Lab of CNII, MOE, Southeast University, Nanjing, China pxu@njit.edu, xyf@seu.edu.cn

We consider online resource allocation under a typical nonprofit setting, where limited or even scarce resources are administered by a not-for-profit organization like a government. We focus on the internal-equity by assuming that arriving requesters are homogeneous in terms of their external factors like demands but heterogeneous for their internal attributes like demographics. Specifically, we associate each arriving requester with one or several groups based on their demographics (i.e., race, gender, and age), and we aim to design an equitable distributing strategy such that every group of requesters can receive a fair share of resources proportional to a preset target ratio. We present two LP-based sampling algorithms and investigate them both theoretically (in terms of competitive-ratio analysis) and experimentally based on real COVID-19 vaccination data maintained by the Minnesota Department of Health. Both theoretical and numerical results show that our LP-based sampling strategies can effectively promote equity, especially when the arrival population is disproportionately represented, as observed in the early stage of the COVID-19 vaccine rollout.

Introduction

We consider online resource allocation under a typical nonprofit setting, where limited or even scarce resources are administered by a not-for-profit organization like a government, and our priority is equity such that every type of online agent could receive a fair share of the limited suppliers. Currently, there are two complementary approaches to studying equity in online resource allocation under the nonprofit setting. The first is called external equity, which is to treat arriving requesters as homogeneous in terms of their internal attributes like demographics but heterogeneous with respect to their external factors like demands and arrival time. The focus of equity is then placed on fairness about external factors. A few works investigating external equity in distributing medical suppliers during the COVID-19 pandemic (Manshadi, Niazadeh, and Rodilitz 2021) and allocating food donations to different agencies (Lien, Iravani, and Smilowitz 2014). Specifically, these studies associate each

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

arriving request with a demand, and aim to devise an allocation policy such that every requester can get a fair share of resources proportional to its demand, regardless of their arrival time. The second follows an opposite direction, called internal equity, which is to treat arriving requesters homogeneous in terms of their external factors like demands but heterogeneous for their internal attributes. Under this approach, each requester has been placed into one or several groups, and a distribution of resources is regarded as equitable when every group of requesters can receive a fair share of resources proportional to the percentage of the group in the whole population. In this paper, we focus on internal-equity promotion in online resource allocation. A typical motivating example is COVID-19 vaccine distribution. There is much news showing stark racial disparities existing at least in the early stage of the vaccine rollout across the country (Stolberg 2021; Fitzsimmons 2021; Board 2021; Singer 2021; Blackstock and Blackstock 2021; Jones 2021; Abcarian 2021; Adamson 2021). The article (Fitzsimmons 2021) published on Feb. 8, 2021, in The New York Times showed that In New Jersey, about 48 percent of vaccine recipients were White, and only 3 percent were Black, even though about 15 percent of the state s population is Black, according to state data. Another article (Blackstock and Blackstock 2021) published on Feb. 1, 2021, in The Washington Post reported that White Americans are being vaccinated at rates of up to three times higher than black Americans, though Black Americans have suffered a much higher death rate from COVID-19 than White Americans. These facts highlight the challenge of achieving an equitable distribution of online resources in a non-profit setting, especially when resources are scarce and competed by an overwhelming number of requesters. One technical challenge in addressing (internal) equity promotion in online resource allocation is how to craft a proper metric of equity. Current metrics of equity proposed so far are all based on the minimum ratio of the number of requesters served to that of total arrivals within any given group (Ma, Xu, and Xu 2020; Nanda et al. 2020; Xu and Xu 2020; Hosseini et al. 2022). Unfortunately, these metrics fail to capture the exact equity we expect in practice. Consider COVID-19 vaccine distribution, for example. Among lots of news reporting the sharp racial and ethnic disparities in the early stage of rollout, a commonly cited evidence is

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

the clear gap between the Black/Hispanic share of the vaccinated population and that of a general population or some specific group (like healthcare personnel or long-term care facility residents). This suggests that in an equitable distribution, we expect the inter-serving-ratio of each group in some population as close as possible to a specific preset goal. In contrast, current metrics emphasize the intra-serving-ratio within each group should be as close as possible to each other. Existing metrics all ignore that we typically have a specific target of serving ratio for each protected group, and the overall equity is often based on how small the gap it is between the serving ratio achieved and the target. In light of the above challenge, we propose a model, called Equity Promotion in Online Resource Allocation (EPORA), which features the following three components.

Graph. There is a bipartite graph G = (I, J, E), where I and J denote the set of types for (offline) supply agents and (online) demand agents. Each supply agent (of type) i has a given serving capacity bi Z+, which suggests that agent i can serve up to bi requesters1; each demand agent (of type) j features a certain demographical attributes (e.g., race, gender, age, and ethnicity); an edge e = (i, j) indicates the feasibility of supply agent (of type) i to serve demand agent (of type) j due to practical constraints2. We have a collection of protected groups G = {g} (possibly overlapping), where each group g J represents a certain class of people.

Arrival process of demand agents. We assume each demand agent (of type) j arrives following an independent Poisson process with homogeneous rate λ j > 0, over a time horizon scaled to be [0, 1]. Upon the arrival of a demand agent j, we (as an online algorithm or policy) have to decide immediately and irrevocably either to miss it or assign j to a feasible supply agent i with (i, j) E with remaining serving capacity then.

Equity metrics. For each group g G, we have a target serving ratio µg (0, 1) that is known as input. Consider a given algorithm ALG and for each demand agent j, let Xj be the number of agent j served by ALG and Aj be that of total arrivals of agent j. By assumption, we have E[Aj] = λ j. Let X = P j J Xj and A = P j J Aj denote the total number of all served demand agents and that of all arrives, respectively. Similarly, for each group g, let Xg = P j g Xj and Ag = P j g Aj denote the respective number of demand agent served and that of arrivals in group g. Consider the below two metrics of equity (which we aim to maximize): Relative-serving ratio (RSR): ming G E[Xg] E[X] µg ;

Absolute-serving ratio (ASR): ming G E[Xg] E[A] µg . Note that both RSR and ASR model the gap between the serving ratio achieved the preset target as the relative percentage of the former in the latter. The key difference be-

1Generally, the serving capacity of each supply agent i can be estimated based on the inventory of resources stored at i and the unit demand per requester. 2Examples includes spacial constraints when each supply and demand agent type features a certain location; see our experimental setup for COVID-19 vaccine distribution in Section 7.

tween the two is how to define the serving ratio achieved. In RSA, the ratio is against the expected number of all agents served (E[X]), while in ASR, it is based on that of all arrivals (E[A]).

Justification of parameters {µg}. Observe that previous studies (Ma, Xu, and Xu 2020; Nanda et al. 2020; Xu and Xu 2020) have chosen a fairness metric as ming G E[Xg]/E[Ag], the minimum ratio of the expected number of agents served to that of arrivals among all groups. This can be cast as a special case of ASR by setting each µg = E[Ag]/E[A]. In other words, these previous works assume by default that the preset target serving ratio for each group is equal to its percentage in the arriving population. This setting of {µg} makes sense when each group is perfectly represented in the arriving population. Unfortunately, this doesn t reflect the truth always: disproportionality is indeed observed in practical scenarios like COVID-19 vaccine distribution. Walker et al. (2021) has reported that Black and Hispanic Americans face much more obstacles to vaccine access compared with their White counterparts and as a result, the arriving population requesting vaccines is dominated by White people (at least in the early rollout stage). Let Max-R and Max-A denote the two objectives of maximization of RSR and ASR, respectively. There are several pros and cons associated with each of the above two objectives. Consider a context when resources are limited or scarce and far outnumbered by online requesters. Max R ensures only that the part of resources administered are distributed according to the preset target ratios among all groups. However, it cannot even guarantee all resources will be used up. In fact, a simple policy ALG can fool Max-R by selecting a small portion of the arriving requesters to serve such that the served population has a perfect blend of all group members that are well aligned with the preset ratios. In that case, ALG will achieve an optimal value 1 on Max-R. In contrast, Max-A will probably lead to an exhaustion of all resources. Additionally, Max-A will direct any policy ALG to undo the potential bias in the arriving population as follows: for underrepresented groups (i.e., E[Ag]/E[A] < µg), ALG will try to serve their arriving members as many as possible; for overrepresented groups (i.e., E[Ag]/E[A] > µg), ALG will instead select only a fraction to serve. That being said, the ASR-based Max-A suffers from the disproportionality in the arriving population, which sets boundaries for the power that an optimal policy can exert on pushing the final ASR toward a preset target. In light of the above discussions, we will focus on the objective of Max-A in this paper. Note that in our model, we assume I = {G = (I, J, E), {bi}, {λ j}, G = {g}, {µg}} are all known as the input. We aim to design an algorithm ALG such that the Absolute-serving ratio (ASR) is maximized.

Other related works. There are a few works that have considered online resource allocation in different contexts, see, e.g., allocation of public housing for lower-income families (Benabbou et al. 2018), distribution of emergence aid for natural disasters like wildfires (Wang, Bier, and Sun 2019), task assignment in crowdsourcing platform (Chatterjee et al. 2018; Sumita et al. 2022), online set selection with

fairness and diversity constraints (Stoyanovich, Yang, and Jagadish 2018), online resource-allocation problems with limited choices in the long-chain design (Asadpour, Wang, and Zhang 2020), and income inequality among rideshare drivers, see, e.g., (Lesmana, Zhang, and Bei 2019; Sühr et al. 2019). The main model here is called Online Stochastic Matching (OSM) under the arrival setting of Known Identical Independent Distributions (KIID).3 OSM was first introduced by Karp, Vazirani, and Vazirani (1990) and the variant of OSM under KIID is well-studied before; see e.g., (Feldman et al. 2009; Haeupler, Mirrokni, and Zadimoghaddam 2011; Manshadi, Gharan, and Saberi 2012; Jaillet and Lu 2013). Our model is particularly related to online-side vertex-weighted OSM under KIID where all edges incident to each online agent shares the same weight. In contrast, current works studying vertex-weighted OSM focus on the setting of offline-side vertex-weighted (Ma, Xu, and Xu 2021; Brubach et al. 2020; Huang et al. 2018; Aggarwal et al. 2011), where all edges incident to each offline agent have the same weight. Most of the existing studies simply conducted a worst-case competitive-ratio analysis and gave a constant lower bound. In contrast, we investigate the worst-case more carefully and explicitly examine the different roles played by each external parameter (e.g., b and s ) in the final performance.

Preliminaries and Main Contributions

Competitive ratio. The competitive ratio is a commonlyused metric to evaluate the performance of online algorithms. Consider a given algorithm ALG and a clairvoyant optimal OPT. Note that ALG is subject to the real-time decision-making requirement, i.e., ALG has to make an irrevocable decision upon every arrival of online demand agents before observing future arrivals. In contrast, OPT is exempt from that requirement: OPT enjoys the privilege of observing the full arrival sequence of online demand agents before optimizing decisions. Consider an instance I of an online maximization problem as studied here. Let ALG(I) and OPT(I) denote the expected performance of ALG and OPT on I, respectively. We say ALG achieves a competitive ratio of ρ [0, 1] if ALG(I) ρ OPT(I) for all possible instances I. Essentially, the competitive ratio captures the gap between an online algorithm and a clairvoyant optimal due to the real-time decision-making requirement.

Main contributions. Let g(s, b) := E[min(Pois(b/s), b)]/b with 0 < s 1 and b 1, where Pois(b/s) denotes a Poisson random variable with mean b/s. Here are some properties about g(s, b). Due to the space limit, we leave the proofs of Lemma 1, Lemma 4, Lemma 5 and Theorem 3 to the full version.

Lemma 1. (P1) For any given 0 < s 1, g(s, b) is increasing over b 1; for any given b 1, g(s, b) is decreasing over s (0, 1]. (P2) For any b 1, g(1, b)

3The arrival setting proposed here is slightly different from the standard KIID as studied before but is essentially equivalent; see (Huang and Shu 2021).

max(1 1/e, 1 1/

2πb). (3) For each given b 1, lims 0+ g(s, b) = 1. First, we consider a general case and present an efficient algorithm with a competitive ratio lower bounded by 1 1/e 0.632. Theorem 1. There exists an LP-based sampling algorithm (SAMP) that achieves an online-competitive ratio of g(1, b) max(1 1/e, 1 1/p2πb), where b = mini I bi. Second, we consider a special case of homogeneous groups when each group consists of one single type of demand agents. In this context, we refer to types of demand agents and groups interchangeably, and use µj to denote the preset target of serving ratio for each group (or type) j. Let λ := P j J λ j be the total arrival rates and κ := minj J λ j/(λ µj), which denotes the degree of disproportionality for the least represented type in the arriving population with respect to the target serving ratio. Generally, the higher κ is, the lower disproportionality the arriving population has (i.e., every group is well represented in the arriving population). Theorem 2. There exists an LP-based sampling algorithm (SAMP-S) that achieves an online-competitive ratio of κ g(s , b), where κ = minj J λ j/(λ µj), b = mini I bi, and s is the optimal value to benchmark LP (12). Remarks. Let B = P i I bi (the total serving capacity among all supply agents), and thus B/λ (the ratio of the total serving capacities to the total expected number of arrivals) represents the degree of resource scarcity. We can show that s B/λ (See Lemma 4) and therefore, in practical cases when resources are highly scarce, we have s B/λ 1 and g(s , b) 1 by Lemma 1. As such, SAMP-S will outperform SAMP when κ is relatively large (i.e., the arriving population has a relatively low disproportionality overall). Theorem 3. The online-competitive analyses for SAMP and SAMP-S are both tight (i.e., the ratios presented above are the best ones they can ever achieve). Also, no algorithm can achieve an online-competitive ratio better than

3 1 0.732 even for homogeneous groups. We test our model and algorithms on publicly available COVID-19 vaccination datasets maintained by the Minnesota Department of Health. Experimental results confirm our theoretical predictions and demonstrate the power of our policies in navigating the distribution of limited resources toward the preset target ratios when compared against heuristics; see more details in Section 7.

An LP-based Policy for the General Case Throughout this paper, we use OPT to denote both of a clairvoyant optimal policy and its corresponding performance. For each pair of supply-demand agents e = (i, j), let xij denote the expected number of times that j is assigned to be served by i in a clairvoyant optimal (unconditional of the number of arrivals of j). Let Ni (Nj) be the set of neighbors of agents with respect to i (j) in the input graph G = (I, J, E). Let λ = P j J λ j. Consider the below linear program (LP). max s (1)

i Nj xij λ j j J (2)

i Nj xij s λ µg g G (3)

j Ni xij bi i I (4)

s, xij 0 (ij) E (5)

Lemma 2. OPT s , where OPT denotes the expected performance of a clairvoyant optimal and s is the optimal value to LP (1).

Proof. Recall that our objective is Max-A, maximization of the absolute-serving ratio (ASR). Observe that the expected number of total served demand agents in each group g is equal to E[Xg] = xg while the expected number of total arrivals is E[A] = λ. Thus, by the definition of ASR, our objective can be expressed as max ming G xg/(λ µg). By setting s = ming G xg/(λ µg), we see Constraint (3) ensures max s is equivalent to the Max-A. In the rest, we try to justify all other constraints are valid for any clairvoyant optimal policies. Constraint (2) is valid due to the expected number of served agents j (LHS) should be no larger than that of total arrives (RHS); Constraint (4) is valid since the expected number of agents served by i (LHS) should be no larger than its capacity (RHS); the last constraint is straightforward. Thus, we claim that LP (1) is maximizing the expected performance on ASR over all possible clairvoyant optimal policies.

For the ease of notation, we use {xij} to denote an optimal solution of LP (1) when the context is clear. Based on {xij}, we propose such a simple algorithm (SAMP) as stated in Algorithm 1, that is to non-adaptively sample a neighbor i Nj with probability xij/λ j upon every arrival of j and assign it whenever i has remaining capacity. Observe that the sampling distribution is valid since P i Nj xij/λ j 1 due to Constraint (2).

Proof of the main Theorem 1. Consider a given supply agent i, we see that each time its capacity will be consumed at a rate of P j Ni λ j (xij/λ j) = P j Ni xij bi. This suggests that at any time t, the probability that i has at least one remaining capacity should be at least Pr[Pois(bit) < bi]. Let Xij be the (random) number of times that demand agent j is served by i in SAMP. We have

λ j Pr[Pois(bit) < bi]dt (6)

0 Pr[Pois(bit) < bi] bi dt (7)

= xij E[min(Pois(bi), bi)]

Observe that the integral part on the second line above (7) essentially counts the number of arrivals in a Poisson process with an arrival rate bi whenever the total number of arrivals so far is less than bi and thus, it is equal

Algorithm 1: An LP-based sampling (SAMP).

1 Offline Phase:

2 Solve LP (1), and let {xij} be an optimal solution.

3 Online Phase:

4 Let a demand agent (of type) j arrive.

5 Sample a neighbor i Nj with probability xij/λ j.

6 if i has remaining serving capacity, then

7 Assign j to i;

9 Reject j.

to E[min(Pois(bi), bi)]. For each group g G, let Xg = P j g P i Nj Xij denote the number of agents in group g served in SAMP.

E[Xg] E[A] µg s =

P j g P i Nj E[Xij]

P j g P i Nj xij λ µg s E[min(Pois(bi), bi)]

E[min(Pois(bi), bi)]

bi = g(1, bi) g(1, b). (11)

As for Line (11): the first inequality is due to Constraint (3); the second inequality is due to (P1) in Lemma 1 (the function g(s, b) is increasing on b) and bi b. Thus, we have ming G E[Xg]/(E[A] µg) g(1, b) s . By Lemma 2, we establish the competitive ratio of SAMP.

A Special Case: Homogeneous Groups Recall that for homogeneous groups, each group consists of one single type of demand agents, and µj denotes the preset target serving ratio for each type (or group) j. Generally, {µj} reflect the demographics of all types among a certain population (e.g., the general population, or some special groups such as infected people). For this reason, we assume that µ := P j J µj 1 (note that in case there are overlaps among types, the sum can exceed one). Similar to before, let xij be the expected number of times that j is served by i in a clairvoyant optimal (OPT). Observe that for homogeneous groups, we have each g = {j} and we can verify that LP-(1) then is reduced to the below.

i Nj xij λ j j J (13)

i Nj xij s λ µj j J (14)

j Ni xij bi i I (15)

s, xij 0 (ij) E (16)

Parallel to Lemma 2, we have the below claim.

Algorithm 2: An improved policy for homogeneous groups (SAMP-S).

1 Offline Phase: Solve LP (12), and let {xij, s } be an optimal solution with each x j = P i Nj xij = s λ µj.

2 Online Phase:

3 Let a demand agent (of type) j arrive.

4 if j is an overpresented agent with κj := λ j/(λ µj) > 1 then

5 Sample a neighbor i Nj with probability xij/(λ j s ). Assign j to i if i still can serve.

7 Sample a neighbor i Nj with probability xij/(λ µj s ). Assign j to i if i still can serve.

Lemma 3. The optimal value of LP (12) serves as a valid upper bound for the expected performance of a clairvoyant optimal.

We present another LP-based sampling algorithm as follows. For the ease of notation, we use {xij, s } to denote an optimal solution to LP (12), and assume WLOG that x j = P j J xij = s λ µj for each j J. Note that we refer to agents j with κj := λ j/(λ µj) > 1 and κj < 1 as overrepresented and underrepresented, respectively. Recall that κ = minj J κj, which denotes the degree of disproportionality of the least represented type in the arriving population, and B = P i I bi. The following observations will be useful later.

Lemma 4. (P1) s κ 1; (P2) s B/λ.

Lemma 5. Sampling distributions in SAMP-S are valid for all demand agents and they can be viewed as a boosted version of those in SAMP.

Proof of the main Theorem 2. For each supply agent i, let Ni,H (Ni,L) denote the set of neighbors of i that are overrepresented (underrepresented). Observe that for each i, its capacity will be consumed in SAMP-S with a rate of X

j Ni, H λ j xij λ j s + X

j Ni, L λ j xij λ µj s bi

Case 1. Consider a given underrepresented type j, let Xij denote the (random) number of times that j is served by i in SAMP-S.

E[Xij] = Z 1

0 λ j xij λ µj s Pr[Pois(bit/s ) < bi]dt

0 Pr[Pois(bit/s ) < bi] bi

= κj xij E[min(Pois(bi/s ), bi)]

bi = κj xij g(s , bi) κ xij g(s , b)

The last inequality is due to (P1) in Lemma 1 (the function g(s, b) is increasing on b) and bi b.

Case 2. Consider a given overrepresented type j and let Xij be the number of times that j is served by i.

E[Xij] = Z 1

0 λ j xij λ j s Pr[Pois(bit/s ) < bi]dt

0 Pr[Pois(bit/s ) < bi] bi

= xij E[min(Pois(bi/s ), bi)]

bi = xij g(s , bi) κ xij g(s , b)

The last inequality is valid since κ 1. Thus, summarizing the above two cases, we claim for any pair of supply-demand agent (ij) E, we have E[Xij] κ xij g(s , b). Let Xj = P i Nj Xij denote the number of agents of j served in SAMP-S.

E[Xj] E[A] µj s = E[Xj] λ µj s = P i Ni E[Xij]

P i Nj κ xij g(s , b)

x j = κ g(s , b),

which suggests that minj J E[Xj]/(E[A] µj) (κ g(s , b)) s . By Lemma 3, we establish the competitive ratio of SAMP-S.

Experimental Results Due to the space limit, we present only the experimental results on the general case. We also conduct experiments on the special case of homogeneous groups and defer the results to the full version. We use the publicly available COVID-19 vaccination datasets that are maintained by the Minnesota Department of Health4.

Preprocessing of the COVID-19 vaccination datasets. The datasets include the following information relevant to our experimental setup: (1) The total cumulative numbers of people with completed vaccine series in any given county (updated weekly); (2) the cumulative numbers of doses of each vaccine product (Pfizer, Moderna, and Johnson & Johnson) shipped to to local Minnesota providers and pharmacies in the C.D.C. partnership program; (3) the weekly progress regarding the percentages of people with completed vaccine series in any age-race group, where age is among 15+, 1544, 45-64, and 65+, and race has options of American Indian (AI), Asian/Pacific Islander (API), Black/African American (BAA), Hispanic (H), and White (W). We extract the data collected from (1), (2), and (3) over the time range from May 7 to June 17 in 2021, and plot them in Figure 1. The first three figures in Figure 1 (from left to right) show the distribution on the numbers of people that get fully vaccinated over different counties, the percentage of the three vaccines administered, and the percentage of people getting fully vaccinated by race, respectively. We also map the distribution of the general population in Minnesota by race based on American Community Survey (ACS) 5-year estimates.

4https://mn.gov/covid19/vaccine/data/index.jsp.

Minnesota Population Distribution

Black/African American

White 83.21%

Minnesot Populatio Distributio

Black/African American

Vaccination Progress

Hispanic 2.80%

Black/African American 3.70% Asian/Pacific Islander

American Indian

White 88.39%

Moderna Pfizer Johnson & Johnson

Asian/Pacific Islander 4.98%

American Indian 1.02%

Figure 1: Overview of the COVID-19 vaccination datasets from May 7 to June 17, 2021, in Minnesota: the distribution on the numbers of people fully vaccinated over counties (First), the percentage of the three vaccines administered (Second), the percentage of people fully vaccinated by race (Third), and the distribution of the general population by race (Fourth), respectively.

Supply Scarcity

1 1.5 2 2.5 3

0.586 0.586

LP Solution

Competitive Ratios

Supply Scarcity

1 1.5 2 2.5 3

SAMP GREEDY UNIFORM RANKING

Competitive Ratios

1 3 5 7 9 11

SAMP Theoretical Lower Bound

ρ The Minimum Serving Capacity b

Figure 2: Experimental results on the COVID-19 vaccination datasets: the competitive ratios achieved when the supply scarcity ρ {1, 1.5, 2, 2.5, 3} (Left), the optimal value s of LP (1) as the supply scarcity ρ {1, 1.5, 2, 2.5, 3} (Middle), and the competitive ratios achieved when the min serving capacity b {1, 3, 5, 7, 9, 11} (Right), respectively.

Based on the above information, we construct the input instance as follows. Figure 1 shows that Minnesota is made up of 87 counties. For each pair of county and vaccine type, we create a supply agent. We set the initial serving capacity for each supply agent being equal to the total number of doses of the specific vaccine administered in the county divided by the number of units needed per requester. To make it computationally tractable, we downsample each bi proportionally such that the total serving capacity B = P i I bi = 104. For each county-race pair, we create a demand agent, and set the initial arriving rate being equal to the percentage of the people getting fully vaccinated in that specific county and race. Motivated by the work (Manshadi, Niazadeh, and Rodilitz 2021), we introduce a concept, called supply scarcity (denoted by ρ 1), which represents the ratio of the expected total of demand to that of supply. We inflate the arriving rate λ j of each demand agent j by a factor of B ρ such that the total arriving rates after scaling up will satisfy λ = P j J λ j = B ρ. We add an edge between a demand agent and a supply agent if the two agents locate in the same or adjacent counties (the relative positives of all the 87 counties are shown in Figure 1). We create a group for each race, and set the preset goal as the percentage in the general pop-

ulation as illustrated in the last plot of Figure 1.

Algorithms. In additional to the two LP-based algorithms SAMP and SAMP-S proposed in this paper, we also implement several heuristic baselines. Suppose a demand agent j arrives at some time t and let Nj,t be the set of neighboring supply agents to j that still have at least one remaining serving capacity at t. If Nj,t is empty, we have to reject j; otherwise, (a) GREEDY: assign j to the agent i that has the largest serving capacity in Nj,t (and break the ties arbitrarily); (b) UNIFORM: select an agent uniformly at random in Nj,t; (c) RANKING: select the agent from Nj,t that has the largest order following a pre-selected random order on I.

Results and discussions. We test different settings when the supply scarcity ρ takes values in {1, 1.5, 2, 2.5, 3} while the minimum serving capacity is fixed at b = 1. For each setting, we run all algorithms for 100 times and take the average as the final performance. The competitive ratios are computed by comparing the averaged performance to the optimal value of LP (1). We also consider another setting when we fix ρ = 2 while vary the minimum serving capacity b {1, 3, 5, 7, 9, 11}, respectively. Here, we scale up b

AI API BAA H W

SAMP GREEDY 1

(a) ASR achieved when ρ = 1.

AI API BAA H W

SAMP GREEDY 1

(b) ASR achieved when ρ = 2.

AI API BAA H W

SAMP GREEDY 1

(c) ASR achieved when ρ = 3.

Figure 3: ASR achieved for different races, i.e., American Indian (AI), Asian/Pacific Islander (API), Black/African American (BAA), Hispanic (H), and White (W)), when the supply scarcity ρ {1, 2, 3}.

AI API BAA H W

Real Vaccinated SAMP GREEDY 1

(a) RSR achieved when ρ = 1.

AI API BAA H W

Real Vaccinated SAMP GREEDY 1

(b) RSR achieved when ρ = 2.

AI API BAA H W

Real Vaccinated SAMP GREEDY 1

(c) RSR achieved when ρ = 3.

Figure 4: RSR achieved for different races when the supply scarcity ρ {1, 2, 3}.

by simply filtering out those supply agents with a serving capacity less than b. Figure 2 (Left) shows that in a typical over-demanded settings (ρ > 1), SAMP outperforms all other benchmarks. This highlights the global-optimization power of SAMP when supply falls short of demand. Figure 2 (Right) shows that SAMP always stay above its theoretical lower bound over different choices of b, which confirms our theoretical prediction as suggested by Theorem 1. To better demonstrate the advantage of SAMP, we visualize two metrics of equality, i.e., the absolute-serving ratio (ASR) and relativeserving ratio (RSR), in Figure 3 and Figure 4, respectively. Since the performances of RANKING and UNIFORM are both similar to GREEDY, we omit them in Figure 3 and Figure 4 for presentation convenience. Figure 3 shows that in over-demanded settings (ρ = 2 and ρ = 3), SAMP demonstrates its power in pushing all races ASR toward the preset targets, but not for the case when supply roughly meets demand (ρ = 1). This is because in the latter case (ρ = 1), performances of both SAMP and the clairvoyant (OPT) are both bottlenecked by the degree of disproportionality of the least represented race, which is Hispanic with κ = 0.586 in our context. Thus, SAMP have no motivation to push the ASR for any races. The bottleneck can be seen from Figure 2 (Middle): when ρ 1.5, the optimal value of LP (1) stays at the value κ = 0.586;

while as ρ increases to 2, the bottleneck of OPT shifts from κ = 0.583 to 1/ρ 0.5. In the over-demanded settings, SAMP can leverage the solution of the benchmark LP (1) by serving the underrepresented arrivals as many as possible, while selecting only a fraction to serve for those overrepresented. Figure 4 shows that under the metric of RSR, Greedy s performance aligns well with the real-world case. This is mainly due to the fact that heuristic-based strategies like Greedy have been widely adopted in practical situations. Figure 4 also suggests that though SAMP is not designed to promote RSR, it can have an excellent performance on RSR (almost equal to 1) in over-demanded settings. This further highlights the superiority of SAMP.

Conclusion and Future Directions This paper presents two LP-based strategies that can effectively navigate the distribution of the limited resources toward preset target ratios. Theoretical and numerical results highlight the power of our policies in reducing the existing biases in the arriving population, which are commonly observed in resource allocation when demands far outnumber supplies. Observe that the current two metrics (ASR and RSR) both model the gap between the serving ratio achieved the preset target as the ratio of the former to the latter. How about replacing the relative-ratio-based gap with the absolute-difference-based gap?

Acknowledgments Yifan Xu was partially supported by NSFC 61971131. Pan Xu was partially supported by NSF CRII Award IIS1948157. The authors would like to thank the anonymous reviewers for their helpful feedback.

References Abcarian, R. 2021. Column: The answer to equitable distribution of COVID-19 vaccines is hiding in plain sight. https://www.latimes.com/opinion/story/2021-02-24/ vaccine-equity-community-health-clinic-role. Accessed: 2021-03-02. Adamson, P. 2021. Vaccine equity: If we build it, will they come? https://www.statnews.com/2021/02/24/vaccineequity-if-we-build-it-will-they-come/. Accessed: 2021-0320. Aggarwal, G.; Goel, G.; Karande, C.; and Mehta, A. 2011. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, 1253 1264. Asadpour, A.; Wang, X.; and Zhang, J. 2020. Online Resource Allocation with Limited Flexibility. Management Science, 66(2): 642 666. Benabbou, N.; Chakraborty, M.; Ho, X.-V.; Sliwinski, J.; and Zick, Y. 2018. Diversity constraints in public housing allocation. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems, 973 981. Blackstock, U.; and Blackstock, O. 2021. White Americans are being vaccinated at higher rates than Black Americans. Such inequity cannot stand. https://www.washingtonpost. com/opinions/2021/02/01/racial-inequality-covid-vaccine/. Accessed: 2021-03-16. Board, T. E. 2021. How New York s Vaccine Program Missed Black and Hispanic Residents. https://www.nytimes.com/2021/02/01/opinion/new-yorkcovid-vaccine.html. Accessed: 2021-03-15. Brubach, B.; Sankararaman, K. A.; Srinivasan, A.; and Xu, P. 2020. Online stochastic matching: New algorithms and bounds. Algorithmica, 1 47. Chatterjee, A.; Borokhovich, M.; Varshney, L. R.; and Vishwanath, S. 2018. Efficient and Flexible Crowdsourcing of Specialized Tasks With Precedence Constraints. IEEE/ACM Transactions Network, 26(2): 879 892. Feldman, J.; Mehta, A.; Mirrokni, V.; and Muthukrishnan, S. 2009. Online stochastic matching: Beating 1-1/e. In 50th Annual IEEE Symposium on Foundations of Computer Science, 117 126. Fitzsimmons, E. G. 2021. Black and Latino New Yorkers Trail White Residents in Vaccine Rollout. https://www.nytimes.com/2021/01/31/nyregion/nyc-covidvaccine-race.html. Accessed: 2021-03-05. Haeupler, B.; Mirrokni, V. S.; and Zadimoghaddam, M. 2011. Online stochastic weighted matching: Improved approximation algorithms. In International Workshop on Internet and Network Economics, 170 181.

Hosseini, H.; Huang, Z.; Igarashi, A.; and Shah, N. 2022. Class Fairness in Online Matching. ar Xiv preprint ar Xiv:2203.03751. Huang, Z.; and Shu, X. 2021. Online stochastic matching, poisson arrivals, and the natural linear program. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 682 693. Huang, Z.; Tang, Z. G.; Wu, X.; and Zhang, Y. 2018. Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals. In 45th International Colloquium on Automata, Languages, and Programming. Jaillet, P.; and Lu, X. 2013. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations Research, 39(3). Jones, G. A. 2021. How we re working toward racial equity in distributing coronavirus vaccines in D.C. https://www.washingtonpost.com/opinions/local-opinions/ how-were-working-toward-racial-equity-in-distributingcoronavirus-vaccines-in-dc/2021/02/25/13fed062-75e411eb-9537-496158cc5fd9_story.html. Accessed: 2021-0320. Karp, R. M.; Vazirani, U. V.; and Vazirani, V. V. 1990. An Optimal Algorithm for On-line Bipartite Matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 352 358. Lesmana, N. S.; Zhang, X.; and Bei, X. 2019. Balancing Efficiency and Fairness in On-Demand Ridesourcing. In Advances in Neural Information Processing Systems, 5310 5320. Lien, R. W.; Iravani, S. M.; and Smilowitz, K. R. 2014. Sequential resource allocation for nonprofit operations. Operations Research, 62(2): 301 317. Ma, W.; Xu, P.; and Xu, Y. 2020. Group-level Fairness Maximization in Online Bipartite Matching. ar Xiv preprint ar Xiv:2011.13908. Ma, W.; Xu, P.; and Xu, Y. 2021. Fairness Maximization among Offline Agents in Online-Matching Markets. ar Xiv preprint ar Xiv:2109.08934. Manshadi, V.; Niazadeh, R.; and Rodilitz, S. 2021. Fair Dynamic Rationing. Proceedings of the 22nd ACM Conference on Economics and Computation. Manshadi, V. H.; Gharan, S. O.; and Saberi, A. 2012. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research, 37(4). Nanda, V.; Xu, P.; Sankararaman, K. A.; Dickerson, J.; and Srinivasan, A. 2020. Balancing the tradeoff between profit and fairness in rideshare platforms during high-demand hours. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2210 2217. Singer, N. 2021. Where Do Vaccine Doses Go, and Who Gets Them? The Algorithms Decide. https://www.nytimes. com/2021/02/07/technology/vaccine-algorithms.html. Accessed: 2021-03-15. Stolberg, S. G. 2021. As Biden Pushes for Racial Equity in Vaccination, Data Is Lagging. https://www.nytimes.com/ 2021/02/09/us/politics/biden-vaccination-race-data.html. Accessed: 2021-03-02.

Stoyanovich, J.; Yang, K.; and Jagadish, H. V. 2018. Online Set Selection with Fairness and Diversity Constraints. In Proceedings of the 21st International Conference on Extending Database Technology, 241 252. Sühr, T.; Biega, A. J.; Zehlike, M.; Gummadi, K. P.; and Chakraborty, A. 2019. Two-sided fairness for repeated matchings in two-sided markets: A case study of a ridehailing platform. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 3082 3092. Sumita, H.; Ito, S.; Takemura, K.; Hatano, D.; Fukunaga, T.; Kakimura, N.; and ichi Kawarabayashi, K. 2022. Online Task Assignment Problems with Reusable Resources. ar Xiv preprint ar Xiv:2203.07605. Walker, A. S.; Singhvi, A.; Holder, J.; Gebeloff, R.; and Avila, Y. 2021. Pandemic s Racial Disparities Persist in Vaccine Rollout. https://www.nytimes.com/interactive/2021/03/ 05/us/vaccine-racial-disparities.html. Accessed: 2021-0315. Wang, Y.; Bier, V. M.; and Sun, B. 2019. Measuring and achieving equity in multiperiod emergency material allocation. Risk Analysis, 39(11): 2408 2426. Xu, Y.; and Xu, P. 2020. Trade the System Efficiency for the Income Equality of Drivers in Rideshare. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 4199 4205.