Econ 504

Professor: John Nachbar

March 1, 2011

Notes on the Myerson-Satterthwaite Theorem

1 Overview
The Myerson-Satterthwaite Theorem (MS) is an impossibility result on bargaining
with asymmetric information.1 One player, the seller, owns one unit of an indivisible
object. The seller values the object at c, which I refer to as the seller’s type. Another
player, the buyer, values the object at v, which I refer to as the buyer’s type. Each
player knows her own type but not her opponent’s.
MS says that, subject to certain restrictions on the joint distribution of c and
v, one cannot simultaneously have ex post efficiency, budget balance, and individual
rationality. “Ex post efficiency” means that, for any (c, v), trade occurs when the
buyer values the object more than the seller (v > c) but not when the reverse is
true (v < c). “Budget balance” means that, for any (c, v), the seller receives exactly
what the buyer pays; no third party subsidizes or taxes the transaction. “Individual
rationality” means that, for any (c, v), no player would strictly prefer to opt out of
the bargaining. One can construct games that satisfy ex post efficiency and budget
balance, and one can construct games that satisfy ex post efficiency and individual
rationality. So it is the combination of all three criteria that causes a problem.
Put differently, if one assumes budget balance and individual rationality, as one
often does in specifying models of bargaining, then, again subject to restrictions on
the joint distribution of c and v, bargaining cannot be ex post efficient. This does
not say that the outcome will be inefficient for all values of c and v, only that it will
be inefficient for some values. For many standard bargaining models, the inefficiency
can be large (on the order of 25%) in expectation in terms of surplus lost.
On one level, an impossibility result of this sort should not be too surprising.
It is reasonably intuitive that, with asymmetric information, players may, in at-
tempting to drive a hard bargain, sometimes fail to trade even when trade would
be worthwhile. Labor strikes may be an example of inefficient bargaining, at least
in part.
But what is very surprising is how general MS is. One might have expected the
result to say something like, “of the following 26 bargaining games, not one yields ex
post efficiency, budget balance, and individual rationality simultaneously.” Instead,
MS applies to all bargaining games.
MS is at least partly a small numbers problem. There are games, in particular
auctions, for which the expected inefficiency, while still positive, becomes vanishingly
1
The original cite is Myerson and Satterthwaite (1983). The proof here follows Krishna (2009).

1
small as the number of players grows large.2

2 The basic setup

The seller’s type c is distributed on [c, c] while the buyer’s type v is distributed
on [v, v]. As is standard in Bayesian games, I assume that the joint distribution
governing (c, v) is part of the description of the game and in particular is known
to both players. I assume that the joint distribution is independent and that the
marginal distributions over [c, c] and [v, v] have strictly positive density.
By a bargaining game I mean any Bayesian game between a buyer and seller
with the following structure.
The seller observers c and then chooses an action as ∈ As . Note that as could
itself be a complicated extensive form strategy. Similarly, the buyer observes v then
chooses an action ab ∈ Ab .
A pure strategy for the seller in the Bayesian game is then a function φs : [c, c] →
As . A pure strategy for the buyer is a function φb : [v, v] → Ab .
The action profile (as , ab ) determines outcomes via the functions π : As × Ab →
[0, 1], τs : As × Ab → R, and τb : As × Ab → R.
π(as , ab ) is the probability that the buyer gets the object. In most bargaining
games of interest, π takes values either 0 or 1.
τs (as , ab ) is the payment received by the seller while τb (as , ab ) is the payment
made by the buyer. I do not assume that τs (as , ab ) = τb (as , ab ). If τs (as , ab ) 6=
τb (as , ab ) then some third party (the “government”) must make up the difference by
taxing or subsidizing.
Finally, payoffs depend on types and on outcomes. If the type profile is (c, v)
and the outcome profile is (q, ts , tb ), then the expected payoff to the seller (net of
the cost c) is
(1 − q)c + ts − c = −qc + ts
and the expected payoff to the buyer is

qv − tb .

Note that preferences are risk neutral.

Remark 1. The payoff specification seems to rule out games in which a payment
is made only when the object is transferred. This would be unfortunate, because
many standard bargaining games have this feature. In fact, such games have not
been ruled out. One merely has to reinterpret ts and tb as expected payments. For
example, suppose that the seller receives the payment t̂s if the object is transferred,
but no payment if it is not. In expectation, therefore, he receives q t̂s . Simply let
ts = q t̂s . This trick works because of risk neutrality. 
2
The classic cite is Rustichini, Satterthwaite, and Williams (1994); for a much more general
treatment, see Cripps and Swinkels (2003)

2
 If (φs , φb ) is a NE then, for each c, φs maximizes the seller’s expected payoff,
