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.
Supply Risk Mitigation in a Decentralized Supply Chain: Pricing Postponement or Payment Postponement? II: Under Reliable Yield the Postponements Are Complements Only at Intermediate CostResearch Paper
A retailer that buys from a supplier with unreliable production has two contractual levers against supply risk, and both postpone a decision until after the yield is known. Payment postponement means paying only for the units actually delivered (pay-by-delivery) instead of the units ordered (pay-by-order). This moves the yield risk upstream. Pricing…
Human and Machine: The Impact of Machine Input on Decision-Making Under Cognitive Limitations II: Machine Input Never Lowers the Decision-Maker's Accuracy or Expected ValueResearch Paper
Machine-learning systems are increasingly placed beside human experts — physicians reading scans, loan officers screening applications, judges assessing risk — rather than replacing them. The machine processes the structured data it can see; the human also has access to information the algorithm cannot observe, but her attention is limited. Whether such a…
Supply Risk Mitigation in a Decentralized Supply Chain: Pricing Postponement or Payment Postponement? I: As Cost Rises the Retailer Prefers Payment, Then Pricing, Then Both, Then Pricing PostponementResearch Paper
When a supplier's production is subject to random yield, only part of a planned production run turns into usable output. A retailer sourcing from such a supplier bears the resulting shortage risk unless the contract or the selling strategy moves it elsewhere. Random yield is a classical topic in production planning (Yano and Lee, 1995), and postponing a…
Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low III: ℓ2-Regularized Best Subset Selection Satisfies Slow-Rate and Fast-Rate Oracle InequalitiesResearch Paper
Best subset selection fits a linear model using at most k of p available predictors, choosing the k that minimize the residual sum of squares. Mixed-integer optimization made it computable at moderate scale (Bertsimas, King & Mazumder, 2016), which reopened the statistical question of when it should be used. Empirical comparisons (Hastie, Tibshirani &…
Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low I: The Discrete First-Order Algorithm Is a Descent Method Whose Successive Steps Shrink at Rate O(1/M)Research Paper
Best subset selection fits a linear model y≈Xβ using at most k of the p available features: it minimizes the residual sum of squares subject to the sparsity constraint∥β∥0≤k, where ∥β∥0 counts the nonzero coordinates of β. Mazumder, Radchenko and Dedieu (arXiv:1708.03288v4; Operations Research, 2023) show that best subsets…
Human and Machine: The Impact of Machine Input on Decision-Making Under Cognitive Limitations I: The Rationally Inattentive Decision-Maker's Optimal Choice Probability in Closed FormResearch Paper
A person using a machine's advice may decide more accurately, but attention is costly. Before asking what a machine changes, the baseline decision has to be understood: how often would the person choose the action associated with a good state without machine input? Boyacı, Canyakmaz, and de Véricourt study this question in a model of a decision maker who…
A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games 3: The Price of Anarchy Is Locally Lipschitz at Games with Constant Costs or Strictly Increasing C¹ CostsResearch Paper
The price of anarchy (PoA) of a nonatomic congestion game is the ratio of the total cost of a Wardrop equilibrium to the minimum total cost. Worst-case bounds on it over whole classes of cost functions are classical (Roughgarden and Tardos, 2002; Correa, Schulz and Stier-Moses, 2004). In practice the demands and cost functions of a traffic model are…
A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games 2: The Social Optimum Cost, the Wardrop Equilibrium Cost and the Price of Anarchy Are Continuous on the Game SpaceResearch Paper
Traffic users choose routes for themselves, while a planner may choose routes that minimize everyone's combined travel cost. The price of anarchy measures the cost of the users' equilibrium relative to the planner's optimum. Travel demand and arc latency functions are estimated from data and change over time, so a ratio that changes abruptly under a small…
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness 5: For Two Agents, Every Equilibrium of an Always-EFX Mechanism Is α-MMS for Some α > 2/3Research Paper
Dividing indivisible goods fairly among agents is a basic problem of fair division. Most of the
literature assumes that the agents' valuations are known to the algorithm. In practice the
algorithm only sees what the agents report, and an agent may misreport to get a better bundle.
For allocation without money, truthful mechanisms are very restricted: for…
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness 4: For Two Agents and Four Goods, Every Equilibrium of an Always-EFX Mechanism Is MMSResearch Paper
Dividing indivisible goods fairly is a central problem of computational social choice. With additive valuations, the fairness notions of interest are relaxations of envy-freeness, since exact envy-freeness is often impossible with indivisible items. The strongest relaxation in common use is envy-freeness up to any good (EFX) (Caragiannis et al., 2019); a…
Linear Programming and Community Detection 6: The LP Relaxation Fails w.h.p. in the Very Dense and Dense SBM Above Explicit ThresholdsResearch Paper
Community detection asks for a hidden partition of the nodes of a graph from its edges. Its simplest probabilistic benchmark is the two-community stochastic block model (SBM), in which the minimum bisection problem is the maximum a posteriori estimator. That problem is NP-hard, so convex relaxations are used in its place, and the question is when a…
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness 2: Round-Robin Has a Pure Nash Equilibrium in Every Instance with Additive ValuationsResearch Paper
Fair division of indivisible goods asks how to split a set of items among agents with different values so that nobody has strong grounds to complain. Algorithms with fairness guarantees, such as Round-Robin, which always produces an allocation that is envy-free up to one good (EF1) when agents report their true additive valuations (Caragiannis et al., 2019),…
Linear Programming and Community Detection 5: The LP Relaxation Recovers the Planted Bisection w.h.p. in the Very Dense SBM When p − q > 1/2Research Paper
The stochastic block model (SBM), introduced by Holland, Laskey and Leinhardt (1983), is the standard random model for networks with community structure, and the basic benchmark for community-detection algorithms (Abbe 2018). In its two-community form the nodes are split into two equal halves, edges inside a half appear with probability p, and edges across…
Load Balancing Under Strict Compatibility Constraints 3: Inhomogeneous Random Graphs with Edge Probabilities Satisfying (3.5) Are Almost Surely Proportionally Sparse and SubcriticalResearch Paper
Large-scale computing systems route incoming tasks to servers through dispatchers, one per task type. A task can only run on a server that holds the data or software it needs, so the set of admissible pairs forms a bipartite compatibility graph between task types and servers. Full flexibility (every server can serve every type) gives the best load balancing…
Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization 2: ZO-RSGD Has Average Expected Squared Riemannian Gradient Norm at Most 4L(f(x₀) − f(x*))/(N+1) + 2μ²L²(d+6)³ + 16(d+4)σ²/mResearch Paper
Many optimization problems are posed over a manifold rather than a vector space: orthogonality constraints (the Stiefel manifold), unit-norm constraints (the sphere), fixed-rank matrices. In some of them the objective can only be evaluated, not differentiated. Black-box adversarial attacks on a neural network with a norm-constrained perturbation,…
Selection and Ordering Policies for Hiring Pipelines via Linear Programming 4: For Every τ ∈ (0, 1) Some τ-Bounded Instance Gives No Value-Ordered Policy More Than (β^τ_k + ε) Times the OptimumResearch Paper
A firm with k open positions often cannot interview and offer sequentially: hiring seasons are short, and offers go out in one batch. Some recipients decline, so the firm overbooks, sending more offers than it has positions, and pays for every hire beyond capacity. The same trade-off appears in airline and hotel overbooking and in university admissions.…
Lightning Network Economics: Channels III: The Minimal Cost of a Symmetric Bidirectional Channel Is 3(2Bλ/r)^{1/3} − B/6 + O(r^{1/3}) as r → 0Research Paper
Payment channels let two parties make repeated transfers while using an on-chain transaction only when a channel needs resetting. They require funds to be committed in advance. The economic choice is therefore between the transaction fees saved by using a channel and the opportunity cost of funds tied up in it. Guasoni, Huberman, and Shikhelman give a…
Climate Impact Investing 2: With Poisson Climate Uncertainty λ, If the Green Portfolio Is Green Then y*_λ Rises to 1 in λ, So Equilibrium Emissions Rise as Uncertainty GrowsResearch Paper
Climate impact investing refers to investors who tilt their portfolios away from companies with large greenhouse-gas emissions. Its stated aim goes beyond aligning portfolios with values: by raising the cost of capital of polluting companies, it is meant to change what those companies do. De Angelis, Tankov and Zerbib (SSRN 3562534, published in Management…
Integer Factorization: Why Two-Item Joint Replenishment Is Hard 2: For Odd Composite M, Every Optimal Plan of an Explicit Two-Item Periodic JRP Instance Has q₂ = M and 1 < gcd(q₁, M) < MResearch Paper
The joint replenishment problem (JRP) is a basic model of inventory coordination: several items are ordered from one supplier, each item pays its own ordering and holding costs, and an additional item-independent joint ordering cost rewards ordering the items at common times. Two accounting conventions are studied. In the periodic JRP (also called the…
Linear Programming and Community Detection 3: The Metric LP Relaxation Recovers the Planted Bisection When d_in − d_out ≥ n/4 Under Regular SandwichingResearch Paper
The minimum bisection problem asks, for a graph G=(V,E) on an even number n of vertices, for a split of V into two halves of size n/2 that cuts as few edges as possible. It is NP-hard, and it is also the maximum a posteriori estimator for the two-community stochastic block model, the standard random model of networks with community structure. A tractable…
Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization 1: ZO-RGD Has Average Expected Squared Riemannian Gradient Norm at Most 8(d+4)L(f(x₀) − f(x*))/(N+1) + 8(d+4)L·C(μ)Research Paper
Many optimization problems in statistics and machine learning constrain the variable to a smooth manifold: orthonormal frames in sparse PCA and dictionary learning (the Stiefel manifold), unit vectors in phase retrieval (the sphere), fixed-rank matrices in matrix completion. Riemannian optimization handles these problems directly on the manifold. A step is…
Accelerability vs. Scalability: R&D Investment Under Financial Constraints and Competition II: Unconstrained R&D Race: Best Responses Rise on Accelerable Projects and a Symmetric Equilibrium ExistsResearch Paper
Two firms developing competing innovations face a decision that a single firm does not: a rival's discovery can end the value of continuing the project. If the first discovery wins the payoff, each firm chooses how much to spend per period while knowing that greater spending may change both its payoff on success and its speed of discovery. The investment…
Designing Approximately Optimal Search on Matching Platforms 1: Some Stationary Equilibrium of Directed Search Attains a Quarter of the First-Best WelfareResearch Paper
Two-sided platforms for dating, freelancing and housing do more than list participants: they decide whom each participant is shown. When search is costly and agents leave the market over time, the platform's choice of assortments (which types of agents meet which, and how often) determines who matches, and agents respond strategically by deciding which…
Online Advertising, Data Sharing, and Consumer Control 3: Under Topics-Style Category Tracking Both Advertisers Bid on ADX1 Exactly When the Inaccuracy τ Is Below an Explicit Threshold τ̃ > 1Research Paper
Online display advertising is sold through ad exchanges, and much of its value comes from targeting: showing an ad to consumers known to be interested in the advertised product. For two decades the main tracking technology was the third-party cookie, under which an exchange can follow a consumer only after an advertiser agrees to share the data from its own…
Sharing Sequentially Triggered Losses: Automated Conflict Resolution Through Smart Contracts 3: The Midpoint Fixed-Fraction Rule Is the Shapley Value and the Nucleolus of the Liability GameResearch Paper
When one breached contract forces the next party to breach its own contract, a single failure travels down a loss chain: agent 1 (the initiator) causes a loss ℓ1 to agent 2, which can then no longer honour its agreement with agent 3 and causes it a loss ℓ2, and so on until agent n causes a loss ℓn to a final victim. Gudmundsson, Hougaard and Ko (…