Research
My research interests broadly span the intersection of Algorithms, Operations Research, and Artificial Intelligence. I am generally interested in various stochastic optimization problems arising in E-commerce, Internet advertising, crowdsourcing markets, data mining, databases, and revenue management. My expertise lies in the interface of Randomized Algorithms, Probabilistic Models, Stochastic Optimization, and Applied AI. My recent research primarily focuses on these two directions: (1) algorithm design and analysis for online and offline stochastic matching models; (2) online allocation policy design for different autonomous systems featuring real-time decision-making process such as crowdsourcing markets and rideshare platforms. For more details, please read my research statement: Research Statement.
The following are projects that I have developed, and actively been investigating together with my collaborators in recent years (2016+).
Recent Projects
- Online matching policy design for ridesharing (or taxi-dispatching) platforms.
Ridesharing platforms such as Uber and Lyft have gained increasing popularity in recent years. One of the central tasks facing Uber and Lyft is the matching policy design among drivers and riders, such that platforms can fulfill their preferences as much as possible, and maintain high profitability meanwhile. Here are a few fundamental challenges.
First, there are substantial uncertainties in the arrival times and locations for both drivers and riders. Furthermore, each rider has to be matched with a nearby driver very shortly after her arrival; otherwise, the rider will run out of patience and leave the system. This real-time decision-making requirement significantly complicates the online matching policy design.
Second, there are natural preferences from drivers and riders, which are somewhat conflicting. Generally, drivers prefer highly-rewarding tasks (e.g., online riders with a long distance) while riders prefer nearby drivers such that her waiting time is minimized. It is highly desirable to balance these preferences perfectly while ensuring that the platform is still highly profitable.
In our projects, we utilize the state-of-the-art machine learning techniques to predict the arrival patterns of online riders from massive historical data and propose several data-driven models to capture the challenging issues shown above. Additionally, we have designed model-specific algorithmic solutions and carefully analyzed them both theoretically and empirically on both real and synthetic datasets.
"Balancing the Tradeoff between Profit and Fairness in Rideshare Platforms during High-Demand Hours", AAAI & AIES (Oral Presentation), 2020."Mix and Match: Markov Chains and Mixing Times for Matching in Rideshare". WINE 2019."Preference-Aware Task Assignment in On-demand Taxi Dispatching: An Online Stable Matching Approach". AAAI, 2019. "Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources". AAAI, 2018.- Algorithmic solutions to online recommendations for digital marketplaces.
One of the fundamental algorithmic challenges facing digital marketplaces such as Amazon and Netflix is how to balance the relevance and diversity in recommendations. To solve this problem, we propose an online-matching based model which has the following two features. The first is dynamic arrivals of online agents such as online buyers and impressions. The second is the objective of maximization of an arbitrary non-negative monotone submodular function over the set of all matched edges. Our formulation is general enough to capture both diversity (e.g., a weighted coverage function) and relevance (e.g., the traditional linear functions)—as well as many other natural objective functions occurring in practice (e.g., the limited total budget in advertising settings).
Another issue arising in the new checkout recommendation system at Walmart’s online grocery is how to dynamically offer discounted items to each online buyer upon her checkout. This can be well captured by the Online Stochastic Matching with Timeouts (OSMT) problem. We have theoretically analyzed OSMT and designed an effective online algorithm, which improve the current best online competitive ratio from 0.24 to 0.46.
"Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity". AAAI, 2019."Attenuate Locally, Win Globally: Attenuation-based Frameworks for Online Stochastic Matching with Timeouts". AAMAS, 2017.- Online task-allocation policy design in crowdsourcing markets.
In our project, we focus on the following two markets. The first is "crowdsourcing human resources" marketplaces (CHRM) such as MTurk (Amazon’s Mechanical Turk) and the second is spatial crowdsourcing markets (SCM). A typical scenario in the first case is as follows. The system has a set of tasks uploaded by a requester. Each time when a worker arrives, the system will assign her a set of tasks based on her interest and she will get paid accordingly from the account created by the requester. One natural question is how to dynamically assign tasks to workers such that the total utility obtained by the requester from all completed tasks is maximized under a given budget. In spatial crowdsourcing markets (e.g., online food-delivery platforms such as Grubhub and Uber Eats), each task and worker has a specific location attribute. To perform a task, the worker is expected to complete a trip specified by the task. A similar question arises here as well: how the platform should match the workers and tasks effectively such that the total number of tasks completed is maximized.
There are several challenging issues in the matching policy design for both markets. The first one is the dynamic arrivals of workers and tasks, which is often further complicated by the real-time decision-making requirement. The second is the various kinds of conflicts among tasks. For example, two tasks in CHRM may conflict each other due to privacy concerns such that they cannot be assigned to the same worker. In SCM, two tasks can be conflicting for some worker if they are too far away from each other such that the worker cannot complete them before deadlines. The third one is the unknown workers' skills, which we need to predict based on historical assignments. To address the above issues, we try to utilize powerful data analytical techniques (for predictions of online arrival patterns of workers and tasks, workers' skills, etc.), and apply existing robust online matching models to output an effective online allocation policy.
"Online Resource Allocation in Matching Problems". AAMAS, 2019."A Unified Approach to Online Matching with Conflict-Aware Constraints". AAAI, 2019."Assigning Tasks to Workers based on Historical Data: Online Task Assignment with Two-sided Arrivals". AAMAS, 2018."Budgeted Online Assignment in Crowdsourcing Markets: Theory and Practice". AAMAS, 2017.