INTRODUCTION

Assigning workers to tasks is a central challenge in various crowdsourcing platforms. For example, in mobile crowd-sensing [50,51], a central platform allocates mobile users to complex data collection and analysis tasks; in joint crowdsourcing [8,29], workers answer small questions with varying difficulties; and in spatial crowdsourcing [44,45], workers and tasks are matched in the context of a spatial metric space. Another type of such assignment, motivated by the COVID-19 pandemic, involves matching medical volunteers and workers to patients and medical tasks during an emergency.

More recently, a special class of worker-task assignment, called online task assignment (OTA), became popular in the literature. The basic setting is as follows: We have a set of offline tasks (known to us beforehand) and a set of online worker types. Each time a worker of a certain type arrives, an immediate and irrevocable decision is required: either reject the worker or assign her a task she shows interest in. Each assignment yields a known profit (uniform across all assignments or non-uniform); the goal is to design an allocation policy such that the (expected) total profit is maximized subject to various practical constraints such as the total budget for payments for workers, deadlines of tasks, and so on (see, e.g., Assadi et al. [6]). There are three common arriving assumptions for the online workers; see the list below.

-Adversarial Order (AO): the arrival sequence is completely unknown but fixed by an adversary; -Random Arrival Order (RAO): the arrival sequence is sampled uniformly at random from the set of all permutations over the unknown set of workers; -Known Independent Identical distributions (KIID): a random worker is chosen with replacement, from a known distribution each time.

Ho and Vaughan [21] considered OTA under RAO, where they assume the profit for each assignment has to be learnt. Assadi et al. [6] studied a budgeted version of OTA under AO and RAO; in the budgeted version, we have a global total budget and each assignment incurs a cost, which is the amount we need to pay the worker (this is equal to the bid the worker submitted for the task after arrival). The budgeted version of OTA and its generalizations have been systematically studied in the context of truthful mechanism design, where the goal is to elicit truthful bids from the online workers (see, e.g., References [17,18,[40][41][42]53]). In particular, Singer and Mittal [41] and Singla and Krause [42] considered the KIID setting, while Zhang et al. [53] and Subramanian et al. [43] considered the RAO setting.

In OTA, the main limiting assumption is that tasks are static (known in advance). This fails to capture various applications where the tasks are not all available at once but come at different times. Hassan and Curry [20] considered a variant of the worker-task assignment problem under the converse setting to that of the OTA, where the spatial tasks arrive dynamically over time while the workers are all available beforehand: the worker has to travel to the specific location of the task to finish it. Tong et al. [45] studied a generalized setting where both workers and tasks arrive dynamically: This was motivated by a spatial crowdsourcing platform on university campuses, where anyone on campus can both post micro-tasks (e.g., buying drinks or collecting a package), and perform tasks as a worker. They assumed that the arrival sequence of workers and tasks form a random permutation over the set of all possible workers and tasks, which is unknown to the algorithm (i.e., RAO). They tested their algorithms on two real-world crowdsourcing datasets, namely, gMission [11] and EverySender.

Inspired by the above works, we propose a model, called Online Task Assignment with Twosided Arrival (OTA-TSA), where both workers and tasks arrive online each from the KIID arrival setting. A known bipartite graph G = (U , V , E) is given as input (this graph is also called the compatibility graph throughout this article), where U and V represent the respective sets of workertypes and task-types and each type has a specific location attribute, and E represents whether a worker-type has expertise in a task-type or not. We have a finite time horizon T , in which vertices in U and V both arrive sequentially in each time-step. We make the common distributional assumptions on the arrival sequence. in each round (for a total of T rounds), a worker of type u is sampled from a known distribution over U , while simultaneously a task of type v is sampled from another known distribution over V independently. Once a task arrives, it has to be instantaneously and irrevocably be matched to one of the workers (from among the neighbors of the task in G) who have arrived before this time instance; we assume that once a worker joins the system they do not leave until matched to a task or the end of the time-horizon, whichever occurs first. Every assignment f = (u, v) yields a given profit w f , and our goal is to design an allocation policy such that the expected total profit is maximized (the expectation is over both the random online arrivals of workers and tasks and any internal randomization of the algorithm).

We now motivate the key assumptions in OTA-TSA.

Known independent and identical arrival distributions (KIID).

In many crowdsourcing platforms, one collects meta-data about the tasks and workers. This data is used to predict both the performance and the arrival patterns of workers and tasks (e.g., References [13,37,39,52,54]).

Hence the underlying compatibility graph G and the arrival sequence of tasks and workers is far from being adversarial. We can exploit the rich historical data to predict both the compatibility graph and the arrival distributions of workers and tasks. This motivates us to consider the KIID model, in which we assume the arrivals of tasks and workers follow two separate distributions that are known, identical and independent across the online phase. The KIID arrival setting has been adopted in many previous works (e.g., References [41,42,46]).

Retention in the system: workers versus tasks. In our model OTA-TSA, we assume that (a) once a task arrives, it has to be instantaneously and irrevocably assigned to one of the neighboring workers who has arrived so far or get rejected; and (b) once a worker arrives, it will stay in the system until being assigned. OTA-TSA is inspired by applications in market-based recommender systems where the two sides of the market are lopsided with more tasks than workers. One example is ride-hailing during peak hours, where drivers (workers) can be far outnumbered by riders (tasks) [38]. Any time a worker joins the system, they have an incentive to stay, since the lopsided numbers of workers and tasks imply that eventually a worker will be assigned to some task.

Adaptive versus non-adaptive algorithms. Non-adaptive algorithms are those whose strategies do not adapt to the (random) outcomes observed during previous rounds such as arrivals of online agents and realizations of random seeds used in algorithms. Otherwise, they are adaptive. Thus, a non-adaptive algorithm is a function mapping the time-step to an action, while adaptive algorithms map the history at the given time-step to an action. Competitive ratio. Consider an input instance of OTA-TSA, denoted by

where P u and P v represent arrival distributions of workers and tasks, respectively. Note that all information in I is accessible to any algorithm in advance. Consider an offline optimal (OPT), also known as "clairvoyant optimal, " which has the privilege of optimizing matching decisions after observing the full arrival sequence of online workers and tasks. In contrast, any (online) algorithm ALG must adhere to the instantaneous and irrevocable decision requirement upon the arrival of each task. Let E[OPT(I)] and E[ALG(I)] denote the expected performance of an offline optimal OPT and any given algorithm ALG on instance I, respectively, where both expectation is taken over randomness in the arrival sequences of workers and tasks and possible random bits in OPT or ALG itself. The competitive ratio of a maximization program, as studied in this article, is defined as inf

