Multiagent Assortment Optimization in Sequential Matching Markets

References

• [1] Adamczyk M (2011) Improved analysis of the greedy algorithm for stochastic matching. Inform. Processing Lett. 111(15):731–737.Crossref, Google Scholar
• [2] Ahmed A, Sohoni MG, Bandi C (2022) Parameterized approximations for the two-sided assortment optimization. Oper. Res. Lett. 50(4):399–406.Crossref, Google Scholar
• [3] Aouad A, Saban D (2023) Online assortment optimization for two-sided matching platforms. Management Sci. 69(4):2069–2087.Link, Google Scholar
• [4] Aouad A, Farias V, Levi R, Segev D (2018) The approximability of assortment optimization under ranking preferences. Oper. Res. 66(6):1661–1669.Link, Google Scholar
• [5] Arnosti N, Johari R, Kanoria Y (2021) Managing congestion in matching markets. Manufacturing Service Oper. Management 23(3):620–636.Link, Google Scholar
• [6] Ashlagi I, Braverman M, Kanoria Y, Shi P (2020) Clearing matching markets efficiently: Informative signals and match recommendations. Management Sci. 66(5):2163–2193.Link, Google Scholar
• [7] Ashlagi I, Krishnaswamy AK, Makhijani R, Saban D, Shiragur K (2022) Technical note—Assortment planning for two-sided sequential matching markets. Oper. Res. 70(5):2784–2803.Link, Google Scholar
• [8] Baltas G, Doyle P (2001) Random utility models in marketing research: A survey. J. Bus. Res. 51(2):115–125.Crossref, Google Scholar
• [9] Banerjee S, Johari R, Riquelme C (2015) Pricing in ride-sharing platforms: A queueing-theoretic approach. EC’15: Proc. 16th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 639.Google Scholar
• [10] Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63:733–762.Crossref, Google Scholar
• [11] Berbeglia G, Joret G (2020) Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments. Algorithmica 82(4):681–720.Crossref, Google Scholar
• [12] Besbes O, Castro F, Lobel I (2021) Surge pricing and its spatial supply response. Management Sci. 67(3):1350–1367.Link, Google Scholar
• [13] Bian AA, Buhmann JM, Krause A, Tschiatschek S (2017) Guarantees for greedy maximization of non-submodular functions with applications. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 70 (PMLR, New York), 498–507.Google Scholar
• [14] Blanchet J, Gallego G, Goyal V (2016) A Markov chain approximation to choice modeling. Oper. Res. 64(4):886–905.Link, Google Scholar
• [15] Bront JJM, Méndez-Díaz I, Vulcano G (2009) A column generation algorithm for choice-based network revenue management. Oper. Res. 57(3):769–784.Link, Google Scholar
• [16] Brubach B, Grammel N, Ma W, Srinivasan A (2021) Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. NIPS’21: Proc. 35th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 27184–27195.Google Scholar
• [17] Buchbinder N, Feldman M, Seffi J, Schwartz R (2015) A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5):1384–1402.Crossref, Google Scholar
• [18] 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
• [19] Chekuri C, Vondrak J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. Proc. 2010 IEEE 51st Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 575–584.Google Scholar
• [20] Chen L, Feldman M, Karbasi A (2018) Weakly submodular maximization beyond cardinality constraints: Does randomization help greedy? Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research (PMLR, New York), 804–813.Google Scholar
• [21] Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Automata, Languages Programming, ICALP 2009, Lecture Notes in Computer Science, vol. 5555 (Springer, Berlin, Heidelberg), 266–278.Google Scholar
• [22] Costello KP, Tetali P, Tripathi P (2012) Stochastic matching with commitment. Czumaj A, Mehlhorn K, Pitts A, Wattenhofer R, eds. Automata, Languages Programming, ICALP 2012, Lecture Notes in Computer Science, vol. 7391 (Springer, Berlin, Heidelberg), 822–833.Google Scholar
• [23] Das A, Kempe D (2011) Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. Getoor L, Scheffer T, eds. ICML’11: Proc. 28th Internat. Conf. Machine Learn. (Omnipress, Madison, WI), 1057–1064.Google Scholar
• [24] Davis JM, Gallego G, Topaloglu H (2014) Assortment optimization under variants of the nested logit model. Oper. Res. 62(2):250–273.Link, Google Scholar
• [25] Désir A, Goyal V, Zhang J (2022) Technical note—Capacitated assortment optimization: Hardness and approximation. Oper. Res. 70(2):893–904.Link, Google Scholar
• [26] Désir A, Goyal V, Segev D, Ye C (2020) Constrained assortment optimization under the Markov chain–based choice model. Management Sci. 66(2):698–721.Link, Google Scholar
• [27] El Housni O, Torrico A, Hennebelle U (2026) Two-sided assortment optimization: Adaptivity gaps and approximation algorithms, 2024. Oper. Res. Forthcoming.Google Scholar
• [28] Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. 2011 IEEE 52nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 570–579.Google Scholar
• [29] Feng Y, Niazadeh R, Saberi A (2024) Near-optimal Bayesian online assortment of reusable resources. Oper. Res. 72(5):1861–1873.Link, Google Scholar
• [30] Fradkin A (2015) Search frictions and the design of online marketplaces. Third Conf. Auctions Market Mechanisms Their Appl. (Association for Computing Machinery, New York).Google Scholar
• [31] Gallego G, Topaloglu H (2014) Constrained assortment optimization for the nested logit model. Management Sci. 60(10):2583–2601.Link, Google Scholar
• [32] Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics, International Series in Operations Research & Management Science, vol. 279 (Springer, New York).Crossref, Google Scholar
• [33] Gamlath B, Kale S, Svensso O (2019) Beating greedy for stochastic bipartite matching. SODA’19: Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2841–2854.Google Scholar
• [34] Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• [35] Gong X-Y, 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
• [36] 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
• [37] Halaburda H, Piskorski MJ, Yildirim P (2018) Competing by restricting choice: The case of search platforms. Management Sci. 64(8):3574–3594.Link, Google Scholar
• [38] Hikima Y, Akagi Y, Kim H, Kohjima M, Kurashima T, Toda H (2021) Integrated optimization of bipartite matching and its stochastic behavior: New formulation and approximation algorithm via min-cost flow optimization. Proc. AAAI Conf. Artificial Intelligence, vol. 35 (AAAI Press, Washington, DC), 3796–3805.Google Scholar
• [39] Horton JJ (2010) Online labor markets. Saberi A, ed. Internet Network Econom., WINE 2010, Lecture Notes in Computer Science, vol. 6484 (Springer, Berlin, Heidelberg), 515–522.Google Scholar
• [40] Horton JJ (2017) The effects of algorithmic labor market recommendations: Evidence from a field experiment. J. Labor Econom. 35(2):345–385.Crossref, Google Scholar
• [41] Immorlica N, Lucier B, Manshadi V, Wei A (2021) Designing approximately optimal search on matching platforms. EC’21: Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 632–633.Google Scholar
• [42] Jeloudar M, Lo I, Pollner T, Saberi A (2021) Decentralized matching in a probabilistic environment. EC’21: Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 635–653.Google Scholar
• [43] Kanoria Y, Saban D (2021) Facilitating the search for partners on matching platforms. Management Sci. 67(10):5990–6029.Link, Google Scholar
• [44] Kapralov M, Post I, Vondrák J (2013) Online submodular welfare maximization: Greedy is optimal. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1216–1225.Google Scholar
• [45] Khot S, Lipton RJ, Markakis E, Mehta A (2008) Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica 52:3–18.Crossref, Google Scholar
• [46] Kök AG, Fisher ML, Vaidyanathan R (2008) Assortment planning: Review of literature and industry practice. Agrawal N, Smith S, eds. Retail Supply Chain Management, International Series in Operations Research & Management Science, vol. 122 (Springer, Boston), 99–153.Crossref, Google Scholar
• [47] Kuhnle A (2019) Interlaced greedy algorithm for maximization of submodular functions in nearly linear time. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, eds. NIPS’19: Proc. 33rd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 2374–2384.Google Scholar
• [48] Lehmann B, Lehmann D, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2):270–296.Crossref, Google Scholar
• [49] Li J, Netessine S (2020) Higher market thickness reduces matching rate in online platforms: Evidence from a quasiexperiment. Management Sci. 66(1):271–289.Link, Google Scholar
• [50] Luce RD, Suppes P (1965) Preference, utility and subjective probability. Luce RD, Bush, RR, Galanter EH, eds. Handbook of Mathematical Psychology, vol. 3 (Wiley, New York), 249–410.Google Scholar
• [51] 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
• [52] Manshadi V, Rodilitz S (2022) Online policies for efficient volunteer crowdsourcing. Management Sci. 68(9):6572–6590.Link, Google Scholar
• [53] Manshadi V, Rodilitz S, Saban D, Suresh A (2025) Online algorithms for matching platforms with multichannel traffic. Management Sci. 71(9):7674–7691.Link, Google Scholar
• [54] McFadden D (1974) Conditional logit analysis of qualitative choice behavior. Zarembka P, ed. Frontiers in Econometrics (Academic Press, New York), 105–142.Google Scholar
• [55] Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. 2012 IEEE 53rd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 728–737.Google Scholar
• [56] Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. J. ACM 54(5):22-es.Crossref, Google Scholar
• [57] Rios I, Torrico A (2026) The dating heuristic: A provably strong matching algorithm for dating platforms. Manufacturing Service Oper. Management, ePub ahead of print March 27, https://doi.org/10.1287/msom.2024.1053.Link, Google Scholar
• [58] Rios I, Saban D, Zheng F (2023) Improving match rates in dating markets through assortment optimization. Manufacturing Service Oper. Management 25(4):1304–1323.Link, Google Scholar
• [59] Rochet J-C, Tirole J (2003) Platform competition in two-sided markets. J. Eur. Econom. Assoc. 1(4):990–1029.Crossref, Google Scholar
• [60] Rusmevichientong P, Shen Z-JM, Shmoys DB (2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Oper. Res. 58(6):1666–1680.Link, Google Scholar
• [61] Rusmevichientong P, Shmoys D, Tong C, Topaloglu H (2014) Assortment optimization under the multinomial logit model with random choice parameters. Production Oper. Management 23(11):2023–2039.Crossref, Google Scholar
• [62] Santiago R, Shepherd FB (2019) Multivariate submodular optimization. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 97 (PMLR, New York), 5599–5609.Google Scholar
• [63] Shi P (2023) Optimal matchmaking strategy in two-sided marketplaces. Management Sci. 69(3):1323–1340.Link, Google Scholar
• [64] Shi P (2025) Optimal match recommendations in two-sided marketplaces with endogenous prices. Management Sci. 71(9):7431–7448.Link, Google Scholar
• [65] Soma T, Yoshida Y (2018) Maximizing monotone submodular functions over the integer lattice. Math. Programming 172:539–563.Crossref, Google Scholar
• [66] Sumida M, Gallego G, Rusmevichientong P, Topaloglu H, Davis J (2021) Revenue-utility tradeoff in assortment optimization under the multinomial logit model with totally unimodular constraints. Management Sci. 67(5):2845–2869.Link, Google Scholar
• [67] Talluri K, Van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(1):15–33.Link, Google Scholar
• [68] Thurstone LL (1927) A law of comparative judgment. Psych. Rev. 34(4):273–286.Crossref, Google Scholar
• [69] Topaloglu H (2013) Joint stocking and product offer decisions under the multinomial logit model. Production Oper. Management 22(5):1182–1199.Crossref, Google Scholar
• [70] Vondrák J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. STOC’08: Proc. 40th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 67–74.Google Scholar
• [71] Williams HC (1977) On the formation of travel demand models and economic evaluation measures of user benefit. Environment Planning A 9(3):285–344.Crossref, Google Scholar