Online Matching with Controllable Rewards and Arrival Probabilities

1 Introduction

Online bipartite matching [Mehta, 2012; Feldman et al., 2009] has attracted much attention because of its many applications, such as advertising [Mehta, 2012], ride-sharing [Dickerson et al., 2018], and crowdsourcing [Ho and Vaughan, 2012]. These applications require platformers to find efficient online ways of allocating their limited resources among customers or participants, which significantly impacts their business profits. Formally, the problem of allocation is defined on a bipartite graph G = (U, V ;E): U is the fixed node set known in advance, and nodes in V arrive at each time in a probabilistic manner; a reward is obtained when an arrival node in V is matched with a node in U; the goal is to find a matching strategy that maximizes the total rewards. 1

1 Codes/details of our experiments and the proof of Lemma 2 can be found in https://github.com/Yuya-Hikima/IJCAI2022-Online-

Existing studies assume that rewards and arrival probabilities are given a priori as fixed constants [Mehta, 2012; Dickerson et al., 2018], in which case only the matching strategy needs to be optimized. However, platformers can usually control rewards, which affect arrival probabilities. This triggers the non-trivial problem of optimizing the rewards as well as the matching strategy for greater profits, due to the trade-off between rewards and arrival probabilities. For example, in a ride-sharing platform, higher fares (rewards) increase the profit obtained with each match, but cause lower participation (arrival) probabilities of requesters for taxis assignment, which might degrade the total profits obtained even if the matching strategy is optimal. Although important and appearing in many applications (described in Section 3.2), the problem has not, to the best of our knowledge, been tackled directly in online matching studies.

In this study, we propose the novel problem of simultaneously optimizing the matching strategy and the trade-off between rewards and arrival probabilities to maximize business profits. We call the problem Online Matching with Controllable Rewards and Arrival probabilities (OM-CRA). OMCRA solutions realize profitable online matching under an appropriate balance of rewards and arrival probabilities. In the case of a ride-sharing platform, business profits are expected to increase in the following scenario: for areas with few taxis, a fare (reward) per one match is prioritized over the arrival probabilities of requesters; for areas with many taxis, the arrival probabilities are increased with lower fares to stimulate many matches.

Although OM-CRA is an important problem for applications, OM-CRA has two difficulties to solve: (i) we need to simultaneously optimize the matching strategy and the tradeoff between the rewards and the arrival probabilities (finding just the optimal matching strategy is hard [Manshadi et al., 2012]); (ii) it takes a lot of time to compute the objective value because it is the expected total rewards for the random order of participants with exponential realizations.

In this paper, we develop a fast 1/2-approximation algorithm for OM-CRA. First, based on recent studies on online matching [Dickerson et al., 2018; Alaei et al., 2012], we approximate the objective value by the optimal value of a linear optimization problem. Using this approximation reduces

Matching-with-Controllable-Rewards-and-Arrival-Probabilities.

OM-CRA to a non-convex continuous optimization problem whose objective value can be evaluated easily. Then, we reduce the problem to a convex-concave saddle-point problem [Benzi et al., 2005] under mild assumptions. Many important functions typically used in the applications satisfy these assumptions. We then solve the convex-concave saddlepoint problem by the Primal-Dual Hybrid Gradient (PDHG) method [Chambolle and Pock, 2011; Goldstein et al., 2015]. It is a powerful optimization method for saddle-point problems; an optimal solution is attained by alternately updating the primal and the dual variables. By utilizing the problem structure, we can accelerate the update of the primal variables in PDHG, which allows us to find a solution quickly even for large-scale problems.

We conducted simulation experiments on real data from a crowdsourcing platform and a ride-sharing platform. The results show that the proposed algorithm outputs solutions with higher total rewards than baselines in practical time.

Notation. Bold lowercase symbols (e.g., x, y) denote vectors, and ‖x‖ denotes the Euclidean norm of vector x. Capitalized writing forms (e.g., A) represent linear maps, while A⊤ denotes the transpose map for the linear map A. The inner product of the vectors x, y is denoted by x⊤y. For x ∈ Rn , we denote (x)+ := (max{0, xi})i=1,...,n.

2 RelatedWorks

2.1 Online Bipartite Matching

In the research field of online matching, the following four problem settings have been the focus of most studies (overviewed by [Mehta, 2012]): (a) Known Identical Independent Distributions (KIID), where each node v has the same arrival probability throughout the entire period [Feldman et al., 2009; Haeupler et al., 2011]; (b) Unknown Identical Independent Distributions (Unknown IID), where each node v has a fixed but unknown arrival probability [Devanur et al., 2011]; (c) Adversarial order, where an adversary can determine the arrival order of all nodes v [Karp et al., 1990; Sun et al., 2017]; (d) Random order, where all v arrive in a random permutation order [Mahdian and Yan, 2011]. In addition, recently, generalizations of KIID have been reported; Known Adversarial Distribution (KAD) assumes that each arrival node v has a different arrival probability at each time [Alaei et al., 2012]. Online Matching with Reusable Resources under Known Adversarial Distributions (OM-RRKAD) is a generalization of KAD, where fixed node u rejoins the system after a certain period after the previous assignment [Dickerson et al., 2018].

