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

1876–1900 of 4812
Open1252Completed3560All4812
🏆Completed
Bandit AlgorithmsInformation TheoryOperations Research+1·Captain: mikedeng1

Data-Based Dynamic Pricing and Inventory Control with Censored Demand and Limited Price Changes 2: Any Policy with at Most m Price Changes Has Regret at Least KT^(1/(m+1)) on a Bernoulli InstanceResearch Paper

A seller learning a demand curve normally adjusts prices as new observations arrive. A price-change limit prevents that continual adjustment: a price may have to be chosen before the seller knows which demand curve it faces, then held through a block of sales. This matters when repricing is operationally costly, constrained by contracts, or visible to…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Optimization-Based Scenario Reduction for Data-Driven Two-Stage Stochastic Optimization II: Under a Symmetric Uncertainty Law the Mean Solves the Convex Upper-Bound Scenario ProblemResearch Paper

A two-stage stochastic programme chooses a decision zzz before an uncertain parameter ξ\xiξ is revealed and pays a cost c(z;ξ)c(z;\xi)c(z;ξ). When ξ\xiξ is known only through nnn data points, or through a law with many atoms, the expected cost is expensive to optimize, and practitioners replace the law by a small set of mmm reduced scenarios. Classical scenario reduction chooses…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Robust Dynamic Pricing with Strategic Customers: Over Horizon T the Simple Robust Pricing Policy Earns at Least V*_β(x₀)/(1 + e^{−βT}/(βT))Research Paper

A seller with a fixed stock must choose prices before knowing when customers will arrive or what they will be willing to pay. If customers can wait for a later price, the seller must also account for how today's price changes their purchasing decisions. Chen and Farias study this problem with strategic customers and identify a simple inventory-based policy…

11 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization+1·Captain: mikedeng1

Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming 1: The Randomized Stochastic Gradient Method Has (1/L)E‖∇f(x_R)‖² ≤ (D_f² + σ²Σγ_k²)/Σ(2γ_k − Lγ_k²)Research Paper

Stochastic gradient methods are the standard tool for minimizing an objective that can only be accessed through noisy gradient samples. Training a machine-learning model on sampled data, simulation-based optimization, and stochastic programs with endogenous uncertainty are all of this kind. In many of these applications the objective is nonconvex: the loss…

13 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs I: Expected (α, β)-Balanced Prices Scaled by α/(1 + αβ) Earn 1/(1 + αβ) of the Expected Welfare of ALGResearch Paper

A prophet inequality compares an online decision maker, who sees random values one at a time and must decide irrevocably, with a "prophet" who sees all values in advance. The classic result of Krengel, Sucheston and Garling (1977) and Samuel-Cahn (1984) says that for a single item and independent values a single threshold earns at least half of the expected…

13 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimal Transport+1·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization and Variation Regularization II: The ∞-Wasserstein Regularizer Equals ρ Times the Mean Local Slope up to ρ²‖H‖ Plus a Boundary TermResearch Paper

In distributionally robust optimization, a decision is judged against probability laws near a nominal law rather than against the nominal law alone. The nominal law is often the empirical distribution of observed data. For a loss function, this produces a worst-case expected loss that depends on the size and geometry of the permitted changes to the data.…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Robust Sample Average Approximation 2: Pearson's χ² Test and the G-Test on a Known Finite Support, with Thresholds √(Q/N), Are Uniformly ConsistentResearch Paper

A decision made from sampled data can be sensitive to the distribution chosen to represent future uncertainty. Robust sample average approximation addresses this by optimizing against every distribution that passes a goodness of fit test, rather than against one fitted distribution. The resulting set of plausible laws is a data driven uncertainty set. Its…

6 thms3 active usersReviewed
🏆Completed
AnalysisOperations ResearchOptimization+1·Captain: mikedeng1

On the Heavy-Tail Behavior of the Distributionally Robust Newsvendor 1: Worst-Case Expected Shortage under Known First and αth Moments Equals That of a Regularly Varying Demand of Tail Index αResearch Paper

A newsvendor chooses an order quantity before seeing demand. Unsold units have no salvage value, while demand above the order quantity cannot be filled. If the demand law is unknown but a few moments are known, the decision maker may minimize cost against the worst distribution consistent with those moments. Das, Dhara and Natarajan study this…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals III: Even for I.I.D. Variables, No Nonadaptive Threshold Rule Beats the Factor 1 − 1/eResearch Paper