. Thus, when we say ALG achieves a ratio at least α ∈ [0, 1], it means that for any instance of the problem, the expected profit obtained by ALG is at least an α fraction of the offline optimal. Note that in our definition, the offline optimal can always get a profit w e with e = (u, v) when matching worker u to task v, irrespective of whether u comes before or after v. This is in sharp contrast with the definition in Reference [47], where they assume both the offline and the online algorithm adopt the same weight function w(u, v, t, s), which denotes the profit obtained when matching a supply agent u arriving at time t to a demand agent v arriving at time s. They set w(u, v, t, s) = 0 for all s < t, which ensures that the benchmark (i.e., offline optimal) and the online algorithm have the same set of available actions. This, however, makes the offline optimal defined in Reference [47] weaker (less powerful) than ours.

Our contributions. First, we propose a theoretical model, OTA-TSA, where both workers and tasks arrive online. We consider the arrival setting of KIID and assume that the distributions can be learned from historical data.

Second, we present a non-adaptive algorithm (NADAP) for the OTA-TSA, which is optimal among all possible non-adaptive algorithms (Section 4). We show that NADAP achieves a ratio of almost 0.3, which is larger than the 1/4 achieved by an adaptive algorithm shown in Reference [45] for the same problem but under the arrival setting of RAO. This is theoretical evidence showing the advantage of using historical data to predict the arrival distributions. Our main approach is to construct and solve an appropriate linear program (LP) and use that LP solution to guide online actions.

Third, we propose a few adaptive algorithms (see Section 6). The first one is a warmup algorithm, GREEDY. We show that it achieves a competitive ratio of at least 0.25 for the unweighted OTA-TSA; however the analysis is not tight. We conjecture that GREEDY obtains a ratio larger than 0.25, which is supported in part by the experimental analysis of Section 8. The second is an adaptive algorithm (ADAP) for OTA-TSA when all the edges incident to each worker-representing the set of all acceptable tasks for that worker-have the same weight, which is referred to as lefthand-side (LHS) vertex-weighted OTA-TSA. We show that ADAP achieves an improved ratio of nearly 0.34. To accomplish this, we construct and solve a stronger LP than the one used for the non-adaptive algorithm and combine this with ideas previously used for other online matching problems. The last algorithm is called SCALED, which can be viewed as a boosted version of NADAP: it samples an available worker for each arriving task following a strengthened distribution extracted from the LP. We show that SCALED achieves a competitive ratio of at least 0.355 for LHS vertex-weighted OTA-TSA.

Fourth, we show conditional and unconditional negative results for OTA-TSA: no (adaptive) algorithm can achieve a ratio better than 0.423 using the benchmark LP and 0.581 unconditionally, even for the unweighted case (Section 7). Note that Brubach et al. [9] gave an adaptive algorithm, which yields a ratio of 0.729 for the classical online matching on an unweighted bipartite graph under KIID but with only one-sided arrival. This formally corroborates our intuition that the complexity increases significantly from one-sided arrival to two-sided arrival. Table 1 summarizes the main theoretical findings in this article. Finally, we run numerical experiments to illustrate the various aspects of our algorithm. First, we run simulated experiments to show the behavior of the algorithm on various ranges of the input space. We illustrate when the proposed algorithm ADAP is better than GREEDY and when an algorithm like GREEDY suffices. Second, we use two real-world crowdsourcing datasets, namely, gMission [11] and EverySender [45] to show how to use this algorithm in practice. We find that despite having provable guarantees, we are able to obtain much better performance by using the GREEDY algorithm. Our experimental analysis also generalizes this model, where we assume that at each time-step a batch of workers and a batch of tasks arrive, respectively. Third, we use the Amazon product review dataset to simulate a modern recommender system and report the performance of our algorithm on this dataset.

In the analysis, we define and use a new technical tool, called two-stage birth-death process, which abstracts the random process into a general framework. This technical tool might be of independent interest to prove competitive ratios in other settings.

Closely-related works. Tong et al. [46] considered a similar online task assignment problem in spatial platforms, called Flexible Two-sided Online task Assignment (FTOA). The two models are incomparable. The work of Reference [46] posits that in each round a single vertex, either a worker or a task, is sampled from a known distribution; in contrast, we assume both a worker and a task are sampled according to two respective distributions independently in each round. Additionally, the work of Reference [46] assumes: (1) unit weights on all assignments (unweighted);

(2) the worker and task stay in the system until the deadline (known as input) after arrival; and (3) any available task-worker pair in the system can be matched (thus, a decision for the arriving vertex is not required to be immediate).

