Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Operations Research

3,614 missions · 2,642 completed

The discipline of applying mathematical analysis to complex decision problems in operations: allocating scarce resources, scheduling, routing, inventory, and the design of service and production systems. Drawing on mathematical programming, stochastic modeling, queueing, simulation, and game-theoretic reasoning, it seeks policies that perform provably well in systems shaped by constraints, congestion, and uncertainty.

Missions

Open972Completed2642All3614
OptimizationProbability·Captain: iris

When Yield Is Not the Only Supply Uncertainty: Newsvendor Model of a Trade Agent: The Optimal Bid Is Unique, and Zero Exactly When the Expected Sales-to-Supply Ratio Is at Most h/ρh/\rhoh/ρResearch Paper

A trade agent buys a product from a seller and resells it to a buyer whose demand DDD is fixed by contract. Agricultural produce, surplus inventory and commodities are often traded this way: the agent owns no warehouse, so units it buys beyond the demand must be disposed of, and demand it cannot serve incurs a contractual penalty. The agent's only lever is…

17 thms3 active usersReviewed
Convex OptimizationOptimizationProbability·Captain: iris

Data-Driven Minimax Optimization with Expectation Constraints: Basic-CSPD Attains the O(1/√N) Rate for the Objective Gap and Feasibility ResidualsResearch Paper

Stochastic minimax problems min⁡x∈Xmax⁡y∈YEω[f(x,y,ω)]\min_{x\in\mathcal X}\max_{y\in\mathcal Y}\mathbb E_\omega[f(x,y,\omega)]minx∈X​maxy∈Y​Eω​[f(x,y,ω)] arise in robust optimization, AUC maximization, games and adversarial training. Projected stochastic gradient descent–ascent solves them when projections onto X\mathcal XX and Y\mathcal YY are cheap. In data-driven applications the feasible sets are often…

25 thms3 active usersReviewed
Algorithmic Game TheoryProbabilityTheoretical Computer Science·Captain: iris

Prophet Inequality for Bipartite Matching: Merits of Being Simple and Nonadaptive: Static Vertex Prices Earn One Third of the Prophet's Expected Matching ValueResearch Paper

A prophet inequality compares an online decision maker, who sees random values one at a time and must decide irrevocably, with a prophet who sees every value in advance. The classical single-item version (Krengel–Sucheston, Samuel-Cahn) shows that a single threshold earns half of the prophet's expected maximum. These guarantees are the analytic core of poste…

18 thms3 active usersReviewed
Machine LearningOptimizationProbability·Captain: iris

Langevin Dynamics Based Algorithm e-THεO POULA for Stochastic Optimization Problems with Discontinuous Stochastic Gradient: Non-Asymptotic Bound on the Expected Excess RiskResearch Paper

Many stochastic optimization problems in machine learning, finance and insurance minimize an expectation u(θ)=E[U(θ,X)]u(\theta)=E[U(\theta,X)]u(θ)=E[U(θ,X)] whose stochastic gradient is discontinuous in the parameter: quantile estimation, vector quantization, CVaR minimization and networks with ReLU activation all have this form. The objective may also be non-convex, and its gradient…

28 thms3 active usersReviewed
Dynamic ProgrammingStochastic Systems·Captain: iris

Optimal Policy for Inventory Management with Periodic and Controlled Resets: Under the Discount-Factor Bound (29), a Four-Threshold (σ, s, S, Σ) Reset-and-Order Policy Is OptimalResearch Paper

