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

Minimal-Access Rights in School Choice and the Deferred Acceptance Mechanism: deferred acceptance is the only mechanism that is minimal-access stable, strategy-proof and minimal-access monotonicResearch Paper

In many school choice systems a school's priority over applicants has two layers: an absolute priority (an exam score, a grade point average, a lottery number) and a set of minimal-access rights (a sibling at the school, living in its walk zone). The standard practice is to merge the two into adjusted priorities: at each school, every student holding a…

21 thms5 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability+1·Captain: Shuze Chen

A Constant-Factor Approximation to Multidimensional Consumer UtilityResearch Paper

In many allocation problems the designer cares about the welfare of the participants, not revenue: public housing, school seats, medical resources, or platforms that screen users through effort or waiting rather than money. Payments in these settings are "burned": they screen buyers but reach nobody. The designer then maximizes consumer utility, also called …

17 thms4 active usersReviewed
Algorithmic Game TheoryComplexity Theory·Captain: mikedeng1

On the Complexity of Mixed Equilibria in First-Price Auctions with Correlated PriorsResearch Paper

A first-price auction awards a single item to a highest bidder and charges that bidder her own bid. Choosing a bid therefore involves predicting competitors' behavior. Researchers studying auction computation ask whether an equilibrium can be found efficiently from the publicly available description of bidders' information. The setting here allows their…

31 thms4 active usersReviewed
Algorithmic Game Theory·Captain: iris

From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive ValuationsResearch Paper

A buyer with budget B>0B>0B>0 wants to buy services from nnn strategic sellers, each holding a private cost, so as to maximize a value function of the set it buys. This is budget-feasible mechanism design, introduced by Singer (2010). It models procurement in data markets, crowdsourcing and content ecosystems, and it departs from the classical setting because VCG…

58 thms4 active usersReviewed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: iris

Supply-Sensitive Revenue Recovery under Unknown Buyer OrderResearch Paper

A seller with one copy of each of mmm items posts personalized item prices to independent buyers. Revenue benchmarks for this setting usually give every buyer full stock and bound expected allocations; the ex ante capped benchmark of Chawla, Rezvan, Teng and Tzamos (arXiv:2204.01962) and the buy-many benchmark of Chawla, Teng and Tzamos (arXiv:1902.10315) are…

29 thms4 active usersReviewed
Machine LearningOperations Research·Captain: iris

The Power of Two Choices in Dynamic Pricing: As Good As Full Feedback, Instance-WiseResearch Paper

A seller with an unlimited supply of one product meets TTT customers in sequence. Each customer's value is drawn independently from a distribution FFF on [0,1][0,1][0,1] that the seller does not know, and the seller wants to earn, over the TTT rounds, nearly as much as the monopoly price pF∗p^*_FpF∗​ would earn if FFF were known. This dynamic pricing problem is a basic model of…

37 thms4 active usersReviewed
Algorithmic Game TheoryInformation TheoryMachine Learning·Captain: iris

Query-Sample Tradeoffs for Revenue MaximizationResearch Paper

A seller posting a price for a single item to a buyer with an unknown value distribution FFF wants a price whose revenue is close to optimal. Two kinds of data are available. A value sample reveals a buyer's value v∼Fv\sim Fv∼F exactly, as in historical bid data or surveys. A pricing query posts a price ppp and reveals only whether a fresh buyer buys, the bit …

36 thms4 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

In Congestion Games, Taxes Achieve Optimal Approximation: Taxes From the Poisson Relaxation of Minimum Social Cost Have Price of Anarchy at Most the Worst Hardness Factor sup ρ_ℓResearch Paper

In an atomic congestion game (Rosenthal, 1973) each of NNN agents chooses a set of resources, such as the edges of a route, and the cost of a resource depends on how many agents use it. Selfish choices are inefficient: the price of anarchy (Koutsoupias and Papadimitriou, 1999) compares the social cost of the worst equilibrium with the minimum social cost, and…