Recently, Truong and Wang [47] introduced a more general online bipartite matching model with two-sided arrival where the two sides are the supply and demand agents. Similar to our work, they assume that the supply and demand agents arrive in each time-step sampled independently from two known distributions. Also, they assume that once a demand agent arrives, it should either be immediately and irrevocably matched to an available supply agent or discarded. In their model, the arrival distributions of supply and demand agents can differ over time. Additionally, they assume that the supply agent departs from the system after a certain finite number of rounds. Finally, when matching a demand agent v arriving at time t to a supply agent u arriving at time s, they assume that the resulting (known) profit is jointly determined by the two matching agents and the difference in their arrival times. Under this general setting, they get lower and upper bounds on the competitive ratio of 1/4 and 1/2, respectively. Apart from the model, their work differs from ours in the benchmark as well. In particular, they have a weaker offline optimal benchmark compared to our work (see further discussion in the definition of competitive ratio). Collina et al. [12] considered a problem of two-sided arrival in a non-bipartite setting. They assumed both the arrival and departure of vertices are specified by a (specific) Poisson process and presented an online-matching algorithm that achieves a competitive ratio of 1/8. Recently, Aouad and Saritaç [2] considered a two-sided dynamic matching problem for both cost minimization and reward maximization. The key difference from our work is that in Reference [2], the performance of a policy is evaluated against an optimal online policy instead of an optimal offline as used here, where the former ratio is called approximation ratio, while the latter is called competitive ratio. The authors acknowledged that the benchmark LP there could have an arbitrarily large gap from the optimal offline performance. They cited that fact to justify their benchmark choice of an online optimal. A series of recent works ( [22,24,25] have considered the two-sided arrival model (called fully online matching) in the adversarial and random order arrival for unweighted graphs. Since the arrival settings there are more general than the one considered in this article, while the unweighted-graph assumption is stronger than those considered in this article, the results are not directly comparable.

Other related works. We now briefly overview related research for the classical online matching problem; for a more in-depth review, we direct readers to the survey by Mehta [35]. Ever since the seminal work [28], online matching and related models have received significant attention during the last two decades, partly fueled by Internet advertising businesses such as Google and Meta. In the basic model, we are given a bipartite graph G = (U , V , E) where U and V represent, respectively, the offline advertisers and online keywords (impressions). Each time a vertex v ∈ V arrives, we have to make an instant and irrevocable decision: either reject it, or assign it to an unmatched neighbor u ∈ U and obtain a profit w e for the match e = (u, v). The central problem is to design an online allocation policy such that the expected profit is maximized. Assumptions on the online arrival process leads to a landscape of different problems. Common arrival assumptions include adversarial order, random arrival order [23], and KIID [9,15,19,26,33]. Online (bipartite) matching models have wide applications beyond online advertising, e.g., online advance admission scheduling [48], kidney exchange and organ matching [3,5,34], social welfare maximization [1], efficient parking allocation [36], and dynamic recommendations [10,30].

Departing from the traditional one-sided arrival setting on a bipartite graph, there are several theoretical models that consider a full arrival setting on general graphs. Wang and Wong [49] introduced a full arrival setting on general graphs with fractional matching. The basic setting is as follows: in each round a single vertex arrives (in an adversarial order) and all its incident edges to previously arrived vertices are revealed; once a vertex v arrives, an online action of either rejecting v or (fractionally) matching it to its neighbors has to be chosen. Dutta and Sholley [14] considered a similar full arrival setting but assumed that each arriving vertex can be matched to only one of the d preceding vertices. Ashlagi et al. [4] studied another interesting variant of the full arrival setting where every agent stays in the system for at most d rounds after arrival and in any round we can match arbitrary pairs of agents currently present in the system. Huang et al. [22] considered a full arrival setting where an online action is required only at the deadline of the vertex. Table 2 provides an overview of the related works.

Roadmap. The rest of this article is organized as follows. We give a general statement of our problem in Section 2. We show our key technical tool, a two-stage birth-death process (TS-BDP), in Section 3 and the benchmark linear program in Section 4. We present one non-adaptive and three adaptive algorithms and related online-competitive analysis in Sections 5 and 6 and offer conditional and unconditional negative results in Section 7. We describe our experimental results in Section 8, offer detailed proofs involved in TS-BDP in Section 9, and conclude our article in Section 10.

PROBLEM STATEMENT

Before describing our OTA-TSA model, we define the following terminologies. We group a set of similar tasks and call them "task types. " Similarly, we group similar workers and call them "worker types. " For example, in the context of spatial crowdsourcing, all workers present around a particular location belong to a single worker type.

Our model is as follows. We have a bipartite graph (known to the algorithm) G = (U , V , E), where U and V represent the set of worker-types and task-types, respectively, and E represents the set of worker-task pairs that are "compatible, " i.e., (u, v) ∈ E iff any worker of type u shows interest toward tasks of type v. We have a finite time horizon T (known beforehand) and for each time t ∈ [T ] {1, 2, . . . ,T }, a worker u from U and a task v from V is sampled (we also say u or v arrives or comes interchangeably) independently from known probability distributions P u = {p u } and Q v = {q v }, respectively, with u p u = 1 and v q v = 1. The sampling process is independent across the whole online T time-steps (or rounds). Note that under the current setting, the total number of arrivals of workers is equal to that of tasks, and both are equal to T .

At each time t ∈ [T ], we first observe the online arrivals from U and V (in that order), say u and v. We then need to make an instantaneous and irrevocable decision to either reject v or assign v to one of its available compatible workers in U . For each u ∈ U , once it arrives, it will stay in the system until being assigned to some task. 1 In our model, we assume that each u has an integral arrival rate,foot_2 i.e., T • p u is an integer for every u, and thus, we can further assume w.l.o.g. this integer to be 1 (by splitting each u into T • p u copies). 3 Hence, we have that |U | = T and p u = 1/T for all u. Similar to most of the theoretical works in online matching [9,19,26,33], we assume T 1 and some of our results are obtained when assuming T approaches infinity. Note that these two assumptions (i.e., T 1 and T • p u being an integer) are mild. When T is small, we can use a dynamic programming-based solution at each time-step to solve it to near optimality. And when T → ∞, the quantity T • p u is arbitrarily close to an integer. We associate a non-negative profit w f with each assignment f = (u, v). Let r v = T • q v denote the expected number of arrivals of v Table 3. Glossary of Notation and Acronyms Used

[T ]

Set of times that is equal to {1, 2, . . . ,T } with T being the whole time horizon. G = (U , V , E) Input compatibility graph where U and V are sets of worker and task types, respectively. during the T rounds, which is referred to as the arrival rate of v. We assume this rate to be any number between [0, 1] (upper bounding it by 1 is again w.l.o.g. via simple scaling). Our goal is to design an online-assignment policy such that the total expected profit of all assignments made is maximized.

Throughout this article, we use edge f = (u, v) and the assignment of v to u interchangeably. Additionally, when we say at time t ∈ [T ], we mean we are at the beginning of time t either before or after observing the arrivals from U and/or V (clarified in the context) but definitely before the algorithm has made any online action. Table 3 offers a glossary of notation and acronyms used in this article.

TWO-STAGE BIRTH-DEATH PROCESS

We propose a new stochastic process, TS-BDP, and use it as a main technical tool to analyze our algorithms and derive negative results. Readers may wish to skip this section temporarily to get a coherent picture of how we design and analyze our algorithms: the technical tools presented here are solely for theoretical analysis purposes.

The process (described on random variables {X t , Y t } and parameterized by values p and q) is described as follows. Consider a stochastic process with a time horizon T such that, (1) the process starts at t = 1 with X 1 = 0; (2) at every round t, first there is a birth event followed by an independent death event. For the birth event, we have Y t = X t + 1 with probability p/T and Y t = X t with probability 1p/T . For the death event, it has a left boundary point at 0; i.e., if Y t = 0, then X t +1 = Y t , else when Y t ≥ 1, we have X t +1 = Y t -1 with probability q/T and X t +1 = Y t with probability 1-q/T . We refer to p and q as the birth and death rates of TS-BDP, respectively. TS-BDP differs from the classical birth-death process (BDP), since in BDP we have that in every round, either a (random) birth or a death event occurs while in TS-BDP the two events occur independently in a sequential manner (the birth event is followed by the death event). Thus, TS-BDP is a special case of non-uniform BDP. (TS-BDP is a BDP with a time-horizon 2T where every odd step is a birth event and every even step is a death event.) Definition 3.1. A two-stage birth-death process parameterized by (T , p, q) (time horizon, birth rate, death rate) refers to a sequence of random variables {X t , Y t |t ∈ [T ]} ∪ {X T +1 }, which satisfies Fig. 1. The random process in a single round of the two-stage birth-death process (TS-BDP) parameterized by (T , p, q). TS-BDP starts with X 1 = 0 and consists of T rounds; in each round, it first goes through a birth process of rate p ≥ 0 and then followed by another independent death process of rate q ≥ 0.

(1) 1 offers a depiction of the random process in a single round.

In this article, we are particularly interested in the case when p = 1, q ≥ 0 is a constant for a sufficiently large T (T → ∞). We denote this specialization with TS-BDP(1, q) (or TS-BDP(q) when the context is clear). For every t ∈ [T ], let Δ(t,T ) := Y t -X t +1 and Δ(T ) := t ∈[T ] Δ(t,T ), the latter can be interpreted as the total number of death events in which Y t gets decreased by 1. Let κ(q) := lim T →∞ E[Δ(T )]. We now state some useful lemmas that we will use later. The detailed proofs are deferred to Section 9 and they involve computer-aided computations that were done on Mathematica 10. All numerical results are precise up to the third decimal place. Lemma 1. (1) κ(0) = 0, (2) κ (0) = 1/e, where κ (0) is the first (right) derivative of κ(q) at q = 0.

e(e-1) ) ≥ 0.343; and (3) κ(1 + 1 e-1 ) ≤ 0.423. Lemma 3. κ(q) is non-decreasing and concave over q ∈ [0, ∞].