In a prophet inequality, a decision maker observes random rewards one at a time and must choose without seeing future realizations. The benchmark is a prophet who sees all rewards and selects their maximum. A nonadaptive threshold rule chooses a threshold for each reward before observations begin, then accepts the first arriving reward that crosses its…

10 thms3 active usersReviewed
Linear algebraNumerical AnalysisProbability+1·Captain: mikedeng1

Low Rank Approximation and Regression in Input Sparsity Time 1: A Sparse Embedding Matrix with O((r/ε)⁴ log²(r/ε)) Rows Is a (1 ± ε) Subspace Embedding for a Rank-r Matrix with Probability 9/10Research Paper

Many matrix algorithms spend most of their time reading their input. A matrix with few nonzero entries should admit routines whose cost scales with that number, rather than with the product of its dimensions. Clarkson and Woodruff study random maps that compress a matrix before a regression or low rank approximation calculation while retaining the geometric…

9 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

A Little Charity Guarantees Almost Envy-Freeness II: With Additive Valuations Such an Allocation Gives Every Agent Her Maximin Share Divided by 2 − |P|/nResearch Paper

A set of nnn agents must share a set MMM of mmm indivisible goods, each agent valuing bundles of goods by her own valuation. Two fairness notions dominate the literature. Envy-freeness up to any good (EFX), introduced by Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang (EC 2016), asks that no agent prefer another's bundle once any single good is removed…

6 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

A game-theoretic approach to computation offloading in mobile cloud computing III: Variational Solutions Are the Nash Equilibria of the Extended Cloudlet-Pricing GameResearch Paper

Mobile devices can divide work between local execution, a nearby shared cloudlet, and a remote cloud. A cloudlet has limited capacity, so one user's choice changes the delay faced by the others. Cardellini and coauthors model this as a generalized Nash equilibrium problem, in which each user's feasible choices depend on the aggregate cloudlet load. The…

8 thms3 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchOptimization·Captain: mikedeng1

Double Counting in Supply Chain Carbon Footprinting II: A Carbon Leader Paying Linear Emission-Contingent Rules That Double-Count Internally Earns Its Effort-Contracting ProfitResearch Paper

Firms increasingly account for, and offset, the greenhouse-gas emissions of their entire supply chain, not only their own operations. Emissions in a supply chain are often jointly produced: the footprint of one process (transport, packaging, a molten-bulk delivery) depends on the abatement efforts of several firms at once. When each firm is charged for…

9 thms3 active usersReviewed
🏆Completed
Algebraic TopologyComputational GeometryMachine Learning+1·Captain: mikedeng1

Persistence-Based Clustering in Riemannian Manifolds: With High Probability the Algorithm Returns as Many Clusters as the Density Has d₂-Prominent PeaksResearch Paper

Mode-seeking clustering groups data points by the peak of an underlying probability density that they "flow up" to. Methods of this kind (mean-shift, graph-based hill climbing) are widely used, but their output depends heavily on noise: a density estimated from finitely many samples has many spurious local maxima, and each of them becomes a cluster. Chazal,…

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

Twin-width I: Tractable FO Model Checking 4: Every K_t-Minor-Free Graph Has Twin-width at Most 4c_g(t)·2^(4c_g(t)+2), a Triple-Exponential Bound in tResearch Paper

Many graph classes are defined by excluding a fixed graph as a minor. A minor can be formed by deleting vertices, deleting edges, and contracting edges. Planar graphs, for example, exclude K5K_5K5​ as a minor. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant proved that every class excluding a fixed clique minor has bounded twin-width, a graph…

17 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 9: Total Completion Time Against a Maximum Cost Has at Most n_A·n_B + 1 Nondominated PairsResearch Paper

Many scheduling decisions are not owned by a single decision maker. A machine shared by two departments, a production line serving two customers, or a computing resource shared by two users must process the jobs of two agents, each of which judges a schedule by its own criterion. Agnetis, Mirchandani, Pacciarelli and Pacifici introduced this model in Schedul…

10 thms3 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchOptimization·Captain: mikedeng1

Double Counting in Supply Chain Carbon Footprinting I: With Joint Carbon Production, Every Differentiable Increasing Payment Rule That Makes the Social First-Best a Nash Equilibrium Double-CountsResearch Paper

Carbon accounting assigns emissions from a shared supply-chain process to firms that can reduce them. If more than one firm can change the same emissions, charging each firm only a share may leave each with too little incentive to abate. Caro, Corbett, Tan and Zuidwijk study the conflict between avoiding double counting in an emissions ledger and inducing…

