Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing Yiding Feng

2025-05-06 0 0 4.42MB 59 页 10玖币

侵权投诉

Two-stage Stochastic Matching and Pricing with

Applications to Ride Hailing

Yiding Feng

Microsoft Research New England, yidingfeng@microsoft.com

Rad Niazadeh

University of Chicago Booth School of Business, Chicago, IL, rad.niazadeh@chicagobooth.edu

Amin Saberi

Management Science and Engineering, Stanford University, Stanford, CA, saberi@stanford.edu

Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply.

The platform can produce more eﬃcient matching and pricing decisions by batching the demand requests.

We initiate the study of the two-stage stochastic matching problem, with or without pricing, to enable the

platform to make improved decisions in a batch with an eye toward the imminent future demand requests.

This problem is motivated in part by applications in online marketplaces such as ride hailing platforms.

We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic match-

ing for maximizing supply eﬃciency, and two-stage joint matching and pricing for maximizing market eﬃ-

ciency. In the former problem, using a randomized primal-dual algorithm applied to a family of “balancing”

convex programs, we obtain the optimal 3/4 competitive ratio against the optimum oﬄine benchmark. Using

a factor revealing program and connections to submodular optimization, we improve this ratio against the

optimum online benchmark to (1 −1/e + 1/e2)≈0.767 for the unweighted and 0.761 for the weighted case.

In the latter problem, we design optimal 1/2-competitive joint pricing and matching algorithm by borrowing

ideas from the ex-ante prophet inequality literature. We also show an improved (1 −1/e)-competitive algo-

rithm for the special case of demand eﬃciency objective using the correlation gap of submodular functions.

Finally, we complement our theoretical study by using DiDi’s ride-sharing dataset for Chengdu city and

numerically evaluating the performance of our proposed algorithms in practical instances of this problem.*

1. Introduction

The recent growth of two-sided online marketplaces for allocating advertisements, rides, or other

goods and services has led to new interest in matching algorithms and enriched the ﬁeld with exciting

and challenging problems. This is mainly due to the real-time nature of these marketplaces which

requires the planner to make matching decisions between the current demand and supply with limited

or uncertain information about the future. This dynamic aspect of the matching decision and the

*A preliminary conference version of this work has appeared in the proceeding of the ACM-SIAM Symposium on Discrete

Algorithm (SODA’21) (Feng et al. 2021b), which contains only parts of this paper. In the current paper, all of the results in

Section 5, Section 6, Appendix C, and Appendix D are new and there are several additional insights throughout. Moreover,

the current paper presents all the proofs and technical details, most of which were missing in the early conference version.

arXiv:2210.11648v1 [cs.DS] 21 Oct 2022

Feng, Niazadeh, Saberi: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing

uncertainty of the future are modeled in diﬀerent ways. One prominent modeling approach in a two-

sided matching platform is using online bipartite matching (Karp et al. 1990;Devanur et al. 2013)

or online stochastic bipartite matching (Feldman et al. 2009b;Manshadi et al. 2012;Jaillet and Lu

2014). This way of modeling the problem captures scenarios when the matching platform has to match

arriving demand to the available supply immediately. This is particularly relevant in the context of

online advertising (Mehta et al. 2007;Buchbinder et al. 2007;Feldman et al. 2010), where arriving

search keywords should be matched to available advertisers—with almost no delay.

In applications that allow for some latency, the platform can produce a more eﬃcient matching

by accumulating requests and making decisions in a batch. For example, ride hailing and ridesharing

platforms such as Uber (Uber 2020), Lyft (Lyft 2016) and DiDi (Zhang et al. 2017) report substantial

improvements when shifting from match-as-you-go algorithms to batching, improving the eﬃciency of

the matching. Despite the eﬀectiveness and popularity of the batching paradigm in practice, quanti-

fying its eﬀectiveness from a theoretical lens—and in particular in the context of matching platforms

facing future demand uncertainty—is less studied.

The goal of this paper is to extend the batching framework in order to enable the platform to make

improved matching decisions in a batch, with an eye toward the immediate future. This is particularly

useful when the planner has side information about the compatibility of the imminently arriving

demand (e.g., the riders who opened their application and are about to make a ride request) to diﬀerent

available supplies, or has historical information about their demand distributions, maybe in the form

of samples from the data. We are also interested in scenarios where the platform not only has an eye

toward the immediate future, but also has a handle through pricing, to control the uncertain demand

in that future period. We then aim to extend our matching decision making framework to also allow

the platform to make improved matching decisions in a batch, jointly with improved pricing decisions

for the imminently arriving demand.

As a canonical model to mathematically capture the above scenarios, we consider this two-stage

