Transcript Patent Pools

Econ 805
Advanced Micro Theory 1
Dan Quint
Fall 2007
Lecture 4 – Sept 18 2007
Today: Necessary and Sufficient Conditions
For Equilibrium
 Problem set 1 online (due 9 a.m. Wed Oct 3); email list
 Last lecture: integral form of the Envelope Theorem holds
in equilibrium of any Independent Private Value auction
where


The highest type wins the object
The lowest possible type gets expected payoff 0
 Today: necessary and sufficient conditions for a particular
bidding function to be a symmetric equilibrium in such an
auction
 Time permitting, stochastic dominance
1
Today’s General Results
 Consider a symmetric independent private values model
of some auction, and a bid function b : T  R+
 Define g(x,t) as one bidder’s expected payoff, given type t
and bid x, if all the other bidders bid according to b
 Under fairly broad (but not all) conditions:
“everyone bidding according to b” is an equilibrium
b strictly increasing and
g(b(t’),t’) – g(b(t),t) = tt’ FN-1(s) ds
2
Necessary Conditions
3
With symmetric IPV, b strictly increasing
implies the envelope theorem
 If everyone bids according to the same bid function b,
 And b is strictly increasing,
 Then the highest type wins,
 And so the envelope theorem holds
 So what we’re really asking here is when a symmetric bid
function must be strictly increasing
4
When must bid functions be increasing?
 Equilibrium strategies are solutions to the maximization
problem maxx g(x,t)
 What conditions on g makes every selection x(t) from x*(t)
nondecreasing?
 Recall supermodularity and Topkis



If g(x,t) has increasing differences in (x,t), then the set x*(t) is
increasing in t (in the strong set order)
For g differentiable, this is when 2g / x t  0
But let t’ > t; if x* is not single-valued, this still allows some points
in x*(t) to be above some points in x*(t’), so it wouldn’t rule out
equilibrium strategies which are decreasing at some points
5
Single crossing and single crossing
differences properties (Milgrom/Shannon)
 A function h : T  R satisfies the strict single crossing
property if for every t’ > t,
h(t)  0  h(t’) > 0
(Also known as, “h crosses 0 only once, from below”)
 A function g : X x T  R satisfies the strict single crossing
differences property if for every x’ > x, the function
h(t) = g(x’,t) – g(x,t) satisfies strict single crossing
 That is, g satisfies strict single crossing differences if
g(x’,t) – g(x,t)  0  g(x’,t’) – g(x,t’) > 0
for every x’ > x, t’ > t
 (When gt exists everywhere, a sufficient condition is for gt to be
6
strictly increasing in x)
What single-crossing differences gives us
 Theorem.* Suppose g(x,t) satisfies strict single crossing
differences. Let S  X be any subset. Let
x*(t) = arg maxx  S g(x,t), and let x(t) be any (pointwise)
selection from x*(t). Then x(t) is nondecreasing in t.




Proof. Let t’ > t, x’ = x(t’) and x = x(t).
By optimality, g(x,t)  g(x’,t) and g(x’,t’)  g(x,t’)
So g(x,t) – g(x’,t) 0 and g(x,t’) – g(x’,t’)  0
If x > x’, this violates strict single crossing differences
* Milgrom (PATW) theorem 4.1, or a special case of theorem 4’ in Milgrom/Shannon 1994
7
Strict single-crossing differences will hold in
“most” symmetric IPV auctions
 Suppose b : T  R+ is a symmetric equilibrium of some auction
game in our general setup
 Assume that the other N-1 bidders bid according to b;
g(x,t)
=
t Pr(win | bid x) – E(pay | bid x)
=
t W(x) – P(x)
 For x’ > x,
g(x’,t) – g(x,t) =
[ W(x’) – W(x) ] t – [ P(x’) – P(x) ]
 When does this satisfy strict single-crossing?
