Matching Algorithm Design in E-Commerce: Harnessing the Power of Machine Learning via Stochastic Optimization

Internet-based matching markets have gained great attention during the last decade, such as Internet advertising (matching keywords and advertisers), ridesharing platforms (pairing riders and drivers), crowdsourcing markets (assigning tasks to workers), online dating (pairing romantically attracted partners), etc. A fundamental challenge is the presence of \emph{uncertainty}, which manifests in the following two ways. The first is on the arrival of agents in the system, e.g., \emph{drivers} and \emph{riders} in ridesharing services, \emph{keywords} in the Internet advertising, and \emph{online workers} in crowdsourcing markets. The second is on the outcome of interaction. For example, two users may \emph{like} or \emph{dislike} each other after a dating arranged by a match-making firm, a user may \emph{click} or \emph{not click} the link of an advertisement shown by an Ad company, to name a few. We are now living in an era of big data, fortunately. Thus, by applying powerful machine learning techniques to huge volumes of historical data, we can often get very accurate estimates of the uncertainty in the system as described above. Given this, the question then is as follows: \emph{How can we exploit estimates for our benefits as a matching-policy designer}? This dissertation aims to address this question. We have built an AI toolbox, which takes as input the estimates over uncertainty in the system, appropriate objectives (e.g., maximization of the total profit, maximization of fairness, etc.), and outputs a matching policy which works well both theoretically and experimentally on those pre-specified targets. The key ingredients are two matching models: stochastic matching and online matching. We have made several foundational algorithmic progress for these two models. Additionally, we have successfully utilized these two models to harness estimates from powerful machine learning algorithms, and designed improved matching policies for various real matching markets including ridesharing, crowdsourcing, and online recommendation applications.

Department dc:contributor.department

Computer Science

Year dc:date.issued

2019

Author dc:creator

• Xu, Pan

Advisors dc:contributor.advisor

• Dickerson, John
• Srinivasan, Aravind

Language dc:language.iso

en

Identifier

https://doi.org/10.13016/jyap-nqmj

OAI identifier oai:identifier

oai:drum.lib.umd.edu:1903/25012