A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
Smart Policies for Multisource Inventory Systems and General Tandem Queues with Order Tracking and Expediting: State Space and Product-Form Stationary Distribution under Policy-MResearch Paper
An inventory system can replenish demand from several stages of a supply process. When an order is placed, the manager chooses where it enters; when work finishes at one stage, the manager may send it past intermediate stages to speed delivery. These choices change the future congestion of every stage. A stationary occupancy distribution is needed to…
Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency: The Multiplicative Weight Algorithm Nearly Matches the Offline Dynamic Optimum's Work While Approximately Satisfying Every SLAResearch Paper
Cloud platforms divide a shared physical resource, such as a pool of processors, among many users at once. Each user is promised a service level agreement (SLA): a fraction β(i) of the resource that it should effectively receive whenever it has work to do. The operator wants two things that pull against each other: to keep the resource busy (total work…
Multivariate Monotone Inclusions in Saddle Form: The Asynchronous Block-Iterative Saddle Splitting Algorithm Converges Weakly to a Primal-Dual Kuhn–Tucker PointResearch Paper
Many problems in convex optimization, variational inequalities, game theory and signal processing are systems of monotone inclusions coupled by linear operators: several unknowns xi in different Hilbert spaces, each subject to its own maximally monotone, cocoercive and Lipschitzian operators, and tied together through linear maps Lki and composite…
Large Deviations for the Single-Server Queue and the Reneging Paradox: The Long-Time Decay Rate of Atypical Reneging Is an Explicit C(γ) Independent of the Reneging RateResearch Paper
Customer abandonment, or reneging, is a basic feature of service systems: call centres, emergency departments and online platforms all lose customers who give up waiting. The number of reneging customers is a natural performance measure, and in many-server and single-server models alike it is the quantity managers monitor and are penalised for. Typical…
Waiting for the Payday? The Market for Startups and the Timing of Entrepreneurial Exit: Low-Capability Startups Commit Early, High-Capability Startups Commit Late, Intermediate Ones Stay FlexibleResearch Paper
Most technology startups that exit successfully are acquired by incumbents rather than taken public. A founder therefore faces a timing question: sell early, while the company is still an invention that only a few incumbents can evaluate, or wait until the invention has been developed into an innovation that every potential buyer can value, at the risk of…
Inventory Integration with Rational Consumers: Unique Correlation and Variability Thresholds Below Which the Behavioral Value of Integration Is PositiveResearch Paper
Inventory integration (or pooling) serves several markets from one stock instead of one stock per market. Its classical value is statistical: when demands are not perfectly correlated, the pooled demand is relatively less variable, so less safety stock is needed for the same service level. Eppen (Management Science, 1979) quantified this for normal demand,…
Online Learning over a Finite Action Set with Limited Switching: An Algorithm for Prediction From Experts Whose Regret and Number of Switches Are Both O(√(T log n log(1/δ))) with Probability 1 − δResearch Paper
In prediction from experts (PFE), an online learner chooses one of n actions in each of T rounds, and an adversary assigns each action a loss in [0,1]. Performance is measured by regret, the learner's total loss minus that of the best single action in hindsight. In many applications changing the action is itself costly: re-routing traffic, re-balancing a…
Time-Varying Semidefinite Programs: Under Strict Feasibility, Feasible Polynomial Solutions Have Objective Values Converging to the TV-SDP Optimal ValueResearch Paper
Many planning problems ask for a decision that varies over a time horizon and must satisfy a constraint at every instant, possibly with cumulative effects of past decisions. The applications in the source paper are a maximum-flow problem with time-varying pipeline capacities, a wireless coverage problem for a moving target region, and the approximation of…
A Model of Queue-Scalping: A Single Queue-Scalper Enters the Queue if and only if the Demand Volume Is IntermediateResearch Paper
A customer who is short of time may pay for a better place in a service queue. Unlike resale of a fixed ticket, this transaction changes the waits faced by later customers, and those customers' choices then change the value of the position being sold. Yang, Wang, and Cui study this feedback in an unobservable queue with a firm that repeatedly sells its…
Artificial Shortage in Agricultural Supply Chains: Cash Subsidy Leaves Artificial Shortage Unchanged on a Small Budget, Mitigates It on a Moderate One, and Aggravates It on a Large OneResearch Paper
Prices of staple vegetables in India, onions above all, rise sharply at irregular intervals. When they do, governments respond with cash transfers, subsidized sales and import programmes. A recurring explanation for these price spikes is artificial shortage: traders who control a large share of the stock withhold supply early in a season, and consumers who…
The Value of Price Discrimination in Large Random Networks: The Expected Fractional Regret of Uniform Pricing Vanishes in Erdős–Rényi Networks of Any DensityResearch Paper
A seller whose customers influence one another faces a choice between two pricing policies. It can collect information about the social network and charge each customer a personalised price that reflects their position in it, or it can ignore the network and charge everyone one uniform price. Personalised pricing is never worse for the seller, but…
Intertemporal Segmentation via Flexible-Duration Group Buying: Above an Explicit Batch-Size Threshold, the Optimal Uniform-Price Campaign Admits High-End Customers First and Both Segments LaterResearch Paper
Group buying sells a product at a discount once enough customers have committed to it. Groupon's "a deal a day" campaigns ran on a fixed deadline. Group buying on Pinduoduo has no preset deadline: a customer pledges, then waits until the group is complete. Most of the operations literature studies the first, fixed-duration form, in which a campaign ends at…
Supplier Encroachment in a Non-Exclusive Reselling Channel: The Encroaching Supplier May Sell Only Directly at a Positive Direct Cost, or Through Both Channels at a Negative OneResearch Paper
Manufacturers that sell through retailers increasingly also sell directly to consumers, through their own web stores or outlets. The operations literature calls this supplier encroachment. The classical analysis (Arya, Mittendorf and Sappington, 2007) assumes an exclusive reseller: the reseller carries only the encroaching supplier's product. In that…
Second-Order Optimality Conditions for Nonconvex Set-Constrained Optimization Problems: A Directional Second-Order Necessary Condition via the Lower Generalized Support FunctionResearch Paper
Optimization problems often require a smooth objective to be minimized subject to membership in a set. When that set is convex, established second-order conditions describe how curvature of the objective and constraints limits a local solution. Complementarity constraints and related models lead to nonconvex constraint sets. The tangent sets needed for a…
Fair Allocation of Indivisible Goods: Improvement and Generalization: Every Instance with Additive Valuations Admits a 3/4-MMS AllocationResearch Paper
Dividing a set of indivisible goods among agents with different preferences is a basic problem of fair division, with applications to inheritance, course allocation and the division of shared assets. With indivisible goods, envy-freeness and proportionality cannot always be achieved: a single good and two agents already rule both out. Budish (The…
Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution: Without Samples, No Stopping Rule Guarantees More Than 1/e of the Expected MaximumResearch Paper
A prophet inequality compares the value obtained by an online decision maker with the largest value in a sequence that could be chosen by someone who sees the entire sequence. The online decision maker observes values one at a time and must decide whether to accept the current value before seeing future values. When the common distribution of the values is…
Correlated Equilibria and Mean Field Games: A Simple Model: Every Limit Point of Symmetric ε_N-Correlated Equilibria in Restricted Strategies Is a Correlated Mean Field Game SolutionResearch Paper
A correlated equilibrium (Aumann, 1974) is a profile of strategies chosen by a mediator: the mediator draws a joint recommendation from a known distribution, tells each player only their own component, and no player can lower their expected cost by systematically deviating from what they are told. Correlated equilibria contain the Nash equilibria, are…
Design and Pricing of Discretionary Service Lines: Under SPT Without Customer Heterogeneity, the Optimal Service Line Has Variety, No Cutoff and a Concave Price Falling at the TopResearch Paper
Many services are discretionary: the provider chooses how long to spend with a customer, and a longer service is worth more to the customer. Medical consultations, legal and tax advice, repair and diagnostic work, and personal services such as hair styling all have this shape. A firm offering such services designs a service line, a menu of service durations…
Promotion Optimization for Multiple Items in Supermarkets: Under Additively Separable Cross-Item Effects, All Higher-Order Promotion Contributions Vanish and App(2) = App(N)Research Paper
Supermarkets run temporary price promotions on a large share of their assortment, and the choice of which item to discount, by how much and in which week is a recurring planning decision for category managers. Promotions on one item change the sales of the others: a discount on one brand of coffee draws customers away from a competing brand (substitution),…
The Discrete Moment Problem with Nonconvex Shape Constraints: Optimal Extreme Point Solutions of the Log-Concave Discrete Moment Problem Are Piecewise Geometric with at Most m PiecesResearch Paper
A discrete moment problem asks for the largest expected payoff compatible with prescribed moments of an unknown probability distribution. A decision maker may know the first few moments of demand or loss while the full distribution remains uncertain. The optimization then asks which compatible distribution makes a chosen payoff largest. Chen, He, Jiang,…
The Value and Cost of Crop Minimum Support Price: Farmer and Consumer Welfare and Implementation Cost: Net Benefit and Net Social Value of a Credit-Based MSP under Market UncertaintyResearch Paper
A minimum support price (MSP) guarantees farmers a unit sale price at least as high as an announced floor. It can protect farmers when the market price is low, but the same guarantee can require a government payment and can change how much crop is produced. Policy evaluation therefore needs to account for farmers, consumers, and public expenditure together.…
A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation: Projected TD(0) Under Markov Chain Sampling Converges at Mixing-Time-Scaled RatesResearch Paper
Temporal-difference (TD) learning is the basic algorithm of reinforcement learning for estimating the value function of a fixed policy from a single stream of experience. With a linear function approximationVθ(s)=ϕ(s)⊤θ, TD(0) is the evaluation step inside many policy-iteration and actor–critic methods, and its behaviour governs how much…
Net-Metered Distributed Renewable Energy: A Peril for Utilities?: DRE Raises a Utility's Expected Profit if and only if Its Existing Resources Are Small and the Wholesale Price Is Sensitive EnoughResearch Paper
Electricity end-users increasingly generate their own power with rooftop solar panels and small wind turbines. This distributed renewable energy (DRE) is usually sold under net metering: a customer who produces less than it consumes buys the shortfall from its utility at the retail price, and a customer who produces more sells the surplus back to the…
The Role of Participation in Innovation Contests: Multiple Rewards Are Optimal Exactly When Entry Is Costly, the Budget Is Large and a Failed Contest Is CostlyResearch Paper
An innovation contest asks people outside a firm to submit solutions and promises payments according to the rank of their submissions. The firm would like a strong best submission, but a potential solver must decide whether entering is worth a fixed cost before knowing who else will enter. Paying only the winner can encourage effort while leaving the…
Strong Algorithms for the Ordinal Matroid Secretary Problem: Every Algorithm with Forbidden Sets of Size k Is α(k) Probability-CompetitiveResearch Paper
The secretary problem asks an online decision maker to pick the best of n candidates who arrive in uniformly random order, deciding irrevocably on each one at arrival. Its matroid generalization, the matroid secretary problem (MSP) of Babaioff, Immorlica and Kleinberg (SODA 2007), asks the algorithm to select an independent set of a matroid whose elements…