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.

3528 completed missions

Missions

1951–1975 of 3528
Open1284Completed3528All4812
🏆Completed
Algorithmic Game TheoryComplexity TheoryOperations Research·Captain: mikedeng1

The Complexity of Computing a Nash Equilibrium 2: The Three-Colorable Addition-Multiplication Gadget Has Error Amplification 81Research Paper

Nash's theorem guarantees that every finite game has a mixed equilibrium, but says nothing about how hard one is to find. Daskalakis, Goldberg and Papadimitriou (SIAM J. Comput. 39(1), 2009) showed that computing a Nash equilibrium is complete for the class PPAD of total search problems whose solutions are guaranteed by a parity argument on a directed graph…

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

One-Machine Sequencing to Minimize Certain Functions of Job Tardiness II: EDD Order Minimizes Any Sum of Convex Nondecreasing Tardiness Penalties When No Job Starts After Its Due DateResearch Paper

A single machine must process a set of jobs, each with a processing time and a due date, and the cost of a schedule depends on how late the jobs finish. Total tardiness is the classical criterion, but in many applications lateness is penalised more than proportionally: a job one week late costs more than twice a job half a week late, and a quadratic or…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+2·Captain: mikedeng1

Secretary Problems: Weights and Discounts 5: A 3e-Competitive Algorithm for the Graphic Matroid Secretary ProblemResearch Paper

In the secretary problem, nnn items with nonnegative values arrive one at a time in a uniformly random order, and an online algorithm must decide on each arrival, irrevocably, whether to keep it. The classical version keeps one item; the rule that observes a 1/e1/e1/e fraction of the arrivals and then takes the first item better than everything seen picks the best…

10 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Discrete Dynamic Programming 2: A Stationary Policy Is Nearly Optimal as the Discount Factor Tends to 1 Exactly When It Maximizes x(g) and, Among Those, y(g)Research Paper

A finite Markov decision problem with discounting is solved by Howard's policy improvement routine: start from a stationary policy, switch to actions that do better against its value, repeat. When the discount factor β\betaβ tends to 111 the total discounted income typically diverges, and the natural targets become the long-run average income and, among…

11 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research·Captain: mikedeng1

Consensus of Subjective Probabilities: The Pari-Mutuel Method: Equilibrium Track Probabilities Exist and Are UniqueResearch Paper

A group of mmm individuals each hold a subjective probability distribution over the same nnn outcomes, and one wants a single distribution representing their consensus. Averaging and convolution are the obvious candidates. Eisenberg and Gale (Ann. Math. Statist. 30(1), 1959) observe that a real institution already performs such an aggregation: the pari-mutuel…

12 thms3 active usersReviewed
🏆Completed
Linear OptimizationMachine LearningProbability+1·Captain: mikedeng1

The Dantzig Selector: Statistical Estimation When p Is Much Larger than n 2: Oracle Inequality within a Logarithmic Factor of the Ideal Mean Squared ErrorResearch Paper

Many regression problems have far more unknown coefficients ppp than observations nnn: gene expression studies with tens of samples and thousands of genes, imaging from few measurements, nonparametric curve recovery from a finite number of noisy samples. Estimation is hopeless in general, but becomes possible when the parameter is sparse, that is, has few…

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

Minimization of Functions Having Lipschitz Continuous First Partial Derivatives: Gradient Steps with Sufficient Decrease δ|∇f(x_k)|², 0 < δ ≤ 1/4K, Converge to the MinimizerResearch Paper

The gradient method minimizes a differentiable function fff on Rn\mathbb{R}^nRn by moving from the current point xkx_kxk​ along the negative gradient, xk+1=xk−λk∇f(xk)x_{k+1} = x_k - \lambda_k \nabla f(x_k)xk+1​=xk​−λk​∇f(xk​). Every practical implementation has to choose the step λk\lambda_kλk​. A fixed step requires knowing a Lipschitz constant of ∇f\nabla f∇f; an exact line search is expensive. Larry Armijo's…

4 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Discrete Dynamic Programming 1: Every Finite Markov Decision Problem Has a Stationary Policy That Is Optimal for All Discount Factors Sufficiently Near 1Research Paper

A Markov decision problem models a system that is observed once per period and controlled by choosing an action: the action earns an immediate income and determines the probabilities of the next state. Inventory control, machine replacement, queue admission and many reinforcement-learning benchmarks are of this form. With future income discounted by a…

