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
🏆Completed
Optimization·Captain: mikedeng1

Product Price, Quality and Service Decisions under Consumer Choice Models III: The Optimal Uniform Service Duration Is the Shortest or the LongestResearch Paper

Firms that sell durable goods compete on price, on product quality and on the services bundled with the product: a factory warranty, free maintenance, technical support. Wang, Ke and Cui (SSRN 3766191; Manufacturing & Service Operations Management, 2022, doi:10.1287/msom.2020.0947) study the joint choice of all three when consumers choose among the firm's…

18 thms6 active users
🏆Completed
Bandit AlgorithmsMachine LearningStatistics·Captain: mikedeng1

Distribution-Free Contextual Dynamic Pricing 1: The DIP Policy Has Expected Regret at Most C T^(2/3) log T Plus 4 p_max L Times the Episode-Weighted ℓ₁ Estimation ErrorsResearch Paper

In contextual dynamic pricing a seller posts a price for each arriving customer, observes only whether the customer buys, and must learn the demand from these binary responses while selling. The problem arises in e-commerce, insurance and consumer lending, where every customer comes with features (product attributes, customer characteristics) that shift the…

18 thms6 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationMachine Learning·Captain: mikedeng1

Fast Convergence of Regularized Learning in Games II: If Every Player Runs Optimistic FTRL with Step Size (n−1)^{−1/2}T^{−1/4}, Each Player's Regret Is at Most (R+4)√(n−1)·T^{1/4}Research Paper

When every participant in a repeated game runs a no-regret learning algorithm, the time-averaged play converges to a coarse correlated equilibrium, and in smooth games the average welfare approaches the price-of-anarchy guarantee. These facts are a standard justification for equilibrium predictions in auctions, routing and markets, where agents learn rather…

15 thms6 active users
🏆Completed
Bandit AlgorithmsMachine LearningStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems V: Symmetric Monotonic Strategies Draw the Suboptimal Arms Collectively a Linear Number of TimesResearch Paper

In a stochastic multi-armed bandit, a player repeatedly chooses one of KKK arms and receives a random reward drawn from the chosen arm's unknown distribution. The classical lower bounds of Lai and Robbins (1985) and Burnetas and Katehakis (1996) describe the regret of good strategies when the horizon TTT tends to infinity: it grows like ln⁡T\ln TlnT, with a constant…

15 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems VI: Uniformly Super-Fast Convergent Strategies Draw Each Suboptimal Arm ln T / K_inf Times up to Explicit Lower-Order TermsResearch Paper

In a stochastic multi-armed bandit, a decision maker repeatedly chooses one of several unknown reward sources. Sampling an arm reveals its reward but uses a round that could have been spent on a better arm. A good strategy must therefore reduce sampling of inferior arms, yet it cannot stop sampling them too early: it must still distinguish the current…

14 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems IV: Under Pairwise Symmetry a Suboptimal Arm Is Drawn T/K Times or Almost as Often as an Optimal ArmResearch Paper

Lower bounds for stochastic multi-armed bandits are usually stated for a large horizon: Lai and Robbins (1985) and Burnetas and Katehakis (1996) show that a consistent strategy pulls a suboptimal arm at least about ln⁡T/Kinf⁡\ln T / \mathcal{K}_{\inf}lnT/Kinf​ times. These bounds say nothing about the small-horizon regime, the first rounds in which a strategy has not yet had…

11 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems II: Uniformly Fast Convergent Strategies Draw Every Suboptimal Arm at Least ln T / K_inf Times AsymptoticallyResearch Paper

In a stochastic multi-armed bandit, a player repeatedly chooses one of finitely many arms and sees only the reward from the chosen arm. To earn a high reward, the player must favor arms that appear best. Yet an arm that currently appears inferior might be best under another plausible reward law. That uncertainty forces any strategy with uniformly strong…

11 thms6 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: mikedeng1

Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming 3: The Two-Phase RSG Method Finds an (ε, Λ)-Solution within S(Λ)[N(ε) + T(ε, Λ)] Oracle CallsResearch Paper

Stochastic optimization methods often see only noisy gradients. For a nonconvex objective, a useful guarantee is that an output point has a small gradient: this is a first-order stationarity certificate, even when there is no claim that the point is globally optimal. A guarantee on the expected squared gradient leaves open how often one particular run…

14 thms6 active users
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

