条件最优停止：一种时间不一致的优化

在这些平衡中，所有主体的选择都是唯一确定的；i、 例如，非唯一性不仅仅是由于在停止和继续之间保持不变的代理的不同选择。此外，多重性甚至在时间齐次马尔可夫均衡类中也会出现。算例还表明，在马尔可夫条件下，非马尔可夫平衡可能存在。示例5.1。考虑状态{0，1，2}上的齐次马尔可夫链X，初始值X=1，其自然过滤中的转移概率（pij）。只有B={1，2}中的状态与代理相关，这意味着σ=inf{t≥ 0：Xt=0}和Dt={X，…，Xt∈ B} 。Payo ff Gt=δtg（Xt）由当前状态的函数g和衰减因子δ给出∈ (0, 1). 具体而言，p=p=p=1/3和g（0）=, g（1）=1，g（2）=a，其中a是一个常数，满足1<3- δ2δ<a<2- δδ.我们还假设p6=1；其他跃迁概率是任意的。那么，正好有两个马尔可夫平衡：（i）处处停止；i、 e.，θ≡ 1.（ii）如果链条处于状态2或已退出，则停止；i、 e.，θt=1{Xt=2}∪Dct。如果p>0，则存在进一步的非马尔可夫平衡。在这些平衡中，给定试剂在某些状态（t，ω）下的诱导停止时间与（i）或（ii）诱导的停止时间一致，这取决于Ft证明。我们首先注意到，当a>g（1）且δ<1时，对于{Xt=2}上的time-t代理，唯一的最佳选择是停止，无论未来代理选择什么。（a） 看到θ≡ 1是一个平衡，考虑处于状态1的一个代理，在t=0时不丧失一般性。ThenJ（θ）=δ（p+ap）1- p=δ（1/3+a/3）2/3=δ1+a<1=G，（5.1）表明停车确实是最佳的，θ是一个平衡。（b） 由θt=1{Xt=2}定义的策略θ∪DCT是允许的。为了确定平衡，再次考虑状态1的时间-0代理。

设τjbe为s状态j的第一次击中时间，因此σ=τ，τ：=Lθ=τ∧ τ.我们有{τ σ} ={τ<τ}自P（τ∧ τ= ∞) = 当p=p时，{τ<τ}和{τ<τ}之间的对称性产生p（τ<τ）=p（τ<τ）=1/2，因此p（τ σ) = 1/2. 此外，E[Δτg（Xτ）1τσ] =aXk≥1δkP（τ=k，k<τ）=aXk≥1δk（1/3）k=aδ3- δ，因为P（τ=k，k<τ）=P（X=···=Xk-1=1，Xk=2）=pk-1便士。I t遵循j（θ）=E[ΔτGττσ] P（τ σ） =2aδ3- δ> 1=G，（5.2），表明延续是最佳的。因此θ是一个平衡。（c） 设θ为马尔可夫平衡；我们证明θ必须是上述两个策略之一。我们已经观察到，任何处于状态2的代理都必须停止。根据可采性，在0国的任何代理人也是如此。也就是说，1{Xt=2}∪Dct公司≤ θt≤ 所有t均为1∈ T、 如果没有其他代理停止，θ是（ii）的策略。否则，在{Xt=1}上存在一个在状态1：θt=1停止的时间-t代理。但是，与（5.1）中相同的计算表明，任何代理时间（t- 1） 状态1也必须停止，以此类推，以便θs≡ 1适用于所有s≤ t、 因此，在状态1停止的所有代理集可以看作是从t=0开始的半行。如果这条半直线是有限的，θ是（i）的平衡。如果不是，则存在一些最大t<∞ 其中time-t代理停止，意味着θs≡ s为1≤ t和θs=1{Xs=2}∪但现在（5.2）中的计算表明，对于任何时间t代理{Xt=1}，停止都不是最优的，这是一个矛盾。（d） 接下来，我们给出一个非马尔可夫均衡的例子。实际上，设置θ=θ≡ 1、对于t≥ 2，我们定义θt（ω）=（如果ω∈ {X=2，Xt=1}∩ Dt，1其他。类似于（5.1）和（5.2）的简单计算表明θ是一个等式。如果p>0，则θ定义中的两种情况都具有正概率，因此θ确实是非马尔可夫的。（e） 设θ为任何平衡，可能为非马尔可夫平衡。