11 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

The Price of Anarchy of Finite Congestion Games II: For Symmetric Games the Average Social Cost Price of Anarchy Is (5N-2)/(2N+1)Research Paper

Selfish routing and resource sharing are modelled by congestion games: each player picks a set of shared resources, and the cost of a resource grows with the number of players using it. The price of anarchy, introduced by Koutsoupias and Papadimitriou (STACS 1999), measures how much worse the social cost of a worst Nash equilibrium is than the optimum. For…

9 thms3 active usersReviewed
🏆Completed
AnalysisFunctional AnalysisMachine Learning·Captain: mikedeng1

Theory of Reproducing Kernels II: One Reproducing Kernel Class Contains Another iff a Multiple of Its Kernel Dominates the Other KernelResearch Paper

A reproducing kernel Hilbert space (RKHS) is a Hilbert space of functions in which evaluation at each point is a continuous functional. Each such space is determined by its kernel, and in practice spaces are usually given by their kernels: Gaussian or Sobolev kernels in kernel methods and Gaussian-process regression, the Bergman and Szegő kernels in complex…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningProbability+1·Captain: mikedeng1

Stability and Generalization 4: Relative-Entropy Regularization of Mixtures Has Uniform Stability M²/(λm)Research Paper

A learning algorithm generalizes when its error on fresh data is close to its error on the training sample. Bousquet and Elisseeff (JMLR 2, 2002) showed that a single property of the algorithm, uniform stability, controls this gap with exponential concentration: if removing any one example from a training set of size mmm changes the loss of the output at…

18 thms3 active users
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Stability and Generalization 2: Exponential Generalization Bounds for Uniformly Stable AlgorithmsResearch Paper

A learning algorithm is judged by its generalization error: the expected loss of the hypothesis it outputs on a fresh example. That quantity depends on an unknown distribution, so it is estimated from the training data, by the empirical error (the average loss on the training set) or the leave-one-out error (the average loss on each training point of the…

13 thms3 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchProbability+1·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 6: An Attractor Whose Basin Meets the Attainable Set Contains the Limit Set with Positive ProbabilityResearch Paper

A stochastic approximation algorithm is a recursion xn+1=xn+γn+1(F(xn)+Un+1)x_{n+1}=x_n+\gamma_{n+1}\big(F(x_n)+U_{n+1}\big)xn+1​=xn​+γn+1​(F(xn​)+Un+1​) with decreasing step sizes γn\gamma_nγn​ and a noise term Un+1U_{n+1}Un+1​. Recursions of this form appear in stochastic gradient methods, adaptive control, learning in games (fictitious play, reinforcement learning) and urn models. The ODE method compares the iterates…

11 thms3 active usersReviewed
🏆Completed
Machine LearningNumerical AnalysisOptimization·Captain: mikedeng1

Gradient Convergence in Gradient Methods with Errors I: With Deterministic Errors Proportional to the Stepsize, Either f(x_t) → −∞ or f(x_t) Converges and ∇f(x_t) → 0Research Paper

Gradient methods are the workhorse of large-scale nonlinear optimization and of the training of statistical models. In practice the direction actually used is rarely the exact negative gradient: it may be scaled, computed incrementally one data component at a time, or perturbed by approximation error. The classical convergence theory of such methods often…

6 thms3 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchProbability+1·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 3: Martingale Noise with Bounded q-th Moments and Summable γ_n^(1+q/2) Satisfies Assumption A1 Almost SurelyResearch Paper

A stochastic approximation algorithm is a recursion

10 thms3 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchStochastic Systems·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 5: If V(Λ) Has Empty Interior for a Lyapunov Function V, Every Internally Chain Transitive Set Lies in ΛResearch Paper

A stochastic approximation algorithm is a recursion xn+1=xn+γn+1(F(xn)+Un+1)x_{n+1}=x_n+\gamma_{n+1}\big(F(x_n)+U_{n+1}\big)xn+1​=xn​+γn+1​(F(xn​)+Un+1​) with decreasing steps γn\gamma_nγn​ and noise UnU_nUn​. Stochastic gradient descent, the Robbins–Monro procedure, reinforcement-learning updates and learning dynamics in games all have this form. The ODE method compares such a recursion with the deterministic dynamics …

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningMarkov Chain+1·Captain: mikedeng1

Reinforcement Learning: An Introduction IX: Average Reward and the Futility of Discounting in Continuing ProblemsTextbook

Reinforcement learning formulates control as maximizing reward accumulated over time. For continuing tasks, where interaction never terminates, the standard textbook objective is the discounted return with a discount rate γ<1\gamma < 1γ<1. Chapter 10 of Sutton and Barto, Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018), argues that once values…

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

