Title Robust Predictions in Dynamic Screening English 526.6 KB 53
```                            Introduction
Related Literature
The Model
Robust predictions
Preliminary properties of optimal mechanisms
Convergence of wedges in expectation
Convergence of policies in probability
Continuum of types
Conclusions
```
##### Document Text Contents
Page 1

Robust Predictions in Dynamic Screening∗

Daniel Garrett† Alessandro Pavan‡ Juuso Toikka§

April, 2018

Abstract

We characterize properties of optimal dynamic mechanisms using a variational approach that

permits us to tackle directly the full program. This allows us to make predictions for a consider-

ably broader class of stochastic processes than can be handled by the “first–order, Myersonian,

approach,” which focuses on local incentive compatibility constraints and has become standard

in the literature. Among other things, we characterize the dynamics of optimal allocations when

the agent’s type evolves according to a stationary Markov processes, and show that, provided the

players are sufficiently patient, optimal allocations converge to the efficient ones in the long run.

JEL classification: D82

Keywords: asymmetric information, dynamic mechanism design, stochastic processes, convergence

to efficiency, variational approach

∗For useful comments and suggestions we thank participants at various conferences and workshops where the paper

has been presented, and in particular Nicola Pavoni. Pavan also thanks Bocconi University for its hospitality during

the 2017-2018 academic year and the National Science Foundation for �nancial support. The usual disclaimer applies.

Email addresses: [email protected] [Garrett], [email protected] [Pavan], [email protected] [Toikka].
†Toulouse School of Economics
‡Northwestern University and CEPR
§Massachusetts Institute of Technology

Page 2

1 Introduction

The ideas and tools developed in the mechanism design literature have found applications in a variety

of contexts, including auctions, regulation, taxation, employment, political economy, matching, and

many others. While much of the literature focuses on environments where the agents learn informa-

tion only at a single point in time, and the mechanism makes one-time decisions, many environments

are inherently dynamic. One class of problems that has been of particular interest involves an agent,

or multiple agents, whose private information (as described by their “type”) changes over time and

is serially correlated. Since a sequence of decisions needs to be made, the mechanism must elicit

this information progressively over time.

Solving these dynamic mechanism design problems is often a complicated task, but a common

approach has become popular in the literature on profit-maximizing mechanisms, building on ideas

from static mechanism design (such as Myerson, 1981). This approach focuses on solving a “relaxed

program” which accounts only for certain necessary incentive compatibility conditions, which can

be derived from the requirement that agents do not have an incentive to misreport their types

locally (e.g., by claiming to have a type adjacent to their true type). Of course, the solution to

such a relaxed program need not correspond to an optimal mechanism in the problem of interest; in

particular, some of the ignored incentive compatibility constraints may be violated. Nonetheless, the

standard approach is to choose conditions on the environment (primitives that include, in particular,

the evolution of the agents’ types) that guarantee global incentive compatibility. Unfortunately,

the conditions imposed, typically, have little to do with the economic environment as it is naturally

conceived. One is then left to wonder to what extent qualitative properties of the optimal mechanism

are a consequence of the restrictions that guarantee the validity of the “relaxed approach.”

The present paper takes an alternative route to the characterization of the qualitative features of

optimal dynamic mechanisms. This route yields insights for settings well beyond those for which the

above approach based on the relaxed program applies. The property of optimal mechanisms that

has received perhaps the most attention in the existing literature on dynamic mechanism design is

the property of vanishing distortions; i.e., optimal mechanisms become progressively more efficient

and distortions from efficient allocations eventually vanish. Examples of such work include Besanko

(1985), Battaglini (2005), Pavan, Segal and Toikka (2014), and Bergemann and Strack (2015), among

others. We investigate whether this and other related properties continue to hold in a broad class

of environments for which the familiar “relaxed approach” need not apply.

Our approach is based on identifying “admissible perturbations” to any optimal mechanism.

For any optimal, and hence incentive-compatible and individually-rational, mechanism, we obtain

nearby mechanisms which continue to satisfy all the relevant incentive-compatibility and individual-

rationality constraints. Of course, for the original mechanism to be optimal, the perturbed mech-

anism must not increase the principal’s expected payoff, which yields necessary conditions for op-

timality. These necessary conditions can in turn be translated into the qualitative properties of

1

Page 26

expected payoff, as given by (22). In particular, suppose that q∗ is such that the period-t schedule

q∗t (·) is bounded away from the boundaries of the set of feasible quantity levels; namely, suppose
that there exist ιt, ῑt ∈ R++, with 0 < ιt ≤ ῑt < q̄, such that, for all ht, q∗t

