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 TheoryCombinatoricsOptimization+1·Captain: iris

Tight Approximation for Unconstrained XOS Maximization: Algorithm 4 Finds a (k−1)(k-1)(k−1)-Maximizer of Every kkk-XOS Function in O(k2n)O(k^2 n)O(k2n) Time, Exactly When k=2k=2k=2Research Paper

Maximizing a set function is a basic task in combinatorial optimization and algorithmic game theory. Computing an agent's demand under prices ppp amounts to maximizing v(X)−∑x∈Xpxv(X)-\sum_{x\in X}p_xv(X)−∑x∈X​px​, which need not be monotone even when the valuation vvv is. XOS functions generalize submodular functions, and they are studied in combinatorial auctions, where they are…

22 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: iris

Online Estimation and Optimization of Utility-Based Shortfall Risk: The Projected Stochastic Approximation Estimator Has Mean-Squared Error O(1/n) with an Explicit ConstantResearch Paper

A risk measure assigns to a random financial position XXX the amount of cash that has to be added to it to make it acceptable. Value-at-Risk ignores the size of losses beyond a quantile, and Conditional Value-at-Risk weighs all losses beyond a threshold equally. Utility-based shortfall risk (UBSR), introduced by Föllmer and Schied (Convex measures of risk and…

19 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: iris

An Accelerated Newton–Dinkelbach Method and Its Application to Two Variables per Inequality Systems: The Look-Ahead Newton–Dinkelbach Method Halves the Bregman Divergence Every Two IterationsResearch Paper

Many optimization problems ask for the largest root of a concave function of one real variable that can only be accessed through oracles. In linear fractional combinatorial optimization, minimizing a ratio c⊤x/d⊤xc^\top x/d^\top xc⊤x/d⊤x over x∈D⊆{0,1}mx\in D\subseteq\{0,1\}^mx∈D⊆{0,1}m reduces to finding the largest root of the concave, piecewise linear function …

14 thms2 active usersReviewed
🏆Completed
Optimization·Captain: iris

Coordination of Multiechelon Supply Chains Using the Guaranteed Service Framework: The Centralized Safety-Stock Optimum Equals the Best Split over the Service Time Between the Two PlayersResearch Paper

Multi-echelon supply chains are rarely run by a single firm. A manufacturer of a finished product buys a component from a supplier, and each firm places its own safety stock. The guaranteed-service model of safety-stock placement, going back to Simpson (1958) and developed by Graves and Willems (2000), lets a planner choose, for each stage, the service time…

5 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: iris

A Unifying Framework for Submodular Mean Field Games: Abstract Submodular MFGs Have Least and Greatest Equilibria, Reached by Iterating the Best-Response MapResearch Paper

Mean field games (MFGs), introduced by Lasry and Lions and by Huang, Malhamé and Caines in 2006–2007, describe the limit of symmetric stochastic games with many small players. A representative player optimizes against the distribution of the population, and an equilibrium is a distribution that reproduces itself when every player best responds to it.…

17 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism Design·Captain: iris

Best of Both Worlds Ad Contracts: Guaranteed Allocation and Price with Programmatic Efficiency: The Market-Maker Contract Strictly Raises Revenue and Welfare at Unchanged Utilities and EfficiencyResearch Paper

Display advertising is sold in two ways. Reservation contracts guarantee an advertiser a volume of impressions at a fixed price, negotiated in advance. Programmatic auctions (ad exchanges) sell impressions one at a time, efficiently, but at a price and with an allocation that the advertiser does not know in advance. Advertisers with fixed campaign budgets…

18 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation VII: expectation, worst case and CVaR are coherent risk measuresTextbook

A stochastic linear program evaluates a decision x∈Rnx\in\mathbb R^nx∈Rn through a random outcome, typically the linear-affine random variable ζ(x,η,ξ)=η⊤x−ξ\zeta(x,\eta,\xi)=\eta^\top x-\xiζ(x,η,ξ)=η⊤x−ξ, where η\etaη is a random vector and ξ\xiξ a random variable. Chapter 2 of Kall and Mayer's Stochastic Linear Programming (Springer, 2005) builds its single-stage models in two steps: a…

34 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation II: joint probability constraints are closed, and convex at high levels under finite discrete distributionsTextbook

A linear program whose technology matrix and right-hand side are random cannot simply require its constraints to hold: for most realizations of the data, no decision satisfies them all. A joint probability constraint (also called a chance constraint) asks instead that the random system T(ξ)x≥h(ξ)T(\xi)x\ge h(\xi)T(ξ)x≥h(ξ) hold with probability at least a prescribed level …

16 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) II: When Least-Cost Dipaths Exist, the Shortest Dipath Cost Equals the Maximum Feasible PotentialTextbook

