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.
Fair and Consistent Prize Allocation in Competitions 2: Anonymity, Order Preservation, Winner Strict Endowment Monotonicity and Local Consistency Characterize Single-Parametric RulesResearch Paper
Tournaments, races, poker finals and sports leagues end with a ranking of the participants and a sum of prize money to be split among them. The split is usually fixed by a published schedule, and different events use very different schedules: some pay almost everything to the winner, some pay many places, some decay geometrically from one place to the next.…
Fair and Consistent Prize Allocation in Competitions 3: Anonymity, Order Preservation, Winner Strict Endowment Monotonicity and Top Consistency Characterize Parametric RulesResearch Paper
Rank-order competitions — sports tournaments, poker final tables, golf tours, crowdsourcing contests, sales leagues — end with a ranking of the participants and a pot of prize money that has to be split according to that ranking. Organisers publish prize tables that change with the number of entrants and with the size of the purse, and these tables are…
Punish Underperformance with Suspension: Optimal Dynamic Contracts in the Presence of Switching Cost II: Condition 2, High Switching Cost, Not-Hiring Value Functions Meet the Optimality ConditionsResearch Paper
Firms that outsource work to an agent whose effort they cannot observe often punish poor performance by suspending the relationship for a while, even though restarting costs money: a new set-up, re-training, re-mobilisation. Cao, Sun and Tian (Management Science, 2024) study this trade-off in a continuous-time principal–agent model with Poisson arrivals and…
Pricing in On-Demand and One-Way Vehicle-Sharing Networks 1: Static Prices Earn at Least K/(N+K−1+Λ/μ) of the Fluid Optimum, via Increasingly Tight Availability BoundsResearch Paper
In one-way car sharing, bike sharing and ride hailing, a vehicle that serves a trip from location i to location j ends up at j. Prices therefore do two jobs: they collect revenue and they steer the fleet. The best dynamic (state-dependent) pricing policy reacts to where every vehicle is, but computing it is a Markov decision problem over a state space that…
Minimum Earnings Regulation and the Stability of Marketplaces I: The Marketplace Is Stable Exactly When M ≤ w* Under Tight Labor Supply (p* ≤ w*) and M ≤ H(R(p*)) Under Loose SupplyResearch Paper
Minimum hourly earnings rules for ride-hailing drivers are meant to protect income during periods when drivers spend part of their time idle. A platform pays a wage per hour carrying riders, yet drivers care about earnings per hour logged onto the platform. When many drivers enter after a wage increase, utilization can fall and offset the increase. A…
Offline Multi-Action Policy Learning: Generalization and Optimization 1: Cross-Fitted AIPW Policy Learning Has Regret O_p(κ(Π)√(V*/n)) Even with Slowly Converging Nuisance EstimatesResearch Paper
Many decisions are made by assigning one of several actions to an individual on the basis of observed features: which of d drugs to prescribe, which of several promotions to show, which job-training programme to offer. Experimentation is often costly or unethical, while historical records of past assignments and their outcomes are plentiful. Offline policy…
Operational Risk Management: Optimal Inspection Policy I: Periodic Inspection Beats Random Inspection Below an Inspection-Cost Threshold and Loses Above ItResearch Paper
A firm that relies on employees to process transactions can lose money when errors remain undetected. Inspection catches errors, but each inspection costs money, and employees may change their care when they know when an inspection will occur. These effects make the timing of inspections part of a contract design problem, not just a scheduling choice. Kim…
Design and Analysis of Switchback Experiments 1: With m-Period Carryover and T = nm, n ≥ 4, the Unique Minimax-Optimal Regular Design Flips Fair Coins at 1, 2m+1, 3m+1, …, (n−2)m+1Research Paper
Online platforms such as ride-hailing, delivery and advertising marketplaces routinely test new pricing or matching policies on a single market. Randomizing over users is often impossible there: every rider and driver in a city shares one supply pool, so treating some users and not others contaminates the control group. The standard alternative is a switchba…
Superstar Exclusivity in Two-Sided Markets: Exclusivity Draws Consumers and Complementors to the Favored Platform and Raises Complementors' Total SurplusResearch Paper
Platform markets often feature a Superstar: a single complement whose presence moves consumers, such as a blockbuster game on a console or a star streamer on a video platform. Whether such a Superstar signs an exclusive deal with one platform or stays available on both is a recurring question for competition authorities and for platform managers. Empirical…
Fair and Consistent Prize Allocation in Competitions 1: A Prize Allocation Rule Satisfies Order Preservation, Endowment Monotonicity and Consistency iff It Is an Interval RuleResearch Paper
Sports leagues, tournaments, esports events and research competitions all end with a ranking of the participants and a sum of prize money to divide among them. How the money is split according to the ranking is a design choice with visible consequences: Winner-Takes-All schemes reward only the top, equal division ignores the ranking, and most real prize…
Digital Privacy I: The Profit-Maximizing Data Collection and Protection Have a Closed Form, and Both Weakly Increase with the Data-Driven Revenue Share PResearch Paper
Platforms that earn money from their users' activity make two linked decisions about the data that activity generates: how much of it to record and store, and how much to spend protecting what they store. Stored data lets a business tailor its services and sell data-driven products, but it also attracts adversaries (hackers, data brokers, unauthorized third…
Secretaries with Advice 5: With Binary-Classifier Advice of Recall p and Specificity p′, the Optimal Success Probability Tends to ((1−p′)/p)^((1−p′)/p′)·e^((p−1)/p′)Research Paper
A secretary problem asks a decision maker to choose one candidate from a sequence, without being able to recall a rejected candidate. Each arrival reveals how the candidate compares with those seen earlier, but the decision maker does not know the candidate's final rank. A classifier can provide an additional Yes or No signal about whether the current…
Secretaries with Advice 3: A Closed Form for the Backward-Induction Dual Solution of the Secretary-with-Samples LPResearch Paper
In the secretary problemn candidates arrive one at a time in uniformly random order; at each arrival the decision maker sees only how the current candidate compares with the earlier ones and must accept or reject irrevocably, aiming to accept the best candidate overall. Dütting, Lattanzi, Paes Leme and Vassilvitskii, Secretaries with Advice (arXiv:2011.0672…
Secretaries with Advice 4: With Advice from a Binary Classifier, a Threshold Policy Is OptimalResearch Paper
The classical secretary problem asks a decision maker to choose the best of n candidates arriving in random order. A decision must be made when each candidate arrives, before later candidates are seen. In the classical model the decision maker sees only comparisons with earlier candidates. In hiring and selection, a prediction system may also classify an…
Secretaries with Advice 2: With k Samples, a Threshold Policy Is Optimal for Selecting the Best of n SecretariesResearch Paper
In the classical secretary problem, n candidates with distinct qualities arrive in uniformly random order; after each arrival one sees only how the current candidate compares with those already seen, and must irrevocably accept or reject. The goal is to accept the best candidate. Dynkin's rule (skip roughly n/e candidates, then accept the first one better…
Persuading Risk-Conscious Agents: A Geometric Approach II: In Binary Persuasion with a Convex Non-Adoption Region the Convex Program Reduces to a Linear Program over Ω ∪ K₀₁Research Paper
In Bayesian persuasion a sender who observes the state of the world commits to a signaling scheme, a receiver updates her belief by Bayes' rule and acts, and the sender chooses the scheme that maximizes her own expected payoff (Kamenica and Gentzkow 2011). The classical theory assumes the receiver maximizes expected utility, so her payoff is linear in her…
Analytical Solution to a Partially Observable Machine Maintenance Problem with Obvious Failures: The Optimal Maintenance Frontier Has Six Possible StructuresResearch Paper
Machines in production lines deteriorate in ways that are only partly visible. A machine may run in a degraded state that raises costs without announcing itself, and eventually fail in a way that cannot be missed. The decision maker must choose between continuing production, paying for an inspection that reveals the hidden state, and replacing the machine…
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization I: The Largest-Coordinate Strategy Keeps the Stochastic Chasing 0 Game within 2(c+R)log(4mk²/p)Research Paper
Cutting plane methods minimize a convex function, or find a point in a convex set, using only a separation oracle: a routine that, given a query point, either certifies it is good or returns a halfspace containing the target. Lee, Sidford and Wong (arXiv:1508.04874, FOCS 2015) gave a cutting plane method for a convex set in Rn inside a box of…
Privacy Rights and Data Security: GDPR and Personal Data Markets 2: Without Privacy Rights the Monopoly Equilibrium Has Three Breach-Cost Regimes and No Trade Once c ≥ 1 + δμ/(1 + δ)Research Paper
Personal data lets a firm tailor its product to each customer, and the same data exposes the customer to the risk of a breach. The EU's General Data Protection Regulation (GDPR, 2018) and the California Consumer Privacy Act give consumers rights over that data. Data collection must be opted into separately from the purchase, and stored data must be erased…
Gathering Information before Negotiation I: The Buyer's Optimal Information Acquisition Increases with Its Bargaining Power and First Increases, Then Decreases with the Seller's CostResearch Paper
Many transactions are priced by negotiation rather than posted prices: business-to-business procurement, used cars, real estate, the purchase of a company. Before negotiating, a buyer can often spend effort finding out how much the object is actually worth to it, through inspections, trials, consultants or market research. That information serves two…
Stall Economy: The Value of Mobility in Retail on Wheels II: Closed-Form Mean and Variance of the Within-Radius Repositioning Trip Length, Increasing in R and Decreasing in rResearch Paper
Mobile retail stalls (self-driving or driver-operated vending vehicles that move to customers who order through a phone app) are studied by Cao and Qi in Stall Economy: The Value of Mobility in Retail on Wheels (Operations Research, 2022; the mission cites the authors' SSRN manuscript 3711896). A retailer partitions a city into service zones, one stall per…
Stall Economy: The Value of Mobility in Retail on Wheels I: The Magnet Rule Makes the Rendezvous Chain Doubly Stochastic, and Its Stationary Distribution Is Uniform on the Inner DiamondResearch Paper
A mobile retail stall can travel toward its next customer while that customer walks toward the stall. The customer's walking allowance changes where the stall stops, so it also changes the location from which the next trip begins. A useful trip-length calculation therefore needs a distribution for successive meeting points, not just a rule for one meeting.…
Gathering Information before Negotiation II: Under a Uniform Prior and Linear Information Cost, the Seller's Expected Payoff Jumps Down at θs = 1 − θ̃, Up at c = c_l and Down at c = c_hResearch Paper
In many trades the buyer does not know how much the good is worth to it, and can find out before negotiating: a firm commissions due diligence before an acquisition, a hospital pilots a device before negotiating its price, a household inspects a house before making an offer. Such information has two effects. It makes the trade decision better informed,…
Platform Competition and Interoperability: The Net Fee Model III: Stronger Interoperability Lowers the Symmetric Equilibrium Net Fee, Except in Duopoly Without an Outside OptionResearch Paper
A recurring proposal in the policy debate on dominant digital platforms is to make competing platforms interoperable, so that users of one service can interact with users of another; the EU Digital Markets Act (Regulation (EU) 2022/1925, Article 7) imposes such an obligation on gatekeepers' messaging services. The economic case is that users then enjoy…
Change-Point Detection in Dynamic Networks with Missing Links III: The Dyadic-Grid Matrix CUSUM Test Detects an Unknown Change Time Above Energy 4(1+ϵ)(6ω_n/T)^{1/2} + C log(4n log₂T/(α∧β))/√TResearch Paper
Many networks are recorded as a sequence of snapshots: contact networks in epidemiology, communication graphs, brain connectivity measured over time, trade or transport links. A basic statistical question is whether the law generating the snapshots changed at some point. Two features make the question hard in practice. The networks are often sparse, so each…