In this paper, we further extend OM-RR-KAD and propose a new problem called Online Matching with Controllable Rewards and Arrival probabilities (OM-CRA), which optimizes not only the matching strategy but also the tradeoff between the rewards and the arrival probabilities under the same setting as OM-RR-KAD. The reason for focusing on the OM-RR-KAD setting is that it is suitable for various applications. For example, in a ride-sharing platform, taxis (resources) can be reused after a certain period of being allocated to requesters. In addition, the arrival probability of requester v, defined by origin/destination areas, varies with time of day. Our problem can deal with these applications since it is an expansion of OM-RR-KAD.

2.2 Optimization problems with Decision-Dependent Noise

Since the uncertainty (i.e., arrival probabilities of nodes) in our problem depends on the decision variables, our optimization problem is classified as a optimization problem with decision-dependent noise [Hellemo et al., 2018]. This category of problems has been addressed for several application areas, such as matching platforms [Hikima et al., 2021; Tong et al., 2018], crowdsourcing systems [Wang et al., 2018], single itemmarkets [Babaioff et al., 2015], and transportation investment [Peeta et al., 2010].

Among these studies, [Hikima et al., 2021; Tong et al., 2018] have tackled matching problems with decisiondependent noise, similar to ours. [Hikima et al., 2021] optimizes some variables, which affect rewards and node existence probabilities, to maximize the expected profit from batch-type matching. In the context of the ride-sharing platform, [Tong et al., 2018] determines the fare for passengers in each area to control passenger participation rates and maximize the expected profits from taxi-requester matching. The difference between these existing studies and ours is whether or not the timeline factor is considered. Existing studies consider only one-time (batch) matching and seek a myopic solution at a certain point in the time horizon. In contrast, our study considers online matching situations and seeks an optimal solution from a long-term perspective.

A problem setting similar to ours is found in [Babaioff et al., 2015]. That work performs price optimization for single item markets. Here, the reward for selling a product and the participant's purchase probability can be controlled by the price. It is similar to our study because we control rewards and arrival probabilities in online matching situations. However, that study did not consider the compatibility of resources and participants, while our study considers it. This allows us to deal with crowdsourcing platforms with skill compatibility between tasks and workers, and ride-sharing platforms with distance compatibility between taxis and requesters.

OptimizationMethods. For the optimization problemwith decision-dependent noise, search methods such as Bayesian optimization [Brochu et al., 2010] and random search [Bergstra and Bengio, 2012] can be applied. However, for our problem, they do not provide good solutions in practical time for the following reasons: (i) the feasible region of the optimization problem is too large to be adequately explored; (ii) it takes a lot of time to compute the exact objective value or its approximation with high accuracy. In contrast, our method can output a 1/2-approximation solution in practical time.

3 ProblemFormulation

3.1 Matching Procedure

Notation. In this paper, we consider allocating resources to participants who arrive one by one at each time t ∈ T :=

{1, 2, . . . , tmax}. 2 The set of resources U := {u1, . . . , um}, the set of participants V := {v1, . . . , vn}, and bipartite graph G = (U, V ; E) are given. Each edge (u, v) ∈ E represents that resource u can be matched to participant v. All u ∈ U and v ∈ V are incident to at least one e ∈ E. For e = (u, v) ∈ E and t ∈ T , if resource u is matched to participant v at time t, the platformer receives reward wet ∈ R and the participant v pays the platformer reward xvt ∈ R. Thus, the platformer receives a total of wet + xvt rewards. For e = (u, v) ∈ E and t ∈ T, the constant cet ∈ {1, 2, . . . , tmax} denotes the time duration that must pass for resource u to become available again when u is matched to v at time t, i.e., u will be available at time t+cet if e = (u, v) is taken at time t. The case cet = |T | for all t ∈ T and e ∈ E corresponds to the problem where the resources are non-reusable. Here, wet and cet are given constants while xvt is a variable controlled by the platformer. We also emphasize that wet and xvt can take a negative value.

System Procedure. In the above setting, we consider the following system procedure: (I) The platformer determines the value of xvt for each v ∈ V and t ∈ T. Then, repeat the following (II) and (III) for each t ∈ T. (II) Participant v appears and accepts the reword/cost with probability pvt(xvt) or any of the participant v ∈ V appears but rejects the reword/cost with probability 1 - ∑v∈V pvt(xvt). Here, pvt : R → (0, rvt) is a given monotonically decreasing function and rvt ∈ R>0 is a given constant such that ∑v∈V rvt = 1. (III) If participant v ∈ V arrives, the platformer chooses either (a) to assign one resource u from U to the participant and get the reward of wet + xvt, where e = (u, v), or (b) not to assign any resource. If the platformer chooses (a), allocated resource u is removed from graph G for cet periods.

