@@title = MECHANISM DESIGN WITH STOPPING PROBLEMS
@@author = YOUNG WU
@@[AS2013] Athey and Segal (2013) An Efficient Dynamic Mechanism. \textit{Econometrica, 81(6):2463-2485}.
@@[BV2010] Bergemann and Valimaki (2010) The Dynamic Pivot Mechanism. \textit{Econometrica, 78(2):771-789}.
@@[BS2014] Board and Skrzypacz (2014) Revenue Management with Forward-Looking Buyers. \textit{Unpublished Manuscript, Stanford University}.
@@[CRS1991] Chow, Robbins and Siegmund (1991) The Theory of Optimal Stopping. \textit{New York: Dover}.
@@[ES2007] Eso and Szentes (2007) Optimal Information Disclosure in Auctions and the Handicap Auction. \textit{The Review of Economic Studies, 74(3):705-731}.
@@[GMS2013] Gershkov, Moldovanu and Strack (2013) Dynamic Allocation and Learning with Strategic Arrivals. \textit{Unpublished Working Paper University of Bonn}.
@@[IP2009] Inoue and Parmigiani (2009) Decision Theory: Principles and Approaches. \textit{John Wiley and Sons}.
@@[KS2014] Kruse and Strack (2014) Optimal Stopping with Private Information. \textit{Working Paper}.
@@[KS2013] Kruse and Strack (2013) Inverse Optimal Stopping. \textit{Working Paper}.
@@[PST2014] Pavan, Segal and Toikka (2014) Dynamic Mechanism Design: A Myersonian Approach. \textit{Econometrica, 82(2), 601-653}.
@@[PS2006] Peskir and Shiryaev (2006) Optimal Stopping and Free-Boundary Problems. \textit{Birkhäuser Basel}.

$$$ ABSTRACT
We analyze a dynamic mechanism design problem where a single agent could choose a time to obtain one of multiple possible allocations. The agent observes a private one dimensional signal and decides on a stopping time and a terminal allocation. The principal designs prices that depend only on the time and allocation the agent chooses. The model generalizes @@[KS2014] and provides sufficient and necessary conditions for implementability in this environment. We show that any stopping rule with continuation region being an interval on the signal space could be implemented if and only if two sets of single crossing conditions are satisfied: one over time and another over the terminal allocations.

$$$ INTRODUCTION
One feature of many decision making process is that gathering information requires time, and information may be costly to obtain. Many irreversible decisions could be modeled as stopping problems, where the decision maker keeps updating her information until some threshold values are reached, then stops and makes the decision. @@[KS2014] analyzes the stopping problem with only one possible allocation after stopping and considered the associated mechanism design problem. They provide conditions where a class of stopping rules are implementable and obtained closed form formulas for the transfers that implement these stopping rules. This paper analyzes another version of the stopping problem with a simpler payoff structure, but one where the agent can make a choice between more than one possible actions after she stops. It is different from the general dynamic mechanism design problem, which is typically difficult to solve, in that the agent can stop and make a decision only once. As a result, it is possible to break the problem into two parts. The agent has to first decide when to stop (a stopping problem), and given this stopping time, she makes a decision (a static mechanism design problem).
Economic examples of mechanism design involving stopping problems include:
* (Monopolistic Screening) A monopolist tries to sell a good to a buyer with private dynamic valuations. The buyer could make the trip to the seller only once but could purchase arbitrary units of the good. The monopolist offers different price-quantity bundles in each time period to incentive the buyer to make the purchasing decision that maximizes the monopolist’s expected profit.
* (Research Funding) A researcher considers working on one of two research projects with potential payoff difference that depends on a private signal and the effort she puts into the project. After observing realizations of the process, she chooses a time to start either project with an arbitrary effort level. The employer does not observe the private signal and provides a funding schedule depending on the starting date and the observable effort level.
* (Job Search) A worker receives job offers with wages following some stochastic process. In each period, the worker could choose to continue the search at a cost or accept an offer. The government designs different employment insurance payments at each time that incentivizes the worker to accept an offer at an earlier or later date.
* (Price of Advice \ Hypothesis Testing) The principal hires an econometrician for an advice (hypothesis test). The econometrician performs a Bayesian sequential test of H_0 vs H_1. After obtaining each sample, she could choose to report one of two advice (reject one of two hypotheses) or obtain one additional sample. Payments are designed for different sample sizes to incentive the econometrician to give the advice (perform the test) that is optimal for the principal.

