Transcript g(x`,t`)

Econ 805
Advanced Micro Theory 1
Dan Quint
Fall 2008
Lecture 4 – Sept 11 2008
Today: Necessary and Sufficient Conditions
For Equilibrium
 Today: necessary and sufficient conditions for a particular
bidding function to be a symmetric equilibrium
1
Tuesday’s big result was the Envelope
Theorem
 Theorem. Suppose that




For all t, x*(t) is nonempty
For all (x,t), gt(x,t) exists
For all x, g(x,-) is absolutely continuous
gt has an integrable bound: supx  X | gt(x,t) |  B(t) for almost all t,
with B(t) some integrable function
Then for any selection x(s) from x*(s),
V(t) = V(0) + 0t gt(x(s),s) ds
 Then we applied this to auctions with symmetric
independent private values
2
Another fairly general necessary condition:
monotonicity
 In symmetric IPV auctions, equilibrium bid strategies will
generally be increasing in values; how to prove?
 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
3
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 (but not necessary)
condition is for gt to be strictly increasing in x)
4
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
5
So now, given a symmetric equilibrium with
the bid function b…
 Define g(x,t) as the expected payoff, given bid x and value t,
when everyone else uses the equilibrium bid function
 If g satisfies strict single crossing differences, then b must be
(weakly) increasing
 And (from Tuesday), if g is absolutely continuous and
differentiable in t with an integrable bound, then
V(t) = V(0) + 0t gt(b(s),s) ds
6
All these conditions are almost always
satisfied by 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)
 So g(x,t) is absolutely continuous and differentiable in t, with
derivative bounded by 1
 What about strict single crossing differences?
 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?
7
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, g will satisfy strict single
8
crossing differences, so we know b will be nondecreasing
In fact, 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
9
b will almost always be strictly increasing
 In first-price auctions, equilibrium bid distributions don’t have point
masses even when type distributions do

When there is a positive probability of each bidder having a particular
value, they play a mixed strategy at that value
 Otherwise, there’d be a positive probability of ties, and the same logic
would hold – either prefer to increase by epsilon to win those ties, or
decrease by epsilon if you’re indifferent about winning them
 In second-price auctions, if the type distribution has a point mass,
bidders still bid their valuations

Still a dominant strategy
 So in that case, there are positive-probability ties
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 hold
 Next: when are these sufficient conditions for a bid
function b to be a symmetric equilibrium?
11
Sufficient Conditions
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
Why do we need smooth single crossing
differences, not just strict s.c.d.?
 Consider g(x,t) = (x – t)3, x(t) = x, X = [0,1]
 Clearly, x(t) is nondecreasing
 And it satisfies the envelope theorem: since
gt(x(t),t) = – (x(t) – t)2 = 0 and g(x(t),t) = 0
 But g(x,t) is maximized at x = 1, so x(t) = t is not a
solution
14
Let’s prove the sufficiency theorem
 Lots of extra terms due to the possibility of
discontinuities – we’ll just do the case where x(t)
is continuous (and therefore absolutely contin)
 x(t) absolutely continuous means it’s
differentiable almost everywhere
 So almost everywhere, by the chain rule,
d/dt g(x(t),t) = gx(x(t),t) x’(t) + gt(x(t),t)
 But we know the envelope condition holds, so
V’(t) = d/dt g(x(t),t) = gt(x(t),t)
 So almost everywhere, gx(x(t),t) x’(t) = 0
15
Let’s prove the sufficiency theorem
 Suppose at type t, instead of x(t), I played x(t’), with t’ > t
 My gain from the change is
g(x(t’),t) – g(x(t),t) = tt’ gx(x(s),t) x’(s) ds
 Now, we know from before that at almost every s,
gx(x(s),s) x’(s) = 0, so either gx(x(s),s) = 0 or x’(s) = 0
 If x’(s) = 0, then gx(x(s),t) x’(s) = 0 as well
 If gx(x(s),s) = 0, then since x(s)  x(t), smooth single crossing
differences says gx(x(s),t)  0 (recall t < s)
 And we know x’(s)  0
 So for almost every s > t, gx(x(s),t) x’(s) ds  0
 So integrating up, the switch from x(t) to x(t’) can’t be good
 The symmetric argument rules out t’ < t
16
So there you have it…
 If g is differentiable and satisfies smooth single crossing
differences, then x weakly increasing and satisfying the
Envelope condition implies x(t) is optimal AMONG THE
RANGE OF x
 We haven’t said anything about other possible x outside the
range of x
 Now, when will smooth single crossing differences be satisfied
in auctions?
 Well, g(x,t) = t W(x) – P(x), so gx = t W’(x) – P’(x) is weakly
increasing in t as long as W is nondecreasing in x
 So as long as higher bids win more often, the only condition we
have to worry about is g being differentiable wrt x
17
Applying this to auctions,
 Let b be a bid function, g the implied expected payoff function
 If



g is differentiable with respect to x
b is weakly increasing
b and g satisfy the envelope condition
 then b(t) is a best-response among the range of b
 Still need to check separately for deviations outside the
range of b

If the range of b is convex, that is, T is convex and b is
continuous, only really have to worry about highest type deviating
to higher bids, lowest type deviating to lower bids
18
Pulling it all together,
 Theorem (Constraint Simplification). Let g(x,t) be a
parameterized optimization problem. Suppose that



g is differentiable in both its arguments
gt has an integrable bound
g satisfies strict and smooth single crossing differences
 Let x : [0,1]  X be the sum of an absolutely continuous
function and a jump function, and let X* be the range of x
 Then x(t)  arg max x  X* g(x,t) for every t if and only if


x is nondecreasing
the envelope condition holds
19
And 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
20
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
21
(I probably won’t get to)
First-Order Stochastic Dominance
22
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.
23
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
24
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
25