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.
Heteroscedastic Exponomial Choice: Under Independent Exponential Utility Errors with Choice-Specific Rates, Every Choice Probability Is a Closed-Form ExponomialResearch Paper
Random utility models are the standard way to turn utilities into demand in operations management, marketing and economics. A consumer facing n products assigns each a random utility and buys the one with the highest realization; the choice probabilities are the market shares that pricing and assortment models optimize. The multinomial logit, built on…
Distributed Stochastic Optimization with Large Delays: Under Polynomially Growing Delays, Asynchronous SGD with Tuned Step-Sizes Drives the Mean-Square Gradient Norm to ZeroResearch Paper
Large-scale learning problems, such as empirical risk minimization over millions of samples, are solved in practice by stochastic gradient descent (SGD) run on many processors at once. In a master–worker system, or in a multi-processor system with shared memory, a worker reads the current parameter, computes a stochastic gradient and writes its update back.…
The Regularity of the Value Function of Repeated Games with Switching Costs: The Value Is Continuous, Increasing, Concave, Piecewise Linear and Eventually Constant in the Switching-Cost WeightResearch Paper
Many repeated interactions charge a player not only for what is played at each stage but also for changing what is played: a firm that reconfigures production, a defender that relocates patrols, a server that migrates jobs. Switching costs model this. In a zero-sum repeated game with switching costs, player 2 pays player 1 a stage payoff that depends on the…
Online Hypergraph Matching with Delays: Randomized Batching with Depth-k Greedy Is 1/d-Competitive for Online-(k, d)-Max-MatchingResearch Paper
Ride-pooling platforms receive trip requests one at a time and must decide, within a short waiting window, which requests to group into a shared vehicle. A request that is not grouped before its window closes is served alone or lost. Online hypergraph matching with delays is the combinatorial core of this decision: requests are vertices that arrive over…
Efficient Allocations in Double Auction Markets: Repeated Double Auctions Drive the Consumer Surplus to Zero at Rate 1/t and Their Cluster Points Are Individually Rational Pareto AllocationsResearch Paper
Double auctions match buy and sell orders at a common price. Stock exchanges, commodity markets and electricity markets use them at their opening and closing auctions and to trade multi-asset portfolios. Economists have long asked how efficient the resulting allocations are. Laboratory work starting with Smith (1962) found that repeated double auctions with…
Model-Free Bounds for Multi-Asset Options Using Option-Implied Information and Their Exact Computation: Under No-Arbitrage with Bid–Ask Spreads, the Superhedging Price ϕ(f) Equals sup_{μ∈Q} ∫f dμResearch Paper
A trader who quotes an exotic option written on several underlying assets (a basket call, a spread option, a best-of option) needs a price range that does not rest on a particular stochastic model. What is observed in the market is a finite set of liquid derivatives (vanilla calls and puts on each asset, and possibly some traded basket options), each with a …
Queueing Dynamics and State Space Collapse in Fragmented Limit Order Book Markets: every equilibrium is the lifting of a one-dimensional workload equilibriumResearch Paper
US equities trade on many exchanges at once. Each exchange keeps its own limit order book, and at the national best bid the same price is offered in several queues that differ in the rebate the exchange pays a liquidity provider and in how long a resting order waits to be filled. An investor who posts a limit order chooses an exchange, or decides to cross…
Distributional Transforms, Probability Distortions, and Their Applications: Probability Distortions Are Exactly the Monotone, Lower-Semicontinuous Transforms Commuting with Shape TransformsResearch Paper
Many models in decision theory, insurance and risk management do not act on random outcomes directly but on their distributions. A distributional transform is a map T that sends a probability distribution F on R to another distribution T(F). The most important class is that of probability distortions, T(F)=g∘F for an increasing function g on …
Time Consistency of the Mean-Risk Problem: The Upper Images of the Dynamic Mean-Risk Problem Satisfy a Set-Valued Bellman RecursionResearch Paper
Markowitz's mean-variance problem trades off the expected terminal wealth of a portfolio against its risk. Over several periods the scalarized form of this problem is time inconsistent: a strategy that is optimal today for a fixed risk-aversion parameter is generally no longer optimal tomorrow for the same parameter, so the investor would deviate from her…
The Folk Theorem for Repeated Games with Time-Dependent Discounting: Subgame Perfect Equilibrium Payoffs Converge to the Feasible and Individually Rational Set as Players Become PatientResearch Paper
Repeated games model long-run relationships: the same players meet stage after stage, observe what was played, and can condition today's behavior on the past. The folk theorem describes what such relationships can sustain. When players are patient, every payoff vector that is feasible and gives each player at least what the others can force on them is the…
The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP: The Circlet Inequality Is Valid and Facet-Defining for the Symmetric TSP Polytope When 4 Divides nResearch Paper
The symmetric traveling salesman polytopeSTSP(n) is the convex hull of the incidence vectors of all Hamiltonian cycles of the complete graph Kn. Minimizing a linear cost over it is the traveling salesman problem, and polyhedral methods for the TSP (cutting planes, branch and cut, LP relaxations and their integrality gaps) depend on linear inequalities…
A Moment-Sum-of-Squares Hierarchy for Robust Polynomial Matrix Inequality Optimization with Sum-of-Squares Convexity: Both Bounds of the Hierarchy Decrease to the Robust Optimum f⋆Research Paper
Many problems in control, robust semidefinite programming and risk management ask for a decision y that keeps a matrix positive semidefinite for every value of an uncertain parameter x in a set X. Examples include robust polynomial SDPs (Scherer and Hol, 2006), Lyapunov-type conditions that must hold on a region of the state space, and robust…
Technical Note—Global Robust Stability in a General Price and Assortment Competition Model: Robust Best-Response Price Dynamics Contract Geometrically to the Special Equilibrium from Any StartResearch Paper
Retailers that sell many products set prices against one another, and the demand for each product depends on the prices of all of them. Affine demand models, q(p)=a−Rp, are the standard starting point for this kind of multi-product price competition in operations management and industrial organization. Two questions follow once an equilibrium is known to…
Network Pricing: How to Induce Optimal Flows Under Strategic Link Operators: Optimal Tolls Bounded by the Marginal Tolls Are (Strong) Cap EquilibriaResearch Paper
Congestion pricing charges road users for the delay they impose on others. The classical theory, going back to Beckmann, McGuire and Winsten (1956), assumes a single benevolent authority that sets every toll: charging each link its marginal toll makes the selfish (Wardrop) traffic pattern socially optimal. Many real networks are different. Roads, bridges…
Game of Thrones: Fully Distributed Learning for Multiplayer Bandits: Without Communication, the Game of Thrones Algorithm Has Expected Total Regret O(log^{1+δ} T)Research Paper
In a multiplayer multi-armed bandit, several agents repeatedly choose among the same finite set of arms, and two agents that choose the same arm collide and receive nothing. The model comes from cognitive radio and wireless networks: users share channels, a channel used by two users at once carries neither transmission, and the quality of a channel differs…
Binary Extended Formulations and Sequential Convexification: Among All d-Hypercube Binarizations, the Logarithmic Binarization Has Minimum RankResearch Paper
Mixed-integer programs often contain general integer variables x∈{0,…,k}. A standard modelling device replaces such a variable by d binary variables y∈{0,1}d linked to x through a polytope, a binarization. Examples are the unary encoding, the "full" encoding with one indicator per value, and the logarithmic encoding x=∑i2i−1yi.…
An Approximate Dynamic Programming Approach to the Incremental Knapsack Problem: For Every ε > 0 the Cluster Dynamic Program Returns a Feasible Solution Within Factor 1 − ε of OptimalResearch Paper
The incremental knapsack problem is a multi-period extension of the binary knapsack problem. Items are inserted over a planning horizon whose capacity grows over time, and an item, once inserted, stays. Sharp (2007) and Hartline (2008) introduced it in their theses on incremental optimization. It models resource allocation in which the available budget…
Modeling, Measuring and Managing Risk X: Dual Representation of Polyhedral Acceptability FunctionalsTextbook
Risk measures enter optimization models as objectives or constraints, and the models that use them
most, multi-stage stochastic programs, are solved as large linear programs. A risk functional is
only usable there if it can itself be written as the value of a linear program. Eichhorn and
Römisch introduced polyhedral risk measures for this purpose
(doi:10.11…
Modeling, Measuring and Managing Risk VII: Dual Representation of Minimal Loss Deviation FunctionalsTextbook
A deviation functional measures how far a random profit Y spreads around its mean: the variance, the standard deviation, the mean absolute deviation from the median, and the average value-at-risk deviation are the standard examples in portfolio selection and in risk-averse stochastic programming. Pflug and Römisch, Modeling, Measuring and Managing Risk (Worl…
Modeling, Measuring and Managing Risk V: Dual Representation of Conditional Acceptability MappingsTextbook
A risk measure that returns a single number answers the question "how acceptable is this random
profit, seen from today?". Multi-period decision problems — portfolio rebalancing, insurance
reserves, stochastic programs on scenario trees — need the same question asked at every later
date, given the information available then. The answer is no longer a number…
Submodular Maximization over Multiple Matroids via Generalized Exchange Properties: Polynomial approximation for monotone submodular maximizationResearch Paper
Selecting a valuable subset subject to several simultaneous restrictions is a common combinatorial optimization problem. A facility may contribute less after nearby facilities have already been selected; a collection of observations may provide overlapping information. Such diminishing returns are captured by submodular objectives. Matroid constraints…
On the Existence of Pure Nash Equilibria in Weighted Congestion Games: Characterizing universal pure equilibrium existenceResearch Paper
A system of users sharing resources may have no stable configuration: whenever the users settle on their choices, somebody may prefer to change. Weighted congestion games describe this question when different users place different demands on the resources they choose. Routing and scheduling provide examples, but the mathematical question here does not…
Food Delivery Service and Restaurant: Friend or Foe?: With Convenient Delivery, a Critical Mass of Tech-Savvy Customers Makes the Restaurant Delivery-Only and Cuts Platform Profit and WelfareResearch Paper
Food delivery platforms such as Uber Eats, DoorDash and Meituan let a restaurant serve customers who never enter it, but they also charge those customers a delivery fee and share the restaurant's kitchen with its walk-in trade. Whether the platform helps or hurts the restaurant is a question restaurant owners, platforms and regulators all ask. Chen, Hu and…
Robust Optimization I: Conic Representations of Robust Linear ConstraintsTextbook
A production or allocation decision can satisfy a linear constraint for nominal data and violate it when those data change. Robust optimization asks for a decision that satisfies the constraint for every realization in a prescribed uncertainty set. The uncertainty set is part of the model: the requirement does not attach probabilities to its elements, and…
Managing Capital Market Frictions via Cost-Reduction Investments: A Positive Friction Effect Makes Cost-Reduction Investment More Beneficial Under Capital Market Frictions than in Their AbsenceResearch Paper
A firm that can lower its unit production cost must usually spend money before it sells anything. That payment improves the margin on future sales but leaves less cash to fund production. If the firm borrows the shortfall, the investment can therefore change both its operating return and the cost of financing. Tanrisever, Joglekar, Erzurumlu and Lévesque…