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

1326–1350 of 4812
Open1285Completed3527All4812
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Display Optimization for Vertically Differentiated Locations Under Multinomial Logit Preferences: Revenue Lower Bound for the Assignment Rounded from Dynamic-Programming ActionsResearch Paper

Retailers, online travel agencies and search engines display products in an ordered list or on a physical layout, and customers inspect only a prefix of it. Display optimization asks how to assign products to positions so as to maximize expected revenue when each customer considers only the products shown in the first kkk positions, with kkk random. Aouad and…

8 thms3 active usersReviewed
🏆Completed
EconomicsOperations ResearchProbability·Captain: mikedeng1

Heteroscedastic Exponomial Choice: Under Independent Exponential Utility Errors with Choice-Specific Rates, Every Choice Probability Is a Closed-Form ExponomialResearch Paper

Random utility models are the standard way to turn utilities into demand in operations management, marketing and economics. A consumer facing nnn products assigns each a random utility and buys the one with the highest realization; the choice probabilities are the market shares that pricing and assortment models optimize. The multinomial logit, built on…

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

Distributed Stochastic Optimization with Large Delays: Under Polynomially Growing Delays, Asynchronous SGD with Tuned Step-Sizes Drives the Mean-Square Gradient Norm to ZeroResearch Paper

Large-scale learning problems, such as empirical risk minimization over millions of samples, are solved in practice by stochastic gradient descent (SGD) run on many processors at once. In a master–worker system, or in a multi-processor system with shared memory, a worker reads the current parameter, computes a stochastic gradient and writes its update back.…

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

The Regularity of the Value Function of Repeated Games with Switching Costs: The Value Is Continuous, Increasing, Concave, Piecewise Linear and Eventually Constant in the Switching-Cost WeightResearch Paper

Many repeated interactions charge a player not only for what is played at each stage but also for changing what is played: a firm that reconfigures production, a defender that relocates patrols, a server that migrates jobs. Switching costs model this. In a zero-sum repeated game with switching costs, player 2 pays player 1 a stage payoff that depends on the…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Online Hypergraph Matching with Delays: Randomized Batching with Depth-k Greedy Is 1/d-Competitive for Online-(k, d)-Max-MatchingResearch Paper

Ride-pooling platforms receive trip requests one at a time and must decide, within a short waiting window, which requests to group into a shared vehicle. A request that is not grouped before its window closes is served alone or lost. Online hypergraph matching with delays is the combinatorial core of this decision: requests are vertices that arrive over…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationEconomicsOperations Research·Captain: mikedeng1

Efficient Allocations in Double Auction Markets: Repeated Double Auctions Drive the Consumer Surplus to Zero at Rate 1/t and Their Cluster Points Are Individually Rational Pareto AllocationsResearch Paper

Double auctions match buy and sell orders at a common price. Stock exchanges, commodity markets and electricity markets use them at their opening and closing auctions and to trade multi-asset portfolios. Economists have long asked how efficient the resulting allocations are. Laboratory work starting with Smith (1962) found that repeated double auctions with…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Model-Free Bounds for Multi-Asset Options Using Option-Implied Information and Their Exact Computation: Under No-Arbitrage with Bid–Ask Spreads, the Superhedging Price ϕ(f) Equals sup_{μ∈Q} ∫f dμResearch Paper

A trader who quotes an exotic option written on several underlying assets (a basket call, a spread option, a best-of option) needs a price range that does not rest on a particular stochastic model. What is observed in the market is a finite set of liquid derivatives (vanilla calls and puts on each asset, and possibly some traded basket options), each with a …

9 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

Queueing Dynamics and State Space Collapse in Fragmented Limit Order Book Markets: every equilibrium is the lifting of a one-dimensional workload equilibriumResearch Paper

US equities trade on many exchanges at once. Each exchange keeps its own limit order book, and at the national best bid the same price is offered in several queues that differ in the rebate the exchange pays a liquidity provider and in how long a resting order waits to be filled. An investor who posts a limit order chooses an exchange, or decides to cross…

7 thms3 active usersReviewed
🏆Completed
Actuarial ScienceEconomicsOperations Research+1·Captain: mikedeng1

Distributional Transforms, Probability Distortions, and Their Applications: Probability Distortions Are Exactly the Monotone, Lower-Semicontinuous Transforms Commuting with Shape TransformsResearch Paper

