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.

4812 missions

Missions

951–975 of 4812
Open1285Completed3527All4812
🏆Completed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems III: Approximating Sequences for the Discounted Cost CriterionTextbook

Optimal control of queueing systems leads to Markov decision problems whose state space is countably infinite (buffer contents, numbers of customers) and whose costs are unbounded (holding costs grow with the queue). Such a problem cannot be solved on a computer as it stands. The standard remedy is to truncate: solve a finite problem on the states …

12 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior IX: Solutions for Acyclic RelationsTextbook

The solution concept of von Neumann and Morgenstern's Theory of Games and Economic Behavior (1944) is defined from two ingredients: a set of imputations and a domination relation between them. A solution is a set of imputations that is internally stable (no member dominates another) and externally stable (every non-member is dominated by some member). In…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior VIII: Characteristic Functions of General n-Person GamesTextbook

The theory of Theory of Games and Economic Behavior (von Neumann and Morgenstern, 1944; 3rd ed. 1953) rests on one object: the characteristic function v(S)v(S)v(S), the amount a coalition SSS of players can secure for itself whatever the other players do. For zero-sum nnn-person games, Chapter VI defines v(S)v(S)v(S) and proves (25.3.1 and 26.1.1) that the set functions…

15 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior VII: Simple Games, Weighted Majorities and the Main Simple SolutionTextbook

Many collective decisions are taken by coalitions that either carry the vote or do not: committees, legislatures, shareholder meetings, councils with weighted votes. In such a situation the only aim of a participant is to be part of a coalition that wins, and nothing is left to bargain about except the division of the prize inside the winning coalition.…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior IV: The Characteristic Function of a Zero-Sum n-Person GameTextbook

Chapter VI of von Neumann and Morgenstern's Theory of Games and Economic Behavior (1944; 3rd ed. 1953) opens the general theory of zero-sum games with more than two players. The authors propose to describe everything that can be said about coalitions, compensations between partners and fights between coalitions through one numerical object, the characteristi…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationLinear Optimization+1·Captain: mikedeng1

Theory of Games and Economic Behavior III: Mixed Strategies, the Minimax Theorem and Good StrategiesTextbook

A zero-sum two-person game in normalized form is a real matrix H(τ1,τ2)\mathcal H(\tau_1, \tau_2)H(τ1​,τ2​): player 1 chooses a row τ1\tau_1τ1​, player 2 simultaneously chooses a column τ2\tau_2τ2​, and player 2 pays player 1 the amount H(τ1,τ2)\mathcal H(\tau_1, \tau_2)H(τ1​,τ2​). Matrix games are the base case of non-cooperative game theory, the prototype of every minimax statement in optimization,…

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

Theory of Games and Economic Behavior I: Numerical Utility from the Axioms of Preference and MixtureTextbook

Game theory as von Neumann and Morgenstern built it measures every outcome by a single number, the utility a player attaches to it, and combines those numbers linearly when an outcome is uncertain: a lottery that yields uuu with probability α\alphaα and vvv with probability 1−α1-\alpha1−α is worth α v(u)+(1−α) v(v)\alpha\,\mathrm v(u) + (1-\alpha)\,\mathrm v(v)αv(u)+(1−α)v(v). Every later chapter of T…

12 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Numerical Techniques for Stochastic Optimization V: Asymptotic Optimality of List Scheduling for the Machine Investment ProblemTextbook

Two-stage stochastic integer programs combine the two hardest features of mathematical programming: uncertainty in the data and integrality of the decisions. Even evaluating the objective of such a program at a single first-stage decision requires the expected optimal value of an NP-hard combinatorial problem. Chapter 8 of Ermoliev and Wets (eds.), Numerical…

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

Numerical Techniques for Stochastic Optimization II: Logarithmic Concavity of Probabilistic ConstraintsTextbook

