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.
Percolation Games: in i.i.d. oriented percolation games the n-stage value converges almost surely to a constant, with sub-Gaussian deviations at rate (lnn/n)1/2Research Paper
Percolation games were introduced by Garnier and Ziliotto (arXiv:2110.12227, published in Mathematics of Operations Research, 2022) as discrete toy models for the stochastic homogenization of non-convex Hamilton–Jacobi equations. In homogenization one asks whether a control or game problem in a random, spatially varying environment behaves, over long…
Fair Exploration via Axiomatic Bargaining: PF-UCB Attains the Nash Social Welfare Upper Bound Y*(I) in Every Grouped K-Armed BanditResearch Paper
Many learning systems serve several populations at once: a recommender serves user segments, a clinical dosing rule serves patient subgroups, an online marketplace serves customer types. When these populations share the same unknown options, the exploration one population performs also informs the others. A policy that minimizes total regret decides who…
Scarcity of Ideas and Optimal R&D Policy: When the Arrival Rate of Ideas Is Unknown, the Optimal Reward Increases to v/r With Delay While Social Welfare DecreasesResearch Paper
Prizes and patents reward the first innovator to fill a market niche. How generous the reward should be depends on how often useful ideas arrive, and a policy maker rarely knows that rate. Basov, Erkal, Minehart and Scotchmer (SSRN 4628270, 2024; published in Management Science, doi:10.1287/mnsc.2023.03362) model ideas as scarce: they arrive at the times of…
A Policy Gradient Algorithm for the Risk-Sensitive Exponential Cost MDP: The Trajectory-Based Algorithm Drives the Truncated and Untruncated Cost Gradients to Zero Almost SurelyResearch Paper
The risk-sensitive exponential cost of a Markov chain replaces the long-run average of the one-step cost by the exponential growth rate of the expected exponential of the accumulated cost. It penalizes rare sample paths with high cost, and it goes back to Howard and Matheson (1972). For a finite chain the growth rate is the logarithm of a Perron eigenvalue (…
Random Perfect Information Games: The Distribution Function of the Value Is the Smallest Fixed Point of the Value Generating FunctionResearch Paper
The extinction probability of a branching process is the smallest fixed point of its offspring generating function, a classical result in the theory of branching processes (Athreya and Ney, 1972). Flesch, Predtetchinski and Suomala (arXiv:2104.10528) ask what becomes of this fact when the tree is contested. Two players choose the path through a random tree,…
Reducing Bias in Event Time Simulations via Measure Changes: the exponential density has unit mean and tilts every point-process intensity by u (corrected: sequential independence)Research Paper
Event timing models describe when defaults, insurance claims or component failures occur. Each event i arrives at the first time its integrated hazard Hti=∫0thsids crosses an independent exponential threshold, and the hazard rates may depend on the history of all events (contagion). Expectations E(f(N)) of path functionals of the event…
Necessary and Sufficient Conditions for Rank-One-Generated Cones: Two LMIs Are ROG iff a Nonzero Combination of M1,M2 Is PSD or M1=Sym(ac⊤), M2=Sym(bc⊤)Research Paper
A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic constraints. Binary integer programs, max-cut, and many robust and polynomial optimization problems can be written this way. Any QCQP has a lifted form in which the vector variable x is replaced by the matrix X=xx⊤; dropping the rank constraint on X…
How to De-Reserve Reserves: Admissions to Technical Colleges in India: DA-BT is the unique individually rational, meritocratic, non-wasteful, open-first and incentive-compatible mechanismResearch Paper
Admissions to the Indian Institutes of Technology and other centrally funded technical institutions run through a single clearinghouse that allocates tens of thousands of seats each year. Seats at each program are reserved for members of the Scheduled Castes (SC), Scheduled Tribes (ST) and Other Backward Classes (OBC); the rest are open-category seats…
A Class of Recursive Optimal Stopping Problems with Applications to Stock Trading: The Recursive Value Is the Unique Fixed Point in Ad and the First Contact Time Is OptimalResearch Paper
In a classical optimal stopping problem the reward collected at the stopping time is a fixed function of the state. Many decisions do not have this shape: an agent may commit to an uncertain option whose outcome is revealed only after a random delay, and if it fails the agent is back where it started and must decide again. The reward of committing then…
Sharing Demand Information with Retailer Under Upstream Competition: substitutability thresholds for manufacturers' information sharing, with the exact condition on a2/σResearch Paper
In many consumer-goods channels the party with the best demand information is the manufacturer, which controls promotion, product launches and brand planning, while the retailer places the order. Whether manufacturers should tell retailers what they know is a question of practice as well as theory, and the answer depends on how the manufacturers compete.…
Direct Trade Sourcing Strategies for Specialty Coffee: specialized, mixed or diversified sourcing is optimal exactly when marginal revenue at QL and QH is below or above marginal costResearch Paper
Specialty coffee roasters buy single-origin beans through direct trade: they contract acreage with a grower before harvest and take the crop that passes the quality specification. A single-origin label (SL) sells at a premium to a small connoisseur segment, while a blend label (BL) has a much larger market. Beans bought for SL can always be sold as BL, a…
Is Full Price the Full Story When Consumers Have Time and Budget Constraints?: Gig Workers Are Full-Price Decision-Makers Whose Value of Time Equals Their WageResearch Paper
Since Naor's 1969 model of queue joining, the literature on pricing congestible services has assumed that a customer judges a time-consuming service by its full price: the money price r plus a constant multiple η of the time commitment δ, r+ηδ. Revenue-maximizing and welfare-maximizing prices for queues, priority schemes and capacity choices…
Regulation with Experimentation: Ex Ante Approval, Ex Post Withdrawal, and Liability: the optimal mix is first best iff the externality is at most a critical level, else liability-free and lenientResearch Paper
New drugs, medical devices and patented technologies reach the market only after a phase of costly testing, and they can be withdrawn later when evidence of harm accumulates. Societies control this process with three instruments: an approval standard (how strong the evidence must be before adoption), a withdrawal standard (how bad the evidence must become…
Dynamic Programming Principles for Mean-Field Controls with Learning: the IQ function satisfies the Bellman equation on the lifted space of state distributions and local policiesResearch Paper
Mean-field control (MFC) models a large population of identical, cooperating agents through a single representative agent whose transitions and rewards depend on the distribution of the whole population. It is the limit of cooperative N-agent problems as N→∞, and it is used for systems such as ride-sharing fleets, resource allocation and equilibrium…
Impact of Network Structure on New Service Pricing: Balanced Networks Share One Optimal Policy and Revenue, the Lowest Among All Networks of the Same Average DegreeResearch Paper
Many online services (social platforms, question-and-answer sites, collaboration tools) become more valuable to a user the more that user's contacts use them. A firm launching such a service commonly offers it for free at first, to let usage grow through these local network effects, and starts charging later. Alizamir, Chen, Kim and Manshadi (SSRN 3236225;…
Technical Note—On Hiring Secretaries with Stochastic Departures: An Optimal Policy Depends Only on Time and Number of Arrivals, Monotone in the Number and, for Uniform Arrivals, in TimeResearch Paper
In the classical secretary problem a known number n of candidates is interviewed in uniformly random order, and each candidate must be accepted or rejected on the spot; the goal is to hire the best one. Its optimal rule (reject the first ≈n/e candidates, then accept the first one better than all before) and its success probability ≈1/e are…
Equilibria Existence in Bayesian Games: Climbing the Countable Borel Equivalence Relation Hierarchy: Every Hyperfinite Purely Atomic Bayesian Game Has a Harsányi ε-Equilibrium for Every ε > 0Research Paper
In a game of incomplete information each player learns a private type and then acts. Two equilibrium notions coexist. A Bayesian (interim) equilibrium asks every type of every player to best-respond given its beliefs. A Harsányi (ex ante) equilibrium asks each player to choose a strategy for all of their types at once that is optimal on average under their…
A General Framework for Learning Mean-Field Games: GMF-V reaches the stationary mean-field equilibrium within C₀ε with probability 1 − 2δ, with an explicit sample-complexity boundResearch Paper
Mean-field games (MFGs) approximate stochastic games with many identical, interchangeable players by a single representative player who interacts with the distribution of the population (Huang, Malhamé, Caines 2006; Lasry, Lions 2007). In applications such as online ad auctions the reward and the dynamics are not known in closed form, and the equilibrium…
Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression: the general arc-flow model has the same integer optimum and LP bound as Gilmore–GomoryResearch Paper
The cutting stock problem and the bin packing problem ask for the fewest rolls (or bins) of a fixed capacity from which given numbers of items of several sizes can be cut (or into which they can be packed). They are among the oldest integer programs in operations research, and exact solvers for them and for their multi-dimensional variants (vector packing,…
Fair Allocation of Vaccines, Ventilators and Antiviral Treatments: Leaving No Ethical Value Behind in Health Care Rationing: Characterization by deferred acceptanceResearch Paper
Allocating scarce vaccines, ventilators, or antiviral treatments can involve several ethical priorities at once. A reserve system attaches a quota to each category and gives that category its own ordering of eligible patients. Categories can express different claims on the same supply without making the medical units physically different. The mathematical…
Always Valid Inference: Continuous Monitoring of A/B Tests: First-order efficiency of mixture sequential probability ratio testsResearch Paper
An A/B experiment collects observations while a user decides whether the evidence
is strong enough to act. A user may inspect the experiment repeatedly and stop
when a result looks convincing. A test calibrated only for one sample size does
not automatically retain its error guarantee under that behavior. A
sequential test instead makes the stopping…
Exact Simulation of Stochastic Volatility and Other Affine Jump Diffusion Processes: Exact Heston simulation and unbiased derivative pricingResearch Paper
A Monte Carlo price estimate averages discounted payoffs over simulated scenarios. Its statistical error can be assessed from the variation of those payoffs. When a continuous-time stochastic model is replaced by a finite time grid, a second error enters: the simulated distribution differs from the model distribution. Increasing the number of scenarios does…
Robust Dynamic Pricing with Demand Learning in the Presence of Outlier Customers: Adaptive regret with general inventoryResearch Paper
A retailer must learn demand while selling a fixed stock over a finite season. A high price preserves inventory but may leave profitable sales unrealized. A low price can exhaust stock before later customers arrive. Learning is harder when some customers behave unlike the population whose demand the retailer wants to learn. Those customers can arrive in a…
Inventory Balancing with Online Learning: The General IBOL Performance GuaranteeResearch Paper
An online platform must allocate resources before it knows which customers will arrive later. Advertising budgets, limited product inventories and workers' task opportunities can all be exhausted by early decisions. When the probabilities of a successful allocation are also unknown, a platform must learn from the same interactions that consume its scarce…
Optimal Stopping and Free-Boundary Problems VI: Uniqueness of the American Put BoundaryTextbook
An American put option gives its holder the right to sell an asset for a fixed strike price before a specified maturity. Exercising produces an immediate payoff, while waiting preserves the possibility of receiving a larger payoff later. The pricing problem therefore includes a decision about when to stop. In the geometric Brownian model without dividends,…