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.
Stochastic Linear Programming: Models, Theory, and Computation V: integrated chance constraints with a finite discrete distribution define polyhedraTextbook
A probability constraint in a stochastic linear program asks that a random linear inequality hold with high probability. It counts every violation the same, however large, and the feasible set it defines is in general not convex, as Klein Haneveld's examples show (Klein Haneveld 1986). Integrated chance constraints replace the probability of a shortfall…
Combinatorial Optimization (Cook et al.) VI: The Tutte–Berge Formula for the Maximum Size of a MatchingTextbook
A matching pairs up nodes of a graph along its edges, each node being used at most once. Finding a largest matching is the model problem of combinatorial optimization: the obvious linear relaxation is not integral on non-bipartite graphs, and the methods developed for it (augmenting paths, odd-circuit shrinking, polyhedral descriptions) became standard…
Combinatorial Optimization (Cook et al.) XII: Edmonds' Matroid Polytope TheoremTextbook
The Greedy Algorithm builds a set one element at a time, always adding the heaviest element that keeps the set feasible. For the forests of a graph it finds a maximum-weight forest (Kruskal's algorithm), but for the matchings of a graph it can fail: on a 4-cycle with edge weights 9, 7, 8, 3 it picks the edges of weight 9 and 3 when the edges of weight 7 and…
Combinatorial Optimization (Cook et al.) I: The Characteristic Vector of a Minimum Spanning Tree Is an Optimal Solution of the Spanning-Tree Linear ProgramTextbook
A minimum spanning tree (MST) of a connected graph with edge costs is a cheapest set of edges that connects all nodes and contains no circuit. It is the prototype of a combinatorial optimization problem solved exactly by a greedy rule, and it opens Chapter 2 of Cook, Cunningham, Pulleyblank and Schrijver's Combinatorial Optimization (Wiley, 1998). The…
Combinatorial Optimization (Cook et al.) VII: For Arbitrary Costs the Minimum Cost of a T-Join Equals the Optimal Value of Its Linear ProgramTextbook
A mail carrier must walk every street of a district and return to the post office, and wants to walk as little as possible. Kwan Mei-Ko posed this Chinese postman problem in 1962. Edmonds observed that the extra streets to be walked a second time form a set of edges whose odd-degree nodes are exactly the odd-degree nodes of the street graph, and generalized…
Combinatorial Optimization (Cook et al.) IX: The Hoffman–Kruskal Theorem: {x≥0:Ax≤b} Is Integral for All Integral b Iff A Is Totally UnimodularTextbook
Many combinatorial optimization problems (bipartite matching, maximum flow, shortest paths, transportation and assignment problems) can be written as integer programs
A General Framework for Bandit Problems Beyond Cumulative Objectives: U-UCB has regret O(log T / T) for every stable, smooth EDPM with a linear gapResearch Paper
In the classical stochastic multi-armed bandit a decision maker is scored by the sum of the rewards it collects. Many applications score the collected rewards differently: a portfolio manager cares about the conditional value at risk (CVaR) or the Sharpe ratio of the returns, a clinical trial about a quantile, a risk-averse controller about mean–variance.…
Combinatorial Optimization (Cook et al.) IV: In a Legal Ordering the Last Node's Star Is a Minimum Cut Separating the Last Two NodesTextbook
The global minimum cut problem asks, for a finite undirected graph with nonnegative edge capacities, for a partition of the nodes into two nonempty sides that is crossed by edges of least total capacity. With unit capacities the optimal value is the edge-connectivity of the graph, a basic measure of network reliability; with general capacities the problem…
Fast Core Pricing for Rich Advertising Auctions: the water-filling algorithm finds an ϵ-bidder-optimal core point in O(nlog(n/ϵ)) oracle calls and O(n2log(n/ϵ)) timeResearch Paper
Online ad platforms sell a limited number of lines of ad space to advertisers whose ads come in several shapes and sizes, so their preferences over the space are combinatorial and often complementary (Niazadeh et al., arXiv:1610.03564v4, §1). The Vickrey–Clarke–Groves auction can earn little revenue on such preferences. Core-selecting auctions (Ausubel and…
Hidden Convexity, Optimization, and Algorithms on Rotation Matrices: Every Linear Image of SO(n) in the Plane Is Convex for n≥3Research Paper
Many problems in computer vision, robotics, satellite attitude estimation and point-cloud registration ask for the rotation that best explains some data. In matrix form they are linear optimization problems over the special orthogonal group, max{⟨A,X⟩:X∈SO(n)}, where ⟨A,X⟩=tr(A⊤X). Without side…
Selection of the Most Probable Best: An Allocation Is Optimal for the Relaxed Budget Allocation Problem iff It Satisfies the Global Balance, Pairwise Balance and Zero-Sampling-Ratio ConditionsResearch Paper
Simulation models of service systems, supply chains and financial products depend on input parameters that are themselves estimated from data, such as arrival rates or demand distributions. When a decision maker compares k candidate designs by simulation, this input uncertainty means that the best design may differ from one plausible parameter value to the…
A Simple Characterization of Supply Correspondences: a supply correspondence is strongly rationalizable iff it is maximal monotone and homogeneous of degree zeroResearch Paper
Producer theory asks which observed supply behaviour is consistent with a profit-maximizing competitive firm. A supply correspondence records, for every vector of prices, the set of production plans the firm is willing to choose. If the firm maximizes profit over a fixed technology, its supply must satisfy testable restrictions; the question of rationalizabi…
A Mean-Field Control Problem of Optimal Portfolio Liquidation with Semimartingale Strategies: The Value Function Is Linear-Quadratic in the State's Law and the Optimal Strategy Jumps Only at t and TResearch Paper
A large investor who must sell a position of x0 shares by a deadline T moves the price against their own position: every sale depresses the price, and the depression decays only gradually. Optimal liquidation models this trade-off between trading fast (incurring impact) and trading slowly (bearing inventory risk), and it is a standard problem in market…
Foundations of Reinforcement Learning XII: E2D Regret Is at Most the Decision-Estimation Coefficient Times T Plus γ·EstSqTextbook
In a structured bandit a learner repeatedly picks a decision πt from a possibly huge or continuous set Π and observes a noisy reward with mean f⋆(πt), where f⋆ belongs to a known class F of functions Π→R. The optimal regret depends on F in ways that are hard to predict: optimism (UCB) and posterior sampling…
Improving Blockchain Consistency by Assigning Weights to Random Blocks: Ironclad's Normalized Minimal Adversarial Mining-Power Requirement Strictly Exceeds Nakamoto's (R > 1)Research Paper
Proof-of-work blockchains such as Bitcoin keep a ledger consistent only while the honest parties hold enough mining power relative to an adversary. Network delay erodes that margin: when two honest blocks are mined within the delay bound Δ, honest parties extend different chains, and an adversary can exploit the fork. The consistency bound of a…
Foundations of Reinforcement Learning VII: Empirical Risk Minimization over a Finite Class Has Expected Excess Risk ≲ √(log|F|/T), and ≲ log|F|/T for Well-Specified Square LossTextbook
Interactive decision making rests on estimation: an agent that acts well must fit a model to past data and rely on it for data not yet seen. The lecture notes of Foster and Rakhlin (arXiv:2312.16730) therefore open with statistical learning, the passive problem in which the learner does not influence the data. It isolates generalization and function…
Approximating the Set of Nash Equilibria for Convex Games: Algorithm 4.8's output contains every Nash equilibrium and consists of (ε₁ + (2+κ)Lε₂)-approximate Nash equilibriaResearch Paper
A game with a shared constraint couples the players twice: through their costs and through a joint feasible set that restricts which strategy profiles are allowed. Such generalized Nash games model system-wide limits, for example a common capacity or emission budget (Rosen 1965; Facchinei–Kanzow 2010). They typically have a continuum of equilibria, so one…
The Edgeworth Conjecture with Small Coalitions and Approximate Equilibria in Large Economies: every κ-core allocation of a replica economy is an ε-Walrasian allocationResearch Paper
Edgeworth (1881) conjectured that as an exchange economy grows, the outcomes that no group of traders can improve upon by trading among themselves shrink to the competitive (Walrasian) outcomes. Debreu and Scarf (DS63) proved this for replica economies: an allocation that lies in the core of the n-fold replica En for every n is a Walrasian…
Limit Theory for Taboo-Regenerative Processes: Conditioned on No Exit by Time t, the Cycles Around t and the Age Converge Uniformly to the Two-Sided Taboo Limit P∗Research Paper
Many stochastic models are studied up to a failure: a queue until overflow, a network until a job is lost, a reliability system until breakdown, a Markov chain until it leaves a set of states. When failure is rare, the informative object is the process conditioned on no failure so far. For Markov chains this is the classical theory of quasi-stationary…
An Equilibrium Model for the Cross-Section of Liquidity Premia: an explicit Radner equilibrium with quadratic transaction costs for any number of agents and assets, via global Riccati solutionsResearch Paper
Assets that are expensive to trade earn higher expected returns than comparable liquid assets. Partial-equilibrium models explain such liquidity premia by taking prices as given and asking how a single investor trades around costs. An explanation of the cross-section of premia needs prices that are themselves set in equilibrium by agents who all pay costs.…
The Multi-Objective Polynomial Optimization: the interior of the convex hull of the epigraph set is a moment-cone set, and weakly Pareto values are the boundary of its closureResearch Paper
A multi-objective optimization problem minimizes several objective functions over one feasible set. The objectives rarely share a minimizer, so the usual targets are Pareto points, where no objective can be improved without worsening another, and weakly Pareto points, where the objectives cannot all be improved at once. Such problems arise in economics,…
Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: relaxation-based sampling is within slogs+log(sn)−slogn+α of the optimumResearch Paper
The maximum entropy sampling problem (MESP) asks which s of n jointly Gaussian random variables to observe so that the observed vector carries the most information. For a Gaussian vector the differential entropy of a sub-vector is, up to constants, the logarithm of the determinant of its covariance matrix, so the question is to choose the size-s principal…
Popularity, Mixed Matchings, and Self-duality: every bipartite instance with strict preferences has a max-utility popular mixed matching {(M0,1/2),(M1,1/2)}, pure if a stable matching is perfectResearch Paper
In a two-sided matching market, applicants and jobs rank their acceptable partners, and a planner wants an assignment that is both acceptable to the participants and good for some external objective, such as total value. Stability (no applicant–job pair prefers each other to their assignments) is the classical acceptability notion, but it is restrictive:…
Underdogs and One-Hit Wonders: When Is Overcoming Adversity Impressive?: low-quality agents gaining proportionally more from resources is necessary but not sufficient for P(H|F,S) > P(H|S,S)Research Paper
Evaluators in labor markets, venture capital, sports and the arts routinely judge people by their track records. A common intuition holds that two successes are better evidence of talent than one. Another, equally common intuition celebrates the underdog: the agent who succeeds after an initial failure, against the odds. Denrell, Liu and Maslach (Management…
Retail Category Management with Slotting Fees: slotting fees raise, lower or keep the retailer's equilibrium product variety on the explicit regions Φ↑, Φ↓ and Φ0Research Paper
A slotting fee is a lump-sum payment a manufacturer makes to a retailer for a place in the retailer's assortment. Such fees are common in grocery retailing, and they are contested: manufacturers and regulators have argued that they limit consumers' access to products and raise barriers to entry (Federal Trade Commission 2003; Bloom, Gundlach and Cannon, Jour…