On the Complexity of Nash Equilibria and Other Fixed Points 3: In Every Nash Equilibrium of Bubelis's Gadget the Primary Player Plays 0 with Probability α, the Unique Root of f in [0, 1]Research Paper

For games with three or more players, Nash equilibria can be irrational, so they cannot in general be computed exactly. Bubelis made this precise: any real root of any univariate polynomial arises as the probability of a particular strategy, or the payoff of a particular player, in a Nash equilibrium of a three-player game whose payoffs depend on the…

11 thms6 active usersReviewed
🏆Completed
Complexity TheoryOptimizationTheoretical Computer Science·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 6: PARTITION Reduces to Two Agents Each Bounding Their Own Total Completion Time on One MachineResearch Paper

In many production and service settings a single resource is shared by parties with different goals: two departments sending orders to the same machine, two customers of a contract manufacturer, or two classes of requests on one processor. Multi-agent scheduling models this directly. Each agent owns its own jobs and its own objective, and a schedule is…

16 thms6 active usersReviewed
🏆Completed
Complexity TheoryOptimizationTheoretical Computer Science·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 2: KNAPSACK Reduces to Minimizing One Agent's Total Weighted Completion Time Under a Makespan Bound for the OtherResearch Paper

In many production and logistics settings a single resource is shared by parties with different goals: two departments of a plant that send orders to the same machine, two customers of a contract manufacturer, or two classes of traffic on one processor. Multi-agent scheduling models this directly. Each agent owns its own jobs and its own objective, and a…

14 thms6 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear algebra·Captain: mikedeng1

Flows and Decompositions of Games: Harmonic and Potential Games 3: In Every Harmonic Game the Uniformly Mixed Strategy Profile Is a Mixed Nash EquilibriumResearch Paper

Finite games in strategic form are the basic model of strategic interaction in economics, engineering and computer science. Potential games (Monderer and Shapley, 1996, DOI 10.1006/game.1996.0044) are the class with the most tractable equilibrium behaviour: every finite potential game has a pure Nash equilibrium, and simple learning dynamics converge to one.

13 thms6 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Consumer Returns Policies and Supply Chain Performance 1: With Valuations Learned after Purchase, the Seller's Optimal Policy Is p* = E max(V, s), F̄(q*) = (c − s)/(p* − s), r* = sResearch Paper

Retailers accept large volumes of returned merchandise, and a common default is the full refund: a buyer who is unhappy with a product brings it back and gets the whole price back. Many consumers only learn how much they value a product after they have it at home — clothes that do not fit, a gadget that does not suit the buyer's needs. A returns policy…

15 thms6 active users
🏆Completed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Worst-Case Equilibria II: On Two Links with Speeds s₁ ≤ s₂ ≤ φs₁ Some Nash Equilibrium Has Expected Makespan 1 + s₂/(s₁ + s₂) Times the Optimum, Reaching φ at s₂ = φs₁Research Paper