（c）中的第一个论证仍然表明，对于（t，ω），如果Xt（ω）=1，θt（ω）=1，那么θt-1(ω) = 1. 然而，（c）merelyshowever的第二个自变量显示了（t，ω）的自变量，因此Xt-1（ω）=Xt（ω）=1和θt-1（ω）=0，则θt=0。（但如果Xt-1（ω）=2，与政策不能直接依赖于Xt的马尔可夫情况相反-1). 这意味着，考虑到时间t之前的过去，θ诱导的停止时间是（i）中的立即停止时间或（ii）中的{1}的首次退出时间。注意，如（d）中所述，这两者之间的选择可能取决于ω。备注5.2。（a） 示例5.1的有限地平线版本有一个非奇异平衡，由处处停止给出。这之后是一个向后递归和（5.1）中相同的计算，因为time-T代理必须停止。该平衡的极限为T→ ∞ 是最终水平平衡（i）。另一方面，平衡（ii）不是作为有限水平平衡的极限出现的。（b） 在这个特定的例子中，两个马尔可夫平衡是有序的：平衡（ii）对所有代理都有较大的值函数。值得注意的是，极限平衡是次平衡。（c） 例5.3表明，通常不存在支配平衡。我们也可以构造简单的例子，其中均衡值过程和对应于不同偏好的停止策略是无序的。5.2不存在时间齐次平衡在本节中，我们构造了一个时间齐次马尔可夫链的示例，该链允许马尔可夫平衡，但不允许时间齐次平衡。在这种意义上，定理4.1和推论4.3无法改进，对时间齐次概念的限制是不可能的（或将导致不存在）。重要的是，该示例还表明，[22]中引人注目的迭代方法不适用于我们的设置。

事实上，在非经验单位折扣问题中，不耐烦度递减，Φ的迭代应用（从合适的起点）会产生一个单调序列，收敛到时间齐次平衡。然而，在我们的例子中，迭代可能不会是单调的。这可能和动态规划原理的两个不等式的失败有关，而减少不耐烦可以保留一个不等式。示例5.3。考虑{0，1，2，3，4}上的齐次马尔可夫链X，其转移概率如图2中的边所示。特别是，状态0、3和4正在吸收。我们设置B={1，2，3，4}，因此0是唯一的退出状态。Payoff过程由Gt=δtg（Xt）给出，其中δ∈ （0，1）是折扣系数，g（1）=a，g（2）=2，g（3）=0，g（4）=bas标记在图2中的框中。为了避免琐事，我们假设初始位置是非吸收态之一，即X=1或X=2，并且我们还将注意力限制在停止于状态3的平衡上。如果f不依赖于t.1 23 40.50.10.5 0.40.40.1图2：示例5.3中的马尔可夫链，状态x用圆圈标记，支付g（x）用方框标记，则称为时间齐次马尔可夫平衡θt=f（t，Xt）。我们假设0<a<δ<1<2<b，这样，由于状态3是吸收的，并且g（3）=0，所有策略对状态3中的前不变代理都没有奖励。这导致了一系列（无趣的）平衡。如果假设提前停止偏好，则在状态3停止是一种结果，而不是一种条件。满足：a<δ，δ（a+4b）<18，（5.3）δ（δ+4b）>18，0.01δmin（5a，bδ）+0.2bδ+4bδ>17.9，（5.4）δ（max（δ，0.25bδ）+4b）<18.9a。（5.5）一个可能的选择是δ=0.999，a=0.96，b=4.257。

