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

676–700 of 4812
Open1285Completed3527All4812
Linear OptimizationMachine LearningStatistics·Captain: mikedeng1

Fast Rates for Contextual Linear Optimization 2: Any Algorithm Choosing from a Policy Class of Natarajan Dimension η Has Regret ≥ (ρ(Z)/2e⁴)((η−1)/n)^((1+α)/(2+α)) on Some Margin-α InstanceResearch Paper

In contextual linear optimization (CLO) a decision maker observes a covariate XXX (features of a day, a customer, a network state) and then chooses a decision zzz from a polytope Z\mathcal ZZ to minimise an uncertain linear cost Y⊤zY^\top zY⊤z. Shortest-path routing with predicted travel times and inventory or portfolio decisions driven by forecasts are standard…

12 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Intrinsic Robustness of the Price of Anarchy I: Every Coarse Correlated Equilibrium of a Smooth Game Has Expected Cost at Most the Robust Price of Anarchy Times OptimalResearch Paper

The price of anarchy (POA) of a game measures how much selfish behaviour costs: it is the ratio between the largest cost of an equilibrium and the cost of an optimal outcome, for a nonnegative objective such as the sum of the players' costs. Since Koutsoupias and Papadimitriou (1999) and Roughgarden and Tardos (2002), POA bounds have been proved for…

12 thms4 active users
🏆Completed
CombinatoricsLinear algebraMarkov Chain+1·Captain: mikedeng1

High Order Random Walks: Beyond Spectral Gap 2: On a Two-Sided λ-Local Spectral Expander, Spec(M⁺_k) ⊆ {1} ∪ ⋃_j [(k+1−j)/(k+2) ± √(k+1)·ε_k/(k+2)] and Eigenvectors Lie Near U^j_kResearch Paper

High-dimensional expanders are simplicial complexes whose local structure forces global mixing. Random walks on their kkk-dimensional faces, the high order random walks, are used to analyse sampling algorithms: the bases-exchange walk on the bases of a matroid is such a walk, and its spectral analysis by Anari, Liu, Oveis Gharan and Vinzant (arXiv:1811.01816)…

15 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning IX: Cover's Universal Portfolio with Uniform or Dirichlet(1/2) Prior Has Logarithmic Regret Against Constantly Rebalanced PortfoliosTextbook

A portfolio manager chooses fractions of current wealth to place in several stocks before seeing that day’s market gains. The gains need not follow a statistical model: a sequence may be selected adversarially, with some stocks losing all value on a given day. A useful benchmark is the best constantly rebalanced portfolio, which holds the same fractions…

9 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

A Modern Introduction to Online Learning VIII: Tsallis-INF Has Adversarial Regret 32L∞√((d − 1)T) and Stochastic Pseudo-Regret 256L∞² Σ_i (1 + ln T)/Δ_iTextbook

In online learning with bandit feedback, the learner chooses one action and sees only that action's loss. This is the information pattern of sequential trials in which testing one option does not reveal the outcomes of the others. The learner must keep its cumulative loss close to that of a good fixed action while learning which actions are good. A…

6 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningProbability·Captain: mikedeng1

A Modern Introduction to Online Learning IV: Every Deterministic Online Linear Optimization Algorithm Has Regret at Least √2·LD√T/4Textbook

Online learning studies decisions made before their costs are known. An algorithm selects a point, observes a loss, and repeats. Regret compares its accumulated loss with the loss of one fixed point chosen after the sequence is known. Upper bounds show what a particular algorithm can guarantee; a lower bound shows what every algorithm must sometimes suffer.…

6 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear algebraMarkov Chain+1·Captain: mikedeng1

High Order Random Walks: Beyond Spectral Gap 1: On a One-Sided λ-Local Spectral Expander, ‖M⁺_k φ‖ ≤ ((k+1)/(k+2) + (k+1)λ/2)‖φ‖ for Every k-Cochain φ Orthogonal to the ConstantsResearch Paper

A high dimensional expander is a simplicial complex whose local structure forces global expansion. The high order random walks on such a complex move from a kkk-face to a kkk-face through a common (k+1)(k+1)(k+1)-face. They were studied for their connection to agreement tests in probabilistically checkable proofs (Dinur–Kaufman 2017; Kaufman–Mass 2017), and they later…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Joint Assortment Optimization and Customization under a Mixture of Multinomial Logit Models 1: Augmented Greedy Earns a (1 − 1/e) Fraction of the Optimal Revenue from the Complete Customer TypesResearch Paper

