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

101–125 of 1285
Open1285Completed3527All4812
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: iris

The Minimax Property in Infinite Two-Person Win-Lose Games: a game is totally minimax if and only if it has no subgame isomorphic to the larger number gameResearch Paper

Von Neumann's minimax theorem says that in a finite two-person zero-sum game, committing first to a mixed strategy costs nothing: max⁡pmin⁡qπmix(p,q)=min⁡qmax⁡pπmix(p,q)\max_p\min_q\pi_{\mathrm{mix}}(p,q)=\min_q\max_p\pi_{\mathrm{mix}}(p,q)maxp​minq​πmix​(p,q)=minq​maxp​πmix​(p,q). Once the players have infinitely many pure strategies this can fail. In the larger number game, where each player names a positive integer and the larger…

16 thms4 active usersReviewed
Machine LearningReinforcement LearningStatistics·Captain: iris

Foundations of Reinforcement Learning XVIII: Freedman's Inequality and Its Multiplicative Corollary for Nonnegative SequencesTextbook

Interactive learning produces data that is not independent: the decision at round ttt depends on everything observed before it. Regret and estimation guarantees in the lecture notes of Foster and Rakhlin (arXiv:2312.16730) therefore rest on concentration for adapted sequences rather than for i.i.d. samples. Appendix A.1 of the notes collects the inequalities…

9 thms4 active usersReviewed
Machine LearningReinforcement LearningStatistics·Captain: iris

Foundations of Reinforcement Learning VIII: Exponential Weights Has Regret ≲Tlog⁡∣F∣\lesssim \sqrt{T\log|F|}≲Tlog∣F∣​ for Bounded Losses and ≲log⁡∣F∣\lesssim \log|F|≲log∣F∣ for Square and Log LossTextbook

Foster and Rakhlin's lecture notes Foundations of Reinforcement Learning and Interactive Decision Making build their theory of decision making on one recurring device: an estimator that keeps small error on any sequence of data, used as a subroutine by an algorithm that chooses decisions. That device is online learning, and the basic algorithm for it is Expo…

15 thms4 active usersReviewed
Algorithmic Game TheoryAnalysisOperations Research·Captain: iris

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games: Polynomial Games of Degree d With No α-PNE for Any α < α(d), Where α(d) ≥ √d/(2 ln d) for Large dResearch Paper

Weighted congestion games model players of different sizes sharing resources whose cost grows with load: traffic of different volumes on network links, jobs of different lengths on machines. Rosenthal (1973) showed that unweighted congestion games always have a pure Nash equilibrium, but weighted games may have none, already with polynomial costs. The…

28 thms4 active usersReviewed
CombinatoricsGraph TheoryOperations Research·Captain: iris

Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k: Cut-Sets of Value OPT_k-cut Are Recovered by Every Minimum (S, T)-Terminal Cut for Some |S|, |T| ≤ 2k − 1Research Paper

Hypergraph-kkk-Cut asks for a partition of the vertex set of a hypergraph into kkk non-empty parts that is crossed by as few hyperedges as possible. It models clustering and partitioning tasks in which an interaction involves more than two objects (VLSI netlists, multi-way relations in data). For graphs, the number of optimum kkk-partitions is polynomial for…

25 thms4 active usersReviewed
Actuarial ScienceEconomicsOperations Research+1·Captain: iris

An Unexpected Stochastic Dominance: Pareto Distributions, Dependence, and Diversification: A Weighted Average of Negatively Associated Super-Pareto Losses Stochastically Dominates a Single LossResearch Paper

Diversification is the default advice of risk management: spreading a unit of exposure over several independent losses reduces risk. For losses with finite mean this is true in a strong sense: if X1,…,XnX_1,\dots,X_nX1​,…,Xn​ are identically distributed with finite mean, the weighted average ∑iθiXi\sum_i\theta_iX_i∑i​θi​Xi​ can never be larger than a single X1X_1X1​ in first-order stochastic…

20 thms4 active usersReviewed
Operations Research·Captain: Shuze Chen

Dynamic Stochastic Matching Under Limited Time: Constant-factor reward approximation on arbitrary and bipartite graphsResearch Paper

A matching platform must decide whether to pair available agents now or wait for a more valuable partner. Waiting creates an opportunity and a risk: an agent may leave before that partner arrives. Ride sharing, service exchanges and matching markets motivate models in which arrivals continue indefinitely and departure times are not announced in advance. A…

23 thms4 active usersReviewed
Complexity TheoryDynamical SystemsLinear Optimization+1·Captain: iris

Robust-to-Dynamics Optimization: With ρ(G) < 1, P Bounded and 0 ∈ int P, S = S_r for a Polynomial-Time-Computable r, and R-LD-LPs with ρ(G) ≤ ρ* < 1 Are Solvable in Polynomial TimeResearch Paper

