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.
Optimal Budget Aggregation with Star-Shaped Preference Domains: With Leontief Utilities, the Nash Product Rule Is the Only Continuous Group-Strategyproof Mechanism Satisfying Core Fair ShareResearch Paper
In budget aggregation, a group has to split a fixed public budget among several projects, and each member proposes her own ideal split. A rule is needed to turn the proposals into one split. The question was studied for ℓ1 preferences by Freeman, Pennock, Peters and Wortman Vaughan (2021), who asked whether strategyproofness, efficiency and…
Shapley–Snow Kernels, Multiparameter Eigenvalue Problems, and Stochastic Games: Every Discounted Value Is a Rank-Drop Root of a Kernel-Reduced Pencil, Algebraic of Degree at Most Its RankResearch Paper
Zero-sum stochastic games model two opponents who interact over a finite set of states, each state being a matrix game whose outcome also decides the next state. Since Shapley (1953), every such game with discount factor λ∈(0,1] has a value vλk at each initial state k, characterised as the fixed point of a contraction. The value is the basic…
Accelerated MM Algorithms for Ranking Scores Inference from Comparison Data: Rescaled MM for Bradley–Terry MAP Estimation Contracts the Log-Posterior Gap at a Rate Set by Algebraic ConnectivityResearch Paper
Paired-comparison data (which of two items a user clicked, which of two players won a game, which of two products a respondent preferred) are summarised by ranking scores, one real number per item. The Bradley–Terry model (Bradley and Terry, 1952) is the standard statistical model for such scores, and its parameters are estimated by maximum likelihood or by…
Informing the Public About a Pandemic: Greater Economic Inequality Makes the Optimal Information Policy Exaggerate Less and Downplay MoreResearch Paper
During an epidemic a government knows more about the severity of the disease than the public, and what it chooses to say changes how many people stay at home. Isolation is cheap for some and expensive for others. A person who cannot work from home loses income, and people facing different costs answer the same message in different ways. de Véricourt, Gurkan…
That’s Not Fair: Tariff Structures for Electric Utilities with Rooftop Solar: A Tiered Solar-Discriminating Tariff Induces Any Target Adoption Outcome Without Cross-Subsidization When Customers GainResearch Paper
Rooftop solar changes both a household's electricity bill and the utility's cost of serving its customers. A tariff that encourages an aggregate amount of solar generation can still leave one customer tier paying more than before. Regulators therefore face a joint design question: can they induce a chosen adoption pattern while meeting the solar supplier's…
Essentiality Checks for Standard Essential Patents: Without an Effective FRAND Royalty Cap, a Marginal Increase in the Accuracy of Essentiality Checks Reduces WelfareResearch Paper
A standard-essential patent is a patent that an implementer must use to make a product compliant with a technical standard. Its owner may demand a royalty from firms using the standard. Whether a patent is truly essential can be disputed, yet licensing offers and investment decisions are made before a court resolves that dispute. Standard-setting…
A Unified Analysis of a Class of Proximal Bundle Methods for Solving Hybrid Convex Composite Optimization Problems: An Iteration-Complexity Bound for Every GPB VariantResearch Paper
Bundle methods minimize a convex objective while using local supporting affine functions to represent a component that may be nonsmooth. Their iterations can spend time improving the model without moving the current proximal center, so a bound on useful center changes alone does not bound the total work. Liang and Monteiro study a common generic proximal…
How Well do LLMs Compress Their Own Chain-of-Thought? A Token Complexity Approach: The Optimal Accuracy-Length Tradeoff Solves the Questions of Smallest Token Complexity FirstResearch Paper
Large language models answer reasoning questions better when they are allowed to write out a chain of thought (CoT) before the final answer, but every generated token costs time and money. A large body of recent work therefore asks models to "think less": prompts such as "be concise" or "use at most 10 words", and training methods that shorten the reasoning…
Optimal Accounting Rules, Private Benefits of Control, and Efficient Liquidation: The Optimal Accounting Rule Is a Threshold Rule, First-Best for Small Private BenefitsResearch Paper
An entrepreneur deciding whether to continue a project may value continued control even when liquidation would generate more cash. The project has a known liquidation value, but its final cash flow is uncertain. An accounting signal changes what the entrepreneur expects from continuation and can therefore change the decision. A regulator who cares about…
Improved Approximations for a CVRP with Unsplittable Demands: The Cheaper of a Matching-Plus-Tank Solution and a Tank-Split TSP Tour Is an (α + 1.75)-ApproximationResearch Paper
Capacitated vehicle routing asks how to serve clients from a depot with vehicles that can carry only a limited load. In the unsplittable version, one vehicle must deliver each client's entire demand. This makes the choice of routes interact with bin packing: a short tour can fail because its total demand exceeds the vehicle's capacity. Approximation…
Carbon Offsetting with Eco-Conscious Consumers: Cheaper Carbon Offsets Can Lead the Firm to Cut Its Controllable Emissions, under Both Negatively and Positively Correlated PreferencesResearch Paper
Firms that disclose a product carbon footprint can lower it in two ways: by cutting the emissions they control (better materials, cleaner processes), which costs money up front, or by buying carbon offsets from a third party at a constant price per tonne. Offsets have become cheap and widely available, and the business press has repeatedly argued that…
Dynamic Risked Equilibrium: Every Multistage Risk-Trading Equilibrium Solves the Social Planning Complementarity ProblemResearch Paper
Electricity systems with hydro storage, and many other resource systems, are operated over time under uncertain inflows. In a centrally planned system a single risk-averse planner chooses releases and storage to minimize a nested (time-consistent) coherent risk measure of total cost. In a deregulated system the same decisions are taken by many agents, each…
Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms: The Optimal Central-Privacy Mechanism Sets Privacy Losses to the Minimizer of a Virtual-Cost ProgramResearch Paper
Platforms that estimate a population quantity from individual data, such as a health service estimating the mean response to a treatment, must compensate users for the privacy they give up. Users differ in how much they value privacy, and that value is private information. Differential privacy (Dwork, McSherry, Nissim, Smith, 2006) supplies a quantitative…
Asset Trade, Real Investment, and a Tilting Financial Transaction Tax: When Information Is Valuable Enough, the Smallest Tax That Rules Out the Liquid Pooling Equilibrium Is the Optimal FTTResearch Paper
A financial transaction tax (FTT) charges a fixed fraction of the value of each securities trade. The idea goes back to Keynes (1936) and to Tobin's proposal of 1972, and it became policy after 2008: France (August 2012) and Italy (March 2013) introduced taxes on equity purchases, and the European Commission has proposed a common FTT (see the introduction…
Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number: For Every ε in (0, 1/2] a (1 − ε)-EFX Allocation Leaves at Most 64(n/ε)^(4/5) Goods UnallocatedResearch Paper
Dividing indivisible goods fairly is a central problem of fair division, with applications from inheritance and course allocation to the division of computing resources. Since envy-free allocations of indivisible goods need not exist (one good, two agents), the field studies relaxations. The most prominent is envy-freeness up to any good (EFX): no agent…
Data Tracking under Competition: In the Interior-Equilibrium Regime m < m_L, Data Tracking Raises Aggregate Consumer Surplus for Both Myopic and Forward-Looking ConsumersResearch Paper
Firms increasingly record what they learn about a customer in one transaction and use it to price the next one. Regulators treat this data tracking as a privacy problem; the consumer-protection question is whether consumers, as a group, lose from it. In a monopoly the answer is typically yes: the seller who learns a consumer's valuation extracts it.…
Data-Driven Mergers: When Data Trade Is Possible, a Merger Raises the Primary-Market Price and Lowers Consumer Surplus on Both Markets (Product-Improvement Model)Research Paper
A merger can give a firm access to data generated in a different market. Its effect on consumers depends on what the data do and whether firms could buy them before the merger. In Data-Driven Mergers, Alexandre de Cornière and Greg Taylor study a firm A whose customers generate data useful to two firms in a second market. Their product-improvement example…
Systemic Portfolio Diversification: With Two Heterogeneous Banks and Two Assets, Equilibrium Portfolios Raise the Probability That Some Bank Liquidates and Lower the Probability That Both DoResearch Paper
When a leveraged financial institution suffers a loss, a leverage constraint can force it to sell assets. If several institutions hold the same assets, their simultaneous sales depress prices and impose losses on everyone holding those assets. These fire-sale spillovers were a central amplification channel in the 2007–2009 financial crisis (Greenwood,…
Incomplete Information VCG Contracts for Common Agency: The Algorithmic IIVCG Contract Is Limited-Liability and Individually Rational Whenever Such an IIVCG Contract ExistsResearch Paper
In the principal–agent model a single agent takes a costly action on behalf of a principal who sees only the action's stochastic outcome, and pays the agent according to that outcome. Many practical relationships have one agent and several principals: a manager and the shareholders, a freelancer and several employers, a marketing agency that bids for ad…
Fair Cake Division Under Monotone Likelihood Ratios: BinSearch Computes a Contiguous Allocation That Is Envy-Free up to η in Time Polynomial in n, log λ and log(1/η)Research Paper
Cake cutting is the standard model of fair division for a divisible, heterogeneous resource: the cake [0,1] stands for time on a shared machine, a stretch of coastline, or bandwidth over a time window, and n agents value its parts differently. The central fairness notion is envy-freeness: every agent weakly prefers its own piece to every other agent's…
Ratings, Reviews, and the Marketing of New Products: With Only an Average Rating the Firm Advertises to a Smaller Set of Consumers and Prices Higher than with Full Reviews or No InformationResearch Paper
Online retailers and platforms summarize the experience of past buyers for future buyers. Some show only an average rating, a single number; others show full reviews, from which a reader can tell who the reviewer was and how well the product suited them. Sellers of new products, in turn, decide whom to advertise to in the launch period, and digital…
Pricing with Tips in Three-Sided Delivery Platforms: Efficient Equilibria under Structured CostsResearch Paper
Online delivery platforms coordinate three distinct sides of a market: buyers choose what to purchase, stores supply the products, and couriers choose which orders to deliver. Unlike a two-sided assignment market, a feasible transaction must align all three participants. Up-front tips matter because couriers can observe the total compensation, including…
An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities: On Infeasible Systems, OEA Returns a Solution of (Alt) Within 2m(m+1) ln((m+1)‖u−ℓ‖/(2mτ)) IterationsResearch Paper
A system of linear inequalities may have either a feasible point or a short witness that no feasible point exists. An algorithm that returns the witness is useful when a solver must explain an infeasibility decision rather than merely announce one. The standard ellipsoid method can test feasibility under suitable geometric bounds, but its ordinary output…
How Endogenization of the Reference Point Affects Loss Aversion: A Study of Portfolio Selection: The Partially Endogenous PPE Is the Exogenous-Reference Optimum with a Lower Degree of Loss AversionResearch Paper
Loss aversion, the tendency to weigh a loss more heavily than a gain of the same size, is the central ingredient of reference-dependent preferences. Measured degrees of loss aversion vary widely across experiments and markets. One explanation is that the reference point is not fixed. People form it partly from their own expectations about what they will…
The Important Role of Time Limits When Consumers Choose Their Time in Service: The Revenue-Maximizing IC and IR Mechanism Achieves the First Best and Imposes a Time Limit When Congestion Is HighResearch Paper
In many services the customer, not the provider, decides how long to stay: a gym session, a car-wash bay, an electric-vehicle charger, a call to a help line, a slot on a shared computing resource. Such services are called discretionary. Their congestion depends on how many customers join and on how long each of them stays. Providers manage them with per-use…