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.
Set Relations via Families of Scalar Functions and Approximate Solutions in Set Optimization: A Weierstrass-Type Existence Theorem with Hausdorff Convergence of Approximate MinimizersResearch Paper
Many decision problems have set-valued outcomes rather than single numbers. Typical cases are a portfolio whose risk is a set of capital vectors, a vector optimization problem whose image is upper-bounded by an ordering cone, or a robust model whose value is the set of all achievable outcomes. Set optimization minimizes such a map f:X→P(Z).…
Reputation, Competition, and Lies in Labor Market Recommendations: The Equilibrium Hiring Probability Rises with the Adviser's Reputation in Top-Heavy Markets and Falls in Bottom-Heavy MarketsResearch Paper
Hiring decisions often rest on a recommendation from someone who knows the candidate: a thesis adviser, a former supervisor, a colleague. Referrals are a common channel of labor market matching, and their value depends on whether the recommender can be trusted. An adviser who cares about his candidate has a reason to overstate the candidate's quality, and…
Regular Matroids Have Polynomial Extension Complexity: The Independence Polytope of Every Regular Matroid on n Elements Has Extension Complexity O(n⁶)Research Paper
Many combinatorial optimization problems are linear programs over a polytope with exponentially many facets, and one way to solve them by a polynomial-size linear program is to write the polytope as the projection of a higher-dimensional polytope with few facets. The minimum number of facets needed is the extension complexity of the polytope. It is now…
Revenue Volatility Under Uncertain Network Effects: The Worst-Case Relative Revenue Change over ε-Perturbed Networks Equals αλmax·ε/(1 − αλmax(1 + ε))Research Paper
A seller of a good with network externalities (a social app, a telecom plan, a game console) gains from knowing how strongly each consumer's demand depends on the consumption of others. Candogan, Bimpikis and Ozdaglar (Operations Research, 2012) showed that, on a known network, the optimal price vector of a monopolist and the resulting revenue have closed…
Naive Learning Through Probability Overmatching: Along Any Vanishing-Influence Network Sequence, Extremization DeGroot Processes Eventually Agree on the True State with Probability Tending to OneResearch Paper
Models of naive social learning ask whether agents who update by simple averaging rules, rather than by Bayes' rule, can still aggregate dispersed information. In the classic DeGroot model every agent repeatedly replaces her belief by a weighted average of her neighbours' beliefs. Golub and Jackson (2010) showed that when agents communicate real-valued…
Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models: The Sampled Upper Base-Stock Policy Costs at Most (1 + ε) Times the Optimum with Probability 1 − δResearch Paper
The periodic-review inventory problem asks how much stock to order in each of T periods when demand is random, unmet demand is backlogged, and both leftover stock and shortages are charged. When the demand distributions are known, a backward dynamic program computes an optimal policy, and the optimal policy is a base-stock policy: in each period, order up…
Introduction to Matrix Analytic Methods in Stochastic Modeling XII: Level-Dependent QBDs and Their Minimal SolutionsTextbook
Many queueing and reliability models are Markov chains on a two-dimensional state space whose first coordinate, the level, moves by at most one unit per transition, while the second, the phase, records an auxiliary state such as the phase of a service time or the number of busy servers. When the transition probabilities do not depend on the level, such a…
A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions: The Algorithm of Figure 3 Returns a Minimizer of Every Real Submodular Function in O(n⁷ log n) StepsResearch Paper
Submodular function minimization asks for a subset X of a finite set V that minimizes a set function f satisfying f(X)+f(Y)≥f(X∪Y)+f(X∩Y). Cut functions, matroid rank functions and entropy are submodular, and minimizing them is a subroutine in dynamic flows, facility location and source coding. Grötschel, Lovász and Schrijver showed in…
The Traveling-Salesman Problem and Minimum Spanning Trees: The 1-Tree Gap Vanishes Exactly When the Subtour LP Has an Integral Optimal SolutionResearch Paper
The symmetric traveling-salesman problem asks for a cheapest cycle through all n vertices of a complete graph with real edge weights. Every exact method for it rests on lower bounds, and the most widely used one comes from Held and Karp's two papers of 1970–71 (Held & Karp 1970; Part II, 1971). Their bound is built from 1-trees, a slight variant of spanning…
Flows in Networks V: Common Systems of Restricted RepresentativesTextbook
Assignment questions ask whether every member of a family can be served by a different resource: committees that each need a distinct member as representative, or tasks that each need an admissible worker. The classical answer is Hall's theorem (Hall 1935): a family of sets has a system of distinct representatives exactly when every k of its sets together…
Lectures on Modern Convex Optimization V: Semidefinite Representability of Symmetric Functions of EigenvaluesTextbook
A convex optimization problem can be handed to a semidefinite programming solver only after its constraints and objective have been written as linear matrix inequalities (LMIs): conditions of the form A(x,u)⪰0, where A is affine in the decision variables x and in auxiliary variables u, and ⪰0 means positive semidefinite. A…
Competition and Opacity in the Financial System: Intense Competition Lowers Disclosure Precision Exactly When Investors' Private Information Is PreciseResearch Paper
Banks and other financial institutions are notoriously hard to see into: their loan books are complex and their public reports are coarse. A long-standing policy question is whether competition among financial institutions makes them more or less transparent. One view holds that competition for funding disciplines institutions into disclosing more; another…
Intertemporal Choice with Continuity Constraints: On a Finite Horizon, Eight Axioms Characterize Preferences over Continuous Trajectories Admitting a Discounted Utility Integral RepresentationResearch Paper
Intertemporal choice compares outcomes received at different times. A familiar model assigns each instantaneous outcome a utility and aggregates those utilities with a time weight. That model is useful in economics and operations research, but its meaning depends on what choices are feasible and how a preference over one stretch of time relates to a…
Bonus Season: A Theory of Periodic Labor Markets and Coordinated Bonuses: A Periodic Equilibrium Exists if and only if the Importance of Match Quality Lies Between Two ThresholdsResearch Paper
Large bonuses in some industries are paid within a few weeks of each other across firms: banks in a given region announce bonuses in the same months, and top-tier US law firms announce theirs almost simultaneously. Van Wesep and Waters (SSRN 3124536, published in Management Science, 2022, doi:10.1287/mnsc.2021.4076) explain this coordination with a search…
Beta and Coskewness Pricing: Perspective from Probability Weighting: The Rank-Dependent Equilibrium Pricing Kernel and the Three-Moment CAPMResearch Paper
Asset-pricing models relate an asset's expected return to the risks it shares with the market. A familiar covariance term measures exposure to the market return, while a coskewness term measures exposure to the square of that return. Shi, Cui and Zhou ask how these two coefficients change when investors weight probabilities as well as valuing outcomes.…
Optimal Auction Duration: A Price Formation Viewpoint: Semi-Explicit Formula for the Expected Squared Clearing-Price Error E(h) as a Function of the Auction DurationResearch Paper
Most equity markets trade through a continuous limit order book (CLOB): any market order is matched immediately against the resting limit orders. Budish, Cramton and Shim (QJE 2015) argued that continuous matching creates mechanical arbitrage and a race in speed between high-frequency market makers, and proposed frequent batch auctions instead, with a lower…
Sufficient Optimality Conditions in Bilevel Programming: A Second-Order Sufficient Condition via the Value Function Reformulation and Second-Order Directional DerivativesResearch Paper
In a bilevel program, the decision maker chooses an upper-level variable while a second decision must solve a lower-level optimization problem. This structure occurs when a leader anticipates the response of a follower, or when an outer design problem contains an optimization problem as a constraint. A feasible upper-level decision can therefore change the…
Extension of Additive Valuations to General Valuations on the Existence of EFX: A Complete EFX Allocation Exists When Every Agent Has One of Two General ValuationsResearch Paper
Dividing indivisible goods fairly among agents with different preferences is a central problem of fair division, with uses ranging from inheritance and divorce settlements to course allocation and fair-division services such as Spliddit (Goldman–Procaccia 2014). Envy-freeness cannot always be achieved with indivisible goods (one good, two agents), so…
Disclosing Delivery Performance Information When Consumers Are Sensitive to Promised Delivery Time, Delivery Reliability, and Price: Full or No Information-Quality Effort Is OptimalResearch Paper
Online retailers and service providers quote a promised delivery time and are judged on how often they meet it. Platforms increasingly publish delivery-performance information, such as on-time ratings or conformance scores, so that consumers can weigh a quoted time against the firm's record. Producing accurate information is costly: the firm must track…
Optimal Dynamic Momentum Strategies: For Horizons Within the Look-Back Period, the Optimal Weight Is the Mean-Variance Weight Plus a Hedging Term Weighted Toward Recent ReturnsResearch Paper
Time-series momentum is the empirical regularity that an asset's recent excess return predicts its future excess return. It has been documented across equity indices, currencies, commodities and bonds (Moskowitz, Ooi & Pedersen 2012), and momentum portfolios are among the most widely traded systematic strategies. Most of that literature builds portfolios…
Product Selling vs. Pay-Per-Use Service: A Strategic Analysis of Competing Business Models: Pay-Per-Use Out-Earns Selling in Duopoly Equilibrium Iff the Delivery Cost Is Below a ThresholdResearch Paper
A firm can sell a product outright or charge customers each time they use it. Selling collects one payment and transfers the asset to the customer. Pay-per-use service (PPU) keeps control of the asset, earns revenue from each use, and incurs a delivery or operating cost each time. These arrangements coexist for equipment, vehicles, and other products whose…
Donations for Refugee Crises: In-kind Versus Cash Assistance: A Price-Dependent Cash Assistance Policy Makes the Target Price Optimal for the RetailerResearch Paper
Humanitarian organizations (HOs) have long helped refugees with in-kind assistance: food, hygiene and shelter items bought at wholesale cost and handed out. Cash assistance, money that refugees spend at local stores, has grown quickly. In 2014 it was 6% of the $25 billion of humanitarian assistance worldwide; by 2019, cash and vouchers were 18% (High Level…
I Don’t “Recall”: The Decision to Delay Innovation Launch to Avoid Costly Product Failure: Neither, Both, or Exactly One of Two Identical Firms Tests, by Failure-Probability CutoffsResearch Paper
Product recalls are frequent and costly. A firm that launches an innovation without thorough quality assurance testing gains time on the market but risks a recall, which brings direct costs (repairs, refunds, legal settlements) and lasting damage to the product's reputation. Testing removes the risk but delays the launch, and while a firm tests, a rival can…
Interactive Information Design: Every Information Design Game with Finite Message Sets Admits a Subgame Perfect EquilibriumResearch Paper
An information designer can change what others know without choosing their actions. When several designers disclose information at once, each designer's experiment affects the incentives faced by agents who receive messages from all of them. The resulting strategic problem appears in competing disclosures, advice, and mediated decisions. Koessler, Laclau,…
Supply Chains and Antitrust Governance: Under the Illinois Brick Ruling, Only the Wholesale-Price-Plus-Fixed-Fee Contract Lets Competing Manufacturers ColludeResearch Paper
In Illinois Brick Co. v. Illinois (431 U.S. 720, 1977) the U.S. Supreme Court held that only direct purchasers may recover antitrust damages; an indirect purchaser, who bought the overpriced goods through an intermediary, may not sue on the ground that the overcharge was passed on to it. In a three-tier supply chain of manufacturers, retailers and…