Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Operations Research

3,614 missions · 2,659 completed

The discipline of applying mathematical analysis to complex decision problems in operations: allocating scarce resources, scheduling, routing, inventory, and the design of service and production systems. Drawing on mathematical programming, stochastic modeling, queueing, simulation, and game-theoretic reasoning, it seeks policies that perform provably well in systems shaped by constraints, congestion, and uncertainty.

Missions

Open955Completed2659All3614
🏆Completed
Dynamic ProgrammingOptimizationReinforcement Learning·Captain: mikedeng1

A First-Order Approach to Accelerated Value Iteration 3: On the n-State Chain MDP, Every First-Order Method Has ‖v_s − v*‖∞ ≥ λ^s/(1+λ) for s = 1, …, n − 1Research Paper

Value iteration (VI) is the basic algorithm for computing the optimal value function of a discounted Markov decision process (MDP). Its error contracts by the discount factor λ\lambdaλ per step, so it needs on the order of (1−λ)−1log⁡(1/ϵ)(1-\lambda)^{-1}\log(1/\epsilon)(1−λ)−1log(1/ϵ) iterations, which is slow when λ\lambdaλ is close to 111, the regime of interest in long-horizon planning and…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue 2: Random-Sampling VCG Is Ex-Post IC-IR and a 4-Approximation to Welfare for Separable SOS ValuationsResearch Paper

In many auctions a bidder's value for what is sold depends on information held by other bidders: the value of an oil-drilling lease depends on every bidder's geological survey, the value of a piece of art on what other experts know about its provenance. This is the interdependent values model of Milgrom and Weber (1982). With interdependent values the…

8 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOptimization·Captain: mikedeng1

Proof-of-Work Cryptocurrencies: Does Mining Technology Undermine Decentralization? 3: Sensitivities of Equilibrium Hash Rates to Mining Capacity and Reward, and Shares Shift to Smaller MinersResearch Paper

Bitcoin and other proof-of-work cryptocurrencies rely on miners, who spend computing power ("hash rate") to win the right to append a block and collect a reward. The security argument for such systems assumes that no single miner, or small coalition, controls a large share of the total hash rate. Whether the economics of mining push the system towards or…

8 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryAnalysisMechanism Design·Captain: mikedeng1

Mechanism Design under Approximate Incentive Compatibility 4: Randomized Perturbed Delayed Mechanisms Gain Ω(ε^(α/(2α−1))) Revenue Under Local α-Power EnvelopesResearch Paper

Classical mechanism design assumes that agents optimize exactly: a buyer facing a menu of lotteries picks the one that maximizes expected utility, and an incentive compatible (IC) mechanism makes truth-telling optimal. Buyers that are only approximately rational, or that face small costs of computing or reporting, need only be made to prefer the truth up to…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Guarantees in Fair Division: General or Monotone Preferences 2: For Monotone Preferences the Moving Knife Guarantee Lies Between minMax and Maxmin and the Bid & Choose Guarantee Is at Most MaxminResearch Paper

Fair division asks how to split a divisible resource among nnn agents whose preferences differ. In the non-atomic ("cake-cutting") model the resource is a region of Euclidean space and an agent values each measurable piece. Bogomolnaia and Moulin (arXiv:1911.10009, Mathematics of Operations Research, 2023) study fair guarantees: utility levels that a division…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationProbability·Captain: mikedeng1

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities: Rounding LP-Match Online Earns 0.51 of the Optimal Online AlgorithmResearch Paper