where the expectation is over the buyer’s action, which depends on the buyer’s value,
which the seller does not know. With this as motivation, I define the following
additional notation.
Fix (φs , φb ). Given c, and hence φs (c) = as , define Qs (c) = Ev [π(ac , φb (v))]
and Ts (c) = Ev [τs (ac , φb (v))]. In words, Qs (c) is the seller’s expectation, given the
strategy profile and given c, of the probability that the good will be traded. Ts (c) is
the seller’s expectation, given the strategy profile and given c, of the payment she will
receive. Analogously, given v, and hence φb (v) = ab , define Qb (v) = Ec [π(φs (c), ab )]
and Tb (v) = Ec [τb (φs (c), ab )].
Thus, if players play (φs , φb ) then the seller, when of type c, has an expected
payoff of
Us (c) = −Qs (c)c + Ts (c),
while the buyer, when of type v, has an expected payoff of
Uv (v) = Qb (v)v − Tb (v).

3 The Statement of the Theorem.

Definition 1. A Nash equilibrium of a bargaining game is ex post efficient iff, for
any (c, v) and associated (q, ts , tb ), q = 1 if c < v and q = 0 if c > v.
Definition 2. A Nash equilibrium of a bargaining game is ex post budget balanced
iff, for any (c, v) and associated (q, ts , tb ), ts = tb . A Nash equilibrium of a bargaining
game is expected budget balanced iff, for Ec,v [ts − tb ] = 0.
If a Nash equilibrium is ex post budget balance then it is expected budget bal-
anced but not necessarily conversely.
Definition 3. A Nash equilibrium of a bargaining game is (interim) individually
rational iff, for any (c, v), Us (c) ≥ 0 and Ub (v) ≥ 0.
Remark 2. A sufficient condition for individual rationality is that the bargaining
game contain an action quit, available to either player, with the property that if
either player quits then the seller retains the object and there is no transfer, in
which case the seller gets c and the buyer gets 0. 
Theorem 1 (Myerson-Satterthwaite Theorem). If v ≤ c and c ≤ v then there does
not exist any NE of any bargaining game that is ex post efficient, expected budget
balanced, and individually rational.
Remark 3. The condition v ≤ c and c ≤ v says that the distributions of c and v
overlap. This condition is necessary for the theorem. Suppose, for example, c < v.
Then trade is always ex post efficient. The “game” in which the good is simply given
to the buyer with a payment of c is ex post efficient, ex post budget balanced, and
individually rational. 

3
Remark 4. The assumption that the joint distribution of c and v is independent
is not innocuous. Suppose, for example, that c is uniformly distributed on [0, 1]
and that v is exactly 2c for every c. Then ex post efficiency calls for trade always.
Consider the game in which the seller announces c∗ (not necessarily equal to the
seller’s true c), the buyer announces v ∗ (ditto), and there is trade iff v ∗ = 2c∗ . If
there is trade, then the buyer pays the seller (v ∗ + c∗ )/2. It is a NE to announce
one’s true type. And this NE is ex post efficient, ex post budget balanced, and
individually rational. For a more general treatment of how MS can fail if types are
correlated, see McAfee and Reny (1992). 

4 The Proof of the Theorem.

Fix a bargaining game and any NE (φs , φb ) of that game. (I could easily handle
mixed strategy equilibria as well but for notational convenience I will not do so.)
The outline of the proof is as follows. If the NE is expected budget balanced,
then Ec,v [tb − ts ] = 0, and hence (by iterated expectation), Ec,v [Tb (v) − Ts (c)] =
0. The proof shows that if the NE is ex post efficient and individually rational,
then Ec,v [Tb (v) − Ts (c)] < 0, meaning that bargaining will be ex post efficient and
individually rational only if some third party provides a subsidy. As you will see,
the required subsidy is large.
I begin by recording some consequences of the assumption that (φs , φb ) is a NE.
If (φs , φb ) is a NE, then no deviation by the seller, say to φ̃s , can be profitable. One
particular deviation is for the seller, when of type c, to play φs (c∗ ) = a∗s instead of
φs (c) = as . Playing a∗s when of type c would generate a payoff of

−Qs (c∗ )c + Ts (c∗ ).

Therefore, if φs is optimal then, for any c and c∗ , it must be that

Us (c) = −Qs (c)c + Ts (c) ≥ −Qs (c∗ )c + Ts (c∗ )

and conversely

Us (c∗ ) = −Qs (c∗ )c∗ + Ts (c∗ ) ≥ −Qs (c)c∗ + Ts (c).

Remark 5. These inequalities are called incentive compatibility conditions for the
seller. 
The above inequalities imply,

