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

401–425 of 4812
Open1285Completed3527All4812
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Introduction to Linear Optimization X: Max-Flow Min-CutTextbook

How much flow can be sent from a source sss to a sink ttt through a network with arc capacities uij∈(0,∞]u_{ij}\in(0,\infty]uij​∈(0,∞] — and what certifies that no more is possible? This mission formalizes §7.4-7.5 of Bertsimas & Tsitsiklis. The circulation calculus of §7.4 supplies the two structural tools: the flow decomposition theorem (Lemma 7.1 — every nonzero nonnegative…

14 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms XIII: Pure Exploration and Best-Arm IdentificationTextbook

Sometimes reward during learning is irrelevant — a pharmaceutical company running phase-II trials only cares about identifying the best treatment, as quickly and as reliably as possible. Chapter 33 of Lattimore–Szepesvári formalizes fixed-confidence best-arm identification: a policy together with a stopping time τ\tauτ and a recommendation must be sound (wrong…

50 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms IV: Bernoulli Bandits and KL-UCBTextbook

When rewards are binary — a click or no click, a cure or no cure — the subgaussian machinery of Missions I–III is not tight: the variance of a Bernoulli arm degrades near the boundary of [0,1][0,1][0,1], and the correct exponential rate is governed by the binary relative entropy d(p,q)=plog⁡pq+(1−p)log⁡1−p1−qd(p,q) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}d(p,q)=plogqp​+(1−p)log1−q1−p​ rather than a squared distance.…

28 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms VI: Information-Theoretic FoundationsTextbook

Every lower bound in bandit theory rests on one question: how hard is it to tell two probability measures apart from a sample? The answer is quantified by the relative entropy D(P,Q)D(P,Q)D(P,Q), and the sharpest elementary tool is the Bretagnolle–Huber inequality: for any event AAA, P(A)+Q(Ac)≥12exp⁡(−D(P,Q))P(A) + Q(A^c) \ge \frac{1}{2}\exp(-D(P,Q))P(A)+Q(Ac)≥21​exp(−D(P,Q)) — no test can distinguish PPP from QQQ with total…

5 thms5 active usersReviewed
Algorithmic Game TheoryComplexity TheoryOperations Research·Captain: iris

Pure Nash Equilibria: Hard and Easy Games: Deciding Whether a Game Has a Pure Nash Equilibrium Is NP-Complete, Even for Graphical Games with 3-Bounded Neighborhood and Three ActionsResearch Paper

A pure Nash equilibrium is a choice of one action per player from which no player can gain by changing only her own action. Unlike mixed equilibria, which exist in every finite game by Nash's theorem, pure equilibria may fail to exist, so deciding whether one exists is a basic algorithmic question about any game model. It matters most for games with many…

30 thms4 active usersReviewed
Dynamic ProgrammingOperations ResearchProbability·Captain: iris

Markov Decision Processes with Applications to Finance XV: The Perpetual American Put Is the Smallest Superharmonic Majorant of the Payoff and Is Exercised Below a ThresholdTextbook

An American option may be exercised at any time up to its expiry, so its fair price is the value of an optimal stopping problem under the risk-neutral measure, and its optimal exercise rule is an optimal stopping time. Chapter 11 of Bäuerle and Rieder's Markov Decision Processes with Applications to Finance (Springer, 2011) treats this problem as a Markov…

26 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: iris

Markov Decision Processes with Applications to Finance VIII: The Binomial Mean-Risk Problem with Average-Value-at-Risk Has an Explicit Value and a Stationary Optimal PolicyTextbook

Markowitz's mean-variance criterion measures the risk of a portfolio by the variance of its terminal wealth. The variance penalizes gains and losses alike, which is one of its drawbacks as a measure of risk. The axiomatic theory of coherent risk measures (Artzner, Delbaen, Eber and Heath, 1999) replaced it in much of risk management by quantities that look…

13 thms4 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: iris

Markov Decision Processes with Applications to Finance V: Under Regime Switching Ordered in the Increasing Concave Order the Value Rises and Consumption Falls with the RegimeTextbook

Return distributions of risky assets are not constant over time: they shift with the business cycle, monetary policy, regulation or catastrophes. A standard way to capture this in portfolio theory is a regime-switching (Markov-modulated) market, in which an observable finite-state Markov chain, the environment process, selects the distribution of next…

33 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: iris

Markov Decision Processes with Applications to Finance XI: Contracting Models Satisfy Value Iteration, Have a Unique Fixed Point and an Optimal Stationary PolicyTextbook

Infinite-horizon Markov Decision Processes with discounted rewards are the standard model for sequential decisions under uncertainty in operations research, economics and finance: inventory and cash management, consumption and investment, dividend payout, replacement and maintenance. Whether the problem has a usable solution depends on two questions. Is the…

12 thms4 active usersReviewed
Machine LearningOperations ResearchProbability+1·Captain: iris

Optimal Policies for Dynamic Pricing and Inventory Control with Nonparametric Censored Demands: Trisection Search with a Difference Estimator Has √T·ln²T Regret for Strongly Concave RewardsResearch Paper

A retailer that sets both a price and a stock level each period, without knowing how demand responds to price or how demand fluctuates, has to learn while selling. In the lost-sales setting the learning problem is harder than in pure pricing: when a period ends with empty shelves, the firm sees only its sales, not the demand that went unmet. Joint pricing…

13 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: iris

Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits: LASSO Batch Greedy Learning Has Regret at Most O~(M3/2Ts0(T/s0)1/(2(2M−1))/(γρ))\tilde O(M^{3/2}\sqrt{Ts_0}(T/s_0)^{1/(2(2^M-1))}/(\gamma\rho))O~(M3/2Ts0​​(T/s0​)1/(2(2M−1))/(γρ))Research Paper

Personalized medicine, online advertising and news recommendation all choose among a few actions using a very large number of features per decision, of which only a few matter. They also rarely update a policy after every decision: clinical trials report in stages, and production recommenders are retrained in batches. Dynamic batch learning models this…

44 thms4 active usersReviewed
Complexity TheoryOperations ResearchOptimization+1·Captain: iris

Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems: Free-Order Prophets Admits an EPTAS, a t(ε)·poly(n)-Time (1 − ε)-Approximate OrderResearch Paper

In Free-Order Prophets a decision maker faces nnn independent non-negative random values with known laws, chooses in advance the order in which to inspect them, and on seeing each value must stop and take it or move on for good. The problem models selection with a sequence the decision maker controls: sequencing interviews, or inspecting alternatives whose…

43 thms4 active usersReviewed
Operations ResearchProbabilityRevenue Management and Pricing+1·Captain: iris

Assortment Optimization Under the Multi-Purchase Multinomial Logit Choice Model: A Deterministic Algorithm Earns 1 − ε of Optimal Revenue in Time n^O(m²/ε) When Each Customer Buys at Most m ProductsResearch Paper

In many retail settings a customer leaves with several products, not one: a basket of groceries, a set of streaming titles, a bundle of software modules. Classical discrete choice models used in revenue management, above all the multinomial logit (MNL) model, describe a customer who buys at most one product. Bai, Feldman, Segev, Topaloglu and Wagner (author…

18 thms4 active usersReviewed
🏆Completed
Information TheoryProbability·Captain: iris

From Classical to Quantum Shannon Theory X: The Private Information of Classical Wiretap Channels Is AdditiveTextbook

A dynamic information measure assigns a number to a channel rather than to a fixed random variable: the largest amount of some kind of correlation that one use of the channel can create. Such a measure is useful as a capacity formula only if it is additive, meaning that the value for two independent channels used together equals the sum of the individual…

20 thms4 active usersReviewed
🏆Completed
Information TheoryProbability·Captain: iris

From Classical to Quantum Shannon Theory XX: Feedback Does Not Increase the Capacity of a Classical ChannelTextbook

A sender who could watch the receiver's screen while transmitting would seem to have an advantage: after each channel use the sender knows exactly which symbol arrived and could adapt the next input to correct errors. Feedback of this kind does help in practice (it simplifies coding schemes and improves error exponents), and it does increase the capacity of…

25 thms4 active usersReviewed
🏆Completed
Information TheoryProbability·Captain: iris

From Classical to Quantum Shannon Theory XIII: Shannon’s Channel Capacity Theorem: C(N)=max⁡pXI(X;Y)C(\mathcal N) = \max_{p_X} I(X;Y)C(N)=maxpX​​I(X;Y)Textbook

A classical channel is the simplest model of a noisy communication link: a sender feeds a letter xxx into it and the receiver sees a letter yyy drawn at random according to a fixed conditional distribution pY∣X(y∣x)p_{Y|X}(y|x)pY∣X​(y∣x). Telephone lines, storage media and radio links are modelled this way, and the question of how fast information can be sent through such a link…

24 thms4 active usersReviewed
🏆Completed
Information TheoryProbability·Captain: iris

From Classical to Quantum Shannon Theory XII: Shannon Compression: The Entropy Is the Smallest Achievable RateTextbook

How many bits per symbol does it take to store the output of a random source so that it can be recovered with vanishing error? Shannon answered this in 1948: the entropy of the source, and no fewer (Shannon 1948). The answer is the first operational meaning of entropy, and every later coding theorem in classical and quantum information theory, channel…

12 thms4 active usersReviewed
Machine LearningOperations ResearchStatistics·Captain: iris

Active Learning for Contextual Search with Binary Feedback: Trisection Search with Margin-Based Active Learning Estimates the Value Function to Accuracy ε with Õ(d³/ε²) Queries among Õ(d³/ε³) ContextsResearch Paper

Many operational decisions are made one item at a time with only a yes/no answer as feedback. A clinic offers a dosage to an arriving patient and learns whether it was adequate; an ad platform posts a price and learns whether it was accepted. Each item carries a context x∈Rdx\in\mathbb R^dx∈Rd and an unobserved valuation that depends linearly on it. A query is…

22 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: iris

Technical Note—On Dynamic Pricing with Covariates: UCB Pricing Has Regret at Most 4ḡp̄γ̄√(Td log((2d+T)/(2d))) + p̄D̄ for Arbitrary CovariatesResearch Paper

A retailer that sets prices online sees, before each sale, information about the customer, the product or the market: a covariate vector. Demand depends on the price and on these covariates through parameters the seller does not know, so the seller must learn the demand model while pricing. This dynamic pricing with covariates problem is a standard model in…

11 thms4 active usersReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

In Congestion Games, Taxes Achieve Optimal Approximation: Taxes From the Poisson Relaxation of Minimum Social Cost Have Price of Anarchy at Most the Worst Hardness Factor sup ρ_ℓResearch Paper

In an atomic congestion game (Rosenthal, 1973) each of NNN agents chooses a set of resources, such as the edges of a route, and the cost of a resource depends on how many agents use it. Selfish choices are inefficient: the price of anarchy (Koutsoupias and Papadimitriou, 1999) compares the social cost of the worst equilibrium with the minimum social cost, and…

39 thms4 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Supermodularity in Two-Stage Distributionally Robust Optimization: With a Supermodular Second-Stage Cost, the Two-Stage DRO Problem Is Equivalent to a Linear Program over K(2n+1) Worst-Case PointsResearch Paper

Two-stage decisions under uncertainty are a basic model of operations planning: capacities, inventories or facility locations are fixed first, demand or yield is observed, and a recourse decision is then taken at the cost of a linear program. When the distribution of the uncertainty is known only through a few statistics, distributionally robust optimization…

27 thms4 active usersReviewed
Operations ResearchOptimizationProbability+1·Captain: iris

The Stability of MNL-Based Demand Under Dynamic Customer Substitution and Its Algorithmic Implications: A Randomized (1 − ε)-Approximation Scheme for Dynamic Assortment PlanningResearch Paper

A retailer chooses which products to carry and how many units of each to stock, under a shelf or warehouse capacity, before a selling season in which inventory is not replenished. Customers who find their favourite product sold out may buy another one instead: this dynamic substitution couples the demand of all products through the stock-out history.…

44 thms4 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: iris

Processing Networks XIX: Increment-Dominated Monotone Paths Have Uniformly-on-Compacts Convergent SubsequencesTextbook

The stability theory of processing networks developed in Dai and Harrison's Processing Networks: Fluid Models and Stability (Cambridge University Press, 2020; pre-publication draft of 2020-4-2 at spnbook.org) rests on fluid limits: the queue lengths, cumulative allocations and other path-valued quantities of a stochastic network are scaled down in space and…

9 thms4 active usersReviewed
Algorithmic Game TheoryComputational ComplexityEconomics+1·Captain: iris

The Complexity of Pacing for Second-Price Auctions: Finding an Approximate Pacing Equilibrium Is PPAD-HardResearch Paper

Online advertising platforms sell billions of impressions through auctions, and most advertisers face a budget for a whole campaign rather than for a single auction. Ad platforms handle this with budget pacing: each advertiser's bids are scaled down by a multiplier so that spending tracks the budget. When every advertiser paces at once, the multipliers…

26 thms4 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Processing Networks XV: A State-Dependent Foster–Lyapunov Drift Condition Implies Positive Recurrence of a Discrete-Time Markov ChainTextbook

Stability of a stochastic processing network (a queueing network, a switch, a wireless scheduler) is usually proved by representing the network as a Markov chain on a countable state space and showing that the chain is positive recurrent: every state is revisited after a finite expected time. Dai and Harrison's Processing Networks: Fluid Models and Stability…

10 thms4 active usersReviewed
PreviousPage 17 of 193Next

Top contributors

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