---
bibliography:
- 'SSRN\_main.bib'
---

Introduction {#sec:intro}
============

Volunteers in the U.S. provide around $8$ billion hours of free labor annually. However, roughly $30\%$ of volunteers become disengaged the following year, representing a loss of approximately $\$70$ billion in economic value as well as a significant challenge for the sustainability of organizations relying on volunteerism [@nationalservice2015; @independentsector2018]. Lack of retention partially stems from overutilization as well as the mismatch between a volunteer’s preferences and the opportunities presented to her [@locke2003hold; @brudney2009ain]. The emergence of online volunteer crowdsourcing platforms presents a unique opportunity to design data-driven volunteer management tools that cater to volunteers’ [heterogeneous]{} preferences. In the present work, we move toward this goal by taking [an algorithmic]{} approach to designing nudging mechanisms commonly used to encourage volunteers to perform tasks.

This work is motivated by our collaboration with a nonprofit platform, called Food Rescue U.S. (FRUS), that [recovers food from local businesses and donates it to nonprofit agencies by crowdsourcing the transportation to volunteers]{}. In the following, we provide background on FRUS and highlight the challenge it faces when making volunteer nudging decisions. Further, we offer insights into volunteer behavior by analyzing FRUS data from different locations. Then, we list a summary of our contributions.

[**FRUS: A Crowdsourcing Platform for Food Recovery:**]{} FRUS is a leading online platform that simultaneously addresses the societal problems of food waste and hunger. Over 60 million tons of food go to waste in the U.S. each year, while 37 million people—including 6 million children—live in food-insecure households. This mismatch is driven in part by the cost of last-mile transportation required to recover perishable donated food from local restaurants and grocery stores. FRUS has empowered donors by connecting them to local agencies and enabling free delivery through its dedicated volunteer base. Currently, it operates in tens of locations across different states, and so far it has recovered over 50 million pounds of food. On FRUS, a volunteering task—which is referred to as a [*rescue*]{}—involves transporting a prearranged, perishable food donation from a donor to a local agency. Scheduled donations are often recurring and they are posted on the FRUS app in advance. While around $78\%$ of rescues are claimed organically by volunteers before the day of the rescue, around $22\%$ remain unclaimed on the last day.[^1] In that case, to encourage volunteers to claim the rescue, FRUS [notifies]{} a subset of volunteers with the hope that at least one of them responds positively. However, based on our interviews with the platform’s local managers, FRUS faces a challenge when deciding whom to notify: on the one hand, it aims to minimize the probability of a missed rescue—which is achievable by notifying more volunteers.[^2] On the other hand, it wants to avoid excessive notifications because that may reduce volunteer engagement.[^3] [Understanding volunteer behavior can help resolve the aforementioned trade-off]{}: if volunteers have preferences for certain rescues, then FRUS should mainly notify them for those tasks. Our analysis of two years of data indeed indicates that volunteer preferences are fairly consistent. To highlight this, in Figure \[fig:pcatotal\] we visualize the first three principal components for characteristics of rescues completed by the most active volunteers in two FRUS locations. Each color represents a different volunteer and the size of each circle is proportional to the frequency with which the volunteer completes a rescue of that type. For instance, more than 90% of the rescues completed by the red volunteer in Location (a), as shown in Figure \[fig:PCA1\], are clustered within a cube whose volume is less than one tenth of the PCA component range. As evident from these plots, volunteers tend to claim rescues that have similar characteristics, reflecting their geographical and time preferences.[^4]

Our interviews and empirical findings raise a key question that motivates our work: facing such volunteer behavior, how should a volunteer-based online platform, such as FRUS, design an effective [notification system]{} for time-sensitive tasks?

[0.48]{} ![Figure \[fig:PCA1\] shows the first three principal components (PCs) for characteristics of rescues completed by the five most active volunteers in Location (a). Each color represents a different volunteer and the size of each circle is proportional to the frequency with which the volunteer completes a rescue with those PCs. Figure \[fig:PCA2\] shows the same plot for Location (b).[]{data-label="fig:pcatotal"}](images/reg1_pca.jpeg "fig:"){width="\textwidth"}

[0.48]{}

[**Summary of Contributions:**]{} Motivated by our collaboration with FRUS, we (1) introduce the online volunteer notification problem which captures key features of volunteer labor consistent with the literature, (2) develop two online randomized policies that achieve constant-factor guarantees for the online volunteer notification problem, (3) establish upper bounds on the performance of any online policy, and (4) demonstrate the effectiveness of our policies by testing them on FRUS’s data from various locations across the U.S.

[**Modeling the Platform’s Notification Problem:**]{} We introduce the [*online volunteer notification problem*]{} to model a platform’s notification decisions when utilizing volunteers to complete time-sensitive tasks. There are three main considerations that the platform should take into account: (1) volunteers’ response to a notification is uncertain, (2) the platform cannot expect volunteers to respond promptly, and (3) if notified excessively, volunteers may suffer from notification fatigue. To include all these considerations in our model, we assume that when each task arrives, the platform simultaneously notifies a [*subset*]{} of volunteers in the hope that at least one responds positively. To model a volunteer’s adverse reaction toward excessive notifications, we assume that a volunteer can be in one of two possible states: [*active*]{} or [*inactive*]{}. In the former state, the volunteer pays attention to the platform’s notifications [and responds positively with her task-specific match probability, whereas in the latter state she ignores all notifications.]{} Upon [notification]{}, an active volunteer will transition to the inactive state for a random inter-activity period. [Because these platforms usually require the recurring completion of similar tasks, they can use historical data to predict their future last-minute needs.]{} For instance, FRUS usually receives donations from the same source on a weekly basis. We model this by assuming that tasks belong to a given set of types and they arrive according to a (time-varying) distribution. The platform makes online decisions aiming to maximize the number of completed tasks knowing the arrival rates, match probabilities, and the inter-activity time distribution, but without observing the state of each volunteer.

[**Developing Online Policies:**]{} We develop two randomized policies that are based on ex ante fractional solutions that can be computed in polynomial time. In order to assess the performance of our policies, we use a [linear program benchmark]{} whose optimal value serves as an upper bound on the value of a clairvoyant solution which knows the sequence of arrivals a priori as well as the state of volunteers at each time (see Program (LP), Proposition \[prop:LP\] and Definition \[def:compratio\]). We remark that the platform’s objective—[maximizing the number of completed tasks]{}—[*jointly*]{} depends on the response of all volunteers and exhibits diminishing returns. For example, if the platform notifies two active volunteers $v$ and $u$ about a task ${s}$, then the probability of completion would be $[1 - (1- p_{v,{s}}) (1 - p_{u,{s}})]$ where $p_{v,{s}}$ and $p_{u,{s}}$ are the match probabilities of the pairs $(v,{s})$ and $(u,{s})$, respectively. [This]{} objective function presents two challenges: (1) an ex ante solution based on upper bounding such an objective function by a piecewise linear one [can be]{} ineffective in practice, and (2) jointly analyzing volunteers’ contribution for an online policy while keeping track of the joint distribution of their states (active or inactive) is prohibitively difficult. We address the former challenge by computing ex ante solutions that “better” approximate the true objective function as opposed to only relying on the LP solution (see Programs and and Proposition \[prop:fxstar\]). We overcome the latter one by assuming an artificial priority among volunteers which allows us to decouple their contributions (see Definition \[def:priority\] and Lemma \[lem:falg\]).

[Attempting to follow the fractional ex ante solution can result in poor performance since volunteers can become inactive at inopportune times (see Appendix \[ex:followingxstar\]).]{} Therefore, in the design of our policies, we modify the ex ante solution to [account for inactivity]{} while guaranteeing a constant-factor competitive ratio. Our first policy, the [*Scaled-Down Notification (SDN) Policy*]{}, relies on a prori computing the probability that a volunteer is active when following this policy. Equipped with these probabilities, the SDN policy notifies each volunteer such that the [*joint*]{} probability that a volunteer is active and notified is proportional to the ex ante solution (see Algorithm \[alg:one\] and the preceding discussion). On the other hand, our second policy, the [*Sparse Notification (SN) Policy*]{}, relies on [solving a sequence of Dynamic Programs (DPs)—one for each volunteer—to resolve the trade-off between notifying a volunteer now and saving her for future tasks. We solve the DPs in order of volunteers’ artificial priorities, and each subsequent DP is formulated based on the previous solutions]{} (see Algorithm \[alg:two\] and the preceding discussion).

Our policies are parameterized by the minimum discrete hazard rate (MDHR) of the inter-activity time distribution, which serves as a sufficient condition for the level of “activeness” of volunteers (see Definition \[def:hazard\] and the following discussion). We analyze the competitive ratios of both policies as functions of the MDHR. Interestingly, both policies achieve the same competitive ratio (see Theorems \[thm:alg1\] and \[thm:alg2\]). However, the SN policy demonstrates significantly better performance in practice (as shown and discussed in Section \[sec:data\]).

The analysis of both policies relies on [decomposing the problem]{} into individual contributions based on our (artificial) priority scheme. Further, the analysis of SDN relies on proving that the probability of being active can be computed in advance and in polynomial time (see Section \[subsec:alg1\] and Appendix \[proof:beta\]). The analysis of SN crucially uses the dual-fitting framework of [@alaei2012online] and it relies on formulating a linear program along with its dual to place a lower bound on the optimal value of each volunteer’s DP (see Section \[subsec:alg2\] and Appendix \[proof:factorrevealingLP\]).

[**[Upper Bound on Online Policies]{}:**]{} In order to gain insight into the limitation of online policies when compared to our benchmark, we develop an upper bound on the achievable competitive ratio of any online policy. [Like our policies, the upper bound is]{} parameterized by the MDHR (see Theorem \[thm:hardness\]). [As a consequence,]{} the gap between the achievable upper bound and our lower bound (attained through our policies) depends on the MDHR (see Figure \[fig:hardness\]). When it is small but positive, the gap is fairly small; however, the gap grows as the MDHR increases. Our upper bound relies on analyzing two instances, one of which provides a relatively tight upper bound when the MDHR is small. [**Testing on FRUS Data:**]{} In order to illustrate the effectiveness of our modeling approach and our policies in practice, we evaluate the performance of our policies by testing them on FRUS’s data from different locations. In Section 6, we describe how we estimate model primitives and construct problem instances. Then we numerically show the superior perform of our policies when compared to strategies that resemble the current practice at different locations.

The rest of the paper is organized as follows. In Section \[sec:lit\], we review the related literature. In Section \[sec:model\], we formally introduce the online volunteer notification problem as well as the benchmark and the measure of competitive ratio. Section \[sec:algos\] is the main algorithmic section of the paper and is devoted to describing and analyzing our two online policies. In Section \[sec:hardness\], we present our upper bound on the achievable competitive ratio of any online policy. In Section \[sec:data\], we revisit the FRUS application and demonstrate the effectiveness of our policies by testing them on the platform’s data from various locations. Section \[sec:conclude\] concludes the paper. For the sake of brevity, we only include proof ideas in the main text. A detailed proof of each statement is provided [in the referenced appendix.]{}

false

1.  General voluteer stuff (reuse the first two sentences of abstract); add citations. (done!)

2.  Intro to FRUS (done!)

3.  Discuss FRUS current approch and the prefernce graphs (done!)

4.  Define research question; Summary of contributions. (Short one ) (almost done!)

5.  one paragraph model

6.  ex-ante solution and why it’ hard to implement; motivate the two algs.

7.  one paragraph both alg 1; talk proof ideas

8.  one paragraph alg 2; tla proof ideas

9.  short paragraph on hardness

10. one paragaph on data

11. organization

Related Work {#sec:lit}
============

Our work relates to and contributes to several streams of literature.

[**Volunteer Operations and Staffing**]{}: Due to the differences between volunteer and traditional labor as highlighted in [@sampson2006optimization], managing a volunteer workforce provides unique challenges and opportunities that have been studied in the literature using various methodologies [@lacetera2014rewarding; @ata2016dynamic; @sonmez2016improving; @dickerson2019blood; @urrea2019volunteer]. One key operational challenge is the uncertainty in both volunteer labor supply and demand. Using an elegant queuing model, [@ata2016dynamic] study the problem of volunteer staffing with an application to gleaning organizations. Our approach to modeling volunteer behavior (specifically, assuming that notifying an active volunteer triggers a random period of inactivity) bears [some resemblance to]{} the approach taken in [@ata2016dynamic]. In a novel recent work, [@dickerson2019blood] studies the problem of matching blood donors to donation centers, assuming that donors have preferences (over centers) and constraints on the frequency of receiving notifications. Using a stochastic matching policy, they demonstrate strong numerical performance relative to various benchmarks. [There are some similarities between our modeling approach and the approach used in [@dickerson2019blood], but we highlight [three]{} key differences.]{} (1) While their work focuses on the numerical evaluation of policies, we theoretically analyze the performance of our policies and provide an upper bound on the performance achievable by any online policy, as stated in Theorems \[thm:alg1\], \[thm:alg2\], and \[thm:hardness\]. (2) We model volunteers’ adverse reactions to excessive notifications in a general form by considering an arbitrary inter-activity time distribution. (3) We parameterize our achievable upper and lower bounds by the minimum discrete hazard rate of that distribution. false

[**Crowdsourcing Platforms**]{}: Reflecting the growth of online technologies, there is a burgeoning literature on the operations of crowdsourcing platforms (see e.g. [@karger2014budget; @hu2015product; @alaei2016dynamic; @papanastasiou2018crowdsourcing]). Our work adds to the growing collection of papers that focus specifically on nonprofit crowdsourcing platforms, with applications as varied as educational crowdfunding [@song2018matching], disaster response [@han2019harnessing], and smallholder supply chains [@de2018sustaining; @de2019crowdsourcing]. [Nonprofits often use crowdsourcing in the absence of monetary incentives; in such settings, successful crowdsourcing relies on efficient utilization and engagement of participants.]{} We contribute to this literature by designing online policies for effectively notifying volunteers while avoiding overutilization.

[**Online Matching and Prophet Inequalities**]{}: Abstracting away from the motivating application, our work is related to the stream of papers on online stochastic matching, prophet matching inequalities, and online allocation of reusable resources. Given the scope of this literature, we highlight only recent advances and kindly refer the interested reader to [@mehta2013online] for an informative survey. A standard approach is to design online policies based on an offline solution (see e.g. [@feldman2009online; @manshadi2012online; @jaillet2014online; @wang2018online; @stein2019advance]) and to compare the performance of these policies to a benchmark such as the clairvoyant solution described in [@golrezaei2014real]. Our work builds on this approach by applying techniques from prophet matching inequalities and the magician’s problem [@alaei2012online; @alaei2014bayesian].

Most similar to our work are [@dickerson2018allocation] and [@Rad2019], which both consider settings with [unit-capacity]{} reusable resources (see also [@gong2019online] and [@rusmevichientong2020dynamic] which mainly focus on large-capacity settings). The former designs an adaptive policy to address an online stochastic matching problem, while the latter considers an online assortment optimization problem. We highlight three key differences between our work and these papers. (1) In our work, the platform’s objective function is non-linear. Despite that, we only consider offline solutions that can be computed in polynomial time (as opposed to relying on an oracle). [(2) Volunteers—which represent the resources in our setting—can]{} become unavailable without being matched (i.e., just through notification). (3) We develop parameterized lower and upper bounds based on the minimum discrete hazard rate of the usage duration. Such an approach enables us to gain insight into the impact of the characteristics of the usage duration distribution on the achievable bounds.

Model {#sec:model}
=====

In this section, we formally introduce the *online volunteer notification problem* that a volunteer-based crowdsourcing platform faces when deciding whom to notify for a task. [As part of]{} the problem definition, we highlight the platform’s objective as well as the trade-off it faces due to the volunteers’ adverse reactions to excessive notifications and the uncertainty in future tasks. Further, we define the measure of competitive ratio and establish a benchmark against which we compare the performance of any online policy.

The online volunteer notification problem consists of a set of volunteers, denoted by ${\mathcal{V}}$, and a set of task types, denoted by ${\mathcal{S}}$.[^5] Volunteers (resp. tasks) are indexed from $1$ to $|{\mathcal{V}}| = V$ (resp. $|{\mathcal{S}}| = {S}$). Over $T$ time steps, the platform solicits volunteers to complete a sequence of tasks. In particular, in each time step $t$, a task of type ${s}$ arrives with known probability $\lambda_{{s},t}$. Without loss of generality, we assume at most one task arrives in each time step. Said differently, we assume $\sum_{{s}= 1}^{{S}} \lambda_{{s},t} \leq 1$ and with probability $1- \sum_{{s}= 1}^{{S}} \lambda_{{s},t} := \lambda_{0,t}$, no task arrives.

[Whenever a task arrives, the platform can notify volunteers. However, ]{} excessively notifying a volunteer may lead her to suffer from notification fatigue. To model this behavior in a general form, we assume that a volunteer can be in two possible states: [*active*]{} or [*inactive*]{}. In the former state, the volunteer pays attention to the platform’s notifications, whereas in the latter state, she is inattentive. Initially, each volunteer is active. However, upon being notified she transitions to the inactive state and will only become active again in $Z$ periods, where $Z$ is independently drawn from a known inter-activity time distribution denoted by $g(\cdot)$. Mathematically, ${\mathbb{P}\left(Z = \tau\right)} = g(\tau)$. To capture the minimum rate at which volunteers transition from inactive to active, we define the minimum discrete hazard rate of the inter-activity time distribution as follows:

\[def:hazard\] For a probability distribution $g(\cdot)$, the *minimum discrete hazard rate* (MDHR) is given by $q = \min_{\tau \in \mathbb{N}} \frac{g(\tau)}{1-G(\tau-1)}$, [where $G(\cdot)$ denotes the corresponding CDF.]{}[^6]

Note that a large value of $q$ is a sufficient condition to ensure that volunteers’ activity level is high. For example, if $g(\cdot)$ is a geometric distribution, $q$ is the same as its success probability. [However, a small value of $q$ does not imply inactive volunteers:]{} if $g(2) = 1$, i.e., if the inter-activity times are deterministic and equal to 2 periods, then $q=0$ but volunteers are quite active.

Before proceeding, we point out that similar modeling assumptions have been made in previous work. In particular, [@ata2016dynamic] models volunteer staffing for gleaning and assumes once a volunteer is utilized, she will go into a random repose period. Similarly, [@dickerson2019blood] focuses on blood donation and puts a constraint on the frequency with which a volunteer can be notified, which is equivalent to assuming a deterministic inter-activity time. The latter strategy is also practiced in [many]{} FRUS locations.

When a donation arrives, the platform observes the donation type and must immediately and irrevocably notify a subset of volunteers.[^7] If an active volunteer $v$ is notified about a task ${s}$, she will respond with match probability $p_{v,{s}}$, independently from all other volunteers. Thus the arriving task is completed if at least one notified volunteer responds. If task ${s}$ arrives at time $t$ and if the the subset of volunteers that are both notified and active is given by ${\mathcal{U}}$, then the task will be completed with probability $1 - \prod_{v \in {\mathcal{U}}} (1-p_{v,{s}})$. We highlight that this probability is monotone and submodular with respect to the set ${\mathcal{U}}$. In Section \[sec:data\], we describe how $p_{v,{s}}$ can be estimated accurately in the FRUS setting by using historical data.

As mentioned earlier, all volunteers are initially active. The platform knows the arrival rates $\lambda_{{s}, t}$, the match probabilities $p_{v, {s}}$, and the inter-activity time distribution $g(\cdot)$, but it does not observe volunteers’ states. For any instance [${\mathcal{I}}$]{} of the online volunteer notification problem [where]{} ${\mathcal{I}} = \big(\{\lambda_{{s},t}:{s}\in [{S}], t \in [T]\}, \{p_{v,{s}}:v \in [V], {s}\in [{S}]\}, g \big)$,[^8] the platform’s goal is to employ an online policy that maximizes the expected number of completed tasks.

In order to evaluate an online policy, we compare its performance to that of a clairvoyant solution that knows the entire sequence of arrivals in advance as well as volunteers’ states in each period. However, [the clairvoyant solution]{} does not know *before* notifying a volunteer how long her period of inactivity will be. Two observations enable us to upper bound the clairvoyant solution with a polynomially-solvable program. First, note that if the clairvoyant solution notifies a subset of volunteers ${\mathcal{U}}$ about task ${s}$ at time $t$, the probability of completing ${s}$ is $$\begin{aligned}
    1 - \prod_{v \in {\mathcal{U}}}(1-p_{v,{s}_t}) \leq \min\Big\{ \sum_{v \in {\mathcal{U}}}p_{v,{s}_t} , 1\Big\}\end{aligned}$$ In words, we can upper bound the success probability of a subset ${\mathcal{U}}$ with a piecewise-linear function that is the minimum of the expected total number of volunteer responses and $1$. Second, recall that the clairvoyant solution only notifies active volunteers and does not know how long those notified volunteers will remain inactive. As a consequence, we can upper bound the clairvoyant solution via the following program which we denote by (LP):

$$\begin{aligned}
\mathbf{LP}_{\mathcal{I}} = \text{max}_{\mathbf{x}} \quad \quad \quad & \sum_{t=1}^T \sum_{{s}=1}^{{S}}   \lambda_{{s},t} \min\Big\{ \sum_{v=1}^V x_{v,{s},t}p_{v,{s}}, 1\Big\}& \tag{LP$^*$} \label{LP} \\
\text{s.t.} \ \ \ \qquad \quad 
    &0\leq  x_{v,{s},t}\leq 1  &\forall v, {s}, t \label{eq:lpcon1} \\
    &1 \geq  \sum_{\tau =1}^t \sum_{{s}=1}^{{S}} \lambda_{{s},t} x_{v,{s},t} (1-G(t-\tau))  &\forall v, t \label{eq:lpcon2}\end{aligned}$$

------------------------------------------------------------------------

The decision variables $x_{v,{s},t}$ represent the probability of notifying volunteer $v$ when a task of type ${s}$ arrives at time $t$. Constraint ensures that $x_{v,{s},t}$ is a valid probability. Constraint places limits on the frequency with which volunteers can be notified according to the inter-activity time distribution. In particular, the clairvoyant solution will only notify an active volunteer who will then become inactive for a random number of periods. Thus, in expectation the clairvoyant solution must meet constraint . For ease of reference, in the following, we define the set of all feasible solutions to (LP). Such a definition proves helpful in the rest of the paper.

\[def:P\] For any $\mathbf{x} \in \mathbb{R}^{V \times {S}\times T}$, $\mathbf{x} \in {\mathcal{P}}$ if [and only if]{} it satisfies constraints and .

The following proposition, which we prove in Appendix \[proof:LP\], establishes the relationship between the clairvoyant solution and $\mathbf{LP}_{\mathcal{I}}$:

\[prop:LP\] [For any instance ${\mathcal{I}}$ of the online volunteer notification problem, $\mathbf{LP}_{\mathcal{I}}$ is an upper bound on its clairvoyant solution]{}.

In light of Proposition \[prop:LP\], we use $\mathbf{LP}_{\mathcal{I}}$ as a benchmark against which we compare the performance of any policy. Consequently, we define the competitive ratio of an online policy as follows:

\[def:compratio\] An online policy is $c$-competitive for the online volunteer notification problem if for any instance ${\mathcal{I}}$, we have: $\mathbf{POL}_{{\mathcal{I}}} \geq c \mathbf{LP}_{{\mathcal{I}}}$, where $\mathbf{POL}_{{\mathcal{I}}}$ represents the expected number of completed tasks by the online policy for instance ${{\mathcal{I}}}$.

We will use the competitive ratio as a way to quantify the performance of an online policy. For each of our two policies (presented in the following section), the competitive ratio is parameterized by the MDHR, $q$, and it improves as $q$ increases.

Online Policies {#sec:algos}
===============

In this section, we present and analyze two policies for the online volunteer notification problem. Both policies are randomized and rely on a fractional solution we compute ex ante using the instance primitives. Thus, we begin this section by introducing the ex ante solution in Section \[subsec:offline\]. We then proceed to describe our algorithms and analyze their competitive ratios in Sections \[subsec:alg1\] and \[subsec:alg2\].

Ex Ante Solution {#subsec:offline}
----------------

As stated in Section \[sec:intro\], both of our online policies rely on an ex ante solution which we denote by $\mathbf{x^*} \in [0,1]^{V \times {S}\times T}$. Given our benchmark, we focus our attention on solutions that are feasible in (LP), i.e., $\mathbf{x^*} \in {\mathcal{P}}$ (see Definition \[def:P\]). Clearly, $\mathbf{x^*_{LP}}$—the solution to (LP) in Section \[sec:model\]—is a potential ex ante solution. However, in practice, such a solution [can]{} prove ineffective because it does not take into account the diminishing returns of notifying an additional volunteer about a task. As a result, it may ignore some tasks while notifying an excessive number of volunteers about others [(e.g., see Appendix \[ex:xstarcandidates\])]{}.

Given any $\mathbf{x} \in {\mathcal{P}}$, for a moment, suppose volunteers are always active. Then if we notify each volunteer independently according to $\mathbf{x}$, the expected number of completed tasks would be:[^9] $$\begin{aligned}
\label{eq:fdef1}
f(\mathbf{x}):= \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} \Big(1 - \prod_{v=1}^{V} (1- x_{v,{s},t}p_{v,{s}}) \Big).\end{aligned}$$ Because $\mathbf{x^*_{LP}}$ is the optimal solution of a piecewise-linear objective, it ignores the submodularity in $f(\mathbf{x})$.[^10] In light of this intuition, we introduce two other candidates that can be computed in polynomial time. First, we aim to find the feasible point that maximizes $f(\cdot)$. We denote this optimization problem by (AA) which stand for [*Always Active*]{}. Even though \[MRG\] is $NP$-hard [@bian2017guaranteed], simple polynomial-time algorithms such as the variant of the Frank-Wolfe algorithm described below (proposed in [@bian2017guaranteed]) are known to work well in practice. The algorithm iteratively maximizes a linearization of $f(\mathbf{x})$ and returns a convex combination of feasible solutions, which therefore must be feasible. We denote the output of this algorithm by $x^*_{AA}$ and use it as another candidate for the ex ante solution.

$$\max_{\mathbf{x} \in \mathcal{P}} f(\mathbf{x}) \label{MRG} \tag{AA}$$

1.  Set $\mathbf{x}^0 = \mathbf{0}$.

2.  **For** $i$ from $1$ to $n$:

    1.  Solve $\mathbf{y}^i =\text{argmax}_{\mathbf{x} \in {\mathcal{P}}} \langle \mathbf{x}, \nabla f(\mathbf{x}^{i-1}) \rangle$

    2.  Set $\mathbf{x}^i = \mathbf{x}^{i-1} +\frac{1}{n} \mathbf{y}^i$

3.  Return $\mathbf{x}^n$

Note that the expected number of completed tasks, as defined in , jointly depends on the contributions of all volunteers. This property makes optimizing such an objective challenging. Further, when assessing any online policy, jointly analyzing volunteers’ contribution while keeping track of the joint distribution of their state (active or inactive) is prohibitively difficult.[^11] We overcome this challenge by defining the following artificial priority scheme among volunteers which enables us to “decouple” the contributions of volunteers and find our last candidate for the ex ante solution.

\[def:priority\] Under the index-based priority scheme, when multiple volunteers respond to a notification, the one with the smallest index completes the task. [^12]

Following the index-based priority scheme allows us to define individual contributions for each volunteer as shown in the following lemma (proven in Appendix \[proof:falg\]).

\[lem:falg\] For any $\mathbf{x} \in [0,1]^{V \times {S}\times T}$, $f(\mathbf{x}) = \sum_{v = 1}^{V} f_v(\mathbf{x})$ where $f(\cdot)$ is defined in and $$\begin{aligned}
 \label{eq:decouple}
 f_v(\mathbf{x}) := \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} \Big(\prod_{u < v}(1-p_{u, {s}} x_{u, {s}, t})\Big)  p_{v, {s}} x_{v, {s}, t}.\end{aligned}$$

For any $v \in [V]$, the term $\left(\prod_{u < v}(1-p_{u, {s}} x_{u, {s}, t})\right)  p_{v, {s}} x_{v, {s}, t}$ in represents the probability that under the index-based priority scheme, volunteer $v$ is the lowest-indexed volunteer to respond positively to a notification about task ${s}$ at time $t$. Further, this term only depends on the fractional solution of volunteers with lower index than $v$. In addition, if we treat $x_{u, {s}, t}$ as fixed for $1 \leq u <v$, then $\left(\prod_{u < v}(1-p_{u, {s}} x_{u, {s}, t})\right)  p_{v, {s}} x_{v, {s}, t}$ is linear in $x_{v, {s}, t}$. In light of these observations, we define our last candidate as the solution of a sequence of linear programs in which volunteers maximize their individual contributions in the order of their priority. This is summarized in the program .

**For** $v$ from $1$ to $V$: $$\begin{aligned}
    \max_{\{x_{v,{s},t}:{s}\in [{S}], t \in [T]\}} \ \  \quad \quad & \sum_{t=1}^T \sum_{{s}=1}^{{S}}  \lambda_{{s},t} \left(\prod_{u \leq v}(1-p_{u, {s}} x^{SQ}_{u, {s}, t})\right)  p_{v, {s}} x_{v, {s}, t}& \tag{SQ-$v$} \label{SQ} \\
    \text{subject to}  \qquad \ \
    0 \leq &x_{v,{s},t} \leq 1 &\forall {s}, t \nonumber \\ 
    1 \geq & \sum_{\tau =1}^t \sum_{{s}=1}^{{S}} \lambda_{{s},t} x_{v,{s},t} (1-G(t-\tau))  &\forall t \nonumber
    \end{aligned}$$

For a given volunteer $v$, the program uses the solutions from previous iterations, i.e., $x^{SQ}_{u,{s},t}$ for $u < v$. As a result, this solution takes into account the diminishing returns from notifying multiple volunteers. We denote the solution to these $V$ sequential LPs as $\mathbf{x^*_{SQ}}$. Finally, we remark that the above decoupling idea proves helpful in both designing and analyzing our online policies.

Having three candidates, we define $$\mathbf{x^*}:= \text{argmax}_{\mathbf{x} \in \{\mathbf{x^*_{LP}}, \mathbf{x^*_{AA}}, \mathbf{x^*_{SQ}} \}} f(\mathbf{x}) \label{eq:xstar}$$ The following proposition establishes a lower bound on $f(\mathbf{x^*})$ based on the benchmark $\mathbf{LP}$.

\[prop:fxstar\] For $\mathbf{x^*}$ defined in , $$f(\mathbf{x^*})  \geq (1-\frac{1}{e})\mathbf{LP}.$$

The above worst case ratio is achieved by the ratio of $f(\mathbf{x^*_{LP}})$ to $\mathbf{LP}$, and it is tight. [However, we stress that $\mathbf{x^*_{AA}}$ and $\mathbf{x^*_{SQ}}$ can provide significant improvements. [A simple example illustrating this point can be found in Appendix \[ex:xstarcandidates\], while a full proof of Proposition \[prop:fxstar\] can be found in Appendix \[proof:fxstar\].]{} When testing our policies on FRUS data (as detailed in Section \[sec:data\]), we find that using $\mathbf{x^*}$ instead of $\mathbf{x^*_{LP}}$ results in an average improvement of 5% up to maximum of 23%.]{}

We conclude this section by noting that an online policy which directly follows $\mathbf{x^*}$ (i.e., a policy that at time $t$, upon arrival of ${s}$, notifies volunteer $v$ independently with probability $x^*_{v,{s},t}$) does not achieve a good competitive ratio. This stems from the fact that $\mathbf{x^*}$ “respects” the inactivity period of volunteers only in expectation. Consequently, it is possible that volunteers are inactive when high-value tasks arrive (e.g. tasks where the match probability is close to $1$) because they were notified earlier (according to $\mathbf{x^*}$) for low-value tasks. We present an illustrative example in Appendix \[ex:followingxstar\].

Therefore, we develop two policies based on two different modifications of the ex ante solution: (1) properly scaling it down and (2) sparsifying it. The former guides our first policy which we call the [*scaled-down notification*]{} policy, whereas the latter guides our second policy, referred to as the [*sparse notification*]{} policy. These policies are described and analyzed in the next two sections, respectively.

Scaled-Down Notification Policy {#subsec:alg1}
-------------------------------

In this section, we present our scaled-down notification (SDN) policy which is a non-adaptive randomized policy that independently notifies volunteers according to a predetermined set of probabilities based on $\mathbf{x^*}$.[^13] The policy relies on the following ideas: (1) [Fixing a policy, suppose we can compute the *ex ante* probability that any volunteer $v$ is active at time $t$ when following that policy.]{} Let us denote such an ex ante probability by $\beta_{v,t}$. Then if ${s}$ arrives at time $t$, we notify $v$ with probability ${c}x^*_{v,{s},t}/\beta_{v,t}$ [where ${c}\in [0,\beta_{v,t}/x^*_{v,{s},t}]$.]{} As a result, she will be active *and* notified with probability ${c}x^*_{v,{s},t}$. (2) If she was the only notified volunteer, then her probability of completing this task would be simply ${c}x^*_{v,{s},t}p_{v,{s}}$. Even though this is not the case, using the index-based priority scheme and the contribution decoupling idea in Lemma \[lem:falg\], we can show her contribution will be proportional to ${c}x^*_{v,{s},t}p_{v,{s}}$. (3) Consequently, we would like to set ${c}$ as large as possible. However, ${c}$ cannot be larger than $\frac{\beta_{v,t}}{x^*_{v, {s}, t}}$ since notification probabilities cannot exceed $1$. Thus in the design of the policy, we find the largest feasible ${c}$, which we prove to be $1/(2-q)$ where $q$ is the MDHR of the inter-activity time distribution (see Definition \[def:hazard\]).

The formal definition of our policy is presented in Algorithm \[alg:one\]. In the rest of this section, we analyze the competitive ratio of the SDN policy. Our main result is the following theorem:

**Offline Phase**:

1.  Compute $\mathbf{x^*}$ according to .

2.  Set $\beta_{v,1} = 1$ and $\beta_{v, t} = 1 - \sum_{t'=1}^{t-1} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} \frac{x^*_{v,{s},t'}}{2-q}(1-G(t - t'))$ for all $v \in [V], t \in [T] \setminus [1]$

**Online Phase**:

1.  **For** $t \in [T]$:

    1.  If task ${s}$ arrives in time $t$, then **for** $v$ in $V$:

        1.  Notify $v$ with probability $\frac{x^*_{v,{s},t}}{(2-q)\beta_{v,t}}$

\[thm:alg1\] Suppose the MDHR of the inter-activity time distribution is $q$. Then the scaled-down notification policy, defined in Algorithm \[alg:one\], is $\frac{1}{2-q}(1-\frac{1}{e})$-competitive.

We remark that Theorem \[thm:alg1\] implies that the competitive ratio of our policy improves as $q$ increases. However, a larger value of $q$ does not imply that the probability of notification is uniformly larger. If $q$ increases, the ex ante solution as well as the ex ante probability of being active will also change, both of which affect the notification probability. The proof of Theorem \[thm:alg1\] builds on the ideas described above and consists of several steps. First, in the following lemma, we prove that for any $v \in [V]$ and $t \in [T]$, $\beta_{v,t}$ defined in Algorithm \[alg:one\] is indeed the probability that $v$ is active at time $t$ and $\beta_{v,t}$ is at least $\frac{1}{2-q}$.[^14]

\[lem:beta\] For the SDN policy defined in Algorithm \[alg:one\], let $\mathcal{E}_{v,t}$ represent the event that volunteer $v$ is active in period $t$. Then for all $v \in [V]$ and all $t \in [T]$, ${\mathbb{P}\left(\mathcal{E}_{v,t}\right)} = \beta_{v,t}$. Further, $\beta_{v,t}\geq \frac{1}{2-q}$.

We prove this lemma via total induction, relying critically on the fact that $\mathbf{x^*} \in \mathcal{P}$ (see Definition \[def:P\]). The full proof can be found in Appendix \[proof:beta\]. Next, utilizing the index-based priority scheme (in Definition \[def:priority\]) and the contribution decoupling idea [(in Lemma \[lem:falg\])]{}, we lower bound the contribution of each volunteer according to their priority in the following lemma:

\[lem:contributionsalg1\] Under the index-based priority scheme (in Definition \[def:priority\]) and the SDN policy, for any $\mathbf{x} \in {\mathcal{P}}$, the contribution of volunteer $v \in [V]$, i.e., the expected number of tasks she completes, is at least $\frac{1}{2-q} f_v(\mathbf{x})$, with $f_v(\cdot)$ defined in .

To prove Lemma \[lem:contributionsalg1\], we first show that a volunteer $v \in [V]$ responds to a notification about task ${s}\in [D]$ in period $t \in [T]$ with probability $\frac{x^*_{v,{s},t}}{2-q}$. We then place an upper bound on the probability that a volunteer with a smaller index also responds to a notification about that same task. A full proof can be found in Appendix \[proof:contributionsalg1\]. The last steps in the proof [of Theorem \[thm:alg1\]]{} are to compare the aggregate contribution of volunteers with the benchmark utilizing Lemma \[lem:falg\] and Proposition \[prop:fxstar\]. The detailed proof of Theorem \[thm:alg1\] is presented in Appendix \[proof:thmalg1\].

Sparse Notification Policy {#subsec:alg2}
--------------------------

In this section, we present our second policy, the sparse notification (SN) policy, which relies on a different modification of the ex ante solution. Before describing the policy, we briefly discuss our motivation for designing a second policy. Though simple and intuitive, the SDN policy only relies on the ex ante solution to resolve the trade-off between the immediate reward of notifying a volunteer and saving her for a future arrival. To see this, note that even in the last period $T$, the SDN policy [follows a scaled-down version of $\mathbf{x^*}$]{}.

[To more accurately resolve this trade-off, in designing the SN policy, we utilize]{} the ex ante solution and the index-based priority scheme (see Definition \[def:priority\]) [to]{} formulate a sequence of one-dimensional DPs whose optimal value will serve as a lower bound on the contribution of each volunteer according to her priority (as shown in Lemma \[lem:contributionsalg2\]). The solution of the these DPs is a sparsified version of the ex ante solution $\mathbf{x^*}$. Namely, let us denote $\mathbf{{\tilde{x}}}$ as the solution of the sequence of DPs. For any $v$, ${s}$, and $t$, $\tilde{x}_{v,{s}, t}$ is either $0$ or $x^*_{v,{s}, t}$. Equipped with $\mathbf{{\tilde{x}}}$, [which we compute in advance,]{} the SN policy simply follows $\mathbf{{\tilde{x}}}$ in the online phase. Our DP formulation and its analysis follows the framework developed in [@alaei2012online] and [@alaei2014bayesian], which is also used in [@Rad2019].

Next we describe the DP formulation. Consider volunteer $v \in [V]$ and suppose we have already solved the first $(v-1)$ DPs. Thus we have $\{\tilde{x}_{u,{s},t}: u \in [v-1], {s}\in [{S}], t \in [T]\}$. Let us denote the value-to-go of the DP at time $t$ by $J_{v,t}$. Clearly $J_{v,T+1} =0$. We set $v$’s reward at time $t$ for task ${s}$ to be $$r_{v, {s}, t} := p_{v,{s}} \prod_{u =1}^{v -1}(1-{\tilde{x}}_{u,{s},t}p_{u,{s}})\footnote{We emphasize that this is not the actual reward, i.e., it is not the probability that volunteer $v$ completes task ${s}$ under the index-based priority scheme. However, it is a lower bound, as shown in the proof of Lemma \ref{lem:contributionsalg2}.} \label{eq:rewards}$$ The actions available when task ${s}$ arrives at time $t$ are to notify $v$ with probability $x^*_{v,{s},t}$ or to not notify $v$. Thus when deciding on the optimal action (which can be either $0$ or $x^*_{v,{s},t}$), we compare the (current and future) reward of notifying $v$ now to the reward of saving her for the next period. Formally, $$\begin{aligned}
\label{eq:DP:sol}
    \tilde{x}_{v, {s}, t} = x^*_{v, {s}, t} {\mathbb{I}\Big(r_{v,{s},t} + \sum_{\tau = t+1}^T g(\tau - t){J}_{v, \tau} \geq {J}_{v,t+1}\Big)}\end{aligned}$$ The term in the indicator on the left hand side is the reward of notifying $v$ in the current period $t$, which consists of two parts: (1) the immediate reward we get from notifying $v$—which will make her inactive for $Z$ periods—and (2) the future reward once she becomes active again. The right hand side within the indicator simply represents the reward when $v$ is not notified [and remains active in period $t+1$]{}.

Given , , [and $J_{v, T+1} = 0$]{}, we can iteratively compute $\{J_{v,t}; t \in [T] \}$ as follows: $$\begin{aligned}
    J_{v,t} = \sum_{{s}=1}^{{S}} \lambda_{{s}, t}\Big((1-{\tilde{x}}_{v, {s}, t}){J}_{v,t+1} + {\tilde{x}}_{v,{s},t}\Big( r_{v,{s},t} + \sum_{\tau = t+1}^{T} g(\tau - t){J}_{v, \tau}\Big) \Big) \label{eq:jv}\end{aligned}$$ The formal definition of our policy is presented in Algorithm \[alg:two\]. In the rest of this section, we analyze the competitive ratio of the SN policy. Our main result is the following theorem:

**Offline Phase**:

1.  Compute $\mathbf{x^*}$ according to

2.  **For** all $v \in [V]$:

    1.  **For** all ${s}\in [{S}]$ and $t \in [T]$, [compute $r_{v,{s}, t}$ according to ]{}

    2.  Set ${J}_{v,T+1} = 0$

    3.  **For** $t =T$ to $t = 1$ :

        1.  **For** all ${s}\in [{S}]$, [compute $\tilde{x}_{v, {s}, t}$ according to ]{}

        2.  [Compute $J_{v,t}$ according to ]{}

**Online Phase**:

1.  **For** $t$ from $1$ to $T$:

    1.  **If** task ${s}$ arrives in time $t$, then **for** $v$ in $V$:

        1.  Notify $v$ with probability ${\tilde{x}}_{v,{s}, t}$

\[thm:alg2\] Suppose the MDHR of the inter-activity time distribution is $q$. Then the sparse notification policy, defined in Algorithm \[alg:two\], is $\frac{1}{2-q}(1-\frac{1}{e})$-competitive.

A few remarks are in order: (1) The competitive ratio of our two policies are identical, implying that in the worst case they guarantee the same performance. However, for practical instances, the SN policy performs significantly better (as shown by our test results in Section \[sec:data\]). Intuitively, this is because the design of the SN policy explicitly aims to [optimally]{} resolve the trade-off between notifying a volunteer now or keeping her active for later [based on $\mathbf{x^*}$]{}. On the other hand, the design of the SDN policy only aims to proportionally follow $\mathbf{x^*}$. As a result, the SDN policy’s numerical performance is not substantially better than its worst-case guarantee. On the other hand, the SN policy can perform much better than its worst-case guarantee [(see Appendix \[ex:SNvsSDN\] for an illustrative example)]{}. (2) Similar to the SDN policy, the competitive ratio of the SN policy improves when $q$ increases. However, the design of the SN policy does not directly make use of $q$.

The proof of Theorem \[thm:alg2\] consists of two main lemmas. First, in the following lemma, we lower bound the contribution of each volunteer $v$ by $J_{v,1}$:

\[lem:contributionsalg2\] Under the index-based priority scheme (in Definition \[def:priority\]) and the SN policy, the contribution of volunteer $v \in [V]$, i.e., the expected number of tasks she completes, is at least $J_{v,1}$, where $J_{v,1}$ is defined in .

The proof of this lemma follows from the DP formulation as well as the observation that for any $v \in [V]$, ${s}\in [{S}]$, and $t \in [T]$, the probability that a higher-priority volunteer completes the task is upper bounded by $1-\prod_{u=1}^{v -1}(1-p_{u,{s}}\tilde{x}_{u, {s}, t})$. A full proof can be found in Appendix \[proof:contributionsalg2\].

The second main step of the proof is to compare $J_{v,1}$ to the benchmark $\mathbf{LP}$. In order to do so, we follow the dual-fitting approach of [@alaei2012online]. In particular, given the inter-activity time distribution, we set up a linear program to find the “worst” possible combination of per-stage rewards that give rise to the minimum possible value of $J_{v,1}$. Finding the optimal solution to this LP proves to be difficult. Instead we find a feasible solution to its dual, which enables us to lower bound $J_{v,1}$. The LP and its dual are presented in Table \[table:lpdual\]. In the LP formulation, the first two sets of constraints follow from the DP definition. [Note that the value of $J_{v,1}$ will crucially depend on $\sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} r_{v, {s}, t} x^*_{v,{s},t}$, e.g., if $r_{v,{s},t} = 0$ for all $v \in [V]$, ${s}\in [{S}]$, and $t \in [T]$, then $J_{v,1} = 0$. This motivates the final constraint, which provides a constant against which we can compare $J_{v,1}$.]{} The following lemma establishes a lower bound on $J_{v,1}$.

\[lemma:factorrevealingLP\] Under the index-based priority scheme (see Definition \[def:priority\]), for any $\mathbf{x} \in {\mathcal{P}}$ and volunteer $v \in [V]$, we have $J_{v,1} \geq  \frac{1}{2-q}f_v(\mathbf{x})$ where $f_v(\mathbf{x})$ is defined in .

The proof of Lemma \[lemma:factorrevealingLP\] (presented in Appendix \[proof:factorrevealingLP\]) amounts to confirming that setting $\mu = \frac{1}{2-q}$ and defining all other dual variables such that the constraints hold with equality is a feasible solution to (Dual). Given Lemma \[lemma:factorrevealingLP\], we complete the proof of Theorem \[thm:alg2\] by applying Lemma \[lem:falg\] and Proposition \[prop:fxstar\]. The complete proof is presented in Appendix \[proof:thmalg2\].

Upper Bound on Competitive Ratio {#sec:hardness}
================================

In this section, we provide an upper bound on the competitive ratio of any online policy in the online volunteer notification problem. Like the lower bound achieved by our policies in Section \[sec:algos\], the upper bound is parameterized by the MDHR of the inter-activity time distribution, $q$. The main result of this section is the following theorem:

\[thm:hardness\] Suppose the MDHR of the inter-activity time distribution is $q$ where $q \in [1/16,1] \cup \{1/n,  n \in \mathbb{N} \} \cup \{0 \} $. Then no online algorithm can achieve a competitive ratio greater than $\kappa$, where for $q>0$ $$\label{eq:kappa}
    \kappa = \min \Big\{\frac{1}{2-q}, 1 + q - \frac{q(1-q)}{\log(\frac{1}{1-q})(1+q)}(1-e^{-1}) \Big \}.$$ and for $q = 0$, we have $\kappa = \frac{1}{2}$.[^15]

Figure \[fig:hardness\] provides a summary of our lower and upper bounds on the achievable competitive ratio for the online volunteer notification problem as a function of $q$. We make the following observations based on the [theorem and accompanying]{} plot: [(1) the upper bound applies to all policies, even those that cannot be computed in polynomial time,]{} (2) both the upper and lower bounds improve as $q$ increases, and (3) the competitive ratio of our online policies are fairly close to the upper bound when $q$ is small but positive. However, the gap grows for larger values of $q$.

The proof of Theorem \[thm:hardness\] relies on analyzing the following two instances, each giving one of the terms in the definition of $\kappa$ as shown in . Instance ${\mathcal{I}}_1$ attains the minimum when $q \in \{0\} \cup [1/16,1]$ whereas Instance ${\mathcal{I}}_2$ attains it when $q \in \{1/n, n > 16, n \in \mathbb{N} \}$.

Suppose $V = 1$, ${S}= 2$, $T=2$, and $g(1) = q$, where $q \in [0,1]$. The arrival probabilities are given by $\lambda_{1, 1} = 1$ and $\lambda_{2, 2} = \frac{\epsilon}{1-q}$, where $\epsilon << 1-q$. The volunteer match probabilities are given by $p_{1, 1} = \epsilon$ and $p_{1,2} = 1$. The left panel of Figure \[fig:exhardness\] visualizes Instance ${\mathcal{I}}_1$. The following lemma—which we prove in Appendix \[proof:exprophet\]—states that no online policy can complete more than a $\frac{1}{2-q}$ fraction of $\mathbf{LP}_{{\mathcal{I}}_1}$.

\[lem:exprophet\] In instance ${\mathcal{I}}_1$, The expected number of completed tasks under any online policy is at most $\frac{1}{2-q} LP_{{\mathcal{I}}_1}$.

Before proceeding to the second instance, we make two remarks: (1) If $q = 0$, the above instance is equivalent to the [canonical]{} instance used in the prophet inequality to establish an upper bound of $1/2$ (see, e.g., [@hill1992survey]). (2) The term $(1-1/e)$ in the competitive ratio of both policies corresponds to the gap between $f(\mathbf{x^*})$ (defined in ) and the benchmark $\mathbf{LP}$, whereas the $\frac{1}{2-q}$ corresponds to the gap between the performance of our online policy and $f(\mathbf{x^*})$ due to the loss in the online phase.In Instance ${\mathcal{I}}_1$, there is only one volunteer and consequently $f(\mathbf{x^*}) = \mathbf{LP}_{{\mathcal{I}}_1}$. Therefore, Instance ${\mathcal{I}}_1$ shows that the lower bound achieved in the online phase of our policies is tight, as they both attain at least $\frac{1}{2-q}f(\mathbf{x^*})$.

The construction of our second instance is more delicate as it aims to find an instance for which both the loss in the offline phase (i.e., the gap between $f(\mathbf{x^*})$ and $\mathbf{LP}_{{\mathcal{I}}}$) and the loss in the online phase (i.e., the gap between the performance of the online policy and $f(\mathbf{x^*})$) are large.

Suppose $V = \frac{1}{q} = n$, ${S}= 1$, $T=n^2+1$, and $g(\cdot)$ is the geometric distribution with parameter $q$, e.g. $g(\tau) = q(1-q)^{\tau-1}$. The arrival probabilities are given by $\lambda_{1, 1} = 1$ and $\lambda_{1, t} = q$ for $t \in [T] \setminus [1]$. The volunteers are homogeneous with $p_{v, 1} = q$ for all $v \in [V]$. The right panel of Figure \[fig:exhardness\] visualizes Instance ${\mathcal{I}}_2$. The following lemma—which is proven in Appendix \[proof:extightsmallq\]—states that no online policy can complete more than a $1 + q - \frac{q(1-q)}{\log(\frac{1}{1-q})(1+q)}(1-e^{-1})$ fraction of $LP_{{\mathcal{I}}_2}$.

\[lem:extightsmallq\] In instance ${\mathcal{I}}_2$, the expected number of completed tasks under any online policy is at most $\Big[1 + q - \frac{q(1-q)}{\log(\frac{1}{1-q})(1+q)}(1-e^{-1})\Big] \mathbf{LP}_{{\mathcal{I}}_2}$.

The proof of this lemma involves three steps: (1) placing a lower bound on $\mathbf{LP}_{{\mathcal{I}}_2}$ by finding a feasible solution, (2) establishing that always notifying every volunteer is the best online policy, and (3) assessing the performance of this policy relative to $\mathbf{LP}_{{\mathcal{I}}_2}$. A full proof can be found in Appendix \[proof:extightsmallq\].

![*Left:* Visualization of instance ${\mathcal{I}}_1$. *Right:* Visualization of instance ${\mathcal{I}}_2$.[]{data-label="fig:exhardness"}](instances_12.pdf){width=".9\textwidth"}

Evaluating Policy Performance on FRUS Data {#sec:data}
==========================================

In this section, we use data from FRUS to evaluate the performance of the two online policies described in Section \[sec:algos\]. First, we briefly explain how we use data to determine the model primitives. Then we exhibit the superior performance of our policies compared to policies that resemble the strategies used at various FRUS locations.

[**Estimating model primitives:**]{} As explained in Section \[sec:model\], in order to define an instance of the online volunteer notification problem, we must determine the match probabilities, i.e., $\{p_{v, {s}}: v \in [V], {s}\in [{S}]\}$; the arrival rates of tasks, i.e., $\{\lambda_{{s}, t}: {s}\in [{S}], t \in [T] \}$; and the inter-activity time distribution $g(\cdot)$.

-   [**Match probabilities:**]{} As evidenced in Figure \[fig:pcatotal\], volunteer preferences over tasks are heterogeneous and predictable. To come up with estimates $\{\hat{p}_{v,{s}}: v \in [V], {s}\in [{S}] \}$ for each FRUS location, we first create a feature vector for each task. We then build a $k$-Nearest Neighbors classification model, tuning the parameter $k$ using cross-validation. The AUCs of such classification models range between [0.89 and 0.95]{} across tested locations.

-   [**Arrival Rates:**]{} Recall that for FRUS, a task is a food rescue (donation) that remains available on the day of delivery. Most food rescues are repeated on a weekly cycle; therefore we define a type ${s}$ for each recurring rescue. Empirically, we observe a relationship between the last minute availability of a rescue of type ${s}$ and its status over the past six weeks [(the correlation coefficient is between $0.4$ and $0.75$ across all tested locations)]{}. Therefore, we estimate $\hat{\lambda}_{{s}, t} \in [0,1]$ as the proportion of times in the past six weeks that a rescue of type ${s}$ was a last-minute availability.

-   [**Inter-activity time distribution:**]{} At FRUS, [many]{} site directors follow a policy of waiting at least a week before notifying the same volunteer about another last-minute food rescue. Consequently, we assume the inter-activity time is deterministic and equal to seven days, e.g. $g(7) = 1$.

In the following, we compare the performance of our online policies to strategies that simulate the current practice at various FRUS locations using instances constructed with data from two different locations as described above. First, we compare our policies against ‘notify-1’ and ‘notify-3’ policies that, respectively, notify one and three volunteer(s) chosen uniformly at random among “eligible” volunteers. Note that here a volunteer is eligible if she has not been notified for at least 6 days. The top panels of Figure \[fig:numerics\] display the ratio between each policy and $\mathbf{LP}_{\mathcal{I}}$ across 50 simulations. We highlight that the SN policy significantly outperforms all other policies. Further note that the SN policy’s performance far exceeds its competitive ratio of $\frac{1}{2}(1-\frac{1}{e})$, as given in Theorem \[thm:alg2\], while the SDN policy performs only slightly above its competitive ratio.[^16]

Next, we compare our policies against a ‘notify-all’ policy that sends a notification to all volunteers. [This policy]{} clearly does not respect the 7-day gap between two successive notifications. Therefore, here we assume that the inter-activity time distribution is geometric with an expected duration of 7 days. The bottom panels of Figure \[fig:numerics\] display the ratio between each policy and $\mathbf{LP}_{\mathcal{I}}$ across 50 simulations. Here, we also observe that the SN policy significantly outperforms all other policies as well as its worst-case guarantee.

\[1.0\][ ![The top (resp. bottom) left plot shows the fraction of $\mathbf{LP}$ achieved in Location (a) using a deterministic (resp. geometric) inter-activity time distribution. The plots on the right do the same for Location (b).[]{data-label="fig:numerics"}](images/numerical_performance.pdf "fig:"){width=".9\textwidth"}]{}

Conclusion {#sec:conclude}
==========

In this paper, we take an algorithmic approach to a commonly faced challenge on volunteer-based crowdsourcing platforms: how to utilize volunteers for time-sensitive tasks at the “right” pace while [maximizing the number of completed]{} tasks. We introduce the online volunteer notification problem [to model]{} volunteer behavior as well as the trade-off that the platfrom faces in this online decision making process. We develop two online policies that achieve constant-factor guarantees [parameterized by the MDHR of the volunteer inter-activity time distribution, which gives insight into the impact of volunteers’ activity level. The guarantees provided by our policies]{} are close to the upper-bound we establish for the performance of any online policy. In this paper, we measure the performance of an online policy by comparing it to an LP-based benchmark which upper bounds a clairvoyant solution. From a theoretical perspective, considering other benchmarks (perhaps less strong) is an interesting future direction.

This work is motivated by our collaboration with FRUS, a leading volunteer-based food recovery platform, analysis of whose data confirms that, by and large, volunteers have persistent preferences. Leveraging on historical data, we estimate the match probability between volunteer-task pairs as well as the arrival rate of tasks. This enables us to test our policies on FRUS data from different locations and illustrate their effectiveness compared to common practice. From an applied perspective, studying the robustness of our policies as well as developing decision tools that can be integrated with the FRUS app are immediate next steps that we plan to pursue. Finding other platforms that can benefit from our work is another direction for future work.

Proofs for Section \[sec:model\]
================================

Proof of Proposition \[prop:LP\] {#proof:LP}
--------------------------------

To show that $\mathbf{LP}$ is an upper bound on the clairvoyant solution, we will construct a feasible solution $\mathbf{x} \in \mathcal{P}$ based on the clairvoyant solution. We will then prove that the value of this solution is an upper bound on the value of the clairvoyant solution.

Let us define the random realizations of inter-activity times as $\vec{Z} \in \vec{\mathcal{Z}} = \mathbb{N}^{[V] \times [T]}$, where $Z_{v,t}$ is the inter-activity time of volunteer $v$ if notified at time $t$. In addition, we denote the random arrival sequence as $\vec{{S}} \in \vec{\mathcal{{S}}} =  [{S}]^{[T]}$, where ${S}_t$ is the arrival at time $t$. Finally, suppose we have an indicator variable $\omega_{v,t}(\vec{{s}}, \vec{z})$, which is equal to one if and only if the clairvoyant solution contacts volunteer $v$ at time $t$ when the arrival order is given by $\vec{{s}}$ and the inter-activity times are given by $\vec{z}$. Because the clairvoyant solution does not know $Z_{v,t}$ until after time $t$, $\omega_{v,t}(\vec{{s}}, \vec{z})$ cannot depend on $z_{v,t'}$ for $t' \geq t$.

For any volunteer $v$, task $j$, and time $t$, we define $$\hat{x}_{v, j, t} = \sum_{\vec{{s}} \in \vec{\mathcal{{S}}}}\sum_{\vec{z} \in \vec{\mathcal{Z}}} {\mathbb{P}\left(\vec{{S}} = \vec{{s}}|{S}_t = j\right)} {\mathbb{P}\left(\vec{Z} = \vec{z}\right)} \omega_{v,t}(\vec{{s}}, \vec{z}).$$

To show that $\mathbf{\hat{x}} \in \mathcal{P}$ (see Definition \[def:P\]), we immediately note that $\hat{x}_{v,j,t} \in [0,1]$, since we are summing indicator variables over probability distributions. We now need to show that constraint $\eqref{eq:lpcon2}$ is met, namely that $1 \geq  \sum_{t' =1}^t \sum_{j =   1}^{{S}} \lambda_{j,t} \hat{x}_{v,j,t} (1-G(t-t'))$. Note that for a given sequence of arrivals $\vec{{s}}$ and inter-activity times given by $\vec{z}$, we must have $$\begin{aligned}
1 &\geq \sum_{t'=1}^t  \omega_{v,t'}(\vec{{s}},\vec{z}) {\mathbb{I}\Big(z_{v,t'} > t-t'\Big)}\end{aligned}$$ This is because both $\omega_{v,t'}(\vec{{s}},\vec{z})$ and ${\mathbb{I}\Big(z_{v,t'} > t-t'\Big)}$ are indicator variables, and if both equal $1$ at time $t'$, then the volunteer $v$ must be inactive until after time $t$. Since the clairvoyant solution only notifies active volunteers, if volunteer $v$ is inactive from $t'$ until after $t$, then $\omega_{v,t''}(\vec{{s}},\vec{z}) = 0$ for all $t'' \in [t'+1, t]$. Thus, the sum from $t'=1$ to $t'= t$ of the product of these indicator variables cannot exceed $1$. We now take a weighted sum over all possible arrival sequences and inter-activity times: $$\begin{aligned}
1 \geq& \sum_{t'=1}^t  \sum_{\vec{{s}} \in \vec{\mathcal{{S}}}} {\mathbb{P}\left(\vec{{S}} = \vec{{s}}\right)}\sum_{\vec{z} \in \vec{\mathcal{Z}}}{\mathbb{P}\left(\vec{Z} = \vec{z}\right)}  \omega_{v,t'}(\vec{{s}},\vec{z}) {\mathbb{I}\Big(z_{v,t'} > t-t'\Big)} \\
=&\sum_{t'=1}^t  \sum_{\vec{{s}} \in \vec{\mathcal{{S}}}} {\mathbb{P}\left(\vec{{S}} = \vec{{s}}\right)}\left(\sum_{\vec{z} \in \vec{\mathcal{Z}}}{\mathbb{P}\left(\vec{Z} = \vec{z}\right)}  \omega_{v,t'}(\vec{{s}},\vec{z})\right) \left(\sum_{\vec{z} \in \vec{\mathcal{Z}}}{\mathbb{P}\left(\vec{Z} = \vec{z}\right)} {\mathbb{I}\Big(z_{v,t'} > t-t'\Big)} \right) \label{eq:lpproof1} \\
=&\sum_{t'=1}^t  \sum_{\vec{{s}} \in \vec{\mathcal{{S}}}} {\mathbb{P}\left(\vec{{S}} = \vec{{s}}\right)}\left(\sum_{\vec{z} \in \vec{\mathcal{Z}}}{\mathbb{P}\left(\vec{Z} = \vec{z}\right)}  \omega_{v,t'}(\vec{{s}},\vec{z})\right) (1-G(t-t')) \label{eq:lpproof2} \\
=&\sum_{t'=1}^t  \sum_{j=1}^{{S}} \lambda_{j,t'} \sum_{\vec{{s}} \in \vec{\mathcal{{S}}}} {\mathbb{P}\left(\vec{{S}} = \vec{{s}} | {s}_{t'} = j\right)}\left(\sum_{\vec{z} \in \vec{\mathcal{Z}}}{\mathbb{P}\left(\vec{Z} = \vec{z}\right)}  \omega_{v,t'}(\vec{{s}},\vec{z})\right) (1-G(t-t')) \label{eq:lpproof3} \\
=& \sum_{t'=1}^t \sum_{j=1}^{{S}} \lambda_{j,t'}\hat{x}_{v,j,t'}(1-G(t-t')) \label{eq:lpproof4}\end{aligned}$$ In line , we use the independence of $\omega_{v,t'}(\vec{{s}},\vec{z})$ and ${\mathbb{I}\Big(z_{v,t'} > t-t'\Big)}$ to rewrite the expected value of their product as the product of their expectations. We substitute in the expected value of ${\mathbb{I}\Big(z_{v,t'} > t-t'\Big)}$ in line . In line , we use the law of total probability to sum over all possible arriving tasks in time $t'$. We then substitute in the definition of $\mathbf{\hat{x}}$ in line . This proves that $\mathbf{\hat{x}} \in {\mathcal{P}}$.

It remains to be shown that $\sum_{t=1}^T \sum_{{s}=1}^{{S}}   \lambda_{{s},t} \sum_{v =1}^{V} \min\{ \hat{x}_{v,{s},t}p_{v,{s}}, 1\}$ exceeds the value of the clairvoyant solution. Let $\mathcal{C}_{{s}, t}$ be the event that task ${s}$ arrives at time $t$ and is completed when following the clairvoyant solution. We must have ${\mathbb{P}\left( \mathcal{C}_{{s}, t}\right)} \leq \lambda_{{s},t}$. In addition, since a volunteer must respond in order to complete a task, we must have $${\mathbb{P}\left(\mathcal{C}_{{s}, t}\right)} \leq \lambda_{{s},t}\sum_{\vec{{s}} \in \vec{\mathcal{{S}}}}\sum_{\vec{z} \in \vec{\mathcal{Z}}} {\mathbb{P}\left(\vec{{S}} = \vec{{s}}|{S}_t = j\right)} {\mathbb{P}\left(\vec{Z} = \vec{z}\right)} \sum_{v =1}^{V} \omega_{v,t}(\vec{{s}}, \vec{z})p_{v,{s}} = \lambda_{{s},t} \sum_{v =1}^{V} \hat{x}_{v, {s}, t}p_{v,{s}}.$$ Combining these two bounds and summing over all tasks and time periods, we see that the clairvoyant solution must be less than $\sum_{t=1}^T \sum_{{s}=1}^{{S}}   \lambda_{{s},t} \sum_{v =1}^{V} \min\{ \hat{x}_{v,{s},t}p_{v,{s}}, 1\}$ Since $\mathbf{\hat{x}} \in {\mathcal{P}}$ and achieves a larger value than the clarivoyant solution, we have shown that $\mathbf{LP}$ is an upper bound on the clairvoyant solution.

Proofs for Section \[sec:algos\]
================================

Proof of Lemma \[lem:falg\] {#proof:falg}
---------------------------

Let $$\hat{f}(\mathbf{x}) := \sum_{v=1}^V f_v(\mathbf{x}) = \sum_{v=1}^V \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} \left(\prod_{u < v}(1-p_{u, {s}} x_{u, {s}, t})\right)  p_{v, {s}} x_{v, {s}, t}.$$ We prove by induction on $V$ that $f(\mathbf{x}) = \hat{f}(\mathbf{x})$, where $f(\mathbf{x})$ is defined in $\eqref{eq:fdef1}$. As a base case, suppose $V=1$. In this case, $f(\mathbf{x}) = \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} \left(1 - \prod_{v=1}^{V} (1- x_{v,{s},t}p_{v,{s}}) \right) = f_1(\mathbf{x})$ so $f(\mathbf{x})$ and $\hat{f}(\mathbf{x})$ are equivalent.

Now suppose this holds for $V = k$. We will show $f(\mathbf{x}) = \hat{f}(\mathbf{x})$ when $V = k+1$. $$\begin{aligned}
    f(\mathbf{x}) =& \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} \left(1 - \prod_{v =1}^{k+1} (1- x_{v,{s},t}p_{v,{s}}) \right) \\
    =& \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} \left(1 - (1-x_{k+1,{s},t}p_{k+1,{s}})\prod_{v =1}^{k} (1- x_{v,{s},t}p_{v,{s}}) \right) \\
    =&\sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} \left(1 - \prod_{v =1}^{k} (1- x_{v,{s},t}p_{v,{s}}) \right) \nonumber \\
    &+ \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} x_{k+1,{s},t}p_{k+1,{s}}\prod_{v =1}^{k} (1- x_{v,{s},t}p_{v,{s}}) \\
    =&\sum_{v =1}^k f_v(\mathbf{x}) + \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} x_{k+1,{s},t}p_{k+1,{s}}\prod_{v =1}^{k} (1- x_{v,{s},t}p_{v,{s}}) \label{eq:proof:falg1}\\
    =&\sum_{v =1}^{k+1} f_v(\mathbf{x}) \\
    =&\hat{f}(\mathbf{x})\end{aligned}$$ All steps are algebraic except for Line , which makes use of the inductive hypothesis. This completes the proof by induction that the two formulas are algebraically equivalent.

Proof of Proposition \[prop:fxstar\] {#proof:fxstar}
------------------------------------

To prove this proposition, we first focus on a particular task ${s}$ at a particular time $t$ and prove that for any $\mathbf{x} \in {\mathcal{P}}$, $$1-\prod_{v=1}^{V}(1-x_{v,{s},t}p_{v,{s}}) \geq (1-\frac{1}{e})\min \{\sum_{v =1}^{V}  x_{v,{s},t}p_{v,{s}}, 1\}.$$

To prove the above inequality, we find the minimum possible value of $1-\prod_{v=1}^{V}(1-x_{v,{s},t}p_{v,{s}})$ when $\min \{\sum_{v =1}^{V}  x_{v,{s},t}p_{v,{s}}, 1\}$ is fixed and equal to $c \in [0,1]$. This is equivalent to solving the program: $$\begin{aligned}
    \text{maximize}_{\mathbf{x} \in [0,1]^{V}} \quad \  &\prod_{v=1}^{V}(1-x_{v,{s},t}p_{v,{s}}) \label{eq:fxstarproof} \\
    \text{subject to} \quad \quad \quad  c\geq& \sum_{v =1}^{V} x_{v,{s},t}p_{v,{s}} \nonumber\end{aligned}$$

\[claim:prooflemfxstar1\] For a fixed number of volunteers $V = n$, the value of is less than or equal to $(1-\frac{c}{n})^n$.

[Proof:]{} First, we make a change of variables $y_{v,{s},t} = x_{v,{s},t}p_{v,{s}}$, where $y_{v,{s},t} \in [0, p_{v,{s}}]$. Relaxing this constraint to $y_{v,{s}, t} \in [0, 1]$ provides an upper bound on . We now prove by induction on $n$ that the solution to this relaxed problem is $y_{v,{s},t} = \frac{c}{n}$ for all $v$. In the base case with one volunteer, the objective becomes maximizing $y_{1,{s},t}$ subject to $y_{1,{s},t} \leq c$, which has a clear solution.

We now assume this holds for $n=k$. If there are $k+1$ volunteers, we consider the problem $$\begin{aligned}
    \text{maximize}_{\mathbf{y} \in [0,1]^{k+1}} \quad \  &(1-y_{k+1,{s}, t})\left(\prod_{v \leq k}(1-y_{v,{s},t})\right) \nonumber \\
    \text{subject to} \quad \quad \quad  c\geq& y_{k+1,{s},t} + \sum_{v=1}^k y_{v,{s},t} \nonumber\end{aligned}$$ For any given $y_{k+1, {s}, t} \in [0,1]$, we can apply the inductive hypothesis to solve $y_{v,{s},t} = \frac{c-y_{k+1, {s}, t}}{k}$ for $v \in [k]$. This yields a single variable maximization problem with objective function $(1-y_{k+1,{s},t})(1-\frac{c-y_{k+1, {s}, t}}{k})^k$. Taking the derivative, this has first order condition of $$(1-\frac{c-y_{k+1, {s}, t}}{k})^{k-1}(1-y_{k+1,{s},t}-1+\frac{c-y_{k+1, {s}, t}}{k}) = 0.$$ One can verify that the solution $y_{k+1,{s},t} = \frac{c}{k+1}$ is the maximum. This implies that $y_{v,{s},t} = \frac{c-y_{k+1, {s}, t}}{k} = \frac{c}{k+1}$ for all $v \in [k+1]$, which completes the proof by induction. Plugging these values for $y_{v,{s},t}$ into the objective function, we get a value of $(1-\frac{c}{n})^n$, which completes the proof of Claim \[claim:prooflemfxstar1\].

Based on this claim, $1-\prod_{v=1}^{V}(1-x_{v,{s},t}p_{v,{s}})$ must be greater than $1-(1-\frac{c}{n})^n$ when $\sum_{v =1}^{V}x_{v,{s},t}p_{v,{s}} \geq c$. This means that the ratio between the two must be at least $\frac{1-(1-\frac{c}{n})^n}{c}$.

For any $n \in \mathbb{N}$ and $c \in [0,1]$, the function $\frac{1-(1-\frac{c}{n})^n}{c}$ is greater than $1-\frac{1}{e}$.

[Proof:]{} We first show that $n \log(1-\frac{c}{n})$ is increasing in $n$, which implies that the numerator is decreasing in $n$. The derivative of that expression with respect to $n$ is given by $\log(1-\frac{c}{n}) + \frac{c}{n-c} \geq \frac{-c}{n-c} + \frac{c}{n-c} = 0$, using the inequality $\log(1-x) \geq \frac{-x}{1-x}$. This means that the function is decreasing in $n$, regardless of $c$.

Taking the limit as $n$ gets large, the ratio can be written as $\frac{1-e^{-c}}{c}$. The derivative of this expression with respect to $c$ is given by $\frac{(1+c)e^{-c} - 1}{c^2} \leq \frac{(1+c)(1-c) - 1}{c^2} \leq 0$. Thus, this expression is decreasing in $c$. It is minimized at $c=1$, where it attains a value of $1-\frac{1}{e}$.

Proving this claim establishes that for any $\mathbf{x} \in {\mathcal{P}}$, any task ${s}\in [{S}]$, and any time $t \in [T]$, $1-\prod_{v=1}^{V}(1-x_{v,{s},t}p_{v,{s}}) \geq (1-\frac{1}{e}) \min\{\sum_{v =1}^{V}  x_{v,{s},t}p_{v,{s}}, 1 \}$.

If we apply this inequality to $\mathbf{x^*_{LP}}$ and take a weighted sum over all tasks and time periods, this completes the proof of the proposition, e.g. $f(\mathbf{x^*_{LP}}) \geq (1-\frac{1}{e})\mathbf{LP}$.

Proof of Lemma \[lem:beta\] {#proof:beta}
---------------------------

We begin by proving that $\beta_{v,t} \geq \frac{1}{2-q}$. Since we set $\beta_{v,1} =1$, this clearly holds for all $v \in [V]$ when $t=1$. Without loss of generality, this proof will now focus on a particular $v \in [V]$ and $t \in [T]\setminus [1]$.

Starting from the definition, we have: $$\begin{aligned}
    \beta_{v,t} &=  1 - \sum_{t'=1}^{t-1} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} \frac{x^*_{v,{s}, t'}}{2-q}(1-G(t - t')) \\
    &=1-\frac{1}{2-q}\left(\sum_{t'=1}^{t-1} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} x^*_{v,{s}, t'}(1-G(t - t'-1)-g(t-t'))\right) \\
    &=1-\frac{1}{2-q}\left(\sum_{t'=1}^{t-1} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} x^*_{v,{s}, t'}(1-G(t - t'-1))(1-\frac{g(t-t')}{1-G(t-t'-1)})\right) \\
    &\geq 1-\frac{1}{2-q}\left(\sum_{t'=1}^{t-1} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} x^*_{v,{s}, t'}(1-G(t - t'-1))(1-q)\right) \label{eq:betaline1} \\
    &\geq 1-\frac{1-q}{2-q} \label{eq:betaline2} \\
    &=\frac{1}{2-q}\end{aligned}$$ Line comes from applying the definition of the minimum hazard rate. Because $\mathbf{x^*} \in {\mathcal{P}}$ (see Definition \[def:P\]), in line we apply the bound given by constraint for $t-1$. This holds for any $v \in [V]$ and any $t \in [T]\setminus [1]$, which implies that $\beta_{v,t} \geq \frac{1}{2-q}$ for all $v \in [V]$ and $t \in [T]$.

We now use total induction to prove that ${\mathbb{P}\left(\mathcal{E}_{v,t}\right)} = \beta_{v,t}$. For notation, we will use $\mathcal{E}^C$ to refer to the complement of event $\mathcal{E}$. At $t=1$, we have ${\mathbb{P}\left(\mathcal{E}_{v,t}\right)}=1$ and $\beta_{v,t} = 1$ by definition. Now we assume that $\beta_{v,t} = {\mathbb{P}\left(\mathcal{E}_{v,t}\right)}$ for all $t \in [k]$. A volunteer can only be inactive at time $t$ if she was notified in a prior period and does not become active again by time $t$. Since these events are disjoint, we can sum their probabilities to compute the probability that a volunteer is inactive at time $k+1$: $${\mathbb{P}\left(\mathcal{E}_{v,k+1}^C\right)} = \sum_{t'=1}^{k} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} {\mathbb{P}\left(\mathcal{E}_{v,t'}\right)}\frac{x^*_{v,{s}, t'}}{(2-q)\beta_{v,t'}}(1-G(t-t'))$$ Because notifications are independent from each volunteer’s status, the notification probability conditional on a volunteer being active is still $\frac{x^*_{v,{s}, t'}}{(2-q)\beta_{v,t'}}$ when following Algorithm \[alg:one\]. Plugging in the inductive hypothesis that ${\mathbb{P}\left(\mathcal{E}_{v,t'}\right)} = \beta_{v,t'}$ for $t' \in [k]$, we see that these terms cancel, leaving us with $${\mathbb{P}\left(\mathcal{E}_{v,k+1}^C\right)} = \sum_{t'=1}^{k} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} \frac{x^*_{v,{s}, t'}}{2-q}(1-G(t-t'))$$ Noting that this sum is definitionally equivalent to $1-\beta_{v, k+1}$ completes the proof.

Proof of Lemma \[lem:contributionsalg1\] {#proof:contributionsalg1}
----------------------------------------

Without loss of generality, this proof will focus on a particular arrival ${s}\in [{S}]$ at a particular time $t \in [T]$. Under an index-based priority scheme, the probability that a volunteer $v \in [V]$ completes this task is equal to $${\mathbb{P}\left(v \text{ responds}\right)}{\mathbb{P}\left(\text{no volunteer with lower index responds}| v \text{ responds}\right)}$$

We start by numerically defining the first term. By Lemma \[lem:beta\], volunteer $v$ will be active at time $t$ with probability $\beta_{v,t}$, and according to Algorithm \[alg:one\], she will be notified with probability $\frac{x^*_{v, {s}, t}}{\beta_{v,t}(2-q)}$. If active, the volunteer will respond to a notification with probability $p_{v,{s}}$. Since these events are all independent, the volunteer will respond to a notification about task ${s}$ at time $t$ with probability $\frac{x^*_{v, {s}, t}}{(2-q)} p_{v,{s}}$.

We now bound the second term. First note that volunteers only respond if they are active, notified, and match with the task. Thus, for any other volunteer $u$, $${\mathbb{P}\left(u \text{ does not respond }| v \text{ responds}\right)} \geq {\mathbb{P}\left(u \text{ not notified or does not match }| v \text{ responds}\right)}$$ Volunteer $u$ will be notified with probability $ \frac{x^*_{u, {s}, t}}{\beta_{u,t}(2-q)} \leq x^*_{u, {s}, t}$ and will match independently with probability $p_{u,{s}}$. Since these events are both independent of $v$ responding, $${\mathbb{P}\left(u \text{ does not respond}| v \text{ responds}\right)} \geq  1 - x^*_{u, {s}, t}p_{u,{s}}$$ Thus, the probability that no other volunteers respond *conditional on $v$ responding* is lower bounded by $${\mathbb{P}\left(\text{no volunteer with lower index responds}| v \text{ responds}\right)} \geq \prod_{u < v} (1-x^*_{u, {s}, t}p_{u,{s}})$$

We have shown that for any arrival ${s}\in [{S}]$ at time $t \in [T]$, volunteer $v \in [V]$ completes the task with probability greater than $\frac{1}{2-q}\left(\prod_{u < v} (1-x^*_{u, {s}, t}p_{u,{s}})\right)x^*_{v, {s}, t} p_{v,{s}}$. Using linearity of expectations, the expected number of tasks completed by $v$ is given by $$\frac{1}{2-q} \sum_{t=1}^T \sum_{{s}=1}^{S}\lambda_{{s},t} \left(\prod_{u < v} (1-x^*_{u, {s}, t}p_{u,{s}})\right)x^*_{v, {s}, t} p_{v,{s}} = f_v(\mathbf{x^*}).$$

Proof of Theorem \[thm:alg1\] {#proof:thmalg1}
-----------------------------

Based on Lemma \[lem:contributionsalg1\], we know that each volunteer completes at least $\frac{1}{2-q}f_v(\mathbf{x^*})$ tasks in expectation. By linearity of expectations and Lemma \[lem:falg\], the expected total number of tasks completed by volunteers must be at least $\frac{1}{2-q}f(\mathbf{x^*})$. Since $f(\mathbf{x^*}) \geq (1-\frac{1}{e})\mathbf{LP}_{\mathcal{I}}$ (see Proposition \[prop:fxstar\]), it immediately follows that the SDN policy is $\frac{1}{2-q}(1-\frac{1}{e})$-competitive.

Proof of Lemma \[lem:contributionsalg2\] {#proof:contributionsalg2}
----------------------------------------

The proof of Lemma \[lem:contributionsalg2\] consists of two parts. First, we prove that $r_{v, {s}, t}$ is a lower bound on the probability that a volunteer $v \in [V]$ completes a task ${s}\in [{S}]$ when it arrives at time $t \in [T]$, conditional on being notified and active under the index-based priority scheme. Then, we show that $J_{v,t}$ represents the value-to-go of volunteer $v$ when active at $t$ under the SN policy with rewards $\{r_{v,{s}, t}:{s}\in [{S}], t \in [T] \}$.

Without loss of generality, we focus on a particular arrival ${s}$ at a particular time $t$. When notified and active, a volunteer $v \in [V]$ responds with probability $p_{v,{s}}$. Any other volunteer $u \in [v-1]$ is notified with probability ${\tilde{x}}_{u, {s}, t}$ under the SN policy. If active, she will respond with probability $p_{u,{s}}$. Since these are both independent from $v$’s response, the probability that $u$ responds conditional on $v$ responding must be less than ${\tilde{x}}_{u, {s}, t}p_{u, {s}}$. Therefore, the probability that $v$ completes the task when active and notified—which happens when she is the lowest indexed volunteer to respond—must exceed $p_{v,{s}}\prod_{u =1}^{v-1}(1-{\tilde{x}}_{u, {s}, t}p_{u, {s}})$. Noting that this is equivalent to the definition of $r_{v,{s}, t}$ completes the first part of the proof.

We now show via total induction that $J_{v,t}$ represents the value-to-go of volunteer $v$ when active at $t$ under the SN policy with rewards $\{r_{v,{s}, t}:{s}\in [{S}], t \in [T] \}$. Clearly, this is true for $J_{v,T+1}$. Now suppose it is true for all $t \geq \tau+1$. We will show that this is true for $t=\tau$. From the definition in , $$\begin{aligned}
 J_{v,\tau} = \sum_{{s}=1}^{{S}} \lambda_{{s}, \tau}\left((1-{\tilde{x}}_{v, {s}, \tau}){J}_{v,\tau+1} + {\tilde{x}}_{v,{s},\tau}( r_{v,{s},\tau} + \sum_{t' = t+1}^{T} g(t' - t){J}_{v, t'}) \right)
 \end{aligned}$$ For any task ${s}\in [{S}]$, the SN policy notifies $v$ with probability ${\tilde{x}}_{v,{s},\tau}$. Assuming that $v$ is active and using the inductive hypothesis, the value-to-go if she is notified is given by $r_{v,{s},\tau} + \sum_{t' = t+1}^{T} g(t' - t){J}_{v, t'}$. If she is not notified, her value-to-go is $J_{v,\tau+1}$. This shows that $J_{v,\tau}$ represents the value-to-go of volunteer $v$ when active at $\tau$ under the SN policy with rewards $\{r_{v,{s}, t}:{s}\in [{S}], t \in [T] \}$, which completes the proof by induction.

We note that $J_{v,t}$ as defined in is weakly increasing in each $r_{v,{s}, t}$. Since we have shown that the rewards are weakly greater than $r_{v,{s}, t}$, we have completed the proof of Lemma \[lem:contributionsalg2\].

Proof of Lemma \[lemma:factorrevealingLP\] {#proof:factorrevealingLP}
------------------------------------------

We prove this lemma with an LP described in Table \[table:lpdual\]. For ease of reference, we have copied the LP and its dual below.

We aim to show that ${J}_{v,1} \geq \frac{1}{2-q} c$, where $c$ is an arbitrary constant imposed in the final constraint of (J-LP). The other constraints in our LP come from the definition of ${J}_{v,t}$: $$\begin{aligned}
    {J}_{v,t} &= \sum_{{s}=1}^{{S}} \lambda_{{s}, t} \max_{x_{v,{s},t} \in \{0, x^*_{v, {s}, t}\}} \{ (1-x_{v,{s}, t}){J}_{v,t+1} + x_{v,{s}, t}(r_{v,{s},t} + \sum_{\tau = t+1}^{T+1} g(\tau - t){J}_{v, \tau}) \} \\
    &\geq \max\{{J}_{v,t+1}, \sum_{{s}=1}^{{S}} \lambda_{{s}, t}(1-x^*_{v,{s}, t}){J}_{v,t+1}+ x^*_{v,{s}, t}(r_{v,{s},t} + \sum_{\tau = t+1}^{T+1} g(\tau - t){J}_{v, \tau})\} \\
    &=\max\{{J}_{v,t+1}, {J}_{v,t+1}+\sum_{{s}=1}^{{S}} \lambda_{{s}, t} x^*_{v,{s}, t}(r_{v,{s},t} -{J}_{v,t+1} + \sum_{\tau = t+1}^{T+1} g(\tau - t){J}_{v, \tau})\}\end{aligned}$$ Together there are $2T + 1$ constraints, which will become the dual variables identified by the labels above. This leads to the dual program in (Dual).

A feasible solution to this dual problem is when $\mu = \frac{1}{2-q}$ and all constraints are tight, i.e. $\gamma_t = \mu$ for all $t$, $\alpha_1 = 1-\mu$, and for $t \geq 2$, $$\begin{aligned}
    \alpha_t &= \alpha_{t-1} - \gamma_{t-1}\sum_{{s}=1}^{{S}} \lambda_{{s},t}x^*_{v,{s},t} + \sum_{t' =1}^{t-1}\beta_{t'} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} x^*_{v,{s},t'}g(t-t') \\
    &=\alpha_{t-1} - \mu \left( \sum_{{s}=1}^{{S}} \lambda_{{s},t}x^*_{v,{s},t} -  \sum_{t' =1}^{t-1} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} x^*_{v,{s},t'}g(t-t') \right) \\
    &= \alpha_1 - \mu \sum_{t' =1}^{t-1} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} x^*_{v,{s},t'}(1-G(t-t')) \label{eq:flp1}\\
    &=\alpha_1 - \mu \sum_{t' =1}^{t-1} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} x^*_{v,{s},t'}(1-G(t-1-t'))(1-\frac{g(t-t')}{1-G(t-1-t')})\label{eq:flp2} \\
    &\geq  \alpha_1 - \mu \sum_{t' =1}^{t-1} \sum_{{s}=1}^{{S}} \lambda_{{s},t'} x^*_{v,{s},t'}(1-G(t-1-t'))(1-q) \label{eq:flp3}\\
    &\geq \alpha_1 - (1-q)\mu \label{eq:flp4} \\
    &= 1 - (2-q)\mu\end{aligned}$$ Line comes from recursively plugging in the definition for $\alpha_{t-1}$ and rearranging terms. Line comes from applying the definition of the minimum hazard rate. Line uses the fact that $\mathbf{x^*} \in {\mathcal{P}}$, which means it must satisfy at time $t-1$.

Since $\mu = \frac{1}{2-q}$, we must have $\alpha_t \geq 0$, which means this solution is feasible in (Dual). Therefore, by weak duality, we have shown that the primal problem has a value of at least $\frac{1}{2-q} c \geq \frac{1}{2-q} \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} r_{v, {s}, t} x^*_{v,{s},t}$.

We conclude by noting that $\left(\prod_{u \leq v}(1-p_{u, {s}} x_{u, {s}, t})\right)  p_{v, {s}}$ is decreasing in $x_{u,{s},t}$. Since ${\tilde{x}}_{u, {s}, t} \leq x^*_{u,{s},t}$, this implies $r_{v,{s},t} \geq \left(\prod_{u \leq v}(1-p_{u, {s}} x^*_{u, {s}, t})\right)  p_{v, {s}}$. Thus, $$J_{v,1} \geq \frac{1}{2-q} \sum_{t=1}^T \sum_{{s}=1}^{{S}} \lambda_{{s},t} \left(\prod_{u \leq v}(1-p_{u, {s}} x^*_{u, {s}, t})\right)  p_{v, {s}} x^*_{v, {s}, t} = f_v(\mathbf{x^*}),$$ which completes the proof of Lemma \[lemma:factorrevealingLP\].

Proof of Theorem \[thm:alg2\] {#proof:thmalg2}
-----------------------------

Based on Lemma \[lemma:factorrevealingLP\], we know that each volunteer completes at least $\frac{1}{2-q}f_v(\mathbf{x^*})$ tasks in expectation. By linearity of expectations and Lemma \[lem:falg\], the expected total number of tasks completed by volunteers must be at least $\frac{1}{2-q}f(\mathbf{x^*})$. Since $f(\mathbf{x^*}) \geq (1-\frac{1}{e})\mathbf{LP}_{\mathcal{I}}$ (see Proposition \[prop:fxstar\]), it immediately follows that the SN policy is $\frac{1}{2-q}(1-\frac{1}{e})$-competitive.

Proofs for Section \[sec:hardness\]
===================================

Proof of Lemma \[lem:exprophet\] {#proof:exprophet}
--------------------------------

In instance ${\mathcal{I}}_1$, a feasible solution to (LP) is to always notify the volunteer when task $2$ arrives in period $2$ and to notify the volunteer in period $1$ as much as possible subject to constraint , e.g. $\hat{x}_{1, 2, 2} = 1$ and $\hat{x}_{1, 1, 1} = 1-\epsilon$. This strategy achieves $(1-\epsilon)\epsilon + \frac{\epsilon}{1-q} = \epsilon(\frac{2-q-(1-q)\epsilon}{1-q})$ completed tasks in expectation.

Since it is clearly optimal to notify $v$ in period $2$, an online policy only has one choice to make: whether or not to notify $v$ in period $1$. If notified in period $1$, $v$ will complete $\epsilon + q\frac{\epsilon}{1-q} = \frac{\epsilon}{1-q}$ tasks in expectation. Otherwise, $v$ will complete $\frac{\epsilon}{1-q}$ tasks in expectation. Thus, no online policy can achieve a value greater than $\frac{\epsilon}{1-q}$. This represents a competitive ratio of no more than $\frac{1}{2-q-(1-q)\epsilon}$, which approaches $\frac{1}{2-q}$ as $\epsilon$ gets small.

Proof of Lemma \[lem:extightsmallq\] {#proof:extightsmallq}
------------------------------------

We prove Lemma \[lem:extightsmallq\] in three steps. First, we show $\mathbf{LP} \geq n$. Then, we establish that always notifying every volunteer is the best online policy. Finally, we assess the performance of this policy relative to $\mathbf{LP}$.

In ${\mathcal{I}}_2$, $\mathbf{LP} \geq n$

[Proof:]{} To prove this claim, we first show that solution $\hat{x}_{v, {s}, t} = 1$ for all $v \in [n]$ and $t \in [T]$ is feasible. Clearly, it satisfies constraint . Now consider for an arbitrary $v \in [n]$ and $t \in [T]$: $$\begin{aligned}
\sum_{\tau =1}^{t} \lambda_{1, \tau} \hat{x}_{v,{s},t} (1-q)^{t-\tau} &= (1-q)^{t-1} + \sum_{\tau = 2}^t q(1-q)^{t-\tau}  \\
&= (1-q)^{t-1} + q \sum_{\tau' = 0}^{t-2} (1-q)^{\tau'} \\
&= (1-q)^{t-1} + q \frac{1 - (1-q)^{t-1}}{q} \\ &= 1\end{aligned}$$

The first step comes from plugging in $\lambda_{1,1} = 1$ and $\lambda_{1,\tau} = q$ for $\tau \in [T]\setminus [1]$. Now that we have established the feasibility of $\mathbf{\hat{x}}$, we can calculate the value of (LP) at that solution, which is given by $$\sum_{t=1}^{T} \lambda_{{s},t}  \min \{\sum_{v =1}^{V} \hat{x}_{v,{s},t} q,1\}  = \sum_{t=1}^{T} \lambda_{{s},t} = 1 + n \geq n.$$

Now that we have an lower bound on $\mathbf{LP}$, we turn our attention to placing an upper bound on any online policy. We do so with the following claim.

Notifying every active volunteer whenever task $1$ arrives achieves a higher expected value than any online policy.

[Proof:]{} We first note that the best online policy cannot do better in expectation than the best online policy that also knows the status of each volunteer $v \in [V]$ at each time $t \in [T]$ because designing a policy without using that additional information is always an option. Thus, it is sufficient to show that notifying every active volunteer whenever task $1$ arrives achieves a higher expected value than any online policy that knows each volunteer’s status.

We proceed via total induction, with a base case at time $T$. Suppose an arrival occurs at time $T$. If there are ${\alpha_1}$ active volunteers, notifying ${\alpha_2}$ of them achieves a value-to-go of $1-(1-q)^{{\alpha_2}}$. This is increasing in ${\alpha_2}$, which means that the optimal online policy is to contact all active volunteers.

Let ${\hat{J}}_{\tau+1}$ represent the expected value-to-go when an arrival occurred in period $\tau$ given an online policy that notifies all active volunteers at $\tau$ and all future arrivals. Note that we can only make this representation because the inter-activity times are geometrically distributed, which implies that volunteers’ transitions from inactive to active are memoryless. Thus the expected payoff is the same regardless of the choices made before period $\tau$. By convention, we set ${\hat{J}}_{T+1} = 0$.

Now we make the inductive hypothesis that contacting all active volunteers whenever task $1$ arrives is the best online policy for $t \in [T]\setminus [k]$. We will show that if an arrival occurs at time $k$, an optimal online policy is to contact all active volunteers. The expected payoff of contacting ${\alpha_2}$ volunteers when ${\alpha_1}$ are active is given by $$\begin{aligned}
   {h}_{k, {\alpha_1}}({\alpha_2}) =& {\mathbb{P}\left(\text{task completed at time $k$}\right)} + {\mathbb{E}\left(\text{tasks completed from $k+1$ to $T$}\right)} \\
   =& {\mathbb{P}\left(\text{task completed at time $k$}\right)} + \nonumber \\ &\sum_{\tau = k+1}^T {\mathbb{P}\left(\text{next arrival at $\tau$}\right)}{\mathbb{E}\left(\text{tasks completed from $k+1$ to $T$}|\text{next arrival at $\tau$}\right)} \label{eq:hk1} \\
   =&1 - (1-q)^{{\alpha_2}} + \label{eq:hk2} \\
   &\sum_{\tau = k+1}^T q(1-q)^{\tau - k - 1} \left(1 - (1-q)^{{\alpha_1}-{\alpha_2}}(1 - q (1 - (1-q)^{\tau - k}))^{n - {\alpha_1}+{\alpha_2}} \right) + \label{eq:hk3} \\
   &\sum_{\tau = k+1}^T q(1-q)^{\tau - k - 1} {\hat{J}}_{\tau+1} \label{eq:hk4}\end{aligned}$$ In line , we use the law of total probability. Line represents the probability of completing the task at time $k$. Each term in the summation in line represents the probability that the next task arrives at $\tau$ and that task gets completed. To compute this probability, first note that we know that at time $\tau$ there will be ${\alpha_2}-{\alpha_1}$ volunteers who are definitely active. The remaining volunteers will be independently active with probability $1 - (1-q)^{\tau - k}$. Thus, each of these remaining volunteers will respond to a notification with probability $q(1 - (1-q)^{\tau - k})$. Since the inductive hypothesis assumes that the online policy will contact every active volunteer at $\tau > k$, the probability of any volunteer completing the next task (conditional on an arrival at $\tau$) is given by $1 - (1-q)^{{\alpha_1}-{\alpha_2}}(1 - q (1 - (1-q)^{\tau - k}))^{n - {\alpha_1}+{\alpha_2}}$. In line , we add the remaining expected number of completed tasks from $\tau+1$ to $T$ after an arrival in period $\tau$, which does not depend on the choice of ${\alpha_2}$ due to the memorylessness of the transitions from inactive to active.

We now define $\Delta_{k,{\alpha_1}}({\alpha_2}) = {h}_{k,{\alpha_1}}({\alpha_2}+1) - {h}_{k,{\alpha_1}}({\alpha_2})$ for $0 \leq {\alpha_2}\leq {\alpha_1}-1$. This is the incremental benefit of notifying one additional active volunteer. We have $$\begin{aligned}
    \Delta_{k,{\alpha_1}}({\alpha_2}) =& (1-q)^{{\alpha_2}} - (1-q)^{{\alpha_2}+1} + \sum_{\tau = k+1}^T q(1-q)^{\tau - k - 1} \cdot \nonumber \\ &[(1-q)^{{\alpha_1}-{\alpha_2}}(1 - q (1 - (1-q)^{\tau - k}))^{n - {\alpha_1}+{\alpha_2}} \nonumber \\&- (1-q)^{{\alpha_1}-{\alpha_2}-1}(1 - q (1 - (1-q)^{\tau - k}))^{n - {\alpha_1}+{\alpha_2}+1} ] \label{longeq:1} \\
    =& q(1-q)^{{\alpha_2}} + \sum_{\tau = k+1}^T q(1-q)^{\tau - k - 1}(1-\frac{1 - q (1 - (1-q)^{\tau - k})}{1-q}) \cdot \nonumber \\
    &[(1-q)^{{\alpha_1}-{\alpha_2}}(1 - q (1 - (1-q)^{\tau - k}))^{n - {\alpha_1}+{\alpha_2}}] \label{longeq:2} \\
        =& q(1-q)^{\alpha_2}- \sum_{\tau = k+1}^T q(1-q)^{\tau - k - 1}(q (1-q)^{\tau - k-1}) \cdot \nonumber \\
    &[(1-q)^{{\alpha_1}-{\alpha_2}}(1 - q (1 - (1-q)^{\tau - k}))^{n - {\alpha_1}+{\alpha_2}}] \label{longeq:3} \\
    \geq& q(1-q)^{{\alpha_1}-1} - \sum_{\tau = k+1}^T q^2(1-q)^{2(\tau - k - 1)}\cdot \nonumber \\ &[(1-q)(1 - q (1 - (1-q)^{\tau - k}))^{n-1}] \label{longeq:4} \\
    \geq& q(1-q)^{n-1} - \sum_{\tau' = 1}^\infty q^2(1-q)^{2\tau' - 1}(1 - q (1 - (1-q)^{\tau'}))^{n-1}\label{longeq:5} \\
    =& q(1-q)^{n-1} \left( 1 - \sum_{\tau' = 1}^\infty q(1-q)^{2\tau' - 1}(1 + q(1-q)^{\tau'-1}))^{n-1} \right)\label{longeq:6} \\
     \geq& q(1-q)^{n-1} \left( 1 - \sum_{\tau' = 1}^\infty q(1-q)^{2\tau' - 1}e^{(1-q)^{\tau'-1}} \right)\label{longeq:7}
    \end{aligned}$$

false $$\begin{aligned}
    \geq& q(1-q)^{n-1} - q^2(1-q)(1-q^2)^{n-1} \nonumber \\ 
    &- \int_{t = 1}^\infty q^2(1-q)^{2t - 1}(1 - q (1 - (1-q)^{t}))^{n-1} \ dt \label{longeq:8} \\
    \geq& q(1-q)^{n-1} + \frac{q^2}{(1-q)\log(1-q)} \int_{u = q}^1 (1-u)(1 - qu )^{n-1} \ du \label{longeq:9} \\
    \geq& q(1-q)^{n-1} + \frac{q^2}{(1-q)\log(1-q)}\left(\frac{(u-q)(1-qu)^n}{1+q} \right)|_{u=q}^1 \label{longeq:10} \\
    \geq & q(1-q)^{n-1} + \frac{q^2}{(1-q)\log(1-q)}\left(\frac{(1-q)^{n+1}}{1+q} \right) \label{longeq:11}\end{aligned}$$

In line we factor like terms. In line we simplify the fraction. In line we combine powers in the top line and lower bound the expression by replacing ${\alpha_2}$ with ${\alpha_1}-1$, its maximum value. Note that this decreases the positive term and increases the negative term. In line , we simplify the bounds of the summation and provide a lower bound (an upper bound on a negative term) by summing all the way to infinity. We also provide a lower bound by setting ${\alpha_1}= n$, which decreases the first term and otherwise has no impact.

Numerically we can verify that is greater than 0 for all $n \geq 1$ (recall we define $q = \frac{1}{n}$). To prove this algebraically, we first factor out terms and simplify to get . We then use the fact that $(1+\frac{r}{n})^{n-1} \leq e^r$ to get the bound in . We can show term by term that the summation is decreasing in $q$. This implies that the inner term is increasing in $q$. We can show via an integral bound that the inner term approaches 0 as $q \rightarrow 0$. Putting these facts together imply that as $q$ increases, the inner term is weakly positive. This would complete an algebraic proof that is non-negative.

Since $\Delta_{k,{\alpha_1}}({\alpha_2}) \geq 0$ for all ${\alpha_2}\leq {\alpha_1}-1 \leq n-1$, we have proved the inductive hypothesis that notifying all active volunteers in period $k$ is optimal. This completes the proof of the claim.

We now provide an upper bound on the value of this optimal online policy.

The value of notifying every active volunteer whenever task ${s}$ arrives is at most $q+\left(1 - \frac{q(1-q)}{\log(\frac{1}{1-q})(1+q)}(1-e^{-1}) \right)$.

[Proof:]{} If we notify every volunteer at every arrival, then in the first period, we achieve a payoff of $1-(1-q)^n \leq 1$. Now suppose every volunteer was most recently notified at time $\tau-1$. The expected reward for the remainder of the time horizon is given by ${\hat{J}}(\tau)$. By definition, the value of this policy is given by $1-(1-q)^n +{\hat{J}}(2) \leq 1 +{\hat{J}}(2)$. Note that ${\hat{J}}(T+1) = 0$, and we can recursively compute: $$\begin{aligned}
{\hat{J}}(\tau) &= \sum_{t=\tau}^{T} q(1-q)^{t-\tau}\left( 1-(1-q(1-(1-q)^{t-\tau+1}))^n + {\hat{J}}(t+1) \right) \end{aligned}$$ We now proceed to place a bound on ${\hat{J}}(2)$. Let ${\zeta}$ be the expected probability of completing the next task unconditional on when it arrives, i.e. $${\zeta}:=\sum_{t=1}^\infty q(1-q)^{t-1}(1-(1-q(1-(1-q)^t))^n).$$ We will prove by total induction that ${\hat{J}}(\tau) \leq q(T+1-\tau){\zeta}$, i.e. the expected number of remaining arrivals $q(T+1-\tau)$, times the (unconditional) expected probability of a completed task.

Clearly this is true for $\tau = T+1$. We now assume this is true for $\tau = k+1$ and try to show it for $\tau = k$. We start by bounding $\sum_{t=k}^{T} q(1-q)^{t-k}\left( 1-(1-q(1-(1-q)^{t-k+1}))^n\right)$. To do so, we claim $$\frac{\sum_{t=k}^{T} q(1-q)^{t-k}\left( 1-(1-q(1-(1-q)^{t-k+1}))^n\right)}{\sum_{t=k}^{T} q(1-q)^{t-k}} \leq$$$$\frac{\sum_{t=T+1}^{\infty} q(1-q)^{t-k}\left( 1-(1-q(1-(1-q)^{t-k+1}))^n\right)}{\sum_{t=T+1}^{\infty} q(1-q)^{t-k}}$$ Both sides of the inequality represent the expected value of a random variable, and all possible values of the random variable on the right side of the inequality are larger than every possible value of the random variable on the left side of the inequality because $1-(1-q(1-(1-q)^{t}))^n$ is increasing in $t$. Now we use the algebraic fact that if $\frac{a}{c} \leq \frac{b}{d}$, then $\frac{a}{c} \leq \frac{a+b}{c+d}$ to yield $$\frac{\sum_{t=k}^{T} q(1-q)^{t-k}\left( 1-(1-q(1-(1-q)^{t-k+1}))^n\right)}{\sum_{t=k}^{T} q(1-q)^{t-k}} \leq$$$$\frac{\sum_{t=k}^{\infty} q(1-q)^{t-k}\left( 1-(1-q(1-(1-q)^{t-k+1}))^n\right)}{\sum_{t=k}^{\infty} q(1-q)^{t-k}} = \frac{{\zeta}}{\sum_{t=k}^{\infty} q(1-q)^{t-k}} = {\zeta}$$ This gives us the bound $$\begin{aligned}
    \sum_{t=k}^{T} q(1-q)^{t-k}\left( 1-(1-q(1-(1-q)^{t-k+1}))^n\right) &\leq {\zeta}\sum_{t=k}^{T}q(1-q)^{t-k} \nonumber \\
    &= {\zeta}(1-(1-q)^{T-k+1}) \label{ex5bound1}\end{aligned}$$

We now bound $\sum_{t=k}^{T} q(1-q)^{t-k} {\hat{J}}(t+1)$. Using the inductive hypothesis, we have $$\begin{aligned}
    \sum_{t=k}^{T} q(1-q)^{t-k}{\hat{J}}(t+1) &\leq q\sum_{t=k}^{T} q(1-q)^{t-k}(T-t){\zeta}\nonumber  \\
    &= q\sum_{t'=0}^{T-k} q(1-q)^{t'}(T-k-t'){\zeta}\nonumber  \\
    &= q\left(\sum_{t'=0}^{T-k} q(1-q)^{t'}(T-k){\zeta}-\sum_{t'=0}^{T-k} q(1-q)^{t'}t'{\zeta}\right) \nonumber \\
    &= q(T-k)(1-(1-q)^{T-k+1}){\zeta}\nonumber \\&- (1-q)(1-(1-q)^{T-k}-(T-k)q(1-q)^{T-k}){\zeta}\nonumber  \\
    &=q(T-k+1){\zeta}- (1 - (1-q)^{T-k+1}){\zeta}\label{ex5bound2}\end{aligned}$$

Combining and gives us, as desired, ${\hat{J}}(k) \leq q(T-k+1)Z$, which completes the proof by induction. All that remains is to bound ${\zeta}$, which we do below:

$$\begin{aligned}
    {\zeta}& = \sum_{t=1}^\infty q(1-q)^{t-1}(1-(1-q(1-(1-q)^t))^n) \\ &\leq 1 - \int_{t=1}^\infty q(1-q)^{t-1}(1-q(1-(1-q)^t))^n dt
    \\&= 1 + \frac{q}{\log(1-q)(1-q)} \int_{u=q}^1 (1-qu)^n du \label{ex5int2}
    \\&= 1 + \frac{q}{\log(1-q)(1-q)(1+q)} \left((1-q^2)^{n+1} - (1-q)^{n+1}\right)
    \\&= 1 + \frac{q(1-q)}{\log(1-q)(1+q)} (1-q)^{n-1}\left((1+q)^{n+1} - 1\right)
    \\ &= 1 - \frac{q(1-q)}{\log(\frac{1}{1-q})(1+q)} (1-q)^{n-1}\left((1+q)^{n+1} - 1\right)
    \\&\leq 1 - \frac{q(1-q)}{\log(\frac{1}{1-q})(1+q)}(1-e^{-1}) \label{ex5expbounds}\end{aligned}$$

Line comes from a substitution of $u = 1-(1-q)^t$. Line comes from first recalling that $q = \frac{1}{n}$ by definition, and $(1-\frac{1}{n})^{n-1} \geq \frac{1}{e}$ while $(1+\frac{1}{n})^{n+1} \geq e$ for all $n \geq 1$.

This implies that $J(2) \leq q(T-1)(1 - \frac{q(1-q)}{\log(\frac{1}{1-q})(1+q)}(1-e^{-1}))$. Since $q(T-1) = n$ by definition, and since the total expected number of successful tasks is bounded by $1+J(2)$, we have proven the claim that the value of notifying every active volunteer whenever task $1$ arrives is at most $1 + n\left(1 - \frac{q(1-q)}{\log(\frac{1}{1-q})(1+q)}(1-e^{-1}) \right)$.

Putting all three claims together (e.g. taking the upper bound on the expected number of completed tasks by the best online policy and dividing by a lower bound on $\mathbf{LP}$), we have shown that in ${\mathcal{I}}_2$, no online algorithm can achieve a competitive ratio of more than $1+q - \frac{q(1-q)}{\log(\frac{1}{1-q})(1+q)}(1-e^{-1})$.

Additional Examples
===================

Comparing Ex Ante Candidate Solutions {#ex:xstarcandidates}
-------------------------------------

In the following instance, we present evidence that $f(\mathbf{x^*_{LP}})$ can be significantly less than $f(\mathbf{x^*})$, where $f(\cdot)$ is defined in , $\mathbf{x^*_{LP}}$ is the solution to (LP), and $\mathbf{x^*}$ is defined in .

[**Instance ${\mathcal{I}}_3$:**]{} Suppose $V = 2$, ${S}= 2$, $T=2$, and $g(1) = q$, where $q \in [0,1]$. The arrival probabilities are given by $\lambda_{1, 1} = 1$ and $\lambda_{2, 2} = 1$. The volunteer match probabilities are given by $p_{1, 1} = p_{2,1} = 0.5$, $p_{1,2} = 0$, and $p_{2,2} = 0.5-\epsilon$, where $\epsilon << 1$. The left panel of Figure \[fig:exappendix\] visualizes Instance ${\mathcal{I}}_3$.

The solution to (LP) for instance ${\mathcal{I}}_3$ is $x_{1,1,1} = x_{2,1,1} = 1$ and $x_{2, 2, 2} = q$. Thus, $f(\mathbf{x}^*_{LP}) = 0.75 + 0.5q - \epsilon q$.

Alternatively, $\mathbf{x^*_{AA}}$, which is result of the Frank-Wolfe variant described in Section \[subsec:offline\], has a solution which depends on the step size. As one example, with a step size of $0.5$, the solution is $x_{1,1,1} = 0.5$, $x_{2,1,1} = 1$, and $x_{2, 2, 2} = 0.5(1+q)$ if $q < 0.5$, which achieves a value of $f(\mathbf{x^*_{AA}}) = 0.875 + 0.25q - \epsilon(0.5)(1+q)$. If $q \geq 0.5$, $\mathbf{x^*_{AA}} = \mathbf{x^*_{LP}}$.

The solution to $(SQ$-$1)$ is $x_{1,1,1} = 1$. If $q < 0.5$, the solution to $(SQ$-$2)$ is $x_{2,1,1} = 0$ and $x_{2,2,2}=1$ and $f(\mathbf{x^*_{SQ}}) = 1 - \epsilon$. Otherwise, the solution to $(SQ$-$2)$ is $x_{2,1,1} = 1$ and $x_{2,2,2} = q$ and $\mathbf{x^*_{SQ}} = \mathbf{x^*_{LP}}$.

If $1 >> q >> \epsilon$, $f(\mathbf{x^*}) \approx 1$, which represents a 33% improvement over $f(\mathbf{x^*_{LP}}) \approx 0.75$.

![*Left:* Visualization of instance ${\mathcal{I}}_3$. *Right:* Visualization of instance ${\mathcal{I}}_4$.[]{data-label="fig:exappendix"}](instances_34.pdf){width=".95\textwidth"}

Directly Following Ex Ante Solution {#ex:followingxstar}
-----------------------------------

In the following instance, we present evidence that following an unadjusted ex ante solution can result in poor performance.

[**Instance ${\mathcal{I}}_4$:**]{} Suppose $V = 1$, ${S}= 2$, $T=2$, and $g(1) = q$, where $q \in [0,1]$. The arrival probabilities are given by $\lambda_{1, 1} = 1$ and $\lambda_{2, 2} = q$. The volunteer match probabilities are given by $p_{1, 1} = \epsilon$ and $p_{1,2} = 1$, where $\epsilon << 1$. The right panel of Figure \[fig:exappendix\] visualizes Instance ${\mathcal{I}}_4$.

The ex ante solution to instance ${\mathcal{I}}_4$ is $x^*_{1,1,1} = 1$ and $x^*_{1, 2, 2} = 1$, since this solution is feasible in (LP) and achieves the highest possible value of any feasible solution as a consequence of monotonicity. Therefore, $\mathbf{LP}_{{\mathcal{I}}_4} = \epsilon + q$.

However, an online policy of following $\mathbf{x^*}$, e.g. always notifying volunteer $1$ when there is an arrival, achieves a payoff of $\epsilon + q^2$. For $q>>\epsilon$, this policy achieves a competitive ratio of $q$.

Gap in Numerical Performance Between Policies {#ex:SNvsSDN}
---------------------------------------------

In instance ${\mathcal{I}}_4$ from Appendix \[ex:followingxstar\] (which is visualized in the right panel of Figure \[fig:exappendix\]), the SDN policy will notify volunteer $1$ at time $1$ with probability $\frac{1}{2-q}$. When donor $2$ arrives at time $2$, the SDN policy will notify volunteer $1$ with probability $\frac{1}{(2-q)\beta_{1,2}}$. Thus, the SDN policy achieves a value of $\frac{\epsilon}{2-q} + q\beta_{1,2}\frac{1}{(2-q)\beta_{1,2}} = \frac{\epsilon+q}{2-q}$. We remark that this is exactly equal to $\frac{1}{2-q}f(\mathbf{x^*})$, which is exactly the guarantee of the SDN policy.

Meanwhile, the SN policy solves a DP starting from $J_{1,3} = 0$. Working backwards, the DP solution for period $2$ is ${\tilde{x}}_{1,2,2} = 1$ and $J_{1,2} = q$. To evaluate the DP solution for period 1, we note that $r_{1,1,1} + q^2 = \epsilon + q^2 \leq {J}_{1,2}$, assuming $q<1$ and $\epsilon$ is chosen to be sufficiently small. Thus, ${\tilde{x}}_{1,1,1} = 0$, so the SN policy achieves a value of $q$. For $1 >> q >> \epsilon$, the SN policy performs roughly twice as well as the SDN policy.

[^1]: Here, by organic, we mean volunteers sign up for those rescues without the platform’s involvement.

[^2]: According to our analysis of FRUS data, a missed rescue increases the probability of donor dropout by a factor of approximately 2.5.

[^3]: We remark that FRUS’s current practice in [many]{} locations is to notify a volunteer at most once a week. Further, we note that FRUS is hesitant to demand prompt responses from volunteers, which renders the option of sequentially notifying volunteers impractical.

[^4]: Characteristics or features of a rescue includes its origin-destination location, day, time, etc.

[^5]: For FRUS, a task represents a scheduled rescue (food donation) which has not been claimed in advance.

[^6]: By convention, if the fraction is $\frac{0}{0}$, we define it to be equal to 1.

[^7]: As explained in the introduction, the platform cannot expect a prompt response from volunteers and therefore sequential notification is impractical.

[^8]: For ease of notation, for any $a \in \mathbb{N}$, we use $[a]$ to refer to the set $\{1, 2, \dots, a\}$.

[^9]: Since a task can only be completed if one arrives, we limit all sums to task types indexed from $1$ to ${S}$.

[^10]: We remark that we design our online policies such that they achieve a constant factor of $f(x)$ [as defined in .]{}

[^11]: We remind that $f(\cdot)$ is the objective in the hypothetical case where all volunteers are always active.

[^12]: Note that this priority scheme is without loss of generality, since in the online volunteer notification problem, *all* volunteers who respond to a notification become inactive for a duration drawn from an identical distribution.

[^13]: Some of the ideas used in our SDN policy are similar to the adaptive algorithm of [@dickerson2018allocation].

[^14]: We also highlight that computing $\beta_{v,t}$ for all $v$ and $t$ can be done in polynomial time.

[^15]: We remark that the condition imposed on $q$ when $0 < q < 1/16$ is added for ease of presentation of the theorem statement as well as its proof. Relaxing the aforementioned condition amounts to modifying the second term in $\kappa$ by rounding any $q$ up to the closest $\hat{q} \in \{1/n,  n \in \mathbb{N} \}$ and slightly modifying the instance in the proof. We omit these details for the sake of brevity.

[^16]: [Part of why our policies outperform their competitive ratio is that in the FRUS locations studied, using $\mathbf{x^*}$ as an ex ante solution improves on using $\mathbf{x^*_{LP}}$ by an average of $5\%$, up to a maximum of $23\%$.]{}