8
When is strict single crossing satisfied by
g(x’,t) – g(x,t) = [ W(x’) – W(x) ] t – [ P(x’) – P(x) ] ?
 Assume W(x’)  W(x) (probability of winning nondecreasing in bid)
 g(x’,t) – g(x,t) is weakly increasing in t, so if it’s strictly positive at t, it’s
strictly positive at t’ > t
 Need to check that if g(x’,t) – g(x,t) = 0, then g(x’,t’) – g(x,t’) > 0
This can only fail if W(x’) = W(x)
 If b has convex range, W(x’) > W(x), so strict single crossing differences
holds and b must be nondecreasing (e.g.: T convex, b continuous)
 If W(x’) = W(x) and P(x’)  P(x) (e.g., first-price auction, since P(x) = x),
then g(x’,t) – g(x,t)  0, so there’s nothing to check
 But, if W(x’) = W(x) and P(x’) = P(x), then bidding x’ and x give the same
expected payoff, so b(t) = x’ and b(t’) = x could happen in equilibrium

 Example. A second-price auction, with values uniformly distributed
over [0,1]  [2,3]. The bid function b(2) = 1, b(1) = 2, b(vi) = vi
otherwise is a symmetric equilibrium.
 But other than in a few weird situations, b will be nondecreasing
9
b will almost always be strictly increasing
 Suppose b(-) were constant over some range of types [t’,t’’]
 Then there is positive probability
(N – 1) [ F(t’’) – F(t’) ] FN – 2(t’)
of tying with one other bidder by bidding b* (plus the additional
possibility of tying with multiple bidders)
 Suppose you only pay if you win; let B be the expected payment,
conditional on bidding b* and winning
 Since t’’ > t’, either t’’ > B or B > t’, so either you strictly prefer to win at
t’’ or you strictly prefer to lose at t’
 Assume that when you tie, you win with probability greater than 0 but
less than 1
 Then you can strictly gain in expectation either by reducing b(t’) by a
sufficiently small amount, or by raising b(t’’) by a sufficiently small
amount
 (In addition: when T has point mass… second-price… first-price…) 10
So to sum up, in “well-behaved” symmetric
IPV auctions, except in very weird situations,
 any symmetric equilibrium bid function will be strictly
increasing,
 and the envelope formula will therefore hold
 Next: when are these sufficient conditions for a bid
function b to be a symmetric equilibrium?
11
Sufficiency
12
What are generally sufficient conditions for
optimality in this type of problem?
 A function g(x,t) satisfies the smooth single crossing
differences condition if for any x’ > x and t’ > t,
 g(x’,t) – g(x,t) > 0 
g(x’,t’) – g(x,t’) > 0
 g(x’,t) – g(x,t)  0 
g(x’,t’) – g(x,t’)  0
 gx(x,t) = 0  gx(x,t+d)  0  gx(x,t – d)
for all d > 0
 Theorem. (PATW th 4.2) Suppose g(x,t) is continuously
differentiable and has the smooth single crossing differences
property. Let x : [0,1]  R have range X’, and suppose x is the
sum of a jump function and an absolutely continuous function. If


x is nondecreasing, and
the envelope formula holds: for every t,
g(x(t),t) – g(x(0),0) = 0t gt(x(s),s) ds
then x(t)  arg maxx  X’ g(x,t)
 (Note that x only guaranteed optimal over X’, not over all X)
13
But…
 Establishing smooth single-crossing differences
requires a bunch of conditions on b
 We can use the payoff structure of an IPV auction
to give a simpler proof
 Proof is taken from Myerson (“Optimal Auctions”),
which we’re doing on Thursday anyway
14
Claim
 Theorem. Consider any auction where the highest bid gets
the object. Assume the type space T has no point masses. Let
b : T  R+ be any function, and define g(x,t) in the usual way.
If


b is strictly increasing, and
the envelope formula holds: for every t,
g(b(t),t) – g(b(0),0) = 0t FN-1(s) ds
then g(b(t),t)  g(b(t’),t), that is, no bidder can gain by making a
bid that a different type would make.
If, in addition, the type space T is convex, b is continuous, and
neither the highest nor the lowest type can gain by bidding
outside the range of b, then everyone bidding b is an
equilibrium.
15
Proof.
 Note that when you bid b(s), you win with probability FN-1(s); let z(s) denote