A linear program assumes that a decision, once taken, stays where it was put. In many applications the decision is an initial state that then evolves under known dynamics: a portfolio drifting under a linear model of returns, an inventory or production profile propagated by a transition matrix, the state of a controlled system after its input is fixed.…

40 thms4 active usersReviewed
AlgebraAlgebraic GeometryOptimization·Captain: iris

Sums of Separable and Quadratic Polynomials: Nonnegative SPQ Polynomials in n Variables of Degree d Are All Sums of Squares iff n = 1, d = 2, or (n, d) = (2, 4)Research Paper

Deciding whether a real polynomial is nonnegative on Rn\mathbb R^nRn is NP-hard already in degree 444, while deciding whether it is a sum of squares (sos) is a semidefinite program (Theorem 1.2 of the paper, after Choi–Lam–Reznick and Parrilo). Every sos polynomial is nonnegative, so sos relaxations are the standard tool of polynomial optimization, and their…

26 thms4 active usersReviewed
Operations ResearchProbability·Captain: iris

Probabilistic Bounds on the k-Traveling Salesman Problem and the Traveling Repairman Problem: The Expected k-TSP Length Among n Uniform Points Is Θ((k−1)·n^(−(1+1/(k−1))/2)) for All 2 ≤ k ≤ nResearch Paper

The kkk-traveling salesman problem (kkk-TSP) asks for the shortest path through some kkk of nnn given points, with the choice of points left to the optimizer. It models routing with selective service, where a vehicle serves only part of its demand, and it is a building block of approximation algorithms for the traveling repairman problem. For the full tour, the…

17 thms4 active usersReviewed
Machine LearningOperations ResearchProbability·Captain: iris

Marrying Stochastic Gradient Descent with Bandits: Learning Algorithms for Inventory Systems with Fixed Costs: the (δ,S) learning algorithm has regret O(log N √N) over N epochsResearch Paper

Periodic-review inventory control with a fixed ordering cost is a basic model of operations management: every order costs K>0K>0K>0 regardless of its size, so a firm orders in batches and the optimal policy is an (s,S)(s,S)(s,S) policy rather than a base-stock level (Scarf 1960; Zheng 1991). In practice the demand distribution is unknown and, when unmet demand is lost,…

41 thms4 active usersReviewed
Dynamic ProgrammingOperations ResearchProbability·Captain: iris

Asymptotically Optimal Lagrangian Policies for Multi-Warehouse, Multi-Store Systems with Lost Sales: the SLaBS policy's expected loss is O(√(min{M,N}·T·N·log(TN)))Research Paper

Retailers with many stores often hold a finite stock of a product in a few distribution centres and ship it to the stores over a selling season, with no replenishment of the centres themselves: seasonal goods, fashion, end-of-life products. Unmet store demand is lost. The decision is how much to send to each store in each period, from which warehouse,…

29 thms4 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Appointment Scheduling for Multiple Servers: the phase-type recursion gives the exact waiting-time and makespan laws and the cost of every schedule of the D/PH/s appointment systemResearch Paper

An appointment schedule fixes in advance when each of nnn clients should arrive for a service of random length. Clinics, MRI suites, legal counselling and visa offices all use one, and the schedule trades off clients' waiting time against the idle time and overtime of the servers. Pooling physicians or machines so that any client can be served by any of sss serv…

46 thms4 active usersReviewed
EconomicsOptimal TransportProbability·Captain: iris

Decision Making Under Model Uncertainty: Fréchet–Wasserstein Mean Preferences: the multiplier utility has a quantile minimizer and a 1/θ expansion around barycentric expected utilityResearch Paper

A decision maker often receives several probability models for one uncertain payoff, one from each expert or data source, and cannot say which is right. The standard responses are the multiplier preferences of Hansen and Sargent (2001) and the variational preferences of Maccheroni, Marinacci and Rustichini (2006): evaluate the payoff under the worst model,…

21 thms4 active usersReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: Shuze Chen

Pacing Equilibrium in First Price Auction Markets: Existence, uniqueness, and revenue maximization of first price pacing equilibriaResearch Paper

An advertiser buying many impressions must decide how to distribute a limited budget across auctions. Bidding the full value in every auction can exhaust the budget before all opportunities have been considered. A pacing multiplier scales an advertiser's bids by one common factor. The resulting allocation depends on other advertisers' multipliers as well as…

15 thms4 active usersReviewed
AnalysisConvex OptimizationOptimization·Captain: iris