Many engineering and economic planning problems must meet random requirements with a prescribed reliability: a reservoir must satisfy demand with probability at least 0.950.950.95, a power system must cover load except on rare days, an inventory must avoid shortage with high probability. Probabilistic constrained programming (also called chance-constrained…

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+2·Captain: mikedeng1

Numerical Techniques for Stochastic Optimization I: Edmundson–Madansky Bounds for Independent Random Data and Simple RecourseTextbook

In a two-stage stochastic linear program a decision xxx is taken before random data ξ\xiξ are observed, and a corrective recourse decision yyy is taken afterwards at a cost. The objective contains the expectation of an optimal value of a linear program, ∫Q(x,ξ(ω)) P(dω)\int Q(x,\xi(\omega))\,P(d\omega)∫Q(x,ξ(ω))P(dω), and for continuous or high-dimensional ξ\xiξ that integral cannot be evaluated…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Information Sharing in a Supply Chain with a Common Retailer 2: Under Production Economy the Retailer Earns Weakly More from Sequential Information Contracting and the Manufacturers from ConcurrentResearch Paper

Large retailers hold point-of-sale and loyalty-card data that their suppliers cannot observe, and many of them sell access to it through data-sharing programs; others share the same data for free, or with only some suppliers (Shang, Ha & Tong 2016, §1). When two competing manufacturers sell through one common retailer, sharing a demand signal with a…

19 thms4 active usersReviewed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

The Matroids with the Max-Flow Min-Cut Property: Binary Mengerian Clutters and the Q6 MinorResearch Paper

Several classical theorems of combinatorial optimization say that a family of sets arising from a graph packs: the maximum number of pairwise disjoint members equals the minimum size of a set meeting every member. König's theorem on bipartite graphs, Menger's theorem, the max-flow min-cut theorem of Ford and Fulkerson, Edmonds' branching theorem and the…

30 thms4 active usersReviewed
🏆Completed
AnalysisFunctional AnalysisPartial Differential Equations·Captain: mikedeng1

Notes on Partial Differential Equations VI: Interior Regularity of Weak Solutions via Difference QuotientsTextbook

A second-order elliptic equation in divergence form, Lu=−∑i,j∂i(aij∂ju)=fLu = -\sum_{i,j}\partial_i(a_{ij}\partial_j u) = fLu=−∑i,j​∂i​(aij​∂j​u)=f, is usually solved in a weak sense: the Lax–Milgram theorem or the Fredholm alternative produces a function u∈H1(Ω)u \in H^1(\Omega)u∈H1(Ω), which has only first-order weak derivatives, and the equation holds after one integration by parts against every test function.…

12 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Algorithmic Mechanism Design I: MinWork Is a Strongly Truthful n-Approximation Mechanism for Task Scheduling on Unrelated MachinesResearch Paper

Algorithmic mechanism design asks for algorithms whose inputs are held by self-interested parties. Each party reports its private data, the algorithm computes an outcome, and payments are arranged so that no party gains by misreporting. Nisan and Ronen introduced the field in Algorithmic Mechanism Design (Games Econ. Behav. 35, 2001). Their running example…

9 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

Competitive Caching with Machine Learned Advice: The Competitive Ratio of Predictive MarkerResearch Paper

Caching (online paging) is one of the oldest problems in online algorithms: a fast memory of kkk slots serves a sequence of requests, and every request for an element not in the fast memory is a cache miss that forces the element to be loaded, possibly evicting another one. With the whole request sequence known in advance, evicting the element whose next…

10 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Selected Topics in Column Generation III: Ryan–Foster Branching — a Fractional Basic Set-Partitioning Solution Covers Some Row Pair FractionallyResearch Paper

Column generation solves linear programs with far too many variables to list: one works with a small subset J′⊆JJ' \subseteq JJ′⊆J of the columns, the restricted master problem (RMP), and adds columns of negative reduced cost as a pricing problem finds them (Lübbecke and Desrosiers 2005, §2.1). Many integer programs from vehicle routing, crew scheduling and crew…

5 thms4 active usersReviewed
🏆Completed
AnalysisDynamical SystemsFunctional Analysis+1·Captain: mikedeng1

Ordinary Differential Equations and Dynamical Systems IV: Regular Sturm–Liouville ProblemsTextbook

Separation of variables reduces the heat equation, the wave equation and the Schrödinger equation on an interval to an eigenvalue problem for a second-order ordinary differential operator with boundary conditions at both ends. Whether the method works depends on one fact: the eigenfunctions of that operator must be complete, so that every reasonable initial…

17 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems IV: The Optimal Randomized Two-Server Ratio 1652/1069 on the 3-4-5 TriangleResearch Paper

The kkk-server problem is a basic model of on-line decision making. kkk mobile servers move in a metric space, requests for points arrive one at a time, and each request has to be covered by a server before the next one arrives. The cost is the total distance the servers move. The problem includes paging, caching and disk-head scheduling as special cases (Manass…

7 thms4 active usersReviewed
🏆Completed
AnalysisDynamical SystemsLinear algebra·Captain: mikedeng1

Ordinary Differential Equations and Dynamical Systems II: Linear Systems and Floquet TheoryTextbook

Linear systems of ordinary differential equations x˙=A(t)x\dot x = A(t)xx˙=A(t)x are the first case of the general theory in which solutions can be described structurally rather than merely shown to exist. They arise directly (circuits, mechanical vibrations, Hill's equation for the stability of periodic motions, the Mathieu equation for parametric resonance) and…

9 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems I: Optimal Competitiveness of Randomized Block Snoopy CachingResearch Paper

In a shared-memory multiprocessor, each processor keeps copies of memory blocks in its own cache, and all caches listen ("snoop") on a common bus. Every bus cycle spent keeping these copies consistent is a cycle not available for useful work, so the protocol that decides when a block is shared by several caches and when it is private to one cache directly…

8 thms4 active usersReviewed
Algorithmic Game TheoryDynamical SystemsProbability+1·Captain: mikedeng1

On the Global Convergence of Stochastic Fictitious Play III: Almost Sure Convergence to Linearly Stable Rest Points in Potential GamesResearch Paper

Stochastic fictitious play is a basic model of learning in repeated games. Each period every player best responds to the empirical frequencies of the opponents' past play, after the player's payoffs have been hit by a fresh random shock. It was introduced by Fudenberg and Kreps (1993), is a standard object in the theory of learning in games (Fudenberg and…

14 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Random Gradient-Free Minimization of Convex Functions III: Accelerated Random SearchResearch Paper

Many optimization problems in engineering, simulation-based design and machine learning give access only to function values: the objective is the output of a simulator or a black-box program, and its gradient is unavailable or too expensive. Derivative-free (or zeroth-order) methods address this setting. Nesterov and Spokoiny (Found. Comput. Math. 17 (2017))…

16 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Random Gradient-Free Minimization of Convex Functions II: Random Gradient Descent for Smooth and Strongly Convex ProblemsResearch Paper

Many optimization problems in engineering, simulation-based design and machine learning give access to the objective only through its values: the function is computed by a black-box code, and derivatives are unavailable or too expensive to program. Zeroth-order (derivative-free) methods address this setting. Classical derivative-free methods (pattern…

14 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Random Gradient-Free Minimization of Convex Functions I: Random Search for Nonsmooth Convex ProblemsResearch Paper

Many optimization problems in engineering, simulation-based design and machine learning give access to the values of an objective function but not to its gradient: the function is computed by a black-box program, by a simulator, or by a model whose derivatives are unavailable or too expensive. Zeroth-order (or derivative-free) methods use only function…

14 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

The Distributionally Robust Chance-Constrained Vehicle Routing Problem I: With a Subadditive Demand Estimator the Two-Index Vehicle Flow Formulation Is ExactResearch Paper

The capacitated vehicle routing problem (CVRP) asks for delivery routes of minimum cost. Each route starts and ends at a depot, every customer is visited exactly once, and the demand served on a route does not exceed the vehicle capacity. The problem is central in logistics and one of the most studied problems in combinatorial optimization. Its standard…

12 thms4 active usersReviewed
PreviousPage 39 of 193Next

Top contributors

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