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
EconomicsOperations ResearchProbability·Captain: mikedeng1

Dynamic Contract Design in the Presence of Double Moral Hazard: One of Three Tenure-and-Termination Contracts γⁱ(wⁱ) Is Optimal Among Contracts Inducing Full Effort and Truth-TellingResearch Paper

Many businesses are run by an agent on behalf of an owner who cannot see everything the agent does. Two frictions arise together. The agent may shirk, saving the cost of the effort that brings customers in, and the agent may divert cash, pocketing the fee of a customer the owner never sees: a plumbing franchise whose offline jobs bypass the head office, or…

13 thms2 active usersReviewed
Control TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

Optimal Electricity Demand Response Contracting with Responsiveness Incentives 1: The Producer's Second-Best Value in Closed FormResearch Paper

Demand response asks electricity consumers to lower or smooth their consumption when generation is expensive, in exchange for payments. Field trials such as Low Carbon London showed two effects of such incentives: consumers reduce their average consumption, and the variability of their response depends on how much effort they put into it. A producer who…

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

Strategyproof Approximation of the Minimax on Networks 2: No Strategyproof Randomized Mechanism Beats 2 - o(1) on TreesResearch Paper

A public facility (a fire station, a hospital, a server) is to be placed on a road network, and the people it serves report their own locations. When the planner wants to minimise the distance to the farthest user (the minimax or egalitarian objective, in the sense of Rawls), each user has an incentive to misreport so as to pull the facility towards…

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

Strategyproof Approximation of the Minimax on Networks 1: A Strategyproof 3/2-Approximation Mechanism on the CircleResearch Paper

A facility — a fire station, a server, a meeting point — must be placed on a network, and every user of the network reports where they are. When the planner cares about the worst-off user, the objective is the minimax: minimize the largest distance from the facility to a user. The reports are private information, so a user may misreport a location to pull…

13 thms2 active usersReviewed
Algorithmic Game Theory·Captain: mikedeng1

The Limits of Posted Prices in Random-Order Combinatorial AuctionsResearch Paper

In a combinatorial auction a seller allocates mmm items M=[m]M=[m]M=[m] among nnn bidders, bidder iii holding a private valuation vi:2M→R+v_i:2^M\to\mathbb R_+vi​:2M→R+​, and wants an allocation (S1,…,Sn)(S_1,\dots,S_n)(S1​,…,Sn​) of pairwise disjoint bundles with large welfare ∑ivi(Si)\sum_i v_i(S_i)∑i​vi​(Si​). Truthful mechanisms that need little communication are a central topic at the boundary of economics and computing.…

26 thms1 active userReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: Shuze Chen

One Trap Is Enough: The Structure and Complexity of Robust Contracts for Sequential SearchResearch Paper

In research and development, procurement and delegated experimentation, an agent tries costly options with random outcomes one at a time, keeps the best outcome found, and decides when to stop; the principal sees only the outcome that is finally submitted and pays a wage that depends on it. Without an incentive problem this is Pandora's box problem (Weitzman…

19 thms1 active userReviewed
Algorithmic Game Theory·Captain: mikedeng1

Lotteries Protect Single-Item Sellers from Monopolist IntermediariesResearch Paper

A publisher can own an advertising impression while an exchange controls which advertiser reaches the publisher. A blockchain application can face a similar separation between the party selling an opportunity and the party selecting participating users. In such settings, optimizing an auction for direct interaction with buyers does not settle the seller's…

25 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Sybil-Proofness of Generalized Adaptive Clinching and Implications for Blockchain Mechanism DesignResearch Paper

An automated market maker (AMM) is a pool of two tokens XXX and YYY that trades against users along a fixed reserve curve y=φ(x)y=\varphi(x)y=φ(x). On a blockchain, orders are collected into a batch by a block builder, and the batch is then executed against the pool. Executing orders one at a time in builder-chosen order exposes users to front-running and sandwich attacks.…

80 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