the expected payment you make from bidding s
 Suppose a bidder had a true type of t and bid b(t’) instead of b(t)
 The gain from doing this is
 g(b(t’), t) – g(b(t), t) = t FN-1(t’) – z(t’) – g(b(t),t)
 = (t – t’) FN-1(t’) + t’ FN-1(t’) – z(t’) – g(b(t),t)
 = (t – t’) FN-1(t’) + g(x(t’),t’) – g(x(t),t)
 Suppose t’ > t. By assumption, the envelope theorem holds, so
 = (t – t’) FN-1(t’) + tt’ FN-1(s) ds
 = tt’ [ FN-1(s) – FN-1(t’) ] ds
 But F is increasing (weakly), so FN-1(t’)  FN-1(s) for every s in the integral, so
this is (weakly) negative
 Symmetric argument holds for t’ < t
 So the envelope formula is exactly the condition that there is never a gain to
deviating to a different type’s equilibrium bid
16
Proof.
 All that’s left is deviations to bids outside the range of b
 With T convex and b continuous, the bid distribution has convex support, so
we only need to check deviations to bids above and below the range of b
 Assume (for notational ease) that T = [0,T]
 If some type t deviated to a bid B > b(T), his expected gain would be
 g(B,t) – g(b(t),t) = [ g(B,t) – g(b(T),t) ] + [ g(b(T),t) – g(b(t),t) ]
 The second term is nonpositive (another type’s bid isn’t a profitable deviation)
 We also know g(x,t) = t Pr(win | bid x) – z(x) has increasing differences in x
and t, so for B > b(T), if g(B,t) – g(b(T),t) > 0, g(B,T) – g(b(T),t) > 0
 So if the highest type T can’t gain by bidding above b(T), no one can
 By the symmetric argument, we only need to check the lowest type’s
incentive to bid below b(0)
 (If b was discontinuous or T had holes, we would need to also check
deviations to the “holes” in the range of b)
 QED
17
So basically, in well-behaved symmetric IPV
auctions,
 b : T  R+ is a symmetric equilibrium if and only if

b is increasing, and

b (and the g derived from it) satisfy the envelope formula
18
Up next…
 Recasting auctions as direct revelation mechanisms
 Optimal (revenue-maximizing) auctions
 Might want to take a look at the Myerson paper, or
the treatment in one of the textbooks

If you don’t know mechanism design, don’t worry, we’ll go
over it
 Meanwhile, since there’s time…
19
A Few Slides on Second-Order
Stochastic Dominance
20
When is one probability distribution less
risky than another?

Two random variables X and Y with the same
mean, with distributions F and G

Three conditions to consider:
1. “Every risk-averse utility maximizer prefers X to Y”, i.e.,
E u(X)  E u(Y) for every nondecreasing, concave u,
or - u(s) dF(s)  - u(s) dG(s)
(also called SOSD)
2. “Y is a mean-preserving spread of X”, or “Y = X + noise”:
$ r.v. Z s.t. Y =d X + Z, with E(Z|X) = 0 for every value of X
3. For every x,
-x F(s) ds  -x G(s) ds

Rothschild-Stiglitz (1970): 1  2  3
21
What does this tell us?

Risk-averse buyers greatly impact auction design –
changes equilibrium strategies – we’ll get to that in
a few lectures (Maskin and Riley)

Risk-averse sellers have less impact – equilibrium
strategies are the same, all that changes is seller’s
valuation of different distributions of revenue

Claim. With symmetric IPV, a risk-averse seller
prefers a first-price to a second-price auction
22
Proof: we’ll show revenue in second-price
auction is MPS of revenue in first-price


Recall that revenue in a second-price auction is v2, and
revenue in a first-price auction is E(v2 | v1)
Let X, Y, and Z be random variables derived from bidders’
valuations, as follows:







