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

201–225 of 4812
Open1285Completed3527All4812
🏆Completed
Algorithmic Game TheoryAnalysisOperations Research+1·Captain: mikedeng1

A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games 1: The Price of Anarchy Is Hölder Continuous with Exponent 1/2 at Every Game with Costs Lipschitz on [0, T(d)]Research Paper

The price of anarchy (PoA) of a nonatomic congestion game is the ratio of the total cost of a Wardrop equilibrium to the minimum possible total cost. It quantifies how much selfish routing loses compared with central coordination, and it has been studied intensively since Koutsoupias and Papadimitriou (1999) and Roughgarden and Tardos (2002), mostly through…

14 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

A First-Order Approach to Accelerated Value Iteration 2: For a Reversible Policy Chain, Momentum Value Computation Converges at Rate (1 − √(1/κ))/(1 + √(1/κ)) + η for Every η > 0Research Paper

Value iteration and its policy-evaluation special case, value computation, are the basic algorithms of dynamic programming for Markov decision processes (MDPs). Both are fixed-point iterations of a λ\lambdaλ-contraction, so they converge at the geometric rate λ\lambdaλ, the discount factor. When λ\lambdaλ is close to 111, which is the regime of long effective…

13 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Lightning Network Economics: Channels II: A Payment Channel Beats On-Chain Settlement Only If the On-Chain Fee Exceeds an Explicit ThresholdResearch Paper

Every Bitcoin transaction recorded on the blockchain pays a fee, and the blockchain processes only a few transactions per second. The Lightning Network is a layer-two protocol that moves repeated payments off chain: two parties lock funds in a payment channel, exchange payments by updating the channel's balance, and touch the blockchain only to open, close…

35 thms5 active users
🏆Completed
CombinatoricsOperations ResearchOptimization+2·Captain: mikedeng1

Pricing in On-Demand and One-Way Vehicle-Sharing Networks 3: The K/(N+K−1+Λ/μ) Guarantee Holds When Static Prices Split the Network into ComponentsResearch Paper

One-way vehicle-sharing systems (car sharing, bike sharing, on-demand fleets) move a fixed fleet of KKK vehicles among NNN locations. Customers take a vehicle at one location and leave it at another, so prices shape both revenue and where the fleet ends up. The optimal dynamic pricing policy, which reacts to the current position of every vehicle, solves a…

26 thms5 active users
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Lightning Network Economics: Channels IV: The Long-Run Number of Channel Transactions per On-Chain Transaction in Closed FormResearch Paper

A blockchain such as Bitcoin settles a limited number of transactions per unit of time, and every on-chain transaction pays a fee that rises with congestion. The Lightning Network moves payments off the chain. Two parties lock funds in a payment channel with one on-chain transaction, and they can then pay each other any number of times by updating the…

13 thms5 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

Contextual Inverse Optimization: Offline and Online Learning 3: EllipsoidalCones Has Worst-Case Regret O(d² ln(T tan α(C₀))) from a Pointed Initial Knowledge SetResearch Paper

In inverse optimization one observes the decisions of an expert who solves an optimization problem and tries to recover the expert's objective. The contextual version of Besbes, Fonseca and Lobel (arXiv:2106.14015; Operations Research, 2025) asks a sharper question: not how well the cost can be estimated, but how well a decision-maker who imitates the…

18 thms5 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+2·Captain: mikedeng1

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes II: With Infinite Patience, Attenuated Random-Order Probing Probes Each Edge w.p. ≥ (1 − e^(−2))y_e/2Research Paper

In stochastic matching a platform knows, for every potential pair, the probability that the pair would succeed, but learns whether it does only by trying it, and a successful trial is binding. Kidney exchange, online dating and labour markets are the standard examples: a crossmatch test, a date or an interview is a probe whose outcome is random, and a…

10 thms5 active users
🏆Completed
Algorithmic Game TheoryCombinatoricsEconomics+2·Captain: mikedeng1

Endogenous Risk Exposure and Systemic Instability II: Banks Take More Risk in the Least Equilibrium of a Complete Network than of a Ring NetworkResearch Paper

Banks lend to one another, and the shape of the resulting network decides how a loss at one bank reaches the others. A long line of work, starting with Allen and Gale (2000) and continued by Acemoglu, Ozdaglar and Tahbaz-Salehi (2015), compares the ring network, where each bank is owed money by one neighbour, with the complete network, where every bank…

15 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Reducing Marketplace Interference Bias Via Shadow Prices 3: The Scaled Expected Matching Value Converges to the Fluid LP Value Φ(λ, π)Research Paper