39 thms4 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

The Pareto Frontier of Inefficiency in Mechanism Design: Second-Price Mechanisms with Relative Reserves Exactly Attain the PoA/PoS Frontier of Anonymous Task-Independent SchedulingResearch Paper

Scheduling tasks on unrelated machines is the problem with which algorithmic mechanism design began (Nisan and Ronen, 1999). The machines are selfish: each one knows its own processing times and may misreport them, and a mechanism must allocate the tasks and pay the machines so that the makespan stays low. For two decades the field studied truthful…

36 thms4 active usersReviewed
Algorithmic Game TheoryComplexity TheoryOperations Research·Captain: iris

Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions: Computing a Welfare-Maximizing Core Outcome Is Σ₂ᵖ-HardResearch Paper

Many markets trade packages of indivisible goods between several buyers and several sellers at once: airport time slots, spectrum licences, transport capacity, emission permits. Such a market is a combinatorial exchange. Its operator chooses who trades which package and at which prices, and wants the outcome to be stable: no group of participants should be…

16 thms4 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Shapley–Scarf Housing Markets: Respecting Improvement, Integer Programming, and Kidney Exchange: With Strict Preferences the Unique Strong Core Allocation Respects ImprovementResearch Paper

In a kidney exchange programme a patient arrives with a willing but incompatible donor, and patients swap donors along cycles so that each patient receives a compatible kidney. The standard model of such swaps is the housing market of Shapley and Scarf (Shapley–Scarf 1974): each agent owns one indivisible object and the agents reallocate the objects among…

14 thms4 active usersReviewed
Algorithmic Game TheoryProbability·Captain: iris

On Simple Mechanisms for Dependent Items: for an Additive Buyer Whose Values Form a Markov Random Field, (2e4Δ+2) SRev+8(e4Δ+1) BRev≥Rev(D)(2e^{4\Delta}+\sqrt2)\,\mathrm{SRev}+8(e^{4\Delta}+1)\,\mathrm{BRev}\ge\mathrm{Rev}(D)(2e4Δ+2​)SRev+8(e4Δ+1)BRev≥Rev(D)Research Paper

A seller with nnn heterogeneous items faces one buyer whose values for the items are private and drawn from a known joint distribution DDD. The revenue-optimal mechanism for this problem is in general randomized, hard to describe, and sensitive to the details of DDD. Two simple mechanisms are used in practice: selling every item separately at its own posted price…

16 thms4 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: Shuze Chen

Pacing Equilibrium in First Price Auction Markets: Existence, uniqueness, and revenue maximization of first price pacing equilibriaResearch Paper

An advertiser buying many impressions must decide how to distribute a limited budget across auctions. Bidding the full value in every auction can exhaust the budget before all opportunities have been considered. A pacing multiplier scales an advertiser's bids by one common factor. The resulting allocation depends on other advertisers' multipliers as well as…

15 thms4 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
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
Operations ResearchOptimization·Captain: mikedeng1

The Important Role of Time Limits When Consumers Choose Their Time in Service: The Revenue-Maximizing IC and IR Mechanism Achieves the First Best and Imposes a Time Limit When Congestion Is HighResearch Paper

In many services the customer, not the provider, decides how long to stay: a gym session, a car-wash bay, an electric-vehicle charger, a call to a help line, a slot on a shared computing resource. Such services are called discretionary. Their congestion depends on how many customers join and on how long each of them stays. Providers manage them with per-use…

10 thms3 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 6: With n Buyers and Dominant-Strategy Implementation, Selling Two Independent Goods Separately Earns at Least Half the Optimal RevenueResearch Paper

A seller who owns several goods and faces buyers with private values must decide how to sell them. The revenue-maximizing mechanism is known in closed form only for one good: for a single buyer it is a posted price, and for several buyers it is Myerson's optimal auction (Myerson 1981). With two or more goods the optimal mechanism may use lotteries, may be…

8 thms3 active usersReviewed
PreviousPage 1 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