A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
Data-Based Dynamic Pricing and Inventory Control with Censored Demand and Limited Price Changes 2: Any Policy with at Most m Price Changes Has Regret at Least KT^(1/(m+1)) on a Bernoulli InstanceResearch Paper
A seller learning a demand curve normally adjusts prices as new observations arrive. A price-change limit prevents that continual adjustment: a price may have to be chosen before the seller knows which demand curve it faces, then held through a block of sales. This matters when repricing is operationally costly, constrained by contracts, or visible to…
Optimization-Based Scenario Reduction for Data-Driven Two-Stage Stochastic Optimization II: Under a Symmetric Uncertainty Law the Mean Solves the Convex Upper-Bound Scenario ProblemResearch Paper
A two-stage stochastic programme chooses a decision z before an uncertain parameter ξ is revealed and pays a cost c(z;ξ). When ξ is known only through n data points, or through a law with many atoms, the expected cost is expensive to optimize, and practitioners replace the law by a small set of mreduced scenarios. Classical scenario reduction chooses…
Robust Dynamic Pricing with Strategic Customers: Over Horizon T the Simple Robust Pricing Policy Earns at Least V*_β(x₀)/(1 + e^{−βT}/(βT))Research Paper
A seller with a fixed stock must choose prices before knowing when customers will arrive or what they will be willing to pay. If customers can wait for a later price, the seller must also account for how today's price changes their purchasing decisions. Chen and Farias study this problem with strategic customers and identify a simple inventory-based policy…
Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming 1: The Randomized Stochastic Gradient Method Has (1/L)E‖∇f(x_R)‖² ≤ (D_f² + σ²Σγ_k²)/Σ(2γ_k − Lγ_k²)Research Paper
Stochastic gradient methods are the standard tool for minimizing an objective that can only be accessed through noisy gradient samples. Training a machine-learning model on sampled data, simulation-based optimization, and stochastic programs with endogenous uncertainty are all of this kind. In many of these applications the objective is nonconvex: the loss…
Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs I: Expected (α, β)-Balanced Prices Scaled by α/(1 + αβ) Earn 1/(1 + αβ) of the Expected Welfare of ALGResearch Paper
A prophet inequality compares an online decision maker, who sees random values one at a time and must decide irrevocably, with a "prophet" who sees all values in advance. The classic result of Krengel, Sucheston and Garling (1977) and Samuel-Cahn (1984) says that for a single item and independent values a single threshold earns at least half of the expected…
Wasserstein Distributionally Robust Optimization and Variation Regularization II: The ∞-Wasserstein Regularizer Equals ρ Times the Mean Local Slope up to ρ²‖H‖ Plus a Boundary TermResearch Paper
In distributionally robust optimization, a decision is judged against probability laws near a nominal law rather than against the nominal law alone. The nominal law is often the empirical distribution of observed data. For a loss function, this produces a worst-case expected loss that depends on the size and geometry of the permitted changes to the data.…
Robust Sample Average Approximation 2: Pearson's χ² Test and the G-Test on a Known Finite Support, with Thresholds √(Q/N), Are Uniformly ConsistentResearch Paper
A decision made from sampled data can be sensitive to the distribution chosen to represent future uncertainty. Robust sample average approximation addresses this by optimizing against every distribution that passes a goodness of fit test, rather than against one fitted distribution. The resulting set of plausible laws is a data driven uncertainty set. Its…
On the Heavy-Tail Behavior of the Distributionally Robust Newsvendor 1: Worst-Case Expected Shortage under Known First and αth Moments Equals That of a Regularly Varying Demand of Tail Index αResearch Paper
A newsvendor chooses an order quantity before seeing demand. Unsold units have no salvage value, while demand above the order quantity cannot be filled. If the demand law is unknown but a few moments are known, the decision maker may minimize cost against the worst distribution consistent with those moments. Das, Dhara and Natarajan study this…
Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals III: Even for I.I.D. Variables, No Nonadaptive Threshold Rule Beats the Factor 1 − 1/eResearch Paper
In a prophet inequality, a decision maker observes random rewards one at a time and must choose without seeing future realizations. The benchmark is a prophet who sees all rewards and selects their maximum. A nonadaptive threshold rule chooses a threshold for each reward before observations begin, then accepts the first arriving reward that crosses its…
Low Rank Approximation and Regression in Input Sparsity Time 1: A Sparse Embedding Matrix with O((r/ε)⁴ log²(r/ε)) Rows Is a (1 ± ε) Subspace Embedding for a Rank-r Matrix with Probability 9/10Research Paper
Many matrix algorithms spend most of their time reading their input. A matrix with few nonzero entries should admit routines whose cost scales with that number, rather than with the product of its dimensions. Clarkson and Woodruff study random maps that compress a matrix before a regression or low rank approximation calculation while retaining the geometric…
A Little Charity Guarantees Almost Envy-Freeness II: With Additive Valuations Such an Allocation Gives Every Agent Her Maximin Share Divided by 2 − |P|/nResearch Paper
A set of n agents must share a set M of m indivisible goods, each agent valuing bundles of goods by her own valuation. Two fairness notions dominate the literature. Envy-freeness up to any good (EFX), introduced by Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang (EC 2016), asks that no agent prefer another's bundle once any single good is removed…
A game-theoretic approach to computation offloading in mobile cloud computing III: Variational Solutions Are the Nash Equilibria of the Extended Cloudlet-Pricing GameResearch Paper
Mobile devices can divide work between local execution, a nearby shared cloudlet, and a remote cloud. A cloudlet has limited capacity, so one user's choice changes the delay faced by the others. Cardellini and coauthors model this as a generalized Nash equilibrium problem, in which each user's feasible choices depend on the aggregate cloudlet load. The…
Double Counting in Supply Chain Carbon Footprinting II: A Carbon Leader Paying Linear Emission-Contingent Rules That Double-Count Internally Earns Its Effort-Contracting ProfitResearch Paper
Firms increasingly account for, and offset, the greenhouse-gas emissions of their entire supply chain, not only their own operations. Emissions in a supply chain are often jointly produced: the footprint of one process (transport, packaging, a molten-bulk delivery) depends on the abatement efforts of several firms at once. When each firm is charged for…
Persistence-Based Clustering in Riemannian Manifolds: With High Probability the Algorithm Returns as Many Clusters as the Density Has d₂-Prominent PeaksResearch Paper
Mode-seeking clustering groups data points by the peak of an underlying probability density that they "flow up" to. Methods of this kind (mean-shift, graph-based hill climbing) are widely used, but their output depends heavily on noise: a density estimated from finitely many samples has many spurious local maxima, and each of them becomes a cluster. Chazal,…
Twin-width I: Tractable FO Model Checking 4: Every K_t-Minor-Free Graph Has Twin-width at Most 4c_g(t)·2^(4c_g(t)+2), a Triple-Exponential Bound in tResearch Paper
Many graph classes are defined by excluding a fixed graph as a minor. A minor can be formed by deleting vertices, deleting edges, and contracting edges. Planar graphs, for example, exclude K5 as a minor. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant proved that every class excluding a fixed clique minor has bounded twin-width, a graph…
Scheduling Problems with Two Competing Agents 9: Total Completion Time Against a Maximum Cost Has at Most n_A·n_B + 1 Nondominated PairsResearch Paper
Many scheduling decisions are not owned by a single decision maker. A machine shared by two departments, a production line serving two customers, or a computing resource shared by two users must process the jobs of two agents, each of which judges a schedule by its own criterion. Agnetis, Mirchandani, Pacciarelli and Pacifici introduced this model in Schedul…
Double Counting in Supply Chain Carbon Footprinting I: With Joint Carbon Production, Every Differentiable Increasing Payment Rule That Makes the Social First-Best a Nash Equilibrium Double-CountsResearch Paper
Carbon accounting assigns emissions from a shared supply-chain process to firms that can reduce them. If more than one firm can change the same emissions, charging each firm only a share may leave each with too little incentive to abate. Caro, Corbett, Tan and Zuidwijk study the conflict between avoiding double counting in an emissions ledger and inducing…
Generalized Couplings and Ergodic Rates for SPDEs and Other Markov Models: A Generalized Coupling and a Lyapunov Function Give a Unique Invariant Measure and Wasserstein Ergodic RatesResearch Paper
Many Markov processes that arise as solutions of stochastic partial differential equations, stochastic delay equations, or other infinite-dimensional models are not strong Feller: their transition probabilities from two nearby starting points can be mutually singular. For such processes convergence to equilibrium cannot hold in total variation, and the…
Steady-State Analysis of the Join-the-Shortest-Queue Model in the Halfin-Whitt Regime 1: Diffusion-Scaled Stationary Queue Lengths Have Expectations Bounded Uniformly in nResearch Paper
Join-the-shortest-queue (JSQ) is the load-balancing rule in which each arriving job is sent to a server with the fewest jobs. It is a baseline in the design of server farms and data centers, and in the many-server Halfin–Whitt regime, where the load per server approaches one at rate 1/n, it combines near-full utilization with vanishing waiting.…
Graphon Mean Field Systems IV: Law of Large Numbers for Particle Systems on Percolated Not-So-Dense Graphs With nβₙ → ∞Research Paper
Large networks are often modeled through a graphon, a measurable function that records how likely two labeled vertices are to interact. For interacting diffusions, this lets one ask whether a finite random network has a predictable population limit. Bayraktar, Chakraborty and Wu study that question for graphon weighted systems, including graphs obtained by…
Twin-width I: Tractable FO Model Checking 3: Grid Minor Theorem for Twin-width — t-Twin-Ordered Matrices Are (2t+2)-Mixed Free, and t-Mixed Free Matrices Have Twin-width at Most 4c_t·α^(4c_t+2)Research Paper
Twin-width is a graph and matrix invariant introduced by Bonnet, Kim, Thomassé and Watrigant (J. ACM 69(1), Article 3, 2021). Classes of bounded twin-width include bounded tree-width and clique-width graphs, proper minor-closed classes, posets of bounded width, and permutations avoiding a fixed pattern; on all of them, first-order model checking is…
Scheduling Problems with Two Competing Agents 3: The Least-Cost Backward Rule Gives a Nondominated Schedule Minimizing Total Completion Time Under a Maximum-Cost BoundResearch Paper
Many scheduling situations involve more than one decision maker sharing a resource. Two departments of a firm may share a machine shop, two clients may share a contractor, or two users may share a processor, and each cares only about how its own jobs are served. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) introduced a systematic…
Dynamic Pricing with Loss-Averse Consumers and Peak-End Anchoring: Every Optimal Price Path Converges Monotonically to a Steady State Set by the Initial Minimum PriceResearch Paper
Firms that change prices over time face customers who remember past prices. A large empirical literature in marketing documents reference price effects: demand depends not only on the current price but on how that price compares with a price the customer expects, and losses (prices above the reference) weigh more than gains of the same size, the loss…
On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems 1: Steepest Descent Can Need ε^(−2+τ) Iterations to Reach |g| ≤ εResearch Paper
Steepest descent is the oldest method for unconstrained minimization: to minimize a smooth function f, it moves from the current point xk along the negative gradient −gk=−∇f(xk). It is the prototype of every first-order method, and its worst-case evaluation complexity — how many iterations it may need before the gradient norm drops below a…
Some Numerical Experiments with Variable-Storage Quasi-Newton Algorithms: The Update (A.7) Is the Unique Least-Change Self-Adjoint Secant Update in a Weighted Hilbert–Schmidt NormResearch Paper
Quasi-Newton methods replace a costly exact Hessian with an operator updated from successive changes in position and gradient. A secant update must map the observed step s to the observed gradient difference y. Many operators satisfy that one equation, so the choice of update needs another criterion. Gilbert and Lemaréchal's working paper studies…