From Bilateral Trade to Matching Markets: Sharp Gains from TradeResearch Paper

In a matching market, unit-demand buyers and unit-supply sellers with privately known values and costs are connected by a compatibility graph, and a platform or market maker must decide who trades with whom and at what prices. Myerson and Satterthwaite (MS83) showed that incentive compatibility, voluntary participation and budget balance already rule out…

38 thms1 active userReviewed
Algorithmic Game TheoryEconomicsOptimization·Captain: Shuze Chen

Otter: A Provably MEV-Resilient Automated Market Maker via Surplus RedistributionResearch Paper

An automated market maker (AMM) is a smart contract that holds reserves of two tokens XXX and YYY and trades with anyone along a fixed pricing curve. On a blockchain the trades of one block are sequenced by a builder, who may also insert trades of its own. Ordering power yields maximal extractable value (MEV): in a sandwich attack the builder buys before a…

18 thms1 active userReviewed
Algorithmic Game TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Pairwise Exchanges of Freely Replicable Goods with Negative ExternalitiesResearch Paper

Datasets, software and patents are freely replicable: giving a copy costs the giver nothing directly. Firms that hold such goods are often competitors, so each one gains from acquiring a good and loses when a rival acquires one. Data consortia and patent pools face this tension: every member wants access to the others' goods, and no member wants its rivals…

30 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Search and Verification for Strategyproof Facility Location on Metric GraphsResearch Paper

In facility location without money, each of nnn agents has a private ideal location on a shared space and a planner places one facility from the agents' reports. An agent's cost is its distance to the facility, and a mechanism is strategyproof (SP) when no agent can lower its cost by misreporting. On networks such as road or communication graphs the space is…

20 thms1 active userReviewed
Algorithmic Game TheoryProbability·Captain: mikedeng1

The Power of Simple Mechanisms: A Tight eee-Approximation for Gains from Trade in Matching MarketsResearch Paper

A two-sided market brings together buyers who value an item and sellers who hold it at a cost. The first-best gains from trade (GFT) match each trade whose value exceeds its cost. The Myerson–Satterthwaite theorem says that no incentive-compatible, individually rational and budget-balanced mechanism attains this benchmark, even in bilateral trade. So the…

23 thms1 active userReviewed
Algorithmic Game Theory·Captain: mikedeng1

A Bulow–Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple AuctionsResearch Paper

A seller with several distinct items must decide both what to offer and how to price it. Even when there is only one buyer and the buyer values a collection by adding its item values, the seller can offer lotteries as well as deterministic bundles. The benchmark of an optimal truthful auction therefore includes many more choices than posting one price for…

25 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Learning vs. Optimizing Players in Budgeted AuctionsResearch Paper

Online advertising platforms run enormous numbers of auctions, and most advertisers delegate bidding to an algorithm that spends a fixed budget over time. A standard choice is pacing: bid a multiple of the value and adjust that multiple according to spending. When one bidder uses such a rule, a competing bidder can observe it and exploit it. In games…

16 thms1 active userReviewed
Algorithmic Game TheoryProbability·Captain: iris

The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided MarketsResearch Paper

A two-sided market has mmm unit-demand buyers and nnn unit-supply sellers. The quantity of interest is the Gains From Trade (GFT): the total value of the buyers who receive an item minus the total cost of the sellers who give one up. Myerson and Satterthwaite showed that already with one buyer and one seller no incentive-compatible, individually rational and…

30 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Tight Approximation Bounds for Clock AuctionsResearch Paper

A clock auction serves a feasible set of single-parameter bidders while learning about them only through rising prices. Each bidder faces a weakly increasing sequence of personal prices; she stays while she accepts and leaves for good at her first rejection, and the auction serves a feasible set of the bidders still active. Clock auctions were introduced by…

85 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Fair and Strategyproof Facility Location in Euclidean SpaceResearch Paper

