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

Approximate Revenue Maximization with Multiple Items 5: Bundling Is Optimal for Two I.I.D. Goods Whose Density on [a, ∞) Satisfies x f′(x) + (3/2) f(x) ≤ 0Research Paper

A seller with several goods and a single buyer of unknown, additive valuation faces the multi-dimensional revenue maximization problem. For one good the answer is classical: by Myerson's theorem (Myerson 1981) a single posted price is optimal. For two or more goods no such simplification exists in general: optimal mechanisms may randomize, may offer menus…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatorics·Captain: mikedeng1

Strategy-Proofness and Arrow's Conditions 1: A Strict Voting Procedure with at Least Three Possible Outcomes Is Strategy-Proof Iff It Is DictatorialResearch Paper

A committee that chooses one alternative by voting would like a voting procedure under which no member can gain by misreporting their preferences. Such a procedure is called strategy-proof. Gibbard (Econometrica 41, 1973) and Satterthwaite (J. Econ. Theory 10, 1975) proved independently that, once at least three outcomes are possible, the only…

12 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Incentive Compatibility and the Bargaining Problem I: The Incentive-Feasible Set Is Compact and Convex, and the Generalized Nash Bargaining Solution over It Exists and Is UniqueResearch Paper

An arbitrator choosing an outcome for several people can ask them about their preferences, but the answer to that question may affect the outcome. A person who expects to gain from a false report may give one. Roger Myerson's 1979 paper puts this incentive problem inside a bargaining model: the arbitrator may randomize over collective choices, and an…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research+1·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 2: Sequential Posted Prices e/(e−1)-Approximate the Optimal Revenue under a Partition Matroid ConstraintResearch Paper

A seller who knows the distributions of buyers' values can maximise expected revenue with Myerson's optimal mechanism (Myerson 1981): collect bids, compute virtual values, serve a feasible set of maximum virtual surplus, and charge threshold payments. Real sellers seldom run such auctions. They post prices: a buyer is offered a take-it-or-leave-it price and…

21 thms4 active users
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research+1·Captain: mikedeng1

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

A seller who must decide whom to serve among several buyers with private values can, in principle, run Myerson's revenue-optimal mechanism: collect bids, compute virtual values, serve the feasible set of largest virtual surplus, and charge threshold payments (Myerson 1981). In practice sellers rarely do this. Retail, ticketing and online platforms mostly…

21 thms4 active users
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Algorithmic Mechanism Design I: MinWork Is a Strongly Truthful n-Approximation Mechanism for Task Scheduling on Unrelated MachinesResearch Paper

Algorithmic mechanism design asks for algorithms whose inputs are held by self-interested parties. Each party reports its private data, the algorithm computes an outcome, and payments are arranged so that no party gains by misreporting. Nisan and Ronen introduced the field in Algorithmic Mechanism Design (Games Econ. Behav. 35, 2001). Their running example…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders IV: A Truthful Value-Query Mechanism for Subadditive BiddersResearch Paper