(
ht
)

a constant ν ∈ R to the schedule q∗t (·) yields a new policy that continues to satisfy the integral
monotonicity conditions in (21) (the arguments are similar to those yielding to Proposition 1). The

variation in the principal’s expected payoff relative to her payoff under 〈q∗,p∗〉 is then equal to

δt−1E

B (q∗t (h̃t)+ ν)− C (q∗t (h̃t)+ ν, h̃t)−

F1

(
h̃1

)
f1

(
h̃1

) It(h̃t)

(q∗t (h̃t)+ ν)

 (25)

−δt−1E

B (q∗t (h̃t))− C (q∗t (h̃t) , h̃t)−

F1

(
h̃1

)
f1

(
h̃1

) It(h̃t)

 q∗t (h̃t)

 .

Dividing the expression in (25) by ν and taking the limit for ν going to zero yields the following

expression for the derivative of the principal’s expected payoff with respect to ν evaluated at ν = 0:

δt−1E

B′ (q∗t (h̃t))− Cq (q∗t (h̃t) , h̃t)−

F1

(
h̃1

)
f1

(
h̃1

) It(h̃t)

 .

A necessary condition for the optimality of 〈q∗,p∗〉 is that such derivative vanishes. We then have
the following result:

Definition 1. The mechanism 〈q,p〉 is “eventually interior” if there exists T and sequences of scalars
(ιt) and (ῑt), with 0 < ιt ≤ ῑt < q̄, all t, such that, for any t > T , any ht, qt

(
ht
)
∈ [ιt, ῑt].

Proposition 6. Assume the processF satis�es Conditions \Markov," \FOSD," and \Regularity".

If 〈q∗,p∗〉 is \eventually interior," then, for all t large enough,

E
[
B′
(
q∗t

(
h̃t
))
− Cq

(
q∗t

(
h̃t
)
, h̃t

)]
= E

F1

(
h̃1

)
f1

(
h̃1

) It(h̃t)

 . (26)

That the quantity schedule under the optimal mechanism is eventually interior appears dif-

ficult to guarantee in general. Naturally, given the Inada conditions (limq→q̄ c (q) = +∞ and
limq→0B (q) = −∞), such interiority can be guaranteed if one imposes continuity restrictions on
the optimal schedules, such as requiring allocations to be Lipschitz continuous with a fixed Lipschitz

constant. Under such a restriction, the perturbations to the optimal policies described above are

then feasible, which in turn guarantees that the expected wedge under the optimal mechanism is

given by the right hand side of (26).

Note that the result in Proposition 6 is related to the result in the literature that focuses on

environments for which the relaxed approach is valid, but with important differences. When the

optimal policies are those that solve the relaxed approach, and such policies are interior, the wedge,

25

Page 27

at any history ht, is given by the marginal handicap F1(h1)It(h
t)/f1(h1). This need not be true more

generally, i.e., for environment where the relaxed approach is not guaranteed to be valid. What

remains true, though, is that the expected wedge is equal to the expected marginal handicap. By

studying the dynamics of the expected marginal handicaps, one can then identify useful properties

for the dynamics of the expected wedges, as we show below. Let B(Θ) be the Borel sigma algebra
associated with the set Θ. For any A ∈ B(Θ), h ∈ Θ, and t ≥ 1, then let

P t(h,A) ≡ Pr
(
h̃t ∈ A|h̃1 = h

)
.

Condition 7. [Ergodicity] The process F is ergodic if there exists a unique (invariant) probability

measure π on B(Θ) whose support has a nonempty interior such that, for all h ∈ Θ,

sup
A∈B(Θ)

∣∣P t(h,A)− π(A)∣∣→ 0 as t→∞. (27)
Under the additional Condition “Ergodicity,” we are able to establish a result analogous to the

one in (8) for discrete types.

Proposition 7. Assume F satisfies Conditions “Regularity” and “Ergodicity.” Then

E
[
F1(θ1)

f1(θ1)
It(θ

t)

]
→ 0 as t→∞.

If, in addition, F satisfies Condition “FOSD,” then convergence is from above, i.e., E
[
F1(θ1)
f1(θ1)

It(θ
t)
]

0 for all t. Furthermore, if, in addition to the above conditions, the period-1 distribution is the

stationary (ergodic) distribution of F , then convergence is monotone in time, i.e., E
[
F1(θ1)
f1(θ1)

It(θ
t)
]

is

decreasing in t.

Together, Propositions 6 and 7 thus provide implications for the dynamics of expected wedges

analogous to those in the discrete case. We summarize such implications in the following Corollary:

