View Full Document

How Pervasive is the Myerson-Satterthwaite Impossibility?



View the full content.
View Full Document
View Full Document

2 views

Unformatted text preview:

How Pervasive is the Myerson Satterthwaite Impossibility Abraham Othman and Tuomas Sandholm Computer Science Department Carnegie Mellon University aothman sandholm cs cmu edu Abstract The Myerson Satterthwaite theorem is a foundational impossibility result in mechanism design which states that no mechanism can be Bayes Nash incentive compatible individually rational and not run a deficit It holds universally for priors that are continuous gapless and overlapping Using automated mechanism design we investigate how often the impossibility occurs over discrete valuation domains While the impossibility appears to hold generally for settings with large numbers of possible valuations approaching the continuous case domains with realistic valuation structure circumvent the impossibility with surprising frequency Even if the impossibility applies the amount of subsidy required to achieve individual rationality and incentive compatibility is relatively small even over large unstructured domains 1 Introduction The Myerson Satterthwaite theorem 1983 belongs to a seminal line of impossibility results in mechanism design Its relatives include the results of Arrow 1970 GibbardSatterthwaite 1973 1975 and Green Laffont 1977 These theorems begin by positing a set of prima facie reasonable desiderata and conclude by proving the impossibility of satisfying those desiderata together The Myerson Satterthwaite theorem states that no mechanisms exist that do not run a deficit are ex post efficient Bayes Nash incentive compatible and ex interim individually rational It is one of the most important results in mechanism design It is also important to the field of political economics because it serves as a negative counterweight to the famous Coase theorem 1960 First proposed by Ronald Coase in 1937 before the advent of game theory the theorem claims that with zero cost access to lawsuits and bargaining parties will establish socially efficient outcomes among themselves Thus a free market



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view How Pervasive is the Myerson-Satterthwaite Impossibility? and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view How Pervasive is the Myerson-Satterthwaite Impossibility? and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?