A Modern Treatment of the Primal-Dual Framework
for Online Resource Allocation
Rad Niazadeh (The University of Chicago Booth School of Business)
Embedded Files
A Modern Treatment of the Primal-Dual Framework
This is an EC 2025 tutorial that will take place virtually on Tuesday, June 17, 2025, from 11 am-1:30 pm EST.
Registration is free but mandatory. Please use this form for registration.
This is an EC 2025 tutorial that will take place virtually on Tuesday, June 17, 2025, from 11 am-1:30 pm EST.
Registration is free but mandatory. Please use this form for registration.
Brief description: Linear programming (LP)-based primal-dual methods are widely used for designing and analyzing online algorithms, especially in online matching and resource allocation problems. Despite their importance, these methods often appear complex and scattered across various research papers. In this tutorial, we provide a simple and modern perspective that unifies many existing results and clearly demonstrates how to extend primal-dual techniques to new, more complicated problems. In particular, we demonstrate recent (i) convex programming-based and (ii) LP-free analysis approaches through various applications.
Tutorial Speakers
Tutorial Speakers
Rad Niazadeh is an Assistant Professor of Operations Management and Asness Junior Faculty Fellow at The University of Chicago Booth School of Business. He is also a faculty member at Toyota Technological Institute of Chicago (TTIC) by a courtesy appointment. Rad primarily studies online algorithms, online learning, and mechanism design, with applications in online platforms and non-profit operations. Rad has received several awards for his research, including the INFORMS Auctions and Market Design Rothkopf Junior Researcher Paper Award, the INFORMS Revenue Management and Pricing Dissertation Award (honorable mention), IJCAI 2024 Distinguished Paper Award, MSOM Best Student Paper (first place), Service Science Best Student Paper (third place), and the Google PhD Fellowship (in Market Algorithms). Prior to joining Chicago Booth, he was a postdoctoral researcher at Google Research and Stanford University CS department. He holds a B.Sc. in Electrical Engineering from Sharif University and a PhD in Computer Science from Cornell University.
Rajan is an Assistant Professor of Industrial Engineering and Operations Research at UC Berkeley. He works on algorithms for optimization under uncertainty with a focus on revenue management and pricing. His work has been recognized by various INFORMS junior faculty and student paper awards. His research is supported by an NSF CAREER award and by an award from the Google Research Scholar Program. Prior to joining UC Berkeley, he was a postdoctoral researcher at Columbia University. He holds a B.Tech. in Electrical Engineering from IIT Bombay and a PhD in Operations Research from MIT.
Tutorial Schedule
Tutorial Schedule
Part I: Convex programming-based Primal-dual Framework by Rad Niazadeh (70 mins, 11:00am-12:10 pm EST)
A new perspective on online fractional matching and resource allocation using convex programming
Applications and new results
[10 minutes break]
Part II: LP-free Primal-dual Framework by Rajan Udwani (70 mins; 12:20pm-1:30 pm EST)
A framework for analyzing algorithms in settings with post-allocation stochasticity
Applications and new results
Target audience: Everyone in the EC community (both researchers and students) interested in conducting research on the theory and practice of online algorithms, especially related to resource allocation. We recommend that the attendee have basic knowledge of LP duality, convex programming, and probability at the level of a graduate course.
Main References
Main References
Feng, Yiding, Rad Niazadeh, and Amin Saberi. "Two-stage stochastic matching and pricing with applications to ride hailing." Operations Research 72.4 (2024): 1574-1594.
Feng, Yiding, and Rad Niazadeh. "Batching and optimal multistage bipartite allocations." Management Science (2024).
Goyal, Vineet, and Rajan Udwani. "Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation." Operations Research 71.2 (2023): 563-580.
Goyal, Vineet, Garud Iyengar, and Rajan Udwani. "Asymptotically optimal competitive ratio for online allocation of reusable resources." Operations Research (2025).
Some Additional References
Some Additional References
Karp, Richard M., Umesh V. Vazirani, and Vijay V. Vazirani. "An optimal algorithm for on-line bipartite matching." Proceedings of the twenty-second annual ACM symposium on Theory of computing. 1990.
Devanur, Nikhil R., Kamal Jain, and Robert D. Kleinberg. "Randomized primal-dual analysis of ranking for online bipartite matching." Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2013.
Mehta, A., Saberi, A., Vazirani, U., & Vazirani, V. (2007). "Adwords and generalized online matching." Journal of the ACM (JACM) 54.5 (2007): 22-es.
Buchbinder, Niv, Kamal Jain, and Joseph Naor. "Online primal-dual algorithms for maximizing ad-auctions revenue." European Symposium on Algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007.
Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., & Pál, M. "Online ad assignment with free disposal." International workshop on internet and network economics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009.
Devanur, N. R., Huang, Z., Korula, N., Mirrokni, V. S., & Yan, Q. "Whole-page optimization and submodular welfare maximization with online bidders." ACM Transactions on Economics and Computation (TEAC) 4.3 (2016): 1-20.
Ekbatani, Farbod, Yiding Feng, and Rad Niazadeh. "Online resource allocation with buyback: Optimal algorithms via primal-dual." Proceedings of the 24th ACM Conference on Economics and Computation. 2023.
Mehta, Aranyak, and Debmalya Panigrahi. "Online matching with stochastic rewards." 2012 IEEE 53rd annual symposium on foundations of computer science. IEEE, 2012.
Mehta, Aranyak, Bo Waggoner, and Morteza Zadimoghaddam. "Online stochastic matching with unequal probabilities." Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.
Golrezaei, Negin, Hamid Nazerzadeh, and Paat Rusmevichientong. "Real-time optimization of personalized assortments." Management Science 60.6 (2014): 1532-1551.
Gong, X. Y., Goyal, V., Iyengar, G. N., Simchi-Levi, D., Udwani, R., & Wang, S. "Online assortment optimization with reusable resources." Management Science 68.7 (2022): 4772-4785.
Feng, Yiding, Rad Niazadeh, and Amin Saberi. "Robustness of online inventory balancing algorithm to inventory shocks." Available at SSRN 3795056 (2021).
Manshadi, V., Rodilitz, S., Saban, D., & Suresh, A. "Online algorithms for matching platforms with multi-channel traffic." Proceedings of the 23rd ACM Conference on Economics and Computation. 2022.
Udwani, Rajan. "Adwords with unknown budgets and beyond." Management Science 71.2 (2025): 1009-1026.
Aouad, Ali, and Daniela Saban. "Online assortment optimization for two-sided matching platforms." Management Science 69.4 (2023): 2069-2087.
Goyal, Vineet, Garud Iyengar, and Rajan Udwani. "Pricing a Finite Inventory of Substitutable Products with Show-All Constraint." Available at SSRN 4055722 (2022).
Feng, Yiding and Jiang, Puping (Phil) and Tang, Wei, "Simple Delay-Oblivious Policies Are Robust: Overbooking with Delayed Purchases." (February 23, 2025). Available at SSRN.
Eden, A., Feldman, M., Fiat, A., & Segal, K. "An Economics-Based Analysis of RANKING for Online Bipartite Matching∗." Symposium on Simplicity in Algorithms (SOSA). Society for Industrial and Applied Mathematics, 2021.
Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. "Online matching: A brief survey."
Mehta, Aranyak. "Online matching and ad allocation." Foundations and Trends® in Theoretical Computer Science 8.4 (2013): 265-368.
Brubach, B., Grammel, N., Ma, W., & Srinivasan, A. (2025). "Online matching frameworks under stochastic rewards, product ranking, and unknown patience." Operations Research, 73(2), 995-1010.
Borodin, Allan, Calum MacRury, and Akash Rakheja. "Prophet matching in the probe-commit model." Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022).
Delong, S., Farhadi, A., Niazadeh, R., Sivan, B., & Udwani, R. (2024). Online Bipartite Matching with Reusable Resources. Mathematics of Operations Research, 49(3), 1825-1854.
Page updated
Report abuse