View source for Myerson–Satterthwaite theorem

{{Short description|Result in mechanism design and economics of asymmetric information}}
The '''Myerson–Satterthwaite theorem''' is an important result in [[mechanism design]] and the economics of [[information asymmetry|asymmetric information]], and named for [[Roger Myerson]] and [[Mark Satterthwaite]].<ref>{{cite journal |last=Myerson |first=Roger B. |author-link=Roger B. Myerson |author2=Mark A. Satterthwaite |year=1983 |title=Efficient Mechanisms for Bilateral Trading |journal=Journal of Economic Theory |volume=29 |issue= 2|pages=265–281 |url= http://www.kellogg.northwestern.edu/research/math/papers/469.pdf|doi=10.1016/0022-0531(83)90048-0 |hdl=10419/220829 |hdl-access=free }}</ref>  Informally, the result says that there is no efficient way for two parties to trade a good when they each have secret and probabilistically varying valuations for it, without the risk of forcing one party to trade at a loss.

The Myerson–Satterthwaite theorem is among the most remarkable and universally applicable negative results in economics—a kind of negative mirror to the [[fundamental theorems of welfare economics]].{{Citation needed|reason=According to who and why?|date=May 2022}} It is, however, much less famous than those results or [[Arrow's impossibility theorem|Arrow's earlier result on the impossibility of satisfactory electoral systems]].

== Notation ==
There are two agents: Sally (the seller) and Bob (the buyer). Sally holds an item that is valuable for both her and Bob. Each agent values the item differently: Bob values it as <math>v_B</math> and Sally as <math>v_S</math>. Each agent knows his/her own valuation with certainty, but knows the valuation of the other agent only probabilistically:
* For Sally, Bob's valuation is represented by a [[probability density]] function <math>f_B</math> which is positive in the range <math>[\underline{B},\overline{B}]</math>. The corresponding cumulative distribution function is <math>F_B</math>.
* For Bob, Sally's valuation is represented by a probability density function <math>f_S</math> which is positive in the range <math>[\underline{S},\overline{S}]</math>. The corresponding cumulative distribution function is <math>F_S</math>.

A ''direct bargaining mechanism'' is a mechanism which asks each agent to report his/her valuation of the item, then decides whether the item will be traded and at what price. Formally, it is represented by two functions:
* The ''trade-probability'' function, <math>t(v'_B,v'_S)</math>, determines the probability that the item will be transferred from the seller to the buyer (in a deterministic mechanism, this probability is either 0 or 1, but the formalism also allows random mechanisms).
* The ''price'' function, <math>p(v'_B,v'_S)</math>, determines the price that Bob should pay to Sally. Note that the reported values are marked by <math>v'</math> since they do not equal the real values.
Note that, thanks to the [[revelation principle]], the assumption that the mechanism is direct does not lose generality.

Every agent knows his value and knows the mechanism. Hence, every agent can calculate his expected gain from the trade. Since we are interested in mechanisms which are truthful in equilibrium, we assume that each agent assumes that the other agent is truthful. Hence:
* For Sally, the expected gain is the expected payment minus the expected loss from giving the object:
:: <math>U_S(v_S,v'_S) = \int_{u_B=\underline{B}}^{\overline{B}} p(v'_S,u_B)f_B(u_B) \,du_B  - v_S \int_{u_B=\underline{B}}^{\overline{B}} t(v'_S,u_B)f_B(u_B)\,du_B </math>
* For Bob, the expected gain is the expected gain from getting the object minus the expected payment:
:: <math>U_B(v_B,v'_B) = v_B \int_{u_S=\underline{S}}^{\overline{S}} t(u_S,v'_B)f_S(u_S)\,du_S - \int_{u_S=\underline{S}}^{\overline{S}} p(u_S,v'_B)f_S(u_S)\,du_S </math>

== Requirements ==
{{See|Double auction#requirements}}

Myerson and Satterthwaite study the following requirements that an ideal mechanism should satisfy.

# '''[[Individual rationality]]''' (IR): The expected value of both Bob and Sally should be non-negative (so that they have an initial incentive to participate). Formally: <math>U_S(v_S,v_S)\geq 0</math> and <math>U_B(v_B,v_B)\geq 0</math>.
# '''Weak balanced budget''' (WBB): The auctioneer should not have to bring money from home in order to subsidize the trade.
# '''[[Nash equilibrium]] [[incentive compatibility]]''' (NEIC): for every agent, if the other agent reports the true value, then the best response is to report the true value too. In other words, no one should want to lie. Formally: <math>\forall v'_s: U_S(v_S,v_S)\geq U_S(v_S,v'_S)</math> and <math>\forall v'_B: U_B(v_B,v_B)\geq U_B(v_B,v'_B)</math>.
# '''Ex-post [[Pareto efficiency]]''' (PE): the item should be finally given to the agent who values it the most. Formally: <math>t(v_B,v_S)=1</math> if <math>v_B>v_S</math> and <math>t(v_B,v_S)=0</math> if <math>v_B<v_S</math>.

== Statement ==
If the following two assumptions are true:
* The intervals <math>[\underline{B},\overline{B}]</math> and <math>[\underline{S},\overline{S}]</math> have a non-empty intersection.
* The [[probability density function|probability densities]] for the valuations are strictly positive on those intervals.

then, there is no mechanism which satisfies the four properties mentioned above (IR, WBB, NEIC and PE).

== Extensions ==
Various variants of the Myerson–Satterthwaite setting have been studied.

# Myerson and Satterthwaite considered a single buyer and a single seller. When there are many buyers and sellers, the inefficiency asymptotically disappears.<ref>{{Cite journal|title = Convergence to Efficiency in a Simple Market with Incomplete Information|jstor = 2951506|journal = Econometrica|volume = 62|issue = 5|pages = 1041–1063|doi = 10.2307/2951506|first1 = Aldo|last1 = Rustichini|first2 = Mark A.|last2 = Satterthwaite|first3 = Steven R.|last3 = Williams|date = 1994|url = http://www.kellogg.northwestern.edu/research/math/papers/995.pdf}}</ref> However, this is only true in the case of private goods; in the case of public goods the inefficiency is aggravated when the number of agents becomes large.<ref>{{Cite journal|title = Pollution claim settlements under private information |journal = Journal of Economic Theory|date = 1989|pages = 307–333|volume = 47|issue = 2|doi = 10.1016/0022-0531(89)90022-7|first = Rafael|last = Rob |author-link=Rafael Robb }}</ref><ref>{{Cite journal|title = Asymmetric Information Bargaining Problems with Many Agents|journal = The Review of Economic Studies|date = 1990|issn = 0034-6527|pages = 351–367|volume = 57|issue = 3|doi = 10.2307/2298018|first1 = George J.|last1 = Mailath|first2 = Andrew|last2 = Postlewaite|jstor = 2298018}}</ref>
# Myerson and Satterthwaite considered an asymmetric initial situation, in the sense that at the outset one party has 100% of the good and the other party has 0% of the good. It has been shown that ex post efficiency can be attained if initially both parties own 50% of the good to be traded.<ref>{{Cite journal|title = Dissolving a Partnership Efficiently|jstor = 1913602|journal = Econometrica|volume = 55|issue = 3|pages = 615–632|doi = 10.2307/1913602|first1 = Peter|last1 = Cramton|first2 = Robert|last2 = Gibbons|first3 = Paul|last3 = Klemperer|date = 1987|citeseerx = 10.1.1.456.4564}}</ref><ref>{{Cite journal|title = A simple status quo that ensures participation (with application to efficient bargaining)|journal = Theoretical Economics|date = 2011|issn = 1555-7561|pages = 109–125|volume = 6|issue = 1|doi = 10.3982/TE591|first1 = Ilya|last1 = Segal|first2 = Michael D.|last2 = Whinston|doi-access = free|hdl = 10419/150149|hdl-access = free}}</ref>
# The latter result has been extended to settings in which the parties can make unobservable ex ante investments in order to increase their own valuations.<ref>{{Cite journal|title = Simple contracts, renegotiation under asymmetric information, and the hold-up problem|journal = European Economic Review|date = 2002|pages = 169–188|volume = 46|issue = 1|doi = 10.1016/S0014-2921(01)00088-5|first = Patrick W.|last = Schmitz|url = https://mpra.ub.uni-muenchen.de/12530/1/MPRA_paper_12530.pdf}}</ref><ref>{{Cite journal|title = Contractual Solutions to the Hold-Up Problem|journal = The Review of Economic Studies|date = 1992|issn = 0034-6527|pages = 777–793|volume = 59|issue = 4|doi = 10.2307/2297997|first = William P.|last = Rogerson|jstor = 2297997|hdl = 10419/221232| url=http://www.kellogg.northwestern.edu/research/math/papers/873.pdf |hdl-access = free}}</ref> Yet, ex post efficiency cannot be achieved if the seller's unobservable investment increases the buyer's valuation, even if only the buyer has private information about his or her valuation.<ref>{{Cite journal|title = On the Interplay of Hidden Action and Hidden Information in Simple Bilateral Trading Problems|journal = Journal of Economic Theory|date = 2002|pages = 444–460|volume = 103|issue = 2|doi = 10.1006/jeth.2001.2790|first = Patrick W.|last = Schmitz|citeseerx = 10.1.1.584.1856}}</ref><ref>{{Cite journal|title = Subgame-Perfect Implementation Under Information Perturbations*|journal = The Quarterly Journal of Economics|date = 2012|issn = 0033-5533|volume = 127|issue = 4|doi = 10.1093/qje/qjs026|first1 = Philippe|last1 = Aghion|first2 = Drew|last2 = Fudenberg|first3 = Richard|last3 = Holden|first4 = Takashi|last4 = Kunimoto|first5 = Olivier|last5 = Tercieux|at = Section V|citeseerx = 10.1.1.224.2883}}</ref>
# Another impossibility result where only one party has private information about its valuation can be shown to hold when the outside option payoffs are not exogenously given.<ref>{{Cite journal|title = Decentralization, Externalities, and Efficiency|journal = The Review of Economic Studies|date = 1995|issn = 0034-6527|pages = 223–247|volume = 62|issue = 2|doi = 10.2307/2297803|first1 = Peter|last1 = Klibanoff|author-link1=Peter Klibanoff|first2 = Jonathan|last2 = Morduch|jstor = 2297803| url=https://ageconsearch.umn.edu/record/294846/files/ipr084.pdf }}</ref>

== See also ==
* [[Double auction]]

==References==
{{Reflist|30em}}

{{DEFAULTSORT:Myerson-Satterthwaite theorem}}
[[Category:Mechanism design]]