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.
On-Demand Delivery from Stores: Dynamic Dispatching and Routing with Random Demand I: The Approximation APT Bounds the Expected Cost-to-Go from Below and Above and Is Exact in the Last PeriodResearch Paper
Retailers and restaurants increasingly deliver orders from their own stores within an hour or less. Orders arrive throughout the day, a fixed pool of drivers is based at the store, and in each dispatch wave the operator must decide how many drivers to send out now and along which routes. Sending many drivers now gives short delivery times for the current…
Right to Repair: Pricing, Welfare, and Environmental Implications: The Manufacturer's Optimal New-Product and Repair Prices and the Resulting No-, Partial- or Full-Repair Equilibrium (Table 1)Research Paper
Repair access changes more than the cost of fixing a broken product. It also changes how many used products reach a resale market, what those products sell for, and whether a manufacturer prefers to sell another new unit or earn a repair margin. Jin, Yang, and Zhu study these connected pricing decisions in a two-period durable-goods model in Right to…
Courier Dispatch in On-Demand Delivery I: With Exogenous Demand, Dedicated Delivery Has the Shorter Wait Exactly Below One Threshold in Demand Rate and in Service RadiusResearch Paper
On-demand delivery platforms for meals and groceries promise delivery within minutes, and the main operational lever they control is how a courier is dispatched. A courier can carry each order as soon as it is ready (dedicated delivery), or wait until two orders are available and deliver them in one trip (batch delivery). Batching saves travel per order but…
Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems 1: Under FIFO Issuance the Heuristic Base-Stock Policy's Optimality Gap Decays Exponentially in the Product LifetimeResearch Paper
Blood platelets, fresh produce, dairy and many pharmaceuticals have a fixed shelf life: a unit that has not been used within m periods of its arrival must be discarded. Managing such stock is a classical problem of inventory theory, going back to Nahmias (1975), and it remains of practical interest for hospital blood banks and grocery retail. The difficulty…
The Conceptual Flaws of Decentralized Automated Market Making: Constant Product Pricing Admits Profitable Front-Running and Multi-Venue ArbitrageResearch Paper
Decentralized exchanges on public blockchains do not match buyers with sellers through an order book. Most of them trade against a liquidity pool: a smart contract that holds reserves of two tokens and quotes a price by a fixed formula. The most widely used formula is the constant product rule of Uniswap (Adams, Zinsmeister and Robinson, 2020), under which…
Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low IV: ℓ1-Regularized Best Subset Selection Satisfies Slow-Rate and Fast-Rate Oracle InequalitiesResearch Paper
Best subset selection fits a linear predictor using at most k of p available columns. Its explicit limit on the number of selected variables makes the model easy to interpret, but the search can still fit noise: among many subsets of the same size, one can align unusually well with a noisy response. Mazumder, Radchenko and Dedieu study this effect in Subset…
Supply Risk Mitigation in a Decentralized Supply Chain: Pricing Postponement or Payment Postponement? III: When Payment Postponement Helps or Hurts the Retailer, the Supplier and the ConsumersResearch Paper
A retailer can pay a supplier when it places an order or after the supplier delivers it. When production yield is uncertain, the choice changes who bears the cost of missing units. It can also change the supplier's production decision and, through the amount available for sale, the surplus received by consumers. Geng, Guo, Xiao and Yang study these effects…
Supply Risk Mitigation in a Decentralized Supply Chain: Pricing Postponement or Payment Postponement? II: Under Reliable Yield the Postponements Are Complements Only at Intermediate CostResearch Paper
A retailer that buys from a supplier with unreliable production has two contractual levers against supply risk, and both postpone a decision until after the yield is known. Payment postponement means paying only for the units actually delivered (pay-by-delivery) instead of the units ordered (pay-by-order). This moves the yield risk upstream. Pricing…
Human and Machine: The Impact of Machine Input on Decision-Making Under Cognitive Limitations II: Machine Input Never Lowers the Decision-Maker's Accuracy or Expected ValueResearch Paper
Machine-learning systems are increasingly placed beside human experts — physicians reading scans, loan officers screening applications, judges assessing risk — rather than replacing them. The machine processes the structured data it can see; the human also has access to information the algorithm cannot observe, but her attention is limited. Whether such a…
Supply Risk Mitigation in a Decentralized Supply Chain: Pricing Postponement or Payment Postponement? I: As Cost Rises the Retailer Prefers Payment, Then Pricing, Then Both, Then Pricing PostponementResearch Paper
When a supplier's production is subject to random yield, only part of a planned production run turns into usable output. A retailer sourcing from such a supplier bears the resulting shortage risk unless the contract or the selling strategy moves it elsewhere. Random yield is a classical topic in production planning (Yano and Lee, 1995), and postponing a…
Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low III: ℓ2-Regularized Best Subset Selection Satisfies Slow-Rate and Fast-Rate Oracle InequalitiesResearch Paper
Best subset selection fits a linear model using at most k of p available predictors, choosing the k that minimize the residual sum of squares. Mixed-integer optimization made it computable at moderate scale (Bertsimas, King & Mazumder, 2016), which reopened the statistical question of when it should be used. Empirical comparisons (Hastie, Tibshirani &…
Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low I: The Discrete First-Order Algorithm Is a Descent Method Whose Successive Steps Shrink at Rate O(1/M)Research Paper
Best subset selection fits a linear model y≈Xβ using at most k of the p available features: it minimizes the residual sum of squares subject to the sparsity constraint∥β∥0≤k, where ∥β∥0 counts the nonzero coordinates of β. Mazumder, Radchenko and Dedieu (arXiv:1708.03288v4; Operations Research, 2023) show that best subsets…
Human and Machine: The Impact of Machine Input on Decision-Making Under Cognitive Limitations I: The Rationally Inattentive Decision-Maker's Optimal Choice Probability in Closed FormResearch Paper
A person using a machine's advice may decide more accurately, but attention is costly. Before asking what a machine changes, the baseline decision has to be understood: how often would the person choose the action associated with a good state without machine input? Boyacı, Canyakmaz, and de Véricourt study this question in a model of a decision maker who…
A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games 3: The Price of Anarchy Is Locally Lipschitz at Games with Constant Costs or Strictly Increasing C¹ CostsResearch Paper
The price of anarchy (PoA) of a nonatomic congestion game is the ratio of the total cost of a Wardrop equilibrium to the minimum total cost. Worst-case bounds on it over whole classes of cost functions are classical (Roughgarden and Tardos, 2002; Correa, Schulz and Stier-Moses, 2004). In practice the demands and cost functions of a traffic model are…
A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games 2: The Social Optimum Cost, the Wardrop Equilibrium Cost and the Price of Anarchy Are Continuous on the Game SpaceResearch Paper
Traffic users choose routes for themselves, while a planner may choose routes that minimize everyone's combined travel cost. The price of anarchy measures the cost of the users' equilibrium relative to the planner's optimum. Travel demand and arc latency functions are estimated from data and change over time, so a ratio that changes abruptly under a small…
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness 5: For Two Agents, Every Equilibrium of an Always-EFX Mechanism Is α-MMS for Some α > 2/3Research Paper
Dividing indivisible goods fairly among agents is a basic problem of fair division. Most of the
literature assumes that the agents' valuations are known to the algorithm. In practice the
algorithm only sees what the agents report, and an agent may misreport to get a better bundle.
For allocation without money, truthful mechanisms are very restricted: for…
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness 4: For Two Agents and Four Goods, Every Equilibrium of an Always-EFX Mechanism Is MMSResearch Paper
Dividing indivisible goods fairly is a central problem of computational social choice. With additive valuations, the fairness notions of interest are relaxations of envy-freeness, since exact envy-freeness is often impossible with indivisible items. The strongest relaxation in common use is envy-freeness up to any good (EFX) (Caragiannis et al., 2019); a…
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness 2: Round-Robin Has a Pure Nash Equilibrium in Every Instance with Additive ValuationsResearch Paper
Fair division of indivisible goods asks how to split a set of items among agents with different values so that nobody has strong grounds to complain. Algorithms with fairness guarantees, such as Round-Robin, which always produces an allocation that is envy-free up to one good (EF1) when agents report their true additive valuations (Caragiannis et al., 2019),…
Linear Programming and Community Detection 5: The LP Relaxation Recovers the Planted Bisection w.h.p. in the Very Dense SBM When p − q > 1/2Research Paper
The stochastic block model (SBM), introduced by Holland, Laskey and Leinhardt (1983), is the standard random model for networks with community structure, and the basic benchmark for community-detection algorithms (Abbe 2018). In its two-community form the nodes are split into two equal halves, edges inside a half appear with probability p, and edges across…
Load Balancing Under Strict Compatibility Constraints 3: Inhomogeneous Random Graphs with Edge Probabilities Satisfying (3.5) Are Almost Surely Proportionally Sparse and SubcriticalResearch Paper
Large-scale computing systems route incoming tasks to servers through dispatchers, one per task type. A task can only run on a server that holds the data or software it needs, so the set of admissible pairs forms a bipartite compatibility graph between task types and servers. Full flexibility (every server can serve every type) gives the best load balancing…
Selection and Ordering Policies for Hiring Pipelines via Linear Programming 4: For Every τ ∈ (0, 1) Some τ-Bounded Instance Gives No Value-Ordered Policy More Than (β^τ_k + ε) Times the OptimumResearch Paper
A firm with k open positions often cannot interview and offer sequentially: hiring seasons are short, and offers go out in one batch. Some recipients decline, so the firm overbooks, sending more offers than it has positions, and pays for every hire beyond capacity. The same trade-off appears in airline and hotel overbooking and in university admissions.…
Lightning Network Economics: Channels III: The Minimal Cost of a Symmetric Bidirectional Channel Is 3(2Bλ/r)^{1/3} − B/6 + O(r^{1/3}) as r → 0Research Paper
Payment channels let two parties make repeated transfers while using an on-chain transaction only when a channel needs resetting. They require funds to be committed in advance. The economic choice is therefore between the transaction fees saved by using a channel and the opportunity cost of funds tied up in it. Guasoni, Huberman, and Shikhelman give a…
Climate Impact Investing 2: With Poisson Climate Uncertainty λ, If the Green Portfolio Is Green Then y*_λ Rises to 1 in λ, So Equilibrium Emissions Rise as Uncertainty GrowsResearch Paper
Climate impact investing refers to investors who tilt their portfolios away from companies with large greenhouse-gas emissions. Its stated aim goes beyond aligning portfolios with values: by raising the cost of capital of polluting companies, it is meant to change what those companies do. De Angelis, Tankov and Zerbib (SSRN 3562534, published in Management…
Integer Factorization: Why Two-Item Joint Replenishment Is Hard 2: For Odd Composite M, Every Optimal Plan of an Explicit Two-Item Periodic JRP Instance Has q₂ = M and 1 < gcd(q₁, M) < MResearch Paper
The joint replenishment problem (JRP) is a basic model of inventory coordination: several items are ordered from one supplier, each item pays its own ordering and holding costs, and an additional item-independent joint ordering cost rewards ordering the items at common times. Two accounting conventions are studied. In the periodic JRP (also called the…
Linear Programming and Community Detection 3: The Metric LP Relaxation Recovers the Planted Bisection When d_in − d_out ≥ n/4 Under Regular SandwichingResearch Paper
The minimum bisection problem asks, for a graph G=(V,E) on an even number n of vertices, for a split of V into two halves of size n/2 that cuts as few edges as possible. It is NP-hard, and it is also the maximum a posteriori estimator for the two-community stochastic block model, the standard random model of networks with community structure. A tractable…