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

1226–1250 of 4812
Open1285Completed3527All4812
🏆Completed
Operations ResearchOptimizationProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation V: integrated chance constraints with a finite discrete distribution define polyhedraTextbook

A probability constraint in a stochastic linear program asks that a random linear inequality hold with high probability. It counts every violation the same, however large, and the feasible set it defines is in general not convex, as Klein Haneveld's examples show (Klein Haneveld 1986). Integrated chance constraints replace the probability of a shortfall…

17 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) VI: The Tutte–Berge Formula for the Maximum Size of a MatchingTextbook

A matching pairs up nodes of a graph along its edges, each node being used at most once. Finding a largest matching is the model problem of combinatorial optimization: the obvious linear relaxation is not integral on non-bipartite graphs, and the methods developed for it (augmenting paths, odd-circuit shrinking, polyhedral descriptions) became standard…

37 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) XII: Edmonds' Matroid Polytope TheoremTextbook

The Greedy Algorithm builds a set one element at a time, always adding the heaviest element that keeps the set feasible. For the forests of a graph it finds a maximum-weight forest (Kruskal's algorithm), but for the matchings of a graph it can fail: on a 4-cycle with edge weights 9, 7, 8, 3 it picks the edges of weight 9 and 3 when the edges of weight 7 and…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) I: The Characteristic Vector of a Minimum Spanning Tree Is an Optimal Solution of the Spanning-Tree Linear ProgramTextbook

A minimum spanning tree (MST) of a connected graph with edge costs is a cheapest set of edges that connects all nodes and contains no circuit. It is the prototype of a combinatorial optimization problem solved exactly by a greedy rule, and it opens Chapter 2 of Cook, Cunningham, Pulleyblank and Schrijver's Combinatorial Optimization (Wiley, 1998). The…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) VII: For Arbitrary Costs the Minimum Cost of a T-Join Equals the Optimal Value of Its Linear ProgramTextbook

A mail carrier must walk every street of a district and return to the post office, and wants to walk as little as possible. Kwan Mei-Ko posed this Chinese postman problem in 1962. Edmonds observed that the extra streets to be walked a second time form a set of edges whose odd-degree nodes are exactly the odd-degree nodes of the street graph, and generalized…

25 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear algebraLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) IX: The Hoffman–Kruskal Theorem: {x≥0:Ax≤b}\{x \ge 0 : Ax \le b\}{x≥0:Ax≤b} Is Integral for All Integral bbb Iff AAA Is Totally UnimodularTextbook

Many combinatorial optimization problems (bipartite matching, maximum flow, shortest paths, transportation and assignment problems) can be written as integer programs

10 thms3 active usersReviewed
Bandit AlgorithmsMachine LearningProbability·Captain: iris

A General Framework for Bandit Problems Beyond Cumulative Objectives: U-UCB has regret O(log T / T) for every stable, smooth EDPM with a linear gapResearch Paper

In the classical stochastic multi-armed bandit a decision maker is scored by the sum of the rewards it collects. Many applications score the collected rewards differently: a portfolio manager cares about the conditional value at risk (CVaR) or the Sharpe ratio of the returns, a clinical trial about a quantile, a risk-averse controller about mean–variance.…

16 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) IV: In a Legal Ordering the Last Node's Star Is a Minimum Cut Separating the Last Two NodesTextbook

The global minimum cut problem asks, for a finite undirected graph with nonnegative edge capacities, for a partition of the nodes into two nonempty sides that is crossed by edges of least total capacity. With unit capacities the optimal value is the edge-connectivity of the graph, a basic measure of network reliability; with general capacities the problem…

14 thms3 active usersReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

Fast Core Pricing for Rich Advertising Auctions: the water-filling algorithm finds an ϵ\epsilonϵ-bidder-optimal core point in O(nlog⁡(n/ϵ))O(n\log(n/\epsilon))O(nlog(n/ϵ)) oracle calls and O(n2log⁡(n/ϵ))O(n^2\log(n/\epsilon))O(n2log(n/ϵ)) timeResearch Paper

