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.
Selling Data to Marketers 2: In Selling Data Appends with Costs Below the Prior Mean, the High-Cost Plan Is Efficient and the Low-Cost Plan Carries Less Information If φ < 1/2 and More If φ > 1/2Research Paper
Data brokers sell information about consumers to firms that decide whom to target: a lender deciding whom to offer credit, a retailer deciding whom to mail. Two products dominate this market. A marketing list sells contact information together with an analysis, so that a firm cannot reach the consumer at all without buying. A data append adds information…
Third-Degree Price Discrimination in Two-Sided Markets: Seller-Side Discrimination Raises Platform Profit, Buyer and Low-Type Seller Surplus and Total Welfare; High-Type Sellers Gain iff b > b̂Research Paper
Third-degree price discrimination means charging different prices to identifiable groups of customers. Its welfare effects are a classical question in industrial organization. With linear demands and every market served under uniform pricing, discrimination leaves total output unchanged and lowers total welfare (Pigou 1920). More generally, welfare can rise…
Flow Allocation Games 1: Every Unit-Ranking Game Has a Strong Equilibrium That Maximizes the Total FlowResearch Paper
Financial firms owe each other money. When some firms cannot meet their obligations, the payments that actually clear in the network are a fixed point: what a firm can pay depends on what it receives, which depends on what others can pay. Eisenberg and Noe (Management Science, 2001) introduced this clearing model under a fixed pro-rata payment rule. Later…
Reducing Marketplace Interference Bias Via Shadow Prices 2: In Expectation the Shadow-Price Estimator Equals the Derivative of the Finite-Sample Partial-Treatment Value FunctionResearch Paper
Two-sided platforms (ride hailing, delivery, freight, cloud capacity) test product changes with user-split experiments: each arriving demand unit is assigned to treatment with probability ρ and to control otherwise. Treated and control units then compete for the same supply, so the outcome of one group depends on the size of the other. This interference b…
Revenue Sharing at Music Streaming Platforms II: The Core of the Streaming Game Is the Set of Allocations Splitting Each User's Payment Among the Artists That User PlayedResearch Paper
Music streaming platforms collect a subscription fee from each user and have to pass the revenue on to the artists whose content was played. The two rules used in practice are pro-rata (each artist is paid in proportion to their total number of streams, over all users) and user-centric (each user's fee is split among the artists that user played, in…
Global Sensitivity Analysis via Optimal Transport 1: An OT-Based Sensitivity Measure Is Maximal Exactly When the Output Is a Function of the InputResearch Paper
Global sensitivity analysis asks how much of the uncertainty in the output Y of a model, a simulator or a learned predictor is attributable to an input X. A standard way to answer is to compare the law of Y with its law after X is revealed, and to average that discrepancy over X. Variance-based indices (Sobol' 1993; Wagner 1995) compare conditional and…
Coopetition in Platform-Based Retailing: On the Platform’s Entry I: The Seller Prefers Entry Exactly Above Thresholds in Spillover and Referral Rate and Outside a Band of Competition IntensityResearch Paper
Large online marketplaces such as Amazon, JD.com and Walmart.com act both as a sales channel for third-party sellers and as a retailer of their own. A platform watches which third-party products sell well and may start selling the same product itself, a move called platform entry. Over ten months of 2013–2014, Amazon entered about 3% of the products first…
Simple and Explicit Bounds for Multiserver Queues with 1/(1−ρ) Scaling: With More Than 2.5 Finite Service Moments, GI/GI/n Steady-State Queue Tails and Delay Probability Obey Explicit BoundsResearch Paper
Multi-server queues model call centres, hospital wards, cloud server pools and any system in which n identical servers work through one first-come-first-served (FCFS) line. Capacity planning for such systems needs bounds on the steady-state queue length and on the probability of delay (the chance that an arriving job finds every server busy) that are…
Optimality Conditions in Control Problems with Random State Constraints in Probabilistic or Almost Sure Form II: Explicit Optimality Conditions for Probabilistic Elliptic PDE State ConstraintsResearch Paper
Optimal control of partial differential equations under uncertainty arises whenever a physical system is steered by a control while its sources, coefficients or loads are only known in distribution. A typical requirement is a state constraint: the state (a temperature, a concentration, a displacement) must stay below a threshold everywhere in the domain.…
Selling Data to Marketers 1: In Selling Marketing Lists, the Low-Cost Plan Is Efficient and the High-Cost Plan Carries More Information Than the Benchmark If φ < 1/2 and Less If φ > 1/2Research Paper
Data brokers such as Acxiom, Nielsen and Oracle, and data generators such as Google and Facebook, sell processed consumer data to firms that use it to decide whom to target, whom to lend to, or which market to enter. The U.S. Federal Trade Commission's 2014 report on data brokers distinguishes two products: a marketing list, which carries contact…
Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria 2: For Submodular Valuations the Bluff Profile Is a Tight 1/2-Approximate Pure Nash Equilibrium of Round-RobinResearch Paper
Dividing indivisible goods among agents without money is a basic problem of fair division. The most widely used procedure is Round-Robin: the agents take turns, in a fixed order, picking their favourite remaining good. For agents with additive valuations, Round-Robin run on the agents' true preferences produces an allocation that is envy-free up to one good…
The Value of Information Design in Supply Chain Management III: With Overlapping Supports, the Optimal Policy Goes from Partial to No to Full Disclosure as the Critical Ratio RisesResearch Paper
A retailer often knows more about her own demand than the supplier who must produce for her. In a decentralized supply chain the supplier sets a production quantity before demand is realized, and an under-informed supplier produces too little or too much. The retailer can shape what the supplier believes by committing in advance to a disclosure policy, a…
Revenue Sharing at Music Streaming Platforms I: Homogeneity and Additivity Characterize Weighted Indices; Adding Equal Individual or Global Impact of Users Gives Pro-Rata or User-CentricResearch Paper
Music streaming platforms collect a subscription fee from each user and pay part of the revenue to the artists whose content was played. The industry standard is the pro-rata method: the revenue pool is divided in proportion to each artist's total number of streams across all users. A competing method, the user-centric method, divides each user's own…
Multitask Learning and Bandits via Robust Statistics: High-Probability ℓ1 Error Bound for the Robust Multitask (Trimmed Mean + LASSO) Estimator under Sparse HeterogeneityResearch Paper
Service providers such as hospitals or retail stores each fit a predictive model on their own data, and many of them have few observations. The models of different providers are usually similar but not identical: most coefficients agree, while each provider deviates from the common model in a few features of its own. Multitask learning asks how data from…
Retention or Acquisition? Behavior-Based Quality Disclosure I: Retention-Focused Disclosure Thresholds and Higher Second-Period Profits under Behavior-Based DisclosureResearch Paper
Firms that hold purchase-history data can treat past customers and a rival's customers differently. The economics of behavior-based pricing (BBP), charging different prices to the two groups, is well developed: in a symmetric duopoly, poaching the rival's customers with discounts intensifies competition and usually lowers profits (Fudenberg and Tirole 2000; …
Thompson Sampling with Information Relaxation Penalties II: The IRS Performance Bounds Are Monotone, W^TS ≥ W^IRS.FH ≥ W^IRS.V-Zero and W^TS ≥ W^IRS.V-EMaxResearch Paper
In a Bayesian multi-armed bandit a decision maker pulls one of K arms in each of T periods, observes the reward, and updates a prior belief about each arm's unknown parameter. The best achievable expected total reward, V∗(T,y), is the value of a dynamic program over beliefs, and for all but the smallest instances it cannot be computed. Upper bounds on V∗…
Achieving Efficiency in Black-Box Simulation of Distribution Tails with Self-Structuring Importance Samplers: The Self-Structuring Importance Sampler Is Logarithmically EfficientResearch Paper
Many operational risk questions ask for a small probability pu=P(L(X)≥u): the chance that the cost L of a decision, evaluated at a random scenario X∈Rd, exceeds a large threshold u. Examples are large delays in project networks or vehicle routing, large portfolio credit losses, and failures in engineered systems. Plain Monte Carlo needs on…
Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria 1: For Cancelable Valuations the Bluff Profile Is an Exact Pure Nash Equilibrium of Round-RobinResearch Paper
Round-Robin is the simplest allocation procedure for indivisible goods: agents take turns, in a fixed order, and at each turn the active agent takes her favourite good among those still available. Run on truthful preferences with additive valuations it returns an allocation that is envy-free up to one good (EF1), which is why it is the default baseline of…
Self-Preferencing and Search Neutrality in Online Retail Platforms I: Under a Low Commission, Search Neutrality Strictly Reduces Consumer Surplus When the Two Products Are Similarly PopularResearch Paper
Large retail platforms both host independent sellers and sell their own products, and they control the order in which products appear in search results. When the platform ranks its own product first regardless of relevance, it engages in self-preferencing. Regulators have treated this as a competition problem: the European Commission opened a second…
Self-Preferencing and Search Neutrality in Online Retail Platforms II: At Equal Popularity, a Commission Below ρL/ρH Makes Search Neutrality Lower Consumer Surplus and Raise the Third-Party ProfitResearch Paper
Large retail platforms such as Amazon both host independent sellers and sell their own products in competition with them. The platform also controls the search ranking, the order in which products are shown to a consumer. The European Commission and the US Federal Trade Commission have examined whether platforms rank their own products ahead of rivals' (self…
Asset Pricing with Costly Short Sales 1: The Lending Agent Charges Half the Pessimist's Frictionless Sharpe Ratio, and Lending Is Active Exactly When Her Net Sharpe Ratio Is NegativeResearch Paper
To sell a stock short, an investor must first borrow it, and the owner who lends it charges a lending fee. Securities lending is a large market, and the fee varies across stocks: D'Avolio (2002) documents that shorting costs are positively related to the dispersion of investors' beliefs. Short-sale constraints have a long history in asset pricing (Miller…
Coordinating Inventory Control and Pricing Strategies for Perishable Products 2: With Zero Lead Time and Minimal Disposal, Two Myopic Solutions Bound the Optimal Order-Up-To LevelResearch Paper
Food, blood products, pharmaceuticals and many retail goods are perishable: a unit is usable for a fixed number of periods and is then discarded. A seller of such a product decides every period how much to order, what price to charge, and how much stock to deplete or dispose of. Because units of different ages coexist, the state of the system is a vector of…
The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation: Error Bound for Least-Squares Policy Iteration with LookaheadResearch Paper
Approximate policy iteration is the template behind most practical reinforcement-learning systems for large state spaces: alternate between choosing a policy that looks good under the current value estimate and estimating the value of that policy, with errors in both steps. Game-playing systems such as AlphaZero add two ingredients to this template: a…
The Continuous-Time Joint Replenishment Problem: ϵ-Optimal Policies via Pairwise Alignment: Ψ-Pairwise Alignment Yields a Replenishment Policy Within Factor 1 + 5ϵ of Any PolicyResearch Paper
The joint replenishment problem is a basic model of coordinated inventory control. A firm stocks n commodities, each of which follows its own Economic Order Quantity (EOQ) model, but every order also incurs a joint ordering costK0, regardless of which commodities it contains. Ordering commodities together therefore saves money, and the question is how to…
Corruption-Robust Exploration in Episodic Reinforcement Learning II: Uniformly Action-Eliminating Algorithms Suffer Expected Regret at Least K/8 for K ≤ A^H/4Research Paper
In stochastic multi-armed bandits, a robust way to explore is action elimination: keep confidence intervals for every arm, discard an arm once its upper confidence bound falls below another arm's lower confidence bound, and sample uniformly among the arms that survive. Uniform sampling is what makes the first corruption-robust bandit algorithm work (Lykouris…