A Unified Model for the Two-stage Offline-then-Online Resource Allocation

1 Introduction

Matching markets involve heterogeneous agents (typically from two parties) who are paired for mutual benefits. During the last decade, matching markets have emerged and grown rapidly through the medium of the Internet. They have evolved into a new style, called Online Matching Markets (OMMs). Typical examples include ridesharing (riders and drivers), crowdsourcing (workers and tasks), and Internet advertising (impressions and advertisers). In OMMs, agents of at least one type join the market in an online fashion, and are referred to as online agents (e.g., riders, workers, and impressions). Furthermore, upon the arrival of any online agent, we have to decide quickly and irrevocably which offline agent(s) to match it with. That is mainly due to the low "patience"

of the online agents. These features-online arrivals and the real-time decision-making requirement-distinguish OMMs from traditional matching markets where the information of all agents is fully disclosed in advance.

OMMs have received significant interest in both computer science and operations research communities. There is a large body of research work who studied matching policy design for the profit maximization in ridesharing [Ashlagi et al., 2019; Lowalekar et al., 2018; Bei and Zhang, 2018; Zhao et al., 2019; Dickerson et al., 2018a], crowdsourcing [Assadi et al., 2015; Ho and Vaughan, 2012; Dickerson et al., 2018b], admission scheduling and online recommendations [Ma and Simchi-Levi, 2017; Chen et al., 2016]. Recently, [Dickerson et al., 2019] presented a general online resource allocation model, called Multi-Budgeted Online Assignment (MBOA), to address the matching policy design in various real-world OMMs featuring that each assignment could potentially consumes multiple resources. The basic model is as follows. We are given a bipartite graph G = (I; J; E) where I and J represent the respective sets of offline and online agents. There is a set K of K resources and each resource k 2 K has a given budget Bk. Each edge e = (i; j) or assignment1 of j to i is associated with a profit and a vector cost of dimension K. A natural question is how to arrange an assignment for each online agent upon its arrival such that the total expected profit is maximized subject to the budget constraints.

MBOA [Dickerson et al., 2019] has greatly generalized the assignment problems in OMMs. Consider Amazon Mechanical Turk for example, which automatically crowdsources online workers for offline tasks. In this case, there are typically two kinds of resources, budget (deposited by a task manager to pay workers) and tasks (typically each task has a limited number of copies). In addition to OMMs, MBOA has captured a wide range of online resource allocation problems in datacenters [Ghodsi et al., 2012; Ghodsi et al., 2013], public safety [Lee et al., 1979; Guedes et al., 2014] and candidates recruitment [Yi et al., 2007], for example. Note that MBOA considers resource allocation only for online arrival agents. In some emerging applications, however, there are both offline and online agents who are competing for the same set of resources. Consider the two motivating examples below.

1Throughout this paper, we use the two terms "edge" and "assignment" interchangeably.