Two-sided platforms (ride hailing, delivery, freelancing, logistics) collect demand and supply requests over a matching cycle and then clear them with an optimization problem. When such a platform runs an experiment, treated and control units compete for the same supply, so the outcome of one unit depends on the treatment of others. Interference bias of…

7 thms5 active users
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Optimality Conditions in Control Problems with Random State Constraints in Probabilistic or Almost Sure Form I: Necessary and Sufficient Optimality Conditions for a Gaussian Probabilistic ConstraintResearch Paper

Probabilistic (chance) constraints require that a decision keeps a random constraint satisfied with probability at least ppp. They are the standard way to model reliability requirements in engineering design, energy networks and the control of systems driven by uncertain data, and they are increasingly imposed on infinite-dimensional decisions such as the…

19 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research+1·Captain: mikedeng1

Imperfect Targeting and Advertising Strategies: With Costless Advertising and A < 1/4, Equilibrium Industry Profit Falls as Targeting Improves, Jumps Up at α̂₂(A), Then Stays ConstantResearch Paper

Online advertising lets a firm aim its messages at the consumers most likely to want its product, but the data behind that aim is noisy: a platform's prediction of who belongs to a demographic or interest segment is right only with some probability. A natural expectation is that sharper targeting raises firms' profits, since fewer messages are wasted. Karle…

10 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

On the Optimality of Affine Policies for Budgeted Uncertainty Sets 1: For Budget of Uncertainty Sets, Affine Policies Approximate the Two-Stage Adjustable Robust Problem within O(log n / log log n)Research Paper

Two-stage adjustable robust optimization models decisions taken in two steps around an uncertain demand: a first-stage decision is fixed now, the demand is revealed, and a second-stage (recourse) decision reacts to it. The objective is the worst-case total cost over a set of possible demands. The model covers set cover, capacity planning and network design…

20 thms5 active usersReviewed
Algorithmic Game TheoryControl TheoryMarkov Chain+1·Captain: mikedeng1

Strong and Weak Equilibria for Time-Inconsistent Stochastic Control in Continuous Time 1: Weak and Strong Equilibria Exist When the Admissible Generator Rows Form Convex Compact SetsResearch Paper

An agent whose preferences change over time cannot simply optimize. Under non-exponential discounting, for instance hyperbolic or pseudo-exponential discount functions, a plan that is optimal today stops being optimal tomorrow, and a later self deviates from it. Strotz (1955) proposed that a sophisticated agent treat future selves as players in a game and…

17 thms5 active usersReviewed
Control TheoryDynamic ProgrammingMarkov Chain+1·Captain: mikedeng1

Strong and Weak Equilibria for Time-Inconsistent Stochastic Control in Continuous Time 3: Discrete-Time Equilibria Exist on an Infinite Horizon for Closed Convex Admissible Transition RowsResearch Paper

In many dynamic decision problems the criterion an agent uses today is not the one it will use tomorrow. The standard example is non-exponential discounting: if a payoff received ttt periods from now is weighted by δ(t)\delta(t)δ(t) and δ\deltaδ is not geometric, then the plan that is optimal from today's point of view will be abandoned by the agent's future selves.…

11 thms5 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationLinear algebra+1·Captain: mikedeng1

Quadratic Matrix Inequalities with Applications to Data-Based Control III: Petersen's Lemma Recovered from the Matrix S-LemmasResearch Paper

Robust control repeatedly meets linear matrix inequalities that must hold for every value of an unknown, norm-bounded matrix. A typical instance is

12 thms5 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Linear Convergence of First Order Methods for Non-Strongly Convex Optimization IV: Projected Gradient on a Quasi-Strongly Convex f Has dist²(x^k, X*) ≤ ((1 − μ)/(1 + μ))^k dist²(x^0, X*)Research Paper

The projected gradient method is the basic algorithm for minimising a smooth convex function over a closed convex set. For an objective with an LfL_fLf​-Lipschitz gradient it converges at the sublinear rate f(xk)−f∗≤Lf∥x0−x∗∥2/(2k)f(x^k)-f^*\le L_f\|x^0-x^*\|^2/(2k)f(xk)−f∗≤Lf​∥x0−x∗∥2/(2k), and the classical way to obtain a linear (geometric) rate is to assume strong convexity. Many objectives that arise in…

13 thms5 active users
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios III: No Online Algorithm Earns More Than F(𝒫) Times the Expected Offline OptimumResearch Paper

A firm sells several products, each in limited supply. Customers arrive one at a time, and each product can be offered at one of a few prices. This is the setting of airline fare classes, hotel rate plans and e-commerce discounting. Because future demand is unknown, the firm must decide online whether to sell a unit now at a low price or keep it for a…

