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.
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…
Financial Derivatives III: Multi-Period Binomial Replication and Optimal ExerciseTextbook
A binomial option-pricing model is more than a numerical approximation: it is a finite complete market in which prices can be derived recursively from self-financing replication. At each node, the one-period stock-and-bank market fixes the value of the two possible continuation payments. Repeating this calculation yields the unique European replication…
Financial Derivatives IV: Compound, Chooser and Barrier Option IdentitiesTextbook
The fourth mission in the financial-derivatives series follows the Cambridge chapter by Paul Wilmott, Sam Howison and Jeff Dewynne, The Mathematics of Financial Derivatives (1995), Chapter 11, Exotic and Path-dependent Options, printed pp. 197–205. In particular, §§11.2–11.4 introduce compound options (options on options), chooser options and barrier…
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…
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…
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…
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…
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…
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∈Rn with as few nonzero entries as possible such that Ax is close to b. The direct formulation, minimizing the number of nonzeros ∥x∥0, is combinatorial and NP-hard in general. A…
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⊆Rn with orthogonal complement L⊥, the pair of problems
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…
Speeding up Policy Simulation in Supply Chain RL: Picard Iteration for Fulfillment Converges in at Most One More Iteration than the Number of Nodes That Run Out of CapacityResearch Paper
Training and back-testing a reinforcement-learning policy for a supply chain requires policy simulation: given an initial state, a horizon T and a sequence of exogenous events, compute the actions the policy takes when the system evolves under its own decisions. In large online retail networks the horizon is the number of customer orders, in the millions,…
Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents: Above Load b_max/t_{b_max} Every Scheduler Diverges, Below It Every Work-Conserving K-FCFS Scheduler Is Positive RecurrentResearch Paper
A large language model (LLM) answers a request in two phases. In the prefill phase it reads the whole prompt; in the decode phase it generates the answer one token at a time, because each new token depends on all previous ones. Serving engines such as vLLM, SGLang and Sarathi-Serve run the GPU in iterations: each iteration processes one batch that may mix…
New Combinatorial Insights for Monotone Apportionment: House-Monotone and Quota-Compliant Apportionments Are the Seat Counts of Extreme Points of a Network Flow LP with Lookahead Φ(p, H)Research Paper
An apportionment method distributes the H seats of a house among n states in proportion to their populations. Exact proportionality is impossible with integer seats, so methods are judged by axioms. Two axioms date back to the debates over the seats of the US House of Representatives. Quota compliance asks that each state receive its exact proportional…
Decomposition of Games: Some Strategic Considerations: Duplicating a Strategy Commutes with the (μ,γ)-Decomposition into Potential, Harmonic and Nonstrategic ComponentsResearch Paper
A finite game can be split into simpler pieces. Candogan, Menache, Ozdaglar and Parrilo (Math. Oper. Res. 36 (2011)) showed that the space of finite games is the direct sum of potential, harmonic and nonstrategic games: potential games have pure equilibria and well-behaved learning dynamics, harmonic games generalize matching pennies, and nonstrategic games…
Search for an Immobile Hider on a Binary Tree with Unreliable Locational Information: The Value Is 2qμ + (p − q)D, Attained by the Recursive Hider Distribution and the Favoring-Bias SearcherResearch Paper
Search games model a Searcher looking for an object or a person whose location is chosen adversarially: a lost hiker, a mine, a hidden explosive device, a fugitive. In the classic search game on a tree, a Hider stands still at a point of a tree network, and a Searcher starts from the root and moves at unit speed. The payoff is the time to find the Hider. Gal…
Differences-in-Neighbors for Network Interference in Experiments: The DN Estimator Has Bias at Most d²ε Under ε-Smooth Neighborhood InterferenceResearch Paper
Online platforms, social networks and marketplaces run randomized experiments (A/B tests) to estimate the effect of a new feature. The standard analysis assumes that one unit's treatment does not affect another unit's outcome. On a network this fails: a treated user changes what their friends see, a treated seller changes what competing sellers sell. The…
Internal Capital Allocation, Voluntary Disclosure, and Investment Efficiency: When a Multi-Divisional Firm Beats Two Stand-Alone FirmsResearch Paper
Conglomerates and stand-alone firms finance projects differently. A multi-divisional firm runs an internal capital market: headquarters raises funds externally and then decides which division gets them. A stand-alone firm must raise capital project by project. A long line of work in corporate finance asks when the internal market is more efficient: Stein (19…
Decision Forest: A Nonparametric Approach to Modeling Irrational Choice: Every Customer Choice Model Is a Decision Forest of Depth at Most N + 1Research Paper
Retailers, airlines and platforms decide which products to offer by predicting how customers substitute among them. Such predictions rest on a discrete choice model: for every set of offered products, a probability distribution over what a customer buys. The classical models are built on random utility maximization (RUM): each customer draws utilities and…
Optimal Experimental Design for Staggered Rollouts: S-Shaped, Covariate-Balanced Rollouts Maximize the Trace of the GLS Precision of Instantaneous and Lagged EffectsResearch Paper
Firms and public agencies often roll a new product, feature or policy out gradually: a few markets first, more later, every market eventually. When the rollout is itself an experiment, its schedule determines how precisely the effect of the treatment can be estimated. A staggered rollout is the common design in which treatment, once switched on in a unit,…
Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressure: Mirror Backpressure Loses at Most O(K/T + 1/K + √(ηK)) Payoff per CustomerResearch Paper
Ride-hailing, car-sharing and bike-sharing platforms, as well as scrip systems, move a fixed stock of reusable resources around a network. Each customer that is served relocates one unit, from a pick-up location to a drop-off location. The operator decides, customer by customer, whether to serve and with which unit. Supply can run dry at a location, which…
When Is Assortment Optimization Optimal?: Under History-Monotone Futures, Assortments Are Optimal Among All IC MechanismsResearch Paper
Assortment optimization is the problem of choosing which items to offer a customer who buys at most one item, when each item has a fixed, exogenous price. It is one of the central problems of revenue management: the customer's behaviour is described by a choice model, and a large literature computes optimal assortments under specific models, from the…
Learning to Rank an Assortment of Products: The Simple Learning Algorithm Hooks Half the Optimal Ranking's Customers up to ε with Probability 1 − δResearch Paper
Online retailers display hundreds of products in a list or a grid, and most visitors never scroll far. A customer who finds nothing appealing near the top leaves without engaging at all, so the order of the first few slots decides whether a visit turns into a click, and through it into a sale. Ferreira, Parthasarathy and Sekar (SSRN 3395992; Management…
The Joint Determination of Haircuts and Interest Rates for Collateralized Loans in Shadow Banking: Better Downside Collateral Quality Lowers the Haircut Iff E[ω | ω > ω*] > (e₀ − e₁)/KResearch Paper
Collateralized short-term loans, repurchase agreements above all, are the funding market of shadow banking. Each such loan carries two terms: an interest rate and a haircut, the fraction of the collateral's value that the lender does not finance. Studies of repo terms by collateral type around the 2007–2009 crisis (Gorton and Metrick, 2012; Krishnamurthy,…
On Time-Consistent Equilibrium Stopping Under Aggregation of Diverse Discount Rates: The Smallest One-Barrier Equilibrium Is the Optimal EquilibriumResearch Paper
A group that shares one stopping decision (a board deciding when to abandon an R&D project, a fund deciding when to exercise a real option) rarely shares one discount rate. A standard way to aggregate heterogeneous time preferences is to treat the discount rate ρ as random with law Fρ and to average discounted payoffs over it. Weitzman (2001) showed…