The shortest path problem asks, in a network whose links carry costs, for a cheapest directed route from a fixed origin to every other point. It is the basic subroutine of network optimization: minimum-cost flow algorithms, matching algorithms and many dynamic programs call it repeatedly, and arc costs that are negative arise naturally, for instance as −log⁡-\log−log…

22 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) V: A Minimum-Cost Flow Problem with Integral Demands and Capacities Has an Integral Optimal SolutionTextbook

The minimum-cost flow problem is the common roof over shortest paths, maximum flows, transportation and assignment problems, and transshipment. It asks for the cheapest way to move a commodity through a directed network so that every node receives its prescribed net amount and no arc carries more than its capacity. Its central structural fact is…

21 thms2 active usersReviewed
🏆Completed
Optimization·Captain: Shuze Chen

Online Assortment Optimization with Reusable Resources: The myopic policy earns at least half the clairvoyant optimal revenueResearch Paper

A server, storage unit or production machine can serve a customer and then become available again. Offering it now earns revenue but may prevent serving a later customer while it remains occupied. Online assortment optimization with reusable resources studies these decisions when each customer chooses among the products offered and an outside option. The…

11 thms2 active usersReviewed
🏆Completed
Economics·Captain: iris

Pride or Guilt? Impacts of Consumers’ Socially Influenced Recycling Behaviors on Closed-Loop Supply Chains: in Ω4 pride raises optimal profit; guilt lowers it iff τ*_m < b1/b0Research Paper

Manufacturers of phones, appliances and packaging increasingly take back used products and remanufacture them, paying consumers a recycling reward (a trade-in credit or gift card). Whether a consumer returns a used product depends not only on money and effort but on social feelings: the pride of recycling when others do not, and the guilt of not recycling…

30 thms2 active usersReviewed
🏆Completed
EconomicsOptimization·Captain: iris

Implied Ambiguity: Mean-Variance Inefficiency and Pricing Errors: the smallest ambiguity aversion making a portfolio optimal is an explicit decreasing function of its normalized Sharpe ratioResearch Paper

Observed portfolios, from mutual fund holdings to market capitalization weights, are rarely mean-variance efficient: their Sharpe ratio falls short of that of the tangency portfolio. In a classical CARA–normal model this cannot happen, so the gap needs an explanation. Hara and Honda (working paper, 2018; Management Science, 2022) explain it by ambiguity…

13 thms2 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: Shuze Chen

Optimal Matchmaking Strategy in Two-Sided Marketplaces: Lower bounds on communication for stable matchmakingResearch Paper

A platform may know the services its users seek and offer while still lacking the preferences that determine whether a particular match is worthwhile. Learning those preferences requires communication. A lower bound on that communication would distinguish a limitation of one search algorithm from a limitation shared by every platform design. Peng Shi's Optim…

8 thms2 active usersReviewed
🏆Completed
EconomicsOptimizationRevenue Management and Pricing·Captain: mikeh

Optimal Feature-Based Market Segmentation and PricingResearch Paper

A seller can often predict a customer's willingness to pay from observed features, yet may be limited to a small number of prices. The decisions are then coupled: the seller must choose both the customer groups and the price assigned to each group. Grouping customers first and optimizing prices afterward does not generally solve the joint problem. Cui and…

24 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingProbability·Captain: Shuze Chen

Markov Decision Processes (Puterman) I: Backward Induction and Optimal PoliciesTextbook

Inventory replenishment, equipment replacement, and resource allocation require decisions whose consequences continue beyond the current period. A choice can earn an immediate reward and change the distribution of future opportunities. Comparing only immediate rewards therefore does not generally identify a good policy. A finite-horizon Markov decision…

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingProbability·Captain: Shuze Chen

Markov Decision Processes (Puterman) II: Markov Policies Preserve Reward CriteriaTextbook