Strategyproof facility location is a basic problem of approximate mechanism design without money (Procaccia and Tennenholtz 2009). Agents report locations, a mechanism places one facility, and every agent wants the facility close to her true location. A mechanism is strategyproof if no agent can move the facility closer to herself by misreporting. Since the…

47 thms1 active userReviewed
Algorithmic Game Theory·Captain: iris

Second-Best Bilateral Trade is 1/21/21/2 EfficientResearch Paper

In bilateral trade a seller owns one indivisible good and a buyer may acquire it. Each holds a private, nonnegative value, sss and bbb, drawn independently from publicly known priors FSF_SFS​ and FBF_BFB​. Trading creates the surplus b−sb-sb−s, and the first-best gains from trade FB=E[(b−s)+]\mathrm{FB}=\mathbb E[(b-s)^+]FB=E[(b−s)+] are obtained by trading exactly when b>sb>sb>s. The Myerson–Satterthwaite…

63 thms1 active userReviewed
Algorithmic Game TheoryOptimizationProbability·Captain: iris

The Exact Welfare Guarantee of Fixed-Price Bilateral TradeResearch Paper

A seller owns one item and a buyer may want it; their values are private and independent. Myerson and Satterthwaite showed that no mechanism is at once efficient, incentive compatible, individually rational and budget balanced (MS83). The simplest mechanism that keeps every property but efficiency is a fixed price: post one price, and trade happens if both…

27 thms1 active userReviewed
Algorithmic Game TheoryBandit AlgorithmsMachine Learning·Captain: iris

Optimal Regret for Profit Maximization in Bilateral TradeResearch Paper

In bilateral trade, a seller and a buyer with private valuations meet an intermediary who posts a purchase price to the seller and a sale price to the buyer. Trade happens only if both accept, and the intermediary keeps the difference. The Myerson–Satterthwaite impossibility theorem makes this setting a central one in mechanism design, and its online…

32 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

On Competing Sellers with Substitutable GoodsResearch Paper

When two sellers offer substitutable goods to the same buyer, classical Bertrand competition with posted prices drives the weaker seller's revenue to zero and leaves the stronger one only the value gap: if the buyer values Alice's good at aaa and Bob's at bbb, Alice earns (a−b)+(a-b)^+(a−b)+. Sellers in practice are not restricted to posted prices. They can offer menus of…

39 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Tight Analysis of Randomized Truthful Scheduling: An (m+1)/2(m+1)/2(m+1)/2 Lower BoundResearch Paper

Truthful scheduling on unrelated machines is the problem with which Nisan and Ronen started algorithmic mechanism design (NR99). A set of jobs has to be assigned to mmm machines; machine iii needs pijp_{ij}pij​ time units for job jjj, and only machine iii knows its row pip_ipi​. A mechanism asks the machines for their rows, assigns the jobs and pays the machines. It should…

26 thms1 active userReviewed
Linear OptimizationOperations Research·Captain: iris

The Power of Simple Menus in Robust Selling Mechanisms: Robust Randomized Pricing over Fixed Price Levels Is a Finite Linear ProgramResearch Paper

A seller offers one item to one buyer whose valuation lies in [0,vˉ][0,\bar v][0,vˉ] and whose valuation distribution FFF is not known. Robust mechanism design asks for a selling mechanism that performs well against every distribution consistent with the seller's partial information. Without restrictions on the menu, the optimal robust mechanism randomizes over a…

25 thms1 active userReviewed
Operations ResearchRevenue Management and Pricing·Captain: iris

Technical Note—On Revenue Management with Strategic Customers Choosing When and What to Buy: Every Dynamic Pricing Policy Earns at Most the Fluid Value Jˉ1\bar J^1Jˉ1Research Paper

Network revenue management studies a seller of perishable capacity: flight legs, hotel nights, cloud resources. Products are bundles of resources, the inventory is fixed, and the season ends at a known time. Upper bounds on optimal revenue are the basic tool of the field, because an exact optimum is out of reach and every performance guarantee for a…

15 thms1 active userReviewed
PreviousPage 4 of 5Next

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