Platformer's Goal. The goal of the platformer is to maximize the total rewards by deciding xvt and matching strategy appropriately. Here, too large xvt leads to a decrease in the total reward due to a decrease in the arrival probabilities of participants, while too small xvt also leads to a decrease in the total reward due to a decrease in the reward for each match. The platformer needs to make decisions while considering such trade-offs.

3.2 Applications

Crowdsourcing Platform. In the crowdsourcing platform, the platformer needs to assign their tasks to arriving workers in real-time [Ho and Vaughan, 2012]. We start with the set of tasks U and the set of worker groups V , where worker groups are differentiated by skills and attributes. The platformer can determine wage xvt(≤ 0) for each worker group v ∈ V and each time t ∈ T. Here, xvt is negative because it is the price the platformer pays for workers. Then, at each time t ∈ T , a worker in group v ∈ V arrives with probability pvt(xvt) = rvtsvt(xvt); worker v appears with probability rvt and accepts the wage xvt with probability svt(xvt). The crowdsourcing platformer assigns task u ∈ U to the accepting worker v and takes the rewards wet + xvt, where e = (u, v). Here, wet(≥ 0) is the reward paid by the task-holder to the platformer when task u is solved by worker v. Reward wet is set based on the skills and performance of each worker group. Usually, we1 = we2 = · · · = we|T|. Once the task u is solved, there is no need to solve it again, so node u is permanently removed after it is assigned. Therefore, cet = |T| for all e ∈ E and t ∈ T .

2 The variable t does not represent an absolute time, but is used to indicate the relative order of appearance of participants.

Ride-sharing Platform. In the ride-sharing platform, the platformer needs to assign taxis to arriving requesters in realtime [Dickerson et al., 2018]. There are multiple taxis, U, and multiple requester groups, V , where each group v ∈ V is defined by the origin/destination areas of the request. We consider every taxi u ∈ U starts and ends at the same location (docking position) for all trips. On receiving a request, the taxi leaves from its docking position to the pick-up point, executes the trip, and returns to its docking position. The platformer can determine fare xvt(≥ 0) for each group v ∈ V and each time t ∈ T . Then, at each time t ∈ T , a requester in group v ∈ V arrives with probability pvt(xvt) = rvtsvt(xvt); requester v appears with probability rvt and accepts the fare xvt with probability svt(xvt). The platformer assigns taxi u ∈ U to the accepting requester v and takes the reward wet + xvt, where e = (u, v) and wet(≤ 0) is the total cost (e.g., gasoline cost) of allocating taxi u to the requester v at time t. If taxi u is assigned to some v at time t, it becomes unavailable for cet rounds.

Other Applications. Our matching procedure is applicable to the following applications in some situations: Optimization of worker wages and task allocation in crowd-sensing [Pu et al., 2017]; Optimization of parking fees and parking lot allocation in city parking [Meir et al., 2013]; Optimization of usage fees and allocation of virtual machines in cloud computing [Du et al., 2019].

3.3 Optimization Problem

We consider an optimization problem to maximize the total rewards of the platformer in the matching procedure in Section 3.1. We propose Online Matching with Controllable Rewards and Arrival probabilities (OM-CRA):

Here, ξ ∈ {V ∪ {⊥}}T is a random variable, where ξt = v means that participant v arrives at time t, and ξt = ⊥ means no participants arrive at time t. D(x) is a probability distribution for ξ ∈ {V ∪ {⊥}}T ; The probability mass function is Pr(ξ | x) = ∏t∈T Pr(ξt | x), where Pr(ξt = v | x) = pvt(xvt) and Pr(ξt = ⊥ | x) = 1-∑v∈V pvt(xvt). Variable π represents a matching strategy in (II) and (III) of the matching procedure in Section 3.1 and Π is the set of all strategies. A matching strategy specifies, upon arrival of vertex v ∈ V , whether to match it, and if so, which u ∈ U to match it to. Function f(π, x, ξ) is the expected total reward obtained from performing the matching procedure given (π, x, ξ).

3.4 Assumption on pvt

We assume the following throughout this paper.

Assumption 1. The function pvt : R → (0, rvt) is monotonically decreasing, differentiable, and bijective. Moreover, -p′vt (x)/pvt(x) is monotonically non-decreasing with respect to x.

Assumption 1 is not so restrictive; many functions used in real applications satisfy Assumption 1. For example, pvt(x) = rvt(1 - F(x)) satisfies Assumption 1 when F(x) is a Gauss error function or a logistic function. 3