A controller making repeated decisions can remember every state visited and every action taken. The resulting policy class is much larger than the class of rules that use only the current state and time. In applications modeled by Markov decision processes, understanding whether that extra memory changes achievable expected rewards determines which policy…

6 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomics·Captain: mikedeng1

Multiplicative Pacing Equilibria in Auction Markets: Every Pacing Game Admits a Second Price Pacing EquilibriumResearch Paper

Internet advertising markets sell impressions, clicks and conversions one auction at a time, and most advertisers attach a budget to a whole campaign. Bidding one's full value until the budget runs out is suboptimal: the buyer drops out early and misses later auctions that may offer the same value at a lower price. A widely used remedy is multiplicative…

11 thms2 active usersReviewed
🏆Completed
EconomicsProbability·Captain: mikedeng1

The Value of Personalized Pricing: A Tight Three-Regime Upper Bound on the Personalized-to-Single-Pricing Profit Ratio in Terms of Scale, Margin and Coefficient of DeviationResearch Paper

Firms increasingly observe enough about individual customers to charge them different prices, and regulators, platforms and sellers all ask the same quantitative question: how much more profit can personalization earn than a single posted price? The upper end of that comparison is idealized personalized pricing (first-degree price discrimination), where…

12 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOptimization·Captain: mikedeng1

Competition Between Two-Sided Platforms Under Demand and Supply Congestion Effects: Surge Pricing Lowers Customer and Raises Driver Utility, and Near the Base Market Size Beats Fixed Prices for BothResearch Paper

Ride-hailing platforms such as Uber and Lyft raise prices when demand spikes, a practice known as surge pricing. The practice is controversial: customers see higher fares, and it is not obvious that anyone but the platform gains. Bernstein, DeCroix and Keskin (MSOM 2020; author version SSRN 3250224) study two competing platforms whose customers dislike…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryMachine Learning·Captain: mikedeng1

Correlation Clustering: Algorithm Cautious Is a Constant-Factor Approximation for Minimizing DisagreementsResearch Paper

In many clustering tasks the data come as pairwise judgements rather than as points in a metric space: a classifier says, for each pair of documents, whether they refer to the same entity or not. Correlation clustering asks for a partition that agrees with as many of these judgements as possible, without fixing the number of clusters in advance. The problem…

12 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

Algorithms for Max-Min Share Fair Allocation of Indivisible Chores: Greedy Round-Robin Gives Every Agent at Least (2 − 1/N) Times Her Max-Min Share, and the Factor Cannot Be ImprovedResearch Paper

Many allocation problems distribute work rather than benefits: household and office tasks, teaching loads, shifts, maintenance duties, or jobs assigned to parallel machines. Each item is a chore, which every agent would rather not receive, and chores cannot be split. Under indivisibility an exactly fair split usually does not exist, so the fair-division…

11 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Sparse Solutions of a Class of Constrained Optimization Problems: For All Small p > 0, Every Lp Minimizer under an L1 Constraint Is a Sparsest Solution, and the Solution Set StabilizesResearch Paper

Many problems in signal processing, statistics and compressed sensing ask for a sparse solution of an underdetermined, possibly noisy linear system: a vector x∈Rnx\in\mathbb R^nx∈Rn with as few nonzero entries as possible such that AxAxAx is close to bbb. The direct formulation, minimizing the number of nonzeros ∥x∥0\|x\|_0∥x∥0​, is combinatorial and NP-hard in general. A…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimizationTheoretical Computer Science·Captain: mikedeng1

Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems: The Maximum Support Algorithm Is Correct and Terminates Within Condition-Measure BoundsResearch Paper

Finding a nonzero nonnegative point in a linear subspace is the feasibility core of linear optimization. For a subspace L⊆RnL \subseteq \mathbb R^nL⊆Rn with orthogonal complement L⊥L^\perpL⊥, the pair of problems

7 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Value Loss in Allocation Systems with Provider Guarantees: Under Pareto-Efficient Provider Guarantees the Relative Value Loss Is at Most max{δ, (n−1)/(n+(1−δ)(n−1))}Research Paper

Centralized platforms that assign work to independent service providers, such as ride-hailing and freelance marketplaces, sales organisations distributing leads, and firms sourcing from several suppliers, are often asked to give their providers guarantees: a minimum income, a max-min fair share of the work, or another fairness criterion. A guarantee shrinks…

11 thms2 active usersReviewed
PreviousPage 69 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