An Approximate Dynamic Programming Approach to Dynamic Stochastic Matching

References

• Abraham DJ, Blum A, Sandholm T (2007) Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. Proc. 8th ACM Conf. Electronic Commerce (ACM, New York), 295–304.Google Scholar
• Adelman D (2004) A price-directed approach to stochastic inventory/routing. Oper. Res. 52(4):499–514.Link, Google Scholar
• Adelman D (2007) Dynamic bid prices in revenue management. Oper. Res. 55(4):647–661.Link, Google Scholar
• Aouad A, Saritac O (2022) Dynamic stochastic matching under limited time. Oper. Res. 70(4):2349–2383.Link, Google Scholar
• Awasthi P, Sandholm T (2009) Online stochastic optimization in the large: Application to kidney exchange. Kitano H, ed. Proc. 21st Internat. Joint Conf. Artificial Intelligence (Morgan Kaufmann Publishers, San Francisco), 405–411.Google Scholar
• Chen Z, Xue S, Kolen J, Navid A, Zaman K, Sun YS, El-Nasr MS (2017) Eomm: An engagement optimized matchmaking framework. Proc. 26th Internat. Conf. World Wide Web (IW3C2, Geneva, Switzerland), 1143–1150.Google Scholar
• Cook WJ, Cunningham W, Pulleyblank W, Schrijver A (1997) Combinatorial Optimization (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Cooper WL (2002) Asymptotic behavior of an allocation policy for revenue management. Oper. Res. 50(4):720–727.Link, Google Scholar
• de Farias DP, Van Roy B (2003) The linear programming approach to approximate dynamic programming. Oper. Res. 51(6):850–865.Link, Google Scholar
• de Farias DP, Van Roy B (2004) On constraint sampling in the linear programming approach to approximate dynamic programming. Math. Oper. Res. 29(3):462–478.Link, Google Scholar
• Derman C, Lieberman GJ, Ross SM (1972) A sequential stochastic assignment problem. Management Sci. 18(7):349–355.Link, Google Scholar
• Desrosiers J, Lübbecke ME (2005) A primer in column generation. Column Generation (Springer, Berlin), 1–32.Crossref, Google Scholar
• Dickerson J, Procaccia A, Sandholm T (2012) Dynamic matching via weighted myopia with application to kidney exchange. Proc. 26th AAAI Conf. Artificial Intelligence, vol. 26 (AAAI Press, Palo Alto, CA), 1340–1346.Google Scholar
• Dickerson JP, Procaccia AD, Sandholm T (2019) Failure-aware kidney exchange. Management Sci. 65(4):1768–1791.Link, Google Scholar
• Edmonds J (1965) Paths, trees, and flowers. Canadian J. Math. 17(3):449–467.Crossref, Google Scholar
• Emek Y, Kutten S, Wattenhofer R (2016) Online matching: Haste makes waste! Proc. 48th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 333–344.Crossref, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 117–126.Google Scholar
• Gallego G, Topaloglu H (2019) Network revenue management with independent demands. Revenue Management and Pricing Analytics (Springer, New York), 47–81.Crossref, Google Scholar
• Hotz A, Wang Q (2019) Gaining insights in a simulated marketplace with machine learning at uber. Accessed August 11, 2023, https://eng.uber.com/simulated-marketplace/.Google Scholar
• Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Math. Oper. Res. 37(2):313–345.Link, Google Scholar
• Lei Y, Jasin S, Uichanco J, Vakhutinsky A (2022) Joint product framing (display, ranking, pricing) and order fulfillment under the multinomial logit model for e-commerce retailers. Manufacturing Service Oper. Management 24(3):1529–1546.Link, Google Scholar
• Li Z, Lieberman K, Macke W, Carrillo S, Ho CJ, Wellen J, Das S (2019) Incorporating compatible pairs in kidney exchange: A dynamic weighted matching model. Proc. ACM Conf. Econom. Comput. (ACM, New York), 349–367.Google Scholar
• Lin Q, Nadarajah S, Soheili N (2020) Revisiting approximate linear programming: Constraint-violation learning with applications to inventory control and energy storage. Management Sci. 66(4):1509–1782.Google Scholar
• Manne AS (1960) Linear programming and sequential decisions. Management Sci. 6(3):259–267.Link, Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22.Crossref, Google Scholar
• Özkan E, Ward AR (2020) Dynamic matching for real-time ride sharing. Stochastic Systems 10(1):29–70.Link, Google Scholar
• Padberg MW, Rao MR (1982) Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7(1):67–80.Link, Google Scholar
• Patrick J, Puterman ML, Queyranne M (2008) Dynamic multipriority patient scheduling for a diagnostic resource. Oper. Res. 56(6):1507–1525.Link, Google Scholar
• Powell WB (2011) Approximate Dynamic Programming: Solving the Curses of Dimensionality, 2nd ed. (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Puterman ML (1994) Markov Decision Processes: Discrete Stochastic Dynamic Programming (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Roth AE, Sönmez T, Ünver MU (2005) A kidney exchange clearinghouse in New England. Amer. Econom. Rev. 95(2):376–380.Crossref, Google Scholar
• Rothvoß T (2017) The matching polytope has exponential extension complexity. J. ACM 64(6):1–19.Crossref, Google Scholar
• Saidman SL, Roth AE, Sönmez T, Ünver MU, Delmonico FL (2006) Increasing the opportunity of live kidney donation by matching for two-and three-way exchanges. Transplantation 81(5):773–782.Crossref, Google Scholar
• Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Schweitzer PJ, Seidmann A (1985) Generalized polynomial approximations in Markovian decision processes. J. Math. Anal. Appl. 110(2):568–582.Crossref, Google Scholar
• Spivey MZ, Powell WB (2004) The dynamic assignment problem. Transportation Sci. 38(4):399–419.Link, Google Scholar
• Su X, Zenios SA (2005) Patient choice in kidney allocation: A sequential stochastic assignment model. Oper. Res. 53(3):443–455.Link, Google Scholar
• Tong C, Topaloglu H (2013) On the approximate linear programming approach for network revenue management problems. INFORMS J. Comput. 26(1):121–134.Link, Google Scholar
• Trick MA, Zin SE (1997) Spline approximations to value functions. Macroeconom. Dynamics 1(1):255–277.Crossref, Google Scholar
• van Dongen J (2018) The awesomenauts matchmaking algorithm: Scoring the quality of a match. Accessed August 11, 2023, http://joostdevblog.blogspot.com/2018/09/the-awesomenauts-matchmaking-algorithm.html.Google Scholar
• Véron M, Marin O, Monnet S (2014) Matchmaking in multi-player on-line games: Studying user traces to improve the user experience. Proc. Network and Operating System Support on Digital Audio and Video Workshop (ACM, New York), 7–12.Google Scholar
• Vossen TWM, Zhang D (2015) Reductions of approximate linear programs for network revenue management. Oper. Res. 63(6):1352–1371.Link, Google Scholar
• Vossen TWM, You F, Zhang D (2022) Finite-horizon approximate linear programs for capacity allocation over a rolling horizon. Production Oper. Management 31(5):2127–2142.Crossref, Google Scholar
• Xu M, Yu Y, Wu C (2021) Rule designs for optimal online game matchmaking. Proc. 40th Chinese Control Conference (IEEE Piscataway, NJ), 1055–1062.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
• You F, Vossen T (2023) An approximate dynamic programming approach to dynamic stochastic matching. https://dx.doi.org/10.1287/ijoc.2021.0203.cd, https://github.com/INFORMSJoC/2021.0203.Google Scholar
• Zhang D, Adelman D (2009) An approximate dynamic programming approach to network revenue management with customer choice. Transportation Sci. 43(3):381–394.Link, Google Scholar
• Zhang L, Hu T, Min Y, Wu G, Zhang J, Feng P, Gong P, et al. (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
• Zhong Y, Wan Z, Shen Z (2020) Queueing vs. surge pricing mechanism: Efficiency, equity, and consumer welfare. Working paper, University of Chicago, Chicago.Google Scholar