Two-Stage Stochastic Matching and Pricing with Applications to Ride Hailing

References

• Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1253–1264.Google Scholar
• Agrawal S, Ding Y, Saberi A, Ye Y (2010) Correlation robust stochastic optimization. Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1087–1096.Google Scholar
• Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• Alaei S, Hajiaghayi MT, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proc. 13th ACM Conf. Electronic Commerce (ACM, New York), 18–35.Google Scholar
• Anari N, Niazadeh R, Saberi A, Shameli A (2019) Nearly optimal pricing algorithms for production constrained and laminar Bayesian selection. Proc. 2019 ACM Conf. Econom. Comput. (ACM, New York), 91–92.Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Eur. Sympos. Algorithms (Springer, New York), 253–264.Google Scholar
• Calinescu G, Chekuri C, Pál M, Vondrák J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6):1740–1766.Crossref, Google Scholar
• Devanur NR, Jain K, Kleinberg RD (2013) Randomized primal-dual analysis of ranking for online bipartite matching. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 101–107.Google Scholar
• DiDi Chuxing (2020) https://outreach.didichuxing.com/appEn-vue/KDD_CUP_2020, 2020.Google Scholar
• Dütting P, Feldman M, Kesselheim T, Lucier B (2017) Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. IEEE 58th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 540–551.Google Scholar
• Edmonds J (1965) Paths, trees, and flowers. Canadian J. Math. 17:449–467.Crossref, Google Scholar
• Ezra T, Feldman M, Gravin N, Tang ZG (2020) Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. Proc. 21st ACM Conf. Econom. Comput. (ACM, New York), 769–787.Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1014–1033.Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 117–126.Google Scholar
• Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C (2010) Online stochastic packing applied to display ad allocation. Eur. Sympos. Algorithms (Springer, New York), 182–194.Google Scholar
• Feng Y, Niazadeh R (2020) Batching and optimal multi-stage bipartite allocations. Chicago Booth Research Paper, Chicago.Google Scholar
• Feng Y, Niazadeh R (2021) Batching and optimal multi-stage bipartite allocations. 12th Innovations Theoretical Comput. Sci. Conf. (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• Feng Y, Niazadeh R, Saberi A (2019) Linear programming based online policies for real-time assortment of reusable resources. Preprint, submitted July 17, https://dx.doi.org/10.2139/ssrn.3421227.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2020) Near-optimal Bayesian online assortment of reusable resources. Chicago Booth Research Paper (20-40), Chicago.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2021) Two-stage stochastic matching with application to ride hailing. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2862–2877.Google Scholar
• Gallai T (1964) Maximale systeme unabhangiger kanten. Magyar Tudományos Akadémia. Matematikai Kutató Intézetének Közleményei 9:401–413.Google Scholar
• Gandhi R, Khuller S, Parthasarathy S, Srinivasan A (2006) Dependent rounding and its applications to approximation algorithms. J. ACM. 53(3):324–360.Crossref, Google Scholar
• Goel A, Kapralov M, Khanna S (2012) On the communication and streaming complexity of maximum bipartite matching. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 468–485.Google Scholar
• Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• Goyal V, Udwani R (2020) Online matching with stochastic rewards: Optimal competitive ratio via path based formulation. Proc. 21st ACM Conf. Econom. Comput. (ACM, New York), 791–791.Google Scholar
• Jaillet P, Lu X (2014) Online stochastic matching: New algorithms with better bounds. Math. Oper. Res. 39(3):624–646.Link, Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358.Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• Lee E, Singla S (2017) Maximum matching in the online batch-arrival model. Internat. Conf. Integer Programming Combin. Optim. (Springer, New York), 355–367.Google Scholar
• Lyft (2016) Matchmaking in Lyft line: Part 1. https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4.Google Scholar
• Ma W, Simchi-Levi D (2020) Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios. Oper. Res. 68(6).Link, Google Scholar
• Ma W, Simchi-Levi D, Zhao J (2021) Dynamic pricing (and assortment) under a static calendar. Management Sci. 67(4):2292–2313.Link, Google Scholar
• Manshadi V, Rodilitz S (2020) Online policies for efficient volunteer crowdsourcing. Proc. 21st ACM Conf. Econom. Comput. (ACM, New York), 315–316.Google Scholar
• Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573.Link, Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM, 54(5):22–es.Crossref, Google Scholar
• Nash JF (1950) The bargaining problem. Econometrica 18(2):155–162.Crossref, Google Scholar
• Rawls J (1971) A Theory of Justice (Harvard University Press, Cambridge, MA).Crossref, Google Scholar
• Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, vol. 24 (Springer Science & Business Media, Berlin).Google Scholar
• Sviridenko M, Vondrák J, Ward J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4):1197–1218.Link, Google Scholar
• Uber (2020) Uber marketplace and matching. https://marketplace.uber.com/matching.Google Scholar
• Yan Q (2011) Mechanism design via correlation gap. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 710–719.Google Scholar
• Zhang L, Hu T, Min Y, Wu G, Zhang J, Feng P, Gong P, Ye J (2017) A taxi order dispatch model based on combinatorial optimization. Proc. 23rd ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 2151–2159.Google Scholar