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

476–500 of 1285
Open1285Completed3527All4812
Dynamic ProgrammingLinear OptimizationOperations Research+1·Captain: iris

Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations: The Optimal Online Policy's Expected Regret Grows at Least Logarithmically in the HorizonResearch Paper

In an online linear program, customers arrive one at a time and a firm must accept or reject each one at once, spending a shared inventory of mmm resources. The model covers network revenue management, ad allocation and order fulfilment (Li and Ye, 2022). Its central performance measure is the regret: the gap between what an omniscient planner collects and…

25 thms2 active usersReviewed
Machine LearningOperations ResearchProbability·Captain: iris

The Nonstationary Newsvendor with (and without) Predictions: The Prediction-Error-Robust Policy Achieves Regret Õ(T^min{(3+v)/4, a}) Without Knowing the Prediction AccuracyResearch Paper

Retailers, hospitals and data-center operators repeatedly decide how much to stock before demand is seen, and in practice the demand distribution drifts over time while external predictions of its mean (human judgement, forecasting software, machine-learned models) are available but of unknown quality. The newsvendor problem is the classical model of a…

26 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Learning to collude in a pricing duopoly: under self-play, Composite SPSA prices converge to the global optimal price and relative regret vanishes at rate T^(-1/5)Research Paper

Firms increasingly delegate pricing to learning algorithms, and regulators ask whether such algorithms can raise prices without any agreement between the firms. Meylahn and den Boer (SSRN:3741385, MSOM, doi:10.1287/msom.2021.1074) answer with a concrete construction: a data-driven policy which, when both duopolists use it, reaches the joint-revenue maximum…

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

Bayesian Mechanism Design for Blockchain Transaction Fee Allocation: The Logit Transaction Fee Mechanism Is U-BNIC and 1-SCP, and UIR, Budget Feasible and Sybil-Proof for n ≥ λ₀kResearch Paper

A blockchain confirms a limited number of transactions per block. Users attach fees (bids) to their transactions; the block producer (the miner) chooses which transactions to include and collects some of the fees. The rule that maps bids to confirmations, payments and miner revenue is a transaction fee mechanism (TFM). Because the miner is itself a…

17 thms2 active usersReviewed
Convex OptimizationOperations ResearchProbability·Captain: iris

The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems: under i.i.d. requests, dual mirror descent has regret ≤ f̄b̄/ρ̲ + (b̄ + ρ̄)²ηT/(2σ) + C₃/ηResearch Paper

Many resource allocation problems arrive one request at a time: an ad exchange decides which campaign gets an impression, a network admits or routes a call, a cloud provider schedules a job. Each decision earns a reward and consumes several budgets, and it cannot be revisited. The usual benchmark is the offline optimum, the best total reward attainable with…

10 thms2 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: iris

A Unified Theory of Robust and Distributionally Robust Optimization via the Primal-Worst-Equals-Dual-Best Principle: Strong Duality Between the Primal Worst and Dual Best ProblemsResearch Paper

A robust convex program chooses a decision xxx that minimizes a convex objective against the worst value of an uncertain parameter zzz drawn from a convex uncertainty set ZZZ, and that stays feasible for every z∈Zz \in Zz∈Z. Robust optimization is a standard modelling tool in operations research, and many distributionally robust problems over moment or…

35 thms2 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: iris

On the Equivalence and Performance of Distributionally Robust Optimization and Robust Satisficing Models: Every Robust Satisficing Optimum Is Optimal for Wasserstein DRO with Radius −1/α, α ∈ ∂κ(τ)Research Paper

Data-driven decisions under uncertainty start from SSS historical samples z^1,…,z^S\hat z_1,\dots,\hat z_Sz^1​,…,z^S​ of a random outcome and a cost f(x,z)f(x,z)f(x,z) of a decision xxx. Minimizing the sample average cost overfits: the decision performs worse out of sample than the sample average suggests. Two models hedge against this with the type-1 Wasserstein distance around the empirical…

19 thms2 active usersReviewed
Operations ResearchOptimizationProbability+1·Captain: iris

A Pareto Dominance Principle for Data-Driven Optimization: Under an Exponential Family Whose Statistic Obeys an LDP, the Distributionally Robust Predictor-Prescriptor Pair Is Pareto DominantResearch Paper

A decision-maker wants to solve min⁡x∈Xc(x,θ⋆)\min_{x\in X} c(x,\theta_\star)minx∈X​c(x,θ⋆​), but the model θ⋆\theta_\starθ⋆​ of the data-generating process is unknown. All that is available is one observed trajectory ξ1,…,ξT\xi_1,\dots,\xi_Tξ1​,…,ξT​ of a process, possibly serially dependent, whose law belongs to a known family {Pθ:θ∈Θ}\{\mathbb P_\theta:\theta\in\Theta\}{Pθ​:θ∈Θ}. Sample average approximation,…

21 thms2 active usersReviewed
Algorithmic Game TheoryMachine LearningOperations Research+2·Captain: iris

