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.
Inventory Integration with Rational Consumers: Unique Correlation and Variability Thresholds Below Which the Behavioral Value of Integration Is PositiveResearch Paper
Inventory integration (or pooling) serves several markets from one stock instead of one stock per market. Its classical value is statistical: when demands are not perfectly correlated, the pooled demand is relatively less variable, so less safety stock is needed for the same service level. Eppen (Management Science, 1979) quantified this for normal demand,…
Time-Varying Semidefinite Programs: Under Strict Feasibility, Feasible Polynomial Solutions Have Objective Values Converging to the TV-SDP Optimal ValueResearch Paper
Many planning problems ask for a decision that varies over a time horizon and must satisfy a constraint at every instant, possibly with cumulative effects of past decisions. The applications in the source paper are a maximum-flow problem with time-varying pipeline capacities, a wireless coverage problem for a moving target region, and the approximation of…
A Model of Queue-Scalping: A Single Queue-Scalper Enters the Queue if and only if the Demand Volume Is IntermediateResearch Paper
A customer who is short of time may pay for a better place in a service queue. Unlike resale of a fixed ticket, this transaction changes the waits faced by later customers, and those customers' choices then change the value of the position being sold. Yang, Wang, and Cui study this feedback in an unobservable queue with a firm that repeatedly sells its…
Artificial Shortage in Agricultural Supply Chains: Cash Subsidy Leaves Artificial Shortage Unchanged on a Small Budget, Mitigates It on a Moderate One, and Aggravates It on a Large OneResearch Paper
Prices of staple vegetables in India, onions above all, rise sharply at irregular intervals. When they do, governments respond with cash transfers, subsidized sales and import programmes. A recurring explanation for these price spikes is artificial shortage: traders who control a large share of the stock withhold supply early in a season, and consumers who…
The Value of Price Discrimination in Large Random Networks: The Expected Fractional Regret of Uniform Pricing Vanishes in Erdős–Rényi Networks of Any DensityResearch Paper
A seller whose customers influence one another faces a choice between two pricing policies. It can collect information about the social network and charge each customer a personalised price that reflects their position in it, or it can ignore the network and charge everyone one uniform price. Personalised pricing is never worse for the seller, but…
Intertemporal Segmentation via Flexible-Duration Group Buying: Above an Explicit Batch-Size Threshold, the Optimal Uniform-Price Campaign Admits High-End Customers First and Both Segments LaterResearch Paper
Group buying sells a product at a discount once enough customers have committed to it. Groupon's "a deal a day" campaigns ran on a fixed deadline. Group buying on Pinduoduo has no preset deadline: a customer pledges, then waits until the group is complete. Most of the operations literature studies the first, fixed-duration form, in which a campaign ends at…
Supplier Encroachment in a Non-Exclusive Reselling Channel: The Encroaching Supplier May Sell Only Directly at a Positive Direct Cost, or Through Both Channels at a Negative OneResearch Paper
Manufacturers that sell through retailers increasingly also sell directly to consumers, through their own web stores or outlets. The operations literature calls this supplier encroachment. The classical analysis (Arya, Mittendorf and Sappington, 2007) assumes an exclusive reseller: the reseller carries only the encroaching supplier's product. In that…
Second-Order Optimality Conditions for Nonconvex Set-Constrained Optimization Problems: A Directional Second-Order Necessary Condition via the Lower Generalized Support FunctionResearch Paper
Optimization problems often require a smooth objective to be minimized subject to membership in a set. When that set is convex, established second-order conditions describe how curvature of the objective and constraints limits a local solution. Complementarity constraints and related models lead to nonconvex constraint sets. The tangent sets needed for a…
Fair Allocation of Indivisible Goods: Improvement and Generalization: Every Instance with Additive Valuations Admits a 3/4-MMS AllocationResearch Paper
Dividing a set of indivisible goods among agents with different preferences is a basic problem of fair division, with applications to inheritance, course allocation and the division of shared assets. With indivisible goods, envy-freeness and proportionality cannot always be achieved: a single good and two agents already rule both out. Budish (The…
Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution: Without Samples, No Stopping Rule Guarantees More Than 1/e of the Expected MaximumResearch Paper
A prophet inequality compares the value obtained by an online decision maker with the largest value in a sequence that could be chosen by someone who sees the entire sequence. The online decision maker observes values one at a time and must decide whether to accept the current value before seeing future values. When the common distribution of the values is…
Correlated Equilibria and Mean Field Games: A Simple Model: Every Limit Point of Symmetric ε_N-Correlated Equilibria in Restricted Strategies Is a Correlated Mean Field Game SolutionResearch Paper
A correlated equilibrium (Aumann, 1974) is a profile of strategies chosen by a mediator: the mediator draws a joint recommendation from a known distribution, tells each player only their own component, and no player can lower their expected cost by systematically deviating from what they are told. Correlated equilibria contain the Nash equilibria, are…
Promotion Optimization for Multiple Items in Supermarkets: Under Additively Separable Cross-Item Effects, All Higher-Order Promotion Contributions Vanish and App(2) = App(N)Research Paper
Supermarkets run temporary price promotions on a large share of their assortment, and the choice of which item to discount, by how much and in which week is a recurring planning decision for category managers. Promotions on one item change the sales of the others: a discount on one brand of coffee draws customers away from a competing brand (substitution),…
The Discrete Moment Problem with Nonconvex Shape Constraints: Optimal Extreme Point Solutions of the Log-Concave Discrete Moment Problem Are Piecewise Geometric with at Most m PiecesResearch Paper
A discrete moment problem asks for the largest expected payoff compatible with prescribed moments of an unknown probability distribution. A decision maker may know the first few moments of demand or loss while the full distribution remains uncertain. The optimization then asks which compatible distribution makes a chosen payoff largest. Chen, He, Jiang,…
The Value and Cost of Crop Minimum Support Price: Farmer and Consumer Welfare and Implementation Cost: Net Benefit and Net Social Value of a Credit-Based MSP under Market UncertaintyResearch Paper
A minimum support price (MSP) guarantees farmers a unit sale price at least as high as an announced floor. It can protect farmers when the market price is low, but the same guarantee can require a government payment and can change how much crop is produced. Policy evaluation therefore needs to account for farmers, consumers, and public expenditure together.…
A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation: Projected TD(0) Under Markov Chain Sampling Converges at Mixing-Time-Scaled RatesResearch Paper
Temporal-difference (TD) learning is the basic algorithm of reinforcement learning for estimating the value function of a fixed policy from a single stream of experience. With a linear function approximationVθ(s)=ϕ(s)⊤θ, TD(0) is the evaluation step inside many policy-iteration and actor–critic methods, and its behaviour governs how much…
Net-Metered Distributed Renewable Energy: A Peril for Utilities?: DRE Raises a Utility's Expected Profit if and only if Its Existing Resources Are Small and the Wholesale Price Is Sensitive EnoughResearch Paper
Electricity end-users increasingly generate their own power with rooftop solar panels and small wind turbines. This distributed renewable energy (DRE) is usually sold under net metering: a customer who produces less than it consumes buys the shortfall from its utility at the retail price, and a customer who produces more sells the surplus back to the…
The Role of Participation in Innovation Contests: Multiple Rewards Are Optimal Exactly When Entry Is Costly, the Budget Is Large and a Failed Contest Is CostlyResearch Paper
An innovation contest asks people outside a firm to submit solutions and promises payments according to the rank of their submissions. The firm would like a strong best submission, but a potential solver must decide whether entering is worth a fixed cost before knowing who else will enter. Paying only the winner can encourage effort while leaving the…
Strong Algorithms for the Ordinal Matroid Secretary Problem: Every Algorithm with Forbidden Sets of Size k Is α(k) Probability-CompetitiveResearch Paper
The secretary problem asks an online decision maker to pick the best of n candidates who arrive in uniformly random order, deciding irrevocably on each one at arrival. Its matroid generalization, the matroid secretary problem (MSP) of Babaioff, Immorlica and Kleinberg (SODA 2007), asks the algorithm to select an independent set of a matroid whose elements…
A Rationale for Imperfect Reporting Standards: With a Low Payoff Threshold and a High Prior, a Conservative Report Beats a Perfectly Informative OneResearch Paper
Financial reports help investors value a firm, but a firm can also learn and voluntarily disclose information outside the report. A regulator who makes mandatory reports more precise changes the firm's incentive to acquire that other information. Friedman, Hughes and Michaeli's 2020 preprint, Proposition 1, studies whether a reporting rule that is less…
The Beneficial Effects of Ad Blockers: Both Platforms Allowing Ad Blockers Is an Equilibrium That Beats a World Without Ad Blockers for Low β and High γ/βResearch Paper
Ad blockers remove advertising from web pages, and with it the revenue that pays for free content. By the time of this paper a large share of desktop users ran one, and publishers had three responses at hand: tolerate ad blockers, block access to users who run one (an adblock wall), or move behind a paywall. The common view was that ad blockers can only…
Information Inundation on Platforms and Implications: Under Unknown Post Accuracy, Screening for the Largest Expected Variance Reduction Selects the Post Closest to the BeliefResearch Paper
Private Sequential Learning: The Query Complexity of an (ϵ, δ, L)-Private Learner Lies Between max{log(1/ϵ), log(δ/ϵ) + 2L − 4} and log(1/(Lϵ)) + 2LResearch Paper
A learner wants to locate an unknown number, the true valuev∗∈[0,1), by asking threshold questions of a database: each queryq is answered by the single bit I(v∗≥q). Bisection finds v∗ to within ϵ/2 with ⌈log2(1/ϵ)⌉ queries, and no strategy does better (Waeber, Frazier and Henderson, 2013). Bisection, however,…
On the Fair Division of a Random Object: The Bottom-Heavy Rule Dominates Every Other Symmetric Almost Prior-Independent Rule for Bads Satisfying Fair ShareResearch Paper
Many allocation problems divide an object whose value to the participants is uncertain at the time the division rule is designed: computing time on a shared cluster, a recurring chore, the cost of a service used jointly. If the rule must be fixed before the realizations are known, and must treat everyone fairly in expectation, the designer faces a tradeoff…
Distributionally Robust Inverse Covariance Estimation: The Wasserstein Shrinkage Estimator: Without Sparsity Information the Robust Estimator Is a Closed-Form Shrinkage of the Sample EigenvaluesResearch Paper
The precision matrixX=Σ−1 of a Gaussian random vector ξ∈Rp encodes its conditional independence structure: Xij=0 exactly when ξi and ξj are independent given the other coordinates. Estimating it is a basic step in Gaussian graphical models, portfolio selection and linear discriminant analysis. The textbook estimator, the…
Platform Tokenization: Financing, Governance, and Moral Hazard: For Small Capacity Cost the Blockchain-Based Business Model Strictly Dominates the Traditional OneResearch Paper
Digital platforms (marketplaces, payment networks, sharing services) need large up-front investments in capacity before any revenue arrives, and their founders typically finance them by selling equity to venture capitalists. Since 2017 an alternative has been available: issuing a platform-specific cryptocurrency (a utility token) in an initial coin offering…