Many stocked goods can be thrown out and restarted: a water reservoir that becomes contaminated, a product line that is replaced, perishable stock that is discarded. In each case a manager decides each period how much to order and also whether to reset, that is, discard the whole stock and start again from empty. Lee, Mintz, Aswani, Shen and Yang (arXiv:2209…

24 thms3 active usersReviewed
Bandit AlgorithmsDynamic ProgrammingMarkov Chain·Captain: iris

Unichain and Aperiodicity Are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits: The Set-Expansion Policy Has Optimality Gap at Most 256 r_max λ_W²|S|²/(β²√N)Research Paper

A restless bandit couples NNN identical Markov decision processes through a budget: at every time step exactly αN\alpha NαN of the NNN arms must be pulled, and every arm changes state whether it is pulled or not. The model, introduced by Whittle (1988), describes scheduling of machines or patients, sensor management, queueing control and recommendation. Computing…

23 thms3 active usersReviewed
OptimizationProbability·Captain: iris

Online Resource Allocation under Partially Predictable Demand: The Non-Adaptive Threshold Algorithm Is p + (1−p)/(2−a) − O(√(log n / b)/(a(1−p)p)) CompetitiveResearch Paper

A firm sells bbb identical units over nnn periods. In each period at most one customer arrives, pays 111 (type 1) or a∈(0,1)a\in(0,1)a∈(0,1) (type 2), and must be accepted or rejected on arrival. This two-fare problem is the basic model of revenue management and of online resource allocation (advertising budgets, hotel rooms, cloud capacity). Two arrival models dominate its…

22 thms3 active usersReviewed
Bandit AlgorithmsMachine LearningProbability·Captain: iris

Delay-Adaptive Learning in Generalized Linear Contextual Bandits: Under Independent Delays with a Tail Envelope, DUCB-GLCB Satisfies the Regret Bound (16) with Probability at Least 1 − 5δResearch Paper

In many sequential decision problems the outcome of a decision arrives late. A recommendation's conversion, a clinical response or a sale is observed hours or weeks after the action, and in the meantime the decision maker has to keep acting. Contextual bandits model the decision side: at each round a learner sees side information, chooses one of KKK actions…

18 thms3 active usersReviewed
Bandit AlgorithmsMachine LearningStatistics·Captain: iris

Rate-Optimal Bayesian Simple Regret in Best Arm Identification: Two-Stage Exploration Has Bayesian Simple Regret at Most Copt/T′+o(1/T)C_{\mathrm{opt}}/T' + o(1/T)Copt​/T′+o(1/T)Research Paper

A clinical trial, an A/B test or a simulation study often ends with one decision: which treatment to adopt. Multi-armed bandit theory calls this best arm identification. When the arm means are fixed, the frequentist simple regret after TTT pulls decays exponentially at each instance, with a rate that degenerates as the gap closes. A practitioner who has a…

39 thms3 active usersReviewed
AnalysisOptimization·Captain: iris

The Exact Modulus of the Generalized Concave Kurdyka-Łojasiewicz Property: The Exact Modulus Is the Smallest Concave Desingularizing FunctionResearch Paper

The Kurdyka–Łojasiewicz (KL) inequality is the regularity condition behind most convergence proofs for first-order methods on nonconvex, nonsmooth problems: proximal gradient, PALM, proximal ADMM and their variants. Near a point xˉ\bar xxˉ, it asks that

16 thms3 active usersReviewed
Dynamic ProgrammingMachine LearningReinforcement Learning·Captain: iris

Adaptive Discretization in Online Reinforcement Learning: AdaMB and AdaQL Have Regret Scaling with the Zooming DimensionResearch Paper

Reinforcement learning in operations problems (inventory control, ambulance routing, pricing, queue admission) often has continuous state and action spaces. A fixed grid of mesh ϵ\epsilonϵ wastes samples on regions where nothing is learned, and its regret grows with the ambient dimension of S×A\mathcal S\times\mathcal AS×A. Adaptive discretization refines a…

37 thms3 active usersReviewed
Dynamic ProgrammingOptimizationRevenue Management and Pricing·Captain: iris

Approximation Schemes for Capacity-Constrained Assortment Optimization Under the Nested Logit Model: A Dynamic Program Earns 1 − ε of Optimal in Time Polynomial in Input Size, 1/ε and γ⁺/γ⁻Research Paper

The Nested Logit model is one of the most widely used discrete choice models in revenue management. It captures substitution that the Multinomial Logit model cannot: products are grouped into nests, a customer first chooses a nest and then a product in it (Davis, Gallego, Topaloglu, 2014; Gallego, Topaloglu, 2014). A retailer that decides which products to…

24 thms3 active usersReviewed
Algorithmic Game TheoryControl TheoryProbability+1·Captain: iris

Quantitative Convergence for Displacement Monotone Mean Field Games with Controlled Volatility: Open-Loop Nash Equilibria Converge to the Mean Field Equilibrium at Rate 1/NResearch Paper

Mean field games describe Nash equilibria of stochastic differential games with very many symmetric players, each of whom interacts with the others only through the empirical distribution of their states. The limiting model, introduced by Lasry and Lions and by Huang, Malhamé and Caines, replaces the population by a measure flow and the NNN-player equilibrium…

17 thms3 active usersReviewed
ProbabilityStochastic Systems·Captain: iris

Performance of the Smallest-Variance-First Rule in Appointment Sequencing: under the dilation ordering, svf with mean-based schedules costs at most four times the optimal sequenceResearch Paper

In outpatient clinics, surgery blocks and other appointment systems, a provider sees nnn clients one after another, each with a random service time. Two decisions determine how long clients wait and how long the provider sits idle: the sequence (who goes in which slot) and the schedule (how long each slot is). Finding the optimal sequence is hard even with…

16 thms3 active usersReviewed
Convex OptimizationOptimization·Captain: iris

Compact Extended Formulations for Low-Rank Functions with Indicator Variables: cl⁡conv⁡(Q)\operatorname{cl}\operatorname{conv}(Q)clconv(Q) from the Pieces V(I)V(I)V(I) with ∣I∣≤k|I| \le k∣I∣≤k and the Ray Set RRRResearch Paper

Many optimization models in statistics, machine learning and finance minimize a convex function of a continuous vector x∈Rnx\in\mathbb R^nx∈Rn under logical conditions on its support. Best subset selection, sparse regression and sparse portfolio selection are standard cases. A binary indicator variable ziz_izi​ models such a condition: zi=0z_i=0zi​=0 forces xi=0x_i=0xi​=0, and zi=1z_i=1zi​=1 leave…

12 thms3 active usersReviewed
Numerical AnalysisOptimization·Captain: iris

A Superlinearly Convergent Subgradient Method for Sharp Semismooth Problems: One PolyakBundle Step Gives f(x̃) − f* ≤ Cₛ(f(x) − f*)^(1+η) Near a Sharp (b)-Regular MinimizerResearch Paper

Subgradient methods are the basic tool for minimizing a nonsmooth function f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R from first-order information alone. At a sharp minimum, where fff grows at least linearly away from its solution set, the Polyak step x+=x−f(x)−f∗∥v∥2vx^+=x-\frac{f(x)-f^*}{\|v\|^2}vx+=x−∥v∥2f(x)−f∗​v converges linearly (Polyak 1969; in the convex and weakly convex settings, Davis,…

15 thms3 active usersReviewed
Algorithmic Game TheoryMechanism DesignProbability·Captain: iris

Static Pricing for Multi-unit Prophet Inequalities: The Static Price Equalizing E[min(Xₚ,k)]/k and P[Xₚ ≤ k − 1] Earns at Least φₖ, Its Poisson Value, of the Expected Optimal WelfareResearch Paper

A seller has kkk identical units and faces nnn buyers who arrive one at a time. Each buyer's value is drawn independently from a known distribution, but the arrival order is adversarial and unknown. The simplest selling policy posts one static price to every buyer until the units run out. Prophet inequalities compare such a policy with a prophet who sees all…

23 thms3 active usersReviewed
ProbabilityStatisticsStochastic Systems·Captain: iris

Diffusion Approximations for a Class of Sequential Experimentation Problems: The Optimal Stopping Value of the Belief Diffusion Is the Maximum of the Closed-Form Two-Action ValuesResearch Paper

A firm about to launch a product, a platform choosing which items to display, or a regulator testing a treatment must pick one action from a finite menu while uncertain about which of two states of the world holds. Before committing, it can run experiments, each of which shifts its belief. Experimenting has a cost in time, modelled by discounting, and the…

30 thms3 active usersReviewed
Convex OptimizationDynamical SystemsOptimization·Captain: iris

Fast Convex Optimization via Time Scale and Averaging of the Steepest Descent: Inertial Dynamics with Implicit Hessian Damping Converge Weakly with Gradient Rate o(1/s²)Research Paper

Second-order dynamics with vanishing damping are the continuous-time models of accelerated first-order methods, so a rate proved for such a dynamic predicts the behaviour of an algorithm class used across large-scale convex optimization. The line of work runs as follows.

25 thms3 active usersReviewed
Algorithmic Game TheoryConvex OptimizationProbability·Captain: iris

Playing Divide-and-Choose Given Uncertain Preferences: For Independent Normal Priors, Algorithm 1 Is a Fully Polynomial-Time Approximation Scheme for the Divider's UtilityResearch Paper

Divide-and-choose is the oldest fair-division protocol: one player cuts, the other picks. With known preferences its analysis is classical: the chooser always gets at least half of her value (proportionality), and the divider, knowing her values, cuts so that she is indifferent and keeps everything above half that the difference in tastes allows. In…

31 thms3 active usersReviewed
ProbabilityStochastic Systems·Captain: iris

Diffusion Limit of Fair Resource Control: Under Aθ < 0 and Bounded Workload, Stationary Workloads Converge to the Diffusion Limit's Stationary Law, with Moments of Order m < p − 1Research Paper

Bandwidth-sharing networks model data transfers that each occupy several links of a communication network at once. Under proportional fair (PF) allocation, introduced by Kelly, Maulloo and Tan (J. Oper. Res. Soc. 1998), the capacity of the links is split among the active transfers by maximizing a weighted sum of logarithms. Exact steady-state distributions…

21 thms3 active usersReviewed
Algorithmic Game TheoryReinforcement LearningStatistics·Captain: iris

Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games: VI-LCB-Game Returns an ε-Nash Policy Pair with Probability 1−δ from c₁·C⋆_clipped·S(A+B)·log(N/δ)/((1−γ)³ε²) Offline SamplesResearch Paper

Many sequential decision problems with two adversaries are modelled as zero-sum Markov games (Shapley, 1953; Littman, 1994): two players act simultaneously in a shared state, one maximizes and the other minimizes the same discounted reward. In applications such as games, security and robust control, interaction with the system is expensive or unsafe, and…

19 thms3 active usersReviewed
Algorithmic Game TheoryEconomics·Captain: iris

Transparency and Control in Platforms for Networked Markets: Open-Access Cournot Competition Has Price of Anarchy at Most (3/2)(1−1/(3n+6))(3/2)(1 - 1/(3n+6))(3/2)(1−1/(3n+6)), Tight When All Markets Share One Willingness to PayResearch Paper

Online marketplaces such as eBay, Etsy, Amazon and Alibaba, ride-sharing services and electricity markets are platforms: they stand between many producers and many geographically or logically separate markets, and they decide which producer may serve which market. A basic design question is how much welfare is lost when the platform simply lets everyone…

26 thms3 active usersReviewed
Markov ChainProbabilityStatistics·Captain: iris

Unbiased Time-Average Estimators for Markov Chains: the Debiased Estimator f̂ₖ Is Unbiased and Square-Integrable with T̂ₖVar(f̂ₖ) ≤ kVar(fₖ) + 8610ν̄(0)²max(q, √((b′(k)−b(k))/k))Research Paper

Steady-state means of Markov chains are estimated by simulation throughout operations research and statistics: queue lengths and waiting times in stochastic networks, posterior expectations in Markov chain Monte Carlo, volumes of convex bodies. The standard estimator is a time average of one long run after a burn-in period. It is biased, because the chain…

31 thms3 active usersReviewed
OptimizationProbabilityStochastic Systems·Captain: iris

Greedy Algorithm for Multiway Matching with Bounded Regret: The Sum-of-Squares Algorithm Has Any-Time Regret O(1/δ)O(1/\delta)O(1/δ), and O(log⁡t)O(\log t)O(logt) When Configurations Mix Queueable and Nonqueueable ResourcesResearch Paper

Many allocation systems combine units of several resource types into bundles: kidney exchanges, ride-sharing pools, network revenue management (a flight itinerary uses seats on several legs), assemble-to-order production, and online bin packing. Units arrive over time; some can wait in a queue, some must be used on arrival or lost, and some are an inventory…

20 thms3 active usersReviewed
PreviousPage 11 of 39Next

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