Rebalancing in Bike Sharing Systems (BSSs). BSSs have become an important alternative for addressing the last mile problem in city Intelligent Transportation Systems. Users varied travel patterns lead to uneven distributions of bikes among docking stations. A common scenario is during afternoon peak hours, "demanding" stations (e.g., near shopping malls or metro stations) have a high demand but a low supply, while "supplying" stations (e.g., suburb areas far away from downtown) have a high supply but a low demand. Thus, BSSs have to rebalance distributions by moving bikes from "supplying" to "demanding" stations such that they can address as many user requests as possible. Two common rebalancing strategies are proposed. One is the Truck-Based Rebalancing (TBR), which directly utilizes trucks or trailers to move bikes from one station to the other. The other is Crowdsourcing-Based Rebalancing (CBR), which incentives online bike users to participate in rebalancing tasks. TBR has a strong controllability, high efficiency during offpeak hours, and a high labor cost. In contrast, CBR has a relatively low controllability, high efficiency during peak hours, and a low labor cost. The two approaches each has received considerable interest, see, e.g., [Raviv et al., 2013; O'Mahony and Shmoys, 2015; Liu et al., 2016; Li et al., 2018] for TBR, and [Singla et al., 2015; Haider et al., 2018; Pan et al., 2019; Duan and Wu, 2019] for CBR. However, very few of them have ever considered both TBR and CBR in the same framework, though the two are proposed to address the same issue. For TBR, it is typically deployed during off-peak hours and involves renting offline trucks and labors. For CBR, it is operated during peak hours instead, and crowdsources online users as potential workers. Note that both TBR and CBR compete for one resource, the global budget used for renting truck and hiring labors in TBR, and paying online workers in CBR. Additionally, the two compete for the same set of tasks, i.e., moving bikes from supplying to demanding stations. In fact, we can view each supplying and demanding station as a "resource" with the capacity being the number of bikes in supply and demand. A natural question arises: How to optimally allocate the "resources" to the two approaches such that we can complete as many tasks as possible?

Trip-vehicle dispatching with multi-type requests. In recent years, ridesharing apps such as DiDi launch services that allow riders to reserve a trip in advance, which is called scheduled requests [Huang et al., 2019]. Consider a short time window W during peak hours. Let C1 be the set of scheduled requests received with starting time in W and C2 be the (random) set of real-time requests which arrive inW. Note that C1 is received well before the start of W and thus can be viewed as offline requests. Both C1 and C2 are competing for the same set of "resources": the available drivers in W. A natural question is: How to allocate drivers to requests such that the total expected profit obtained is maximized?

The above two examples both feature a two-stage resource allocation: the first stage involves a set of static offline agents while the second stage involves a set of dynamic online agents, and they are competing for the same set of resources.

Main contributions. Our contributions are summarized as follows. First, we propose a unified framework, called Two-Stage Resource Allocation (TS-RA), by generalizing the model in [Dickerson et al., 2019]. Overall, TS-RA incorporates the offline and online resource allocation into one single framework, which can potentially capture a wider range of applications and optimize the allocation jointly. Second, we propose a parameterized linear programming (LP)-based algorithm, which is shown to be at most a constant factor of 1=4 from the optimal. One highlight is the performance of our LP-based approaches depends only on the sparsity, i.e., the maximum number of different resources requested by an assignment, regardless of the total number of resources involved which can be potentially large. Third, we present several greedy-based heuristics and compare our LP-based algorithms against those LP-agnostic heuristics. Experimental results on the real dataset show our LP-based approaches are robust and effective in a wide range of settings and they can universally dominate all LP-agnostic heuristics.

2 Preliminaries

We first formally define the model considered in this paper and then describe the required background for the technical sections of this paper. As a notation, denote [k] � f1; 2; : : : ; kg for any positive integer k.

Two-Stage Resource Allocation (TS-RA). We have a bipartite graph G of vertex sets (I; H �[ J) where I and H represent the sets of types of offline vertices, and J disjointed from H represents the set of types of online vertices. Let E 1 and E 2 be the respective sets of edges in the subgraphs G 1 of (I; H) and G 2 of (I; J). There are K offline resources and each resource k has a budget Bk 2 R + . Each edge or assignment e yields a positive reward (weight) we > 0 and incurs a vector-valued cost ae = (ae;k) 2 [0; 1] K , where ae;k denotes the consumption of resource k by e. The assignment process consists of two sequential stages, (offline) Phase I and (online) Phase II. We first select an arbitrary set of edges E1 (can be a multiset of E 1 ) in Phase I and then in Phase II, we conduct an online assignment process on the subgraph G 2 with I and J be the respective sets of offline and online vertices and output a set of edges E2 (can be a multiset of E 2 ). Our overall goal is to design an allocation policy to maximize the expected total weights of all edges in E1 [ E2 while the total cost of all edges in E1 [ E2 does not exceed the budget B = (Bk ) (the budget constraint is enforced throughout Phase I and Phase II).

Note that the full graph G of (I; H �[ J) is known as part of the input2. The only stochastic part to the algorithm is the arrival sequence of online vertices in Phase II, which is specified as follows. We have a finite horizon T (known in advance). For each time (or round) t 2 [T] � f1; 2; : : : ; Tg, a vertex of type3 j 2 J will be sampled (or j arrives) from a known distribution fpjt g such that P j 2J pjt = 1, and the sampling procedures are independent across the T rounds. Upon the arrival of an online vertex j , an immediate and irrevocable decision is required: either reject j, or select an edge e 2 E 2 j , where E 2 j � E 2 is the set of incident edges to j in G 2 . Observe that there could be multiple arrivals for each given type of online vertices, we can possibly select multiple copies of a single edge e 2 E 2 in Phase II.

2A future direction is to explore how to incorporate online learning into our framework to learn the input dynamically.

3The two terms "a vertex of type j" and "a vertex j" will be used interchangeably when the context is clear.

Remarks. First, the algorithms presented in this paper are applicable directly to a more general setting where each assignment e yields a random reward We (independent from others). What we need is just the expectation we � E[We] for each e. Second, we cannot simply merge Phase I to part of Phase II. Recall that in Phase II, we have to make an irrevocable matching decision upon the arrival of each online vertex. Suppose we try to treat Phase I as part of Phase II by viewing each arrival h 2 H with probability 1 during the first jHj rounds. This reduction will essentially restrict the power of algorithm design in Phase I in the way that we should process all assignments in E 1 following the arrival order of vertices of H. In fact, we can process all assignments in E 1 simultaneously since the graph G 1 is fully known in advance.

Integral and non-integral resources. For an integral resource k, we have that for any edge e 2 E 1 [E 2 , ae;k 2 f0; 1g while for a non-integral resource k, we have that for any e 2 E, ae;k 2 [0; 1]. For any integral resource k, WLOG we assume that Bk 2 Z+. Let K1 = f1; 2; � � � ; K1g and K2 = fK1 + 1; � � � ; K1 + K2g denote the set of integral and non-integral resources, respectively. For any edge e, let Se be the set of resources requested by e, i.e., Se = fk 2 K : ae;k > 0g. In this paper, we assume that jSe \K1j � '1 and jSe \ K2j � '2, where '1 and '2 are the integral and nonintegral sparsities (i.e., for types of resources), respectively.

Let us briefly show how rebalancing in BSSs can be cast under TS-RA (similarly for trip-vehicle dispatching). Suppose we have two sets, C1 and C2, which denote the respective sets of supplying and demanding bike stations. Let each a 2 C1 have a supply of ca 2 Z + and each b 2 C2 have a demand of cb 2 Z + . Define I = C1 � C2, H = fhg includes one dummy node, and J is the set of all online worker types. Consider a given i = (a; b) with a 2 C1; b 2 C2. Let the edge e = (i; h) denote the assignment of the task of moving one bike from a to b via TBR and e = (i; j ) denote the assignment of the same task to a worker of type j via CBR. In this way, we have jC1 j+jC2 j kinds of integral resources and each a 2 C1 and b 2 C2 have a budget of ca and cb, respectively. We have one non-integral resource, which is the global budget used to pay rented trucks, labor fees, and online workers. Though we potentially have a huge number of resources (jC1 j + jC2 j + 1), each assignment requests at most two integral resources (the supplying and demanding stations) and one non-integral resource (the global budget), i.e., '1 = 2; '2 = 1. Later we will show that the performance of our allocation policy depends only on the total number of sparsity '1 + '2, regardless of the total number of resources.

Extension of competitive ratio. Competitive ratio (CR) is a commonly-used metric to evaluate the performance of online algorithms. In our case, we have two stages, offline Phase I and online Phase II. We can extend CR to our setting as follows. Recall that our overall goal is to maximize the total weights of all assignments made in the two phases. Let ALG denote an assignment policy for Phases I and II. Consider an input I of the problem. Let E[ALG(I)] denote the expected profit obtained by ALG for this instance, where the expectation is over the randomness in the arrival sequence in Phase II and any internal randomness wired in the algorithm. Similarly, let E[OPT(I)] denote the expected value of the optimal offline solution (i.e., the expected value of optimal assignments for Phases I and II after observing the entire arrival sequence in Phase II). The competitive ratio is defined as infI E[ALG(I)]= E[OPT(I)].

For any maximization problem such as the one studied here, we say ALG achieves a ratio at least � 2 (0; 1) if for any input of the problem the expected profit obtained by ALG is at least a fraction � of the offline optimal solution. Typically computing the value of E[OPT(I)] directly is hard. A common method to bypass this is to construct a linear program (called benchmark LP) whose optimal value is an upper bound on E[OPT(I)] due to the integrality gap. Hence comparing E[ALG(I)] to the optimal value of this LP gives a lower bound on the competitive ratio. We will now describe the benchmark LP used in this paper.

Benchmark LP. Recall that E 2 j � E 2 is the set of incident edges to j in G 2 . Consider an offline optimal algorithm. For each e 2 E 1 , let xe be the expected number of copies that e is selected during Phase I and for each e 2 E 2 and t 2 [T], let ye;t be the probability that edge e is selected at t. Consider the following benchmark LP.

This LP can be interpreted as follows. Constraint (2) : for any given vertex of type j and time t during Phase II, the probability that we select an edge incident to j is at most the probability that j arrives at time t. Constraint (3) : for any resource k, the expected consumption cannot be larger than its budget (Bk). The last constraint (4) is due to the fact that all fye;t g are probability values and hence should lie in the interval [0; 1]. Also xe should be non-negative since it denotes the number of copies that e is selected. The above analysis suggests that any offline optimal algorithm, fxe; ye;t g should be feasible for the above LP. Formally, we have Lemma 1 which claims that the optimal solution of this LP is an upper bound on the expected offline optimal value. We defer the proof of Lemma 1 to the full version 4.

Lemma 1. The optimal value to LP (1) is a valid upper bound for the offline optimal solution.

3 Main Algorithm and Results

In this section, we describe our main algorithm SAMP, which is an LP-guided sampling policy.

Let fx � e; y � e;t g be an optimal solution to the LP (1). The main idea behind SAMP (described in Algorithm 1) is as follows.

4https://tinyurl.com/ybfyg9cx

Algorithm 1 SAMP(�; �)

Offline Phase I:

• 1 Independently sample RD(�x � e) copies of edges for each e 2 E 1 .
• 2 Remove all copies of e if e is not safe (i.e., e requests some resource on which there is a budget overrun).

Online Phase II:

• 3 Assume a vertex (of type) j arrives at time t.
• 4 Sample an edge e from E 2 j with probability �y � e; t =pj t .
• 5 If e is safe (i.e., adding e will not break any budget constraint at t), then select it; otherwise reject it.

For a given non-negative value x � 0, let RD(x) be such an integral random variable that RD(x) = dxee with probability x � bxc and RD(x) = bxc otherwise. Essentially RD(x) takes values between bxc and dxe with E[RD(x)] = x. In the offline Phase I, we independently sample RD(�x � e) copies of edges for each e 2 E 1 , where � 2 (0; 1] is a scaling factor to optimize later. Let E be the random multiset of all edges sampled in Phase I. Notice that the total consumption of E can potentially violate budget constraints for some resources. If so, then remove all copies of e if any number of e contributes to the violation5. In the online Phase II, suppose a vertex (of type) j arrives at time t. We say an edge e 2 E 2 j is safe iff adding e will not violate any budget constraint (i.e., the remaining budget at t is enough to cover all resources requested by e). Sample an edge e from E 2 j with probability �y � e;t =pj;t and select it iff e is safe. Here � 2 (0; 1] is scaling factor to optimize later. Note that Step 4 of SAMP is well defined since we have P e2E 2 j �y � e;t =pjt � P e2E 2 j y � e;t =pjt � 1, due to Constraint (2) in LP (1).

3.1 Main Theoretical Results

Theorem 1 (Performance of SAMP for the integral case). For TS-RA when all resources are integral with a sparsity of ', SAMP with � = � = 1 2' achieves a competitive ratio of at least 1 4' using LP (1) as the benchmark.

Theorem 2 (Performance of SAMP for the general case). For TS-RA when both integral and non-integral resources are involved with respective sparsities of '1 and '2, SAMP with � = � = 1 2' achieves a competitive ratio of at least 1 4' (1 � �) using LP (1) as the benchmark, where ' = '1 + '2 and � = 2max � 1=(B�2); '2 exp(�B=12+1=6) � with B being the minimum budget over all non-integral resources.

The main technique used here is a combination of randomized rounding with alterations introduced to solve packing integer programs [Bansal et al., 2012] and randomized sampling for online resource allocation [Dickerson et al., 2019]. Generally, we cannot beat the ratio of 1=('�1+1=') for the integral case with a sparsity of ' using LP (1) as the benchmark, due to the hardness result derived from the set packing problem [Füredi et al., 1993]. This suggests that the performance of SAMP is almost a constant factor (1=4) from the optimal for the integral case. For the general case, Theorem 2 implies that we can simply treat non-integral resources as integral and SAMP will achieve nearly the same ratio when the budgets among all non-integral resources are moderately large �(1=�). Note that in the absence of a lower bound on the budgets of all non-integral resources, LP-based randomized samplings can have an arbitrarily bad performance for online resource allocation, as shown in [Dickerson et al., 2019]. We will present the proof of Theorem 1 in Section 4 and defer the proof of Theorem 2 to the full version 4.

5Theoretically, we can act in this way, though we can implement the removal of copies sequentially until no violation of budget.

4 Performance Analysis of SAMP

For each e 2 E 1 , let Xe be the random number of copies of e selected in Phase I and for each e 2 E 2 and t 2 [T], let Ye;t indicate if e is selected at t in Phase II by SAMP. Suppose for a given target constant � 2 (0; 1), we can show that E[Xe] � � x � e for all e 2 E 1 and E[Ye;t ] � �y � e;t for all e 2 E 2 and t 2 [T]. Then by linearity of expectation, the expected total rewards should be at least � � P e2E 1 we x � e + P e2E 2 wey � e; t � , which is followed by that SAMP achieves an online ratio at least � from Lemma 1.

For Phase I, we have the following lemma.

Lemma 2. For each e 2 E 1 , we have E[Xe] � �(1 � �) ' x � e.

Proof. According to SAMP, we first sample RD(�x � e) copies of edge e and then include all of them iff e is safe, i.e., all resources requested by e have no budget overrun. Consider a given e 2 E 1 and recall that Se � K1 is the set of all integral resources requested by e. By the sparsity assumption, we have jSe j � '.

Consider a given k 2 Se and thus ae;k = 1. For each e 0 2 E 1 including e 0 = e, let Ze 0 = RD(�x � e 0 ). Notice that

Inequality (7) is due to d�x � ee � dx � ee � x � e + 1. Inequality (8) is due to Markov's inequality and the fact that E f P e 0 2E 1 ;e 0 ,e Ze 0ae 0 ;k g = P e 0 2E 1 ;e 0 ,e �x � e 0 ae 0 ;k � �(Bk �x � e) from Constraint (3) in LP (1). We can verify that in the other case when Ze gets rounded down to b�x � ec, the probability that resource k has a budget overrun should be no larger than that when Ze is rounded up to d�x � ee. Therefore, we claim that regardless the outcomes of Ze = ze 2 fd�x � ee; b�x � ec g, there is a budget overrun on resource k with probability at most �.

Observe that fZe 0 je 0 2 E 1 g are all independent random variables and events f( P e 0 2E 1 ;e 0 ,e Ze 0ae 0 ;k � Bk�zeae;k)jk 2 Seg are decreasingly likely events for each given ze. Thus applying the FKG inequality [Fortuin et al., 1971], the probability that e is safe should be

Note that the above inequality is valid regardless the choices of ze 2 fd�x � ee; b�x � ecg. Therefore, E[Xe] � E[Ze] � (1 � �) ' = � (1 � �) ' x � e. �

For Phase II, we have the following lemma.

Lemma 3. For each e 2 E 2 and t 2 [T], we have E[Ye;t ] � � � 1 � ' � max(�; �) � y � e; t .

Proof. Consider a given t 2 [T], e = (i; j) 2 E 2 and k 2 Se. Let �1 = P e 0 2E 1 x � e 0 ae 0 ;k and �2 = P e 0 2E 2 ;t 0 <t y � e 0 ; t 0 ae 0 ;k. From Constraint (3) in LP (1), �1 + �2 � Bk.

Assume j arrives at time t, which occurs with probability pjt . Let U1 andU2;t be the respective (random) consumptions of resource k during Phase I and at the beginning of time t during Phase II. Notice that the event occurs that e is safe at t with respect to resource k, denoted by SFe;t;k, iff U1 +U2;t � Bk � 1 (since ae;k = 1).

Observe that E[U1] � P e 0 2E 1 E[RD(�x � e 0 ) � ae 0 ;k] � ��1. For each t 0 < t and j 2 J, let 1j;t 0 indicate if j arrives at t 0 . For each e 0 2 E 2 j , let 1e 0 ;t 0 indicate if e 0 is sampled when j comes at t 0 . Thus,

Substituting results on E[U1] and E[U2;t ] back to Equation (9), we have

The last inequality is due to �1 + �2 � Bk. Therefore, for the edge e = (i; j),

Thus, we get our claim.

Proof of main Theorem 1.

Proof. From Lemmas 2 and 3, the final online competitive ratio achieved by SAMP(�; �) should be min � � (1�� ) ' ; � � 1� ' � max(�; �) � � . By choosing � = � = 1=(2'), we see that the final ratio is 1=(4'). �

5 Experiments

5.1 The Bike Sharing Dataset and Preprocessing

We use the Citibike dataset in New York City,6 which contains the trip histories for trips and real-time data for hundreds of stations. Each trip record includes the starting station, the destination station, and the starting and ending time of each trip. In our experiments, we focus on the city of Manhattan.

6https://www.citibikenyc.com/system-data

�

We partition all stations into 50 sites by applying Kmedians clustering method, based on the geographical location and Manhattan distance. Note that the clustering method may converge to a local optimum. Basically, we have two kinds of sites, supplying sites with a large check-in amount and thus abundant bikes available, and demanding sites with a high check-out demand. Since not all sites are highly imbalanced, we focus on the rebalancing among the top 10 supplying sites and the top 10 demanding sites, which are denoted by C1 and C2, respectively. The total set of task types I = C1 � C2 and each i = (a; b) 2 I represents a task type of moving one bike from a 2 C1 to b 2 C2. Focus on the morning rush hour of 8 AM to 9 AM from Monday to Thursday in September and October of 2017 (34 days in total). For each a 2 C1 and b 2 C2, we first compute the average supply (sa) at site a and the average demand (db) at b and then set the final supply ca = � � sa for a and the final demand cb = � � db for b, where � is a parameter adjusting the scale of supply and demand overall. We assume that for TBR, one unit task of each type incurs a uniform cost � � 17, which captures the labor cost of loading one bike up and off a truck and the amortized cost of renting and operating a truck.

Now we discuss the setting for CBR. Let L be the collection of 50 sites. For each pair (c; d) 2 L � L, we create a worker type j = (c; d) such that j has the starting and ending sites of c and d, respectively. For a given worker of type j = (c; d), we set that it is qualified for task i = (a; b) if D(c; a) + D(b; d) � �, where D(�) refers to the Manhattan distance between two sites and � is a given threshold for the additional walking distance. For each assignment e = (i; j), the cost of payment for worker j is set as Cost(e) = � + (1 � �) D(c;a)+D(b;d) � , which consists of a basic rate � 2 [0; 1] (a parameter) and an incentive part proportional to the travel distance due to the rebalancing work. Here we scale down such that the largest cost of payment is 1 among all assignments in CBR.

For each worker of type j, we first compute the average number of trips r 0 j during the rush hour over the 34 days. Then we introduce a parameter � to adjust the degree of peak hour and set the final arrival rate r j = ��r 0 j and the total arrivals T = P j 2J r j . We consider a special arrival setting of KIID, where arrival distributions are assumed identical and independent throughout the online phase. This is mainly due to the short time window considered here (i.e., the rush hour of 8 AM to 9 AM). The same setting is adopted by [Zhao et al., 2019; Dickerson et al., 2018b] for ridesharing and crowdsourcing. After splitting the online phase into T rounds, the arrival distributions are set as pjt = pj = rj=T for every t 2 [T] and j 2 J such that P j2J pj = 1. For each task i, we assign it with a uniformly random weight wi 2 [0; 1] and assume all assignments with respect to i return a profit/weight of wi regardless of TBR or CBR. Set the default total budget as � � A, where � = 0:5 and A is the expected minimum cost of payment to complete all tasks. Since the average cost of CBR is less than that of TBR for each task, we set A as the product of the average cost of all assignments in CBR and the total number of all potential tasks (equal to min( P a2C1 ca; P b2C2 cb)). Algorithms. By default, we set � = 1 and test SAMP(�) (which is short for SAMP(�; 1)) with � = 1 and � = 0:8, respectively, against several heuristic baselines, namely Greedy and Greedy-Uniform. Note that for SAMP(1) and SAMP(0:8), they independently sample RD(x � e) and RD(0:8x � e) copies of edges for each e 2 E 1 . For each heuristic Greedy(�) with � 2 f0:2; 0:4; 0:6; 0:8; 1g, it first allocates at most a fraction � of the total budget (� � B) to Phase I and all the rest goes to Phase II. In Phase I, Greedy(�) greedily chooses edges e sequentially in a decreasing order of their weights until allocated budgets are exhausted. In Phase II when a worker of type j arrives, Greedy(�) will always assign j with an assignment e 2 E 2 j which has the maximum weight among all safe choices. Greedy-Uniform can be viewed as a randomized version of Greedy: it first samples a uniform value q 2 [0; 1] and then runs Greedy(q). For each given setting, we run all algorithms for 1000 times and take the average as the final performance. We compare the performance of each algorithm against the optimal value to the benchmark LP (1) and use that ratio as the final competitive ratio achieved. Note that the algorithms designed for the MBOA model [Dickerson et al., 2019] are applicable in Phase II only, a future direction is to construct a new LP for these algorithms which can capture the features of the TS-RA model.

7Later we will set the maximum cost of assignments in CBR is 1; thus, � can be viewed as the relative cost of TBR to CBR.

5.2 Results on the Real Dataset

Figure 1 (Left) shows the effect of �, which captures the relative ratio of cost in Phase I to that in Phase II. The results show that for each given � � 1:5, the performances of Greedy(�) decreases as � increases. What is more, the neighboring gaps widen when � increases. Observe that a larger value of � implies more costly TBR is and thus, it will be more profitable to allocate more budgets to Phase II. This explains why Greedy(�) achieves a higher ratio when � is smaller (thus a higher fraction of budget goes to Phase II). However, SAMP(1) and SAMP(0:8) universally beat all heuristics with a constant gap around 0:3 in the competitive ratios. Figure 1 (Middle) shows the effect of �, which captures the scale of supply and demand. Note that when � increases, we increase our default budget value A proportionally. Results show that all heuristics have an increasing performance though SAMP(1) and SAMP(0:8) strictly dominate all of them. This is due to the fact that the more resources we have (with a larger �), the less planning we need. Thus, the superiority of our LP-based policies is reduced when resources are more abundant. Figure 1 (Right) shows the effect of �, which captures the different scale of arrival rates of worker types. When � increases, we have more arrivals of low-cost workers in Phase II. Thus, we expect that the optimal policy will allocate more budget to Phase II. However, each Greedy(�) sticks with a fixed fraction of budget on each phase. This can explain why each Greedy(�) has a decreasing performance. Again, our LP-based policies dominate all the greedy-based heuristics.

Overall, Figure 1 suggests that our LP-based policies can optimize the budget allocation in Phases I and II to well respond to different costs in the two phases. Additionally, they have robust performances, which universally dominate all greedy-based heuristics under various settings. Furthermore, the ratios achieved by SAMP(1) and SAMP(0:8) are far larger than the lower bounds shown in Theorem 2, however. This is due to real-world settings are often faraway from the theoretical worst-case scenario.

6 Conclusions and Future Directions

In this paper, we proposed a unified model TS-RA, which incorporates both offline and online resource allocation into a single framework. Extensive experimental results on the real dataset show the robustness and effectiveness of our LPbased approaches in a wide range of settings. We observe that competitive ratios on experimental results, although guaranteed, are much above those theoretical lower bounds. This fact suggests that the hypothetical worst-case scenario has a structure faraway from those in the real world. A natural direction is to figure out the reasons behind the big gap between the actual performances and theoretical lower bounds. Can we improve the current ratio of 1=(4') further? Another interesting question is whether we can remove the requirement of a lower bound of budgets on all non-integral resources.

Acknowledgments

Yifan Xu and Jun Tao's research was partially supported by the CERNET Southeastern China (North) Regional Network Center, CIGRI and the National Key Research and Development Program of China (No. 2018YFB1800205). Pan Xu was partially supported by NSF CRII Award IIS-1948157. Jianping Pan's research was partially supported by NSERC and CFI of Canada. The authors would like to thank the anonymous reviewers for their helpful feedback.