This paper is most closely related to @@[KS2014] , which describes the mechanism design problem where a single agent could choose a single allocation at a single point in time. @@[PST2014] concerns with the problem where a single agent could one of multiple possible allocations in multiple periods. @@[BS2014] and @@[GMS2013] study the sale of indivisible goods over time, which is similar to the case when the agent could choose a single allocation in multiple periods. @@[BV2010] and @@[AS2013] consider the design of repeated auctions, which is the multiple agent version of the previous problems. Our model is a direct extension of @@[KS2014] to include the possibility of multiple actions after the agents stops. It focuses on the conditions when a class of stopping rules are implementable, namely, cut-off rules where the agent stops when the private signal falls outside an interval with upper and lower thresholds that varies over time. The sufficient and necessary conditions for implementability of this class of stopping rules could be viewed as two sets of single crossing conditions:
* (Spence-Mirrlees) Terminal allocations are non-decreasing in the signal.
* (Paven-Segal-Toikka) Expected change in utility due to change in the signal is non-increasing in time.
The first condition is the standard Spence-Mirrlees condition from static mechanism design and the second condition is a simplified version of the single crossing condition from @@[PST2014] .

Section 2 introduces the model with definitions and assumptions of the agent's problem and principal's problem. Section 3 gives sufficient and necessary conditions when cutoff rules are implementable. Section 4 provides simplifications of these conditions for examples with special utility functions or signal processes. Section 5 concludes.

$$$ MODEL
$$ Agent's Problem
An agent observes a one dimensional Markov process {X_t}_(t inn T), where T = {0, 1, 2, ..., T^--}. Each X_t has compact support X = [x_-- , x^--].
At time tsc, the agent could continue experimenting or stop and choose from a set of possible allocations. Denote the stopping time as tau inn Tssc, and the terminal allocation as q inn Q sube {Q_--, Q_-- + 1, Q_-- + 2, ..., Q^--} (or Q sube [Q_--, Q^--] in some examples). If the agent stops at time tau = tsc and chooses q = q_t, her payoff is u_t(q_t, X_t) - p_t(q_t). Assume Q_--, Q^-- and T^-- are finite.
Let the expected utility of the agent be:
U_0(tau, x) = Eop[u_tau(q_tau, X_tau) - p_tau(q_tau) | X_0 = x]

[asm:uqx] Assume the period tsc utility function is partially differentiable with respect to xsc and satisfies cross derivative condition for all t inn Tssc:
sgn(q) u_t(q, x) par x >= 0 __(is non-decreasing in) qsc 
When there is only one action Qssc = {1}, this condition should be seen as u_t(x) dff x >= 0. In the cases where Q_-- < 0 and Q^-- > 0, q_t = 0 is used as the action that separates two types of terminal actions: the positive type and the negative type. The sgn(qsc) in this assumption ensures that the utility is increasing in the signals for the positive type actions and decreasing in the signals for the negative type actions.

$$ Principal’s Problem
The principal sets prices {p_t(q_t)}_(t inn T) to incentivize the agent to choose the tau and {q_t}_(t inn T) that is optimal for the principal. The agent observes signal X_t = x_t and reports her signal x^^_t to either obtain allocation q_t(x^^_t) paying a price of p_t(q_t(x^^_t)) or be told to wait for another period. The prices and allocations are designed such that the agent will report her signal truthfully, x^^_t = x_t. 

[df:mech] (Mechanism) A mechanism is pair of sequences ({q_t}_(t inn T), {p_t}_(t inn T)), of allocations and prices. q_t : X -> Q UU {C} __for t < T^-- with q_(T^--) : X -> Qssc and p_t : Q -> reals. Given the reports x^^_t, the allocation includes stopping to get q_t(x^^_t), or delaying the decision to the next period, denoted by C_t. The transfers p_t(q) are functions of only the stopping time tsc and terminal allocation qsc = qsc_t.

Alternatively, a mechanism could be viewed as a stopping rule tau and a terminal allocation {q_t}_(t inn T) that the principal wants to implement, along with the sequence of transfer functions {p_t}_(t inn T) to incentivize the agent the use tau with truthful reports of x_t.

