pith. sign in

arxiv: 2606.15501 · v2 · pith:W22UFSFZnew · submitted 2026-06-13 · 🧮 math.OC · cs.DS

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

Rad Niazadeh , Rajan Udwani This is my paper

Pith reviewed 2026-06-27 03:42 UTC · model grok-4.3

classification 🧮 math.OC cs.DS
keywords primal-dual methodsonline resource allocationconvex programmingcompetitive analysisKKT conditionsLP-free certificatesonline matchingassortment optimization
0
0 comments X

The pith

Solving regularized convex programs at each arrival yields dual certificates via KKT conditions for prior-free online resource allocation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops two complementary primal-dual frameworks for analyzing algorithms in adversarial online resource allocation. Part I shows that solving a regularized convex program upon each arrival balances the tradeoff between greediness and hedging, then produces a dual certificate from the KKT conditions. Part II supplies an LP-free certificate system that evaluates competitive ratios when stochastic outcomes make standard LP relaxations weak or intractable. These templates cover models such as online vertex-weighted bipartite matching, edge-weighted matching with free disposal, stochastic-reward matching, reusable resources, two-sided assortment optimization, configuration allocation, AdWords, and costly cancellations.

Core claim

The paper establishes that an LP-based convex-programming framework, in which a regularized convex program is solved at each arrival to capture the greediness-hedging tradeoff and to extract a dual certificate via KKT conditions, together with a complementary LP-free framework that supplies a universal certificate system, together provide versatile proof templates for competitive analysis across a wide array of prior-free online resource allocation models.

What carries the argument

The regularized convex program solved at each arrival, which encodes the greediness-hedging tradeoff and generates dual certificates through KKT conditions, together with the universal LP-free certificate system for stochastic settings.

If this is right

  • The frameworks supply proof templates that recover competitive ratios for online vertex-weighted bipartite matching.
  • They analyze edge-weighted online matching with free disposal and online matching with stochastic rewards.
  • They extend to reusable resources, two-sided assortment optimization, and whole-page configuration allocation.
  • They handle AdWords and models with costly cancellations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same certificate construction could be applied to newly arising online allocation problems that share the same arrival-and-decision structure.
  • The LP-free system may allow direct comparison of competitive ratios across models that previously required separate LP relaxations.
  • Algorithm designers could substitute the regularized convex program with simpler heuristics while retaining the same dual-certificate verification step.

Load-bearing premise

Standard LP relaxations can be weak or intractable when outcomes are stochastic.

What would settle it

The KKT-derived dual certificates fail to recover the known competitive ratio for online vertex-weighted bipartite matching.

read the original abstract

Linear-programming (LP)-based primal-dual methods are fundamental for designing and analyzing algorithms in adversarial (prior-free) online resource allocation. This chapter provides a tutorial on two modern primal-dual frameworks, emphasizing recent developments and contemporary models in operations research. Part~I develops an LP-based convex-programming framework where solving a regularized convex program at each arrival captures the tradeoff between greediness and hedging, yielding a dual certificate via Karush-Kuhn-Tucker (KKT) conditions. Because standard LP relaxations can be weak or intractable for stochastic outcomes, Part~II introduces a complementary LP-free framework that provides a universal certificate system for evaluating competitive ratios under such uncertainty. Covering a wide array of models -- including online vertex-weighted bipartite matching, edge-weighted online matching with free disposal, online matching with stochastic rewards, reusable resources, two-sided assortment optimization, configuration allocation (whole-page optimization), AdWords, and costly cancellations -- the tutorial equips readers with versatile proof templates to analyze existing algorithms and develop new solutions for emerging applications.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript is a tutorial presenting two primal-dual frameworks for prior-free online resource allocation. Part I develops an LP-based convex-programming approach in which a regularized convex program is solved upon each arrival to trade off greediness against hedging, with dual certificates obtained from the KKT conditions. Part II introduces a complementary LP-free certificate system intended to evaluate competitive ratios when stochastic outcomes render standard LP relaxations weak or intractable. The frameworks are positioned as proof templates and are illustrated on models including online vertex-weighted bipartite matching, edge-weighted matching with free disposal, stochastic-reward matching, reusable resources, two-sided assortment optimization, configuration allocation, AdWords, and costly cancellations.