BENCHMARK LINEAR PROGRAM (LP)

As is common in this line of work, our algorithms use optimal solutions to LP constructed on the offline (expected) graph as a guide to the online algorithm. Additionally, this benchmark LP is used to upper bound the expected value of the optimal solution on a particular (offline) instance. Hence to compute a lower bound on the competitive ratio, it suffices to compute the ratio of the reward obtained by the algorithm to the optimal solution of this benchmark LP. We now describe the benchmark LP we use for our non-adaptive algorithm. Later, we show that this can further be strengthened based on some observations, which is used in our adaptive algorithm. We associate a variable with every edge f in the graph. For each edge f , x f denotes the expected number of matches in any offline optimal matching. For each u (resp. v), let E u (resp E v ) be the set of its neighboring edges. Consider the following LP:

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

Proof. Let x := (x f ) denote the optimal distribution over the edges for the offline optimal. We now argue that x is feasible for this linear program, which yields the lemma above. Constraint Equation ( 2) captures the fact that the expected total number of matches incident to a task v is no more than the expected number of arrivals of v. The same reasoning applies to Constraint Equation (3) but for workers. Constraint Equation ( 4) follows from the fact that the expected number of matches is non-negative. The objective function computes the expected reward obtained in the optimal offline solution. Thus, we claim that for any offline optimal, (x f ) should be feasible to the LP above. We therefore have that LP Equation ( 1) is a valid benchmark LP, i.e., its optimal value is an upper bound on the offline optimal.

Throughout the article, we use (x * f ) to denote an optimal solution of benchmark LP (or the stronger LP we define later, as appropriate).

NADAP: A BEST POSSIBLE NON-ADAPTIVE ALGORITHM

In this section, we present a non-adaptive algorithm, denoted by NADAP, which is optimal among all possible non-adaptive algorithms. Algorithm 1 describes our algorithm formally. Proof. Consider a given u. Let X t and Y t be the number of copies of u before and after the arrival process for U at time t, respectively. From the assumption that u arrives with probability 1/T in each round, we have Y t = X t + 1 with probability 1/T and Y t = X t with probability 1 -1/T . From NADAP, we have that if Y t ≥ 1, then it decreases by 1 with probability