In a combinatorial auction a seller offers several indivisible items at once, and bidders value bundles of items rather than items one at a time. Allocating the items to maximize total value is the central optimization problem of the area, and it arises in spectrum licensing, procurement and transport contracting (Cramton, Shoham and Steinberg, Combinatorial…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Bargaining under Incomplete Information I: Class A Equilibrium Offer Strategies Satisfy the Linked Differential EquationsResearch Paper

A buyer and a seller negotiate over a single indivisible good. Each knows how much the good is worth to them, but not how much it is worth to the other side. Whether the two will trade, and at what price, then depends on how each party shades its offer to exploit the other's uncertainty. Chatterjee and Samuelson (Bargaining under Incomplete Information,…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

Transparency in Team ContractsResearch Paper

A principal who delegates a project often knows more about its prospects than the people whose effort makes it succeed. Revealing that information changes agents’ incentives and therefore changes the payments needed to obtain their effort. The question is whether a principal can lose substantially by disclosing everything, even when she remains free to…

26 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: Shuze Chen

Stratifying Markets for Efficient TradeResearch Paper

In bilateral trade a seller owns one item and a buyer wants it; each knows only their own cost or value. Myerson and Satterthwaite (1983) showed that no incentive-compatible, individually rational, budget-balanced mechanism trades efficiently whenever the supports of the value and the cost overlap, so the question becomes which simple mechanisms capture a…

30 thms3 active usersReviewed
Algorithmic Game TheoryEconomicsOperations Research+1·Captain: Shuze Chen

On the Power and Limitations of Multiple Intermediaries for Single-Item AuctionsResearch Paper

A seller may be unable to receive buyers' bids directly. Intermediaries can control access to its auction and charge bidders for the right to participate. Competition between those intermediaries might reduce exclusion, but it need not transfer their revenue back to the seller. These are different questions: whether the item reaches the buyer who values it…

16 thms3 active usersReviewed
Algorithmic Game Theory·Captain: mikedeng1

Money Burning Mechanism Design: From Welfare to SurplusResearch Paper

Waiting time and effort can screen people for access to a service, but their costs do not become revenue available to someone else. In such settings, the value of the selected outcome alone misses part of the social cost. The relevant objective is residual surplus: the agents' total value minus the payments they incur. A mechanism can improve its allocation…

16 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research·Captain: iris

Fair Team ContractsResearch Paper

A firm, a research group or an open-source project often pays a team for a joint outcome it cannot observe in detail: it sees whether the project succeeded, not who worked. Combinatorial contract theory models this as a principal who offers each hired agent a linear contract, a share of the success reward, and lets the agents decide whether to exert costly…

28 thms3 active usersReviewed
Algorithmic Game Theory·Captain: iris

Strategyproof Aggregation in Euclidean Spaces: Rigidity and Median OptimalityResearch Paper

In single-facility location, nnn agents report ideal points x1,…,xn∈Rdx_1,\dots,x_n\in\mathbb R^dx1​,…,xn​∈Rd and a mechanism selects one location yyy. Each agent's cost is its Euclidean distance ∥xi−y∥\|x_i-y\|∥xi​−y∥, and the planner wants to keep the total distance small. Agents may misreport, so the mechanism is required to be strategyproof: no agent can move the outcome closer to its true…

46 thms3 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

On the Power of Determinism in Multi-Item AuctionsResearch Paper

A seller with mmm items faces one buyer whose values for the items are private and drawn from a known distribution. The revenue-optimal mechanism for a single item is a posted price (Myerson 1981). For two or more items the optimal mechanism can require lotteries, an infinite menu, and can be non-monotone in the value distribution (Hart and Reny 2015), so the…

23 thms3 active usersReviewed
Operations Research·Captain: iris

Maximizing the Benefits of an On-Demand Workforce: Fill Rate-Based Allocation and Coordination Mechanisms: fill-rate contracts with membership fees achieve system-wide optimal staffingResearch Paper

On-demand staffing platforms supply short-notice workers to restaurants, retailers and warehouses. A firm that uses one decides how many permanent workers to hire before its demand is known and asks the platform to cover the shortfall afterwards. The platform posts a wage, which determines how many self-scheduling workers become available, and then splits…

20 thms3 active usersReviewed
EconomicsOperations ResearchProbability·Captain: iris

The Value of Observing the Buyers’ Arrival Time in Dynamic Pricing: Observing the Buyer’s Arrival Raises the Seller’s Optimal Revenue by a Factor of at Most 4.911Research Paper

A retailer who sells a seasonal good over time faces customers who know that prices may fall and who time their purchases strategically. A large operations literature studies how a seller should set a price path against such forward-looking buyers (for example Besanko and Winston, 1990; Aviv and Pazgal, 2008; Cachon and Swinney, 2009). A basic informational…

12 thms3 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Static Pricing for Multi-unit Prophet Inequalities: The Static Price Equalizing E[min(Xₚ,k)]/k and P[Xₚ ≤ k − 1] Earns at Least φₖ, Its Poisson Value, of the Expected Optimal WelfareResearch Paper

A seller has kkk identical units and faces nnn buyers who arrive one at a time. Each buyer's value is drawn independently from a known distribution, but the arrival order is adversarial and unknown. The simplest selling policy posts one static price to every buyer until the units run out. Prophet inequalities compare such a policy with a prophet who sees all…

23 thms3 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Strategy-Proof Multidimensional Mechanism Design: A Strategy-Proof, Agent-Sovereign Mechanism That Sells Every Object Is Anonymous If and Only If It Is EfficientResearch Paper

When a seller has several different indivisible objects and buyers value bundles additively, the simplest selling procedure is to run one sealed-bid second-price auction per object. The New Zealand government sold cellular management rights tenders this way in 1990 (Remark 3 of Basu–Mukherjee, citing Mueller). Basu and Mukherjee ask which normative axioms…

29 thms3 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Fast Core Pricing for Rich Advertising Auctions: the water-filling algorithm finds an ϵ\epsilonϵ-bidder-optimal core point in O(nlog⁡(n/ϵ))O(n\log(n/\epsilon))O(nlog(n/ϵ)) oracle calls and O(n2log⁡(n/ϵ))O(n^2\log(n/\epsilon))O(n2log(n/ϵ)) timeResearch Paper

Online ad platforms sell a limited number of lines of ad space to advertisers whose ads come in several shapes and sizes, so their preferences over the space are combinatorial and often complementary (Niazadeh et al., arXiv:1610.03564v4, §1). The Vickrey–Clarke–Groves auction can earn little revenue on such preferences. Core-selecting auctions (Ausubel and…

40 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Driver Surge Pricing: Prices m_iτ + z_i q_{i→j}(τ) Make Accepting Every Trip the Unique Optimal Driver Policy When R1/R2 ∈ (C, 1), and Accepting All Surge Trips Optimal for Every R1 < R2Research Paper

Ride-hailing platforms pay drivers per trip, and drivers are free to decline requests. When demand fluctuates, a trip accepted now also decides where and when the driver will be free next. During a surge (a period of high demand and high pay) a long trip keeps a driver busy after the surge may have ended, so a driver may rationally decline trips the…

20 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Pricing with Samples: Posting 0.76 Times a Single Sample Earns at Least 64% of the Optimal Revenue Against Every Monotone Hazard Rate DistributionResearch Paper

A seller who knows the distribution FFF of a buyer's value can post the revenue-maximizing price. In practice the seller rarely knows FFF; often it has only a handful of past observations. Pricing with samples asks how much revenue such data can guarantee: the seller sees NNN independent draws from FFF, posts a price that depends on them, and is judged by the…

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

Optimal Monopoly Mechanisms with Demand Uncertainty: When All Consumers Find the Low-Demand State More Likely, State-by-State Monopoly Pricing Is an Optimal BIC and EIR MechanismResearch Paper

A monopolist selling to a large market of unit-demand consumers with a known demand curve cannot do better than posting a single price (Myerson 1981; Bulow and Roberts 1989). When the demand curve itself is uncertain, consumers' valuations are correlated through the aggregate state, and the picture changes. Crémer and McLean (1985, 1988) showed that with…

10 thms3 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Information Nudges and Self-Control: An Optimal Incentive-Compatible Information Nudge Is a Cutoff MechanismResearch Paper

Warnings about health, financial or environmental risks are among the most common policy instruments: cigarette packs carry risk statements, doctors tell patients which risk group they belong to, and retirement planners report survival probabilities. Standard decision theory says that more accurate information can only help a decision maker. That conclusion…

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

New Constructions of Obviously Strategyproof Mechanisms: No OSP Mechanism for Scheduling Identical Jobs on Related Machines with Three-Value Domains Is Better Than √n-ApproximateResearch Paper

A mechanism is strategyproof when truth-telling is a dominant strategy for every agent. Experimental and theoretical work has found that this guarantee is fragile in practice: agents faced with a sealed-bid second-price auction often misreport, while the same agents bid truthfully in the strategically equivalent ascending clock auction. Li (Obviously…

6 thms3 active usersReviewed
PreviousPage 2 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