Ride hailing, online advertising and kidney exchange share a decision problem: resources that are present from the start must be matched, irrevocably and one at a time, to requests that arrive at random. When the arrival probabilities are known in advance, the natural benchmark for an online algorithm is not the offline optimum (the "prophet", who sees…

21 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Linear Programming and Community Detection 1: Minimum Bisection Recovers the Planted Bisection When d_in − d_out > n/4 − 1Research Paper

Community detection asks for a partition of the vertices of a graph into groups that are densely connected inside and sparsely connected across. In its simplest form there are two communities of equal size, and the natural combinatorial formulation is the minimum bisection problem: among all ways of splitting the vertex set into two halves, find one that…

5 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimizationStochastic Systems·Captain: mikedeng1

Managing Outpatient Service with Strategic Walk-ins I: With Total Capacity μ ≤ √(λC_D/(2R)), the Observable Scheduling Setting Costs No More Than the Unobservable OneResearch Paper

Outpatient clinics serve two kinds of patients: those who book an appointment and those who walk in on the day. Many providers now run open-access or hybrid schedules, which reserve part of the day for walk-ins. Whether patients book or walk in depends on what they know about the appointment delay. Some clinics publish the next available slot in real time…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOptimization·Captain: mikedeng1

Marketplace Leakage 4: The Marketplace Prefers Not to Impose a Price-Parity Clause If and Only If q < 1/2 and μ > (v − c)/2Research Paper

Online marketplaces (Amazon, Booking.com, Airbnb, Upwork) charge sellers a fee on every transaction they intermediate. Once a buyer has found a seller on the marketplace, both have an incentive to complete the sale off the platform and split the fee they save. This is leakage (also called disintermediation or showrooming), and it limits the fees a…

6 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOptimization·Captain: mikedeng1

Marketplace Leakage 2: Optimal Investment in Transaction Benefits Decreases in Its Cost and Is First Constant, Then Decreasing, Then Increasing in Switching CostsResearch Paper

Online marketplaces for services (home repair, tutoring, beauty appointments, freelancing) earn a fee on each transaction they intermediate. After a buyer has found a seller on the marketplace, both sides can often complete the transaction, or the next one, off the platform and avoid the fee. This leakage (also called disintermediation) is a central…

8 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomics·Captain: mikedeng1

A Strongly Polynomial Algorithm for Linear Exchange Markets I: Over Revealed Edges, the Prices of an F-Equilibrium Support a Market EquilibriumResearch Paper

The linear exchange market (the linear Arrow–Debreu model) is the basic model of general equilibrium with linear utilities: each agent brings goods to the market, sells them at the going prices, and spends the proceeds on the goods that give the most utility per unit of money. Computing its equilibrium is a classical problem in algorithmic game theory and…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationProbabilityTheoretical Computer Science·Captain: mikedeng1

Selection and Ordering Policies for Hiring Pipelines via Linear Programming 2: An LP-Rounding Policy That Sends Offers in Parallel Lists Earns at Least (1 − 1/e) Times the LP BoundResearch Paper

Firms that hire for several roles at once face a timing problem. An offer occupies a candidate until they answer, a candidate can hold only one offer, and the hiring season has a fixed number of decision rounds. Sending offers one at a time is slow; sending them all at once risks over-hiring. Epstein and Ma (arXiv:2210.04059v3, Operations Research 2024)…

8 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimizationProbability·Captain: mikedeng1

How Advance Sales Can Reduce Profits: When to Buy, When to Sell, and What Price to Charge: The Profit-Maximizing Price and Induced Arrival Rates Under High DemandResearch Paper

A seller with scarce stock may offer a product before its main selling period. This gives buyers another chance to obtain it, but it can also alter when they compete for the stock. The seller must choose a price while anticipating that buyers respond to both the price and the chance that the unit will already be gone. Glazer, Hassin, and Nowik study this…

11 thms2 active usersReviewed
🏆Completed
Mechanism DesignOptimizationProbability·Captain: mikedeng1

Intertemporal Price Discrimination via Randomized Promotions: A Two-Point Price Distribution Is Optimal for Randomized Pricing with Two Customer SegmentsResearch Paper

Retailers that run predictable promotions teach their customers to wait for them. A customer who knows that a discount will come next week has no reason to buy at the list price today. Firms therefore lose margin on exactly the customers who would have paid in full. One response, documented in practice by Moon, Bimpikis and Mendelson (2017), is to randomize…

8 thms2 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingStochastic Systems·Captain: mikedeng1

A Dynamic Model for Managing Volunteer Engagement I: The Bellman Equation of the Drift-Rate Control Problem Has a SolutionResearch Paper

Non-profit organizations depend on volunteers whose availability they cannot schedule. They can only influence it, through recruiting drives, reminders and recognition events. Ata, Tongarlak, Lee and Field (arXiv:2312.02920) model a food-recovery non-profit's volunteer pool as a queueing network. Repeat volunteers rest between shifts, one-time volunteers…

17 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOptimization+1·Captain: mikedeng1

Partial Vertical Ownership, Capacity Investment, and Information Exchange in a Supply Chain II: Truthful Cheap Talk Is an Equilibrium Iff the Ownership Share β Is at Least β̳Research Paper

A supplier who must build capacity before a selling season would like to know how large demand will be, and the retailer downstream often knows better. Under a simple wholesale-price contract, however, the retailer gains from overstating demand: more capacity means more sales for her, and the cost of idle capacity falls on the supplier. Since the retailer's…

8 thms2 active usersReviewed
🏆Completed
EconomicsOptimizationProbability·Captain: mikedeng1

Partial Vertical Ownership, Capacity Investment, and Information Exchange in a Supply Chain I: Under Complete Information the Retailer Finances the Entire Capacity Iff β ≥ β̲, and β̲ < 1Research Paper

Firms in a supply chain often hold equity in one another. A retailer may own a minority stake in a supplier without controlling it: the stake is passive, but it changes what the retailer cares about, because part of the supplier's profit now accrues to her. Avinadav and Shamir (Management Science, 2023) study how such partial vertical ownership (PVO) affects…

9 thms2 active usersReviewed
🏆Completed
Dynamical SystemsEconomicsOptimization·Captain: mikedeng1

Minimum Earnings Regulation and the Stability of Marketplaces II: Without Subsidies a Utilization Shock u₀ Can Be Absorbed Exactly When u₀ ≥ M/J(C(M))Research Paper

In 2018 New York City's Taxi and Limousine Commission adopted a minimum earnings rule for ride-hailing drivers: each platform must pay drivers, per hour spent with a passenger, at least a target hourly earnings level divided by the platform's measured driver utilization in the previous period. The rule ties next period's wage floor to this period's idle…

6 thms2 active usersReviewed
🏆Completed
Dynamical SystemsEconomicsOptimization·Captain: mikedeng1

Minimum Earnings Regulation and the Stability of Marketplaces III: A Minimum Earnings Marketplace Is Dynamically Stable Exactly When It Is Statically StableResearch Paper

In 2018 New York City's Taxi and Limousine Commission (TLC) imposed a minimum pay formula on the largest ride-hailing platforms, following a proposal by Parrott and Reich (2018): the pay per minute and per mile driven is divided by the platform's utilization rate, the fraction of drivers' working time spent carrying passengers. Seattle adopted a similar…

7 thms2 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingProbability·Captain: mikedeng1

A Dynamic Model for Managing Volunteer Engagement II: The Bellman Solution in Closed Form Between Consecutive Engagement ThresholdsResearch Paper

Non-profit organizations such as food banks run on volunteer labour. Volunteers sign up for shifts, wait on a sign-up list, work, rest, and may or may not return; the organization can spend money on engagement activities (reminders, recognition events, recruitment drives) that raise the rate at which volunteers come back or arrive. Spending too little…

6 thms2 active usersReviewed
🏆Completed
EconomicsProbability·Captain: mikedeng1

Operational Risk Management: Optimal Inspection Policy II: The Optimal Hybrid Inspection Policy Strictly Beats the Random Policy and Weakly Beats the Periodic PolicyResearch Paper

Banks and other financial firms lose money through operational errors: mistyped trades, missed reconciliations, compliance lapses. Regulators require the firm to hold capital against these losses, and internal audit teams spend most of their effort deciding when to inspect. Two inspection schedules are common in practice: a periodic schedule (inspect every…

9 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOptimization·Captain: mikedeng1

Marketplace Leakage 1: With Uniform Switching Costs the Equilibrium Fee Is min{μ, v − c}, Leakage Is Positive but Partial, and the Marketplace's Profit Increases in μResearch Paper

Online marketplaces such as Airbnb, Amazon, eBay, Preply or Upwork earn most of their revenue from transaction fees: a seller who sells through the marketplace pays a fee on every sale. Many of these sellers also run their own sales channel, and a buyer who discovers a seller on the marketplace can often complete the purchase directly with that seller,…

6 thms2 active usersReviewed
🏆Completed
EconomicsOptimization·Captain: mikedeng1

Digital Privacy II: Against the Social Optimum, a Business Never Under-Collects While Over-Protecting Data, and a Purely Usage-Driven One Under-Collects and Under-ProtectsResearch Paper

Digital businesses (search engines, social networks, marketplaces) record what their users do and decide how well to protect what they record. Both choices affect users: stored data can improve the service, and it can also be accessed by adversaries such as hackers, fraudsters or data brokers, whose activity harms users. Regulation of data collection and…

7 thms2 active usersReviewed
🏆Completed
AnalysisOptimizationProbability·Captain: mikedeng1

Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality I: Feasible Solutions of the Continuous Stopping LP Can Be Improved to Threshold FormResearch Paper

Two classical online selection problems sit at opposite ends of an information spectrum. In the secretary problem items arrive in uniformly random order, only their relative ranks are observed, and the best possible probability of stopping on the best item tends to 1/e1/e1/e. In the i.i.d. prophet inequality the values are independent draws from a known distributi…

8 thms2 active usersReviewed
🏆Completed
AnalysisControl TheoryEconomics·Captain: mikedeng1

Punish Underperformance with Suspension: Optimal Dynamic Contracts in the Presence of Switching Cost III: Condition 2, Medium Switching Cost, Always-Work Value Functions Meet the Optimality ConditionsResearch Paper

Many service relationships pay an agent per unit of output whose arrival is random: a salesperson closing deals, a call-centre worker resolving tickets, a contractor delivering jobs. When effort is unobservable, the classical tool for keeping an agent motivated is the threat of termination after poor performance. In practice firms often use a milder…

6 thms2 active usersReviewed
PreviousPage 83 of 107Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me