Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Probability

2,743 missions · 1,549 completed

Missions

Open1194Completed1549All2743
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Algorithmic Mechanism Design V: The Randomly Biased Min Work Mechanism Is a Strongly Truthful 7/4-Approximation for Two AgentsResearch Paper

Algorithmic mechanism design, introduced by Nisan and Ronen (Games Econ. Behav. 35, 2001), studies optimization problems whose input is held by self-interested agents. Each agent reports its private data to a protocol, and the protocol must choose an output and payments so that reporting the truth is in every agent's interest while the chosen output is…

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

Single Machine Scheduling with Release Dates III: The Random Per-Job α-Schedule with a Truncated Exponential DensityResearch Paper

Scheduling jobs with release dates on one machine to minimize the total weighted completion time, written 1∣rj∣∑wjCj1|r_j|\sum w_jC_j1∣rj​∣∑wj​Cj​, is strongly NP-hard even with unit weights (Lenstra, Rinnooy Kan & Brucker, 1977). It is a basic model of scheduling theory and a standard testbed for approximation algorithms built on linear programming relaxations. Several LP…

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

Single Machine Scheduling with Release Dates II: The Random α-Schedule with a Truncated Exponential DensityResearch Paper

Minimizing the total weighted completion time ∑jwjCj\sum_j w_j C_j∑j​wj​Cj​ of jobs with release dates on a single machine, written 1 ∣ rj ∣ ∑wjCj1\,|\,r_j\,|\,\sum w_j C_j1∣rj​∣∑wj​Cj​ in scheduling notation, is strongly NP-hard. It is one of the basic models of machine scheduling, and it has served as a test case for a general technique in approximation algorithms: solve a linear programming…

18 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryDynamical SystemsStochastic Systems·Captain: mikedeng1

On the Global Convergence of Stochastic Fictitious Play II: Almost Sure Convergence in Zero-Sum Games and Symmetric Games with an Interior ESSResearch Paper

Fictitious play is the oldest model of learning in games: players repeatedly play a fixed normal form game, and each round every player best-responds to the empirical frequencies of the opponents' past play. Brown (1951) proposed it as an algorithm for computing the value of a zero-sum game, and Robinson (1951) proved that the empirical frequencies converge…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research·Captain: mikedeng1

On the Global Convergence of Stochastic Fictitious Play I: Every Additive Random Utility Choice Function Has an Admissible Deterministic Perturbation RepresentationResearch Paper

Models of learning in games, and discrete choice models in econometrics, describe an agent who does not always pick the best alternative. Two descriptions of such an agent are standard. In the additive random utility model (McFadden 1981; Anderson, de Palma and Thisse 1992) the agent maximizes payoffs perturbed by random shocks. In the deterministic…

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

The Distributionally Robust Chance-Constrained Vehicle Routing Problem V: Worst-Case Value-at-Risk over Covariance Ambiguity Sets as a Quadratically Constrained ProgramResearch Paper

In the capacitated vehicle routing problem (CVRP) a fleet of mmm vehicles of capacity QQQ leaves a depot and serves nnn customers; every customer is visited once, and the load of each route must not exceed QQQ. In practice customer demands are uncertain at planning time. The chance-constrained CVRP asks that each route respect the capacity with probability at least …

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

The Distributionally Robust Chance-Constrained Vehicle Routing Problem IV: Worst-Case Value-at-Risk over First-Order Generic Moment Ambiguity Sets as a Convex ProgramResearch Paper

In the capacitated vehicle routing problem (CVRP) a depot serves customers VC={1,…,n}V_C=\{1,\dots,n\}VC​={1,…,n} with mmm vehicles of capacity QQQ, and every route must respect the capacity. When customer demands are uncertain, the distributionally robust chance-constrained CVRP of Ghosal and Wiesemann (Oper. Res. 68(3), 2020) requires every route to meet its capacity with…

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