7 thms3 active users
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

Generalized Couplings and Ergodic Rates for SPDEs and Other Markov Models: A Generalized Coupling and a Lyapunov Function Give a Unique Invariant Measure and Wasserstein Ergodic RatesResearch Paper

Many Markov processes that arise as solutions of stochastic partial differential equations, stochastic delay equations, or other infinite-dimensional models are not strong Feller: their transition probabilities from two nearby starting points can be mutually singular. For such processes convergence to equilibrium cannot hold in total variation, and the…

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

Steady-State Analysis of the Join-the-Shortest-Queue Model in the Halfin-Whitt Regime 1: Diffusion-Scaled Stationary Queue Lengths Have Expectations Bounded Uniformly in nResearch Paper

Join-the-shortest-queue (JSQ) is the load-balancing rule in which each arriving job is sent to a server with the fewest jobs. It is a baseline in the design of server farms and data centers, and in the many-server Halfin–Whitt regime, where the load per server approaches one at rate 1/n1/\sqrt n1/n​, it combines near-full utilization with vanishing waiting.…

17 thms3 active usersReviewed
Graph TheoryOperations ResearchProbability+1·Captain: mikedeng1

Graphon Mean Field Systems IV: Law of Large Numbers for Particle Systems on Percolated Not-So-Dense Graphs With nβₙ → ∞Research Paper

Large networks are often modeled through a graphon, a measurable function that records how likely two labeled vertices are to interact. For interacting diffusions, this lets one ask whether a finite random network has a predictable population limit. Bayraktar, Chakraborty and Wu study that question for graphon weighted systems, including graphs obtained by…

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

Twin-width I: Tractable FO Model Checking 3: Grid Minor Theorem for Twin-width — t-Twin-Ordered Matrices Are (2t+2)-Mixed Free, and t-Mixed Free Matrices Have Twin-width at Most 4c_t·α^(4c_t+2)Research Paper

Twin-width is a graph and matrix invariant introduced by Bonnet, Kim, Thomassé and Watrigant (J. ACM 69(1), Article 3, 2021). Classes of bounded twin-width include bounded tree-width and clique-width graphs, proper minor-closed classes, posets of bounded width, and permutations avoiding a fixed pattern; on all of them, first-order model checking is…

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

Scheduling Problems with Two Competing Agents 3: The Least-Cost Backward Rule Gives a Nondominated Schedule Minimizing Total Completion Time Under a Maximum-Cost BoundResearch Paper

Many scheduling situations involve more than one decision maker sharing a resource. Two departments of a firm may share a machine shop, two clients may share a contractor, or two users may share a processor, and each cares only about how its own jobs are served. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) introduced a systematic…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Dynamic Pricing with Loss-Averse Consumers and Peak-End Anchoring: Every Optimal Price Path Converges Monotonically to a Steady State Set by the Initial Minimum PriceResearch Paper

Firms that change prices over time face customers who remember past prices. A large empirical literature in marketing documents reference price effects: demand depends not only on the current price but on how that price compares with a price the customer expects, and losses (prices above the reference) weigh more than gains of the same size, the loss…

14 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems 1: Steepest Descent Can Need ε^(−2+τ) Iterations to Reach |g| ≤ εResearch Paper

Steepest descent is the oldest method for unconstrained minimization: to minimize a smooth function fff, it moves from the current point xkx_kxk​ along the negative gradient −gk=−∇f(xk)-g_k = -\nabla f(x_k)−gk​=−∇f(xk​). It is the prototype of every first-order method, and its worst-case evaluation complexity — how many iterations it may need before the gradient norm drops below a…

10 thms3 active usersReviewed
🏆Completed
Functional AnalysisNumerical AnalysisOperations Research+1·Captain: mikedeng1

Some Numerical Experiments with Variable-Storage Quasi-Newton Algorithms: The Update (A.7) Is the Unique Least-Change Self-Adjoint Secant Update in a Weighted Hilbert–Schmidt NormResearch Paper

Quasi-Newton methods replace a costly exact Hessian with an operator updated from successive changes in position and gradient. A secant update must map the observed step sss to the observed gradient difference yyy. Many operators satisfy that one equation, so the choice of update needs another criterion. Gilbert and Lemaréchal's working paper studies…

14 thms3 active usersReviewed
PreviousPage 76 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5240500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36735482
5NINickrobbins953289156
6VEvebis25800
7FIfizzyinc321725
8SHshivm17510
9KMkmehltretter82972263
10SCShuze Chen9455324

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