T and it remains unchanged with the remaining probability (here

From the definition of TS-BDP in 3.1, we have that {X t , Y t } is a TS-BDP(1, x * u ) with a time horizon of T .

Matching Tasks and Workers under Known Arrival Distributions

6:11

Let A f be the (random) number of matches for f = (u, v) in NADAP across the T online rounds. Thus, we have

From Lemma 3, we have that κ is non-decreasing and concave over [0, 1]. Thus, κ(x )-κ(0)

x -0 should be non-increasing over x ∈ [0, 1]. We also have that κ(0) = 0. Therefore,

This implies that we have that

. Since LP Equation ( 1) is a valid upper bound on the performance of an optimal offline, by linearity of expectation, we have that NADAP achieves a competitive ratio of κ (1).

Negative results for non-adaptive algorithms. We now show that any algorithm that is nonadaptive, cannot achieve a ratio better than κ (1). In particular, we prove the following lemma. Let OPT-A and OPT-B be the offline optimal algorithm and online optimal non-adaptive algorithm, respectively. With a slight abuse of notation, we use OPT-A and OPT-B to denote the corresponding performance as well. Observe that OPT-A = T for every offline instance. Now, we analyze OPT-B. Since the probability that any v comes at least twice across the T rounds is arbitrarily small (when T → ∞), hence it suffices for OPT-B to specify the online matching policy only for the case when v comes for the first time. Let the policy in OPT-B be {x

Consider a given u. Let Z u be the expected number of matches of u in OPT-B across the T online rounds. The number of copies of u at t before and after an arrival from U can be captured by a TS-BDP with a birth rate of 1 and a death rate of x u /T , i.e., the corresponding probabilities of a birth and death events are 1/T and x u /T 2 , respectively. Thus, by definition, we have

Define α u := x u /T . We have u α u ≤ T due to the fact that u x u ≤ T 2 . Consequently, The (optimal) performance of OPT-B can be obtained by solving a maximization program as follows: max

From Lemma 3, we have that κ(q) is non-decreasing and concave when q ∈ [0, ∞]. This implies that the maximization Program ( 5) is maximized when α u = 1 for everyu, and the resulting optimal value is T • κ (1). Thus, we have that OPT-B achieves an online competitive ratio of κ(1) on this example.

ADAPTIVE ALGORITHMS 6.1 Warmup: Greedy

Our greedy algorithm is formally stated in Algorithm 2 as follows.

ALGORITHM 2: Greedy Algorithm (GREEDY) Note that for the unweighted case (i.e., when all assignments have unit weights), GREEDY will choose an arbitrary available worker u when a task v arrives. We show that for the unweight case, GREEDY achieves an online competitive ratio at least 1/4. Theorem 6.1. GREEDY achieves a competitive ratio of at least 0.25 for the unweighted OTA-TSA.

Proof. The arrival setting of random arrival order (RAO) is stricter than that of KIID as studied here. In the RAO, an adversary (with no information of the algorithm) selects two independent uniform random permutations over U and V , σ and π , respectively. At each time-step t ∈ [T ], the algorithm observes a worker σ (t) and a task π (t). As shown in Reference [27], a lower bound on the competitive ratio of any algorithm under RAO is also one for the KIID model. Thus, it suffices to show that GREEDY achieves a competitive ratio of at least 0.25 for the unweighted OTA-TSA under RAO.

Consider a graph G = (U , V , E) and assume w.l.o.g. that |U | = |V | = T . At time t, the algorithm sees a neighbor u of π (t) such that σ -1 (u) ≤ t. Let G(σ , π ) be the graph of G under (σ , π ) such that all vertices in U and V are re-ordered under σ and π , respectively, and where an edge f = (u, v) ∈ E exists iff σ -1 (u) ≤ π -1 (v). Note that GREEDY computes a maximal matching for G(σ , π ). Let GREEDY(σ , π ) be the total number of matched edges and OPT(σ , π ) be the size of the maximum matching. Since GREEDY computes a maximal matching, this implies GREEDY(σ , π ) ≥ OPT(σ , π )/2.

where OPT refers to the size of the maximum matching on G.

The last inequality is obtained as follows. Let M be a maximum matching of G with OPT = |M|.

Adaptive Algorithm ADAP for the LHS Vertex-weighted Case

In this section, we consider a relaxed version of the problem where for any u ∈ U , all edges in E u have the same weight w u ≥ 0. We refer to this relaxed version as OTA-TSA with LHS vertex-weighted. For this relaxation, one can strengthen the benchmark LP Equation (1) due to the following observation: the probability that an edge can be matched is at most that both the worker and the task is present at least once in the arrival sequence. This boils down to computing the expected value of the minimum of two i.i.d. Poisson random variables with mean upper bounded by 1. We later show that this expected value is at most (1 -1/e) •r v and hence adding this stronger constraint, we obtain the following stronger LP Equation (6). As a side note, this constraint is also valid for the general version of edge-weighted OTA-TSA, but the simpler LP Equation (1) suffices for an optimal non-adaptive algorithm. max

Lemma 6.2. The optimal value to LP Equation ( 6) is an upper bound of the offline optimal for the OTA-TSA with LHS vertex-weighted.

Proof. Consider a given edge f = (u, v). For any offline instance, let X u and X v be the respective number of arrivals of u and v and X f be the corresponding number of matches for edge e in an offline optimal. We have that X

From our arrival assumption, we have that X u is the sum of T i.i.d. Bernoulli random variables each with mean 1/T . Thus, X u ∼ Pois(1) when T → ∞. Similarly, we have that X v ∼ Pois(r v ). Hence, we have the following:

The inequality Equation (11) on the second line is due to the following fact: for any given integral k ≥ 1, we have Pr[Pois(1) ≥ k] ≤ 1 -1/e. The inequality Equation (11) becomes tight when r v ∼ 0.

Our adaptive algorithm is inspired by the work [33]. Let {x * f } be an optimal solution to LP Equation (6). Every time when a task v arrives, we generate a random ordered list L of two choices from E v such that it satisfies the below two properties.

where L(1) and L(2) denote the first and second choices on this list L, respectively.

Later in this section, we will describe how to efficiently generate a random list satisfying Properties (P1) and (P2). Note that Property (P2) relies critically on the new constraint Equation ( 9) added into LP Equation (6). The main idea of ADAP is as follows: Upon the arrival of an online task v at time t, we first generate random list L with respect to v, and then check the availability of the first choice L(1) and the second choice L(2) sequentially; make it if it is available. Compared with NADAP, ADAP gives every edge f a second chance to be potentially matched. Property (P1) ensures that the marginal distribution is same as that of the optimal LP solution for the first choice; Property (P2) gives a lower bound on the event that every f is tried as a second choice-a high-enough lower bound ensured by Property (P2) is the reason we have an improvement on the final ratio over the NADAP. Algorithm 3 formally describes ADAP.

ALGORITHM 3: An adaptive algorithm (ADAP)

1 Let v be a task arriving at time t ∈ [T ]. 2 Generate a random list L satisfying Properties (P1) and (P2). 3 If the first choice L(1) is available, then assign v to L(1); else, if the second choice L(2) is available, then assign v to L(2); otherwise, skip v.

Theorem 6.3. The adaptive algorithm ADAP achieves a competitive ratio of at least κ 1+ 1 e(e-1) ≥ 0.343 for the OTA-TSA with LHS vertex-weighted.

Proof. Consider a worker u. Let X t and Y t be the number of copies of u at time t before and after observing an arrival from U . From the problem assumption u arrives with probability 1/T in each round and thus we have Y t = X t + 1 with probability 1/T and Y t = X t with probability 1 -1/T .

Consider the case when Y t ≥ 1 and a compatible task v of u arrives at t. Let L be the random list that is generated for v at t. From ADAP, we have that Y t decreases by 1 iff either (1) the assignment f = (u, v) is made as a first choice (L(1) = f ) or ( 2) the assignment f = (u, v) is made as a second choice (L(2) = f ) and the first choice L(1) is unavailable. Thus, we have the following:

The inequality on the second line follows from Properties (P1) and (P2). The inequality on the third line is due to the fact that any given L(1) = (u , v) will be unavailable with probability at least (1 -1/T ) t ≥ 1/e (this refers to the probability that u never comes in the first t time-steps). Thus, summing over all the neighbors of u, we have

We have that {X t , Y t } is a TS-BDP with death rate at least

e ). From the definition of the function κ, we have that κ(x * u •q) is equal to the expected number of matches for worker u. Note that x * u is the expected number of matches for u in the benchmark LP Equation (6). Thus, the resultant ratio is at least

The inequality above is due to the fact that κ(q) is a concave function when q ∈ [0, ∞], and that x * u ≤ 1 due to Constraint on u in LP Equation (6).

Matching Tasks and Workers under Known Arrival Distributions 6:15

Generating a Random List L Satisfying Properties (P1) and (P2)

The list satisfying the two properties is primarily generated via a randomized procedure that introduces negative correlations. In what follows, we describe two different approaches, both satisfying the required properties.

The first approach. This idea is due to Manshadi et al. [33]. For every

has the meaning that we do nothing when v comes). Create two unit intervals, I 1 and I 2 as follows: (1) Sort {y f | f ∈ E v } ∪ {y f } in an increasing order; let y f 1 ≤ y f 2 ≤ . . . ≤ y f n be this order; (2) Let S i be a segment of length y f i with a label f i for each i ∈ [n]. Let I 1 be the unit interval formed by ordered segements (S 1 , S 2 , S 3 , . . . , S n ) and let I 2 be another unit interval formed by (S n , S 1 , S 2 , . . . , S n-1 ). The random list L based on (I 1 , I 2 ) as follows: (1) Choose a value x ∈ [0, 1] uniformly at random; (2) Let I 1 (x) and I 2 (x) be the labels of the segments where x falls in on the two unit intervals I 1 and I 2 , respectively; Set L(1) = I 1 (x) and L(2) = I 2 (x).

