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.
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…
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…
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…
A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents: The Gaussian Gittins Index Equals the Posterior γ-Quantile μ + Φ⁻¹(γ)σ up to o(1) as γ → 1Research Paper
A Gittins index assigns a number to an uncertain arm in a discounted bandit problem. The index converts a sequential choice, where an agent may keep gathering information or retire, into a tax threshold for playing the arm. Computing it generally requires an optimal stopping calculation. A Bayesian upper confidence bound, by comparison, is a quantile of the…
Computation of Dynamic Equilibria in Series-Parallel Networks: The Thin-Flow Label Function of a Series-Parallel Network Has at Most 2|A′| − |A*| − |V| + 1 BreakpointsResearch Paper
In the fluid queuing model (Vickrey's model) of flows over time, a continuum of infinitesimal particles travels from a source s to a sink t through a network whose arcs have capacities and transit times. Each particle picks a route that minimizes its own arrival time, and a dynamic equilibrium (a Nash flow over time) is a flow in which no particle can…
Geometric Deep Learning VIII: An RNN Seeded at a Fixed Point h⁽⁰⁾ = R(0, h⁽⁰⁾) Is Equivariant to Left Shifts of a Zero-Padded Input SequenceTextbook
A recurrent neural network (RNN) processes an ordered stream while retaining a summary of earlier inputs. The same update rule is applied at every time step, so it is natural to ask whether shifting the input stream simply shifts the resulting sequence of summaries. The answer depends on how the run begins. The first summary is supplied as an initial state,…
Geometric Deep Learning III: An n × n Matrix Commutes with the Cyclic Shift S if and only if It Is Circulant, So Convolution Is Shift EquivarianceTextbook
Convolutional neural networks process images, audio and time series with layers whose weights are shared across positions. The Geometric Deep Learning programme of Bronstein, Bruna, Cohen and Veličković (arXiv:2104.13478v2) explains this architecture by symmetry: on a grid the relevant symmetry is translation, and a linear layer that respects translations…
Follow the Crowd with Uncertain Service Capacity: A Customer Who Infers Capacity from the Queue Length Follows the Crowd if and only if the Reward-Cost Ratio Lies in an Inference IntervalResearch Paper
Whether a customer joins a queue depends on how long she expects to wait. In the classical observable-queue model of Naor (1969), the service rate is known, and a longer queue only means a longer wait: customers avoid the crowd (ATC), so the more willing others are to join, the less willing the individual is. Many services do not publish their capacity.…
Invite Your Friend and You’ll Move Up in Line: Optimal Design of Referral Priority Programs: A Unique Cutoff Base Market Size Separates Partial Priority, Full Priority and Strategic DelayResearch Paper
Firms launching a new product often open a sign-up waitlist before they can serve everyone, and many of them reward customers who invite friends with a better place in line. Robinhood (commission-free trading) and x.ai (AI email scheduling) ran such referral priority programs, the first with full priority for referrers and the second with a partial jump in…
Simulation of a Random Variable and its Application to Game Theory: With a Leaked Randomness Source, Alice Can Secure J_cav(H(X|Y)) in the n-Stage Repeated Game up to the Error Term (10)Research Paper
A mixed strategy assumes a player can draw from any distribution. A real player may only have a limited or imperfect source of randomness, and an opponent may observe part of it. Repeated games with bounded randomness ask how much a player can guarantee in that situation. Gossner and Vieille (2002, Games Econ. Behav. 41(2), 206–226) studied a repeated…