A simple example of such stopping rule is "stopping when the value exceeds a certain threshold":
tau = min_(t inn T) {t : X_t > b}
A more general stopping rule with varying thresholds will be defined as cut-off stopping rules in the next section.

$$ Signal Process
Assumptions similar to @@[KS2014] will be imposed on the stochastic process {X_t}_(t inn T):
[asm:xcts] (Continuous Transitions) For any continuous phi , Eop[phi(X_t+1) | X_t = x] is continuous.
[asm:xmono] (Monotonic Transitions) For any non-increasing phi, Eop[phi(X_t+1) | X_t = x] is non-increasing.
[asm:supp] (Full Support) For any interval [a , b) sube X, Eop[1_(X_t+1 inn [a, b)) | X_t = x] is strictly positive.

The above monotonicity condition is equivalent to:
 F_t+1(x_t+1 | X_t = x) par x <= 0
Examples of the processes that satisfy the above four assumptions are stated and proven in @@[KS2014] , which include additive and multiplicative random walks. The continuity-preserving and monotonicity-preserving properties are used to ensure that the shape of the value function in the future periods stays the same after taken expectations given the signal of the current period. The full support property is included to ensure the uniqueness of the representation of a cut-off stopping rule: without full support, multiple cut-off thresholds could be used to represent the same stopping random variable.

$$$ IMPLEMENTABLITY
$$ Cut-off Stopping Rules
[df:cut2] (Cut-off Stopping Rule) A cut-off stopping rule tau is a stopping rule where tau can be written as:
tau = min_(t inn T) {x_t notin [a_t, b_t]}, __(for some) (a_t, b_t) inn X^2
At period tsc, a_t is the lower cut-off threshold and b_t is the upper cut-off threshold. Fix a_T = b_T.

The cut-off rules defined in @@[KS2014] contain only one set of thresholds, namely the upper cutoff thresholds, but we allow the possibility of two sets of thresholds in this paper. These stopping rules arise naturally in decision making:
* There are situations where the agent has two types of actions to make after she stops: one type of actions yields high utility when the signal is high and the other type yields high utility when the signal is low. The agent will choose to stop when the signal is too low (below a_t) or too high (above b_t).
* The utility function may be concave in the signal violating @@(uqx) . In this case, the utility function could be broken into the two pieces: the increasing portion will correspond to utility function for the positive type actions and the decreasing portion will correspond to the utility function for the negative type actions.

$$ Conditions for Implementability
The following conditions will guarantee the implementability of all cut-off stopping rules.
[cond:qincr2] (Spence-Mirrlees) The allocations q_t(x) satisfy the condition for each tsc:
 q_t __(is non-decreasing in) xsc
[cond:qmono2] (Pavan-Segal-Toikka) The allocations q_t(x) satisfy the condition for each tsc:
Eop[lft| u_t+1(q_t+1(X_t+1), X_t+1) par x rgt| Isc(X_t+1, X_t) | X_t = x] <= lft| u_t(q_t(x), x) par x rgt|
where Isc(x_t+1, x_t) = - F_t+1(x_t+1| x_t) par x_t 1 / (f_t+1(x_t+1| x_t)) is the impulse response function in @@[PST2014].

Here, @@(qincr2) is the monotonicity condition on q_t, and it is used to implement the desired terminal allocation, as in static mechanism design problems; and @@(qmono2) is a simplified version of the condition from @@[PST2014] that implies the monotonicity of the expected marginal increase in utility by continuing for another period, and it is used to implement the desired cut-off stopping rule, as in @@[KS2014] .
Note that q_t could be discrete and still satisfy @@(qincr2) and @@(qmono2) , and it will be differentiable almost everywhere (not differentiable at countable points where q_t(x) is discontinuous).

