Help
Cart
Skip main navigation

Modern Primal–Dual Frameworks for Prior-Free Online Resource Allocation

Published Online:1 Nov 2026https://doi.org/10.1287/educ.2026.0304
Acknowledgments

The authors are grateful to the editorial team and anonymous reviewers for their insightful and constructive feedback.

Endnotes

1 This is a prior-free setting in which no assumptions are made about how demand requests arrive over time.

2 All results can be extended to randomized integral allocations under “large-budget” assumptions by using standard randomized rounding algorithms and concentration inequalities; see Feng and Niazadeh [14] for an example.

3 This normalization is without loss because one can replace each offline vertex with integer capacity by that many identical unit-capacity copies for our analysis of integral algorithms. In the case of fractional allocations, this is again without loss of generality, as one can reduce the problem with arbitrary capacities to unit capacity by normalization and change of variables.

4 In the stochastic-rewards model, we may assume a complete graph without loss of generality by setting ptj=0 for absent edges.

5 Equivalently, each offline vertex can be successfully matched multiple times but yields its reward at most once, upon its first successful match. The algorithms considered in this tutorial never attempt to match an unavailable resource, though this need not hold for policies that are oblivious to stochastic realizations (e.g., Udwani [36]).

6 In the matching warm-up, this yields the functional equation 1−f(y)+F(y)=Γ; in the edge-weighted model with free disposal, the same identity is applied pointwise in the reward coordinate; and in the batch-arrival model, it becomes a stage-wise functional recursion.

7 In this section of the tutorial, we study only fractional algorithms, which are without loss of generality deterministic.

8 In fact, the continuous water-filling process is not a combinatorial algorithm; in fact, it is equivalent to running a particular first-order method (coordinate ascent; Wright [37]) to solve the arrival-wise concave program.

9 When the current time is clear from the context, we write yj(·) and Yj(·) instead of their time-dependent forms yjt(·) and Yjt(·).