Multi-Agent Online Learning in Time-Varying Games: Mirror Descent Converges Almost Surely to the Nash Equilibrium of a Strictly Monotone Limit GameResearch Paper

Many systems in which several agents repeatedly make continuous decisions are modelled as games whose rules drift over time: bidders in repeated Kelly auctions whose valuations change with traffic, wireless users whose channel gains fluctuate, firms in Cournot markets with shifting demand. In such settings agents rarely know the game they are playing; they…

17 thms2 active usersReviewed
Algorithmic Game TheoryConvex OptimizationEconomics+2·Captain: iris

S-Convexity and Gross Substitutability: A Usc, Coercive, Continuously Differentiable, Strictly Concave Function with Open Domain Is a Proper GS-Function If and Only If It Is S-ConcaveResearch Paper

Gross substitutability (GS) is the condition under which competitive prices behave well: if the prices of some goods rise and the others stay fixed, demand for the unchanged goods does not fall. Kelso and Crawford (1982) introduced it for job matching, and Gul and Stacchetti (1999) showed that for indivisible goods it is the condition under which a…

26 thms2 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Ordinary and Prophet Planning under Uncertainty in Bernoulli Congestion Games: The Worst-Case Prophet Price of Anarchy Equals the Optimal (λ,μ,q)(\lambda,\mu,q)(λ,μ,q)-Smoothness Bound γpr(C,q)\gamma_{pr}(C,q)γpr​(C,q)Research Paper

Atomic congestion games model players who share resources, such as links of a network, servers or road segments, and whose cost on a resource grows with the number of its users. The price of anarchy measures how much worse a selfish equilibrium is than the best outcome. The inefficiency of these games is well understood when the set of players is fixed:…

32 thms2 active usersReviewed
Dynamic ProgrammingLinear OptimizationOperations Research+1·Captain: iris

Robust Online Selection with Uncertain Offer Acceptance: The Best Robust Ratio Equals the Value of an Explicit Linear Program, and Its Optimal Solutions Give Optimal PoliciesResearch Paper

In the classical secretary problem a decision maker sees candidates in random order, learns only how each compares with those already seen, and must decide irrevocably whether to hire. Many real selection processes add one more source of uncertainty: the chosen candidate may refuse. Job offers are declined, customers ignore promotions, admitted students…

14 thms2 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Many-Server Heavy-Traffic Limits for Queueing Systems with Perfectly Correlated Service and Patience Times: the diffusion-scaled number in system converges to the Erlang-C Halfin-Whitt diffusionResearch Paper

Many-server queues with customer abandonment are the standard model of call and contact centers. The textbook model, the Erlang-A queue M/M/n+MM/M/n+MM/M/n+M, assumes that a customer's patience is independent of its service requirement. In practice a customer's patience depends on its service requirement, as empirical studies of contact centers and restaurants cited by…

23 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization·Captain: iris

Submodular Order Functions and Assortment Optimization: Threshold Add in a Weak Submodular Order Is a (1−ϵ)/2(1-\epsilon)/2(1−ϵ)/2-Approximation for Cardinality Constraints with O((n/ϵ)log⁡k)O((n/\epsilon)\log k)O((n/ϵ)logk) QueriesResearch Paper

Assortment optimization asks a retailer which set SSS of products to offer, out of a ground set NNN, when customers choose among the offered products according to a choice model; the expected revenue R(S)R(S)R(S) is a set function of the assortment. Under the multinomial logit model and its mixtures, RRR is neither monotone nor submodular, so the classical theory of…

24 thms2 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: iris

Continuous Assortment Optimization with Logit Choice Probabilities under Incomplete Information: The Stochastic Approximation Policy SAP(α, β) Has Worst-Case Regret O(log T)Research Paper

A retailer choosing which products to display, a platform choosing which items to recommend, and a broadcaster choosing which content to stream all face an assortment problem: offer a set of products, observe what customers buy, and earn the revenue of the purchased item. The standard demand model is the multinomial logit (MNL) model, under which the…

17 thms2 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: iris

Minimization Fractional Prophet Inequalities for Sequential Procurement: With In-House Production the Competitive Ratio Is Exactly (1 + (n−1)/ℓ^{1/(p−1)})^{p−1}Research Paper

A firm that must buy a fixed quantity of a commodity often faces suppliers one at a time: a quote arrives, the firm decides how much to buy at that price, and the decision cannot be revisited. Electricity procurement, cloud capacity and spot markets for raw materials all have this shape. When the marginal cost of buying grows with the amount bought from one…

10 thms2 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: iris

Optimal Error Bounds in the Absence of Constraint Qualifications with Applications to p-Cones and Beyond: Tight Hölderian Error Bounds with Optimal Exponents for Every p-ConeResearch Paper

The conic feasibility problem asks for a point of (L+a)∩K(\mathcal L+a)\cap\mathcal K(L+a)∩K, where K\mathcal KK is a closed convex cone in a finite dimensional Euclidean space, L\mathcal LL is a subspace and aaa is a point. An error bound estimates the distance from a trial point xxx to that intersection using only the two individual distances dist⁡(x,K)\operatorname{dist}(x,\mathcal K)dist(x,K) a…

