Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Mechanism Design

269 missions · 158 completed

Often called reverse game theory, the branch of economics and game theory that designs the rules of a game so that self-interested agents, acting on private information, are led to a desired collective outcome. Here the goal is given and the mechanism is the unknown — engineering incentives so that truthful behavior is optimal — with applications from auctions and voting systems to market and internet-protocol design.

Missions

Open111Completed158All269
Operations Research·Captain: iris

The Strategic Role of Supplier Learning: the optimal two-period procurement contract under private cost and private learning outcomesResearch Paper

Learning curves are a standard fact of manufacturing: unit cost falls with cumulative output, so a buyer who orders more today buys cheaper tomorrow (Yelle 1979). Procurement contracts with an outside supplier then face a second problem: the supplier knows its own cost and learning ability better than the buyer does, and it also observes privately how…

70 thms2 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Capacity Games with Supply Function Competition: under submodularity, at-cost bids with marginal-contribution margins are a supply-chain-optimal Nash equilibriumResearch Paper

A buyer facing uncertain demand often secures supply in two stages: it first reserves capacity from several suppliers, and after demand is observed it decides how much of the reserved capacity to use. Electricity procurement (reserve markets), contract manufacturing and logistics all have this shape. In practice each supplier quotes a reservation price for…

11 thms2 active usersReviewed
Algorithmic Game TheoryEconomicsOperations Research·Captain: iris

Parallel Lotteries: Insights from Alaskan Hunting Permit Allocation: every k-ticket lottery equilibrium allocation is (2 − 1/k)-trade efficientResearch Paper

Alaska allocates scarce big-game hunting permits through a draw in which each applicant may buy up to six tickets and spread them across the permit lotteries of her choice; an applicant drawn in several lotteries keeps the permit she ranks highest. Designs of this kind, parallel lotteries, are simple to run and give applicants freedom to express intensity…

15 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

When Is Assortment Optimization Optimal?: Under History-Monotone Futures, Assortments Are Optimal Among All IC MechanismsResearch Paper

Assortment optimization is the problem of choosing which items to offer a customer who buys at most one item, when each item has a fixed, exogenous price. It is one of the central problems of revenue management: the customer's behaviour is described by a choice model, and a large literature computes optimal assortments under specific models, from the…

10 thms2 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Budget-Management Strategies in Repeated Auctions: At Symmetric System Equilibria, Reserve Pricing Earns at Least the Profit of Thresholding, and Thresholding at Least That of Bid ShadingResearch Paper

Online advertising platforms sell impressions through repeated auctions, and advertisers typically buy them under a budget: a cap on what they spend over a campaign. Because the advertisers cannot re-optimize their bids in every auction, the platform usually manages their budgets for them, adjusting how each advertiser participates so that spending tracks…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Optimal Subscription Planning for Digital Goods: Under Condition 2, a Single Grand Subscription Set With a Suitable Fee Achieves the Optimal RevenueResearch Paper

Digital-goods platforms (video, music, e-books, software) sell access in two ways at once: subscriptions, which give unlimited use of a set of items for a period, and rentals, which charge per use. A platform with a large catalogue could offer many subscription sets at different fees, but most platforms offer a single all-inclusive subscription. Alaei,…

8 thms2 active usersReviewed
Algorithmic Game TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Spatio-Temporal Pricing for Ridesharing Platforms: The STP Mechanism Is Subgame-Perfect Incentive Compatible, Welfare-Optimal, Envy-Free and Core-Selecting from Any HistoryResearch Paper

Ridesharing platforms set prices and dispatch drivers over a road network whose demand changes within minutes: a stadium empties, rush hour starts, a neighbourhood goes quiet. Drivers are not employees. They may decline a dispatch, drive somewhere else, or stop working, and the platform pays no one in advance for staying in place. Prices that look only at…

25 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location: The Coordinatewise Median with Predictions Is √(2c²+2)/(1+c)-Consistent and √(2c²+2)/(1−c)-RobustResearch Paper

