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

Dynamic Development Contests: Probabilistic Change-of-State Disclosure Minimizes the Expected Lead Time of a Budget-Constrained ContestResearch Paper

Governments and firms often buy development work through contests: suppliers race through milestones, and the first to finish gets a prize. Such contests stall when a supplier learns that it has fallen behind and stops working, so the organizer's control over what suppliers learn is a design lever alongside the prize. Khorasani, Körpeoğlu and Krishnan study…

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

Strategy-Proof Multi-Issue Mediation: An Application to Online Dispute Resolution: A Mediation Rule Is Efficient, Individually Rational and Strategy-Proof Iff It Is an Adjacent RuleResearch Paper

Mediation is a dispute resolution method in which a neutral third party helps disputants reach a voluntary agreement short of litigation. Courts in all US states offer some form of it, and online platforms use automated mechanisms to resolve large numbers of small disputes (Kesten and Özyurt, 2018, p.2). A mediator who proposes an outcome from the parties'…

19 thms1 active userReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Bayesian and Randomized Clock Auctions: A Deterministic Single-Price Clock Auction Achieves an O(log⁡log⁡k)O(\log\log k)O(loglogk)-Approximation to the Expected Optimal WelfareResearch Paper

A seller offers a service to a set of buyers, each with a private value, and a feasibility constraint limits which sets of buyers can be served together. This is the basic single-parameter problem of mechanism design. Milgrom and Segal proposed clock auctions for it, and designed one for reallocating radio frequency licenses (Milgrom and Segal 2020). In a…

21 thms1 active userReviewed
Algorithmic Game TheoryBandit AlgorithmsMachine Learning+1·Captain: iris

Bilateral Trade: A Regret Minimization Perspective: Under Realistic Feedback and Independent Bounded-Density Valuations, Scouting Bandits Has Regret O(MT^{2/3}) via an Explicit Bound in T₀, K and αResearch Paper

In bilateral trade a seller and a buyer each hold a private valuation for one good, and an intermediary (a platform or broker) decides at which price the good changes hands. Myerson and Satterthwaite showed that no mechanism can be at once efficient, incentive compatible, individually rational and budget balanced (Myerson–Satterthwaite 1983). Among…

17 thms1 active userReviewed
EconomicsOperations Research·Captain: iris

Price Delegation with Learning Agents: a static separable contract implements the fluid first-best policy to within any ε\varepsilonε under limited liability and limited inventoryResearch Paper

Many firms let their salespeople set prices. A salesperson who spends effort talking to a customer can learn what that customer is willing to pay and quote a price close to it; a salesperson who skips that effort can only quote a price that works on average. The firm sees neither the effort nor the customer's value, only the revenue of each sale, and it can…

13 thms1 active userReviewed
Operations ResearchProbability·Captain: iris

Optimal Relative Performance Criteria in Mean-Field Contribution Games: The Two-Layer Game Has an Equilibrium with the Unique Team-Wise Equilibrium and an Explicit Optimal Ratio-Based RPCResearch Paper

When a team's reward depends on the total effort of its members and the reward is shared equally, every member bears her own effort cost but receives only a small share of what that effort adds. With a continuum of members, each member's effort has no effect on the shared reward, so in a Nash equilibrium nobody works: the extreme case of free riding. Firms,…

19 thms1 active userReviewed
Operations ResearchOptimization·Captain: iris

Optimal Pricing and Introduction Timing of Technology Upgrades in Subscription-Based Services: The DiscriminatoryPricing Algorithm Computes Optimal Prices for Any Fixed Introduction TimesResearch Paper

A provider of a subscription service, such as a cloud platform or a software suite, releases better technology over time. Existing customers do not move to the newest release for free: migrating has a cost, and they compare the benefit with the price they are offered. The provider must decide how much to charge new customers and how much to charge those who…

48 thms1 active userReviewed
EconomicsOperations Research·Captain: iris

Optimal Salesforce Compensation with General Demand and Operational Considerations: neither demand censoring nor inventory delegation lowers the firm's optimal profitResearch Paper

Firms that sell through a sales division or a retail store face two frictions at once. The local agent knows the market better than headquarters (adverse selection), and the agent's selling effort is costly and unobserved (moral hazard). Since Laffont and Tirole (1986) and Rao (1990), the standard remedy has been a menu of linear commission contracts (MLC):…

12 thms1 active userReviewed
Algorithmic Game TheoryEconomicsOperations Research·Captain: iris

How to De-Reserve Reserves: Admissions to Technical Colleges in India: DA-BT is the unique individually rational, meritocratic, non-wasteful, open-first and incentive-compatible mechanismResearch Paper

Admissions to the Indian Institutes of Technology and other centrally funded technical institutions run through a single clearinghouse that allocates tens of thousands of seats each year. Seats at each program are reserved for members of the Scheduled Castes (SC), Scheduled Tribes (ST) and Other Backward Classes (OBC); the rest are open-category seats…

18 thms1 active userReviewed
Algorithmic Game TheoryEconomics·Captain: mikedeng1

Interim Rationalizable Implementation of Functions: Weak Interim Rationalizable Monotonicity and the Weak No-Worst-Rule Condition Suffice for Implementation in Interim Rationalizable StrategiesResearch Paper

A mechanism designer chooses a rule for turning agents’ messages into an outcome. When agents know their own types but have only beliefs about the others, the designer cannot assume that they use a single equilibrium strategy. Interim correlated rationalizability instead keeps every message that is a best response to some belief consistent with the agent’s…

12 thms1 active userReviewed
Algorithmic Game Theory·Captain: mikedeng1

Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria 4: For Subadditive Cancelable Valuations Every α-Approximate Pure Nash Equilibrium of Round-Robin Is α/2-EF1Research Paper

Round-Robin is the simplest procedure for dividing indivisible goods: agents take turns, in a fixed cyclic order, each picking a favourite among the goods still available. When agents have additive valuations and pick truthfully, the resulting allocation is envy-free up to one good (EF1): no agent prefers another agent's bundle once a single good is removed…

7 thms1 active userReviewed
PreviousPage 11 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