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.

1285 open missions

Missions

426–450 of 1285
Open1285Completed3527All4812
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Average Optimality in Dynamic Programming with General State Space: Under (W) or (S) and Bounded Relative Discounted Values, a Limit of Discount-Optimal Policies Is Average OptimalResearch Paper

A Markov decision process with the average cost criterion asks for a policy that minimizes the long-run expected cost per unit time. The criterion is the natural one for inventory, queueing and maintenance systems that run indefinitely without a meaningful discount rate, and it is the standard benchmark in the theory of controlled Markov chains (Arapostathis…

15 thms3 active usersReviewed
Convex OptimizationFunctional AnalysisOperations Research·Captain: mikedeng1

Stochastic Convex Programming: Basic Duality 1: With Bounded Constraint Sets the Two-Stage Stochastic Convex Program Satisfies min P = sup DResearch Paper

A two-stage stochastic program with recourse models a decision taken in two steps: a first-stage decision is fixed before a random outcome is observed, and a second-stage (recourse) decision is chosen after the outcome is known, both subject to constraints and both incurring costs. The model is the standard framework for planning under uncertainty in…

9 thms3 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

The Tight Constant in the Dvoretzky–Kiefer–Wolfowitz Inequality I: P(√n sup(F − F̂ₙ) > λ) ≤ exp(−2λ²) for λ ≥ min(√(log 2/2), 1.0841 n^(−1/6))Research Paper

The Kolmogorov–Smirnov statistics measure how far the empirical distribution of a sample lies from a hypothesised distribution. They are the standard goodness-of-fit test for continuous data, and their tail probabilities are the basic tool for confidence bands around a distribution function. A test is only usable at a fixed sample size if those tail…

23 thms3 active usersReviewed
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

Subadditive Ergodic Theory 6: The Ulam–Hammersley Constant of the Longest Increasing Subsequence Satisfies (8/π)^{1/2} ≤ c ≤ δ^{1/2} + δ^{−1/2}Research Paper

Ulam asked, in the early 1960s, how long the longest increasing subsequence of a random permutation typically is. The question is a test case for a whole class of problems in combinatorial probability: a quantity defined by an optimisation over exponentially many configurations (here, all subsequences) whose typical size has to be found without enumerating…

10 thms3 active usersReviewed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

The Ellipsoid Method and Its Consequences in Combinatorial Optimization: With a Weak Separation Oracle, the Rounded Ellipsoid Method Is ε-Optimal After N = 4n²⌈log(2R²‖c‖/(rε))⌉ StepsResearch Paper

The ellipsoid method decides questions about a convex set K⊆RnK \subseteq \mathbb{R}^nK⊆Rn by maintaining an ellipsoid that contains the relevant part of KKK and shrinking it step by step. Introduced for convex minimization by Yudin and Nemirovskii and by Shor in the 1970s, it became famous in 1979 when Khachiyan used it to show that linear programming is solvable in…

10 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Reflected Brownian Motion on an Orthant: The Skorokhod Construction Yields an Adapted, Almost Surely Unique, Time-Homogeneous Markov ProcessResearch Paper

Reflected Brownian motion on the orthant is the diffusion that arises as the heavy-traffic limit of open networks of queues. In a KKK-station network the scaled queue-length vector lives in the nonnegative orthant R+K\mathbb R^K_+R+K​; in the interior it moves like a Brownian motion, and when a station empties the process is pushed back into the orthant in a…

13 thms3 active usersReviewed
Algorithmic Game TheoryConvex OptimizationOperations Research+1·Captain: mikedeng1

Cooperative Fuzzy Games 1: A Balanced Game without Side Payments Has a Nonempty Core Containing the Core of Its Fuzzy ExtensionResearch Paper

A game without side payments (an NTU game) describes cooperation in which utility cannot be transferred between players: each coalition AAA of players is assigned the set V(A)V(A)V(A) of payoff vectors it can secure on its own. The core is the set of payoffs to the grand coalition that no coalition can improve upon. Whether the core is nonempty is the basic stability…

13 thms3 active usersReviewed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Optimality and Duality Theory for Stochastic Optimization Problems with Nonlinear Dominance Constraints 1: Under Uniform Dominance, Optimal Solutions Have Concave Utility and L∞ MultipliersResearch Paper

Stochastic programs often optimize a decision that changes several random outcomes at once. A reference outcome may be acceptable even when no fixed threshold captures its risk: one wants the new outcome to be preferable under every increasing concave assessment of gains. Second order stochastic dominance expresses that comparison. Dentcheva and Ruszczyński…

11 thms3 active usersReviewed
Control TheoryOperations ResearchProbability+1·Captain: mikedeng1

Scheduling a Multi Class Queue with Many Exponential Servers: Asymptotic Optimality in Heavy Traffic: The HJB-Based Preemptive Policy Is Asymptotically Optimal Among Work-Conserving PoliciesResearch Paper

Large call centers route several types of customers to a common pool of agents. When the pool is large and highly utilized, the relevant asymptotic regime is the quality-and-efficiency-driven (QED) or Halfin–Whitt regime (Halfin & Whitt 1981). The number of servers nnn grows while the offered load stays within O(n)O(\sqrt n)O(n​) of nnn. Waiting is then neither…

18 thms3 active usersReviewed
Control TheoryDynamic ProgrammingOperations Research+3·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case IX: Imperfect State Information — Reduction to a Perfect-Information Model through a Statistic Sufficient for ControlTextbook

In most control problems the controller does not see the state of the system. It sees noisy observations, remembers its past controls, and must act on that record. Inventory systems with delayed or inaccurate counts, maintenance of machines whose wear is only inspected, target tracking, and medical treatment planned from test results all have this form. The…

15 thms3 active usersReviewed
Control TheoryDynamic ProgrammingOperations Research+2·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case VII: The Finite-Horizon Borel Model — over Universally Measurable Policies J*_K = T^K(J_0)Textbook

Finite-horizon stochastic control on general state and control spaces — inventory levels, queue lengths, positions, beliefs — cannot be written down without measure theory, and the measure theory turns out to be the hard part. The dynamic programming (DP) recursion "start from zero and minimise one stage at a time" is easy to state, but on uncountable…

19 thms3 active usersReviewed
Control TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Optimal Electricity Demand Response Contracting with Responsiveness Incentives 2: The Producer's First-Best Value in Closed FormResearch Paper

Electricity demand response asks consumers to lower their consumption during price events, when generation is expensive or scarce. Field trials such as the Low Carbon London experiment showed that consumers do react to price signals, but that the reaction is erratic: the average consumption falls while its variability stays high, and a producer that has to…

10 thms3 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: mikedeng1

Optimal Dynamic Assortment Planning with Demand Learning: The Separation-Based Policy Has Regret at Most κ₁⌈N/C⌉ log T + K̄₁Research Paper

A retailer who can display only a limited number of products must decide which assortment to show each arriving customer, without knowing how attractive each product is. Offering a product reveals how often it is bought, but offering a poor product costs revenue. This exploration–exploitation trade-off arises in fast fashion, where the selling season is…

13 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Dynamic Pricing Strategies with Reference Effects II: A Myopic Firm Underprices and Its Prices Converge MonotonicallyResearch Paper

Consumers judge a price against a reference price, an internal expectation formed from the prices they have seen before. A price below the reference feels like a gain and raises demand, a price above it feels like a loss and lowers demand. Because today's price moves tomorrow's reference price, a firm facing such consumers solves a dynamic problem even when…

12 thms3 active usersReviewed
Dynamic ProgrammingMarkov ChainOperations Research+2·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems VII: The (BOR) Assumptions and Positive Recurrence of Optimal PoliciesTextbook

Queueing control problems (admission control, routing, service rate selection) are naturally modelled as Markov decision chains with a countably infinite state space and unbounded costs, for instance a holding cost that grows with the queue length. For such models the long-run average cost criterion is often the relevant one, and the central question is…

15 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Elements of Queueing Theory IV: PASTA and the Formulas of Palm CalculusTextbook

Chapter 1 of Baccelli and Brémaud's Elements of Queueing Theory builds Palm calculus. Chapter 2 settles when a queue has a stationary regime. Chapter 3 is called simply Formulas, and it is what the first two chapters were for: it computes.

14 thms3 active usersReviewed
CombinatoricsGraph TheoryLinear algebra·Captain: mikedeng1

On a Conjecture of Spectral Extremal Problems: If the Extremal Graphs for F Are Turán Graphs Plus a Fixed Number of Edges, Every F-Free Graph of Maximum Spectral Radius Is ExtremalResearch Paper

Extremal graph theory asks how many edges a graph on nnn vertices can have without containing a fixed graph FFF. The answer, the Turán number ex(n,F)\mathrm{ex}(n,F)ex(n,F), and the graphs attaining it, the set Ex(n,F)\mathrm{Ex}(n,F)Ex(n,F) of extremal graphs, are known precisely only for special FFF; the Erdős–Stone–Simonovits theorem gives …

24 thms3 active users
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Algorithmic Mechanism Design VIII: A Truthful Approximation Scheme for Bounded Scheduling with VerificationResearch Paper

Algorithmic mechanism design asks for algorithms whose inputs are held by self-interested agents: the designer can pay the agents, and must choose payments so that each agent's own interest leads it to reveal what the algorithm needs. Nisan and Ronen introduced the framework with task scheduling on unrelated machines as the running example (Nisan–Ronen 2001)…

16 thms3 active users
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: mikedeng1

Golden Ratio Algorithms for Variational Inequalities II: The Explicit Golden Ratio Algorithm Converges for Locally Lipschitz Monotone OperatorsResearch Paper

Monotone variational inequalities cover convex minimisation, convex–concave saddle-point problems, Nash equilibria of monotone games and complementarity problems, and they are the standard model for these in optimization and operations research. First-order methods for them (extragradient, forward–backward–forward, reflected and projected gradient methods)…

18 thms3 active users
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks III: Fluid Model Stability Implies SPN StabilityTextbook

A stochastic processing network (SPN) — buffers holding waiting work, activities that consume items from buffers and produce items into others, driven by stochastic arrivals and service requirements — is stable, in the sense of mission I's Definition 3.6, exactly when its ambient Markov chain is positive recurrent. That definition is correct, but it is a…

11 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks I: The Equivalence of SPN StabilityTextbook

A stochastic processing network (SPN) is the general model behind manufacturing lines, call centers, computer systems, communication networks and hospital wards: a collection of buffers holding waiting work, a collection of activities (servers) that consume items from buffers and produce items into others, and stochastic primitives — arrival processes and…

11 thms3 active usersReviewed
Discrete GeometryNumber TheoryOperations Research·Captain: mikedeng1

Minkowski's Convex Body Theorem and Integer Programming: Lattice-Free Convex Bodies Meet Few Translates of an Integral SubspaceResearch Paper

Integer programming asks whether a system of linear inequalities Ax≤bAx\le bAx≤b has a solution x∈Znx\in\mathbb Z^nx∈Zn. In fixed dimension nnn it is solvable in polynomial time: Lenstra (1983) proved this by showing that a convex body without integer points is "flat" in some integral direction, so that the search splits into few lower-dimensional subproblems. Kannan's 1987…

9 thms3 active usersReviewed
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

The Erdős Matching Conjecture and Concentration Inequalities: The Conjecture in a Linear RangeResearch Paper

In 1965 Erdős asked how large a family of kkk-element subsets of an nnn-element set can be if it contains no s+1s+1s+1 pairwise disjoint members. The question, now called the Erdős Matching Conjecture (EMC), contains the Erdős–Ko–Rado theorem (the case s=1s=1s=1) and is one of the central open problems of extremal set theory. Beyond combinatorics it is tied to tail bounds…

23 thms3 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Sorting in c log n Parallel Steps: Sorting Networks of Logarithmic DepthResearch Paper

A sorting network is a sorting procedure whose sequence of comparisons is fixed in advance, independently of the data. Its depth, the number of rounds of simultaneous comparisons on disjoint pairs, is the parallel running time. Sorting networks are used in parallel and hardware sorting, in switching networks, and in cryptography, where a data-independent…

13 thms3 active usersReviewed
Algorithmic Game TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

A General Framework for the Study of Decentralized Distribution Systems: A Core Allocation Rule Whose Nash Equilibrium Is First-BestResearch Paper

Retailers that sell the same product can raise their joint profit by pooling: stock left over at one location is shipped to meet unmet demand at another, and stock can be held in shared warehouses until demand is known (Eppen 1979; Eppen and Schrage 1981). When the retailers are independent firms, pooling creates two questions at once. After demand is…

10 thms3 active usersReviewed
PreviousPage 18 of 52Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36415412
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