Retailers that carry a limited range of products often know something about a customer before choosing which of those products to display. The customized assortment problem asks which products to carry when the displayed assortment may be tailored to the arriving customer's type. This separates the first-stage capacity decision from the later offer…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryComplexity Theory·Captain: mikedeng1

Settling the Complexity of Computing Approximate Two-Player Nash Equilibria: An (ε, δ)-WeakNash of a Bipartite Polymatrix Game Yields a (√ε(√ε + 5), δ)-Well-Supported WeakNashResearch Paper

Computing an approximate Nash equilibrium of a two-player game is one of the central questions of algorithmic game theory. For a constant approximation ϵ\epsilonϵ, the algorithm of Lipton, Markakis and Mehta runs in quasi-polynomial time nO(log⁡n/ϵ2)n^{O(\log n/\epsilon^2)}nO(logn/ϵ2), and for a long time it was unknown whether polynomial time is possible. A. Rubinstein, Settling…

10 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming 2: One Aggressive Stepsize Policy Drives the AG Gradient Mapping to Zero on Nonconvex Composite ProblemsResearch Paper

Many problems in statistics, signal processing and machine learning have the form "smooth loss plus simple non-smooth term": a differentiable data-fit term together with a constraint set or a sparsity-inducing penalty such as the ℓ1\ell_1ℓ1​ norm. When the loss is convex, Nesterov's accelerated gradient (AG) method and its proximal variants are known to be…

17 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming 1: The AG Method Converges on Smooth Nonconvex Problems and Attains the Optimal Rate When Ψ Is ConvexResearch Paper

Accelerated gradient (AG) methods go back to Nesterov (1983), who showed that a first-order method with a momentum-like extrapolation reaches an ϵ\epsilonϵ-optimal value of a smooth convex function in O(1/ϵ)O(1/\sqrt\epsilon)O(1/ϵ​) iterations, against O(1/ϵ)O(1/\epsilon)O(1/ϵ) for gradient descent, and that this rate is optimal among first-order methods. Many objectives met in…

18 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Greed Works – Online Algorithms For Unrelated Machine Stochastic Scheduling 2: Greedy Assignment With Nominal Start Times Is (7.216 + 3.608Δ)h(Δ)-Competitive in the Online-Time ModelResearch Paper

Scheduling jobs on parallel machines to minimize the total weighted completion time ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​ is a basic model of service and computing systems. Two features of practice are hard to combine with performance guarantees: jobs are not known in advance but arrive over time, and their processing times are random, with only their distributions known when they…

12 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 2: Selling Two I.I.D. Goods Separately Guarantees at Least e/(e + 1) ≈ 73% of the Optimal RevenueResearch Paper

A seller with several goods can sell them one at a time or offer a mechanism that links allocation and payment across goods. Separate selling asks the seller to solve a one-good pricing problem for each item. A general mechanism can offer lotteries and menus whose outcomes depend on the buyer's whole valuation vector. The difference matters because the…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 5: Bundling Is Optimal for Two I.I.D. Goods Whose Density on [a, ∞) Satisfies x f′(x) + (3/2) f(x) ≤ 0Research Paper

A seller with several goods and a single buyer of unknown, additive valuation faces the multi-dimensional revenue maximization problem. For one good the answer is classical: by Myerson's theorem (Myerson 1981) a single posted price is optimal. For two or more goods no such simplification exists in general: optimal mechanisms may randomize, may offer menus…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Finding Cliques in Social Networks: A New Distribution-Free Model 1: Every Weakly c-Closed Graph on n Vertices Has at Most 3^((c−1)/3)·n² Maximal CliquesResearch Paper