然后，直到a.s.等价：（i）所有平衡都是马尔可夫的。（ii）不存在时间齐次平衡。（iii）正好有两个平衡，它们由彼此的位移给出。实际上，设θt=f（t，Xt），θt=f（t+1，Xt），θt=f（t+2，Xt），θt=f（t+3，Xt），其中f（t，x）=R（x），t≡ 0米外径4R（x），t≡ 1米外径4R（x），t≡ 2米外径4R（x），t≡ 3 m od 4forR={0，1，2，3，4}，R={0，2，3，4}，R={0，3，4}，R={0，1，3，4}。那么θi，i=1，4是马尔可夫平衡，其中正好有两个在a.s.等效下是不同的：如果X=1，那么θ=θ和θ=θ，而如果X=2，那么θ=θ和θ=θ，a.s.所有平衡都是马尔可夫的，这与过滤相对较小（a.s.）有关，因为各种状态都在吸收这一事实，不应给予太多的权重。其他项目的证明相当冗长，因此让我们尝试试探性地总结关键机制。首先，对动力学进行了设计，使得在任何平衡中，time-t代理的决策都要求初始条件在我们的基本设置中是确定的。如果X=1，则状态1只能在奇数t处访问，状态2只能在偶数t处访问；如果x=2，则相反。这导致了两对θi的a.s.等价性。然而，如果我们将初始状态视为不固定状态（在马尔可夫框架中可能被视为自然状态），或者如果我们假设Xhas是一个包含两种状态的支持分布，那么所有四个平衡都是不同的。仅取决于t+1处的代理。此外，正如下面引理5.4所强调的，它嵌入了两种不能同意（甚至不能同意不同意）的代理：打电话给Minniet2和time t的代理，打电话给Donald1和time t的代理。Minnie喜欢和谐相处，总是想同意，而Donald只有在与Minnie发生冲突时才会高兴。支持Donaldtsays在某个时间“1”（停止）。

然后是米妮特-1也希望如此，但好斗的Donald-2立即回答为0，从而简化了时间不均匀性，因为他在反驳Donaldt。如果Donaldtstarts的值为0，则情况类似。相反，存在两个平衡点，因为一旦初始Donald（或Minnie，取决于初始s状态Xis）确定了两个可能的选择0或1中的一个，上述反向递归也意味着一个唯一的正向递归。（i）–（iii）的证明。让我们首先观察到，根据可容许性，任何均衡停止策略θ（可能是非马尔可夫的）必须在{Xt=0}上停止。此外，它必须在{Xt=4}上停止：状态4是吸收的，而g（4）>0，因此，由于贴现因子δ<1，继续永远不是最优的。由于我们也讨论了θ在{Xt=3}上的停止，因此我们可以将注意力限制在满足{Xt上θt=1的平衡上∈ 所有t的{0，3，4}}∈ T.（i）设θ为任意平衡；我们证明θ是马尔可夫的（或者更确切地说，a.s.等价于M-阿尔可夫平衡）。实际上，首先假设初始条件为X=1，并且X t∈ T、 在{Xt上有θT=1∈ {0, 3, 4}}. 但由于0，3，4是吸收态，{Xt∈ {0, 3, 4}} =∪s≤t{Xs∈ {0, 3, 4}}. 假设t∈ T是奇数。那么{Xt=1}是一个空集，因此在达到a.s.等价时，只有θton{Xt=2}的值尚未确定。但由于{0，3，4}上的吸收，以及集合{Xs=1}和{Xs=2}中正好有一个具有正概率的事实≤ t、 我们有{Xt=2}={X=2，X=1，X=2，…，Xt=2}，这意味着{Xt=2}是Ft中的一个原子。特别是，{Xt=2}上的θtis a.s.常数，并且由于{Xt=2}c上的θt=1 a.s，因此θtis是马尔可夫形式。如果t是偶数，则情况类似，因此θ是马尔可夫的。

初始条件为X=2时的处理类似。（ii）和（iii）的证明需要以下引理来描述上述米妮-唐纳德关系。引理5.4。设0<a<δ<1<2<b满足（5.3）–（5.5），并设θ是可容许的停止策略，使得θt=1在{Xt∈ t为{0，3，4}}∈ T、 那么对于所有T≥ 1，（P1）如果{Xt=1}上的θt=1，则Φ（θ）t-在{Xt上1=1-1= 2};（P2）如果{Xt=1}上的θt=0，则Φ（θ）t-{Xt上的1=0-1= 2};（P3）如果{Xt=2}上的θt=1，则Φ（θ）t-{Xt上的1=0-1= 1};（P4）如果{Xt=2}上的θt=0，则Φ（θ）t-在{Xt上1=1-1= 1}.引理的pro在证明（ii）和（iii）之后被报告。（ii）通过Rn=Rn+4z定义4周期序列（Rn），其中R，罕见，如上文（iii）所述。请注意，R，Rexhaust{0，3，4}和其余状态的所有组合。因此，时间齐次平衡θ（a.s.）的形式必须为θt=1Rn（Xt），t∈ T、 对于某些n.另一方面，对于任何T∈ T、 （P1）–（P4）意味着Φ（Φ（1Rn（Xt））=1Rn+2（Xt）6=Rn（Xt），从而排除了时间齐次平衡的存在。（我们迭代Φ两次，以确保策略也会模化a.s.等价）。（iii）θi（i=1，2，3，4）的可容许性成立，因为Dt={Xt=0}ca.s.（由于{0}正在吸收），并且因为从任何非吸收状态来看，在达到{0}之前达到{3，4}的正概率。此外，Φ（θi）=θi通过使用（P1）–（P4）直接验证得出。因此，θi平衡。为了确定有两个平衡点，首先假设初始条件为X=1，θ为（必然是马尔可夫）平衡点。模a.s.等价，θ完全由其在{X=1}、{X=2}、{X=1}等上的值决定，因为状态1只能在事件时间访问，状态2只能在奇数时间访问。接下来，我们使用（P1）–（P4）：假设θ=1在{X=1}上。