Many models in decision theory, insurance and risk management do not act on random outcomes directly but on their distributions. A distributional transform is a map TTT that sends a probability distribution FFF on R\mathbb RR to another distribution T(F)T(F)T(F). The most important class is that of probability distortions, T(F)=g∘FT(F)=g\circ FT(F)=g∘F for an increasing function ggg on …

11 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: mikedeng1

Time Consistency of the Mean-Risk Problem: The Upper Images of the Dynamic Mean-Risk Problem Satisfy a Set-Valued Bellman RecursionResearch Paper

Markowitz's mean-variance problem trades off the expected terminal wealth of a portfolio against its risk. Over several periods the scalarized form of this problem is time inconsistent: a strategy that is optimal today for a fixed risk-aversion parameter is generally no longer optimal tomorrow for the same parameter, so the investor would deviate from her…

11 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research·Captain: mikedeng1

The Folk Theorem for Repeated Games with Time-Dependent Discounting: Subgame Perfect Equilibrium Payoffs Converge to the Feasible and Individually Rational Set as Players Become PatientResearch Paper

Repeated games model long-run relationships: the same players meet stage after stage, observe what was played, and can condition today's behavior on the past. The folk theorem describes what such relationships can sustain. When players are patient, every payoff vector that is feasible and gives each player at least what the others can force on them is the…

14 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP: The Circlet Inequality Is Valid and Facet-Defining for the Symmetric TSP Polytope When 4 Divides nResearch Paper

The symmetric traveling salesman polytope STSP(n)STSP(n)STSP(n) is the convex hull of the incidence vectors of all Hamiltonian cycles of the complete graph KnK_nKn​. Minimizing a linear cost over it is the traveling salesman problem, and polyhedral methods for the TSP (cutting planes, branch and cut, LP relaxations and their integrality gaps) depend on linear inequalities…

19 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Moment-Sum-of-Squares Hierarchy for Robust Polynomial Matrix Inequality Optimization with Sum-of-Squares Convexity: Both Bounds of the Hierarchy Decrease to the Robust Optimum f⋆Research Paper

Many problems in control, robust semidefinite programming and risk management ask for a decision yyy that keeps a matrix positive semidefinite for every value of an uncertain parameter xxx in a set X\mathcal XX. Examples include robust polynomial SDPs (Scherer and Hol, 2006), Lyapunov-type conditions that must hold on a region of the state space, and robust…

11 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear algebraOperations Research·Captain: mikedeng1

Technical Note—Global Robust Stability in a General Price and Assortment Competition Model: Robust Best-Response Price Dynamics Contract Geometrically to the Special Equilibrium from Any StartResearch Paper

Retailers that sell many products set prices against one another, and the demand for each product depends on the prices of all of them. Affine demand models, q(p)=a−Rpq(p)=a-Rpq(p)=a−Rp, are the standard starting point for this kind of multi-product price competition in operations management and industrial organization. Two questions follow once an equilibrium is known to…

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

Network Pricing: How to Induce Optimal Flows Under Strategic Link Operators: Optimal Tolls Bounded by the Marginal Tolls Are (Strong) Cap EquilibriaResearch Paper

Congestion pricing charges road users for the delay they impose on others. The classical theory, going back to Beckmann, McGuire and Winsten (1956), assumes a single benevolent authority that sets every toll: charging each link its marginal toll makes the selfish (Wardrop) traffic pattern socially optimal. Many real networks are different. Roads, bridges…

8 thms3 active usersReviewed
Algorithmic Game TheoryBandit AlgorithmsOperations Research+1·Captain: mikedeng1

Game of Thrones: Fully Distributed Learning for Multiplayer Bandits: Without Communication, the Game of Thrones Algorithm Has Expected Total Regret O(log^{1+δ} T)Research Paper

In a multiplayer multi-armed bandit, several agents repeatedly choose among the same finite set of arms, and two agents that choose the same arm collide and receive nothing. The model comes from cognitive radio and wireless networks: users share channels, a channel used by two users at once carries neither transmission, and the quality of a channel differs…

13 thms3 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryLinear Optimization+2·Captain: mikedeng1

Binary Extended Formulations and Sequential Convexification: Among All d-Hypercube Binarizations, the Logarithmic Binarization Has Minimum RankResearch Paper