Us (c∗ ) − Us (c) ≥ −Qs (c)c∗ + Ts (c) − Us (c)

= −Qs (c)c∗ + Ts (c) − [−Qs (c)c + Ts (c)]
= −Qs (c)(c∗ − c).

4
Similarly,
Us (c∗ ) − Us (c) ≤ Us (c∗ ) − [−Qs (c∗ )c + Ts (c∗ )]
= −Qs (c∗ )c∗ + Ts (c∗ ) − [−Qs (c∗ )c + Ts (c∗ )]
= −Qs (c∗ )(c∗ − c).
Combining,
−Qs (c)(c∗ − c) ≤ Us (c∗ ) − Us (c) ≤ −Qs (c∗ )(c∗ − c). (1)
If c∗ > c, this implies −Qs is weakly increasing in c, hence Qs is weakly decreasing.
This should be intuitive: as c increases, it is increasingly unlikely that trade is
worthwhile, so the probability of trade should decrease.
Since −Qs is weakly increasing, −Qs is (Riemann) integrable.3 By the definition
of the Riemann integral in terms of upper and lower integrals, it follows from (1)
that for any c ∈ [c, c],
Z c
Us (c) − Us (c) = −Qs (x) dx. (2)
c

Remark 6. The following intuition for (2) may be helpful. Assume for the moment
that Qs and Ts are differentiable.4 Let Vsc (c∗ ) be the expected payoff to a seller
of type c when she plays φs (c∗ ) = a∗s . Thus, Vsc (c∗ ) = −Qs (c∗ )c + Ts (c∗ ). If φs
is optimal, then, given c, Vsc (c∗ ) must be maximized at c∗ = c. The first order
condition for this is
DVsc (c) = −DQs (c)c + DTs (c) = 0.
Therefore,
DUs (c) = −Qs (c) − DQs (c)c + DTs (c) = −Qs (c).
(This argument is just the Envelope Theorem.) Integrating DUs (c) = −Qs (c) gives
(2). 
By an analogous argument, one can show that for the buyer,
Z v
Ub (v) − Ub (v) = Qb (x) dx. (3)
v

Rearranging (2) and (3) yields the following .

Theorem 2. In any NE of any bargaining game,
Z c
Us (c) = Us (c) + Qs (x) dx, (4)
Zc v
Ub (v) = Ub (v) + Qb (x) dx. (5)
v
3
Rudin (1976), Theorem 6.9.
4
I cannot, in fact, freely make this assumption because the differentiability of these functions
depend on (φs , φb ), which are endogenous.

5
 It is convenient at this point to record a technical fact about individual ratio-
nality. In words, the following theorem says that a NE will be individually rational
iff it is individually rational for the seller and buyer types who are least likely to
trade.

Theorem 3. (φs , φb ) satisfies individual rationality iff Us (c) ≥ 0 and Ub (v) ≥ 0.

Proof. If Us (c) ≥ 0 for every c, then in particular Us (c) ≥ 0. So Us (c) ≥ c is

necessary for individual rationality for the seller. To see that it is sufficient, note
that since Qs (c) ≥ 0 for every c, (4) implies that if Us (c) ≥ 0 then Us (c) ≥ 0 for
every c. And similarly for Ub . 

To complete the proof, I argue, as sketched above, that if the NE is ex post

efficient and individually rational, then Ec,v [Tb (v) − Ts (c)] < 0.
Substituting Us (c) = −Qs (c)c + Ts (c) and Ub (v) = Qb (v)v − Tb (v) into (4) and
(5) and rearranging yields
Z c
Ts (c) = Us (c) + Qs (c)c + Qs (x) dx, (6)
c
Z v
Tb (v) = −Ub (v) + Qb (v)v − Qb (x) dx. (7)
v

Now, suppose that the NE is ex post efficient. Then the Qs and Qb functions are
pinned down. In particular, it must be that Qs (c) = Probv [c < v|c] and Qb (v) =
Probc [c < v|v]. This calculation depends only on the type distributions, rather than
on, say, equilibrium strategies. In view of (6) and (7), Ts (c) and Tb (v), and hence
Ec,v [Tb (v) − Ts (c)], are then determined entirely by Us (c) and Ub (v). This implies
the following result.

Theorem 4. Consider any two bargaining games and any two NE of those games.
Suppose that both NE are ex post efficient. If Us (c) is the same in both NE, then
Ts is the same in both NE. And if Ub (v) is the same in both NE then Tb is the same
in both NE.

Remark 7. Theorem 4 is a variant of the Revenue Equivalence Theorem, an impor-