[thm:impcut2] For p_T(x_--) = 0, p_T(x^--) = 0, the following are equivalent:
(1) The terminal actions {q_t}_t=0^T satisfy @@(qincr2) and @@(qmono2),
(2) The decision rule (tau, {q_t}_t=0^T) is implementable for any cutoff stopping rule tau with cutoff valuations {a_t, b_t}_(t inn T) by prices:
p_t(x) = - p^((b))_t(x) + p^((m))_t(x), __for x notin [a_t, b_t]
where
p^((m))_t(x) = int_(a_t vv x)^(b_t nn x) u_t(q_t(x^~), x^~) par q q_t(x^~) dff x d x^~ 
p^((b))_t(x) = Z_t(a_t vv x nn b_t) + sum_s=t+1^T-1 Eop[Z^~_s(a_t vv X_s nn b_t) | X_t = a_t vv x nn b_t]
where the marginal incentive functions are defined as:
Z^~_t(q, x) = Eop[max_(q^') u_t(q^', X_t+1) | X_t = x] - u_t(q, x)
Z_t(q, x) = Eop[u_t(q, X_t+1) | X_t = x] - u_t(q, x)

The base price p^((b))_t at the cut-off is from @@[KS2014] and the modification p^((m))_t comes from standard static mechanism design problem. Note that the condtions are sufficient to implement any cut-off rule, but not necessary to implement a particular cut-off rule: they are only necessary to implement all possible cut-off rules at the same time. The main steps of the proof are showing:
 @@(qincr2) and @@(qmono2) <=> Z_t are monotonic
 <=> value functions are monotonic
 <=> cut-off rules are implementable
The details are provided in the appendix.

$$$ EXAMPLES
 @@(impcut2) describes the sufficient conditions for implementing a cut-off rule with possibly two thresholds: the agent would stop when her signal is below a_t or above b_t for some (a_t, b_t) inn [x_--, x^--]^2. In this section, we show that the conditions could be further simplified if there is only one set of thresholds. We also provide intuitions for the condition from @@[PST2014] for special signal processes and utility functions. 

$$ Monopolistic Screening
A single buyer has valuations X_t+1 = X_t + eps_t for a good sold by a monopolist, where eps_t ~ G_t for some independently distributed G_t. The buyer could only make the trip to the monopolist once at time tau and purchase q_tau inn [0, Q^--] units of the good which results in discounted utility u_t(q, x) = bet^t q x - sum_s=0^t c_s, where bet is the discount factor and c_t is the cost for waiting at time tsc. With these specifications:
(^2 u_t(q, x)) par (q bdy x) = bet^t
Isc(x_t+1, x) = - ( G_t(x_t+1 - x) par x ) 1 / (g_t(x)) = - (- g_t(x)) / (g_t(x)) = 1
Then @@(qincr2) becomes:
 q^'_t(x) >= 0 
and @@(qmono2) becomes:
 q_t(x) >= bet Eop[q_t+1(X_t+1) | X_t = x]
This means that if the quantity sold to the buyer tomorrow is smaller in expectation than the quantity today, then this allocation could be implementable by cut-off rules with arbitrary thresholds {b_t}_(t inn T), in the sense that the buyer will purchase q_t(X_t) units of the good the first time when X_t > b_t.