Significance. If the templates are correctly derived and the KKT and LP-free certificates are shown to be tight for the listed models, the tutorial would supply reusable analysis tools for a broad class of online allocation problems. The explicit separation of the convex-programming and LP-free routes, together with the coverage of both adversarial and stochastic settings, would constitute a useful reference for researchers working on competitive analysis in operations research.

major comments (2)
  1. [Part II] Part II: the claim that the LP-free framework supplies a 'universal certificate system' for stochastic outcomes is load-bearing for the motivation of the second half of the tutorial. A precise definition of universality (i.e., the class of uncertainty models and competitive-ratio bounds to which the certificates apply without further assumptions) together with a statement of the conditions under which the certificates remain valid must be supplied; the current motivation paragraph does not constitute such a statement.
  2. [online matching with stochastic rewards] § on online matching with stochastic rewards (or the corresponding subsection in Part I): the derivation of the dual certificate via KKT conditions for the regularized program must be checked against the stochastic reward distribution; if the regularization parameter is chosen independently of the reward probabilities, the resulting competitive ratio may degrade, and this dependence (or lack thereof) should be stated explicitly.
minor comments (3)
  1. [Abstract] The abstract refers to 'this chapter'; the manuscript should clarify whether it is intended as a standalone journal article or as a book chapter, and adjust the title and front matter accordingly.
  2. Notation for the regularized convex program (objective, feasible set, and dual variables) should be introduced once in a dedicated preliminary section and then used uniformly across all models; repeated re-definition of the same symbols in each application section reduces readability.
  3. All cited competitive-ratio bounds should be accompanied by a short table or list that records the ratio achieved by the template versus the best known ratio in the literature, so that readers can immediately assess the tightness of the new certificates.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation of the tutorial and for the constructive major comments. We address each point below and will revise the manuscript accordingly to strengthen the presentation.

read point-by-point responses

  1. Referee: [Part II] Part II: the claim that the LP-free framework supplies a 'universal certificate system' for stochastic outcomes is load-bearing for the motivation of the second half of the tutorial. A precise definition of universality (i.e., the class of uncertainty models and competitive-ratio bounds to which the certificates apply without further assumptions) together with a statement of the conditions under which the certificates remain valid must be supplied; the current motivation paragraph does not constitute such a statement.

    Authors: We agree that the motivation paragraph alone is insufficient to support the universality claim. In the revised manuscript we will insert a precise definition immediately following the motivation paragraph in Part II. The definition will state that the LP-free certificates apply to uncertainty models consisting of adversarial arrivals whose stochastic attributes (rewards, usage durations, or acceptance probabilities) are drawn independently from known distributions; the certificates yield competitive ratios with respect to the expected value of the optimal offline solution, provided the per-arrival certificate inequality holds in expectation and no further correlation or support assumptions are imposed beyond those already used in the listed applications. revision: yes

  2. Referee: [online matching with stochastic rewards] § on online matching with stochastic rewards (or the corresponding subsection in Part I): the derivation of the dual certificate via KKT conditions for the regularized program must be checked against the stochastic reward distribution; if the regularization parameter is chosen independently of the reward probabilities, the resulting competitive ratio may degrade, and this dependence (or lack thereof) should be stated explicitly.

    Authors: We have re-examined the KKT derivation in the stochastic-rewards subsection. The regularization parameter is deliberately chosen independently of the reward probabilities so that the algorithm remains prior-free. The resulting dual certificate is taken in expectation over the stochastic rewards; the analysis shows that the competitive ratio is preserved uniformly and does not degrade with the particular probability values. We will add an explicit sentence in the subsection stating this independence and confirming that the ratio bound holds for any reward distribution (subject only to the normalization already assumed in the model). revision: yes