X = g(v1)
Z = v2 – g(v1)
Y = v2
where g(t) = 0t s dFN-1(s) / FN-1(t) = E(v2 | v1 = t)
Note that Y = X + Z, and
E(Z | X=g(t)) = E(v2 | v1 = t) – E(v2 | v1 = t) = 0
So Y is a mean-preserving spread of X, so any risk-averse
utility maximizer prefers X to Y
But X is the revenue in the first-price auction, and Y is the
23
revenue in the second-price auction – Q.E.D.
A cool proof SOSD 
“-x F(s) ds  -x G(s) ds everywhere”
 We’ll use the “extremal method” or “basis function method”
 We’ll rewrite our generic (increasing concave) function u(s) as a
positive sum of basis functions
u(s) = - w(q) h(s,q) dq
with w(q)  0, where these basis functions are themselves increasing
and concave
 Then we’ll show that X SOSD Y if and only if
- h(x,q) dF(x)  - h(y,q) dG(y)
for all the basis functions
 (“Only if” is trivial, since h(s,q) is increasing and concave; “if” just
involves multiplying this inequality by w(q) and integrating over q)
24
A cool proof SOSD 
“-x F(s) ds  -x G(s) ds everywhere”
 We’ll do the special case of u twice differentiable. Our basis functions
will be a constant, a linear term, and the functions
h(x,q) = min(x,q)
 Claim is that
u(x) = a + bx + 0 (-u’’(q)) h(x,q) dq
 Note that -u’’(q) is nonnegative, since u is concave
 To see the equality, integrate by parts, with db = -u’’ dq, a = h:
a db
= a b – b da
= –h(x,q)u’(q)|q=- – - –u’(q) 1q<x dq
= –xu’() + constant + -x u’(q) dq
 Since X and Y have the same mean,
- (a+bx) dF(x) = - (a+by) dG(y)
25
A cool proof SOSD 
“-x F(s) ds  -x G(s) ds everywhere”
 So all that’s left is to determine when
- h(s,q) dF(s)  - h(s,q) dG(s)
 Integrate by parts: u = h(s,q), dv = dF(s), LHS becomes
h(,q) F() – h(-q) F(-) – -F(s) hs(s,q) ds
= q – 0 – -F(s) 1s<q ds
= q – -qF(s) ds
 Similarly, the right-hand side becomes q – -qG(s) ds
 So Es~F h(s,q)  Es~G h(s,q)

-qF(s) ds  -qG(s) ds
 So X SOSD Y if and only if this holds for every q
26
(I don’t expect to get to)
First-Order Stochastic Dominance
27
When is one probability distribution “better”
than another?
 Two probability distributions, F and G
 F first-order stochastically dominates G if
- u(s) dF(s)  - u(s) dG(s)
for every nondecreasing function u
 So anyone who’s maximizing any increasing function
prefers the distribution of outcomes F to G
 (Very strong condition.)
 Theorem. F first-order stochastically dominates G if
and only if F(x)  G(x) for every x.
28
Proving FOSD  “F(x)  G(x) everywhere”
 Proof for differentiable u. Rewrite it using a basis consisting of
step functions
dq(s) = 0 if s < q, 1 if s  q
 Up to an additive constant,
u(s) = - u’(q) dq(s) dq
 To see this, calculate
u(s’) – u(s) = - u’(q) (dq(s’) – dq(s)) dq = ss’ u’(q) dq
 So F FOSD G if and only if - dq(s) dF(s)  - dq(s) dG(s) for
every q
29
Proving FOSD  “F(x)  G(x) everywhere”
 But
- dq(s) dF(s) = Pr(s  q) = 1 – F(q)
and similarly
- dq(s) dG(s) = 1 – G(q)
 So if F(x)  G(x) for all x,
Es~F u(s)  Es~G u(s)
for any increasing u
 “Only if” is because dq(x) is a valid increasing function of x
30