stochastic optimization problem for matching the demand vertices Dto the supply vertices S:

Two-stage stochastic matching: We are given a bipartite graph G= (D, S, E), in which ver-

tices in Dare divided into two sets, D1and D2. In the ﬁrst stage, the algorithm chooses

a matching M1between D1and S. In the second stage, each vertex iin D2arrives inde-

pendently at random with probability πi. The algorithm can choose a matching M2between

the unmatched vertices of Sand a subset of D2that have arrived. The goal is to maximize

|M1∪M2|(in expectation).

Our techniques apply to a more general version of the problem in which every supply vertex j∈S

has a weight wjand these weights can be diﬀerent. The new objective function is to maximize (the

Feng, Niazadeh, Saberi: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing 3

expected) sum of the weights of the vertices in Smatched by either M1or M2. Naturally, we refer to

this problem as the vertex-weighted two-stage stochastic matching problem.

1.1. Connections to Ride Hailing Matching and Pricing

The reader may be interested in the formulation of the problem in the context of ride hailing. In

that setting, the supply set Srepresents the set of available drivers in a neighborhood. The ﬁrst

stage demand set D1represents the set of riders who have made a request for a ride and need to be

matched to a driver. The second stage demand set D2represents the set of riders who are entering

their destinations in the application and are about to receive a price quote and may or may not make a

request. Probability πicaptures the rate at which each rider in D2will be available for matching in the

second stage. The edge set Edetermines the compatibility of the riders and drivers, most commonly

based on their distance and occasionally other factors, such as riders and drivers review scores. Note

that in this context, the decision-maker (i.e., the platform) knows the graph in advance, meaning it

knows the drivers that will be compatible to each second stage rider, but it does not know whether

each second stage rider decides to make a ride request or not.

1.1.1. Application to Matching In real-world ride hailing applications, the number of available

drivers is normally large enough to serve all the riders in D1; however, the platform still must take into

consideration the combination of a long list of objectives to use the supply eﬃciently. This includes the

probability that the supply accepts the ride request, the number of ride requests fulﬁlled by a nearby

supply, or the total traveling distance, among others. The unweighted version of our problem can be

seen as a simpliﬁcation of this objective function in which the goal is to maximize the number of ride

requests matched to a compatible supply within a given distance. The vertex weights in our model can

be used to increase the priority of the supply nodes who have been idle longer, or to implement policies

that prioritize supply nodes with higher ratings or elite status. Now, the goal is to pick matchings M1

and M2to maximize the total weight of matched drivers at the end of the second stage—an objective

function which we refer to as supply eﬃciency.1

As a remark, one can also consider the edge-weighted version of this problem, in which the weight

of an edge captures the degree of compatibility of the two nodes (e.g., as a function of their distance).

This case is uninteresting, at least theoretically; the simple algorithm that tosses a fair coin to optimize

either for M1or M2gets at least 1

2of the total weight of the optimum oﬄine and that is the best

possible ratio that an algorithm can hope for (see Appendix EC.8 for details).

1Here we implicitly assume prices are exogenous and known, therefore the matching algorithm knows the rider availability

rates πifor each rider in D2.

Feng, Niazadeh, Saberi: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing

1.1.2. Application to Joint Matching and Pricing Also important is the price lever available

to the platform that can adjust the probability πiof being available for matching in the second stage

for vertices i∈D2. In this scenario, the platform oﬀers a personalized price to each vertex i∈D2

in the ﬁrst stage. We consider a Bayesian model where each rider i∈Dhas an independent value

drawn from a known prior distribution for the ride. Rider ithen accepts her price quote – and hence

will be available for matching in the second stage – if and only if her value for the ride exceeds the

price. Therefore, the price oﬀered to rider i∈D2determines the probability πithat she is available for

matching in the second stage. In the ﬁrst stage, the platform chooses a matching between D1and Sand

oﬀers prices to riders in D2. In the second stage, it chooses a matching between the unmatched vertices

in Sand those vertices in D2who have accepted the prices. The goal is to maximize a particular

objective function through this process.

The choice of the objective function for this matching/pricing problem requires some care. If we

only aim to maximize supply eﬃciency, the best choice of prices is all zero; this is simply because

with increasing prices there will be less riders accepting their price oﬀers to be matched to the drivers.

However, from the eye of a market designer who pays attention to both sides of the market, non-zero

prices will help with increasing the demand eﬃciency—i.e., increasing total valuation of matched riders

or equivalently, their social welfare. At ﬁrst glance, it might seem intuitive that setting prices to zero

will also help with increasing the demand eﬃciency. This is indeed not the case, as the platform only