Social networks exhibit triadic closure: two people with a common friend are more likely to be friends themselves than two people chosen at random, and the more common friends they have, the more likely they are to be connected. The principle goes back to sociology (Granovetter 1973) and is documented on large network data sets (see the Enron e-mail graph…

8 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Partially Observable Total-Cost Markov Decision Processes with Weakly Continuous Transition Probabilities 1: The Belief MDP Satisfies Assumption (W*) Under Total-Variation-Continuous ObservationsResearch Paper

A partially observable Markov decision process (POMDP) models a controller that cannot see the state of the system it steers, only noisy observations of it. Inventory control with unrecorded demand, machine maintenance with imperfect inspection, and target tracking from sensor readings all have this form. The standard way to solve a POMDP is to replace it…

16 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: mikedeng1

Regret in Online Combinatorial Optimization I: For Every Learning Rate the Exponentially Weighted Forecaster EXP2 Has Full-Information Regret at Least 0.01 d^{3/2}√n on Some Action SetResearch Paper

Online combinatorial optimization is a repeated game in which a learner selects, round after round, a structured object (a subset of fixed size, a path, a matching, a spanning tree) encoded as a 0/1 vector, and an adversary assigns a cost to every coordinate. It models routing, ranking, scheduling and many other sequential decision problems in operations…

7 thms4 active users
🏆Completed
OptimizationProbability·Captain: visuddhi

Information Limits of Multistage Inventory Control: BoundsResearch Paper

An inventory policy specifies how much stock to hold before demand arrives. Its financial value is the expected sum of holding and shortage costs. Learning a useful policy and estimating its value are different statistical tasks. This proposal starts the formalization of the principal bounds in Qin, Simchi-Levi and Zhu, Information Limits of Multistage…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Recovering Best Statistical Guarantees via the Empirical Divergence-Based Distributionally Robust Optimization 1: Empirical Burg-Ball DRO Bounds Cover E[h(x;ξ)] with Probability Tending to 1 − αResearch Paper

Stochastic programs and chance-constrained models in operations research contain expectations of the form

14 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals I: Under Random Arrival Order, Nonadaptive Thresholds Earn a 1 − 1/e Fraction of E[max Xᵢ]Research Paper

In a prophet inequality, a gambler sees prizes one at a time and must decide when to stop, while a prophet knows every realization and takes the largest. A stopping guarantee compares the gambler’s expected prize with the prophet’s. The order of arrival changes the problem: here the prizes are independent but can have different distributions, and every…

12 thms4 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals II: For I.I.D. Variables, Adaptive Thresholds Achieve E[max Xᵢ] ≤ β*·E[X_t] with β* ≈ 1.341Research Paper

A prophet inequality compares a gambler who sees nonnegative random rewards X1,…,XnX_1,\ldots,X_nX1​,…,Xn​ one at a time, and must accept or reject each on arrival, with a prophet who knows all values in advance and simply takes max⁡iXi\max_i X_imaxi​Xi​. For independent and identically distributed (i.i.d.) rewards the question is the best constant β\betaβ such that some online rule always…

17 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

A Little Charity Guarantees Almost Envy-Freeness III: With Additive Valuations, Donating the Pool to an Unenvied Agent Yields a 4/7-Groupwise-Maximin-Share AllocationResearch Paper

When indivisible goods are shared among people, comparing each person's bundle with another person's bundle is only one way to judge fairness. A second test asks whether a group could repartition the goods it collectively received so that one of its members would reliably obtain more. Groupwise maximin share (GMMS) makes this test for every subgroup. It…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

A Little Charity Guarantees Almost Envy-Freeness I: Under Monotone Valuations an EFX Allocation Exists Whose Unenvied Pool Has Fewer Goods Than There Are Unenvied AgentsResearch Paper

Allocating indivisible goods fairly is difficult because a single good can change how an agent compares two bundles. Exact envy-freeness can be impossible (one good, two agents), so the field works with relaxations. Envy-freeness up to any good (EFX) requires each agent to prefer her own bundle to every other agent's bundle after any one good of that other…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

A game-theoretic approach to computation offloading in mobile cloud computing II: The VI Map of the Offloading GNEP Is Monotone When the Cloudlet Is Not OverloadedResearch Paper

Mobile devices run applications whose computational demand often exceeds what a battery-powered processor can serve with acceptable delay. Computation offloading sends part of the work elsewhere: to a cloudlet, a small cluster of servers one wireless hop away, or to a distant cloud reached through the wide-area network. When many users share one cloudlet,…

10 thms4 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryGraph Theory·Captain: mikedeng1

Twin-width I: Tractable FO Model Checking 2: Every Subgraph of a Unit d-Dimensional Ball Graph with Clique Number k Has Twin-width at Most (3⌈√d⌉)^d·kResearch Paper

Twin-width is a graph parameter introduced by Bonnet, Kim, Thomassé and Watrigant in Twin-width I: Tractable FO Model Checking (J. ACM 69(1), Article 3, 2021; arXiv:2004.14789). Its main theorem says that first-order model checking is fixed-parameter tractable on every class of graphs of bounded twin-width, provided a witnessing contraction sequence is…

10 thms4 active usersReviewed
PreviousPage 28 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