The Distributionally Robust Chance-Constrained Vehicle Routing Problem III: Worst-Case Value-at-Risk Is Additive over Marginalized Moment Ambiguity SetsResearch Paper

The capacitated vehicle routing problem (CVRP) assigns customers to a fleet of mmm identical vehicles of capacity QQQ and orders each vehicle's visits so as to minimize transportation cost, subject to each vehicle's total load not exceeding QQQ. In practice the customers' demands are not known when the routes are planned. Two classical responses are the robust CVR…

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

The Distributionally Robust Chance-Constrained Vehicle Routing Problem II: Moment Ambiguity Sets Give Subadditive Demand EstimatorsResearch Paper

The capacitated vehicle routing problem (CVRP) asks for a set of minimum-cost routes by which a fleet of identical vehicles of capacity QQQ, based at a depot, serves every customer exactly once without any vehicle carrying more than its capacity. In practice customer demands are not known when routes are planned. Ghosal and Wiesemann (Oper. Res. 68(3), 2020)…

4 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Applied Combinatorics X: The Lovász Local Lemma and the Gale–Ryser TheoremTextbook

Chapter 16 of Keller and Trotter's Applied Combinatorics (2017 Edition, CC BY-SA 4.0) is a survey of seven topics. Two of them are self-contained results with complete proofs on the page, and this mission formalizes both.

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

Applied Combinatorics VI: Ramsey's Theorem and Erdős's Lower BoundTextbook

Ramsey theory studies the principle that complete disorder is impossible: every sufficiently large structure contains a large, perfectly uniform substructure. Its most familiar instance concerns graphs. In any graph on six vertices there are three vertices that are pairwise adjacent or three that are pairwise non-adjacent, and the same phenomenon persists…

7 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: Shuze Chen

Markov Decision Processes XIX: Theory of Optimal Stopping ProblemsTextbook

A gambler watching a sequence unfold has to decide, at each moment and knowing only the past, whether to take what is on the table or wait for something better. That is the whole of optimal stopping, and it is one of the few problems in stochastic control with a clean and completely general answer: the value of the problem is the smallest superharmonic…

16 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

Star-Shaped Risk Measures 2: law-invariant star-shaped risk measures as robustified Value-at-RiskResearch Paper

Financial regulators and risk managers summarise the loss distribution of a position by a single number, the capital that must be held against it. The two standards in practice are Value-at-Risk (VaR), a quantile of the loss, and expected shortfall (ES), an average of the upper quantiles; ES is the standard of the Basel framework. Both depend on the…

7 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: Shuze Chen

Markov Decision Processes XV: Optimal Play in Red-and-Black and the Gittins IndexTextbook

Chapter 7's abstract machinery — contracting Markov Decision Models, the Structure Theorem, value iteration with an explicit convergence rate — earns its keep by solving concrete problems. Section 7.6 works through four kinds of application: a return to the classical cash-balance inventory problem, now over an infinite horizon; the "red-and-black" gambling…

17 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: Shuze Chen

Markov Decision Processes VII: Consumption-Investment Problems and Regime SwitchingTextbook

Real investors do not merely accumulate wealth for a single terminal payoff; they consume along the way, and the market they invest in is rarely a single fixed statistical regime for years at a time — bull and bear markets, business cycles, and volatility regimes shift the distribution of returns. Bäuerle and Rieder's §4.3 extends the terminal-wealth theory…

16 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryOperations Research+2·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions V: Beating 1/2 for Symmetric Functions Requires Exponentially Many Value QueriesResearch Paper

