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.
Tokenomics: When Tokens Beat Equity IV: Under Moral Hazard Every Equity-Financeable Venture Is Token-Financeable and Every Token-Financeable One Is Debt-Financeable, Both StrictlyResearch Paper
Start-ups that build a platform or a digital service increasingly raise their set-up capital by pre-selling tokens: claims on the future output of the service, redeemable once it exists. Between 2017 and 2019 such token offerings raised billions of dollars, and corporate finance asked whether a token is anything more than a disguised equity or debt claim.…
Tokenomics: When Tokens Beat Equity III: The Break-Even Token Pre-Sale Strictly Increases in the Set-Up Cost and the Marginal Cost and Strictly Decreases in Expected DemandResearch Paper
Firms can raise money before production by selling claims on future output. In the model of Malinova and Park, these claims are tokens: a buyer prepays for a quantity of the good, and the final contract also gives token holders a share of tokens issued after demand becomes known. The firm must choose how many tokens to pre-sell. A larger pre-sale brings in…
Nonstationary Reinforcement Learning: The Blessing of (More) Optimism II: Per-Step Dynamic Regret of SWUCRL2-CW When the Widened Confidence Region Contains an MDP of Diameter at Most DResearch Paper
A reinforcement-learning agent chooses actions while learning how those actions affect future states. In a stationary model, observations collected long ago remain relevant to the current transition law. In a nonstationary Markov decision process, rewards and transition probabilities may change at each round. Old observations can then bias an estimate even…
Nonstationary Reinforcement Learning: The Blessing of (More) Optimism I: No Policy Earns More Than the Sum of Per-Step Optimal Gains Plus 4(D_max+1)√((B_r+2D_max B_p)T)Research Paper
Reinforcement learning in a changing environment needs a benchmark that remains meaningful when the transition law and rewards vary from round to round. For a stationary Markov decision process (MDP), the optimal long-run average reward is a standard benchmark. In a nonstationary MDP, summing those stationary optima across rounds is convenient, but it need…
Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems 6: Under LIFO Issuance with m ≥ 2 and S^NP > D̲ > 0 the Best Base-Stock Policy Is Not Asymptotically Optimal as θ → ∞Research Paper
Blood platelets, fresh produce and many pharmaceuticals have a fixed lifetime: a unit not used within m periods of its arrival must be discarded. Optimal ordering for such products depends on the whole age profile of the stock, and the dynamic program that describes it has an (m−1)-dimensional state. It is intractable beyond small m (Nahmias, 1982;…
Personalized Pricing and Distribution Strategies I: With Positively Correlated Valuations and a Uniform Manufacturer Price, Dual Distribution Is Optimal Under Either Retailer Pricing PolicyResearch Paper
A manufacturer that already sells directly to consumers may also supply an independent retailer. Adding the retailer can reach consumers who prefer its service, but the two channels then compete for some of the same buyers. A wholesale price affects both the retailer's ability to serve consumers and its retail pricing. The manufacturer's choice of…
Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems 7: With Backlogging and Positive Lead Times a Simple Base-Stock Policy Is Asymptotically Optimal in m, n and θResearch Paper
Blood platelets, fresh produce, dairy and many pharmaceuticals have a fixed shelf life: a unit that is not used within m periods of its arrival must be discarded. Managing such products is a classical problem of inventory theory (Nahmias 1982, Operations Research 30(4), doi:10.1287/opre.30.4.680). The optimal ordering policy depends on the entire age…
Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems 4: Under FIFO Issuance the Heuristic Base-Stock Policy Is Asymptotically Optimal as the Unit Outdating Cost GrowsResearch Paper
Blood platelets, fresh produce, bakery items and many pharmaceuticals have a fixed lifetime: a unit that is not used within m periods of arrival must be discarded. Replenishing such a product is a classical problem of inventory theory (Nahmias 1982), and its optimal policy depends on the whole age profile of the stock, so it cannot be computed for realistic…
The Voice of Customers in Customization III: Under O-Learning, No Separating Equilibrium Exists When θH/θL < ΛResearch Paper
When customers request a customized product, their requests can reveal information about what they value. A seller can use that information when setting a price, while a customer can choose a request with the resulting price in mind. The question is whether customers with different preferences can make different requests in equilibrium. Liang Guo's The…
Social Media and News: Content Bundling and News Quality I: Unilateral Content Bundling Lowers Publisher Profit and Raises News Quality and Consumer Surplus iff c < c†Research Paper
News publishers depend on direct visits for advertising revenue, while social platforms can show publishers' content inside their own feeds. That arrangement can move reading time from the publisher's site to the platform without changing how much news a consumer reads. It can therefore change the publisher's return from improving content quality. De…
Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems 5: Under LIFO Issuance a Simple Base-Stock Policy Has Gap ≤ 3θE[(S^NP−D)⁺]/(2m) and Is Asymptotically Optimal in p and θResearch Paper
Blood platelets, fresh food and many pharmaceuticals have a fixed lifetime: a unit that has not been used within m periods of its arrival must be discarded. A retailer of such a product faces the usual trade-off between leftover stock and lost sales, plus the cost of discarding outdated units. The issuance policy, the order in which units of different ages…
Information Design for Congested Social Services: Optimal Need-Based Persuasion 2: With Only Low-Need Users, Full Information Is Within a Factor of the Optimal Signaling MechanismResearch Paper
Social services such as public housing, food banks and free clinics are congested: the users who arrive wait in a queue they cannot see, and some of them could do almost as well elsewhere. A provider who sees the queue can decide what to tell arriving users about it. Telling low-need users that the queue is long sends them to their outside option and…
Information Design for Congested Social Services: Optimal Need-Based Persuasion 4: Signaling Achieves the First-Best Admission Policy for All Welfare Weights Above a ThresholdResearch Paper
Social services such as public health clinics, legal aid offices and food banks are congested: users wait in a queue whose length they cannot see. Some users have no alternative (high need) and others have an outside option (low need). A provider cannot price access, but can decide what to tell arriving users about the queue. Anunrojwong, Iyer and Manshadi…
Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems 2: Under FIFO Issuance the Heuristic Base-Stock Policy's Optimality Gap Decays Exponentially in Demand Population SizeResearch Paper
Perishable products (blood platelets, fresh food, pharmaceuticals) have a fixed lifetime: units not sold within m periods expire and are discarded. Managing such inventory well is a classical problem in operations research, going back to Nahmias (1975). The difficulty is that the state of the system is the whole age profile of the stock, so the optimal…
Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems 3: Under FIFO Issuance the Heuristic Base-Stock Policy Is Asymptotically Optimal as the Unit Penalty Cost GrowsResearch Paper
Perishable products, among them fresh food, blood platelets and pharmaceuticals, lose their value after a fixed number of periods. Their inventory control has been studied since the 1970s (Nahmias, Perishable inventory theory: a review, Operations Research 1982). The optimal policy of the standard lost-sales model depends on the whole age profile of the…
Information Design for Congested Social Services: Optimal Need-Based Persuasion 1: Every Pareto-Efficient Signaling Mechanism Has a Threshold Structure at or Below the Full-Information ThresholdResearch Paper
Many social services are rationed by waiting rather than by price: public health clinics, food banks, shelters, legal aid. Users who need the service most often have no outside option, while users with less need could be served elsewhere but join the queue anyway and lengthen everyone's wait. The provider usually cannot force anyone to leave, and charging…
A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based on the Augmented Lagrangian 1: NAPP-AL Drives the Best Stationarity Residual to Zero at Rate o(1/√k)Research Paper
Many models in statistics, machine learning and engineering are nonconvex, nonsmooth and coupled by constraints: a sparsity penalty such as SCAD, MCP or capped-ℓ1 on one block of variables, a smooth loss coupling the blocks, and a nonlinear equality constraint tying them together. Augmented-Lagrangian methods and ADMM-type splittings are the workhorses…
On-Demand Delivery from Stores: Dynamic Dispatching and Routing with Random Demand I: The Approximation APT Bounds the Expected Cost-to-Go from Below and Above and Is Exact in the Last PeriodResearch Paper
Retailers and restaurants increasingly deliver orders from their own stores within an hour or less. Orders arrive throughout the day, a fixed pool of drivers is based at the store, and in each dispatch wave the operator must decide how many drivers to send out now and along which routes. Sending many drivers now gives short delivery times for the current…
Right to Repair: Pricing, Welfare, and Environmental Implications: The Manufacturer's Optimal New-Product and Repair Prices and the Resulting No-, Partial- or Full-Repair Equilibrium (Table 1)Research Paper
Repair access changes more than the cost of fixing a broken product. It also changes how many used products reach a resale market, what those products sell for, and whether a manufacturer prefers to sell another new unit or earn a repair margin. Jin, Yang, and Zhu study these connected pricing decisions in a two-period durable-goods model in Right to…
Courier Dispatch in On-Demand Delivery I: With Exogenous Demand, Dedicated Delivery Has the Shorter Wait Exactly Below One Threshold in Demand Rate and in Service RadiusResearch Paper
On-demand delivery platforms for meals and groceries promise delivery within minutes, and the main operational lever they control is how a courier is dispatched. A courier can carry each order as soon as it is ready (dedicated delivery), or wait until two orders are available and deliver them in one trip (batch delivery). Batching saves travel per order but…
Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems 1: Under FIFO Issuance the Heuristic Base-Stock Policy's Optimality Gap Decays Exponentially in the Product LifetimeResearch Paper
Blood platelets, fresh produce, dairy and many pharmaceuticals have a fixed shelf life: a unit that has not been used within m periods of its arrival must be discarded. Managing such stock is a classical problem of inventory theory, going back to Nahmias (1975), and it remains of practical interest for hospital blood banks and grocery retail. The difficulty…
A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based on the Augmented Lagrangian 2: Under the VP-EB Error Bound, NAPP-AL Converges Linearly to a Stationary PointResearch Paper
Many problems in machine learning, signal processing and engineering design minimize a nonconvex, possibly nonsmooth objective subject to nonlinear equality constraints. Augmented Lagrangian methods are the standard tool for such constraints, but each classical iteration solves a hard nonconvex subproblem. Zhu, Zhao and Zhang (arXiv:2007.12219v1, published…
The Conceptual Flaws of Decentralized Automated Market Making: Constant Product Pricing Admits Profitable Front-Running and Multi-Venue ArbitrageResearch Paper
Decentralized exchanges on public blockchains do not match buyers with sellers through an order book. Most of them trade against a liquidity pool: a smart contract that holds reserves of two tokens and quotes a price by a fixed formula. The most widely used formula is the constant product rule of Uniswap (Adams, Zinsmeister and Robinson, 2020), under which…
Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low IV: ℓ1-Regularized Best Subset Selection Satisfies Slow-Rate and Fast-Rate Oracle InequalitiesResearch Paper
Best subset selection fits a linear predictor using at most k of p available columns. Its explicit limit on the number of selected variables makes the model easy to interpret, but the search can still fit noise: among many subsets of the same size, one can align unusually well with a noisy response. Mazumder, Radchenko and Dedieu study this effect in Subset…
Supply Risk Mitigation in a Decentralized Supply Chain: Pricing Postponement or Payment Postponement? III: When Payment Postponement Helps or Hurts the Retailer, the Supplier and the ConsumersResearch Paper
A retailer can pay a supplier when it places an order or after the supplier delivers it. When production yield is uncertain, the choice changes who bears the cost of missing units. It can also change the supplier's production decision and, through the amount available for sale, the surplus received by consumers. Geng, Guo, Xiao and Yang study these effects…