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

51–75 of 1285
Open1285Completed3527All4812
Complexity TheoryLinear OptimizationOperations Research·Captain: mikedeng1

On Linear Characterizations of Combinatorial Optimization Problems I: A Small Facial Description in NP Puts the Decision Problem in co-NPResearch Paper

Polyhedral combinatorics attacks a combinatorial optimization problem by replacing its finite set of feasible solutions with the convex hull of that set and describing the hull by linear inequalities. Once such a description is known, the problem becomes a linear program, and linear programming duality supplies optimality certificates. For matchings,…

12 thms5 active usersReviewed
Computational GeometryLinear OptimizationOperations Research+1·Captain: mikedeng1

Linear Programming in Linear Time When the Dimension Is Fixed: Fixed-Dimension LP Feasibility Decided in Linear Time on the Real RAMResearch Paper

A linear program asks for a point x∈Rdx\in\mathbb{R}^dx∈Rd minimizing cTxc^TxcTx subject to nnn linear inequalities ∑j=1daijxj≥bi\sum_{j=1}^d a_{ij}x_j\ge b_i∑j=1d​aij​xj​≥bi​. Many problems in computational geometry and statistics are linear programs with few variables and very many constraints: separating two point sets by a line or plane, fitting a line in the Chebyshev (L∞L_\inftyL∞​) norm, finding the…

16 thms5 active usersReviewed
Control TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Resource Allocation and Cross-Layer Control in Wireless Networks IV: The Energy-Constrained Control AlgorithmTextbook

Battery-powered and energy-harvesting wireless devices cannot treat transmission power as free: a control algorithm that maximizes throughput without regard to energy will drain a device long before the network's other resources are exhausted. Chapter 6 of Georgiadis, Neely & Tassiulas's survey Resource Allocation and Cross-Layer Control in Wireless Networks…

15 thms5 active users
CombinatoricsLinear Optimization·Captain: Shuze Chen

The Polynomial Hirsch ConjectureOpen Problem

The simplex method walks along edges of a polytope from vertex to vertex. Whether any pivot rule could ever make that walk short in the worst case is governed by a prior, purely geometric question: how far apart, in the edge graph, can two vertices of a polytope be? Warren Hirsch conjectured in 1957 that the diameter of a ddd-dimensional polytope with nnn facets…

82 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
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
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
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
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
Bandit AlgorithmsOperations ResearchProbability+2·Captain: iris

Regret Analysis of a Markov Policy Gradient Algorithm for Multiarm Bandits: SAMBA Converges to the Optimal Arm Almost Surely with Regret at Most NαΔlog⁡T+Q\frac{N}{\alpha\Delta}\log T + QαΔN​logT+QResearch Paper

Policy-gradient methods adjust the probabilities with which a learner picks actions by following an estimated gradient of its expected reward. They underlie much of modern reinforcement learning (Williams 1992; Sutton–Barto 2018), yet regret guarantees for them are scarce even in the simplest setting, the stochastic multi-armed bandit, where the benchmark…

24 thms4 active usersReviewed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: iris

Risk Averse Stochastic Programming: Time Consistency and Optimal Stopping: The Nested-Risk Snell Envelope Is the Optimal Stopping Value, Attained by the First Time It Meets the RewardResearch Paper

Optimal stopping asks when to stop a reward process Z0,…,ZTZ_0,\dots,Z_TZ0​,…,ZT​ so as to make the stopped reward ZτZ_\tauZτ​ as large as possible. In its classical form the criterion is the expectation E[Zτ]\mathbb E[Z_\tau]E[Zτ​], and the solution is the Snell envelope: the value process obtained by comparing, at each date, the reward for stopping now with the conditional expectation…

22 thms4 active usersReviewed
Machine LearningOperations ResearchReinforcement Learning+1·Captain: iris

Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis: Synchronous Q-Learning Is ε-Accurate in ℓ∞ with Probability 1−δ Once T ≥ c₃·log⁴T·log(|S||A|T/δ)/((1−γ)⁴ε²)Research Paper

Q-learning (Watkins and Dayan, 1992) is the textbook model-free reinforcement learning method: it estimates the optimal action-value function of a Markov decision process directly from samples, without estimating the transition kernel. Understanding how many samples it needs is the basic statistical question about the algorithm, and it decides whether plain…

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

The Pareto Frontier of Inefficiency in Mechanism Design: Second-Price Mechanisms with Relative Reserves Exactly Attain the PoA/PoS Frontier of Anonymous Task-Independent SchedulingResearch Paper

Scheduling tasks on unrelated machines is the problem with which algorithmic mechanism design began (Nisan and Ronen, 1999). The machines are selfish: each one knows its own processing times and may misreport them, and a mechanism must allocate the tasks and pay the machines so that the makespan stays low. For two decades the field studied truthful…

36 thms4 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Heavy-Traffic Universality of Redundancy Systems with Assignment Constraints: The Scaled Stationary Job Counts Collapse onto One Exponential Variable Times the Critical Arrival ProportionsResearch Paper

Parallel-server systems in data centres cannot send every job everywhere: data locality and license restrictions tie each job to a subset of the servers. Redundancy scheduling copes with this by replicating a job to all of its compatible servers. Under cancel-on-completion (c.o.c.) the other replicas are discarded when the first one finishes; under cancel-on…

54 thms4 active usersReviewed
Algorithmic Game TheoryComplexity TheoryMechanism Design+1·Captain: iris

Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions: Computing a Welfare-Maximizing Core Outcome Is Σ₂ᵖ-HardResearch Paper

Many markets trade packages of indivisible goods between several buyers and several sellers at once: airport time slots, spectrum licences, transport capacity, emission permits. Such a market is a combinatorial exchange. Its operator chooses who trades which package and at which prices, and wants the outcome to be stable: no group of participants should be…

16 thms4 active usersReviewed
Convex OptimizationOperations ResearchProbability·Captain: iris

Stochastic Localization Methods for Convex Discrete Optimization via Simulation: Shrinking Uniform Sampling Returns an (ε, δ)-PGS Solution at Cost O(ε⁻² log(N/δ) + N)Research Paper

Many operational decisions are a single integer: the number of trucks to recruit for a region, the number of staff for an event, the number of servers in a queueing system. When the performance of each choice can only be estimated by simulation, finding a good choice is a problem of optimization via simulation: each evaluation of a candidate returns a noisy…

44 thms4 active usersReviewed
PreviousPage 3 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