4 ProposedMethod

Finding the optimal solution for OM-CRA is difficult for two main reasons: (i) We need to simultaneously optimize the matching strategy π and variable x (even finding just the optimal matching strategy is hard [Manshadi et al., 2012]). (ii) It takes a large amount of time to compute the exact objective value or its approximation with high accuracy. This is because the objective value is the expected total rewards for the random variable ξ with |V + 1||T| realizations. Our solution is to propose a 1/2-approximation algorithm for OM-CRA.

4.1 Approximation of Objective Function

We consider the approximation of the objective function of OM-CRA. First, we introduce the following problem for a given x, and denote the optimal value by ˆ f (x):

where δ(v) denotes the set of edges incident to node v.

Here, for given x, we consider the following matching strategy πADAP(1/2) (x) [Dickerson et al., 2018]:

1. Let z∗ (x) be the optimal solution of the problem (1).
2. When vertex v arrives at time t, choose an edge, e = (u, v) ∈ Evt, with probability z∗ et (x) pvt(xvt) 1 2βet or reject v with probability 1 - ∑e∈Evt z∗ et (x) pvt(xvt) 1 2βet ,

whereEvt := {(u, v) ∈ E | resource u is available at time t}; βet is the probability that edge e is available at time t. We can estimate βet for each e ∈ E and t ∈ T with arbitrarily small error by simulating the matching strategy up to t - 1 [Dickerson et al., 2018].

Then, the following theorem holds by the results of [Dickerson et al., 2018; Alaei et al., 2012].

3 When F(x) is a twice-differentiable distribution function and -G′ (x)/G(x) is monotonically non-decreasing for G(x) := 1 - F(x), F is called a Monotone Hazard Rate function [Barlow et al., 1963]. This type of function is frequently used to model the relationship between the offered prices and the acceptance probabilities in the dynamic pricing literature [Babaioff et al., 2015; Tong et al., 2018].

Theorem 1. For any x, the following holds:

We obtain the following problem by replacing maxπ∈Π Eξ∼D(x)[f(π, x, ξ)] with ˆ f(x) for OM-CRA:

Here, the following lemma and theorem hold:

Lemma 2. (PA) has an optimal solution under Assumption 1.

Theorem 3. Suppose that Assumption 1 holds. Let ˆx be an optimal solution for (PA). Then, (ˆx, πADAP(1/2) (ˆx)) is a 1/2approximation solution for OM-CRA.

From Theorem 3, solving (PA) yields a 1/2-approximation solution to OM-CRA.

4.2 Reduce (PA) to Convex Optimization Problem

Although (PA) is a non-convex optimization problem with non-convex functions pvt(xvt), we can reduce (PA) to a convex optimization problem under Assumption 1. First, we consider the following problem, which is obtained by eliminating x from (PA) by using xvt := p-1 vt (∑e∈δ(v) zet):

Here, Svt is the range of function pvt. Then, we show the following proposition.

Proposition 4. Let Assumption 1 hold. Let the optimal solution of (CP) be z∗ and x∗vt := p-1 vt (∑e∈δ(v) z∗ et ) for all v ∈ V and t ∈ T . Then, (x∗ , z∗ ) is an optimal solution for (PA).

From Proposition 4, we can obtain an optimal solution for (PA) by solving (CP). Moreover, the following lemma holds by the results of [Hikima et al., 2021].

Lemma 5. Let Assumption 1 hold. Then, -p-1 vt (z)z is convex with respect to z for all v ∈ V and t ∈ T. Moreover, the objective function of (CP) is convex.

From Lemma 5, (CP) is a convex optimization problem.

4.3 PDHGMethod for (CP)

We can solve problem (CP) efficiently by applying the Primal-Dual Hybrid Gradient (PDHG) method [Chambolle and Pock, 2011; Goldstein et al., 2015]. The PDHG method was developed for convex-concave saddle-point problems and approaches the optimal solution by alternately updating primal and dual variables. In this section, we reduce (CP) to a convex-concave saddle-point problem and solve the problem by the PDHG method.

Here, (CP) can be rewritten as the following problem:

Symbol 1 denotes the all-one vector. Variable zvt denotes zvt := (zet)e∈δ(v) ∈ Rδ(v) . Vector w denotes w := (wet)(e,t)∈E×T ∈ RE×T . A ∈ RE×T → RU×T is a linear map according to the second constraint of problem (CP), that is, A(z) = (∑e∈δ(u) ∑t′ : 0≤t-t′≤cet′ zet′ )(u,t)∈U×T .

The problem (CP′ ) is equivalent to the following saddlepoint problem:

The function L is called the Lagrange function. Since this problem is convex-concave from Lemma 5 and the definition of fvt, we can solve it by the PDHG method.