这意味着{X=2}上的θ=0，这意味着{X=1}上的θ=0，这意味着{X=2}上的θ=1，等等。因此，我们有θ=θ=θa.s。或者，{X=1}上的θ=0。这意味着{X=2}上的θ=1，因此{X=1}上的θ=1，因此{X=2}上的θ=0，等等。特别是，我们有θ=θ=θa.s。初始条件X=2的情况类似。引理5.4的证明。让t≥ 1并设置▄Jt（θ）=E[δLtθ-tg（XLtθ）1{Ltθ<σ}| Ft]P（Ltθ<σ| Ft）如果初始状态不被认为是固定的，或者如果它是随机的，P（X=1）>0，P（X=2）>0，那么（P1）–（P4）意味着θ是四个θi中的一个，由{X=1}和{X=2}上的θ值唯一确定。因此，Jt（θ）=δtJt（θ）是时间t的延拓值。请注意，将Jt（θ）与gts进行比较相当于将Jt（θ）与g（Xt）进行比较。我们将展示（P1）和（P3）。（P1）：假设Xt-1= 2. 这意味着Xt∈ {0，1，3，4}，因此（P1）的假设得出θt=1，Lt-1θ=t和▄Jt-1（θ）=δ（0.1a+0.4b）/0.9。在（5.3）的第二部分中，我们得到了Jt-1（θ）<2=g（2），因此Φ（θ）t-1=1，如权利要求所述。（P3）：如果Xt-1=1，然后是Xt∈ {2，3}，（P3）的赋值意味着θt=1，Lt-1θ=t和▄Jt-1(θ) = δ. 到（5.3）的第一部分，我们有Jt-1（θ）>a=g（1），因此Φ（θ）t-1= 0.接下来，我们分析（P2）和（P4）。用ht（θ）和pt（θ）表示~Jt（θ）的数字和分母。很明显，ht（θ）≤Jt（θ）≤ b代表所有t，因为bis是最大可能的支付。

