Online Matching Frameworks Under Stochastic Rewards, Product Ranking, and Unknown Patience

References

• Adamczyk M, Grandoni F, Mukherjee J (2015) Improved approximation algorithms for stochastic matching. Bansal N, Finocchi I, eds. Algorithms – ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14–16 (Springer, Berlin), 1–12.Google Scholar
• Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia), 1253–1264.Google Scholar
• Alaei S, Hajiaghayi M, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proceedings of the 13th ACM Conference on Electronic Commerce (Association for Computing Machinery, New York), 18–35.Google Scholar
• Alijani R, Banerjee S, Gollapudi S, Munagala K, Wang K (2020) Predict and match: Prophet inequalities with uncertain supply. Proc. ACM Measurement Anal. Comput. Systems 4(1):1–23.Crossref, Google Scholar
• Aouad A, Saritaç Ö (2022) Dynamic stochastic matching under limited time. Oper. Res. 70(4):2349–2383.Link, Google Scholar
• Aveklouris A, DeValve L, Ward AR (2021) Matching impatient and heterogeneous demand and supply. Preprint, submitted February 4, https://doi.org/10.48550/arXiv.2102.02710.Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2010) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithms – ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6–8 (Springer, Berlin), 218–229.Google Scholar
• Borodin A, MacRury C, Rakheja A (2021) Secretary matching meets probing with commitment. Wootters M, Sanita L, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany), 13:1–13:23.Google Scholar
• Borodin A, MacRury C, Rakheja A (2022) Prophet matching in the probe-commit model. Chakrabarti A, Swamy C, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany), 46:1–46:24.Google Scholar
• Brubach B, Grammel N, Ma W, Srinivasan A (2021) Follow your star: New frameworks for online stochastic matching with known and unknown patience. Proc. Machine Learn. Res. 130:2872–2880.Google Scholar
• Brubach B, Sankararaman KA, Srinivasan A, Xu P (2017) Attenuate locally, win globally: An attenuation-based framework for online stochastic matching with timeouts. AAMAS ‘17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 1223–1231.Google Scholar
• Brubach B, Sankararaman KA, Srinivasan A, Xu P (2020) Online stochastic matching: New algorithms and bounds. Algorithmica 82(10):2737–2783.Crossref, Google Scholar
• Chen N, Li A, Yang S (2021) Revenue maximization and learning in products ranking. EC ‘21: Proceedings of the 22nd ACM Conference on Economics and Computation (Association for Computing Machinery, New York), 316–317.Google Scholar
• Cheung WC, Simchi-Levi D (2016) Efficiency and performance guarantees for choice-based network revenue management problems with flexible products. Preprint, submitted August 15, https://dx.doi.org/10.2139/ssrn.2823339.Google Scholar
• Cheung WC, Ma W, Simchi-Levi D, Wang X (2022) Inventory balancing with online learning. Management Sci. 68(3):1776–1807.Link, Google Scholar
• Derakhshan M, Golrezaei N, Manshadi V, Mirrokni V (2022) Product ranking on online platforms. Management Sci. 68(6):4024–4041.Link, Google Scholar
• Fata E, Ma W, Simchi-Levi D (2019) Multi-stage and multi-customer assortment optimization with inventory constraints. Preprint, submitted August 26, https://dx.doi.org/10.2139/ssrn.3443109.Google Scholar
• Feldman J, Segev D (2019) Improved approximation schemes for MNL-driven sequential assortment optimization. Preprint, submitted August 21, https://dx.doi.org/10.2139/ssrn.3440645.Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. Proceedings of the 50th Annual Symposium on Foundations of Computer Science (IEEE, New York), 117–126.Google Scholar
• Gamlath B, Kale S, Svensson O (2019) Beating greedy for stochastic bipartite matching. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ‘19) (Society for Applied and Industrial Mathematics, Philadelphia), 2841–2854.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 (2023) Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Oper. Res. 71(2):563–580.Link, Google Scholar
• Huang Z, Zhang Q (2020) Online primal dual meets online matching with stochastic rewards: Configuration lp to the rescue. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Association for Computing Machinery, New York), 1153–1164.Google Scholar
• Jiang J, Ma W, Zhang J (2022) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (SIAM, Philadelphia), 1221–1246.Google Scholar
• Kalyanasundaram B, Pruhs KR (2000) An optimal deterministic algorithm for online b-matching. Theoret. Comput. Sci. 233(1–2):319–325.Crossref, Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, New York), 352–358.Google Scholar
• Kempe D, Mahdian M (2008) A cascade model for externalities in sponsored search. Papadimitriou C, Zhang S, eds. International Workshop on Internet and Network Economics (Springer, Berlin), 585–596.Google Scholar
• Kerimov S, Ashlagi I, Gurvich I (2021) On the optimality of greedy policies in dynamic matching. Preprint, submitted September 6, https://dx.doi.org/10.2139/ssrn.3918497.Google Scholar
• Kessel K, Shameli A, Saberi A, Wajc D (2022) The stationary prophet inequality problem. Proceedings of the 23rd ACM Conference on Economics and Computation (Association for Computing Machinery, New York), 243–244.Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. (N.S.) 83(4):745–747.Crossref, Google Scholar
• Ma W (2018) Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms. Math. Oper. Res. 43(3):789–812.Link, 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
• 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
• Mehta A (2012) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. FOCS ‘12: Proceedings of the 2012 IEEE Annual Symposium on Foundations of Computer Science (IEEE, New York), 728–737.Google Scholar
• Mehta A, Waggoner B, Zadimoghaddam M (2015) Online stochastic matching with unequal probabilities. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia), 1388–1404.Google Scholar
• Purohit M, Gollapudi S, Raghavan M (2019) Hiring under uncertainty. Proc. Machine Learn. Res. 97:5181–5189.Google Scholar
• Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, Inc., Hoboken, NJ), 1–484.Google Scholar