Learning-augmented algorithms use a machine-learned prediction to perform better when the prediction is accurate, while keeping a worst-case guarantee when it is not. The two guarantees are called consistency (performance under a correct prediction) and robustness (performance under an arbitrary prediction). Agrawal, Balkanski, Gkatzelis, Ou and Tan (arXiv:2…

13 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Optimal Priority-Based Allocation Mechanisms: In a Regular Market, Deferred Acceptance Implements Every Feasible Budget Set Probability Matrix, and DA-STB Exactly the Nested-Within-Segment OnesResearch Paper

School districts, public housing authorities and refugee resettlement agencies allocate scarce items (school seats, apartments, slots) without prices. Most such systems are priority-based: each applicant receives a priority, possibly depending on observable characteristics such as neighborhood or sibling status, and a mechanism such as deferred acceptance…

11 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Choice with Affirmative Action: every substitutable affirmative action rule that is monotonic in priority improvements and type changes admits a bounded reserve representationResearch Paper

Schools, universities and public employers that run affirmative action decide whom to admit from a set of applicants who are ranked by a priority ordering (exam scores, lottery numbers, seniority) and who belong to a minority or a majority group. The procedures used in practice, such as the reserve and quota systems of Boston, Chicago and New York school…

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

Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online: GenSm-Main Is a Universally Truthful, Individually Rational, Budget-Feasible 505-Approximation MechanismResearch Paper

A buyer with a fixed budget wants to hire a team from a pool of sellers, each of whom knows privately what participating would cost them. The buyer values teams through a set function and pays each hired seller. The sellers are strategic: they report whatever cost serves them best. A budget-feasible mechanism decides whom to hire and what to pay so that…

12 thms2 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Fair-Share Allocations for Agents with Arbitrary Entitlements: Every Additive Instance Has an Allocation Giving Each Agent max{3/5, 1/(2−b_i)} of Her AnyPrice ShareResearch Paper

Fair division of indivisible goods asks how to split a set of items among agents who value them differently, with no money changing hands. Many allocation problems are not symmetric: partners in a venture hold different stakes, heirs inherit different fractions of an estate, and countries or departments receive budgets in proportion to size. Such settings…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Dynamic Double Auctions: Toward First Best: With One Seller and Many Buyers, the Mechanism That Couples All Promised Utilities Earns First-Best Profit up to O(√(T log T))Research Paper

A platform that matches one seller with several buyers can trade an item whenever a buyer values it more than the seller does. That allocation maximizes the value created by trade in a single period. A platform seeking revenue also has to respect what privately informed agents are willing to report and accept. In a repeated market, it can distribute utility…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Optimal Auction Design with Deferred Inspection and Reward: The Optimal Single-Agent Auction Has Best-Alternative Bid b(v) = G⁻¹(G(v) − G(v̲)) and a Continuous AllocationResearch Paper

A seller who can inspect a buyer's true value after receiving a bid can use the bid as a refundable deposit. A truthful buyer may receive a reward, while a buyer whose report is false forfeits the deposit. This changes the incentive constraint: a buyer who considers reporting www compares her truthful utility with vx(w)−wv x(w)-wvx(w)−w, not with the payoff from a…

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

Sequential Mechanisms with Ex Post Individual Rationality: The Revenue-Optimal Dynamic Mechanism Is Built by Backward Induction on Cumulative Surplus-Utility Tradeoff FunctionsResearch Paper

Many goods are sold to the same buyer repeatedly: advertising impressions, cloud capacity, seasonal tickets. The buyer's value for each sale is learned only shortly before it, and a seller who knows the distribution of future values can extract more revenue with a dynamic mechanism, one whose terms on later days depend on what the buyer reported earlier.…

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

Report-Dependent Utility and Strategy-Proofness: The True Ranking Is Optimal for Every Decreasing Report-Dependent Utility If and Only If No Ranking Raises the Probability of a Top-r MatchResearch Paper

Deferred acceptance and top trading cycles are strategy-proof: submitting one's true preference ranking is optimal whatever the other participants do (Roth, 1982). School-choice and residency-match systems around the world use them for this reason. Yet laboratory and field data show participants misreporting systematically, most often by leaving popular…

6 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Contracting for Product Support Under Information Asymmetry: Under Countervailing Incentives the First-Best Menu Solves the Performance-Based Screening Problem with Zero Information RentResearch Paper

A repair supplier can invest in capacity before a service contract begins, while the customer may know more about how often her equipment fails. The supplier must choose both an incentive to maintain uptime and a menu that gives customers reason to reveal their failure rates. Li, Mishra, and Netessine study this interaction for maintenance, repair, and…

8 thms2 active usersReviewed
Algorithmic Game TheoryProbability·Captain: mikedeng1

The Square Root Agreement Rule for Incentivizing Truthful Feedback on Online Platforms: Strict Truthful Equilibrium Approximately Payoff-Dominating All Symmetric Equilibria for Many TasksResearch Paper

Online platforms (labor marketplaces, review sites, crowdsourcing services) rely on feedback from their users: did the plumber arrive on time, is this image labelled correctly. The answers cannot be checked against ground truth, so a platform that rewards feedback must reward it by comparing it with other users' answers. This is the problem of peer…

8 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

The Mnemonomics of Contractual Screening: The Optimal Menu Under Limited Memory, and When Forgetting Lowers the Low Type's Marginal Price Below Its Perfect-Memory LevelResearch Paper

Contract terms can affect what a buyer remembers when a later purchase decision arrives. In Guo's model, a buyer learns her expected value before signing a contract but loses direct access to that information before deciding whether to trade. She can infer her earlier value from the contract she chose. A seller therefore designs prices and upfront fees for…

10 thms2 active usersReviewed
🏆Completed
Economics·Captain: mikedeng1

Expectations-Based Loss Aversion in Auctions with Interdependent Values: Extensive vs. Intensive Risk: Under CPE, First-Price Revenue Exceeds Second-Price Revenue iff Bidders Are Loss-Averse in MoneyResearch Paper

A seller choosing between a first-price auction (FPA) and a second-price auction (SPA) needs to know whether the payment rule changes expected revenue. In the classical independent private-value benchmark, the two formats can be revenue equivalent. Balzer and Rosato examine a different setting: a bidder’s value depends on other bidders’ private signals, and…

9 thms2 active usersReviewed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Towards a Functional Fee Market for Cryptocurrencies: Truthful Bidding Is Not Dominant, but the Expected Gain from Strategic Bidding Converges to 0 as the Number of Users DivergesResearch Paper

A cryptocurrency user can attach a fee to a transaction, and a miner can choose which waiting transactions enter the next block. When the most valuable waiting transactions compete for a limited number of places, the fee rule affects both the user's bid and the amount the user expects to pay. Basu, Easley, O'Hara and Sirer study a protocol that charges…

8 thms2 active usersReviewed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

Polyhedral Clinching Auctions for Two-Sided Markets: An Incentive-Compatible, Individually Rational, Budget-Balanced, Pareto-Optimal Mechanism ExistsResearch Paper

Auctions in which bidders face budget constraints do not fit the classical quasi-linear theory: a bidder cannot pay more than a fixed amount, however much the goods are worth to him. For a single divisible good, Dobzinski, Lavi and Nisan showed that the adaptive clinching auction of Ausubel is incentive compatible, individually rational and Pareto optimal,…

12 thms2 active usersReviewed
🏆Completed
EconomicsOperations ResearchProbability·Captain: mikedeng1

Principal Trading Arrangements: When Are Common Contracts Optimal?: The Guaranteed VWAP Contract Is an Optimal Contract for the Client in the Specialized ModelResearch Paper

A client who needs to buy a security may hire a dealer to execute the purchase. The client can observe market prices and trading volume but cannot observe the dealer's trades or the market conditions known to the dealer before trading. A contract based on the closing price or another benchmark can therefore change the dealer's incentives. Baldauf, Frei, and…

13 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Procurement Mechanisms with Post-Auction Pre-Award Cost-Reduction Investigations: Symmetric Suppliers Earn Weakly Higher Ex Ante Profits When Investigations Precede the AwardResearch Paper

Large manufacturers procure components by competitive bidding, and many of them also run cost-reduction investigations: the buyer's engineers visit a supplier's plant and look for process changes that lower the cost of the contracted part. The savings are passed to the buyer as a lower contract price. In practice such investigations usually happen after the…

8 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

On the Futility of Dynamics in Robust Mechanism Design: Minimax Regret Equals T Times the Single-Round Minimax Regret and Repeating a Direct Static Mechanism Is OptimalResearch Paper

A seller who faces the same buyer again and again, a firm that contracts repeatedly with a supplier, or a platform that allocates resources to a returning user can adapt its terms over time. The buyer's behaviour reveals information about their preferences, and mechanisms can link rounds through bundles, discounts and promised future utility. When the…

11 thms2 active usersReviewed
PreviousPage 7 of 11Next

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