Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

The OR Formalization Drive

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.

3527 completed missions

Missions

1676–1700 of 3527
Open1285Completed3527All4812
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

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…

13 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchTheoretical Computer Science·Captain: mikedeng1

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…

6 thms3 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

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)P(S_n\ge x)P(Sn​≥x) of a sum Sn=X1+⋯+XnS_n=X_1+\dots+X_nSn​=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)…

9 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

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)…

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

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…

22 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryAnalysisOperations Research+1·Captain: mikedeng1

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…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

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…

8 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

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→Rf:\mathbb R^n\to\mathbb Rf: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…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

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}Y=\{Y(t):t\ge0\}Y={Y(t):t≥0}, and the quantity of interest is its long-run mean μ\muμ. The central difficulty of simulation output analysis is that the observations are correlated, so the classical confidence interval Yˉn(1)±z σ^/n\bar Y_n(1)\pm z\,\hat\sigma/\sqrt nYˉn​(1)±zσ^/n​ needs a consistent estimate of the time-average variance…

8 thms3 active usersReviewed
🏆Completed
Functional AnalysisMarkov ChainProbability·Captain: mikedeng1

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…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryMarkov ChainProbability·Captain: mikedeng1

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≥−11=\beta_0>\beta_1\ge\dots\ge\beta_{m-1}\ge-11=β0​>β1​≥⋯≥βm−1​≥−1, the distance to stationarity after nnn steps is governed by β∗ n\beta_*^{\,n}β∗n​, where β∗=max⁡(β1,∣βm−1∣)\beta_*=\max(\beta_1,|\beta_{m-1}|)β∗​=max(β1​,∣βm−1​∣) (Diaconis and Stroock 1991, Proposition 3).…

12 thms3 active usersReviewed
🏆Completed
Functional AnalysisMarkov ChainProbability·Captain: mikedeng1

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 λ\lambdaλ, which controls convergence in ℓ2(π)\ell^2(\pi)ℓ2(π) but loses a factor 1/π(x)1/\pi(x)1/π(x) when converted into a bound for a chain started at a point.…

14 thms3 active usersReviewed
🏆Completed
AnalysisOperations ResearchProbability+1·Captain: mikedeng1

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…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

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,…

9 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

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 PPP on X×{−1,1}X \times \{-1, 1\}X×{−1,1}, and its quality is measured by its excess classification risk over the Bayes classifier. Without assumptions on PPP no learning method converges at a uniform rate, so every rate theorem rests on a condition that describes how hard PPP is. Two such conditions are standard: Tsy…

9 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsDynamic ProgrammingOperations Research+1·Captain: mikedeng1

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 nnn 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…

11 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

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…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

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…

12 thms3 active users
🏆Completed
Functional AnalysisProbability·Captain: mikedeng1

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…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Primal-dual subgradient methods for convex problems 1: Dual Averaging Keeps the Gap Below β_{k+1}D + (1/2σ)Σλᵢ²‖gᵢ‖²_*/βᵢ and Its Iterates BoundedResearch Paper

Subgradient methods are the basic tool for minimizing a nonsmooth convex function when only a black-box oracle returning one subgradient per query is available. In the classical method the new subgradient enters the iterate with a weight that decreases over time, so information collected late is counted less than information collected early, and the method…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces VIII: The Longest Increasing Subsequence — Gaussian Concentration of L_N around Its Median MTextbook

Pick NNN independent points X1,…,XNX_1, \dots, X_NX1​,…,XN​ uniformly in [0,1][0,1][0,1] and let LNL_NLN​ be the length of the longest increasing subsequence. Because the points are almost surely distinct, LNL_NLN​ has the law of the longest increasing subsequence of a uniform random permutation of {1,…,N}\{1, \dots, N\}{1,…,N}. This is Ulam's problem, one of the most studied random combinatorial quantities.…

8 thms3 active usersReviewed
🏆Completed
Complexity TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming 2: The Adaptive-Step Algorithm in N∞(β) or N∞⁻(β) with γ ≤ 2(1 − β) Attains Precision t in O(nt) IterationsResearch Paper

Primal-dual interior-point methods solve a linear program by following, approximately, the central path of strictly feasible primal-dual pairs whose complementarity products xjsjx_js_jxj​sj​ are all equal. Every such method confines its iterates to a neighbourhood of that path, and the neighbourhood governs both the theory and the practice. The first primal-dual…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces II: The Two-Point Space — an N-Free Exponential Bound for the One-Sided Hamming Distance under a Second MeasureTextbook

The concentration of measure phenomenon says that in a product probability space a set of probability not too small is "large" in the sense that most points lie within a small distance of it. M. Talagrand's 1995 memoir Concentration of measure and isoperimetric inequalities in product spaces develops this phenomenon through exponential moment bounds for…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Regenerative Stochastic Processes 4: Cumulative Processes on the Same Regeneration Points Are Jointly Asymptotically NormalResearch Paper

Many quantities in queueing, inventory and reliability models are additive functionals of a regenerative process: the total work processed by a server up to time ttt, the cost accumulated by an inventory policy, the time a machine spends broken. Each such quantity grows by independent, identically distributed amounts over the cycles between successive…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisNumerical Analysis+2·Captain: mikedeng1

Régularisation d'inéquations variationnelles par approximations successives II: The Proximal Regularization of a Convex Minimization Problem Is a Minimizing SequenceResearch Paper

The proximal point algorithm replaces a hard optimization or equilibrium problem by a sequence of better-conditioned ones: from the current point xnx^nxn it solves the original problem with a quadratic penalty ∥x−xn∥2\|x-x^n\|^2∥x−xn∥2 added, and takes the solution as xn+1x^{n+1}xn+1. The method is a building block of modern convex optimization. Augmented Lagrangian methods,…

6 thms3 active usersReviewed
PreviousPage 68 of 142Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36535436
5NINickrobbins953286155
6VEvebis25800
7FIfizzyinc321725
8SHshivm17490
9SCShuze Chen9455324
10KMkmehltretter82895261

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me