38 thms2 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: iris

Enhanced Balancing of Bias-Variance Tradeoff in Stochastic Estimation: A Minimax Perspective: The Minimax Risk Ratio of Weighted Estimators Is q1/((q1+q2)K^(2q2)), Attained by Two-Decay WeightsResearch Paper

Many simulation estimators are biased, and the bias is controlled by a tuning parameter that also controls the noise. A central finite difference for the derivative of an expectation is the standard example: a perturbation size δ\deltaδ gives a bias of order δ2\delta^2δ2 and a variance of order δ−2\delta^{-2}δ−2. Simulation budgets are then spent on a trade-off.…

22 thms2 active usersReviewed
Linear OptimizationOperations ResearchOptimization·Captain: iris

Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover: a 2Δ-Approximation for 0/1 Processing Times and a (2Δ+ε)-Approximation in GeneralResearch Paper

Min-sum set cover asks for an order of the elements of a ground set that minimizes the average time at which a hyperedge is first covered. Feige, Lovász and Tetali showed that the greedy algorithm is a 4-approximation and that no better constant is possible unless P = NP (Feige, Lovász, Tetali 2004). Min-sum vertex cover, pipelined set cover,…

49 thms2 active usersReviewed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: iris

Robust Multiple Stopping — A Pathwise Duality Approach: The Upper Snell Envelope with LLL Exercise Rights Equals Its Attained Martingale Dual, Almost Surely When ho hoho Is SensitiveResearch Paper

Many contracts in finance and insurance give their holder several exercise rights that must be used at distinct dates: swing options in energy markets, flexible interest-rate caps, partial surrender options in life insurance. Valuing such a contract is an optimal multiple stopping problem. When the model itself is uncertain, or when the holder is risk…

26 thms2 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: iris

Weak Signal Asymptotics for Sequentially Randomized Experiments: Sample Paths of Lipschitz Sequentially Randomized Markov Experiments Converge Weakly to the Unique Diffusion Limit (3.1)Research Paper

Sequential experiments choose which treatment to try next from the outcomes seen so far. Multi-armed bandit algorithms such as Thompson sampling, tempered greedy rules and Luce's rule are the standard examples, and they are used in clinical trials, online platforms and adaptive A/B testing. Their behaviour is usually studied either in the large-signal…

14 thms2 active usersReviewed
Machine LearningOperations ResearchReinforcement Learning+1·Captain: iris

Fast Rates for the Regret of Offline Reinforcement Learning: Under the Margin Condition, the Greedy Policy of a Q*-Estimate with Uniform Sub-Gaussian Error at Rate aₙ Has Regret O(aₙ^(1+α))Research Paper

Offline reinforcement learning asks for a good policy in a Markov decision process using only logged transitions, without further interaction. A common family of methods (fitted QQQ-iteration, Bellman residual minimization) first estimates the optimal action-value function Q∗Q^*Q∗ by some f^\hat ff^​ and then acts greedily with respect to f^\hat ff^​. Standard analyses…

11 thms2 active usersReviewed
Machine LearningOptimizationStatistics·Captain: iris

Distributionally Robust Losses for Latent Covariate Mixtures: The Marginal DRO Estimator Nearly Minimizes the LpL^pLp Bound on Worst-Case Subpopulation RiskResearch Paper

A model trained to minimize average loss can perform badly on a subpopulation: a minority group in a language corpus, or a demographic underrepresented in a medical or vision dataset. Marginal distributionally robust optimization asks for good performance on every sufficiently large subpopulation of the covariates, without knowing which subpopulations…

27 thms2 active usersReviewed
Algorithmic Game TheoryEconomicsOperations Research·Captain: iris

Satiation in Fisher Markets and Approximation of Nash Social Welfare: Rounding a Market Equilibrium Is a 2e1/(2e)2e^{1/(2e)}2e1/(2e)-Approximation for Budget-Additive Nash Social WelfareResearch Paper

The Nash social welfare of an allocation of indivisible items is the geometric mean of the agents' valuations. Nash proposed it for the bargaining problem as the objective characterized by a set of natural axioms, and it has since become a standard objective in fair division because it balances efficiency against fairness. Maximizing it exactly is NP-hard,…

16 thms2 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: iris

The Iterates of the Frank-Wolfe Algorithm May Not Converge: for Every d ≥ 2, a C^d Convex Instance in ℝ² on Which Every Line-Search Frank-Wolfe Sequence Has f(xₜ) → min f but Does Not ConvergeResearch Paper

The Frank-Wolfe algorithm (conditional gradient method) minimizes a smooth convex function over a compact convex set using only a linear minimization oracle: at each step it minimizes the linearization of the objective over the constraint set and moves towards the minimizer. It avoids projections, which is why it is used for problems over polytopes,…

14 thms2 active usersReviewed
PreviousPage 20 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