References

  • [1] G. Aggarwal, G. Goel, C. Karande, and A. Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, 1253–1264, 2011.Google Scholar
  • [2] A. Aouad and D. Saban. Online assortment optimization for two-sided matching platforms. Management Science 69(4):2069–2087, 2023.Link, Google Scholar
  • [3] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, UK, 2005.Google Scholar
  • [4] A. Borodin, C. MacRury, and A. Rakheja. Prophet matching in the probe-commit model. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany, 46:1–46:24, 2022.Google Scholar
  • [5] B. Brubach, N. Grammel, W. Ma, and A. Srinivasan. Online matching frameworks under stochastic rewards, product ranking, and unknown patience. Operations Research 73(2):995–1010, 2025.Link, Google Scholar
  • [6] N. Buchbinder and J. Naor. The design of competitive online algorithms via a primal—Dual approach. Foundations and Trends in Theoretical Computer Science 3(2–3):93–263, 2009. Crossref, Google Scholar
  • [7] N. Buchbinder, K. Jain, and J. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. European Symposium on Algorithms. Springer, Berlin, 253–264, 2007.Google Scholar
  • [8] C. W. Chan and V. F. Farias. Stochastic depletion problems: Effective myopic policies for a class of dynamic optimization problems. Mathematics of Operations Research 34(2):333–350, 2009.Link, Google Scholar
  • [9] S. Delong, A. Farhadi, R. Niazadeh, B. Sivan, and R. Udwani. Online bipartite matching with reusable resources. Mathematics of Operations Research 49(3):1825–1854, 2024. Link, Google Scholar
  • [10] N. R. Devanur, K. Jain, and R. D. Kleinberg. Randomized primal-dual analysis of RANKING for online bipartite matching. Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, 101–107, 2013.Google Scholar
  • [11] N. R. Devanur, Z. Huang, N. Korula, V. Mirrokni, and Q. Yan. Whole-page optimization and submodular welfare maximization with online bidders. ACM Transactions on Economics and Computation 4(3):14, 2016.Crossref, Google Scholar
  • [12] F. Ekbatani, Y. Feng, and R. Niazadeh. Online resource allocation with buyback: Optimal algorithms via primal-dual. Proceedings of the 24th ACM Conference on Economics and Computation. Association for Computing Machinery, New York, 583, 2023.Google Scholar
  • [13] J. Feldman, N. Korula, V. Mirrokni, S. Muthukrishnan, and M. Pal. Online ad assignment with free disposal. International Workshop on Internet and Network Economics. Springer, Berlin, 374–385, 2009.Crossref, Google Scholar
  • [14] Y. Feng and R. Niazadeh. Batching and optimal multistage bipartite allocations. Management Science 71(5):4108–4130, 2025.Link, Google Scholar
  • [15] Y. Feng, P. P. Jiang, and W. Tang. Simple delay-oblivious policies are robust: Overbooking with delayed purchases. Preprint, submitted February 25, https://doi.org/10.2139/ssrn.5150007, 2025.Google Scholar
  • [16] Y. Feng, R. Niazadeh, and A. Saberi. Robustness of online inventory balancing algorithm to inventory shocks. Preprint, submitted March 2, https://doi.org/10.2139/ssrn.3795056, 2021.Google Scholar
  • [17] Y. Feng, R. Niazadeh, and A. Saberi. Two-stage stochastic matching and pricing with applications to ride hailing. Operations Research 72(4):1574–1594, 2024.Link, Google Scholar
  • [18] N. Golrezaei, H. Nazerzadeh, and P. Rusmevichientong. Real-time optimization of personalized assortments. Management Science 60(6):1532–1551, 2014.Link, Google Scholar
  • [19] X. Y. Gong, V. Goyal, G. N. Iyengar, D. Simchi-Levi, R. Udwani, and S. Wang. Online assortment optimization with reusable resources. Management Science 68(7):4772–4785, 2022.Link, Google Scholar
  • [20] V. Goyal and R. Udwani. Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Operations Research 71(2):563–580, 2023.Link, Google Scholar
  • [21] V. Goyal, G. Iyengar, and R. Udwani. Asymptotically optimal competitive ratio for online allocation of reusable resources. Operations Research 73(4):1897–1915, 2025.Link, Google Scholar
  • [22] V. Goyal, G. Iyengar, and R. Udwani. Pricing a finite inventory of substitutable products with show-all constraint. Operations Research, ePub ahead of print June 3, https://doi.org/10.1287/opre.2022.0479, 2026.Link, Google Scholar
  • [23] Z. Huang and Q. Zhang. Online primal dual meets online matching with stochastic rewards: Configuration LP to the rescue. SIAM Journal on Computing 53(5):1217–1256, 2024.Crossref, Google Scholar
  • [24] Z. Huang, Z. G. Tang, and D. Wajc. Online matching: A brief survey. ACM SIGecom Exchanges 22(1):135–158, 2024.Crossref, Google Scholar
  • [25] Z. Huang, H. Jiang, A. Shen, J. Song, Z. Wu, and Q. Zhang. Online matching with stochastic rewards: Advanced analyses using configuration linear programs. International Conference on Web and Internet Economics. Springer, Cham, Switzerland, 384–401, 2023.Google Scholar
  • [26] B. Jin and W. Ma. Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model. S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, eds. Advances in Neural Information Processing Systems, vol. 35. Curran Associates, Red Hook, NY, 14555–14567, 2022.Crossref, Google Scholar
  • [27] B. Kalyanasundaram and K. R. Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science 233(1–2):319–325, 2000.Crossref, Google Scholar
  • [28] R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, New York, 352–358, 1990.Google Scholar
  • [29] V. Manshadi, S. Rodilitz, D. Saban, and A. Suresh. Online algorithms for matching platforms with multichannel traffic. Management Science 71(9):7674–7691, 2025.Link, Google Scholar
  • [30] A. Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science 8(4):265–368, 2013.Crossref, Google Scholar
  • [31] A. Mehta and D. Panigrahi. Online matching with stochastic rewards. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers, Piscataway, NJ, 728–737, 2012.Google Scholar
  • [32] A. Mehta, B. Waggoner, and M. Zadimoghaddam. Online stochastic matching with unequal probabilities. Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, 1388–1404, 2014.Google Scholar
  • [33] A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. AdWords and generalized online matching. Journal of the ACM 54(5):22:1–22:19, 2007.Crossref, Google Scholar
  • [34] R. Udwani. When stochastic rewards reduce to deterministic rewards in online bipartite matching. 2024 Symposium on Simplicity in Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, 321–330, 2024.Google Scholar
  • [35] R. Udwani. AdWords with unknown budgets and beyond. Management Science 71(2):1009–1026, 2025a.Link, Google Scholar
  • [36] R. Udwani. Optimality of non-adaptive algorithms in online submodular welfare maximization with stochastic outcomes. Proceedings of the 26th ACM Conference on Economics and Computation. Association for Computing Machinery, New York, 1, 2025b.Google Scholar
  • [37] S. J. Wright. Coordinate descent algorithms. Mathematical Programming 151(1):3–34, 2015.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree