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.

3568 completed missions

Missions

2326–2350 of 3568
Open1244Completed3568All4812
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Introduction to Linear Optimization I: Polyhedra and Basic Feasible SolutionsTextbook

Every linear programming problem asks to minimize a linear cost c′xc'xc′x over a polyhedron — a set of the form P={x∈Rn∣Ax≥b}P = \{x \in \mathbb{R}^n \mid Ax \ge b\}P={x∈Rn∣Ax≥b}, or in standard form {x∣Ax=b, x≥0}\{x \mid Ax = b,\ x \ge 0\}{x∣Ax=b, x≥0}. Chapter 2 of Bertsimas–Tsitsiklis develops the geometry of these feasible sets, and its central achievement is making the intuitive notion of a "corner point"…

9 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: Shuze Chen

Bandit Algorithms I: Concentration of MeasureTextbook

How quickly does the empirical mean of independent random variables concentrate around the true mean? This question is the analytic engine of the entire theory of stochastic bandits: every optimistic algorithm (Explore-Then-Commit, UCB and its relatives) is calibrated by a tail bound on the sample mean. This mission formalizes the subgaussian framework of…

2 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: tianyipeng

Markov Entanglement: Decomposition Error via Agent-wise TV DistanceResearch Paper

Multi-agent reinforcement learning approximates a global value function by summing per-agent local value functions learned independently — a trick that works surprisingly well in practice (ride-hailing dispatch, restless bandits) but had no general theoretical justification. Chen and Peng (arXiv:2506.02385) explain why: they define a Markov entanglement meas…

4 thms3 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: qm2204

Buying to Bundle: Asymptotic Optimality of Surrogate BundlingResearch Paper

A platform sourcing items from monopolistic sellers with private quality cannot tractably maximize its true profit: the bundle revenue Rev(vS)Rev(v_S)Rev(vS​) is neither monotone, submodular, supermodular, subadditive, nor superadditive. Theorem 4.6 of Buying to Bundle: Optimal Sourcing from Monopolistic Sellers shows that the simple surrogate threshold mechanism —…

19 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: iris

Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience: Greedy with a κ-Approximate Star-Graph Black Box Is κ/2-Competitive under Adversarial ArrivalsResearch Paper

Online bipartite matching, introduced by Karp, Vazirani and Vazirani (1990), models a platform that must assign arriving customers to a known stock of items, one customer at a time and irrevocably. In e-commerce, job search and online advertising, a recommendation is only a suggestion: a customer buys an offered item with some known probability, and after…

15 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsDynamic ProgrammingMarkov Chain+1·Captain: iris

Relaxed Indexability and Index Policy for Partially Observable Restless Bandits: Relaxed Indexability Is Equivalent to a Passive-Time Inequality, and the Approximate Whittle Index Has a Closed FormResearch Paper

A restless multi-armed bandit has NNN arms, each a Markov chain that keeps evolving whether or not it is used; in every slot a decision maker activates some of the arms and collects rewards from them. Channel selection in wireless networks, machine maintenance, target tracking and patient monitoring are of this form. Finding an optimal policy is PSPACE-hard…

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

Effects of Reactive Capacity on Product Quality and Firm Profitability in an Uncertain Market: equilibrium quality rises then falls in the supplier's reactive capacityResearch Paper

Brand-owning retailers outsource production and use pull contracts: the retailer names a wholesale price, the supplier decides how much to stock before the season, and the retailer orders only after it has seen demand, so the supplier carries the inventory risk (Cachon 2004, cited on p.13 of the source). Investment in reactive capacity (shorter set-up…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research·Captain: iris

Correlated Equilibria in Large Anonymous Bayesian Games: with a convex potential, coarse correlated and correlated Wardrop equilibria are the mixtures of Wardrop equilibria, all with equal costsResearch Paper

In large populations of anonymous agents (commuters choosing routes, users choosing servers, customers choosing a bar), each individual has a negligible effect on the others, and the natural equilibrium notion is the Wardrop equilibrium (WE): only cheapest actions carry mass. A mediator such as a navigation app may instead recommend actions at random,…

13 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research+2·Captain: iris

Tight Approximation for Unconstrained XOS Maximization: Algorithm 4 Finds a (k−1)(k-1)(k−1)-Maximizer of Every kkk-XOS Function in O(k2n)O(k^2 n)O(k2n) Time, Exactly When k=2k=2k=2Research Paper

Maximizing a set function is a basic task in combinatorial optimization and algorithmic game theory. Computing an agent's demand under prices ppp amounts to maximizing v(X)−∑x∈Xpxv(X)-\sum_{x\in X}p_xv(X)−∑x∈X​px​, which need not be monotone even when the valuation vvv is. XOS functions generalize submodular functions, and they are studied in combinatorial auctions, where they are…

22 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: iris

Online Estimation and Optimization of Utility-Based Shortfall Risk: The Projected Stochastic Approximation Estimator Has Mean-Squared Error O(1/n) with an Explicit ConstantResearch Paper

A risk measure assigns to a random financial position XXX the amount of cash that has to be added to it to make it acceptable. Value-at-Risk ignores the size of losses beyond a quantile, and Conditional Value-at-Risk weighs all losses beyond a threshold equally. Utility-based shortfall risk (UBSR), introduced by Föllmer and Schied (Convex measures of risk and…

19 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: iris

An Accelerated Newton–Dinkelbach Method and Its Application to Two Variables per Inequality Systems: The Look-Ahead Newton–Dinkelbach Method Halves the Bregman Divergence Every Two IterationsResearch Paper

Many optimization problems ask for the largest root of a concave function of one real variable that can only be accessed through oracles. In linear fractional combinatorial optimization, minimizing a ratio c⊤x/d⊤xc^\top x/d^\top xc⊤x/d⊤x over x∈D⊆{0,1}mx\in D\subseteq\{0,1\}^mx∈D⊆{0,1}m reduces to finding the largest root of the concave, piecewise linear function …

14 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsMechanism Design·Captain: iris

Auctions of Auctions: exchanges' double bid-shading lowers both publisher revenue and advertiser profit below the direct benchmarkResearch Paper

Display advertising is sold impression by impression in real-time auctions. A publisher rarely sells to advertisers directly: advertisers delegate bidding to intermediaries, ad exchanges, which collect their clients' bids in an internal auction and then bid on the winner's behalf in the publisher's header auction. Since the industry's move to first-price…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: iris

Coordination of Multiechelon Supply Chains Using the Guaranteed Service Framework: The Centralized Safety-Stock Optimum Equals the Best Split over the Service Time Between the Two PlayersResearch Paper

Multi-echelon supply chains are rarely run by a single firm. A manufacturer of a finished product buys a component from a supplier, and each firm places its own safety stock. The guaranteed-service model of safety-stock placement, going back to Simpson (1958) and developed by Graves and Willems (2000), lets a planner choose, for each stage, the service time…

5 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: iris

A Unifying Framework for Submodular Mean Field Games: Abstract Submodular MFGs Have Least and Greatest Equilibria, Reached by Iterating the Best-Response MapResearch Paper

Mean field games (MFGs), introduced by Lasry and Lions and by Huang, Malhamé and Caines in 2006–2007, describe the limit of symmetric stochastic games with many small players. A representative player optimizes against the distribution of the population, and an equilibrium is a distribution that reproduces itself when every player best responds to it.…

17 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

Best of Both Worlds Ad Contracts: Guaranteed Allocation and Price with Programmatic Efficiency: The Market-Maker Contract Strictly Raises Revenue and Welfare at Unchanged Utilities and EfficiencyResearch Paper

Display advertising is sold in two ways. Reservation contracts guarantee an advertiser a volume of impressions at a fixed price, negotiated in advance. Programmatic auctions (ad exchanges) sell impressions one at a time, efficiently, but at a price and with an allocation that the advertiser does not know in advance. Advertisers with fixed campaign budgets…

18 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation VII: expectation, worst case and CVaR are coherent risk measuresTextbook

A stochastic linear program evaluates a decision x∈Rnx\in\mathbb R^nx∈Rn through a random outcome, typically the linear-affine random variable ζ(x,η,ξ)=η⊤x−ξ\zeta(x,\eta,\xi)=\eta^\top x-\xiζ(x,η,ξ)=η⊤x−ξ, where η\etaη is a random vector and ξ\xiξ a random variable. Chapter 2 of Kall and Mayer's Stochastic Linear Programming (Springer, 2005) builds its single-stage models in two steps: a…

34 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation II: joint probability constraints are closed, and convex at high levels under finite discrete distributionsTextbook

A linear program whose technology matrix and right-hand side are random cannot simply require its constraints to hold: for most realizations of the data, no decision satisfies them all. A joint probability constraint (also called a chance constraint) asks instead that the random system T(ξ)x≥h(ξ)T(\xi)x\ge h(\xi)T(ξ)x≥h(ξ) hold with probability at least a prescribed level …

16 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) II: When Least-Cost Dipaths Exist, the Shortest Dipath Cost Equals the Maximum Feasible PotentialTextbook

The shortest path problem asks, in a network whose links carry costs, for a cheapest directed route from a fixed origin to every other point. It is the basic subroutine of network optimization: minimum-cost flow algorithms, matching algorithms and many dynamic programs call it repeatedly, and arc costs that are negative arise naturally, for instance as −log⁡-\log−log…

22 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) V: A Minimum-Cost Flow Problem with Integral Demands and Capacities Has an Integral Optimal SolutionTextbook

The minimum-cost flow problem is the common roof over shortest paths, maximum flows, transportation and assignment problems, and transshipment. It asks for the cheapest way to move a commodity through a directed network so that every node receives its prescribed net amount and no arc carries more than its capacity. Its central structural fact is…

21 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Online Assortment Optimization with Reusable Resources: The myopic policy earns at least half the clairvoyant optimal revenueResearch Paper

A server, storage unit or production machine can serve a customer and then become available again. Offering it now earns revenue but may prevent serving a later customer while it remains occupied. Online assortment optimization with reusable resources studies these decisions when each customer chooses among the products offered and an outside option. The…

11 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: iris

Pride or Guilt? Impacts of Consumers’ Socially Influenced Recycling Behaviors on Closed-Loop Supply Chains: in Ω4 pride raises optimal profit; guilt lowers it iff τ*_m < b1/b0Research Paper

Manufacturers of phones, appliances and packaging increasingly take back used products and remanufacture them, paying consumers a recycling reward (a trade-in credit or gift card). Whether a consumer returns a used product depends not only on money and effort but on social feelings: the pride of recycling when others do not, and the guilt of not recycling…

30 thms2 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: iris

Implied Ambiguity: Mean-Variance Inefficiency and Pricing Errors: the smallest ambiguity aversion making a portfolio optimal is an explicit decreasing function of its normalized Sharpe ratioResearch Paper

Observed portfolios, from mutual fund holdings to market capitalization weights, are rarely mean-variance efficient: their Sharpe ratio falls short of that of the tangency portfolio. In a classical CARA–normal model this cannot happen, so the gap needs an explanation. Hara and Honda (working paper, 2018; Management Science, 2022) explain it by ambiguity…

13 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: Shuze Chen

Optimal Matchmaking Strategy in Two-Sided Marketplaces: Lower bounds on communication for stable matchmakingResearch Paper

A platform may know the services its users seek and offer while still lacking the preferences that determine whether a particular match is worthwhile. Learning those preferences requires communication. A lower bound on that communication would distinguish a limitation of one search algorithm from a limitation shared by every platform design. Peng Shi's Optim…

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Markov Decision Processes (Puterman) I: Backward Induction and Optimal PoliciesTextbook

Inventory replenishment, equipment replacement, and resource allocation require decisions whose consequences continue beyond the current period. A choice can earn an immediate reward and change the distribution of future opportunities. Comparing only immediate rewards therefore does not generally identify a good policy. A finite-horizon Markov decision…

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Markov Decision Processes (Puterman) II: Markov Policies Preserve Reward CriteriaTextbook

A controller making repeated decisions can remember every state visited and every action taken. The resulting policy class is much larger than the class of rules that use only the current state and time. In applications modeled by Markov decision processes, understanding whether that extra memory changes achievable expected rewards determines which policy…

6 thms2 active usersReviewed
PreviousPage 94 of 143Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5262500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR37055544
5NINickrobbins953290156
6VEvebis25800
7FIfizzyinc321735
8SHshivm17520
9KMkmehltretter821002265
10SCShuze Chen9455327

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