13 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios I: Multi-price Balance Is minᵢ F̃ᵢ-Competitive, F̃ᵢ Bounded via F(𝒫ᵢ), G(𝒫ᵢ)/2 and kᵢResearch Paper

Online matching and its revenue-management variants model a firm that allocates limited inventory to customers who arrive one at a time, without knowing who comes next. Classical results in this area assume each item has a single price, or weight. For a single price and large inventories, the BALANCE algorithm of Kalyanasundaram and Pruhs (2000) and its…

11 thms5 active usersReviewed
Machine LearningOperations ResearchOptimization+1·Captain: mikedeng1

A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization: NASA with Stepsizes 1/√N Drives the Expected Stationarity Measure E[V(x_R, z_R)] Below C/(√N − 1)Research Paper

Many learning and risk-averse decision problems minimize a function of an expectation that is itself passed through another function: F(x)=f(g(x))F(x)=f(g(x))F(x)=f(g(x)) with g(x)=E[G(x,ξ)]g(x)=\mathbb E[G(x,\xi)]g(x)=E[G(x,ξ)]. Examples are mean–deviation risk measures, stochastic variational inequalities rewritten as minimization, and policy evaluation in reinforcement learning. Only noisy samples of ggg,…

15 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationDynamical Systems·Captain: mikedeng1

Learning in Games via Reinforcement and Regularization 2: Under Regularized Reinforcement Learning, Every Strict Nash Equilibrium Is Asymptotically StableResearch Paper

In a repeated game, players who do not know the payoff structure can still learn by reinforcement: each player keeps a running score for every action, the cumulative payoff that action would have earned, and plays a mixed strategy that favours actions with high scores. Turning scores into mixed strategies through a regularized best response (maximize score…

12 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationDynamical Systems·Captain: mikedeng1

Learning in Games via Reinforcement and Regularization 3: In 2-Player Zero-Sum Games with an Interior Equilibrium, Time-Averaged Play Converges to the Nash SetResearch Paper

Learning dynamics in games describe how players who repeatedly interact adjust their strategies from observed payoffs. A central question is whether such dynamics lead to Nash equilibrium. For the replicator dynamics, the canonical model of evolutionary game theory, the answer is negative in general: in Matching Pennies and in generic zero-sum games with a…

10 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimal Transport+1·Captain: mikedeng1

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls 2: With Q = 0 and Ξ = ℝ^K, the 1-Wasserstein Problem Is the Linear Program (32)Research Paper

Two-stage stochastic linear programs model decisions taken in two steps: a first-stage decision xxx is fixed before an uncertain parameter ξ\xiξ is observed, and a second-stage (recourse) decision yyy adapts to ξ\xiξ afterwards. They underlie capacity planning, inventory and network design. In practice the distribution of ξ\xiξ is known only through samples …

13 thms5 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

On the Convergence of Decentralized Gradient Descent I: Under (Restricted) Strong Convexity Every Agent Satisfies ‖x₍ᵢ₎(k) − x*(k)‖ ≤ c₃ᵏ‖x*(0)‖ + c₄/√(1 − c₃²) + αD/(1 − β)Research Paper

In decentralized optimization a group of agents minimizes a sum of functions without a central coordinator: agent iii knows only its own function fif_ifi​ and can exchange vectors only with its neighbours in a communication network. The setting covers sensor networks, multi-robot coordination and data-parallel learning in which the data cannot be pooled. The basic…

14 thms5 active usersReviewed
Control TheoryDynamical SystemsGraph Theory+1·Captain: mikedeng1

Synchronization via Pinning Control on General Complex Networks I: A Kronecker LMI Weighted by the Positive Left Null Vector of G Globally Synchronizes a Pinned Strongly Connected NetworkResearch Paper

Many engineered and natural systems are networks of identical dynamical units coupled through a directed interaction graph: arrays of oscillators, power grids, sensor and multi-agent networks, gene regulatory circuits. A basic control question for such a network is how to force every unit onto a prescribed reference trajectory (an equilibrium, a periodic…

10 thms5 active users
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Dynamic Assortment Personalization in High Dimensions 1: The Nuclear-Norm Explore-Then-Exploit Policy Has Regret at Most ((Cr(m+n)+3) log T + 1)ωResearch Paper

An online retailer that serves many kinds of customers must decide, for each arriving customer, which handful of products to display. Showing too many items is impossible (screen space, shelf space), and which items sell depends on who is looking. The retailer does not know the customers' preferences in advance and learns them only from the choices…

22 thms5 active usersReviewed
PreviousPage 9 of 193Next

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