Optimality of Nonadaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes

References

• Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Randall D, ed. Proc. Twenty-Second Annual ACM-SIAM Sympos. Discrete Algorithms SODA 2011 (SIAM, Philadelphia), 1253–1264.Google Scholar
• Aouad A, Saban D (2023) Online assortment optimization for two-sided matching platforms. Management Sci. 69(4):2069–2087.Link, Google Scholar
• Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• Barrientos B, Freund D, Saban D (2025) Online matching and market imbalance. Preprint, submitted February 11, https://arxiv.org/abs/2502.07731.Google Scholar
• Borodin A, MacRury C, Rakheja A (2020) Greedy approaches to online stochastic matching. Preprint, submitted August 21, https://arxiv.org/abs/2008.09260v1.Google Scholar
• Borodin A, MacRury C, Rakheja A (2022) Prophet matching in the probe-commit model. Chakrabarti A, Swamy C, eds. Approximation Randomization Combinatorial Optim. Algorithms Techniques APPROX/RANDOM 2022, vol. 245 (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 46:1–46:24.Google Scholar
• Bradac D, Singla S, Zuzic G (2019) (Near) optimal adaptivity gaps for stochastic multi-value probing. Achlioptas D, Végh LA, eds. Approximation Randomization Combinatorial Optim. Algorithms Techniques APPROX/RANDOM 2019, vol. 145 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 49:1–49:21.Google Scholar
• Brubach B, Grammel N, Ma W, Srinivasan A (2025) Online matching frameworks under stochastic rewards, product ranking, and unknown patience. Oper. Res. 73(2):995–1010.Link, Google Scholar
• Buchbinder N, Feldman M, Schwartz R (2019) Online submodular maximization with preemption. ACM Trans. Algorithms 15(3):1–31.Crossref, Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Eur. Sympos. Algorithms (Springer, Berlin, Heidelberg), 253–264.Google Scholar
• Buchbinder N, Feldman M, Filmus Y, Garg M (2020) Online submodular maximization: Beating 1/2 made simple. Math. Programming 183(1):149–169.Crossref, Google Scholar
• Chan CW, Farias VF (2009) Stochastic depletion problems: Effective myopic policies for a class of dynamic optimization problems. Math. Oper. Res. 34(2):333–350.Link, Google Scholar
• Devanur NR, Jain K (2012) Online matching with concave returns. Proc. Forty-Fourth Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 137–144.Google Scholar
• Devanur NR, Jain K, Kleinberg RD (2013) Randomized primal-dual analysis of ranking for online bipartite matching. Proc. Twenty-Fourth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 101–107.Google Scholar
• Devanur NR, Huang Z, Korula N, Mirrokni VS, Yan Q (2016) Whole-page optimization and submodular welfare maximization with online bidders. ACM Trans. Econom. Comput. 4(3):14.Google Scholar
• El Housni O, Hennebelle U, Torrico A (2024) Two-sided assortment optimization: Adaptivity gaps and approximation algorithms. Preprint, submitted March 13, https://arxiv.org/abs/2403.08929v1.Google Scholar
• Feldman J, Korula N, Mirrokni V, Muthukrishnan S, Pál M (2009) Online ad assignment with free disposal. Internat. Workshop Internet Network Econom. (Springer, Berlin, Heidelberg), 374–385.Google Scholar
• Feng Y, Jiang PP, Tang W (2025) Simple delay-oblivious policies are robust: Overbooking with delayed purchases. Preprint, submitted February 23, https://doi.org/10.2139/ssrn.5150007.Google Scholar
• Ganz A, Nuti P, Schwartz R (2023) A tight competitive ratio for online submodular welfare maximization. Gørtz IL, Farach-Colton M, Puglisi SJ, Herman G, eds. 31st Annual Eur. Sympos. Algorithms ESA 2023, Leibniz International Proceedings in Informatics (LIPIcs), vol. 274 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 52:1–52:17.Google Scholar
• Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• Gong XY, Goyal V, Iyengar GN, Simchi-Levi D, Udwani R, Wang S (2022) Online assortment optimization with reusable resources. Management Sci. 68(7):4772–4785.Link, Google Scholar
• Goyal V, Iyengar G, Udwani R (2025) Asymptotically optimal competitive ratio for online allocation of reusable resources. Oper. Res. 73(4):1897–1915.Link, Google Scholar
• Harshaw C, Kazemi E, Feldman M, Karbasi A (2022) The power of subsampling in submodular maximization. Math. Oper. Res. 47(2):1365–1393.Link, Google Scholar
• Jagabathula S (2022) ML, AI and operations: A conversation with Srikanth Jagabathula. Podcast interview (March 29), https://srikanth-jagabathula.com/podcast-interview-ml-ai-and-operations-a-conversation-with-srikanth-jagabathula/.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
• Kapralov M, Post I, Vondrák J (2013) Online submodular welfare maximization: Greedy is optimal. Proc. Twenty-Fourth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1216–1225.Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. Twenty-Second Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 352–358.Google Scholar
• Korula N, Mirrokni V, Zadimoghaddam M (2015) Online submodular welfare maximization: Greedy beats 1/2 in random order. Proc. Forty-Seventh Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 889–898.Google Scholar
• Lehmann B, Lehmann D, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2):270–296.Crossref, Google Scholar
• Mehta A (2013) 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. Foundations Comput. Sci. FOCS 2012 IEEE 53rd Annual Sympos. (IEEE, Piscataway, NJ), 728–737.Google Scholar
• Mehta A, Waggoner B, Zadimoghaddam M (2015) Online stochastic matching with unequal probabilities. Proc. Twenty-Sixth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1388–1404.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
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14:265–294.Crossref, Google Scholar
• Singla S (2018) The price of information in combinatorial optimization. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2523–2532.Google Scholar
• Sumida M (2024) Dynamic resource allocation with recovering rewards under non-stationary arrivals. Preprint, submitted December 6, https://doi.org/10.2139/ssrn.5046898.Google Scholar
• Torrico A, Carvalho M, Lodi A (2023) Multi-agent assortment optimization in sequential matching markets. Preprint, submitted September 19, https://arxiv.org/abs/2006.04313v4.Google Scholar
• Udwani R (2024) When stochastic rewards reduce to deterministic rewards in online bipartite matching. 2024 Sympos. Simplicity Algorithms SOSA (SIAM, Philadelphia), 321–330.Google Scholar
• Udwani R (2025) Submodular order functions and assortment optimization. Management Sci. 71(1):202–218.Abstract, Google Scholar
• Vondrák J (2007) Submodularity in combinatorial optimization. Doctoral thesis, Charles University, Prague.Google Scholar