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

Algorithmic Mechanism Design VIII: A Truthful Approximation Scheme for Bounded Scheduling with VerificationResearch Paper

Algorithmic mechanism design asks for algorithms whose inputs are held by self-interested agents: the designer can pay the agents, and must choose payments so that each agent's own interest leads it to reveal what the algorithm needs. Nisan and Ronen introduced the framework with task scheduling on unrelated machines as the running example (Nisan–Ronen 2001)…

16 thms3 active users
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Algorithmic Mechanism Design VI: With Verification, the Compensation-and-Bonus Mechanism Is a Strongly Truthful Optimal ImplementationResearch Paper

Scheduling tasks on machines owned by self-interested parties is the running example of Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001), the paper that introduced the study of mechanisms whose allocation rule is an algorithm with a computational objective. Each machine (agent) privately knows how long it needs for each…

8 thms3 active usersReviewed
🏆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
Captain: mikedeng1

Information Pricing with Independent State-Contingent Payoffs: Simple vs. Optimal MechanismsResearch Paper

An information seller can tell a decision maker something about an uncertain state before she chooses an action. The seller's revenue depends on the buyer's private payoffs and on what she can already do without buying information. For a buyer choosing between acting and not acting, the ability to act using her prior knowledge creates a free alternative…

42 thms2 active usersReviewed
Algorithmic Game Theory·Captain: mikedeng1

The Power and Limits of Money Burning in Bilateral TradeResearch Paper

In bilateral trade a seller owns one indivisible good and a buyer may want it. Each trader privately knows their own value. A mechanism asks both for reports and decides whether to trade and what each trader pays or receives. A mechanism is strongly budget-balanced (SBB) when the buyer's payment always equals the seller's receipt. It is weakly…

38 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Optimal Multi-Item Auctions with I.I.D. ValuesResearch Paper

A seller with several items and several buyers who wants the largest expected revenue faces the multi-item version of Myerson's problem. For one item, Myerson (1981) gives the answer in closed form for every prior. For several items, explicit optimal mechanisms are known only in special cases: two items under analytic conditions, a few uniform or…

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

The No-Menu Complexity of Revenue-Maximizing AuctionsResearch Paper

A revenue guarantee for an auction does not by itself say how much the seller and buyer must communicate. A familiar way to describe a deterministic auction is to give its menu of bundles and prices. That description treats the menu as already available to the buyer. When the seller chooses the menu using information unavailable to the buyer, learning…

21 thms2 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
Algorithmic Game Theory·Captain: iris

How Many Votes Is a Lie Worth? Measuring Strategyproofness through Resource AugmentationResearch Paper

By the Gibbard–Satterthwaite theorem (Gibbard 1973, Satterthwaite 1975), every non-dictatorial voting rule with at least three possible winners can be manipulated: some voter, at some profile, obtains a strictly better winner by misreporting her ranking. The theorem says that manipulation is possible, but not how much it is worth. Berker, Conitzer, Hartman,…

54 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
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

At What Cost? (In)efficiency in First-Price Procurement AuctionsResearch Paper

A first-price procurement auction purchases one good or service by asking suppliers to submit prices simultaneously. The supplier quoting the lowest price wins and receives that price. A buyer concerned with productive efficiency cares about the selected supplier's actual cost, rather than the payment alone. The two can differ because suppliers bid…

19 thms2 active usersReviewed
Algorithmic Game Theory·Captain: mikedeng1

Optimal Truthful Approximation for House Allocation and Rank-Maximal Matchings with TiesResearch Paper

In house allocation, agents rank objects and each agent can receive at most one object. A rule that chooses an allocation from reported rankings must account for the possibility that agents misreport. The mathematical question is how much allocation quality an incentive requirement necessarily costs. Zhang, Zhao, Xu, Xi and Zhao study this question both for…

24 thms2 active usersReviewed
Captain: mikedeng1

On the Menu Complexity of Consumer Utility MaximizationResearch Paper

Allocating a scarce service can require a recipient to incur a cost without giving the provider revenue: waiting, paperwork and other costly participation requirements are examples. Consumer utility measures the value of an allocation after subtracting those costs. A designer maximizing it must consider both who receives a service and what recipients must…

16 thms2 active usersReviewed
Algorithmic Game Theory·Captain: iris

Convergent Dynamics in Second Price Autobidding GamesResearch Paper

Online advertising platforms sell impressions through repeated auctions in which advertisers do not bid by hand: an autobidder scales each value by a pacing multiplier αi∈[0,1]\alpha_i\in[0,1]αi​∈[0,1] so that the advertiser's spending stays within its budget. When every advertiser paces at once, the multipliers interact, and the natural steady state is a second-price…

68 thms2 active usersReviewed
Algorithmic Game Theory·Captain: iris

Second-Best Gains from Trade in Matching MarketsResearch Paper

Two-sided markets match buyers with sellers: labor markets, ride-sharing, advertising exchanges, procurement. If every buyer's value and every seller's cost were public, a designer would choose the feasible set of trades with the largest total surplus, the first best. Values and costs are private, and the Myerson–Satterthwaite theorem (Myerson and…

60 thms2 active usersReviewed
Algorithmic Game Theory·Captain: iris

The DSIC Competition Complexity of Additive Buyers over Independent ItemsResearch Paper

A seller with mmm heterogeneous items faces nnn bidders. The revenue-optimal mechanism for this multi-item setting is in general randomized, hard to compute, and only Bayesian incentive compatible. Competition complexity measures how much a simple mechanism loses by asking a different question from approximation ratios: how many extra bidders must a simple…

31 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
Algorithmic Game TheoryTheoretical Computer Science·Captain: iris

Truthful-in-Expectation Mechanism with Constant Maximin-Share GuaranteeResearch Paper

Dividing indivisible goods among agents with private additive valuations is a basic problem of algorithmic game theory: the agents' reports are the only input, so a rule that rewards misreporting cannot be fair with respect to the true values. A randomized mechanism is truthful in expectation (TIE) if no agent can raise her expected true value by…

43 thms2 active usersReviewed
PreviousPage 5 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