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.
Negative Dynamic Programming III: If the Actions Are Essentially Finite, Value Iteration from Zero Converges to the Optimal Return and a Stationary Policy Is OptimalResearch Paper
A dynamic programming problem in Blackwell's sense describes a controller who observes the state of a system, picks an action, collects a return, and watches the system move at random to a new state, forever. Blackwell treated the discounted case, with a bounded return and a discount factor below one (Blackwell 1965), and the positive bounded case.…
Consistent Nonparametric Regression III: Consistent Probability Weights Give Consistent Estimators of Conditional Quantiles (Theorem 3)Research Paper
Many prediction tasks ask not for the mean of a response Y given covariates X but for a quantile of its conditional distribution: a median that is robust to outliers, a high quantile that sets a safety stock or a value at risk, or a pair of quantiles that forms a prediction interval. Conditional quantiles are also the Bayes rules for piecewise linear loss,…
Potential Games 3: A Finite Game Has the Finite Improvement Property If and Only If It Has a Generalized Ordinal PotentialResearch Paper
In a strategic game, players may repeatedly change their own choices when a change raises their payoff. This gives a simple model of decentralized adjustment: each move uses the current profile and one player's immediate incentive. The central question is whether such adjustment can continue forever. Monderer and Shapley introduced the finite improvement…
The Weighted Majority Algorithm 4: The Continuous Master WMC Has Total Absolute Loss at Most ln(w_init/w_fin)/(1−β)Research Paper
In sequential prediction, several forecasters can issue different answers for the same instance. A master algorithm must combine their advice before the true label is known. Littlestone and Warmuth's Weighted Majority framework gives worst-case guarantees for this setting: the instances and labels need not come from a probability distribution. The paper…
Large Deviations of Sums of Independent Random Variables 2: For g with Positive Nondecreasing g′, P(S_n ≥ x) ≤ Π(b_j(x/n) + b_gj)exp{−ng(x/n)}Research Paper
Bounds on the upper tail P(Sn≥x) of a sum Sn=X1+⋯+Xn of independent random variables are used throughout probability, statistics, queueing and risk theory: they control ruin probabilities, the error of empirical averages, and the size of the largest deviations of random walks. The classical exponential inequalities (Bernstein, Hoeffding, Bennett)…
Potential Games 2: Every Finite Potential Game Is Isomorphic to a Congestion GameResearch Paper
Congestion games model situations in which agents choose sets of shared resources and the payoff of each resource depends only on how many agents use it: drivers choosing routes through road segments, jobs choosing machines, flows choosing links in a network. Rosenthal (A class of games possessing pure-strategy Nash equilibria, Int. J. Game Theory 2, 1973)…
Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 5: Nonquadratic Proximal Methods of Multipliers Converge to a Saddle PointResearch Paper
The method of multipliers (augmented Lagrangian method) solves a constrained convex program by alternating an unconstrained minimization in the primal variables with an explicit update of the Lagrange multipliers. Rockafellar showed in 1976 that the classical quadratic version is the proximal point algorithm applied to the dual problem, and that a variant…
Cooperative Fuzzy Games 3: The Diagonal Formula Is the Unique Continuous Linear Pareto-Optimal, Symmetric and Atomic Value of Smooth Fuzzy GamesResearch Paper
A value for cooperative games assigns to every game a payoff vector, chosen by axioms rather than by bargaining. Shapley's value (1953) does this for finite games with side payments, and Aumann and Shapley (Values of Non-Atomic Games, 1974) extended it to games with a continuum of players, where it is given by a diagonal formula: a player's value is the…
Monotone Comparative Statics II: f Is Quasisupermodular If and Only If a Strictly Increasing Transformation Makes It Supermodular on Every Sublattice {x₁, x₂, x₁ ∨ x₂, x₁ ∧ x₂}Research Paper
Monotone comparative statics asks when the optimal choice of a decision maker moves in a predictable direction as a parameter of the problem changes: when a firm facing a higher price produces more, when a monopolist facing lower costs sets a lower price, when a player in a game best-responds with a higher strategy to higher strategies of the others. The…
Convergence Properties of the Nelder–Mead Simplex Method in Low Dimensions III: In Dimension 2, the Standard Method's Vertex Values Share One Limit and Simplex Diameters Tend to ZeroResearch Paper
The Nelder–Mead simplex method (Nelder and Mead, 1965) minimizes a function f:Rn→R using function values only. It is among the most widely used derivative-free methods in practice, built into standard numerical libraries, and for decades it had essentially no convergence theory. Lagarias, Reeds, Wright and Wright (1998) gave the first…
Reflected Solutions of Backward SDE's, and Related Obstacle Problems for PDE's 2: With a Concave Coefficient, the Reflected BSDE Is the Value of a Minimax Optimal Stopping–Control ProblemResearch Paper
A backward stochastic differential equation (BSDE) prescribes the terminal value of an adapted process instead of its initial value. Pardoux and Peng (1990) proved existence and uniqueness for Lipschitz coefficients, and BSDEs have since become a standard tool in stochastic control, mathematical finance and the probabilistic treatment of semilinear PDEs. El…
Simulation Output Analysis Using Standardized Time Series 3: No g in 𝓜 Makes g(σB) Almost Surely Constant, So the Length Bound Is Not AttainedResearch Paper
A steady-state simulation produces a single long output path Y={Y(t):t≥0}, and the quantity of interest is its long-run mean μ. The central difficulty of simulation output analysis is that the observations are correlated, so the classical confidence interval Yˉn(1)±zσ^/n needs a consistent estimate of the time-average variance…
Logarithmic Sobolev Inequalities for Finite Markov Chains 3: Lower Bound α ≥ (1 − 2/q)λ / 2(λt_q + log M_q + (q − 2)/q) from a Bound on ‖H_{t_q}‖_{2→q}Research Paper
A finite Markov chain describes a system that changes state according to fixed transition probabilities. For a chain that settles toward an equilibrium distribution, a central question is how quickly the effect of its starting state disappears. The logarithmic Sobolev constant supplies quantitative control of this convergence and, through hypercontractive…
Geometric Bounds for Eigenvalues of Markov Chains 2: Odd Closed Paths Bound the Smallest Eigenvalue, β_min ≥ −1 + 2/ιResearch Paper
The speed at which a finite reversible Markov chain approaches its stationary distribution is controlled by its eigenvalues. For a chain with eigenvalues 1=β0>β1≥⋯≥βm−1≥−1, the distance to stationarity after n steps is governed by β∗n, where β∗=max(β1,∣βm−1∣) (Diaconis and Stroock 1991, Proposition 3).…
Logarithmic Sobolev Inequalities for Finite Markov Chains 2: Entropy Decay Ent_π(μH_t) ≤ e^{−2αt} Ent_π(μ), Improved to e^{−4αt} for Reversible ChainsResearch Paper
How fast a finite Markov chain forgets its starting point is the central quantitative question in the analysis of Monte Carlo algorithms, card shuffling and random walks on groups. The classical tool is the spectral gapλ, which controls convergence in ℓ2(π) but loses a factor 1/π(x) when converted into a bound for a chain started at a point.…
Fast Rates for Support Vector Machines Using Gaussian Kernels 1: Under Tsybakov and Geometric Noise, Gaussian-Kernel SVMs Reach Excess Risk Cx²n^{−β+ε} with Probability 1 − e^{−x}Research Paper
Support vector machines classify observations by choosing a real-valued function from a reproducing kernel Hilbert space and using its sign as the predicted label. The Gaussian kernel is widely used because it gives a flexible class of functions, but that flexibility alone does not explain how quickly classification error approaches the best possible error…
Some Useful Functions for Functional Limit Theorems 4: Time Reversal Is a J₁ Isometry and Reversal from the Origin Is 2-LipschitzResearch Paper
Functional limit theorems describe the behavior of entire time-indexed paths under scaling. In queueing and other stochastic models, a path of departures, workload, or accumulated input may be related to another path by reversing a finite observation window. To carry a limit theorem through that change of viewpoint, one needs to know how reversal acts on…
An Airline Seat Management Model for a Single Leg Route When Lower Fare Classes Book First: The Marginal Seat Value ΔZ_m(n) Decreases in n, So Rejecting Class m Exactly When n ≤ k_m Is OptimalResearch Paper
An airline sells the seats of one flight leg at several fares. Cheap fares are usually booked well before departure and expensive ones close to it, so every early request poses the same question: is the certain revenue of selling a seat now worth more than the chance of selling it later at a higher fare? The policy that answers it is seat inventory control,…
Fast Rates for Support Vector Machines Using Gaussian Kernels 2: An Envelope of Order γ and Tsybakov Noise Exponent q Give Geometric Noise Exponent (q+1)γ/dResearch Paper
A binary classifier is learned from a sample of a distribution P on X×{−1,1}, and its quality is measured by its excess classification risk over the Bayes classifier. Without assumptions on P no learning method converges at a uniform rate, so every rate theorem rests on a condition that describes how hard P is. Two such conditions are standard: Tsy…
A Short Proof of the Gittins Index Theorem: For Finite-State Semi-Markov Bandits, Every Priority Policy Ordering States by the Index Algorithm's Indices Is OptimalResearch Paper
The multi-armed bandit problem with discounted rewards asks how to allocate effort among n independent projects, only one of which can be worked on at a time, when the project worked on evolves randomly and the others stay frozen. It models job scheduling, research planning, search, and sequential clinical experimentation. Gittins and Jones showed in 1974…
Optimal Ordering and Rationing Policies in a Nonstationary Dynamic Inventory Model with n Demand Classes III: Under Full Backlogging, Class-j Rationing Levels Ignore Lower-Class Penalties and DemandsResearch Paper
A single stock of one product often serves customers of different importance: emergency and routine orders for spare parts, contract and spot customers, high- and low-priority patients for a blood bank. When stock runs low, the question is not only how much to order but how much of the remaining stock to hand to the less important customers now, and how…
Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks I: Policy π₀ Is Throughput-Optimal, C′ ⊂ C_π₀ ⊂ C ⊂ C̄′Research Paper
In a wireless multihop network, a switch, or a parallel computer, transmissions interfere: two links that share a receiver, or two crossbar paths that share a port, cannot be active in the same time slot. The scheduler must choose, slot by slot, a set of links that may operate together and decide which traffic each one carries. The basic question is which…
Optimal Ordering and Rationing Policies in a Nonstationary Dynamic Inventory Model with n Demand Classes II: Without Backlogging, the Critical Rationing Levels Are Nondecreasing in tResearch Paper
A firm that holds a single stock of one product often faces demand from several classes of customers that differ in importance: emergency and routine orders for spare parts, contract and spot customers, high- and low-priority users of a military supply system. When stock runs low it can pay to refuse a less important demand now in order to keep stock for a…
Dynamic Scheduling with Convex Delay Costs: The Generalized cμ Rule: Policies Equalizing the Indices μ_k c_k(W_k/ρ_k) Attain the Heavy-Traffic Lower Bound on Cumulative Delay CostResearch Paper
A single server shared by several classes of jobs must decide, at every moment, which class to work on. When each class k incurs a linear delay cost ck per unit of waiting time and needs mean service time 1/μk, the classical cμ rule (serve the waiting class with the largest ckμk) minimizes expected cost in many settings, from the M/G/1 queue to…
Concentration of Measure and Isoperimetric Inequalities in Product Spaces IX: Suprema of Linear Forms in Bounded Independent Variables — P(|Z − M| ≥ u) ≤ 4 exp(−u²/(4σ²))Textbook
A family of linear forms turns independent observations into a single random maximum. Examples include the largest value of a collection of statistical scores and the norm of a random vector sum, which can itself be expressed through the continuous dual of a normed space. A bound for each form separately does not automatically control the supremum over an…