Lipschitz Behavior of Solutions to Convex Minimization Problems: Solutions and Lagrange Multipliers Are Pseudo-Lipschitz in (p,y,A)(p, y, A)(p,y,A) When the Matrix of Generalized Second Derivatives Is SurjectiveResearch Paper

A convex program is rarely solved once. Its data are estimates, its right-hand sides are budgets that change, and the constraint matrix itself may be uncertain. Sensitivity analysis asks how the solution and the Lagrange multiplier move when the data move. For smooth problems, the classical answer is the implicit function theorem applied to the optimality…

35 thms4 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: Shuze Chen

Distributionally Robust Conditional Quantile Prediction with Fixed Design: Concentration of the surrogate residual distributionResearch Paper

A conditional quantile describes a level of a response that is exceeded with a specified probability after its explanatory variables are fixed. Such predictions enter inventory decisions when demand depends on prices, promotions, or product characteristics. These explanatory variables may be designed or selected deliberately. Treating their historical…

20 thms4 active usersReviewed
Operations Research·Captain: Shuze Chen

Perishable Inventory Theory: A Review: Convex costs and age-sensitive optimal orderingResearch Paper

Perishability makes inventory age matter. Two warehouses with the same total stock can face different expiration risks and choose different replenishments. Nahmias’ 1982 review collects structural results for these decisions and contrasts fixed shelf lives with random lifetimes and proportional decay.

37 thms4 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: Shuze Chen

Dynamic Programs with Shared Resources and Signals: Dynamic Fluid Policies and Asymptotic Optimality: Asymptotic optimality of feasible dynamic fluid policiesResearch Paper

Many sequential allocation problems combine numerous individually small projects with a common capacity constraint. A firm may allocate capital across investments, inventory across locations, or service opportunities across competing activities. Each local decision changes future rewards and local states. At the same time, a common observed signal can…

22 thms4 active usersReviewed
Convex OptimizationMachine LearningOperations Research+1·Captain: Shuze Chen

Shape-Constrained Regression Using Sum of Squares Polynomials: Almost-sure consistency of convex sum-of-squares estimatorsResearch Paper

Regression estimates an unknown relationship between features and responses from noisy observations. In many applications, a qualitative property of that relationship is known before data are collected. A production response may exhibit convexity, or a response may have a known directional derivative bound. Enforcing such information throughout a continuous…

18 thms4 active usersReviewed
Operations ResearchOptimizationProbability·Captain: Shuze Chen

Pandora’s Box Problem with Order Constraints: Optimal threshold search on treesResearch Paper

A searcher comparing possible hires, research directions, or other alternatives may have to pay to learn each alternative's value. Only the best inspected alternative is eventually selected, while every inspection cost is paid. When access to one alternative requires investigating another first, a locally unattractive inspection may unlock a valuable…

12 thms4 active usersReviewed
Operations ResearchOptimization·Captain: Shuze Chen

Assortment Planning for Recommendations at Checkout Under Inventory Constraints: Quarter-competitive online recommendations with polynomial runtimeResearch Paper

A recommendation at checkout can earn immediate revenue while consuming inventory that would have made later recommendations possible. A customer shopping for a table may also buy chairs, but a later customer who wanted those chairs as her primary purchase may leave if they have sold out. The decision therefore affects both direct sales and future…

20 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: Shuze Chen

Matching While Learning: Asymptotically optimal regret for decentralized matchingResearch Paper

A service platform may know which kinds of jobs are available while still learning the abilities of new workers. An assignment then has two effects: it produces a reward and supplies information that can improve later assignments. Limited job supply couples these decisions across workers. Sending one worker to a useful learning task consumes capacity that…

16 thms4 active usersReviewed
Machine LearningOperations ResearchProbability·Captain: Shuze Chen

Nonparametric Learning Algorithms for Joint Pricing and Inventory Control with Lost Sales and Censored Demand: Nearly square-root regret for SALAResearch Paper

A retailer choosing both a price and an inventory target faces two coupled decisions. A higher price changes customer demand, while a smaller inventory target hides demand that exceeds available stock. The retailer observes sales, but cannot count customers who leave empty-handed. This makes even the realized lost-sales penalty unavailable as a learning…

15 thms4 active usersReviewed
CombinatoricsComplexity TheoryComputational Complexity·Captain: mikedeng1

Kurodoko is NP-Complete: Deciding the Solvability of Kurodoko Puzzles Is NP-CompleteResearch Paper

Kurodoko ("where are the black squares?") is a pen-and-paper logic puzzle published by Nikoli. Its rules are short: colour some squares of a grid black so that the numbered squares stay white, no two black squares touch, the white squares stay connected, and every number counts the white squares it can see along its row and column. The computational…

15 thms4 active usersReviewed
PreviousPage 5 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