When many independent users share a network, each routes its own traffic to minimize its own delay, and nobody optimizes the system as a whole. Koutsoupias and Papadimitriou asked how much this lack of coordination can cost: how far the social cost of a Nash equilibrium can be from the social optimum, in the worst case. Their paper Worst-case equilibria (STA…

11 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

MNL-Bandit: A Dynamic Learning Approach to Assortment Selection III: On Instances Separated by Δ(v) the UCB Policy Has Regret at Most B₁N² log T/Δ(v) + B₂Research Paper

A retailer with limited shelf or screen space must choose which subset of its products to show each arriving customer. Which assortment earns the most depends on customer preferences, and those are unknown at first: the seller learns them from the purchases it observes. This is dynamic assortment selection, and it is a standard model in online retail and…

10 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsStochastic Systems·Captain: mikedeng1

On the Gittins Index for Multiarmed Bandits 2: A Policy Falls Short of the Gittins Policy by at Most Its Expected Discounted Gap Between the Greatest Gittins Index and That of the Bandit It PlaysResearch Paper

The multiarmed bandit problem asks how to allocate a single resource, one play at a time, among several alternative projects whose states evolve only when they are worked on. It models the scheduling of jobs on a single machine, the design of sequential clinical trials and many problems of research planning. Gittins and Jones showed that it is optimal to…

11 thms6 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Scenarios and Policy Aggregation in Optimization Under Uncertainty 2: A Limit of Locally Optimal Progressive Hedging Steps Is a Stationary Point of the Nonconvex ProblemResearch Paper

Multistage decision problems under uncertainty are often modelled by a finite set of scenarios: each scenario sss fixes one possible future, and for it a deterministic problem can be solved. What makes the problem stochastic is the requirement that decisions may depend only on information available at the time they are taken. Rockafellar and Wets (WP-87-119,…

15 thms6 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Revenue Management Under a General Discrete Choice Model of Consumer Behavior 3: The Multinomial Logit Model Has the Nesting-by-Fare-Order PropertyResearch Paper

Airline and hotel revenue management sells one perishable resource (seats on a flight, rooms on a night) through several fare products at different prices. The classical models of Littlewood (1972), Belobaba (1989) and Lee and Hersh (1993) assume independent demand: a customer who wants fare class jjj either buys class jjj or leaves, whatever else is on offer.…

16 thms6 active users
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Revenue Management Under a General Discrete Choice Model of Consumer Behavior 2: Nesting by Fare Order Holds Iff Purchase Probability Increases and Mixtures of Complete Sets Majorize Incomplete SetsResearch Paper

Airline and hotel revenue-management systems have traditionally been built around nesting by fare order: classes are ranked by price, and as capacity runs short the cheapest open class is closed first, so that the set of open fares is always a top segment {1,…,k}\{1, \dots, k\}{1,…,k} of the fare ladder. This structure is what makes booking limits, protection levels and…

10 thms6 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 4: KNAPSACK Reduces to Single-Machine Total Completion Time with One Release DateResearch Paper

Minimizing the total completion time ∑jCj\sum_j C_j∑j​Cj​ of jobs on a single machine is one of the oldest problems in scheduling theory. When every job is available at time 000, processing the jobs in order of nondecreasing processing time is optimal (the shortest-processing-time rule), so the problem is solved by sorting. Release dates, times before which a job may…

18 thms6 active usersReviewed
🏆Completed
Convex OptimizationOptimizationStochastic Systems·Captain: mikedeng1

Loss Networks 2: The Erlang Fixed Point Is E_j = 1 − exp(−y_j) for the Unique Optimum y of the Strictly Convex Revised Dual ProblemResearch Paper

A loss network is a model of a circuit-switched network: telephone networks, and more generally any system in which a request seizes several resources at once and is lost if any of them is unavailable. Exact loss probabilities in such networks are given by a product-form distribution over a state space whose size grows exponentially with the number of…

15 thms6 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 7: Makespan Reduces to Total Completion Time on Identical Machines with Precedence ConstraintsResearch Paper

Scheduling jobs on parallel machines under precedence constraints is the core model of project and parallel-processing scheduling: a job may start only after its predecessors have finished. Two criteria dominate the literature, the makespan Cmax⁡C_{\max}Cmax​ (when does the last job finish?) and the total completion time ∑jCj\sum_j C_j∑j​Cj​ (how long do jobs wait on…

20 thms6 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 6: DIRECTED HAMILTON PATH Reduces to No-Wait Flow Shop Makespan and Total Completion TimeResearch Paper

In a no-wait flow shop every job passes through the machines M1,…,MmM_1,\dots,M_mM1​,…,Mm​ in the same order, and once it has started it may never wait between two machines. The constraint comes from processes in which the material changes state if it is left standing, such as hot metal rolling, chemical and food processing, and some pharmaceutical lines; see the survey of…

25 thms6 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 3: KNAPSACK Reduces to Single-Machine Total Weighted TardinessResearch Paper

Minimizing total weighted tardiness on a single machine, written n∣1∣∣∑wjTjn|1||\sum w_jT_jn∣1∣∣∑wj​Tj​, is one of the basic problems of deterministic scheduling. A job that finishes after its due date is penalized in proportion to its lateness and its weight. Practitioners use this criterion to model penalty clauses and customer priority. In the theory it was a reference…

23 thms6 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 2: KNAPSACK Reduces to Single-Machine Maximum Lateness, Weighted Number of Late Jobs, and Weighted Completion Time with DeadlinesResearch Paper

Deterministic machine scheduling was one of the first application areas of the theory of NP-completeness. After Cook (1971) and Karp (1972) showed that a large family of combinatorial problems are polynomially equivalent, Brucker, Lenstra and Rinnooy Kan set out to locate the boundary between the polynomially solvable and the NP-complete scheduling…

15 thms6 active usersReviewed
PreviousPage 3 of 106Next

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