Circularity Check

0 steps flagged

No significant circularity; tutorial presents independent frameworks

full rationale

The manuscript is a tutorial on two primal-dual frameworks for online allocation. Part I applies standard regularized convex programs and KKT conditions to obtain dual certificates; Part II supplies an LP-free certificate system motivated by known limitations of LP relaxations under stochastic outcomes. No equation reduces a claimed prediction or certificate to a fitted parameter or self-defined quantity. No load-bearing uniqueness theorem or ansatz is imported via self-citation. The frameworks are presented as reusable analysis templates for listed models, with all core steps relying on external convex optimization theory rather than internal re-derivation. This is the expected non-finding for an expository paper whose central contribution is organization of existing techniques.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The tutorial relies on standard optimization theory such as KKT conditions and convex programming; no free parameters, ad-hoc axioms, or invented entities are apparent from the abstract.

axioms (1)
  • standard math KKT conditions yield valid dual certificates for the regularized convex program
    Invoked for the LP-based framework in Part I

pith-pipeline@v0.9.1-grok · 5707 in / 1187 out tokens · 50344 ms · 2026-06-27T03:42:58.027080+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references

  1. [1]

    Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations.Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1253–1264

    2011

  2. [2]

    Aouad A, Saban D (2023) Online assortment optimization for two-sided matching platforms.Management Science 69(4):2069–2087

    2023

  3. [3]

    Borodin A, El-Yaniv R (2005)Online Computation and Competitive Analysis(Cambridge University Press)

    2005

  4. [4]

    Algorithms and Techniques (APPROX/RANDOM 2022), 46–1 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik)

    Borodin A, MacRury C, Rakheja A (2022) Prophet matching in the probe-commit model.Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), 46–1 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik)

    2022

  5. [5]

    Brubach B, Grammel N, Ma W, Srinivasan A (2025) Online matching frameworks under stochastic rewards, product ranking, and unknown patience.Operations Research73(2):995–1010

    2025

  6. [6]

    Buchbinder N, Jain K, Naor J (2007) Online primal-dual algorithms for maximizing ad-auctions revenue.European Symposium on Algorithms, 253–264

    2007

  7. [7]

    Buchbinder N, Naor J (2009) The design of competitive online algorithms via a primal—dual approach.Founda- tions and Trends® in Theoretical Computer Science3(2-3):93–263

    2009

  8. [8]

    Chan CW, Farias VF (2009) Stochastic depletion problems: Effective myopic policies for a class of dynamic optimization problems.Mathematics of Operations Research34(2):333–350

    2009

  9. [9]

    Mathematics of Operations Research49(3)

    Delong S, Farhadi A, Niazadeh R, Sivan B, Udwani R (2024) Online bipartite matching with reusable resources. Mathematics of Operations Research49(3)

    2024

  10. [10]

    Devanur NR, Huang Z, Korula N, Mirrokni V , Yan Q (2016) Whole-page optimization and submodular welfare maximization with online bidders.ACM Transactions on Economics and Computation4(3):14:1–14:20

    2016

  11. [11]

    Devanur NR, Jain K, Kleinberg RD (2013) Randomized primal-dual analysis of Ranking for online bipartite matching.Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 101–107

    2013

  12. [12]

    Ekbatani F, Feng Y , Niazadeh R (2023) Online resource allocation with buyback: Optimal algorithms via primal- dual.Proceedings of the 24th ACM Conference on Economics and Computation, 583

    2023

  13. [13]

    International Workshop on Internet and Network Economics, 374–385

    Feldman J, Korula N, Mirrokni V , Muthukrishnan S, Pal M (2009) Online ad assignment with free disposal. International Workshop on Internet and Network Economics, 374–385

    2009

  14. [14]

    Available at SSRN: https://ssrn.com/abstract=5150007

    Feng Y , Jiang PP, Tang W (2025) Simple delay-oblivious policies are robust: Overbooking with delayed purchases. Available at SSRN: https://ssrn.com/abstract=5150007

    2025

  15. [15]

    Feng Y , Niazadeh R (2025) Batching and optimal multistage bipartite allocations.Management Science71(5):4108– 4130

    2025

  16. [16]

    Available at SSRN 3795056

    Feng Y , Niazadeh R, Saberi A (2021) Robustness of online inventory balancing algorithm to inventory shocks. Available at SSRN 3795056. Niazadeh and Udwani:Primal-Dual for Prior-Free Online Resource Allocation 34 Article submitted toTutORials in Operations Research

    2021

  17. [17]

    Operations Research72(4):1574–1594

    Feng Y , Niazadeh R, Saberi A (2024) Two-stage stochastic matching and pricing with applications to ride hailing. Operations Research72(4):1574–1594

    2024

  18. [18]

    Management Science60(6):1532–1551

    Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Science60(6):1532–1551

    2014

  19. [19]

    Gong XY , Goyal V , Iyengar GN, Simchi-Levi D, Udwani R, Wang S (2022) Online assortment optimization with reusable resources.Management Science68(7):4772–4785

    2022

  20. [20]

    Goyal V , Iyengar G, Udwani R (2025) Asymptotically optimal competitive ratio for online allocation of reusable resources.Operations Research73(4):1897–1915

    2025

  21. [21]

    Operations Research (Forthcoming)

    Goyal V , Iyengar G, Udwani R (2026) Pricing a finite inventory of substitutable products with show-all constraint. Operations Research (Forthcoming)

    2026

  22. [22]

    Goyal V , Udwani R (2023) Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation.Operations Research71(2):563–580

    2023

  23. [23]

    Huang Z, Jiang H, Shen A, Song J, Wu Z, Zhang Q (2023) Online matching with stochastic rewards: Advanced analyses using configuration linear programs.International Conference on Web and Internet Economics, 384–401 (Springer)

    2023

  24. [24]

    Huang Z, Tang ZG, Wajc D (2024) Online matching: A brief survey.ACM SIGecom Exchanges22(1):135–158

    2024

  25. [25]

    Huang Z, Zhang Q (2024) Online primal dual meets online matching with stochastic rewards: Configuration lp to the rescue.SIAM Journal on Computing53(5):1217–1256

    2024

  26. [26]

    Jin B, Ma W (2022) Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model.Advances in Neural Information Processing Systems35:14555–14567

    2022

  27. [27]

    Kalyanasundaram B, Pruhs KR (2000) An optimal deterministic algorithm for online b-matching.Theoretical Computer Science233(1–2):319–325

    2000

  28. [28]

    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, 352–358

    1990

  29. [29]

    Manshadi V , Rodilitz S, Saban D, Suresh A (2025) Online algorithms for matching platforms with multichannel traffic.Management Science71(9):7674–7691

    2025

  30. [30]

    Mehta A (2013) Online matching and ad allocation.Foundations and Trends in Theoretical Computer Science 8(4):265–368

    2013

  31. [31]

    Mehta A, Panigrahi D (2012) Online matching with stochastic rewards.2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 728–737

    2012

  32. [32]

    Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching.Journal of the ACM54(5):22:1–22:19

    2007

  33. [33]

    Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 1388–1404

    Mehta A, Waggoner B, Zadimoghaddam M (2014) Online stochastic matching with unequal probabilities. Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 1388–1404. Niazadeh and Udwani:Primal-Dual for Prior-Free Online Resource Allocation Article submitted toTutORials in Operations Research35

    2014

  34. [34]

    Udwani R (2024) When stochastic rewards reduce to deterministic rewards in online bipartite matching.2024 Symposium on Simplicity in Algorithms (SOSA), 321–330 (SIAM)

    2024

  35. [35]

    Udwani R (2025) AdWords with unknown budgets and beyond.Management Science71(2):1009–1026

    2025

  36. [36]

    Udwani R (2025) Optimality of non-adaptive algorithms in online submodular welfare maximization with stochastic outcomes.Proceedings of the 26th ACM Conference on Economics and Computation, 1–1

    2025

  37. [37]

    e-companion toNiazadeh and Udwani:Primal-Dual for Prior-Free Online Resource Allocationec1 This page is intentionally blank

    Wright SJ (2015) Coordinate descent algorithms.Mathematical programming151(1):3–34. e-companion toNiazadeh and Udwani:Primal-Dual for Prior-Free Online Resource Allocationec1 This page is intentionally blank. Proper e-companion title page, with INFORMS branding and exact metadata of the main paper, will be produced by the INFORMS office when the issue is ...

    2015

  38. [38]

    Batch arrival.We study the K-stage arrival model, introduce the stage-dependent polynomial regularizers that yield the optimal factor Γ(K) = 1−(1−1/K) K, and record the recursive dual-fitting argument that replaces the scalar identity from the fully online setting (Section EC.2 and Section EC.5)

  39. [39]

    Configuration allocation / whole-page optimization.We move from scalar or reward-indexed states to a price-level state vector and show how direct convex duality replaces the support-graph decomposition that was available in matching (Section EC.3 and Section EC.6)

  40. [40]

    The emphasis is on reusability of the main ideas rather than on developing a separate proof for every variant (Section EC.4)

    Other extensions.We explain how the same template specializes to AdWords, costly cancellations, and several nearby allocation models. The emphasis is on reusability of the main ideas rather than on developing a separate proof for every variant (Section EC.4). The companion is therefore meant to be read in two ways. A first pass can follow only the model s...

  41. [41]

    The state remains the offline load vector, but it is updated stage by stage rather than arrival by arrival

  42. [42]

    The regularizer is stage dependent: the stage-kprogram usesF k rather than a single functionF

  43. [43]

    matchability level

    The KKT conditions are now written for an entire batch. As a result, the relevant structure is no longer the one-arrival water-filling picture, but a decomposition of the positive-support graph of the batch. The conceptual message is unchanged: the regularizer determines the online rule, and the KKT system determines the dual update. EC.2.2. Stage-depende...

  44. [44]

    In configuration allocation, advertiser j may value different user–configuration pairs at very different prices

    Multiple price levels.In matching, all mass assigned to a fixed offline node has the same value. In configuration allocation, advertiser j may value different user–configuration pairs at very different prices. ec6e-companion toNiazadeh and Udwani:Primal-Dual for Prior-Free Online Resource Allocation

  45. [45]

    Here an advertiser may be tight at some price thresholds and slack at others, so a graph-only description no longer captures the relevant structure

    No useful graph decomposition.In batch matching, the KKT system induced a graph decomposition of the positive-support edges. Here an advertiser may be tight at some price thresholds and slack at others, so a graph-only description no longer captures the relevant structure

  46. [46]

    These are precisely the reasons the analysis moves from combinatorial structure to direct convex duality

    Allocation and preemption are coupled.At each stage, the algorithm must decide not only what new mass to keep, but also which previously retained mass to discard. These are precisely the reasons the analysis moves from combinatorial structure to direct convex duality. EC.3.2. State, stage program, and interpretation of the variables Assume there is a fini...

  47. [47]

    Dual construction:use the Lagrangian dual of the stage program directly rather than a graph decomposi- tion

  48. [48]

    choose one configuration from a feasible family,

    Scalar inequality:apply the same one-dimensional recursion from batch arrival, now threshold by threshold. The next two subsections make these points precise (with proofs and details in Section EC.6). ec8e-companion toNiazadeh and Udwani:Primal-Dual for Prior-Free Online Resource Allocation EC.3.5. Structural lemmas from convex duality The first lemma rec...