PhD Defense: 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 uncertainty, which manifests in the following two ways. The first is on the arrival of agents in the system, e.g., drivers and riders in ridesharing services, keywords in the Internet advertising, and online workers in crowdsourcing markets. The second is on the outcome of interactions. For example, two users may like or dislike each other after a dating arranged by a match-making firm, a user may click or 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: 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.
Examining Committee:

Chair: Dr. John Dickerson Dean's rep: Dr. Prakash Narayan Members: Dr. Andrew Childs Dr. Furong Huang Dr. David Mount Dr. Aravind Srinivasan