通过迭代条件作用，我们在集合{Xt=1}上得到了 {Xt+1∈ {2，3}}，ht（θ）=E[δLtθ-tg（XLtθ）1{Ltθ<σ}| Ft]=E[1{Xt+1=2}δLtθ-tg（XLtθ）1{Ltθ<σ}+1{Xt+1=3}δg（3）| Ft]=E[1{Xt+1=2，θt+1=1}δg（2）| Ft]+E[1{Xt+1=2，θt+1=0}δLt+1θ-（t+1）δg（XLt+1θ）1{Lt+1θ<σ}| Ft]=δE[1{Xt+1=2，θt+1=1}2+1{Xt+1=2，θt+1=0}ht+1（θ）| Ft]，（5.6）其中，如果θt+1=1，则Ltθ=t+1，如果θt+1=0，则Ltθ=Lt+1θ。类似地，我们推导出在{Xt=1}，pt（θ）=E[1{Xt+1=2，θt+1=1}+1{Xt+1=2，θt+1=0}pt+1（θ）| Ft][0.5，（5.7）和在{Xt=2}，ht（θ）=δE[1{Xt+1=1，θt+1=1}a+1{Xt+1=1，θt+1=0}ht+1（1θ）| Ft]+0.4bδ，（5.8）pt（θ）=E[1{Xt+1=1，θt+1=1}+1{Xt+1=1，θt+1=0}pt+1（θ）| Ft]+0.8。（5.9）方程（5.6）-（5.9）得出以下界限：{Xt=1}，ht（θ）≤ δE[1{Xt+1=2}max（2，ht+1（θ））| Ft]，（5.10）ht（θ）≥ δE[1{Xt+1=2}min（2，ht+1（θ））| Ft]，（5.11）pt（θ）≥ 0.5+E[1{Xt+1=2}pt+1（θ）| Ft]，（5.12）和{Xt=2}，ht（θ）≤ δE[1{Xt+1=1}max（a，ht+1（θ））| Ft]+0.4bδ，（5.13）ht（θ）≥ δE[1{Xt+1=1}min（a，ht+1（θ））| Ft]+0.4bδ，（5.14）0.8+E[1{Xt+1=1}pt+1（θ）| Ft]≤ pt（θ）≤ 0.9. （5.15）（P2）：假设θt=0在{Xt=1}上。在（P2）的证明中，我们假设我们在集合{Xt上-1= 2}; i、 例如，所有语句都以Xt为条件-1= 2. 然后，1{Xt=1，θt=0}=1{Xt=1}和1{Xt=1，θt=1}=0。确定Φ（θ）t-1=0，必须显示▄Jt-1（θ）>g（2）=2。为此，我们推导出ht的下界-1（θ）和上界forpt-1（θ）（有条件地在Xt上-1= 2). Letγt-1： =P（Xt=1，Xt+1=2，θt+1=1 | Ft-1） 请注意，0≤ γt-1.≤ 0.05.

从ht+3（θ）这一事实出发≥ 在{Xt+3=2}上的0.4bδ通过（5.14），我们使用（5.11）可以看到在{Xt+2=1}，ht+2（θ）≥ δE[1{Xt+3=2}min（2，ht+3（θ））| Ft+2]≥ δE[1{Xt+3=2}min（2，0.4bδ）| Ft+2]=0.5δmin（2，0.4bδ）=min（δ，0.2bδ），然后（5.14）和a<δ来推断{Xt+1=2}，ht+1（θ）≥ δE[1{Xt+2=1}min（a，ht+2（θ））| Ft+1]+0.4bδ≥ δE[1{Xt+2=1}min（a，min（δ，0.2bδ））| Ft+1]+0.4bδ=0.1δmin（a，0.2bδ）+0.4bδ=0.1A，（5.16），其中：=δmin（a，0.2bδ）+4bδ。根据（5.8），（P2），（5.6）的假设和迭代条件，我们已经-1（θ）=δE[1{Xt=1}ht（θ）| Ft-1] +0.4bδ=δE[1{Xt=1，Xt+1=2，θt+1=1}2+1{Xt=1，Xt+1=2，θt+1=0}ht+1（θ）| Ft-1] +0.4bδ。将下限（5.16）替换为ht+1（θ）到上述方程中，ht-1(θ) ≥ δ（2γt-1+0.1A（0.05- γt-1） ）+0.4bδ。类似地，使用（5.9），假设（P2），（5.7），迭代条件和（5.15），我们得到了-1（θ）=E[1{Xt=1}pt（θ）| Ft-1] +0.8=E[1{Xt=1，Xt+1=2，θt+1=1}+1{Xt=1，Xt+1=2，θt+1=0}pt+1（θ）| Ft-1] +0.5P（Xt=1 | Ft-1) + 0.8≤ E[1{Xt=1，Xt+1=2，θt+1=1}+1{Xt=1，Xt+1=2，θt+1=0}0.9 | Ft-1] +0.85=γt-1+ 0.9(0.05 - γt-1） +0.85=0.1γt-1+ 0.895.这两个界限产生▄Jt-1（θ）=ht-1（θ）pt-1(θ)≥δ（2γt-1+0.1A（0.05- γt-1） ）+0.4bδ0.1γt-1+ 0.895.因此，对于▄Jt而言-1（θ）>2是f（y）：=δ（2y+0.1A（0.05-y） ）+0.4bδ-（0.2y+1.79）>0表示所有y∈ [0, 0.05].由于f在y中是线性的，这相当于f（0）>0和f（0.05）>0，精确地说是（5.4）。（P4）：假设θt=0在{Xt=2}上，因此1{Xt=2，θt=0}=1{Xt=2}和1{Xt=2，θt=1}=0。