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.
Markov Entanglement: Decomposition Error via Agent-wise TV DistanceResearch Paper
Multi-agent reinforcement learning approximates a global value function by summing per-agent local value functions learned independently — a trick that works surprisingly well in practice (ride-hailing dispatch, restless bandits) but had no general theoretical justification. Chen and Peng (arXiv:2506.02385) explain why: they define a Markov entanglement meas…
Buying to Bundle: Asymptotic Optimality of Surrogate BundlingResearch Paper
A platform sourcing items from monopolistic sellers with private quality cannot tractably maximize its true profit: the bundle revenue Rev(vS) is neither monotone, submodular, supermodular, subadditive, nor superadditive. Theorem 4.6 of Buying to Bundle: Optimal Sourcing from Monopolistic Sellers shows that the simple surrogate threshold mechanism —…
Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience: Greedy with a κ-Approximate Star-Graph Black Box Is κ/2-Competitive under Adversarial ArrivalsResearch Paper
Online bipartite matching, introduced by Karp, Vazirani and Vazirani (1990), models a platform that must assign arriving customers to a known stock of items, one customer at a time and irrevocably. In e-commerce, job search and online advertising, a recommendation is only a suggestion: a customer buys an offered item with some known probability, and after…
Relaxed Indexability and Index Policy for Partially Observable Restless Bandits: Relaxed Indexability Is Equivalent to a Passive-Time Inequality, and the Approximate Whittle Index Has a Closed FormResearch Paper
A restless multi-armed bandit has N arms, each a Markov chain that keeps evolving whether or not it is used; in every slot a decision maker activates some of the arms and collects rewards from them. Channel selection in wireless networks, machine maintenance, target tracking and patient monitoring are of this form. Finding an optimal policy is PSPACE-hard…
Effects of Reactive Capacity on Product Quality and Firm Profitability in an Uncertain Market: equilibrium quality rises then falls in the supplier's reactive capacityResearch Paper
Brand-owning retailers outsource production and use pull contracts: the retailer names a wholesale price, the supplier decides how much to stock before the season, and the retailer orders only after it has seen demand, so the supplier carries the inventory risk (Cachon 2004, cited on p.13 of the source). Investment in reactive capacity (shorter set-up…
Correlated Equilibria in Large Anonymous Bayesian Games: with a convex potential, coarse correlated and correlated Wardrop equilibria are the mixtures of Wardrop equilibria, all with equal costsResearch Paper
In large populations of anonymous agents (commuters choosing routes, users choosing servers, customers choosing a bar), each individual has a negligible effect on the others, and the natural equilibrium notion is the Wardrop equilibrium (WE): only cheapest actions carry mass. A mediator such as a navigation app may instead recommend actions at random,…
Tight Approximation for Unconstrained XOS Maximization: Algorithm 4 Finds a (k−1)-Maximizer of Every k-XOS Function in O(k2n) Time, Exactly When k=2Research Paper
Maximizing a set function is a basic task in combinatorial optimization and algorithmic game theory. Computing an agent's demand under prices p amounts to maximizing v(X)−∑x∈Xpx, which need not be monotone even when the valuation v is. XOS functions generalize submodular functions, and they are studied in combinatorial auctions, where they are…
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 X 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…
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⊤x over x∈D⊆{0,1}m reduces to finding the largest root of the concave, piecewise linear function …
Auctions of Auctions: exchanges' double bid-shading lowers both publisher revenue and advertiser profit below the direct benchmarkResearch Paper
Display advertising is sold impression by impression in real-time auctions. A publisher rarely sells to advertisers directly: advertisers delegate bidding to intermediaries, ad exchanges, which collect their clients' bids in an internal auction and then bid on the winner's behalf in the publisher's header auction. Since the industry's move to first-price…
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…
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.…
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…
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∈Rn through a random outcome, typically the linear-affine random variable ζ(x,η,ξ)=η⊤x−ξ, where η is a random vector and ξ a random variable. Chapter 2 of Kall and Mayer's Stochastic Linear Programming (Springer, 2005) builds its single-stage models in two steps: a…
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(ξ) hold with probability at least a prescribed level …
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…
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…
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…
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…
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…
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…
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…
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…
Financial Derivatives VI: Heat Kernels, Black-Scholes European Prices and Deterministic CarryTextbook
This single substantial mission combines the mathematical work formerly scheduled as FD-06, FD-07 and FD-08 in the Financial Derivatives programme. It develops the heat equation, Gaussian diffusion kernels, the analytic Black–Scholes European call/put formulas and their sensitivities, followed by continuous dividends, forwards and deterministic time-varying…
Financial Derivatives V: Binomial Barrier Options, First-Hit Pricing and RebatesTextbook
Wilmott, Howison and Dewynne, The Mathematics of Financial Derivatives: A Student Introduction (1995), Chapter 12, pp. 206–212 (https://doi.org/10.1017/CBO9780511812545.013), examine knock-out and knock-in options, barrier conditions and rebates. This fifth Financial Derivatives mission establishes rigorous finite-binomial first-hit valuation identities…