In each iteration k of PDHG, the following updates are performed:

Here, τk, σk > 0 are step-size parameters. Eq. (5) can be solved explicitly as λk+1 = (λk + σk(A(zk+1 ) - 1))+. Although (4) requires solving a (|E||T |)-dimensional optimization problem, we can solve it quickly by utilizing the problem structure.

The optimization problem in (4) can be decomposed into the following |δ(v)|-dimensional optimization problems for v ∈ V and t ∈ T:

where Avt : Rδ(v) →RU×T is the linear map such that

The vector wvt denotes wvt := (wet)e∈δ(v) ∈ Rδ(v) . Moreover, the following proposition holds for problem (6). Proposition 6. Let a := zk vt + τk(wvt -A⊤vt (λk )). We consider the following equation with respect to s:

Then, the left-hand side of Eq. (7) is monotonically decreasing, and (7) has a unique solution, s∗ . In addition, zvt = (a- τkf ′vt (s∗ )1) is the optimal solution for the problem (6).

Algorithm 1 Adaptive PDHG for (CP′ )

Because the left-hand side of (7) is monotonically decreasing and the right-hand side is monotonically increasing, the bisection method can quickly find s∗ . By Proposition 6, the solution for the problem (6) can be easily calculated from s∗ .

We now propose Algorithm 1. Algorithm 1 incorporates the decomposition of the problem (6) and the results of Proposition 6 into the method of [Goldstein et al., 2015]. In this algorithm, lines 3-6 update the primal and dual variables by (4) and (5), and lines 7-14 adjusts the step-size, τ and σ.

This algorithm is a specialized version of the method of [Goldstein et al., 2015]; the updates of the primal variables are accelerated by using problem decomposition (6) and Proposition 6.

5 Experiments

We conduct experiments to show that the following hold: (i) our algorithm outputs solutions with higher total rewards than the baselines in each application; (ii) our algorithm outputs the solution in practical time. We performed simulation experiments using real data from crowdsourcing and ridesharing platforms. Experiments were run on a computer with Xeon Platinum 8168 (4 x 2.7GHz), 1TB of memory, CentOS 7.6. The program codes were implemented in Python 3.6.3. Codes and more details of our experiments can be found in our repository provided in the footnote on the first page.

5.1 Baselines

We compared our method to the following six baselines.

CU-A. We set x by Capped-UCB [Babaioff et al., 2015], which is the pricing strategy for limited supply in a single item market. This method determines the price while estimating the average participation probability for all demanders; here we take it to be a given function. Specifically, for all v and t, let xvt := argmaxx{(x + ˆw)min(|U||T|/ˆ c, ˆ p(x))}, where ˆw and ˆ c are the averages of wet and cet for all e and t, respectively, and ˆ p(x) = ∑t∈T ∑v∈V pvt(x). Here,

|U ||T |/ˆ c approximates the number of times the resources can be used over the entire period, based on the average length of periods that resources are unavailable. If cet = |T| for all (e, t) ∈ E × T, i.e., the resource is not reusable, then |U ||T |/ˆ c = |U|. Function ˆ p(x) represents the average total number of arriving requesters for x. Then, we adopt the 1 2 -approximation strategy [Dickerson et al., 2018].

CU-G. CU-G adopts a greedy strategy instead of the 12 - approximation strategy for CU-A. The greedy strategy takes the edge ˆ e(v, t) = argmaxe{wet + xvt | e = (u, v) ∈ E, u is available} when the node v arrives at time t.

BO-A. We apply Bayesian optimization [Brochu et al., 2010] to search x while adopting the 12 -approximation strategy [Dickerson et al., 2018] as the matching strategy. BO-A first evaluates five random points of x. Then, after running the Bayesian optimization for 1000 seconds, it outputs the solution with the highest objective value among the evaluated points. The set to search for x is [0, 1]V ×T in crowd-sourcing platform experiments and [0, 50]V ×T in ride-sharing platform experiments.

• BO-G. BO-G adopts a greedy strategy instead of the 12 - approximation strategy of BO-A.

RS-A. We apply the random search to variable x while adopting the 12 -approximation strategy [Dickerson et al., 2018] as the matching strategy. In each iteration, search points are generated from the set [0, 1]V ×T in crowd-sourcing platform experiments and [0, 50]V ×T in ride-sharing platform experiments. RS-A outputs the solution with the highest objective value among the points evaluated in 1000 seconds.

RS-G. RS-G adopts the greedy strategy instead of the 12 - approximation strategy of RS-A.

5.2 Metric

We use Expected Total Rewards (ETR), which is the average of obtained total rewards in 103 simulations, as the metric.

5.3 Experiments of Crowd Sourcing Platform

We conduct experiments for a crowdsourcing platform whose problem setting is described in Section 3.2.