Online ad platforms sell a limited number of lines of ad space to advertisers whose ads come in several shapes and sizes, so their preferences over the space are combinatorial and often complementary (Niazadeh et al., arXiv:1610.03564v4, §1). The Vickrey–Clarke–Groves auction can earn little revenue on such preferences. Core-selecting auctions (Ausubel and…

40 thms3 active usersReviewed
Algebraic TopologyLinear algebraOptimization·Captain: iris

Hidden Convexity, Optimization, and Algorithms on Rotation Matrices: Every Linear Image of SO(n)\mathrm{SO}(n)SO(n) in the Plane Is Convex for n≥3n \ge 3n≥3Research Paper

Many problems in computer vision, robotics, satellite attitude estimation and point-cloud registration ask for the rotation that best explains some data. In matrix form they are linear optimization problems over the special orthogonal group, max⁡{⟨A,X⟩:X∈SO(n)}\max\{\langle A,X\rangle : X\in\mathrm{SO}(n)\}max{⟨A,X⟩:X∈SO(n)}, where ⟨A,X⟩=tr⁡(A⊤X)\langle A,X\rangle=\operatorname{tr}(A^\top X)⟨A,X⟩=tr(A⊤X). Without side…

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchStatistics·Captain: iris

Selection of the Most Probable Best: An Allocation Is Optimal for the Relaxed Budget Allocation Problem iff It Satisfies the Global Balance, Pairwise Balance and Zero-Sampling-Ratio ConditionsResearch Paper

Simulation models of service systems, supply chains and financial products depend on input parameters that are themselves estimated from data, such as arrival rates or demand distributions. When a decision maker compares kkk candidate designs by simulation, this input uncertainty means that the best design may differ from one plausible parameter value to the…

18 thms3 active usersReviewed
🏆Completed
Convex OptimizationEconomicsOperations Research·Captain: iris

A Simple Characterization of Supply Correspondences: a supply correspondence is strongly rationalizable iff it is maximal monotone and homogeneous of degree zeroResearch Paper

Producer theory asks which observed supply behaviour is consistent with a profit-maximizing competitive firm. A supply correspondence records, for every vector of prices, the set of production plans the firm is willing to choose. If the firm maximizes profit over a fixed technology, its supply must satisfy testable restrictions; the question of rationalizabi…

15 thms3 active usersReviewed
Control TheoryOperations ResearchProbability+1·Captain: iris

A Mean-Field Control Problem of Optimal Portfolio Liquidation with Semimartingale Strategies: The Value Function Is Linear-Quadratic in the State's Law and the Optimal Strategy Jumps Only at t and TResearch Paper

A large investor who must sell a position of x0x_0x0​ shares by a deadline TTT moves the price against their own position: every sale depresses the price, and the depression decays only gradually. Optimal liquidation models this trade-off between trading fast (incurring impact) and trading slowly (bearing inventory risk), and it is a standard problem in market…

24 thms3 active usersReviewed
Bandit AlgorithmsMachine LearningReinforcement Learning+1·Captain: iris

Foundations of Reinforcement Learning XII: E2D Regret Is at Most the Decision-Estimation Coefficient Times T Plus γ·EstSqTextbook

In a structured bandit a learner repeatedly picks a decision πt\pi^tπt from a possibly huge or continuous set Π\PiΠ and observes a noisy reward with mean f⋆(πt)f^\star(\pi^t)f⋆(πt), where f⋆f^\starf⋆ belongs to a known class F\mathcal FF of functions Π→R\Pi\to\mathbb RΠ→R. The optimal regret depends on F\mathcal FF in ways that are hard to predict: optimism (UCB) and posterior sampling…

27 thms3 active usersReviewed
Markov ChainOperations ResearchProbability·Captain: iris

Improving Blockchain Consistency by Assigning Weights to Random Blocks: Ironclad's Normalized Minimal Adversarial Mining-Power Requirement Strictly Exceeds Nakamoto's (R > 1)Research Paper

Proof-of-work blockchains such as Bitcoin keep a ledger consistent only while the honest parties hold enough mining power relative to an adversary. Network delay erodes that margin: when two honest blocks are mined within the delay bound Δ\DeltaΔ, honest parties extend different chains, and an adversary can exploit the fork. The consistency bound of a…

15 thms3 active usersReviewed
Machine LearningReinforcement LearningStatistics·Captain: iris

Foundations of Reinforcement Learning VII: Empirical Risk Minimization over a Finite Class Has Expected Excess Risk ≲ √(log|F|/T), and ≲ log|F|/T for Well-Specified Square LossTextbook

Interactive decision making rests on estimation: an agent that acts well must fit a model to past data and rely on it for data not yet seen. The lecture notes of Foster and Rakhlin (arXiv:2312.16730) therefore open with statistical learning, the passive problem in which the learner does not influence the data. It isolates generalization and function…

20 thms3 active usersReviewed
Algorithmic Game TheoryConvex OptimizationOperations Research·Captain: iris

Approximating the Set of Nash Equilibria for Convex Games: Algorithm 4.8's output contains every Nash equilibrium and consists of (ε₁ + (2+κ)Lε₂)-approximate Nash equilibriaResearch Paper

A game with a shared constraint couples the players twice: through their costs and through a joint feasible set that restricts which strategy profiles are allowed. Such generalized Nash games model system-wide limits, for example a common capacity or emission budget (Rosen 1965; Facchinei–Kanzow 2010). They typically have a continuum of equilibria, so one…

12 thms3 active usersReviewed
Algorithmic Game TheoryConvex OptimizationEconomics·Captain: iris

The Edgeworth Conjecture with Small Coalitions and Approximate Equilibria in Large Economies: every κ-core allocation of a replica economy is an ε-Walrasian allocationResearch Paper

Edgeworth (1881) conjectured that as an exchange economy grows, the outcomes that no group of traders can improve upon by trading among themselves shrink to the competitive (Walrasian) outcomes. Debreu and Scarf (DS63) proved this for replica economies: an allocation that lies in the core of the nnn-fold replica En\mathcal E^nEn for every nnn is a Walrasian…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Limit Theory for Taboo-Regenerative Processes: Conditioned on No Exit by Time ttt, the Cycles Around ttt and the Age Converge Uniformly to the Two-Sided Taboo Limit P∗P^*P∗Research Paper

Many stochastic models are studied up to a failure: a queue until overflow, a network until a job is lost, a reliability system until breakdown, a Markov chain until it leaves a set of states. When failure is rare, the informative object is the process conditioned on no failure so far. For Markov chains this is the classical theory of quasi-stationary…

20 thms3 active usersReviewed
EconomicsOperations ResearchProbability·Captain: iris

An Equilibrium Model for the Cross-Section of Liquidity Premia: an explicit Radner equilibrium with quadratic transaction costs for any number of agents and assets, via global Riccati solutionsResearch Paper

Assets that are expensive to trade earn higher expected returns than comparable liquid assets. Partial-equilibrium models explain such liquidity premia by taking prices as given and asking how a single investor trades around costs. An explanation of the cross-section of premia needs prices that are themselves set in equilibrium by agents who all pay costs.…

26 thms3 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: iris

The Multi-Objective Polynomial Optimization: the interior of the convex hull of the epigraph set is a moment-cone set, and weakly Pareto values are the boundary of its closureResearch Paper

A multi-objective optimization problem minimizes several objective functions over one feasible set. The objectives rarely share a minimizer, so the usual targets are Pareto points, where no objective can be improved without worsening another, and weakly Pareto points, where the objectives cannot all be improved at once. Such problems arise in economics,…

20 thms3 active usersReviewed
Linear algebraOperations ResearchOptimization·Captain: iris

Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: relaxation-based sampling is within slog⁡s+log⁡(ns)−slog⁡n+αs\log s+\log\binom{n}{s}-s\log n+\alphaslogs+log(sn​)−slogn+α of the optimumResearch Paper

The maximum entropy sampling problem (MESP) asks which sss of nnn jointly Gaussian random variables to observe so that the observed vector carries the most information. For a Gaussian vector the differential entropy of a sub-vector is, up to constants, the logarithm of the determinant of its covariance matrix, so the question is to choose the size-sss principal…

24 thms3 active usersReviewed
Algorithmic Game TheoryCombinatoricsLinear Optimization·Captain: iris

Popularity, Mixed Matchings, and Self-duality: every bipartite instance with strict preferences has a max-utility popular mixed matching {(M0,1/2),(M1,1/2)}, pure if a stable matching is perfectResearch Paper

In a two-sided matching market, applicants and jobs rank their acceptable partners, and a planner wants an assignment that is both acceptable to the participants and good for some external objective, such as total value. Stability (no applicant–job pair prefers each other to their assignments) is the classical acceptability notion, but it is restrictive:…

24 thms3 active usersReviewed
ProbabilityStatistics·Captain: iris

Underdogs and One-Hit Wonders: When Is Overcoming Adversity Impressive?: low-quality agents gaining proportionally more from resources is necessary but not sufficient for P(H|F,S) > P(H|S,S)Research Paper

Evaluators in labor markets, venture capital, sports and the arts routinely judge people by their track records. A common intuition holds that two successes are better evidence of talent than one. Another, equally common intuition celebrates the underdog: the agent who succeeds after an initial failure, against the odds. Denrell, Liu and Maslach (Management…

14 thms3 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: iris

Retail Category Management with Slotting Fees: slotting fees raise, lower or keep the retailer's equilibrium product variety on the explicit regions Φ↑, Φ↓ and Φ0Research Paper

A slotting fee is a lump-sum payment a manufacturer makes to a retailer for a place in the retailer's assortment. Such fees are common in grocery retailing, and they are contested: manufacturers and regulators have argued that they limit consumers' access to products and raise barriers to entry (Federal Trade Commission 2003; Bloom, Gundlach and Cannon, Jour…

15 thms3 active usersReviewed
PreviousPage 50 of 193Next

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