Corollary 2. Suppose F satisfies Conditions “Markov,” “Regularity,” “FOSD,” and “Ergodicity,”

and that the optimal policies are “eventually interior.” Then the expected wedges are eventually

positive and vanish in the long run. If, in addition, the period-1 distribution of F coincides with the

ergodic distribution, then, eventually, convergence becomes monotone in time.

As in the discrete case, the result in Corollary 2 does not imply convergence of of the quantity

schedules to the efficient ones in probability. Nonetheless, we expect that the same restrictions on the

quantity schedules that guarantee the eventual interiority of the policies, such as the requirement that

qt(·) be Lipschitz with known Lipschitz constants, also rule out pathological behavior, permitting
arguments analogous to those in the discrete case to establish convergence of the allocations to the

efficient levels (in probability) when players are sufficiently patient.

26

Page 52

the mechanism 〈µ∗,p∗〉 considered above for the case where an optimal mechanism exists. Suppose,
towards a contraddiction, that there is ε > 0 for which there is no value t̄ ∈ N and corresponding
sequence (sk), with sk →∞, for which (19) is satisfied for all t̄ ≤ t ≤ t̄+ sk. Then, for any t̄, there
is s̄ (t̄) such that, for any k ∈ N, there exists t (t̄; k) ∈ {t̄, t̄+ 1, . . . , t̄+ s̄ (t̄)} with

E
[
B
(
qE
(
h̃t(t̄;k)

))
− C

(
qE
(
h̃t(t̄;k)

)
, h̃t(t̄;k)

)]
−E

[∫ (
B (q̃)− C

(
q̃, h̃t(t̄;k)

))
dµk

t(t̄;k)

(
h̃t(t̄;k)

)]
≥ ε.

Now, consider mechanisms

µk,γ ,pk,γ

whose policies are given, for each t ≥ 1 and each ht, by

µ
k,γ
t

(
ht
)

= γtµ
E
t

(
ht
)

+ (1− γt)µkt
(
ht
)

and

p
k,γ
t

(
ht
)

= γtp
E
t

(
ht
)

+ (1− γt) pkt
(
ht
)
,

with γt = min

{
γ1

(
1 + κ

2δλ̄

)t−1
, 1

}
and γ1 =

(
1 + κ

2δλ̄

)1−t(t̄;k)
. Arguments analogous to those used

above to establish the first clam in the proposition imply that the mechanism

µk,γ ,pk,γ

increases

the principal’s expected profits by at least

δt(t̄;k)−1
(
ε−

(
δ +

κ

2λ̄

)1−t(t̄;k)(
E
[
V
〈qE ,pE〉

1

(
h̃1

)]
− E

[
V
〈µk,pk〉

1

(
h̃1

)]))
,

which, provided t̄ is taken sufficiently large, exceeds zero by at least some amount that is independent

of k. For k large enough, this implies the principal obtains expected profits that are strictly higher

than sup〈µ,p〉∈ΨS Π (µ,p), a contradiction. Q.E.D.

Proof of Proposition 6. The result follows from the arguments in the main text. Q.E.D.

Proof of Proposition 7. Observe that, when the process satisfies Condition “Regularity,”

E[It(h̃t)h1] = ddh1 E[h̃t|h1]. Thus,

E
[
F1(h̃1)

f1(h̃1)
It(h̃

t)
]

= E
[
F1(h̃1)

f1(h̃1)
E[It(h̃t) | h̃1]

]
=

∫ θ̄
θ
F1(θ1)E[It(h̃t) | θ1]dθ1

= F1(θ1)E[h̃t| θ1]
∣∣∣θ1=θ̄
θ1=θ

+

∫ θ
θ
f1(θ1)E[h̃t| θ1]dθ1

= E[h̃t | θ̄]− E[h̃t].

When, in addition, F satisfies Condition “Ergodicity,” then E[h̃t | θ̄]−E[h̃t]→ 0, as t→∞, implying
that E

[
F1(h̃1)

f1(h̃1)
It(h̃

t)
]
→ 0, as t→∞, as claimed.

If, in addition to Condition “Ergodicity,” F satisfies Condition “FOSD,” then

E[h̃t | θ̄]− E[h̃t] ≥ 0

51

Page 53

so that the convergence is from above.

Finally, if, in addition to the conditions above, F is stationary, then

E
[
F1(h̃1)

f1(h̃1)
It(h̃

t)
]

� E
[
F1(h̃1)

f1(h̃1)
Is(h̃

s)
]

= E[h̃t j θ̄] � E[h̃s j θ̄] � 0

for any t > s, which implies that convergence is monotone in time. Q.E.D.

52