Dynamic Stochastic Matching Under Limited Time

References

• Adan I, Weiss G (2012) Exact FCFS matching rates for two infinite multitype sequences. Oper. Res. 60(2):475–489.Link, Google Scholar
• Adan I, Weiss G (2014) A skill based parallel service system under FCFS-ALIS—Steady state, overloads, and abandonments. Stochastic Systems 4(1):250–299.Link, Google Scholar
• Afeche P, Caldentey R, Gupta V (2022) On the optimal design of a bipartite matching queueing system. Oper. Res. Forthcoming.Link, Google Scholar
• Akbarpour M, Li S, Gharan SO (2020) Thickness and information in dynamic matching markets. J. Political Econom. 128(3):783–815.Crossref, Google Scholar
• Alonso-Mora J, Samaranayake S, Wallar A, Frazzoli E, Rus D (2017) On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc. National Acad. Sci. USA 114(3):462–467.Crossref, Google Scholar
• Anderson R, Ashlagi I, Gamarnik D, Kanoria Y (2017) Efficient dynamic barter exchange. Oper. Res. 65(6):1446–1459.Link, Google Scholar
• Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2019) Edge weighted online windowed matching. Proc. ACM Conf. on Econom. and Comput. (ACM, New York), 729–742.Google Scholar
• Ashlagi I, Azar Y, Charikar M, Chiplunkar A, Geri O, Kaplan H, Makhijani R, et al. (2017) Min-cost bipartite perfect matching with delays. Approximation, Randomization, and Combinatorial Optimization.Google Scholar
• Ashlagi I, Bingaman A, Burq M, Manshadi V, Gamarnik D, Murphey C, Roth AE, et al. (2018) Effect of match-run frequencies on the number of transplants and waiting times in kidney exchange. Amer. J. Transplantation 18(5):1177–1186.Crossref, Google Scholar
• Baccara M, Lee S, Yariv L (2020) Optimal dynamic matching. Theoretical Econom. 15(3):1221–1278.Crossref, Google Scholar
• Banerjee S, Kanoria Y, Qian P (2018) Dynamic assignment control of a closed queueing network under complete resource pooling. Preprint, submitted March 13, https://arxiv.org/abs/1803.04959.Google Scholar
• Bansal N, Buchbinder N, Gupta A, Naor JS (2007) An O(log2k)-competitive algorithm for metric bipartite matching. Proc. Eur. Sympos. on Algorithms (Springer, New York), 522–533.Google Scholar
• Bertsekas DP, Tsitsiklis JN (1996) Neuro-Dynamic Programming, vol. 5 (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D, Jaillet P, Martin S (2019) Online vehicle routing: The edge of optimization in large-scale applications. Oper. Res. 67(1):143–162.Link, Google Scholar
• Brandt A, Last G (1994) On the pathwise comparison of jump processes driven by stochastic intensities. Math. Nachrichten 167(1):21–42.Crossref, Google Scholar
• Buchholz N (2022) Spatial equilibrium, search frictions and efficient regulation in the taxi industry. Rev. Econom. Stud. 89(2):556–591.Crossref, Google Scholar
• Cadas A, Bušić A, Doncel J (2019) Optimal control of dynamic bipartite matching models. Proc. 12th EAI Internat. Conf. on Performance Evaluation Methodologies and Tools (ACM, New York), 39–46.Google Scholar
• Caldentey R, Kaplan EH, Weiss G (2009) FCFS infinite bipartite matching of servers and customers. Adv. Appl. Probabilities 41(3):695–730.Crossref, Google Scholar
• Collina N, Immorlica N, Leyton-Brown K, Lucier B, Newman N (2020) Dynamic weighted matching with heterogeneous arrival and departure rates. Chen X, Gravin N, Hoefer M, Mehta R, eds. Proc. Web and Internet Econom. (Springer-Verlag, Berlin, Heidelberg), 17–30.Google Scholar
• Devanur NR, Hayes TP (2009) The Adwords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. on Electronic Commerce (ACM, New York), 71–78.Google Scholar
• Dickerson J, Sankararaman K, Srinivasan A, Xu P (2018) Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. Proc. AAAI Conf. on Artificial Intelligence, vol. 32.Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. Proc. 50th Annual IEEE Sympos. on Foundations of Comput. Sci. (IEEE, New York), 117–126.Google Scholar
• Gallego G, Ratliff R, Shebalov S (2014) A general attraction model and sales-based linear program for network revenue management under customer choice. Oper. Res. 63(1):212–232.Link, Google Scholar
• Garg N, Nazerzadeh H (2021) Driver surge pricing. Management Sci., ePub ahead of print August 9, https://doi.org/10.1287/mnsc.2021.4058.Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to Adwords. Proc. 19th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 982–991.Google Scholar
• Guo X, Hernández-Lerma O (2009) Continuous-Time Markov Decision Processes (Springer, Berlin).Crossref, Google Scholar
• Gupta A, Guruganesh G, Peng B, Wajc D (2019) Stochastic online metric matching. Preprint, submitted XX, https://arxiv.org/abs/1904.09284.Google Scholar
• Gurvich I, Ward A (2014) On the dynamic control of matching queues. Stochastic Systems 4(2):479–523.Link, Google Scholar
• Hu M, Zhou Y (2021) Dynamic type matching. Manufacturing Service Oper. Management 24(1):125–142.Link, Google Scholar
• Huang Z, Kang N, Tang ZG, Wu X, Zhang Y, Zhu X (2018) How to match when all vertices arrive online. Proc. 50th Annual ACM SIGACT Sympos. on Theory of Comput. (ACM, New York), 17–29.Google Scholar
• Huang Z, Peng B, Tang ZG, Tao R, Wu X, Zhang Y (2019) Tight competitive ratios of classic matching algorithms in the fully online model. Proc. 30th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 2875–2886.Google Scholar
• Jaillet P, Lu X (2013) Online stochastic matching: New algorithms with better bounds. Math. Oper. Res. 39(3):624–646.Link, Google Scholar
• Kalyanasundaram B, Pruhs K (1993) Online weighted matching. J. Algorithms 14(3):478–488.Crossref, Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. on Theory of Comput. (ACM, New York), 352–358.Google Scholar
• Khuller S, Mitchell SG, Vazirani VV (1994) On-line algorithms for weighted bipartite matching and stable marriages. Theoretical Comput. Sci. 127(2):255–267.Crossref, Google Scholar
• López FJ, Martínez S, Sanz G (2000) Stochastic domination and Markovian couplings. Adv. Appl. Probabilities 32(4):1064–1076.Crossref, Google Scholar
• Lyft (2016) Matchmaking in lyft line: Part 1. https://eng.lyft.com/matchmaking-in-lyft-line9c2635fe62c4.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):1787–1803.Link, 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 (2005) Adwords and generalized on-line matching. Proc. 46th Annual IEEE Sympos. on Foundations of Comput. Sci. (IEEE, New York), 264–273.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Found. Trends Theoretical Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Özkan E, Ward AR (2020) Dynamic matching for real-time ride sharing. Stochastic Systems 10(1):29–70.Link, Google Scholar
• Puterman ML (2014) Markov Decision Processes: Discrete Stochastic Dynamic Programming (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Santi P, Resta G, Szell M, Sobolevsky S, Strogatz SH, Ratti C (2014) Quantifying the benefits of vehicle pooling with shareability networks. Proc. National Acad. Sci. USA 111(37):13290–13294.Crossref, Google Scholar
• Talluri K, van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(24):15–33.Link, Google Scholar
• Talreja R, Whitt W (2008) Fluid models for overloaded multiclass many-server queueing systems with first-come, first-served routing. Management Sci. 54(8):1513–1527.Link, Google Scholar
• Topaloglu H (2013) Joint stocking and product offer decisions under the multinomial logit model. Production Oper. Management 22(5):1182–1199.Crossref, Google Scholar
• Truong VA, Wang X (2019) Prophet inequality with correlated arrival probabilities, with application to two sided matchings. Preprint, submitted XX, https://arxiv.org/abs/1901.02552.Google Scholar
• Tsitsiklis JN, Xu K (2017) Flexible queueing architectures. Oper. Res. 65(5):1398–1413.Link, Google Scholar
• Wolff RW (1982) Poisson arrivals see time averages. Oper. Res. 30(2):223–231.Link, Google Scholar
• Yan C, Zhu H, Korolko N, Woodard D (2020) Dynamic pricing and matching in ride-hailing platforms. Naval Res. Logist. 67(8):705–724.Crossref, Google Scholar