Data Set and Parameter Setup. We used an open crowdsourcing dataset [Buckley et al., 2010]. The dataset contains records of workers' judgments on the task of checking the relevance of a given topic and a web page. We set the inputs U, V , E, wet, and pvt from the data for each experiment, based on [Hikima et al., 2021; Ho and Vaughan, 2012].

Experimental Results. Table 1 shows the results of the simulation experiments with different parameter values. The proposed method outperforms all baselines in terms of ETR. This is because the baselines are not able to find proper x; (i) CU-A and CU-G propose an average price for all v ∈ V , which is inappropriate for many v ∈ V ; they offer the same price to workers with different skill levels. (ii) BO-A, BO-G, RS-A, and RS-G cannot fully explore x since (a) it takes a large amount of time to evaluate the objective value and (b) the dimension of x is large. Moreover, the computation time of the proposed method is short enough for practical use.

5.4 Experiments of Ride-sharing Platform

We conduct experiments on a ride-sharing platform whose setting is described in Section 3.2.

Data Set and Parameter Setup. We used ride data of yellow taxis in Manhattan in New York 4 . We perform simulations using data from 10:00 to 20:00 on weekends and weekdays for randomly chosen weeks from January to March 2019. We set the inputs U, V , E, wet, and pvt from the data for each experiment, based on [Dickerson et al., 2018; Hikima et al., 2021].

4 https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page

Experimental Results. Table 2 shows the results of the simulation experiments with different dates. Regardless of the date, the proposed method outperforms all baselines in terms of ETR. Moreover, compared to the results of crowdsourcing experiments, the differences between the proposed method and the baselines are larger. This occurs for the following reasons; (i) CU-A and CU-G output further inappropriate x when the resource is reusable. Capped-UCB, which is used in CU-G and CU-A, is a method to determine x based on the number of times the resources can be used, NR. When the resources are not reusable, NR is equal to the total number of resources. However, when the resources are reusable, NR depends on the input and the matching strategy, so we cannot calculate NR exactly and must approximate it. The inaccuracy of the approximation deteriorates the quality of the output of Capped-UCB. (ii) BO-A, BO-G, RS-A, and RS-G become more inefficient because |V | is larger than that of crowdsourcing, and then the dimension of x becomes relatively large. In contrast, the proposed method can stably determine appropriate prices even in the large-scale problem with reusable resources. In addition, the proposed method outputs solutions in practical time.

6 Conclusion

We formulated a novel optimization problem, OM-CRA, to simultaneously determine the matching strategy and the trade-off between rewards and arrival probabilities. It is useful in obtaining high profits in various applications. We proposed a fast 1/2-approximation algorithm for OM-CRA. Simulation experiments on real data from two applications, crowdsourcing and ride-sharing platforms, confirmed the effectiveness of the proposed algorithm.

7 Proof

7.1 Proof of Theorem 1

First, based on [Alaei et al., 2012, Lemma 3.1], we show that maxπ∈ΠEξ∼D(x)[f(π, x, ξ)] ≤ ˆ f(x). For each ξ, we consider the following problem:

where ξvt is a constant that is 1 if ξt = v and 0 otherwise. In other words, ξvt = 1 if v appears at time t and 0 otherwise. Here, let z∗ (ξ) be the optimal solution for (P(ξ)). Since the optimal value of P(ξ) is the maximum profit from performing the matching procedure for ξ,

Therefore, the following holds:

From the first constraints of (P(ξ)), ∑e∈δ(v) z∗ et (ξ) ≤ ξvt for all v ∈ V , t ∈ T. Since it holds for all ξ, the following holds for all v ∈ V and t ∈ T :

From the second constraints of (P(ξ)), we have ∑e∈δ(u) ∑t′ : 0≤t-t′<cet′ z∗ et′(ξ) ≤ 1 for all u ∈ U, t ∈ T. Since it holds for all ξ, the following holds for all u ∈ U and t ∈ T:

Since z∗ et (ξ) ∈ {0, 1} for all e ∈ E, t ∈ T, and ξ, the following holds for all e ∈ E, t ∈ T , and ξ:

Then, from (9), (10) and (11), Eξ∼D(x)[z∗ (ξ)] is a feasible solution for problem (1). Therefore, ∑t∈T ∑e=(u,v)∈E (xvt + wet)Eξ∼D(x)[z∗ et (ξ)] ≤ ˆ f (x). Then, from (8), maxπ∈Π Eξ∼D(x)[f(π, x, ξ)] ≤ ˆ f (x).