tant result in auction theory. In its general form, the Revenue Equivalence Theorem
was first recorded in Myerson (1981) and Riley and Samuelson (1981). 
Now consider the problem of finding a bargaining game and an associated NE
that is ex post efficient, individually rational, and that makes Ec,v [Tb (v) − Ts (c)] as
large as possible. In view of (6) and (7), I want Us (c) and Ub (v) to be as small
as possible. By Theorem 3, the smallest possible values of Us (c) and Ub (v) are
Us (c) = 0 and Ub (v) = 0.
It is conceivable that there may not be any NE of any bargaining game that is
ex post efficient and for which Us (c) = 0 and Ub (v) = 0. But if any such NE exist,

6
Theorem 4 implies that it maximizes Ec,v [Tb (v) − Ts (c)] over all ex post efficient,
individually rational NE in all bargaining games.
Consider then the following bargaining game, which I call the VCG game in
honor of Vickrey (1962), Clarke (1971), and Groves (1973), who considered games
closely related to this one.
In the VCG game, the seller’s action is to announce a type c∗ ∈ [c, c] and the
buyer’s action is to announce a type v ∗ ∈ [v, v]. Trade occurs iff v ∗ ≥ c∗ . If there is
trade then the buyer pays max{c∗ , v} and the seller receives min{v ∗ , c}. If there is
no trade then there are no payments.
It is weakly dominant in the VCG game for players to tell the truth: φs (c) = c
and φb (v) = v.5 It is immediate that this equilibrium is ex post efficient. Moreover,
Us (c) = 0, since if c = c then either v < c, in which case there is no trade, or v ≥ c,
in which case trade occurs and the seller receives a payment of c. Either way, the
seller gets a net payoff of 0. Similarly, Ub (v) = 0.
Since the equilibrium of the VCG game in weakly dominant strategies is ex
post efficient and satisfies Us (c) = c and Ub (v) = 0, the equilibrium maximizes
Ec,v [Tb (v)−Ts (c)] over all ex post efficient, individually rational NE in all bargaining
games.
But in this equilibrium, for any (c, v) such that v > c,

tb (c, v) − ts (c, v) = c − v < 0.

That is, whenever trade occurs (ignoring the cases c = v, which occur with zero
probability), some third party must subsidize the players by an amount equal to the
total surplus from trade, namely v − c. Loosely, the VCG game works by bribing the
players to tell the truth, and the bribe is huge, equal to the trade surplus itself. Since
tb (c, v) − ts (c, v) < 0 whenever trade occurs, this implies that Ec,v [Tb (v) − Ts (c)] < 0.
Summing up, for any bargaining game, if a NE equilibrium is ex post efficient
and individually rational then it is not budget balanced, and indeed requires an
expected subsidy as large as the expected gain from trade. This proves Theorem 1.

References
Clarke, E. (1971): “Multipart Pricing of Public Goods,” Public Choice, 2, 19–33.

Cripps, M., and J. Swinkels (2003): “Depth and Efficiency in Large Double
Auctions,” Washington University.

Groves, T. (1973): “Incentives in Teams,” Econometrica, 41, 617–631.

5
Briefly, consider the seller. Given c, suppose the seller reports c∗ > c. The only circumstance
in which lying in this way changes one’s payoff is when v ∗ ∈ (c, c∗ ]. In this case, there is trade if the
seller tells the truth, in which case the seller gets a payoff of v ∗ , while there is no trade if the seller
reports c∗ , in which case the seller gets a payoff of c. So lying yields a lower payoff than telling the
truth. The other cases are similar.

7
Krishna, V. (2009): Auction Theory. Academic Press, second edn.

McAfee, P., and P. Reny (1992): “Correlated Information and Mechanism De-
sign,” Econometrica, 60(2), 395–421.

Myerson, R. (1981): “Optimal Auction Design,” Mathematics of Operation Re-

search, 6, 58–73.

Myerson, R., and M. Satterthwaite (1983): “Efficient Mechanisms for Bilat-

eral Trading,” Journal of Economic Theory, 28, 265–81.

Riley, J., and W. Samuelson (1981): “Optimal Auctions,” American Economic

Review, 71, 381–392.

Rudin (1976): Principles of Mathematical Analysis. McGraw-Hill, New York, third

edn.

Rustichini, A., M. Satterthwaite, and S. Williams (1994): “Convergence to

Efficiency in a Simple Market With Incomplete Information,” Econometrica, 62,
1041–63.

Vickrey, W. (1962): “Auctions and Bidding in Games,” in Recent Advances in

Game Theory, vol. 29 of Princeton Conference Series, pp. 15–27. Princeton Uni-
versity Press, Princeton.