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

On the Robustness of Second-Price Auctions in Prior-Independent Mechanism Design II: Against Exchangeable Affiliated Valuations the Minimax Regret Equals the I.I.D. ValueResearch Paper

A seller offers one indivisible item to nnn buyers but does not know the joint distribution of their valuations. The seller knows only that every valuation lies in [0,1][0,1][0,1]. Prior-independent mechanism design asks for a selling mechanism that performs well against every distribution in a class. One measure of performance is the regret: the expected gap between…

14 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Deterministic Budget-Feasible Clock Auctions III: A Deterministic Clock Auction Achieves an O(log n / log log n)-Approximation for Subadditive ValuationsResearch Paper

A budget-feasible procurement auction buys services from strategic sellers under a hard budget. Each of nnn bidders can provide a service at a private cost; the auctioneer values each set of acquired services through a set function vvv and must keep total payments within a budget BBB. The question, introduced by Singer (FOCS 2010), is how much of the optimal…

7 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

On the Robustness of Second-Price Auctions in Prior-Independent Mechanism Design I: For I.I.D. Valuations a Second-Price Auction with Random Reserve Φ*ₙ Is Minimax-Regret Optimal over DSIC MechanismsResearch Paper

Optimal auction theory in the tradition of Myerson (1981) assumes that the seller knows the distribution of the buyers' valuations. In practice that distribution is estimated, misspecified, or simply unknown. Prior-independent mechanism design asks for a mechanism that performs well across a whole class of distributions, without being tuned to any one of…

13 thms3 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

Selling Data to Marketers 2: In Selling Data Appends with Costs Below the Prior Mean, the High-Cost Plan Is Efficient and the Low-Cost Plan Carries Less Information If φ < 1/2 and More If φ > 1/2Research Paper

Data brokers sell information about consumers to firms that decide whom to target: a lender deciding whom to offer credit, a retailer deciding whom to mail. Two products dominate this market. A marketing list sells contact information together with an analysis, so that a firm cannot reach the consumer at all without buying. A data append adds information…

7 thms3 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

Selling Data to Marketers 1: In Selling Marketing Lists, the Low-Cost Plan Is Efficient and the High-Cost Plan Carries More Information Than the Benchmark If φ < 1/2 and Less If φ > 1/2Research Paper

Data brokers such as Acxiom, Nielsen and Oracle, and data generators such as Google and Facebook, sell processed consumer data to firms that use it to decide whom to target, whom to lend to, or which market to enter. The U.S. Federal Trade Commission's 2014 report on data brokers distinguishes two products: a marketing list, which carries contact…

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

Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria 2: For Submodular Valuations the Bluff Profile Is a Tight 1/2-Approximate Pure Nash Equilibrium of Round-RobinResearch Paper

Dividing indivisible goods among agents without money is a basic problem of fair division. The most widely used procedure is Round-Robin: the agents take turns, in a fixed order, picking their favourite remaining good. For agents with additive valuations, Round-Robin run on the agents' true preferences produces an allocation that is envy-free up to one good…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria 1: For Cancelable Valuations the Bluff Profile Is an Exact Pure Nash Equilibrium of Round-RobinResearch Paper

Round-Robin is the simplest allocation procedure for indivisible goods: agents take turns, in a fixed order, and at each turn the active agent takes her favourite good among those still available. Run on truthful preferences with additive valuations it returns an allocation that is envy-free up to one good (EF1), which is why it is the default baseline of…

6 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 4: Bundling k ≥ 2 I.I.D. Goods Guarantees a Fraction c/log k of the Optimal RevenueResearch Paper

A seller with several goods and a single buyer is the smallest setting in which multi-dimensional mechanism design differs from the one-good theory. For one good, Myerson's theorem (Myerson 1981) says the optimal mechanism posts a price. For two or more goods the optimal mechanism may use lotteries, may be non-monotone in the buyer's values, and is in…

15 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 3: Selling k ≥ 2 Independent Goods Separately Guarantees a Fraction c/log² k of the Optimal RevenueResearch Paper

A seller who knows the distributions of a buyer's values for several goods can, in principle, design a mechanism that offers lotteries and prices conditional on the buyer's reported values. Finding the best such mechanism can be difficult even with two goods. Separate selling is much simpler: choose a one-good price for each item and let the buyer decide…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 1: For Independent Groups of Goods Y and Z, Rev(Y, Z) ≤ Rev(Y) + Rev(Z) + BRev(Y) + BRev(Z)Research Paper

A seller who offers several goods to a buyer with private values has to choose a selling mechanism. For one good the optimal mechanism is known: post the best take-it-or-leave-it price (Myerson 1981). For two or more goods the optimal mechanism can be complicated: it may use lotteries, its menu may be infinite, and it may not be computable in closed form…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Double Counting in Supply Chain Carbon Footprinting II: A Carbon Leader Paying Linear Emission-Contingent Rules That Double-Count Internally Earns Its Effort-Contracting ProfitResearch Paper

Firms increasingly account for, and offset, the greenhouse-gas emissions of their entire supply chain, not only their own operations. Emissions in a supply chain are often jointly produced: the footprint of one process (transport, packaging, a molten-bulk delivery) depends on the abatement efforts of several firms at once. When each firm is charged for…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Double Counting in Supply Chain Carbon Footprinting I: With Joint Carbon Production, Every Differentiable Increasing Payment Rule That Makes the Social First-Best a Nash Equilibrium Double-CountsResearch Paper

