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.
Dynamic Fair Resource Division: The Optimal Fairness Ratio of d-Uniform Control Vectors Is 1/((d+1)·ln((d+1)/d)), Attained by the Frugally Fair AlgorithmResearch Paper
Shared computing infrastructure — a data-centre cluster, a cloud platform's memory — is divided among users who arrive over time. Two requirements pull against each other. Proportional fairness asks that, when t users are present, each holds at least a 1/t fraction of the resource. Limited disruption asks that the system not take resource away from running…
Costly Interpretation of Asset Prices: With Costly Price Interpretation There Is a Unique Linear Financial Market Equilibrium, and Its Price Carries Endogenous NoiseResearch Paper
A central question of financial economics is how much of the information dispersed among traders ends up in market prices. The workhorse model is the noisy rational expectations equilibrium (REE): investors with private signals trade a risky asset, the price aggregates their information, and each investor learns from the price as well as from her own signal…
Stochastic Knapsack Revisited: The Service Level Perspective: Anticipative Policies Need at Most 2Δ More Capacity Than Adaptive Policies to Meet Type-I Service LevelsResearch Paper
A central planner holds a single pool of Q units of a product and must supply N customers whose demands d~1,…,d~N are random. Each customer i asks to be fully served, i.e. to receive her entire demand, with probability at least a target αi. This Type-I service level (the persistency value of the stochastic knapsack) is the standard…
Risk Guarantees for End-to-End Prediction and Optimization Processes: The Excess Squared-Loss Risk Bounds the Squared Excess Optimality-Gap Risk, Scaled by the Squared Diameter of the Feasible SetResearch Paper
Many operational decisions are optimization problems whose cost vector is unknown when the decision is made but can be predicted from observed features: shortest paths under predicted travel times, portfolios under predicted returns, production plans under predicted prices. The common practice, predict-then-optimize, first fits a regression model g mapping…
Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time: A Maximal Minimum k-Partition's First Part Is the Source-Maximal Minimum (S, T)-Terminal Cut for Some |S| = 2k − 2Research Paper
The hypergraph k-cut problem asks for a least-cost way to split the vertices of a hypergraph into k nonempty groups. An edge of a hypergraph may contain more than two vertices, so the graph version does not capture the behavior of every input. For fixed k, randomized polynomial-time algorithms for hypergraph k-cut were known before the deterministic result…
Mechanism Design for Managing Hidden Rebates and Inflated Quotes of a Procurement Service Provider: Paying a Fee Equal to the Hidden Rebate Is the Optimal Truthful Contract for Small RebatesResearch Paper
Retailers that source apparel and other consumer goods from contract manufacturers in developing countries often work through a procurement service provider, an intermediary that solicits quotes, negotiates and manages production on the retailer's behalf. A documented problem in this industry is the hidden rebate: some manufacturers pay the intermediary a…
Optimal Price/Advertising Menus for Two-Sided Media Platforms: In Duopoly with Multi-Item Menus the Unique Equilibrium Is a Symmetric Two-Item Menu on Which Both Consumer Types Multi-HomeResearch Paper
Ad-supported media and digital services (streaming music and video, news sites, social platforms) sell to two sides at once. Consumers value the content, advertisers value the consumers' attention, and consumers usually regard advertising as a nuisance whose cost differs from one person to the next. Many such platforms answer this with menu pricing: a free…
Pricing of Debt and Equity in a Financial Network with Comonotonic Endowments: Closed-Form Default Probabilities and Expected Wealth, Debt Payments and Equity under Bankruptcy CostsResearch Paper
Banks hold claims on one another. When one bank cannot pay, its creditors receive less, which can push them into default in turn. Clearing models compute the payments and wealths that are consistent across the whole network. Regulators and researchers use them to measure systemic risk and to price interbank debt. The basic model is that of Eisenberg and Noe…
Market Efficient Portfolios in a Systemic Economy: f-Efficient Bank Holdings Exist, Attain Mean Squared Deviation (bᵀv)²/(1ᵀG⁻¹1), and Are Unique if and only if There Are Exactly Two BanksResearch Paper
When banks are hit by losses they sell assets to restore their leverage targets, and these fire sales depress prices for every other holder of the same assets. The resulting deviation of market capitalization from its fundamental value is a systemic externality: it depends not on any single bank's portfolio but on how the stock of each asset is distributed…
A General Framework to Compare Announcement Accuracy: Static vs. LES-Based Announcement: The Static Announcement Has No Larger MSE if and only if the Correlation Is at Most 1/2Research Paper
A customer who is told that service will be delayed can use the announced wait to decide whether to stay, leave, or plan around the delay. A service operator needs to know whether a changing, customer-specific announcement actually predicts the eventual wait more accurately than a fixed announcement. Bassamboo and Ibrahim studied this question for the last-e…
Multiregional Oligopoly with Capacity Constraints: The Capacity-Constrained Cournot Game Has a Unique Equilibrium, Implementing the Unique Fixed Point of the Marginal-Profit Best ResponseResearch Paper
Firms that serve several geographic markets must decide both how much to produce and where to sell it. A capacity limit couples those regional decisions: an extra unit sent to one region cannot also be sent to another. Different transport costs and demand curves make a collection of independent single-region Cournot models inadequate. Alsabah, Bernard,…
Adversarial Patrolling in a Uniform: Attacking in the Second Period of the Patroller's Absence and Never Staying at a Location Are Optimal Strategies for Every Attack DurationResearch Paper
A visible patroller gives an attacker information: the attacker can observe when a location is vacant and wait for a favorable moment. This changes the patrolling problem from choosing how often to visit each location to choosing a movement rule that remains effective against an adversary who chooses the attack time. The preprint The Uniformed Patroller Game…
Maximizing Sequence-Submodular Functions and Its Application to Online Advertising: Any α-Greedy Sequence Achieves 1 − 1/e^α of the Optimum of a Non-Decreasing Sequence-Submodular FunctionResearch Paper
Many allocation problems in online advertising are decisions about order, not only about membership. A search engine that rewrites an incoming query into one of several ad-matching configurations, or a publisher that runs a sequence of ad allocations over a day, extracts revenue that depends on which configurations are used and on the order in which they…
“Now or Later?” When to Deploy Qualification Screening in Open-Bid Auction for Re-Sourcing: The Incumbent's Optimal Drop-Out Price Is a Compete-or-Fold Threshold RuleResearch Paper
Firms that already buy a service from an incumbent supplier regularly re-source the contract: they invite new suppliers, the entrants, to compete in a descending open-bid auction. Entrants may be cheaper but are unproven: before the contract can be awarded to an entrant, the buyer must pay for qualification screening (visits to the supplier's facility,…
Co-Opetition in Service Clusters with Waiting-Area Entertainment: With an Even Cost Split, Co-Opetition Is at Least as Profitable as Local Monopoly iff Price Competition Is Below a ThresholdResearch Paper
Restaurants, clinics and amusement venues that announce a waiting-time standard compete not only on price but on how unpleasant the wait feels. Waiting-area entertainment (a piano player, a television, a play area) lowers the perceived cost of waiting, and when several providers sit in one service cluster, a food court, a mall, a strip of restaurants, a…
Financial Intermediation Chains in an Over-the-Counter Market: For Search Costs Below the Threshold c*, There Is a Unique Steady-State Equilibrium with an Intermediary SectorResearch Paper
Many financial assets (corporate and municipal bonds, swaps, asset-backed securities) trade over the counter (OTC): there is no central exchange, and a trade requires that a buyer and a seller find each other. Empirically, a large share of OTC volume passes through intermediation chains, in which an asset moves from the original seller to the final buyer…
Optimal Patrol of a Perimeter: Optimal Randomized Patrol Schedule and Value of the Patrol Game Against an Observing AttackerResearch Paper
Patrolling protects a border or facility perimeter against an intruder who needs uninterrupted time to complete an attack. The defender controls when patrollers pass; the attacker controls when to strike. In a patrol game, the question is how to time patrols when the attacker can observe them (Lin, Optimal Patrol of a Perimeter).
Timing It Right: Balancing Inpatient Congestion vs. Readmission Risk at Discharge: Discharge a Patient Type Only After Every Strongly Dominating Type of No Shorter StayResearch Paper
Every day a hospital ward with a fixed number of beds decides which patients go home. Sending a patient home early frees a bed for the next admission, which matters when the ward is congested and arrivals board in the emergency department or elective surgeries are cancelled. Sending a patient home too early raises the chance that the patient is readmitted,…
Approximate Parametric Computation of Minimum-Cost Flows with Convex Costs: Linear Splines of the Marginal Costs with Bounded Step Sizes Give an (α, β)-Approximate Minimum-Cost Flow FunctionResearch Paper
Flow networks model the movement of material, traffic, electricity, or gas through connected systems. In many such models, the required net flow at each vertex varies with a parameter, so the object of interest is a whole family of optimal flows rather than one solution. When edge costs are nonlinear, solving a new optimization problem for every parameter…
Managing Social Responsibility in Multitier Supply Chains: The Buyer's Optimal Strategy Is Control, Delegation or No Effort, Decided by Thresholds in the Loss-Adjusted Effort CostsResearch Paper
A buyer can face public and financial losses when a remote supplier violates labor, safety, or environmental standards, even if the buyer did not cause the violation directly. The buyer and an intermediate supplier can spend resources to help the remote supplier reduce this risk. Their incentives depend on who pays for the effort and who bears the loss when…
Optimal Management of Evolving Hierarchies: Full Transfers to Immediate Predecessors Form the Unique Decentralized Socially Optimal Allocation SchemeResearch Paper
Some organizations grow by asking each member to recruit a successor. The incentive facing a member depends on where the revenue generated by later members goes. A transfer rule may reward the recruiter, keep the revenue with the entrant, or divide it among several predecessors. Hougaard, Moreno-Ternero, and Østerdal ask which fixed rule gives the greatest…
Optimal Short-Termism: The No-Underinvestment and No-Overhang Problems Have the Same Solutions, so Committing to Unlevered Long-Term Effort Rules Out Excessive Short-TermismResearch Paper
Managers are often accused of short-termism: boosting current cash flow at the expense of long-run firm value. Hackbarth, Rivera and Wong (Management Science, 2022; working paper SSRN 3060869) study short-termism inside a dynamic-agency model of a levered firm. A risk-averse manager exerts two unobservable efforts: long-term efforta, which raises the…
Contracting, Pricing, and Data Collection Under the AI Flywheel Effect: Under Moral Hazard the Firm Collects More (Less) Data Than First Best When the Data Impact Increases (Decreases)Research Paper
Companies often sell a machine-learning product before its model has reached its final quality. Use of the product then yields data that can improve later versions. This feedback is the AI flywheel studied by Gurkan and de Véricourt. A firm may hire a specialist to develop the model, but the specialist's effort is costly and hidden. More customer data can…
Optimal Team Composition: Diversity to Foster Implicit Team Incentives: The Specialized–Diverse Wage Gap Falls Until Collusion Binds, Then Rises, and Diverse Teams Are Optimal Below S*(δ)Research Paper
Firms decide not only how to pay workers but whom to put together. A long empirical and theoretical literature on teams asks whether homogeneous ("specialized") or heterogeneous ("diverse") teams perform better. Most arguments for diversity are informational: diverse teams bring different knowledge or perspectives. Glover and Kim (SSRN 3344922, published in …
“Un”Fair Machine Learning Algorithms: With Endogenous Learning Effort, Equal Treatment Accepts a Larger Share of the Protected Group's Good Candidates than Equal Opportunity in a Risky MarketResearch Paper
Lenders, employers and insurers increasingly screen applicants with learned scores, and regulators and the fair machine learning literature ask that such screening be fair across demographic groups. Two notions are standard. Equal treatment (ET) asks that the same decision rule be applied to everyone, regardless of group; the paper notes that it is what the…