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.
Modeling, Measuring and Managing Risk IV: Kusuoka Representations of Version-Independent Acceptability FunctionalsTextbook
Risk measures used in portfolio optimization, insurance pricing and regulation are almost always law invariant: they assign a number to a random profit Y that depends only on its distribution, not on the scenario in which each outcome occurs. Kusuoka (Kusuoka 2001) showed that on a non-atomic space every law-invariant coherent risk measure is the worst…
Stochastic Networks XV: Positive Recurrence under MaxWeight SchedulingTextbook
A switch or wireless network can have several queues ready for service while its hardware permits only certain combinations to be served together. A scheduler must choose a feasible combination repeatedly as new packets arrive. The question is whether this local sequence of decisions keeps the queue process stable whenever the arrival rates fit within the…
Stochastic Networks XIII: The Capacity Region of Distributed Random AccessTextbook
Stations sharing a communication channel must decide when to transmit. If nearby stations transmit together, their signals may interfere; if they all wait, capacity is wasted. A central scheduler can coordinate activity, but distributed access assigns decisions to individual stations. The mathematical question is whether simple random local decisions can…
Robust Optimization XIII: Exact Quadratic Decision Rules on EllipsoidsTextbook
An adjustable decision is a rule that responds to information revealed after an optimization problem is specified. In production planning, for example, a later quantity may depend on observed demand, while an earlier commitment must remain constant. A robust counterpart requires the resulting decisions to satisfy the constraints for every realization in a…
Robust Optimization XIV: Extreme-Scenario Reduction in Multistage InventoryTextbook
An inventory manager chooses replenishment orders before knowing all future demand. Orders made today affect both the stock available tomorrow and the cost of later decisions. A flexible commitment contract adds another consideration: deviations from previously announced orders can incur penalties. The uncertainty therefore concerns a sequence of…
Robust Optimization XI: Finite Reformulations of Worst-Case Convex LossTextbook
Regression and classification fit a parameter vector to observed data. When measurements can vary within a prescribed set, a fit judged only at the nominal observations need not control its loss on the possible data. A worst-case loss constraint requires the loss bound to hold for every admissible matrix of measurements. Such a requirement can contain…
Robust Optimization II: Safe Robust Counterparts for Bounded Random PerturbationsTextbook
A linear constraint can fail when its coefficients vary. In an engineering or planning model, requiring it to hold for every imaginable realization may exclude useful decisions, while checking it only at an average realization may give little control over failure. A chance constraint specifies an acceptable probability of violation. Chapter 2 of Ben-Tal, El…
Robust Optimization IV: The Bernstein Uncertainty SetTextbook
An optimization model can require a linear inequality to hold with high probability when its coefficients are random. Such a chance constraint controls the probability of violation, but its feasible set need not be convex or easy to describe. A conservative convex approximation can make the requirement usable within a larger optimization model. Chapter 4 of …
Robust Optimization III: Global Sensitivity for Linear ConstraintsTextbook
A resource constraint can remain useful even when an exceptional disturbance makes exact satisfaction impractical. In such cases the model needs to distinguish the disturbances against which feasibility is mandatory from those for which a controlled violation is acceptable. Ordinary robust optimization specifies a set of perturbations and requires the…
An Axiomatic Foundation for the Expected Shortfall: Monotonicity, Law Invariance, Prudence and No Reward for Concentration Characterize ES on L¹Research Paper
Banks hold capital against the risk of their trading books, and the amount is computed by a risk measure: a functional ρ that assigns a real number to each random loss X. For two decades the regulatory standard was the Value-at-RiskVaRp, a quantile of the loss. The Fundamental Review of the Trading Book of the Basel Committee (BCBS, 2019)…
Geometric Deep Learning V: A Degree-r Polynomial Filter Σ αₖΔᵏX of a Graph Laplacian Is Localised in r-Hop NeighbourhoodsTextbook
Graph neural networks and geometric learning on meshes rely on operators that combine the features of a node with those of its neighbours. The graph Laplacian is the oldest such operator: it is the discrete analogue of the Laplace–Beltrami operator of a surface, and its eigenvectors play the role of a Fourier basis on a graph. Early spectral graph networks (…
Geometric Deep Learning VII: The E(3)-Equivariant Message-Passing Layer Leaves Node Features Invariant and Moves Coordinates with Every Rigid MotionTextbook
Many graphs that graph neural networks (GNNs) are applied to are embedded in space. In a molecular graph the nodes are atoms, and each atom carries both chemical information (its type) and its three-dimensional position. A prediction about the molecule (an energy, a binding affinity) must not depend on where the molecule sits or how it is oriented, and a…
Geometric Deep Learning VI: Cotangent Weights Are Intrinsic, cot ∠uqv = (ℓ²_uq + ℓ²_vq − ℓ²_uv)/(4a_uvq) with Heron's Area a_uvqTextbook
Surfaces of three-dimensional objects are stored in computer graphics, vision and geometry processing as triangular meshes: finitely many points glued together by triangles. Geometric deep learning on such data needs a discretisation of the Laplace–Beltrami operator, because spectral filters, diffusion and many graph neural network layers on meshes are…
Geometric Deep Learning II: Every Linear Permutation-Equivariant Map on ℝⁿ Is a Linear Combination of the Identity and the Averaging Map (1/n)𝟙𝟙ᵀTextbook
Many learning problems take an unordered collection as input: the points of a point cloud, the particles of a physical system, the atoms of a molecule, the nodes of a graph. Storing such data in memory fixes an order of the elements, but the order carries no information, and a model whose output changes when the rows of its input are shuffled is answering a…
Geometric Deep Learning IV: Group Convolution (x ⋆ θ)(g) = ⟨x, ρ(g)θ⟩ Against an Invariant Measure Is Equivariant, (ρ(h)x) ⋆ θ = ρ(h)(x ⋆ θ)Textbook
Convolutional networks use the same filter at many locations. A shift of the input then shifts the output in a predictable way, allowing one set of filter coefficients to serve every location. Bronstein, Bruna, Cohen and Veličković, Geometric Deep Learning, §4.3, pp. 40–43 ask how this idea extends when the transformations form a group and the signal domain…
Negotiating Government-to-Government Food Importing Contracts: A Nash Bargaining Framework: With Sufficiently Many Suppliers, Forward Negotiations Beat Ad Hoc Negotiations for the BuyerResearch Paper
Food importers that also produce domestically must decide whether to commit to purchases before the domestic harvest or negotiate after observing it. This choice matters when suppliers must plant before the harvest is known: a late negotiation leaves them exposed to unsold production, while an early contract commits the importer to purchases it may no…
Offering Memories to Sell Goods? Pricing and Welfare Implications of Experiential Retail: A Sufficiently Low-Quality Free Experience Raises Both the Monopoly Retailer's Profit and Consumer WelfareResearch Paper
Retailers increasingly pair products with free in-store experiences: yoga classes at Lululemon, playgrounds at Toys "R" Us, cooking classes at Whole Foods. The experience is free to anyone who travels to the store, so it attracts buyers and free riders (visitors who enjoy the experience without buying) alike. The retailer earns revenue only from product…
Selling Assets: Are Sellers Better Off with Strong Buyers?: Under Free Entry, a More Dominant Strong Buyer Lowers the Seller's RevenueResearch Paper
A seller who can attract a buyer with a higher valuation might expect a higher auction price. That intuition holds when the number of competing buyers is fixed. If other buyers must pay to learn their valuations and decide whether to enter, a stronger buyer can instead cause some of them to stay out. Marquez and Singh study this response in a second-price…
Managerial Regret and Inventory Pricing: The Regretful Seller's Marginal Value of Inventory and Price Increase with Time-to-Go and Decrease with Remaining InventoryResearch Paper
Revenue management studies how a seller with a fixed stock and a finite selling season should price over time. The classical models assume an expected-revenue maximizer: Gallego and van Ryzin (1994) in continuous time and Bitran and Mondschein (1997) in discrete time showed that the optimal price and the marginal value of inventory rise with the time left…
Joint Mixability and Notions of Negative Dependence: The Minimizers of the Worst-Case Quadratic Cost over Subsets of Components Are Exactly the NCD Joint Mixes with Correlation Matrix P*_nResearch Paper
A joint mix is a random vector X=(X1,…,Xn) whose component sum ∑i=1nXi is almost surely constant. For fixed marginal distributions it minimizes the variance, the stop-loss premium and the Expected Shortfall of the aggregate, which comonotonicity maximizes, and for this reason it is regarded as the canonical form of extremal negative…
Feasible Bases for a Polytope Related to the Hamilton Cycle Problem: Every Ultimate Feasible Basis Is a Good Augmented Spanning Tree Whose Thick Arcs Form the Unique Perfect MatchingResearch Paper
A Hamilton cycle visits every vertex of a directed graph once and returns to its start. Finding one is a standard combinatorial optimization problem, and linear programming provides a way to study it through extreme points. Kalinowski and Mohammadian examine a polytope introduced for this purpose and ask what its feasible bases look like when a discount…
Endogenous Inverse Demand Functions: Necessary and Sufficient Conditions for a Unique Clearing Price of a Liquidated ClaimResearch Paper
When a bank or fund in distress must sell a large position, the price it receives depends on how much it sells: the market's capacity to absorb the sale is finite. Models of fire sales and systemic risk (for instance Cifuentes, Shin and Ferrucci and Amini, Filipović and Minca) encode this through an inverse demand function, the price per unit as a function…
Dynamic Double Auctions: Toward First Best: With One Seller and Many Buyers, the Mechanism That Couples All Promised Utilities Earns First-Best Profit up to O(√(T log T))Research Paper
A platform that matches one seller with several buyers can trade an item whenever a buyer values it more than the seller does. That allocation maximizes the value created by trade in a single period. A platform seeking revenue also has to respect what privately informed agents are willing to report and accept. In a repeated market, it can distribute utility…
Optimal Auction Design with Deferred Inspection and Reward: The Optimal Single-Agent Auction Has Best-Alternative Bid b(v) = G⁻¹(G(v) − G(v̲)) and a Continuous AllocationResearch Paper
A seller who can inspect a buyer's true value after receiving a bid can use the bid as a refundable deposit. A truthful buyer may receive a reward, while a buyer whose report is false forfeits the deposit. This changes the incentive constraint: a buyer who considers reporting w compares her truthful utility with vx(w)−w, not with the payoff from a…
Adaptive Bin Packing with Overflow: Budgeted Greedy Has Expected Cost at Most (3 + 2√2) Times That of the Optimal Policy for I.I.D. Item SizesResearch Paper
Sequential packing matters when an item's size is known statistically before placement but revealed only afterward. A connection request has uncertain bandwidth, a shipment has uncertain final weight, and a virtual machine has uncertain resource use. In each example, exceeding capacity can have a separate cost from opening another container. Perez-Salazar,…