We show 1 2 ˆ f(x) ≤ Eξ∼D(x)[f(πADAP(1/2) (x), x, ξ)], based on [Dickerson et al., 2018, Section 3]. About LP(1) of [Dickerson et al., 2018], let pvt := pvt(xvt), we := xvt + wet, and let Pr[Ce > t - t′ ] be 1 if cet′ > t - t′ and 0 otherwise. Then, LP(1) of [Dickerson et al., 2018] corresponds to problem (1) in our paper. Therefore, from [Dickerson et al., 2018, Lemma 2, Section 3], 1 2 ˆ f(x) ≤ Eξ∼D(x)[f(πADAP(1/2) (x), x, ξ)]. Here, although we does not have t subscript in LP(1) of [Dickerson et al., 2018], Lemma 2 of [Dickerson et al., 2018] holds.

7.2 Proof of Lemma 2

The proof can be found in the supplementary material in our repository provided in the footnote on the first page.

7.3 Proof of Theorem 3

From Theorem 1, Eξ∼D(ˆx)[f(πADAP(ˆx)), ˆx, ξ)] ≥ 12 ˆ f ( ˆx). Since problem (PA) is equivalent to maxx∈RV×T ˆ f(x), for any x ∈ RV×T , 1 2 ˆ f(ˆx) ≥ 12 ˆ f(x). Here, for any (x, π) ∈ RV×T × Π, Theorem 1 shows 12 ˆ f(x) ≥ 1 2 maxπ′∈ΠEξ∼D(x)[f(π′ , x, ξ)] ≥ 12 Eξ∼D(x)[f(π, x, ξ)]. Then, we have Eξ∼D(ˆx)[f(πADAP(1/2) (ˆx)), ˆx, ξ)] ≥ 12 Eξ∼D(x)[f(π, x, ξ)] for (x, π) ∈ RV×T ×Π. This means (ˆx, πADAP(1/2) (ˆx)) is 12 -approximation solution for OMCRA.

7.4 Proof of Proposition 4