Carbon accounting assigns emissions from a shared supply-chain process to firms that can reduce them. If more than one firm can change the same emissions, charging each firm only a share may leave each with too little incentive to abate. Caro, Corbett, Tan and Zuidwijk study the conflict between avoiding double counting in an emissions ledger and inducing…

7 thms3 active users
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 3: A Coalition Technology Satisfying Gross Substitutes for m + 1 Identical Firms Has a Strict Core AllocationResearch Paper

Workers can form groups and produce an output that they divide through salaries. A group may object to a proposed allocation when it can pay all of its members at least as much and one member more. The central question is whether any allocation survives every such objection. Kelso and Crawford's 1982 paper gives a sufficient condition based on how an…

6 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 4: Without Ties the Salary-Adjustment Process Reaches the Firm-Optimal Discrete Strict Core AllocationResearch Paper

Labor markets match heterogeneous workers to heterogeneous firms, and the terms of each match — the salary — are negotiated. Kelso and Crawford (Econometrica 50 (1982)) studied such a market in which a firm may hire many workers, its output depends on the whole set it hires, and salaries are set worker by worker. Their model contains the marriage problem of…

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

Job Matching, Coalition Formation, and Gross Substitutes 2: Under Gross Substitutes Every Job-Matching Market with Continuous Salaries Has a Strict Core AllocationResearch Paper

Labour markets match workers to firms that hire teams: a firm's output depends on the whole set of workers it employs, while each worker holds one job. A salary agreement is stable when no firm and group of workers can renegotiate among themselves to the benefit of all of them. Shapley and Shubik (1971) showed that such stable outcomes exist when each firm…

6 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

On Cores and Indivisibility 2: Gale's Top Trading Cycles Give a Core Allocation Supported by Competitive PricesResearch Paper

Markets for indivisible goods, in which each participant owns one unit and wants one unit (houses, kidneys in paired donation, dormitory rooms, school seats), cannot be analysed with the convexity assumptions of classical general equilibrium theory. Shapley and Scarf (1974) introduced the housing market to ask whether the two central solution concepts of…

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

Job Matching, Coalition Formation, and Gross Substitutes 1: Under Gross Substitutes the Salary-Adjustment Process Reaches a Discrete Core Allocation in Finitely Many RoundsResearch Paper

Labor markets match workers to firms, and the terms of each match (the salary) are negotiated along with the match itself. A firm's output depends on the whole team it hires, so a firm cares about sets of workers, not individual workers one at a time. Kelso and Crawford (1982) asked when such a market has a stable outcome, the core, in which no firm and…

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

Optimal Auction Design: Giving the Object to a Bidder with the Highest Priority Level c̄ᵢ(tᵢ) ≥ t₀ and Charging (6.8) Is an Optimal Auction MechanismResearch Paper

A seller with one indivisible object must decide whether to keep it or transfer it to one of several bidders whose values she does not observe. The allocation and the payment rule affect what bidders choose to report. Myerson's 1981 paper identifies a revenue-maximizing rule when bidders' private value estimates are independent, their densities are…

13 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 3: Order-Oblivious Posted Prices 2-Approximate the Optimal Revenue under a Uniform Matroid ConstraintResearch Paper

Myerson's optimal auction (Myerson 1981) maximizes a seller's expected revenue when buyers have independent private values, but it is a sealed-bid mechanism: every buyer reports a value, and the allocation and payments are computed from all reports at once. Real sellers more often post prices: buyers arrive, each sees a take-it-or-leave-it price, and buys…

10 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine Learning·Captain: mikedeng1

How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design 2: Neutral Affine Maximizers Have Pseudo-Dimension at Least ⌊n/2⌋Research Paper

In data-driven algorithm design, an algorithm or mechanism comes with a vector of tunable parameters ρ\rhoρ, and the parameters are chosen by optimizing average performance over sample instances drawn from an unknown distribution. How many samples suffice for the empirical optimum to be near-optimal in expectation is governed by the pseudo-dimension of the…

6 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

An Introduction to the Theory of Mechanism Design XI: Optimal Sequential Screening by Option ContractsTextbook

Many sales are contracted before the buyer knows what the good is worth to her. An airline sells a ticket months before the trip, a hotel sells a refundable or non-refundable room before the traveller's plans are settled, and a supplier signs a capacity contract before demand is realised. At the time of contracting the buyer holds some private information…

18 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

An Introduction to the Theory of Mechanism Design X: Robust Mechanism Design — Belief Revelation on Finite Type SpacesTextbook

Classical Bayesian mechanism design assumes that the designer knows the agents' beliefs about each other: typically a commonly known prior over independent private values. Wilson's critique (1987) observed that mechanisms tuned to such a prior can depend on details that no designer knows, and a literature on robust mechanism design replaced the fixed prior…

19 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

An Introduction to the Theory of Mechanism Design IX: Monotone Direct Mechanisms Are Dictatorial (Gibbard–Satterthwaite)Textbook

Voting rules, committee procedures and any other method that turns individual rankings into one collective choice face the same question: can the rule be designed so that no participant ever gains by misreporting their ranking? The Gibbard–Satterthwaite theorem (Gibbard, 1973; Satterthwaite, 1975) answers no. When at least three alternatives can be chosen…

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

An Introduction to the Theory of Mechanism Design VII: Crémer–McLean Full Surplus Extraction with Correlated TypesTextbook

Bayesian mechanism design asks which collective decisions and payments a designer can implement when every agent holds private information, the type, drawn from a commonly known prior. Most of the classical theory (Myerson's optimal auction, the Myerson–Satterthwaite impossibility, the public goods results) assumes that types are independent. Once types are…

10 thms3 active usersReviewed
🏆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
PreviousPage 3 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