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.
Opinion Dynamics on Directed Complex Networks 3: On a Galton-Watson Limit, the Stationary Opinion with Memory Has Variance at Most That of the Proportional No-Memory RecursionResearch Paper
Linear opinion models describe how individuals in a social network revise their views by averaging what their neighbours think, what external media tell them, and what they themselves believed a moment ago. The last ingredient, an autoregressive or memory term, appears in the Friedkin–Johnsen family of models and in its stochastic variants. Fraiman, Lin and…
Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes III: Bipartite, Unit-Patience Side: Rounding Then Probing by Weight Earns ≥ (1 − 1/e)·Σ w_e p_e y_eResearch Paper
Stochastic matching with patience models kidney exchange, online dating and labour platforms: every edge of a graph is present only with some probability, the only way to learn whether it is present is to probe it, and a probed edge that turns out to be present must be added to the matching. Each vertex v also has a patiencetv, a limit on how many of its…
Pigeonhole Design: Balancing Sequential Experiments from an Online Matching Perspective 3: For p ≥ 2 Continuous Covariates, Expected Discrepancy O(T^(1−φ) + T^((p−1)φ)), with (log T)^(3/2) at p = 2Research Paper
Online platforms run randomized experiments on subjects (users, sessions, orders) that arrive one at a time and must be assigned to a control or a treatment group on arrival, before later subjects are seen. The precision of a treatment-effect estimate depends on how similar the two groups are in their observed covariates. When the groups are badly balanced,…
Optimal No-regret Learning in Repeated First-price Auctions 2: The ML-IS-UCB Bidding Policy Achieves Expected Regret at Most C√T log³ T for Every Oblivious Private-Value SequenceResearch Paper
Display advertising has been moving from second-price to first-price auctions: several exchanges began rolling them out in 2017, and Google Ad Manager completed its move at the end of 2019 (Davies 2019). In a second-price auction bidding one's value is a dominant strategy; in a first-price auction the optimal bid depends on the distribution of the competing…
Lightning Network Economics: Topology II: A Lightning Network with Average Degree Above 2g₊⁻¹(2·disc) Contains a Hermetizable SetResearch Paper
The Lightning Network (LN) is a layer-two payment system for Bitcoin. Two parties open a payment channel by locking funds on the blockchain and can then pay each other off-chain; payments between parties without a common channel are routed along paths of channels. Locking funds is costly, and the amount a channel needs grows with the net flow it has to…
Contextual Inverse Optimization: Offline and Online Learning 2: The Greedy Circumcenter Policy Can Incur Regret Linear in the Horizon from a Pointed Knowledge SetResearch Paper
In inverse optimization, an observer sees decisions made by an expert who solves an optimization problem, and wants to recover the expert's unknown objective. Besbes, Fonseca and Lobel study a contextual version: in each period a feasible set and a context function are revealed, a learner must act before seeing the expert's choice, and then observes the…
Contextual Inverse Optimization: Offline and Online Learning 4: The Polyhedral Cone of η-Separated Effective Differences Has Uncertainty Angle at Most arccos(η^(d−1)/d^(3/2))Research Paper
In contextual inverse optimization a decision-maker repeatedly faces linear problems minx∈Xtft(x)′c⋆ whose cost vector c⋆∈Sd is unknown. After each period it observes an action that an expert who knows c⋆ would have taken. Every observation is a set of linear inequalities on c⋆, so the costs consistent with the data…
Deterministic Budget-Feasible Clock Auctions I: Iterative-Pruning Is a Budget-Feasible 4.75-Approximation for Monotone Submodular ValuationsResearch Paper
In a budget-feasible procurement auction a buyer with a hard budget B acquires services from strategic sellers. Each seller i has a private cost ci, and the buyer values a set S of hired sellers at v(S). The auction must keep total payments within B and make truthful behaviour optimal for every seller, while hiring a set whose value is close to the best…
Human in the Loop Automation: Ride-Hailing with Remote (Tele-)Drivers 3: In a Large Supply-Limited Market, Choosing the Number of Remote Drivers Raises Service Level by a Factor of at Least 2 − αResearch Paper
Autonomous vehicles that cannot yet drive every trip on their own can be supervised or driven by remote (tele-)drivers who sit in a control center and take over a vehicle only while it serves a customer. Because a remote driver is not tied to one vehicle, a platform may operate more vehicles than drivers. Benjaafar, Wang and Yang ask when this decoupling…
On the Robustness of Second-Price Auctions in Prior-Independent Mechanism Design II: Against Exchangeable Affiliated Valuations the Minimax Regret Equals the I.I.D. ValueResearch Paper
A seller offers one indivisible item to n buyers but does not know the joint distribution of their valuations. The seller knows only that every valuation lies in [0,1]. Prior-independent mechanism design asks for a selling mechanism that performs well against every distribution in a class. One measure of performance is the regret: the expected gap between…
Human in the Loop Automation: Ride-Hailing with Remote (Tele-)Drivers 2: With Ample Vehicles, Service Level Strictly Increases in the Number of Drivers, with an Explicit Lower BoundResearch Paper
Remote driving, or tele-driving, lets a human operator in a control center drive a vehicle over a wireless link. A ride-hailing platform that adopts it decouples drivers from vehicles: a driver is attached to a vehicle only while that vehicle carries or fetches a customer, and is released the moment the trip ends. Since an idle vehicle needs no driver, the…
Source Theory: A Tractable and Positive Ambiguity Theory 4: Two Sources Are Equally Preferred and Insensitive If and Only If Both Are Uniform with Equal Source FunctionsResearch Paper
Decision makers facing uncertainty treat different sources of uncertainty differently. The Ellsberg paradox, home bias in investment, and the competence effect all show people preferring bets on one source (a known urn, domestic stocks, a familiar domain) over equally likely bets on another. Ambiguity theories try to describe these differences. Most of them…
Source Theory: A Tractable and Positive Ambiguity Theory 3: A Source Is More Insensitive Than Another If and Only If the Pmatcher Between Them Is InsensitiveResearch Paper
Decision makers facing uncertainty do not treat all events alike. Beyond liking or disliking ambiguity (the Ellsberg paradox, the home bias, the competence effect), people show insensitivity: a lack of discriminatory power that makes them overweight unlikely and underweight likely events, more so when they understand the uncertainty less. For risk this is…
Monetary Easing, Leveraged Payouts, and Lack of Investment II: There Is a Shock-Size Threshold Above Which the Optimal Date-0 Rate Stays at R and Below Which It Is CutResearch Paper
Low interest rates are meant to stimulate investment, yet periods of monetary easing have coincided with weak corporate investment and large debt-financed share buybacks and dividends. Acharya and Plantin (SSRN 3484935; Management Science, 2025, doi:10.1287/mnsc.2022.01440) explain this with a moral-hazard channel: when the market rate r falls below the…
Source Theory: A Tractable and Positive Ambiguity Theory 2: A Source Is Preferred to Another If and Only If the Pmatcher Between Them Is DislikedResearch Paper
Decisions under uncertainty rarely come with known probabilities. Since Ellsberg's (1961) urn experiments it has been documented that people prefer betting on events whose likelihood they understand — a known urn, a familiar domestic stock, a domain they feel competent in — over events of an unfamiliar source of uncertainty, even when they judge the events…
Scores for Multivariate Distributions and Level Sets I: The L² Scoring Rules S and S′ Are Proper, With Divergence the h-Weighted L² Distance Between f_X ∗ w and f_Y ∗ wResearch Paper
A probabilistic forecast issues a whole distribution PX for an uncertain quantity Y∈Rd rather than a single number: wind and wave heights at several sites, demand for several products, the joint returns of several assets. Forecasts of this kind are compared and estimated with a scoring ruleS(PX,y), a number assigned to the forecast once the…
Lambda Value-at-Risk under Ambiguity and Risk Sharing II: The Inf-Convolution of ΛVaRs under Continuous Capacities Is Induced by a Family of Downsets, and Is Itself a ΛVaR When Every Λ IncreasesResearch Paper
Risk sharing asks how a total loss X should be split among n agents, each of whom evaluates its share with its own risk measure, so that the sum of their assessments is as small as possible. The smallest achievable sum is the inf-convolution of the agents' risk measures, and an allocation that attains it is an optimal allocation. For Value-at-Risk, the risk…
Optimal No-regret Learning in Repeated First-price Auctions 1: With IID Private Values a Bidding Policy Achieves Expected Regret at Most C√T log^2.5 TResearch Paper
Most display advertising is sold in first-price auctions: the highest bidder wins and pays its own bid. Since the industry's move away from second-price formats around 2019, a bidder can no longer bid its value and must instead learn how much to shade its bid, from data about how the other bidders behave. A demand-side platform faces this problem millions…
Retailer-Led Marketplaces 3: An Ad Valorem Fee Dominates a Per-Unit Fee, So the Monopolist Charges No Per-Unit FeeResearch Paper
Large online retailers such as Amazon, Walmart and JD.com run a retailer-led marketplace: they sell products on their own account and, on the same storefront, host independent third-party sellers whose sales they tax. How the platform charges those sellers is a live question for competition authorities and for the platforms themselves. Real marketplaces…
The (Surprising) Sample Optimality of Greedy Procedures for Large-Scale Ranking and Selection 4: The Greedy-Phase Budget of the Explore-First Greedy Procedure Decays Exponentially in n0Research Paper
Ranking and selection (R&S) asks which of k simulated alternatives has the largest mean when each observation is noisy and the simulation budget is fixed. Large-scale problems, with thousands or millions of alternatives, arise in simulation optimization run on parallel computers, and for them the relevant question is how the total budget B must grow with k.…
Endogenous Multihoming and Network Effects: PlayStation, Xbox, or Both? II: Under Partial Multihoming, Network Effects Raise the Price iff e < 2(t − μ) and the Profit iff e < e_πResearch Paper
Many network goods are bought in more than one variety at once. Gamers own both a PlayStation and an Xbox, households subscribe to several streaming services, and users keep accounts on competing social networks. A consumer who multihomes pays twice but enjoys the exclusive content of both products and the network of both user bases. Much of the literature…
Contextual Inverse Optimization: Offline and Online Learning 1: The Circumcenter Policy Has Offline Worst-Case Regret at Most sin α(C(D)), or 1 When α(C(D)) ≥ π/2, and No Policy Does BetterResearch Paper
Inverse optimization asks for the objective of an optimization problem when only its optimal decisions are observed. It was formalized for linear programs by Ahuja and Orlin (Operations Research 2001) and has since been used to infer costs, preferences and utilities from observed choices, for instance in routing, pricing and the imitation of expert planners…
Deterministic Budget-Feasible Clock Auctions III: A Deterministic Clock Auction Achieves an O(log n / log log n)-Approximation for Subadditive ValuationsResearch Paper
A budget-feasible procurement auction buys services from strategic sellers under a hard budget. Each of n bidders can provide a service at a private cost; the auctioneer values each set of acquired services through a set function v and must keep total payments within a budget B. The question, introduced by Singer (FOCS 2010), is how much of the optimal…
Acquihiring for Monopsony Power 2: With Nash Bargaining and Poaching After a Failed Bid, the Acquirer Hires Directly Above v̄_a, Acquihires Between v̲_a and v̄_a, and Does Not Hire Below v̲_aResearch Paper
Large technology firms often buy small startups less for their products than for their staff: the product is shut down and the employees move to the acquirer. This practice, called acquihiring, has drawn the attention of competition authorities because it can be a way to buy labour-market power rather than to create value. Bar-Isaac, Johnson and Nocke (CRC…
Auditing with a Chance of Whistleblowing: Increasing Whistleblowing Intensity Lowers Equilibrium Audit Quality If and Only If the Enforcer's Incentive Exceeds r* and the Auditor's Is Below d*Research Paper
Many accounting frauds have come to light through whistleblowers rather than through audits, and regulators now run programs to encourage tips: since the Dodd–Frank Act of 2010 the U.S. Securities and Exchange Commission pays awards for original information that leads to a successful enforcement action. Empirically, whistleblower involvement is associated…