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
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Algorithmic Mechanism Design V: The Randomly Biased Min Work Mechanism Is a Strongly Truthful 7/4-Approximation for Two AgentsResearch Paper

Algorithmic mechanism design, introduced by Nisan and Ronen (Games Econ. Behav. 35, 2001), studies optimization problems whose input is held by self-interested agents. Each agent reports its private data to a protocol, and the protocol must choose an output and payments so that reporting the truth is in every agent's interest while the chosen output is…

10 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Algorithmic Mechanism Design IV: No Local Truthful Mechanism Achieves a c-Approximation for Task Scheduling for Any c < nResearch Paper

Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) asks how well a computational task can be carried out when its inputs are held by self-interested agents who may lie about them. Their test case is scheduling on unrelated machines: tasks must be assigned to agents (machines), each agent privately knows how long it needs…

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

Algorithmic Mechanism Design II: A Lower Bound for Truthful Task SchedulingResearch Paper

Algorithms deployed on the Internet often take their inputs from parties who own them and who may lie when lying pays. Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) proposed studying optimization problems in this setting: the algorithm designer may hand out payments, and must guarantee that the intended output is…

11 thms3 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

The Theory and Practice of Revenue Management IV: AuctionsTextbook

Airlines selling last seats, Priceline's name-your-own-price, procurement of supply contracts: Chapter 6 of Talluri and van Ryzin's The Theory and Practice of Revenue Management (2004) treats auctions as pricing mechanisms and asks what revenue they earn and how to design them. Its centre is Myerson's (1981) theory for independent private values: whatever…

7 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: Shuze Chen

Algorithmic Game Theory V: Stable Matching and Trading without MoneyTextbook

When money is off the table and the Gibbard–Satterthwaite theorem (Mission III of this series) blocks general strategyproof choice, restricted preference domains reopen the door. The two great examples both come from allocation: Shapley–Scarf's housing market (1974), where Gale's Top Trading Cycle algorithm finds the unique core allocation and Roth (1982)…

9 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: Shuze Chen

Algorithmic Game Theory IV: VCG and the Limits of TruthfulnessTextbook

Mission III of this series ends at an impossibility: without money, incentive compatibility over three or more alternatives means dictatorship. This mission formalizes the classical escape route — quasilinear utilities and payments — and the exact price of it. Vickrey (1961) discovered that a second-price auction makes truth-telling dominant; Clarke (1971)…

6 thms3 active usersReviewed
🏆Completed
Operations Research·Captain: qm2204

Buying to Bundle: Asymptotic Optimality of Surrogate BundlingResearch Paper

A platform sourcing items from monopolistic sellers with private quality cannot tractably maximize its true profit: the bundle revenue Rev(vS)Rev(v_S)Rev(vS​) is neither monotone, submodular, supermodular, subadditive, nor superadditive. Theorem 4.6 of Buying to Bundle: Optimal Sourcing from Monopolistic Sellers shows that the simple surrogate threshold mechanism —…

19 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomics·Captain: iris

Multitask Contracts: Realizing the Value of BundlingResearch Paper

Delegating many tasks to one agent is the norm in practice: a contractor builds several components of a project, a crowd worker labels a batch of items, a manager runs several business lines. The principal cannot observe effort, only which tasks succeed, so she must pay for outcomes. A natural design question in the multitask principal–agent model of Zhao…

32 thms2 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

Second-Best Trade Is Half Efficient in Multidimensional MarketsResearch Paper

A trading platform may know which transactions are feasible without knowing which ones create value. Buyers privately know their willingness to pay, while sellers privately know their costs. The gains from trade are the buyers' total value minus the sellers' total cost. A mechanism must elicit these numbers while giving participants a reason to report…

24 thms2 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

Pareto Inefficiency of EFXResearch Paper

Dividing indivisible goods asks for a complete assignment of objects to people whose preferences may differ. A fair assignment should limit envy, while an efficient assignment should avoid a redistribution that benefits someone without harming anyone else. These requirements address different concerns. A participant can regard an allocation as unfair even…

13 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: iris

Compensation DesignResearch Paper

Platforms that aggregate content or data, such as generative-AI answer engines, recommendation services and data marketplaces, depend on independent contributors who decide for themselves whether to take part. Each contributor bears a private cost of participating, and the platform has a fixed budget to distribute. The platform knows how much value any set…

41 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomics·Captain: iris

Auctions of Auctions: exchanges' double bid-shading lowers both publisher revenue and advertiser profit below the direct benchmarkResearch Paper

Display advertising is sold impression by impression in real-time auctions. A publisher rarely sells to advertisers directly: advertisers delegate bidding to intermediaries, ad exchanges, which collect their clients' bids in an internal auction and then bid on the winner's behalf in the publisher's header auction. Since the industry's move to first-price…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: iris

Best of Both Worlds Ad Contracts: Guaranteed Allocation and Price with Programmatic Efficiency: The Market-Maker Contract Strictly Raises Revenue and Welfare at Unchanged Utilities and EfficiencyResearch Paper

Display advertising is sold in two ways. Reservation contracts guarantee an advertiser a volume of impressions at a fixed price, negotiated in advance. Programmatic auctions (ad exchanges) sell impressions one at a time, efficiently, but at a price and with an allocation that the advertiser does not know in advance. Advertisers with fixed campaign budgets…

18 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
🏆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
🏆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
🏆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
🏆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
PreviousPage 4 of 7Next

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