Lemma 6.4. The random list L generated by the above procedure satisfies Properties (P1) and (P2).

Proof. To prove Property (P1), notice that x takes a value in [0, 1] uniformly at random. Thus each f ∈ E v , x falls in the segment labelled by f in I 1 with probability

). Consider the other case y f > 1/2. The event (L(2) = f ∧ L(1) f ) occurs only when the random value x falls in the segment labelled by f in I 2 and x does not fall in the segment labelled by f in I 1 . Therefore,

The last inequality follows from y f = x * f /r v ≤ 1 -1/e for every f ∈ E v that is due to Constraint Equation (9).

A second approach. This idea is based on a modified version of dependent rounding (DR) [16] as shown in Reference [9], which accepts a more efficient implementation in practice. First, create a star graph with edge set

f . Second, multiply each value y f by 2 and apply the dependent rounding technique [16] to this modified vector y = (2y

with the respective probabilities of 1/2 and 1/2. We justify that L satisfies Properties (P1) and (P2) as follows. Lemma 6.5. The random list L generated by the above DR-based procedure satisfies Properties (P1) and (P2).

Proof. We prove Property (P1) first. Consider a given edge f ∈ E v with y f ≤ 1/2. In this case, we have Y f ∈ {0, 1}. Since marginal distribution is maintained in DR [16], we see that Pr

For the other case y f > 1/2, we see that Y f = 1 with probability 2 -2y f and Y f = 2 with probability 2y f -1. Thus,

Now, we show Property (P2). Consider a given edge

As for the case y f > 1/2: We see that with probability 2 -2y f , Y f = 1. Thus,

The above analysis is similar to that in the proof of Lemma 6.4.

Another Adaptive Algorithm

SCALED for the LHS Vertex-weighted OTA-TSA Recall that LP Equation ( 6) is a valid benchmark LP for the LHS vertex-weighted OTA-TSA. Let (x * f | f ∈ E) be an optimal solution to LP Equation ( 6). The adaptive algorithm SCALED presented below can be viewed as a boosted version of NADAP. The main idea is as follows. Suppose a task v arrives at some time t ∈ [T ], and let E v,t be the set of available edges incident to v at time t after observing the arrival from U . If E v,t is empty, then do nothing; otherwise, sample an edge f ∈ E v,t with probability x * f / f ∈E v, t . Note that (1) E v,t is not a multi-set: some neighbor u of v may have multiple copies at time t after the arrival from U , and in this case, we add only one copy f = (u, v) into E v,t ; (2) E v is deterministic (specified by the input compatible bipartite graph G), while E v,t is stochastic, whose outcome is determined jointly by the arrival sequences from the two sides and the random actions chosen by the algorithm up to time t. ALGORITHM 4: An adaptive algorithm for OTA-TSA: SCALED.

1 Let v be a task arriving at time t ∈ [T ] and E v,t be the set of available assignments with respect to v at t after observing the arrival from U .

Theorem 6.6. Algorithm 4, SCALED, achieves a competitive ratio at least 0.355 for the LHS vertexweighted OTA-TSA.

Proof. Consider a given worker u. For each given t ∈ [T ], let A t = 1 indicate that worker u arrives at time t and gets matched at some later time t ≥ t, t ≤ T . Thus, E[A] with A = t ∈[T ] A t denotes the expected number of times that u gets matched. In the following, we lower bound E[A]/τ that yields a competitive ratio for SCALED.

Assume u arrives at some time t ∈ [T ] with probability 1/T (denoted by X u,t = 1). For each given t ∈ {t, t + 1, . . . ,T }, let α t be the probability that u gets matched at time t assuming ū remains unmatched at t . For each u ∈ U and t ≤ t ≤ T , let χ u ,t = 1 indicate that u is available at time t (after the arrival of U and before any actions of the algorithm). Observe the following chain of reasoning, where the first inequality follows from Jensen's inequality applied to the function z → 1/z: specifically, we use the fact that if the λ i 's are non-negative constants and the Z i 's are non-negative random variables, then

Matching Tasks and Workers under Known Arrival Distributions 6:17

from Constraint Equation ( 7):

from Constraint Equation ( 9):

Thus, the probability that an arrival of u at time t gets matched should be

where the "o(1)" is a vanishing term when T → ∞. Summarizing the analysis thus far, we have

We can numerically verify that д(x * u )/x * u is decreasing over x * u ∈ [0, 1] with д(x * u )/x * u ≥ д(1) ∼ 0.355. We thus establish a lower bound on the competitive ratio of SCALED for the LHS vertexweighted case.

NEGATIVE RESULTS

We now show some negative results, i.e., upper bounds on the competitive ratio that any algorithm can achieve. All our results hold even in the simpler case of unweighted OTA-TSA when all edges take a uniform weight.

Conditional Negative Results

Theorem 7.1. No algorithm can achieve a competitive ratio better than κ(1 + 1/(e -1)) ∼ 0.423 based on LP Equation (6) even for the unweighted OTA-TSA.

Proof. Consider an unweighted star graph, where we have one single worker u with p u = 1/T , which is connected to T tasks each having r v = (1/T )/(1 -1/e). We can verify LP Equation ( 6) has an optimal solution such that x * f = 1/T for all the T edges and an optimal LP value equal to 1. Now consider an optimal online algorithm, denoted by OPT. We see that every time upon the arrival of any v, OPT will match it to u as long as there is one copy of u available then. Note that in each round, u arrives with probability 1/T , while one of the T tasks arrives with probability v r v /T = (1/T )/(1 -1/e). By the definition of TS-BDP in 3.1, OPT has an expected number of matches equal to κ(1/(1e)). Thus, we claim that on this example, OPT achieves a competitive ratio no more than κ(1/(1e)) ∼ 0.423 by Lemma 2.

Unconditional Negative Results

We now present an unconditional negative result that is independent of the choice of the benchmark LP. The result stems implicitly from the nature of the online process and can be viewed as the online-offline stochastic gap. In particular, we have the following theorem: Theorem 7.2. No algorithm can achieve a competitive ratio better than κ (0)

1-1/e = 1 e-1 ∼ 0.581 even for the unweighted OTA-TSA.

Proof. Consider an unweighted bipartite graph G = (U , V , E), where |U | = |V | = T and |E| = T , which consists of a perfect matching. Let the arrival rates for every u be 1 with p u = 1/T and let every v have an arrival rate of ϵ (where ϵ is arbitrarily close to 0) with p v = ϵ/T . We assume that there exists a dummy node v such that p v = 1ϵ with v having no neighbors.

Consider a given f = (u, v). Let OPT-A and OPT-B be the respective offline and online optimal algorithms. Let X f be the number of matches of f in OPT-A after the T rounds. Let X u and X v be the respective number of arrivals of u and v in an offline instance. We have that X f = min(X u , X v ). Observe that X u ∼ Pois(1) and X v ∼ Pois(ϵ). Thus, we have

Hence, we have that

Matching Tasks and Workers under Known Arrival Distributions

6:19

Let Y f be the number of matches of f in OPT-B. Similar to the proof in Theorem 5.1, we have E[Y f ] = κ(ϵ). Thus, the ratio on the above instance is

.

Taking ϵ → 0, we have that the above value is

From Lemma 1, κ (0) = 1/e; thus, we get our claim.

EXPERIMENTS

In this section, we describe the experimental results in this article. We implement the adaptive and non-adaptive algorithms on both a simulated setup and a public ridesharing dataset collected in the city of Chicago.foot_6

Preprocessing of a real-world dataset. The dataset has more than 169 million trips since November 2018. Each trip record includes the following information: departure and arrival timestamps, pick-up and drop-off locations, and some other information like the total fare. Following the idea in Reference [31], we use the community area to divide the Chicago into 77 regions and categorize all trips according to the predefined community areas. In the context of ridesharing, we assume that driver-types and request-types represent the worker-types and task-types in the OTA-TSA model, respectively. We group the drivers into a "type" if they share the same community area. Similarly, we group the requests into a "type" if they share the same starting and ending community areas.

In this way, we end up with 77 driver-types and 77 × 77 = 5929 request-types.

To precisely construct the compatibility graph between the drivers and requests, we focus on the rush hour from 18:00 to 19:00 between August 1 and August 5 in 2022, and we have 36,907 trips in total. By categorizing these trips according to the 77 predefined community areas, we have 2,661 trip types, each associated a capacity of c. Inspired by the setting in Reference [38], we continue to filter out those trip types with capacities no larger than 10 and sample 200 trip types randomly, and thus, we get the set of driver-types U with |U | = 52 and the set of requesttypes V with |V | = 200. Here, we construct the arriving distribution among requests by setting

Similarly, the arriving probability for each driver-type u ∈ U is computed as p u = c u / u ∈U c u . We add an edge between a driver and a request type if the community area of driver type is the same as the starting community area of request type. In the edge-weighted case, for each edge f = (u, v), we use the averaged total fare of request-type v as the final weight of w f ; while in the LHS vertex-weighted case, we use the averaged total fare of driver-type u instead. The detailed setting of all other parameters can be found in Table 4.

A synthetic dataset. We generate the bipartite graph by setting the parameters of |U |, |V | and T as shown in Table 4. Note that we set the number of copy for each driver-type as 1, such that the total number of drivers arriving is the same as |U |. We further assume that all driver-types have the same arriving probability p u = 1/T for every u ∈ U . Hence, with probability 1 -|U |/T , no drivers will arrive in each round t ∈ [T ]. We generate the request-type arrival probabilities by choosing a random vector {q v } such that each q v is uniformly distributed over [0, 1] conditioning on v q v = 1. For each pair of u and v, we add an edge between them with probability 0.2. In the edge-weighted case, for each edge f = (u, v), we choose a value from [0, 1] uniformly at random and set it as w f . While in the LHS vertex-weighted case, for each driver-type u, we generate w u from [0, 1] uniformly at random, and then set w f = w u for all edge incident to u.

Algorithms. We implement all the algorithms analyzed in the article, namely, NADAP, GREEDY, ADAP, and SCALED. Additionally, we test one heuristic, denoted by UR, which selects one of the available drivers uniformly at random upon every arrival of rider. Observe that both GREEDY and UR are agnostic to the underlying LP.

Results and discussion. We run two types of experiments by varying either the total number of rounds T (i.e., the total number of requests' arrivals) or the total number of drivers's arrivals, while keep all other parameters fixed, as shown in Table 4. For each instance, we run all algorithms 100 independent trials and take the average as the final performance. The competitive ratios are computed as the ratio of the averaged performance to the optimal value of the corresponding LPs. 5We also report the 95% confidence intervals to keep track of the robustness. Figure 2 shows that the proposed NADAP algorithm always stays above its theoretical lower bound of 0.295, as suggested in Theorem 5.1. This suggests the tightness of our theoretical analysis. Additionally, we see that SCALED is the clear winner in almost all the instances for the edgeweighted case except when T is extremely small, as shown in Figures 2(a) and 2(c). Observe that when the total number of rounds (T ) is small, each arriving request has a limited number of drivers to choose from, since the number of drivers who have arrived and are compatible is small. In this case, the advantage of greedily matching an available driver outweighs the potential loss from a mismatch. However, when T increases and each arriving request has more options to choose from, the guidance from the LP becomes increasingly crucial, since it takes the future arrivals into consideration (in expectation). This also explains why ADAP beats GREEDY as T increases in the synthetic dataset. Figure 2(b) shows that as the total number of drivers increases, the competitive ratios of GREEDY and UR (the lines for these two algorithms are overlapped) both increase. This is because more available drivers make it less necessary to optimize the matching process. Note that ADAP outperforms GREEDY in the synthetic dataset, but not the real one. This is partially due to that we have less driver-types in the real dataset compared with the synthetic. Thus, we have lower density for the driver arrivals and less need to reserve drivers as ADAP does.

Figure 3 shows that, for all tested instances, the competitive ratios achieved by ADAP and SCALED always stay above their corresponding theoretical lower bounds, i.e., 0.343 (Theorem 6.3) and 0.355 (Theorem 6.6), respectively. We notice that the three algorithms, GREEDY, SCALED and UR, all have a similar performance and outperform the rest two. This is expected, since the LHS vertex-weighted setting reduces variations among edge weights, which gives favor to LP-agnostic algorithms.

Matching Tasks and Workers underKnown Arrival Distributions 6:21

PROOFS OF KEY LEMMAS IN THE BIRTH-DEATH PROCESS

Consider a two-stage birth-death process {X t , Y t |t ∈ [T ]} ∪ {X T +1 } with a birth rate of 1, a death rate of q ≥ 0, and a finite-time horizon T (denoted by TS-BDP(q)). Recall that Δ(T ) is the (random) number of death events (i.e., Y t gets decreased by 1) in the T rounds, and κ(q) = lim T →∞ E[Δ(T )]. The random process of TS-BDP(q) can be viewed equivalently as follows. First, we generate a random binary string S of length T such that each S(t) ∼ Ber(1/T ) with t ∈ [T ], i.e., each S(t) is an independent Bernoulli random variable with mean 1/T . We call S the "birth" string. Second, we apply a "death" process to the random birth string S = S ∈ {0, 1} T as follows.

For a given T and S = S, we refer to the above death process applied to S with death rate q as DP(T , S, q).

Proof of Lemma 1

Lemma 1. (1) κ(0) = 0, (2) κ (0) = 1/e, where κ (0) is the first (right) derivative of κ(q) at q = 0. Proof. This Lemma is proved via the following two observations.

-When q = 0, for any given S = S ∈ {0, 1} T , we have Δ S (T ) = 0, since Δ(T ) = 0 and thus κ(q) = 0. -First, note that we have κ (0) = lim q→0 κ(q) q . Additionally, when T → ∞, and S is the all-ones string, we have D ∼ Pois(q). This implies that lim

Moreover, we have that lim

Thus, we have

Plugging the above expression back into Equation ( 12), we have 3) κ(1 + 1 e-1 ) ≤ 0.423. Proof. We prove a stronger version of the Lemma, where we consider an arbitrary given q ≥ 0. Recall that Δ(T ) is the expected number of "death" events (i.e., Y t decreases by 1) in the TS-BDP(1, q). Hence, κ(q) = lim

Using computer-aided proof, we have that F 2 (q) lim T →∞ F 2 (T , q) = e -q-1 e q (1 -2q) + e q+1 (q -1) + q + e -1 q -1 .

Finally, we have that Thus, from Equation ( 13), we have F 1 (q) + F 2 (q) ≤ κ(q) ≤ F 1 (q) + F 2 (q) + Notice that |S | = t -1 and therefore from induction, we have that f a,S ≤ 0 for all a and S ∈ {0, 1} t . Therefore, we claim that Property (P1) holds for the case of t. Now, we show that Property (P2) holds for the case of t as well. We split the proof into two cases.

-Case 1: a ≥ 2. In this case, we have that f a,Sf a-1,S = (1p) f a,Sf a-1,S + p f a-1,Sf a-2,S + f a-1,Sf a-2,S -(f a,Sf a-1,S )

From the inductive hypothesis for Property (P2) and Claim 3, we have that f a,S ≥ f a-1,S . -Case 2: a = 1. In this case, we have f 1,Sf 0,S = (1p) f 1,Sf 0,S + 1 -(f 1,Sf 0,S ).

From the inductive hypothesis for Property (P2) and Claim 3, we have that f 1,S ≥ f 0,S .

Following a similar analysis to above, we can show the case when S[0] = 1. Therefore, we establish our claim. Claim 3. For any S and a ≥ 2, we have that (1) f a-1,Sf a-2,S -(f a,Sf a-1,S ) ≥ 0 and (2) 1 -(f 1,Sf 0,S ) ≥ 0.

Proof of Claim 3. Recall that f a,S with |S | = T denotes the expected number of death events during the generalized death process with a initial count set as a ≥ 0 and a fixed birth string S ∈ {0, 1} T . Consider a given death string S * ∈ {0, 1} T , where S * (t) = 1 indicates a checking point. The two-stage birth-death process with an initial count a ≥ 0, a given birth string S, and a given death string S * , denoted by TS-BDP(a, S, S * ), goes as follows: (i) Set C = a and D = 0 at t = 0. (ii) For each time t = 1, 2, . . . ,T : (ii-a) Update C ← C + S(t); (ii-b) If S * (t) = o, then continue to t + 1 (if t < T ) or stop (if t = T ); otherwise, update C ← C -1 and D ← 1, provided that C ≥ 1. Let f a,S,S * be the value of D (the number of death event) at the end. It will suffice to show that the two inequalities hold for f a,S,S * on any fixed S * ∈ {0, 1} T .

Consider the process TS-BDP(a, S, S * ). Let t a ∈ [T ] be the first checking point such that C + S(t a ) = 0 and S * (t a ) = 1 and thus, we have no death event at t a in TS-BDP(a, S, S * ). Set t a = T + 1 if such t a doesnot exist in TS-BDP(a, S, S * ). When t a ≤ T : We have in TS-BDP(a +1, S, S * ), C +S(t a ) = 1, and thus, we have have one extra death event at t a and there will be only one, since the two processes TS-BDP(a, S, S * ) and TS-BDP(a + 1, S, S * ) will be the same when t < t a and t > t a . When t a = T + 1 (t a does not exist), the two process will have the same set of updates all the time. This analysis suggests that f a+1,S,S * ≤ f a,S,S * + 1 for all a ≥ 0. Thus, we prove the second inequality (which is a = 0). Note that f a-1,S,S *f a-2,S,S * = 1 iff t a-2 ≤ T and f a,S,S *f a-1,S,S * = 1 iff t a-1 ≤ T . Since t a-1 > t a-2 , we have that f a-1,S,S *f a-2,S,S * ≥ f a,S,S *f a-1,S,S * . Thus, we are done.

CONCLUSION AND FUTURE DIRECTIONS

In this article, we present a mathematical model for crowdsourcing platforms where the number of workers is far fewer than the number of tasks (e.g., UberEats delivering food to customers). We propose an LP-based non-adaptive algorithm for the edge-weighted case, and GREEDY and two LP-based adaptive algorithms for the unweighted and vertex-weighted cases, respectively. These algorithms, as demonstrated in this article, can be theoretically analyzed to prove lower bounds on their competitive ratios. On the hardness side, we establish both conditional (based on benchmark LP) and unconditional hardness results. Finally, we implement all the algorithms on two datasets (a real-world and a synthetic) and evaluate their practical performance numerically.

Our work suggests several future directions. The primary open question is to formally analyze the performance of GREEDY for both the edge-weighted and vertex-weighted cases. In particular, it would be interesting to prove that GREEDY is optimal for the vertex-weighted case, as observed in the experiments. Another open direction is to propose an improved benchmark LP that closely approximates the best offline (expected) solution.