On Conjugate Convex Functions: Conjugation Is a Symmetric Correspondence Between Lower Semicontinuous Convex FunctionsResearch Paper

Convex duality in optimization rests on one transformation: to a convex function fff one associates the function φ(ξ)=sup⁡x(Σxξ−f(x))\varphi(\xi) = \sup_x(\Sigma x\xi - f(x))φ(ξ)=supx​(Σxξ−f(x)), which records, for each slope ξ\xiξ, the best affine lower bound of fff with that slope. Lagrangian duality, the duality theory of linear and conic programming, the analysis of first-order methods through…

12 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

An Inventory Model with Limited Production Capacity and Uncertain Demands I. The Average-Cost Criterion: With Finite Storage a Modified Base-Stock Policy Is Strongly Average-Cost OptimalResearch Paper

A manufacturer that makes one product to stock faces random demand, can produce at most bbb units per period, and can store at most UUU units. The classical result without the production limit is that a base-stock policy is optimal: raise inventory to a fixed level yˉ\bar yyˉ​ each period. With a production limit, the natural modification is to produce up to yˉ\bar yyˉ​ w…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives II: The 4n/k Rate of the Averaged Iterate without Strong ConvexityResearch Paper

Many problems in statistics and machine learning minimize an average of nnn losses, one per data point, plus a regularizer: least squares, logistic regression, and their ℓ1\ell_1ℓ1​- or ℓ2\ell_2ℓ2​-penalized versions. When nnn is large, a full gradient costs nnn component gradients, while stochastic gradient descent, which uses one component per step, needs decreasing step…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Twice Regularized MDPs and the Equivalence Between Robustness and Regularization 1: The Robust Value Function Is the Optimum of a Policy- and Value-Regularized Convex ProgramResearch Paper

A Markov decision process (MDP) is solved for one model of its dynamics and rewards, but in practice that model is estimated from data, and a policy that is optimal for the estimate can perform poorly on the true system (Mannor et al., 2007). Robust MDPs address this by evaluating a policy against the worst model in an uncertainty set U\mathcal UU (Iyengar,…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives I: Linear Convergence under Strong ConvexityResearch Paper

Many problems in machine learning and statistics are finite sums: an empirical risk f(x)=1n∑i=1nfi(x)f(x)=\frac1n\sum_{i=1}^n f_i(x)f(x)=n1​∑i=1n​fi​(x) over nnn data points, often plus a regulariser hhh such as an ℓ1\ell_1ℓ1​ penalty. When nnn is large, a full gradient of fff costs nnn component gradients, while stochastic gradient descent uses one component per step but converges only sublinearly because…

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

Open Queueing Networks in Heavy Traffic: Reflected Brownian Motion Limit for the Queue Length ProcessResearch Paper

Open networks of single-server queues with general interarrival and service distributions are the standard model of job shops, communication networks and service systems. Outside the product-form (Jackson) case their queue-length distributions are not known in closed form. When every station is close to saturation, a heavy-traffic limit replaces the network…

18 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction IV: Policy Iteration for ε-Soft PoliciesTextbook

Policy iteration alternates two steps: evaluate the current policy, then replace it by a policy that is greedy with respect to the evaluated action values. The policy improvement theorem guarantees that each greedy step does not make the policy worse, and that the process stops only at an optimal policy. When the action values are estimated from experience…

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

Quantifying the Bullwhip Effect in a Simple Supply Chain: The Impact of Forecasting, Lead Times, and Information 1: Centralizing Demand Information Does Not Eliminate the Bullwhip EffectResearch Paper

The bullwhip effect is the observation that the variability of orders increases as one moves up a supply chain, from the retailer towards the manufacturer and its suppliers. It was documented in industry and in classroom experiments such as the Beer Game (Sterman 1989), and analysed by Lee, Padmanabhan and Whang (1997), who named demand forecasting, lead…

9 thms3 active usersReviewed
PreviousPage 79 of 142Next

Top contributors

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

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