Maximizing a nonnegative submodular set function without constraints contains Max Cut, Max Directed Cut and facility-location problems as special cases. In the value-oracle model an algorithm knows nothing about the function except the values f(S)f(S)f(S) of the sets SSS it queries, and it is judged by the number of queries it makes. Feige, Mirrokni and Vondrák (SIAM…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions IV: Smooth Local Search Achieves 2/5 of the OptimumResearch Paper

Many optimization problems ask for a subset of a finite ground set that maximizes a submodular function, a set function with diminishing marginal returns. Max Cut and Max Directed Cut in graphs, facility location with fixed costs, and the maximization of mutual information or entropy of a subset of random variables are all of this form. Unlike the monotone…

14 thms3 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisRandom Matrix Theory·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix IV: Sample Bound for Hutchinson's Trace EstimatorResearch Paper

Many computations need the trace of a matrix AAA that is never formed explicitly and can only be applied to vectors: the trace of a matrix function such as trace(A−1)\mathrm{trace}(A^{-1})trace(A−1) or log⁡det⁡A=trace(log⁡A)\log\det A = \mathrm{trace}(\log A)logdetA=trace(logA) in statistics and lattice QCD, the Frobenius norm ∥B∥F2=trace(BTB)\|B\|_F^2 = \mathrm{trace}(B^TB)∥B∥F2​=trace(BTB) of an operator, or the number of triangles of a graph. The…

7 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: Shuze Chen

Markov Decision Processes II: Existence of Optimal Policies under Compactness and ContinuityTextbook

The finite-horizon theory of chunk 02a-model-bellman-equation (Bäuerle and Rieder's Theorem 2.3.8, the Structure Theorem) reduces the existence of an optimal policy and the validity of the Bellman equation to a single abstract hypothesis: the Structure Assumption (SAN), the existence of function classes IMn\mathrm{IM}_nIMn​ and decision-rule classes Δn\Delta_nΔn​ closed…

14 thms3 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisRandom Matrix Theory·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix II: Exact Rank of a Projection Matrix from the Gaussian Trace EstimatorResearch Paper

Many matrices in scientific computing are available only implicitly: one can multiply a vector by AAA, for instance by solving a linear system or applying a matrix function, but the entries of AAA are never formed. Quantities such as the trace must then be estimated from a small number of matrix–vector products. Randomized trace estimators do exactly this: draw…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: Shuze Chen

Processing Networks XI: Maximal Stability of Workload-Weighted Task AllocationTextbook

Large-scale data-intensive computing splits a job into many small "map tasks," each of which must be assigned to one of thousands of general-purpose servers in a data center — the MapReduce paradigm introduced by Dean and Ghemawat (2008). Because a task's input data is stored on only a few of those servers, routing it to a server that already holds its data…

10 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem: The Base Stock Ordering Policy Is OptimalResearch Paper

An inventory manager who stocks many products, faces random demand and pays ordering, holding and shortage costs must decide each period how much of each product to order. In general the optimal decision depends on the whole state and is found by solving a dynamic programme, which becomes impractical as the number of products grows. Myopic (or base stock)…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: Shuze Chen

Processing Networks X: Maximal Stability of Proportionally Fair ControlTextbook

Mission IX (09-proportional-fairness-core) formalized proportional fairness (PF) as a control policy and proved the technical core of its stability theory: under a load condition, the PF fluid model is stable (Theorem 10.5), via an entropy Lyapunov function that is genuinely not Lipschitz continuous — a departure from every other stability argument in J. G.…

13 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

An Overview of Pricing Models for Revenue Management: Performance Guarantee of the Deterministic Price Heuristic in Periodic-Review PricingResearch Paper

Dynamic pricing under limited inventory is a core problem of revenue management: a seller holds C0C_0C0​ units of a perishable product (airline seats, hotel rooms, seasonal goods) and must choose prices over a finite selling horizon while demand is random and responds to price. The exactly optimal policy solves a stochastic dynamic program whose state is the…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: Shuze Chen

Processing Networks IX: Fluid Stability of the Proportionally Fair AllocationTextbook

Every control policy formalized so far in this series — HLSPS (mission VI), back-pressure/ max-weight (mission VIII) — allocates service effort to entire job classes as indivisible units. Proportional fairness takes a different starting point: it is a general-purpose recipe for dividing a shared, continuously divisible resource among competing demands,…

12 thms3 active usersReviewed
PreviousPage 35 of 62Next

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