ISE Seminar Calendar

View Full Calendar

ISE Graduate Seminar Series: Rad Niazadeh

Event Type
Seminar/Symposium
Sponsor
ISE Graduate Programs
Date
Oct 30, 2020   10:00 - 11:00 am  
Speaker
Rad Niazadeh
Views
42

When Matching Meets Batching: Optimal Multi-stage Algorithms and Applications

In several applications of real-time matching of demand to supply in online marketplaces -- for example matching delivery requests to dispatching centers in Amazon or matching riders to drivers in ride hailing platforms such as Uber/Lyft -- the platform can allow for some latency to batch the demand and improve the matching's efficiency. Motivated by these scenarios, I investigate the optimal trade-off between batching and inefficiency for online allocations in this talk. In particular, I consider K-stage variants of classic online bipartite allocation problems such as vertex-weighted budgeted matching (Aggarwal et al., 2011) and online budgeted allocation/AdWords (Mehta et al., 2007), where online vertices arrive in K batches. Our main result is showing  (1-(1-1/K)^K)-competitive algorithms for these problems, improving the (1-1/e) competitive ratios known in the literature for the online variant of these problems. We further show no multi-stage algorithm can obtain a better competitive ratio -- proving the optimality of our result.

Our main technique is focusing on a family of convex-programming based matchings that distribute the demand in a particularly balanced way among supply in different stages. More precisely, we identify a sequence of "polynomials with decreasing degrees" that can be used as strictly concave regularizers of the optimal matching linear program to form this family. By providing structural decompositions of the underlying stage graph using the optimal solutions of these convex programs, we develop a new multi-stage primal-dual framework to analyze the fractional multi-stage algorithm that returns the corresponding regularized optimal matching in each stage. We extend our results to integral allocations in the large budget regime using standard rounding techniques. If time allows, I also briefly mention other results related to two-stage stochastic matching and two-stage joint matching and pricing in ride hailing platforms, that are intimately connected to some of the ideas which will be presented in this talk.

The talk is based on the following two working papers:

(i) "Batching and Optimal Multi-stage Bipartite Allocations", with Yiding Feng 

(https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3689448)

(ii) "Two-stage Matching and Pricing with Applications to Ride Hailing", with Yiding Feng and Amin Saberi

(https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3613755)

link for robots only