Mixed-integer programs often contain general integer variables x∈{0,…,k}x \in \{0, \dots, k\}x∈{0,…,k}. A standard modelling device replaces such a variable by ddd binary variables y∈{0,1}dy \in \{0,1\}^dy∈{0,1}d linked to xxx through a polytope, a binarization. Examples are the unary encoding, the "full" encoding with one indicator per value, and the logarithmic encoding x=∑i2i−1yix = \sum_i 2^{i-1} y_ix=∑i​2i−1yi​.…

15 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

An Approximate Dynamic Programming Approach to the Incremental Knapsack Problem: For Every ε > 0 the Cluster Dynamic Program Returns a Feasible Solution Within Factor 1 − ε of OptimalResearch Paper

The incremental knapsack problem is a multi-period extension of the binary knapsack problem. Items are inserted over a planning horizon whose capacity grows over time, and an item, once inserted, stays. Sharp (2007) and Hartline (2008) introduced it in their theses on incremental optimization. It models resource allocation in which the available budget…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+2·Captain: Shuze Chen

Modeling, Measuring and Managing Risk X: Dual Representation of Polyhedral Acceptability FunctionalsTextbook

Risk measures enter optimization models as objectives or constraints, and the models that use them most, multi-stage stochastic programs, are solved as large linear programs. A risk functional is only usable there if it can itself be written as the value of a linear program. Eichhorn and Römisch introduced polyhedral risk measures for this purpose (doi:10.11…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+2·Captain: Shuze Chen

Modeling, Measuring and Managing Risk VII: Dual Representation of Minimal Loss Deviation FunctionalsTextbook

A deviation functional measures how far a random profit YYY spreads around its mean: the variance, the standard deviation, the mean absolute deviation from the median, and the average value-at-risk deviation are the standard examples in portfolio selection and in risk-averse stochastic programming. Pflug and Römisch, Modeling, Measuring and Managing Risk (Worl…

6 thms3 active usersReviewed
🏆Completed
Functional AnalysisOperations ResearchOptimization+1·Captain: Shuze Chen

Modeling, Measuring and Managing Risk V: Dual Representation of Conditional Acceptability MappingsTextbook

A risk measure that returns a single number answers the question "how acceptable is this random profit, seen from today?". Multi-period decision problems — portfolio rebalancing, insurance reserves, stochastic programs on scenario trees — need the same question asked at every later date, given the information available then. The answer is no longer a number…

6 thms3 active usersReviewed
CombinatoricsOperations ResearchOptimization·Captain: Shuze Chen

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties: Polynomial approximation for monotone submodular maximizationResearch Paper

Selecting a valuable subset subject to several simultaneous restrictions is a common combinatorial optimization problem. A facility may contribute less after nearby facilities have already been selected; a collection of observations may provide overlapping information. Such diminishing returns are captured by submodular objectives. Matroid constraints…

16 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: Shuze Chen

On the Existence of Pure Nash Equilibria in Weighted Congestion Games: Characterizing universal pure equilibrium existenceResearch Paper

A system of users sharing resources may have no stable configuration: whenever the users settle on their choices, somebody may prefer to change. Weighted congestion games describe this question when different users place different demands on the resources they choose. Routing and scheduling provide examples, but the mathematical question here does not…

22 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research+1·Captain: Shuze Chen

Food Delivery Service and Restaurant: Friend or Foe?: With Convenient Delivery, a Critical Mass of Tech-Savvy Customers Makes the Restaurant Delivery-Only and Cuts Platform Profit and WelfareResearch Paper

Food delivery platforms such as Uber Eats, DoorDash and Meituan let a restaurant serve customers who never enter it, but they also charge those customers a delivery fee and share the restaurant's kitchen with its walk-in trade. Whether the platform helps or hurts the restaurant is a question restaurant owners, platforms and regulators all ask. Chen, Hu and…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Robust Optimization I: Conic Representations of Robust Linear ConstraintsTextbook

A production or allocation decision can satisfy a linear constraint for nominal data and violate it when those data change. Robust optimization asks for a decision that satisfies the constraint for every realization in a prescribed uncertainty set. The uncertainty set is part of the model: the requirement does not attach probabilities to its elements, and…

7 thms3 active usersReviewed
PreviousPage 54 of 193Next

Top contributors

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