Let (ˆx, ˆ z) be an optimal solution for (PA). First, we show ∑e∈δ(v) ˆ zet ̸= 0 for all v ∈ V and t ∈ T. We assume there are ` v ∈ V and ` t ∈ T satisfying ∑e∈δ(` v) ˆ ze` t = 0 to obtain a contradiction. We pick an arbitrary vertex ` e ∈ δ(` v). Then, there exists xM satisfying xM + w` e` t > ∑(e=(u,v),t)∈E×T\(` e,` t) {ˆxvt + wet}. Here, we let ϵ := p` v` t (xM) and show that replacing ˆx` v` t with xM, ˆ z` e` t (= 0) with ϵ, and ˆ zet with max{0, ˆ zet - ϵ} for all (e, t) ∈ E × T \ (` e, ` t) increases the objective value of (PA) from (ˆx, ˆ z) without impairing feasibility. The objective value of (PA) increases because (xM + w` e` t )ϵ - ∑(e=(u,v),t)∈E×T \(` e,` t):ˆxvt+wet≥0 (ˆxvt + wet) min{ˆ zet, ϵ} ≥ (xM + w` e` t - ∑(e=(u,v),t)∈E×T\(` e,` t):ˆxvt+wet≥0 (ˆxvt + wet))ϵ > 0. Here, for all e = (u, v) ∈ E and t ∈ T, if ˆxvt +wet < 0, then ˆ zet = 0; if ˆ zet > 0 and (ˆxvt +wet) < 0, we can increase the objective value of (PA) without impairing feasibility by setting ˆ zet := 0 and this contradicts the assumption that (ˆx, ˆ z) is the optimal solution of (PA). The first constraint of (PA) is satisfied because ϵ ≤ p` v` t (xM) and ∑e∈δ(v) max{0, ˆ zet - ϵ} ≤ ∑e∈δ(v) ˆ zet ≤ pvt(ˆxvt) for all (v, t) ∈ {V ×T}\{(` v, ` t)}. Here, let `u ∈ U be the node incident to ` e and J(` e, ` t) := {t′ ∈ T | 0 ≤ t′ -` t < c` e` t }. Then, the second constraint holds for all (u, t) ∈ {U×T}\{`u}×J(` e, ` t) since the left-hand side of the inequality only decreases. For all (u, t) ∈ {`u}×J(` e, ` t), the second constraint holds because ∑(e,t)∈{(e,t)∈E×T |e∈δ(u),0≤t-t′<cet′ }\(` e,` t) max{0, ˆ zet′ -

ϵ}+ϵ ≤ 1. Therefore, replacing ˆx` v` t with xM, ˆ z` e` t (= 0) with ϵ, and ˆ zet with max{0, ˆ zet - ϵ} for all (e, t) ∈ E × T \ (` e, ` t) increases the objective value of (PA) from (ˆx, ˆ z) without impairing feasibility. This contradicts the optimality of (ˆx, ˆ z) for (PA). Then, ∑e∈δ(v) ˆ zet ̸= 0 for all v ∈ V , t ∈ T .

Then, we show that there exists an optimal solution (˜x, ˜ z) for (PA) that satisfies pvt(˜xvt) = ∑e∈δ(v) ˜ zet for all v ∈ V, t ∈ T. Let (ˆx, ˆ z) be an optimal solution for (PA). Then, from constraints of (PA), ∑e∈δ(v) ˆ zet ≤ pvt(ˆxvt) for all v ∈ V, t ∈ T. Suppose that there exists (v, t) satisfying ∑e∈δ(v) ˆ zet < pvt(ˆxvt) and let Ω := {(v, t) | ∑e∈δ(v) ˆ zet < pvt(ˆxvt)}. Since ∑e∈δ(v) ˆ zet > 0 and limx→∞pvt(x) = 0 fromAssumption 1, there exists a positive scalar dvt that satisfies ∑e∈δ(v) ˆ zet = pvt(ˆxvt + dvt) for all (v, t) ∈ Ω. Let ˜xvt be ˆxvt + dvt for all (v, t) ∈ Ω, and ˜xvt be ˆxvt for all (v, t) /∈ Ω, and ˜ z be ˆ z. Then, (˜x, ˜ z) is an optimal solution for (PA) because it is a feasible solution and the objective value is greater than or equal to the optimal value from ˆ z ≥ 0. Therefore, in (PA), there exists an optimal solution (˜x, ˜ z) satisfying ∑e∈δ(v) ˜ zet = pvt(˜xvt) for all v ∈ V and t ∈ T. Therefore, (PA) with the constraint "xvt = p-1 vt (∑e∈δ(v) zet) for all v ∈ V, t ∈ T", that is, (CP) is equivalent to (PA). Then, (x∗ , z∗ ) is an optimal solution for (PA).

7.5 Proof of Lemma 5

Since -p′vt (x)/pvt(x) is monotonically non-decreasing from Assumption 1, -pvt(x)/p′vt (x) is monotonically nonincreasing. Then, -x - pvt(x)/p′vt (x) is monotonically decreasing because -x is monotonically decreasing.

For all (v, t) ∈ V ×T and given z ∈ Svt, there exists only one x that satisfies pvt(x) = z from Assumption 1. Then, the following equality holds:

Here, we consider z1 ∈ Svt and z2 ∈ Svt satisfying z1 < z2 . Let x1 satisfy pvt(x1 ) = z1 and x2 satisfy pvt(x2 ) = z2 . Then, x1 > x2 since pvt is monotonically decreasing from Assumption 1. Since (12) holds and -x - pvt(x)/p′vt (x) is monotonically decreasing, (-p-1 vt (z1 )z1 )′ = -x1 - pvt(x1 )/p′vt (x1 ) < -x2 - pvt(x2 )/p′vt (x2 ) = (-p-1 vt (z2 )z2 )′ . Since (-p-1 vt (z)z)′ is monotonically increasing, (-p-1 vt (z)z) is convex. Moreover, the objective function of (CP) is convex since -p-1 vt (∑e∈δ(v) zet )∑e∈δ(v) zet is convex with respect to z for all v ∈ V and t ∈ T from [Boyd and Vandenberghe, 2004, Section 3.2.2].

7.6 Proof of Proposition 6

From Lemma 5, f ′vt is monotonically increasing and the left-hand side of equation (7), ∑i∈δ(v) (ai - τkf ′vt (s)), is monotonically decreasing. In addition, lims→0 f ′vt (s) = limx→∞ -x - pvt(x)/p′vt (x) = -∞ and lims→rvt f ′vt (s) = limx→-∞-x - pvt(x)/p′vt (x) = ∞ since pvt(x)/p′vt (x) is monotonically non-decreasing from Assumption 1. Therefore, lims→0 ∑i∈δ(v) (ai - τkf ′vt (s)) = ∞ and lims→rvt ∑i∈δ(v) (ai - τkf ′vt (s)) = -∞. Hence, equation (7) has a unique solution s∗ ∈ (0, rvt).

Next we show zvt = a-τkf ′vt (s∗ )1 is the optimal solution for the problem (6). Let y := zvt. Problem (6) is equivalent to the following optimization problem:

Then, we can define its Lagrangian function as follows:

The KKT conditions are f ′vt (s) - λ = 0, yi-ai τk + λ = 0 for all i ∈ δ(v), and 1⊤y - s = 0. Here, let λ∗ := f ′vt (s∗ ) and y∗ i := ai-τkf ′vt (s∗ ). Then, (s∗ , λ∗ , y∗ ) satisfy theKKT conditions. Since problem (13) satisfies the Slater's constraint qualification, y∗ is an optimal solution for problem (13) from [Boyd and Vandenberghe, 2004, Section 5.2.3]. Then, zvt satisfying zvt = y∗ = a - τkf ′vt (s∗ )1 is an optimal solution for problem (6).