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.
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-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…
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…
Set Relations via Families of Scalar Functions and Approximate Solutions in Set Optimization: A Weierstrass-Type Existence Theorem with Hausdorff Convergence of Approximate MinimizersResearch Paper
Many decision problems have set-valued outcomes rather than single numbers. Typical cases are a portfolio whose risk is a set of capital vectors, a vector optimization problem whose image is upper-bounded by an ordering cone, or a robust model whose value is the set of all achievable outcomes. Set optimization minimizes such a map f:X→P(Z).…
Reputation, Competition, and Lies in Labor Market Recommendations: The Equilibrium Hiring Probability Rises with the Adviser's Reputation in Top-Heavy Markets and Falls in Bottom-Heavy MarketsResearch Paper
Hiring decisions often rest on a recommendation from someone who knows the candidate: a thesis adviser, a former supervisor, a colleague. Referrals are a common channel of labor market matching, and their value depends on whether the recommender can be trusted. An adviser who cares about his candidate has a reason to overstate the candidate's quality, and…
Revenue Volatility Under Uncertain Network Effects: The Worst-Case Relative Revenue Change over ε-Perturbed Networks Equals αλmax·ε/(1 − αλmax(1 + ε))Research Paper
A seller of a good with network externalities (a social app, a telecom plan, a game console) gains from knowing how strongly each consumer's demand depends on the consumption of others. Candogan, Bimpikis and Ozdaglar (Operations Research, 2012) showed that, on a known network, the optimal price vector of a monopolist and the resulting revenue have closed…
Naive Learning Through Probability Overmatching: Along Any Vanishing-Influence Network Sequence, Extremization DeGroot Processes Eventually Agree on the True State with Probability Tending to OneResearch Paper
Models of naive social learning ask whether agents who update by simple averaging rules, rather than by Bayes' rule, can still aggregate dispersed information. In the classic DeGroot model every agent repeatedly replaces her belief by a weighted average of her neighbours' beliefs. Golub and Jackson (2010) showed that when agents communicate real-valued…
Introduction to Matrix Analytic Methods in Stochastic Modeling XII: Level-Dependent QBDs and Their Minimal SolutionsTextbook
Many queueing and reliability models are Markov chains on a two-dimensional state space whose first coordinate, the level, moves by at most one unit per transition, while the second, the phase, records an auxiliary state such as the phase of a service time or the number of busy servers. When the transition probabilities do not depend on the level, such a…
A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions: The Algorithm of Figure 3 Returns a Minimizer of Every Real Submodular Function in O(n⁷ log n) StepsResearch Paper
Submodular function minimization asks for a subset X of a finite set V that minimizes a set function f satisfying f(X)+f(Y)≥f(X∪Y)+f(X∩Y). Cut functions, matroid rank functions and entropy are submodular, and minimizing them is a subroutine in dynamic flows, facility location and source coding. Grötschel, Lovász and Schrijver showed in…
The Traveling-Salesman Problem and Minimum Spanning Trees: The 1-Tree Gap Vanishes Exactly When the Subtour LP Has an Integral Optimal SolutionResearch Paper
The symmetric traveling-salesman problem asks for a cheapest cycle through all n vertices of a complete graph with real edge weights. Every exact method for it rests on lower bounds, and the most widely used one comes from Held and Karp's two papers of 1970–71 (Held & Karp 1970; Part II, 1971). Their bound is built from 1-trees, a slight variant of spanning…
Flows in Networks V: Common Systems of Restricted RepresentativesTextbook
Assignment questions ask whether every member of a family can be served by a different resource: committees that each need a distinct member as representative, or tasks that each need an admissible worker. The classical answer is Hall's theorem (Hall 1935): a family of sets has a system of distinct representatives exactly when every k of its sets together…
Lectures on Modern Convex Optimization V: Semidefinite Representability of Symmetric Functions of EigenvaluesTextbook
A convex optimization problem can be handed to a semidefinite programming solver only after its constraints and objective have been written as linear matrix inequalities (LMIs): conditions of the form A(x,u)⪰0, where A is affine in the decision variables x and in auxiliary variables u, and ⪰0 means positive semidefinite. A…
Competition and Opacity in the Financial System: Intense Competition Lowers Disclosure Precision Exactly When Investors' Private Information Is PreciseResearch Paper
Banks and other financial institutions are notoriously hard to see into: their loan books are complex and their public reports are coarse. A long-standing policy question is whether competition among financial institutions makes them more or less transparent. One view holds that competition for funding disciplines institutions into disclosing more; another…
Bonus Season: A Theory of Periodic Labor Markets and Coordinated Bonuses: A Periodic Equilibrium Exists if and only if the Importance of Match Quality Lies Between Two ThresholdsResearch Paper
Large bonuses in some industries are paid within a few weeks of each other across firms: banks in a given region announce bonuses in the same months, and top-tier US law firms announce theirs almost simultaneously. Van Wesep and Waters (SSRN 3124536, published in Management Science, 2022, doi:10.1287/mnsc.2021.4076) explain this coordination with a search…
Beta and Coskewness Pricing: Perspective from Probability Weighting: The Rank-Dependent Equilibrium Pricing Kernel and the Three-Moment CAPMResearch Paper
Asset-pricing models relate an asset's expected return to the risks it shares with the market. A familiar covariance term measures exposure to the market return, while a coskewness term measures exposure to the square of that return. Shi, Cui and Zhou ask how these two coefficients change when investors weight probabilities as well as valuing outcomes.…
Optimal Auction Duration: A Price Formation Viewpoint: Semi-Explicit Formula for the Expected Squared Clearing-Price Error E(h) as a Function of the Auction DurationResearch Paper
Most equity markets trade through a continuous limit order book (CLOB): any market order is matched immediately against the resting limit orders. Budish, Cramton and Shim (QJE 2015) argued that continuous matching creates mechanical arbitrage and a race in speed between high-frequency market makers, and proposed frequent batch auctions instead, with a lower…
Sufficient Optimality Conditions in Bilevel Programming: A Second-Order Sufficient Condition via the Value Function Reformulation and Second-Order Directional DerivativesResearch Paper
In a bilevel program, the decision maker chooses an upper-level variable while a second decision must solve a lower-level optimization problem. This structure occurs when a leader anticipates the response of a follower, or when an outer design problem contains an optimization problem as a constraint. A feasible upper-level decision can therefore change the…
Extension of Additive Valuations to General Valuations on the Existence of EFX: A Complete EFX Allocation Exists When Every Agent Has One of Two General ValuationsResearch Paper
Dividing indivisible goods fairly among agents with different preferences is a central problem of fair division, with uses ranging from inheritance and divorce settlements to course allocation and fair-division services such as Spliddit (Goldman–Procaccia 2014). Envy-freeness cannot always be achieved with indivisible goods (one good, two agents), so…
Disclosing Delivery Performance Information When Consumers Are Sensitive to Promised Delivery Time, Delivery Reliability, and Price: Full or No Information-Quality Effort Is OptimalResearch Paper
Online retailers and service providers quote a promised delivery time and are judged on how often they meet it. Platforms increasingly publish delivery-performance information, such as on-time ratings or conformance scores, so that consumers can weigh a quoted time against the firm's record. Producing accurate information is costly: the firm must track…
Optimal Dynamic Momentum Strategies: For Horizons Within the Look-Back Period, the Optimal Weight Is the Mean-Variance Weight Plus a Hedging Term Weighted Toward Recent ReturnsResearch Paper
Time-series momentum is the empirical regularity that an asset's recent excess return predicts its future excess return. It has been documented across equity indices, currencies, commodities and bonds (Moskowitz, Ooi & Pedersen 2012), and momentum portfolios are among the most widely traded systematic strategies. Most of that literature builds portfolios…