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
Algorithmic Game TheoryMechanism DesignProbability·Captain: Shuze Chen

Robust Analysis of First-Price Auctions with Large SupplyResearch Paper

Auctions that sell many identical units to many bidders, such as treasury bills, emission permits and advertising slots, are often run as multi-unit first-price auctions: the highest bids win and each winner pays its own bid. Bidders then shade their bids below their values. In equilibrium, a bidder with a higher value can lose to one with a lower value, so…

18 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatorics·Captain: Shuze Chen

Counterexamples to EFX for Submodular and Subadditive ValuationsResearch Paper

Dividing a set of indivisible goods among agents with different tastes is a basic problem of fair division, with applications from inheritance and course allocation to the sharing of computing resources. Exact envy-freeness (no agent prefers another agent's bundle to its own) cannot always be achieved with indivisible goods: a single good and two agents…

10 thms4 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

A Simple Computer-Assisted Proof of the 5/6-Bound for Real-Period Pinwheel SchedulingResearch Paper

A machine that performs one task each day may need to revisit several tasks indefinitely. Pinwheel scheduling asks whether all required revisit frequencies can be met by a single daily assignment. The requirement concerns every consecutive block of days: a good long-run average alone does not prevent a task from waiting too long. This distinction makes the…

948 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignProbability·Captain: mikedeng1

Persuasion by PartsResearch Paper

An information designer may know the distribution of a system's total benefit while each observer sees only one contribution. A supplier can grade its own component; a regional office can evaluate its own market. A receiver combines these reports before deciding whether the total justifies action. The designer can commit to reporting rules in advance, but…

16 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsTheoretical Computer Science·Captain: iris

A 2.81n2.81^n2.81n upper bound on the number of stable matchingsResearch Paper

A stable matching instance has nnn men and nnn women, each ranking the other side strictly. Gale and Shapley showed that a stable matching always exists (1962). How many there can be is a question Knuth posed in 1976, and it is listed among the open problems of Gusfield and Irving (1989), Manlove (2013) and Cechlárová, Cseh and Manlove (2019). The answer…

25 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOptimization·Captain: iris

Approximate Submodularity in Network Design Problems: Every Greedy-Type Heuristic of Algorithm 1 Is a (1 − (1 − 2/K)^K)/2 ≥ (1 − e^{−2})/2 Approximation for Flexibility DesignResearch Paper

Process flexibility lets a plant, warehouse or server pool serve more than one product or customer class. A firm that cannot predict which products will be in demand chooses, before demand and capacity are realized, which supply–demand pairs to connect; after the uncertainty resolves it routes capacity to demand along the installed links. Since Jordan and…

24 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance VIII: The Binomial Mean-Risk Problem with Average-Value-at-Risk Has an Explicit Value and a Stationary Optimal PolicyTextbook

Markowitz's mean-variance criterion measures the risk of a portfolio by the variance of its terminal wealth. The variance penalizes gains and losses alike, which is one of its drawbacks as a measure of risk. The axiomatic theory of coherent risk measures (Artzner, Delbaen, Eber and Heath, 1999) replaced it in much of risk management by quantities that look…

13 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOptimizationProbability·Captain: iris

Markov Decision Processes with Applications to Finance XI: Contracting Models Satisfy Value Iteration, Have a Unique Fixed Point and an Optimal Stationary PolicyTextbook

Infinite-horizon Markov Decision Processes with discounted rewards are the standard model for sequential decisions under uncertainty in operations research, economics and finance: inventory and cash management, consumption and investment, dividend payout, replacement and maintenance. Whether the problem has a usable solution depends on two questions. Is the…

12 thms4 active usersReviewed
🏆Completed
Analysis·Captain: iris

Processing Networks XIX: Increment-Dominated Monotone Paths Have Uniformly-on-Compacts Convergent SubsequencesTextbook

The stability theory of processing networks developed in Dai and Harrison's Processing Networks: Fluid Models and Stability (Cambridge University Press, 2020; pre-publication draft of 2020-4-2 at spnbook.org) rests on fluid limits: the queue lengths, cumulative allocations and other path-valued quantities of a stochastic network are scaled down in space and…

9 thms4 active usersReviewed
🏆Completed
OptimizationRevenue Management and Pricing·Captain: iris

Technical Note—Optimizing Risk-Balancing Return Under Discrete Choice Models: Under Symmetric MNL Demand the Optimal Markup Is Uniform and Falls with Risk Aversion, Reaching Zero Past a ThresholdResearch Paper

Pricing under discrete choice models is a core tool of revenue management: a firm sets prices for a line of substitute products, and customers choose one product or nothing according to a probabilistic choice rule. Almost all of this literature assumes a risk-neutral firm that maximizes expected profit. Under the multinomial logit (MNL) model with a common…

13 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingProbabilityStochastic Systems·Captain: iris

Cloud Cost Optimization: Model, Bounds, and Asymptotics: The Newsvendor Policy π* Has Optimality Gap at Most √θ Times the Bound (14), So It Is Asymptotically Optimal as Demand Scales by θResearch Paper

Cloud providers sell computing capacity in two ways: reserved resources, paid for every period whether used or not, and on-demand resources, rented one period at a time at a higher price. A firm that runs a stream of computing jobs with deadlines must decide how much capacity to reserve once, how much to rent each period, and which job runs on which…

48 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomics·Captain: iris

Negotiations in Competing Supply Chains: The Kalai-Smorodinsky Bargaining Solution: Simultaneous KS Wholesale Prices Equal the Nash Bargaining Prices at Retailer Power 0.6Research Paper

Wholesale prices between a supplier and a retailer are usually negotiated, not posted. Models of such negotiations almost always use the Nash bargaining solution (Nash, 1950), often in the generalized form with a bargaining power θ\thetaθ (Binmore, Rubinstein, Wolinsky, 1986). The Nash solution satisfies independence of irrelevant alternatives, which is the…

13 thms4 active usersReviewed
🏆Completed
Graph TheoryOptimization·Captain: iris

Convexification of Bilinear Terms over Network Polytopes: For m=1m = 1m=1, Every Tree Meeting Exactly One Endpoint of Arc lll Gives an EC&R Assignment of Class l±l^\pml± for Every Partition of Its NodesResearch Paper

Products yjxiy_jx_iyj​xi​ of a flow variable xix_ixi​ and a second decision variable yjy_jyj​ appear whenever a flow decision interacts with a pricing, design or selection decision: pooling and blending problems, network interdiction, transportation with fixed charges, and bilevel network models. Global solvers handle such terms by convexification: they replace the nonconvex…

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: iris

Dynamic Data-Driven Estimation of Non-Parametric Choice Models: With Primal-Oracle Steps, the Weighted Average Has Primal Optimality Gap at Most the Dual Regret Plus the Two Data-Error TermsResearch Paper

A non-parametric choice model describes customers by a probability distribution over rankings of nnn products: a customer offered a subset of products buys the one ranked highest among them. Revenue management and assortment planning use such models because they impose no functional form on substitution behaviour (Farias, Jagabathula and Shah, 2013; van Ryzin…

16 thms4 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: iris

Learning Optimal Forecast Aggregation in Partial Evidence Environments: A Prior-Aware Aggregator Learns the Bayes-Optimal Forecast with O~(nσ−1T)\tilde O(n\sigma^{-1}\sqrt{T})O~(nσ−1T​) Regret in a Dynamic EnvironmentResearch Paper

Weather services, medical teams and forecasting platforms routinely receive several probability forecasts for the same binary event and must combine them into one. When the forecasters are Bayesian and their information overlaps, simple rules such as averaging are not optimal: two experts who saw the same piece of evidence should not count it twice, while…

27 thms4 active usersReviewed
🏆Completed
Probability·Captain: iris

Taming the Long Tail: The Gambler's Fallacy in Intermittent Demand Management: the finite-horizon relative bias of the arrival-after-arrival estimate is strictly decreasing in ppp and in nnnResearch Paper

Spare parts, slow-moving retail items and humanitarian relief stock share a demand pattern: most periods see no demand, and a demand arrives only now and then. Planners of such long-tail or intermittent-demand items estimate the inter-arrival distribution from a finite observed history and feed it into an inventory policy. Bi, He and Teo (MSOM 2023) observe…

7 thms4 active usersReviewed
🏆Completed
OptimizationProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation IX: Jensen and generalized Edmundson–Madansky bounds sharpen on every partition of the support boxTextbook

In a two-stage stochastic linear program the objective contains the expected recourse Q(x)=Eξ[Q(x;T(ξ),h(ξ))]\mathcal Q(x)=\mathbb E_\xi[Q(x;T(\xi),h(\xi))]Q(x)=Eξ​[Q(x;T(ξ),h(ξ))], the expectation of a second-stage LP value over a random vector ξ∈Rr\xi\in\mathbb R^rξ∈Rr. For a continuous distribution this is an rrr-dimensional integral of a function that is itself defined by an optimization problem, and it…

25 thms4 active usersReviewed
🏆Completed
Graph TheoryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) III: Hoffman's Circulation Theorem with Infinite Bounds and Its Integral FormTextbook

Many combinatorial problems reduce to one question: can a prescribed amount of material be routed through a network without breaking any arc limit? Transportation problems, assignment and scheduling constraints, and the feasibility phase of minimum-cost flow all take this form. Hoffman's circulation theorem (Hoffman, 1960) answers it with a certificate: if…

23 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: iris

When Nash Meets Stackelberg: The Enumeration Algorithm Returns a Mixed Nash Equilibrium or Correctly Certifies That None ExistsResearch Paper

Many markets are organised as competition among firms that each anticipate the reaction of a group of followers. Electricity producers decide capacities while the system operator and consumers clear the market; carriers set prices while shippers choose routes. Operations research models these settings as equilibrium problems with equilibrium constraints…

23 thms4 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: iris

Investment Efforts Under Complementary Sourcing: The Role of Market Risk and Endogenous Pricing: market risk reverses the first-mover disadvantage when rµ ≥ 3ϵ0 + σ and σ/ϵ0 ≤ 3 − 2√2Research Paper

In complementary sourcing, a product's value depends on the efforts of both a supplier and a manufacturer, and each firm's effort raises the marginal value of the other's. Chip lithography is a standard example: an equipment maker and a chip maker each invest heavily, and neither investment pays without the other. When firms invest in sequence, the…

30 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear OptimizationOptimization·Captain: iris

Zero-Sum Games and Linear Programming Duality: Every Max-Min Strategy of Dantzig's Game with One Extra Row Yields Optimal LP Solutions or Certifies That No Optimal Solution ExistsResearch Paper

Linear programming duality and the minimax theorem for zero-sum games are two faces of the same convexity fact. The classical direction, from LP duality to the minimax theorem, is textbook material: the optimal strategies of a matrix game are the optimal solutions of a pair of dual LPs. The converse direction, solving an LP by solving a game, goes back to Da…

23 thms4 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: Shuze Chen

Online Matching and Ad Allocation: MSVV attains the optimal small-bids competitive ratioResearch Paper

An advertising platform must decide which advertiser receives each arriving opportunity before it knows what will arrive later. A bidder offering a high payment now may also be the only bidder interested in a later request. Spending that bidder’s budget immediately can therefore reduce the total money collected over the day. This tension is the Adwords…

16 thms4 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: Shuze Chen

College Admissions and the Stability of Marriage: Applicant optimality of deferred acceptanceResearch Paper

College admissions involves decisions on both sides of a capacity-constrained market. An applicant may prefer one college while that college prefers another applicant. An offer can be declined, and a waiting-list place can become available after another offer has already been accepted. Gale and Shapley formulate an assignment problem in which the inputs are…

5 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: Shuze Chen

Robust Assortment Optimization Under the Markov Chain Choice Model: Min-max duality and optimal robust assortmentsResearch Paper

A retailer chooses which products to offer before learning exactly how customers will substitute between them. A product that looks attractive under estimated demand can perform poorly when those estimates are wrong. Robust assortment optimization evaluates each offer set by its worst expected revenue over a specified set of possible customer models. The…

14 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: Shuze Chen

Minimum Label s-t Cut has Large Integrality Gaps: Nearly cube-root integrality gap for the strengthened relaxationResearch Paper

A network failure can remove several connections at once. When the connections share a physical resource, paying for or disabling that resource acts on an entire class of edges. The minimum label s-t cut problem captures this distinction: edges carry labels, and the cost of removing a label is paid once, regardless of how many edges have that label. Zhang…

14 thms4 active usersReviewed
PreviousPage 11 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