$$ Research Funding
A researcher observes potential payoff from two research projects A and B. Let the payoff from project A follow {X^((A))_t}_(t inn T) and payoff from project B follow {X^((B))_t}_(t inn T) and define {X_t}_(t inn T) by X_t = X^((B))_t - X^((A))_t for each t inn Tssc. She can start the project at an arbitrary time tau and put in effort q_tau^((i)) inn [0, Q^--] obtaining utility u_tau^((i))(q_tau^((i)), X_tau) for isc inn {Assc, Bssc}.
This problem can be rewritten by defining q_t inn [- Q^--, Q^--] by:
%%{ q^((A))_t = %%{ q_t if q_t > 0
%%{ 0 ow
and,
%%{ q^((B))_t = %%{ -q_t if q_t < 0
%%{ 0 ow
The utility function could also be combined by:
%%{ u_t(q_t, x_t) = %%{ u_t^((A))(q_t, x_t) if q_t > 0
%%{ u_t^((B))(q_t, x_t) if q_t < 0
Then @@(impcut2) requires four separate conditions:
 q_t^((A)) == __(is non-increasing in) xsc 
 q_t^((B)) == __(is non-decreasing in) xsc 
 u_t(-q_t^((A))(x), x) par x <= Eop [ u_t+1(-q_t+1^((A))(X_t+1), X_t+1) par x Isc(X_t+1, X_t) | X_t = x]
 u_t(q_t^((B))(x), x) par x >= Eop [ u_t+1(q_t+1^((B))(X_t+1), X_t+1) par x Isc(X_t+1, X_t) | X_t = x]
And the prices are given separately for putting effort into each project:
 p_t^((A))(x) = - sum_s=t+1^T-1 P^~_(t,s)[Z^~_s](a_t) - Z^~_t^((A))(a_t) + int_(a_t)^x u_t(-q_t^((A))(x^~), x^~) par q q_t^((A))(x^~) dff x d x^~ 
 p_t^((B))(x) = - sum_s=t+1^T-1 P^~_(t,s)[Z^~_s](b_t) - Z^~_t^((B))(b_t) - int_x^(b_t) u_t(q_t^((B))(x^~), x^~) par q q_t^((B))(x^~) dff x d x^~ 

$$ Job Search
A worker observes job offers with wage X_t in period tsc and decides a time tau to accept an offer. The government pays lump !!sum employment insurance p_tau in period tau incentivize the worker to accept either higher or lower job offers. This example is borrowed from @@[KS2014] to illustrate the equivalence of the single crossing conditions in their paper and @@(impcut2) .
Here Qssc = {1} so @@(qincr2) is not relevant. Define u_t(x) = u_t(1, x), then @@(qmono2) can be reduced to 
Eop[u^'_t+1(X_t+1) Isc(X_t+1, X_t) | X_t = x] <= u^'_t(x)
which can be rearranged to get the dynamic single crossing condition in @@[KS2014]:
== d / (d x) (Eop[u_t+1(X_t+1) | X_t = x] - u_t(x)) <= 0
== __or Eop[u_t+1(X_t+1) | X_t = x] - u_t(x) __(is non-increasing in) xsc 
The prices specified by can also be simplified to
p_t = -sum_s=t^T-1 P^~_t,s [Z_s](b_t)
where {Z_t}_(t inn T) coincide with the marginal incentives defined in @@[KS2014].

$$ Price of Advice \ Hypothesis Testing
An econometrician observes iid samples sequentially with the cost of tsc-th sample c_t. There are two states theta inn {-1, 1} and the econometrician with tau samples has posterior belief X_tau that the state is -1, and gives one of two advices q_tau inn Q = {-1, 1}. If the advice matches the state, she gets payoff alp_theta, otherwise, she gets payoff bet_theta < alp_theta. Define the following:
m_-1 = alp_-1 - bet_-1 __and m_1 = bet_1 - alp_1 
k_-1(t) = bet_-1 - sum_s=1^t c_s __and k_1(t) = alp_1 - sum_s=1^t c_s
Then the utility function will be:
u_t(q, x) = m_q x + k_q(t)
Note that @@(qincr2) is satisfied vacuously. The linearity of the utility and the martingale property of the posterior beliefs guarantees that @@(qmono2) is always satisfied. The proof of this observation is given in the appendix.
The prices to implement the cut-off rule {a_t, b_t}_(t inn T), where the advice -1 is given when X_t < a_t and the advice 1 is given when X_t > b_t, are given by:
p_t(-1, x) = -Z_t(-1, a_t) -sum_s=t+1^T-1 Eop[Z^~_s(-1, a_t vv X_s) | X_t = a_t]
p_t(1, x) = -Z_t(1, b_t) -sum_s=t+1^T-1 Eop[Z^~_s(1, b_t nn X_s) | X_t = b_t]
In particular, Bayesian hypothesis test of any size could be implemented by adding the above {p_t}_(t inn T) to the loss function, or equivalently, to the cost of the samples.

$$$ CONCLUDING REMARKS

This paper provides sufficient conditions for implementing cut-off rules with possibly two sets of thresholds, and necessary conditions for implementability of all such cut-off rules, for a principal agent problem where the agent could choose a time to stop and then select one of many possible actions. We also provide closed-form solutions for the transfers at each time for each terminal action similar to @@[KS2014].
The sufficient and necessary conditions resemble two sets of single crossing conditions over time and terminal action. The single crossing conditions on the terminal actions are Spence-Mirrlees conditions for each period, and the single crossing conditions in the time dimension is a simplified version of the ones from @@[PST2014].
Further work is required to extend the problem to implement dynamic auctions with multiple agents. One possible solution is to have optimal auctions at each period with dynamic reservation prices that are equal to the thresholds in the cut-off rules, but @@(impcut2) does not directly apply. This question is left for future research.

$$$$