gets to observe whether riders accepted or declined their price oﬀers, and not their exact valuations.

Therefore, non-zero prices will help with demand discovery and ﬁltering out low value buyers from

getting matched in the market, and hence can increase the demand eﬃciency. See Appendix EC.7 for

details of how pricing can help with the demand eﬃciency of the matching.

To capture the above trade-oﬀ between high prices for demand discovery and low prices for supply

eﬃciency, we consider maximizing an objective function which we refer to as market eﬃciency. This

objective function includes both the expected total weights of the matched drivers in D(i.e., the

supply eﬃciency objective) and the expected social welfare/total values of the matched riders in both

D1and D2, given the information of the platform regarding riders in D1and D2(i.e., the demand

eﬃciency objective). See Section 2for a formal deﬁnition.

1.2. Technical Contributions

We initiate the study of both two-stage stochastic matching problem and two-stage joint matching and

pricing problem with a focus on the worst case competitive analysis of these problems. For measuring

the competitive ratio, we consider the optimum solution in hindsight, which we refer to as the optimum

oﬄine, and the solution of the computationally-unbounded optimum algorithm, which we refer to as

the optimum online. We now summarize our main contributions.

Feng, Niazadeh, Saberi: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing 5

Optimal competitive two-stage matching vs. optimum oﬄine: In Section 3.1, we present

polynomial-time algorithms with the competitive ratio of 3

4compared to the optimum oﬄine for both

weighted and unweighted versions of the problem and show that this factor is optimum for both cases

of two-stage stochastic matching. Somewhat interestingly, our optimum competitive algorithms do not

use any information about the second stage graph (including the edges and availability probabilities

πi’s). In fact, we show a stronger result and prove that our algorithms achieve the competitive ratio

of 3

4even when the second stage graph is picked by an oblivious adversary.

Convex programming based weighted-balanced-utilization: The main idea of both algo-

rithms is to ﬁnd a balanced allocation of demand D1to supply S, while also taking the priority weights

into consideration in a principled way. We identify a family of convex programs to characterize such

a balanced randomized allocation in the ﬁrst stage—not necessarily of maximum total weight—that

hedges against the uncertainty of the demand in the second stage. Using the strong duality of the con-

vex programs, we introduce a primal-dual framework that bounds the competitive ratio of randomized

integral matchings sampled from the optimal solution of these convex programs.

Primal-dual using the convex programming based graph decomposition: The convex

program family we consider also oﬀers a decomposition of the ﬁrst stage graph into pairs of supply

and demand nodes, which in the special unweighted case coincides with the well-studied matching

skeleton introduced by Goel et al. (2012). Notably, this matching skeleton graph decomposition is

closely related to the Edmonds-Gallai decomposition (Edmonds 1965,Gallai 1964) of bipartite graphs.

In this sense, we generalize the concept of matching skeleton to vertex weighted graphs as a byproduct

of our primal-dual approach, which might be of independent interest. We should note that our convex

programming based decomposition is constructed using strong duality and incorporating the KKT

conditions of the convex program. As a result, it plays a critical role in setting up our improved primal-

dual framework for this problem in a way that diverges from the standard primal-dual framework in the

literature on online bipartite allocations (e.g., Mehta et al. (2007), Buchbinder et al. (2007), Devanur

et al. (2013), Golrezaei et al. (2014), Goyal and Udwani (2020), Feng et al. (2019), Ma and Simchi-Levi

(2020)). Note that the competitive ratio (1 −1/e) is known for the fully online version of the problem,

thanks to the classic work of Karp, Vazirani and Vazriani (1990) and its extension to vertex-weighted

online bipartite matching in Aggarwal et al. (2011). The new algorithmic construct of using convex

programming based decomposition in the primal-dual analysis is the key to improve this competitive

ratio from (1 −1/e) to 3

4, which is optimum for our two-stage problem.

Complexity of optimum online and an improved competitive algorithm: In Section 4.1 and

Section 4.2, we turn our attention to approximating the optimum online. In that case, the problem is

in the realm of approximation algorithms and related to maximizing the sum of monotone submodular

and negative linear functions subject to matroid constraints (Calinescu et al. 2011,Sviridenko et al.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Two-stageStochasticMatchingandPricingwithApplicationstoRideHailingYidingFengMicrosoftResearchNewEngland,yidingfeng@microsoft.comRadNiazadehUniversityofChicagoBoothSchoolofBusiness,Chicago,IL,rad.niazadeh@chicagobooth.eduAminSaberiManagementScienceandEngineering,StanfordUniversity,Stanford,CA,saberi@...

展开>> 收起<<

Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing Yiding Feng.pdf

共59页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing Yiding Feng

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: