Philippe Gambette
email: philippe.gambette@u-pem.fr

Andreas D M Gunawan

Anthony Labarre
email: anthony.labarre@u-pem.fr

Stéphane Vialette
email: stephane.vialette@u-pem.fr

Louxin Zhang

Solving the Tree Containment Problem in Linear Time for Nearly Stable Phylogenetic Networks $

Keywords: phylogenetic trees, phylogenetic networks, tree containment, reticulation visibility, nearly stable networks, genetically stable networks

A phylogenetic network is a rooted acyclic digraph whose leaves are uniquely labeled with a set of taxa. The tree containment problem asks whether or not a phylogenetic network displays a phylogenetic tree over the same set of labeled leaves. It is a fundamental problem arising from validation of phylogenetic network models. The tree containment problem is NP-complete in general. To identify network classes on which the problem is polynomial time solvable, we introduce two classes of networks by generalizations of tree-child networks through vertex stability, namely nearly stable networks and genetically stable networks.

Here, we study the combinatorial properties of these two classes of phylogenetic networks. We also develop a linear-time algorithm for solving the tree containment problem on binary nearly stable networks.

Introduction

With thousands of genomes being fully sequenced, phylogenetic networks have been adopted to study "horizontal" processes that transfer genetic material from a living organism to another without descendant relation. These processes are believed to be a driving force that shapes the genome of a species in evolution [START_REF] Chan | Topology of viral evolution[END_REF][START_REF] Treangen | Horizontal transfer, not duplication, drives the expansion of protein families in prokaryotes[END_REF].

A (phylogenetic) network over a set X of taxa is a rooted acyclic digraph with a set of leaves (i.e., vertices of outdegree zero) that are uniquely labeled with the taxa. Such a network represents the evolutionary history of the taxa in X. In a network, the tree vertices (i.e., vertices of indegree one) represent speciation events, whereas the vertices of indegree at least two (called reticulation vertices, or simply reticulations) represent genetic material flow from several ancestral species into an "unrelated" species. A plethora of methods for reconstructing networks and related algorithmic issues have been extensively studied over the past two decades [START_REF] Gusfield | ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks[END_REF][START_REF] Huson | Phylogenetic Networks: Concepts, Algorithms and Applications[END_REF][START_REF] Nakhleh | Computational approaches to species phylogeny inference and gene tree reconciliation[END_REF][START_REF] Steel | Phylogeny: Discrete and Random Processes in Evolution[END_REF][START_REF] Wang | Perfect phylogenetic networks with recombination[END_REF].

One approach to assessing the quality of a network is to verify whether or not it is consistent with previous biological knowledge about the species. Biologists therefore demand that the network displays existing gene trees, which corresponds to the tree containment (TC) problem [START_REF] Huson | Phylogenetic Networks: Concepts, Algorithms and Applications[END_REF]. This problem is well-known to be NP-complete [START_REF] Kanj | Seeing the trees and their branches in the network is hard[END_REF][START_REF] Van Iersel | Locating a tree in a phylogenetic network[END_REF], and great efforts have therefore been devoted to identifying "tractable" subclasses of binary networks, such as galled trees [START_REF] Kanj | Seeing the trees and their branches in the network is hard[END_REF], normal networks, tree-child networks and level-k networks [START_REF] Van Iersel | Locating a tree in a phylogenetic network[END_REF].

Recently, Gunawan et al. [START_REF] Gunawan | Locating a tree in a reticulation-visible network in cubic time[END_REF] and Bordewich and Semple [START_REF] Bordewich | Reticulation-visible networks[END_REF] independently proved that the TC problem can be solved in cubic time for binary reticulation-visible networks, thereby settling an open problem [START_REF] Huson | Phylogenetic Networks: Concepts, Algorithms and Applications[END_REF][START_REF] Van Iersel | Locating a tree in a phylogenetic network[END_REF]. The time complexity was further improved to quadratic time even for arbitrary (i.e. non-binary) reticulation-visible networks in [START_REF] Gunawan | A decomposition theorem and two algorithms for reticulation-visible networks[END_REF].

To tackle the TC problem for reticulation-visible networks, we introduced nearly stable networks and genetically stable networks, which both generalize tree-child networks, and gave quadratic time algorithms for solving the TC problem on both classes [START_REF] Gambette | Locating a tree in a phylogenetic network in quadratic time[END_REF][START_REF] Gambette | Solving the tree containment problem for genetically stable networks in quadratic time[END_REF]. These results gave an insight on the topological structure of a reticulation-visible network, and eventually led to a solution to the open problem in [START_REF] Gunawan | Locating a tree in a reticulation-visible network in cubic time[END_REF]. In this paper, we establish the tight upper bounds on the numbers of vertices in a nearly stable network and in a genetically stable network. We further show on simulated data that these two new classes cover a significant proportion of phylogenetic networks, compared with binary reticulation-visible networks.

In this paper, we also revisit the TC problem for nearly stable networks. In an earlier version of this work [START_REF] Gambette | Locating a tree in a phylogenetic network in quadratic time[END_REF], we developed a quadratic-time algorithm for the TC problem on that class. The time complexity of the algorithm was further improved to O(n log n) in [START_REF] Fakcharoenphol | A faster algorithm for the tree containment problem for binary nearly stable phylogenetic networks[END_REF] using the same approach but with a more efficient data structure. Here, we develop a linear-time TC algorithm by combining the structure analysis in [START_REF] Gambette | Locating a tree in a phylogenetic network in quadratic time[END_REF] and a decomposition technique introduced in [START_REF] Gunawan | Locating a tree in a reticulation-visible network in cubic time[END_REF]. This technique plays a vital role in the designs of a quadratictime TC algorithm for reticulation-visible networks and of a fast exponential-time algorithm for arbitrary networks [START_REF] Gunawan | A program for verification of phylogenetic network models[END_REF].

Concepts and notions

Phylogenetic trees and networks

A (phylogenetic) network on a set X of taxa is an acyclic digraph N with a single root ρ N (a unique vertex with indegree 0) whose leaves (vertices with outdegree 0) are in oneto-one correspondence with the taxa in X. The fact that the root is the unique vertex with indegree 0 implies that there is a (directed) path from the root to every other vertex. For convenience, we attach an incoming edge to ρ N (so the indegree becomes one) with one open-end. We identify each leaf with the taxon corresponding to it.

In a network, reticulation vertices (or simply reticulations) are vertices with indegree at least two and outdegree one; tree vertices are vertices with indegree one, which includes the root and leaves. For a given network N , L(N ) denotes its leaf set, R(N ) its set of reticulation vertices, T (N ) its set of tree vertices (including leaves), V(N ) the entire set of vertices, and E(N ) the entire set of edges. An edge is a reticulation edge if it is an edge entering a reticulation vertex.

Let N be a network. For an edge set E ⊆ E(N ), N -E denotes the subnetwork with vertex set V(N ) and edge set E(N )\E. Similarly, for a vertex subset S ⊆ V(N ), N -S denotes the subnetwork with the vertex set V(N )\S and the edge set

{(u, v) ∈ E(N ) | u ∈ S, v ∈ S}.
When E or S contains only one element x, we simply write N -x.

Let v ∈ V(N ). The subnetwork of N induced by v consists of v and all its descendants and the edges between them. It is rooted at v and is denoted by

N [v].
We say that a network obtained by removing all but one incoming edge from each reticulation in a network N is a spanning tree of N .

A network is binary if its leaves are of degree one, and all other vertices are of degree three. A phylogenetic tree is simply a binary network without reticulation vertices. All networks we shall consider in this paper are binary unless stated otherwise.

Reticulation stability

Consider a network N . Let x and y be two vertices of N . We say that x is a parent of y and y is a child of x if (x, y) is an edge of N . More generally, we say that x = y is an ancestor of y (or above y) and equivalently y is a descendant of x (or below x) if there is a directed path from x to y in N . Two vertices are siblings if they are the children of the same vertex.

A vertex x is a stable ancestor of a vertex v (or x is stable on v) if it belongs to all directed paths from ρ N to v. We say that x is stable (or visible) if there exists a leaf such that x is a stable ancestor of . A vertex is unstable if it is not a stable ancestor of any leaf.

A network is reticulation-visible [START_REF] Huson | Phylogenetic Networks: Concepts, Algorithms and Applications[END_REF] if every reticulation vertex it contains is visible.

Proposition 2.1. (Lemma 2.3, [START_REF] Gunawan | Bounding the size of a network defined by visibility property[END_REF]) Let N be a network and u ∈ V(N ). Let R be a set of reticulations below u such that for each r ∈ R, either (i) r is a descendant of another reticulation r ∈ R, or (ii) there is a path from ρ N to r that avoids u. Then, u is not stable on any leaf below a reticulation in R.

By Proposition 2.1, we have the following simple criteria to determine whether a vertex is stable or not in a network.

Corollary 2.1. Let v be a tree vertex in a network N .

(1) If v has two reticulation children, then v is unstable.

(2) Assume v has two children u and w such that u is a tree vertex with two reticulation children and w is a reticulation vertex (Fig. 1). If w is different from the children of u, then v is unstable.

Proposition 2.2. The following facts hold for a network. (1) A vertex u is stable if it has a stable tree vertex as a child.

(2) A reticulation u is stable if and only if its unique child is a stable tree vertex.

(3) If u and v are stable ancestors of w, then either u is an ancestor of v or vice versa.

Proof. [START_REF] Arenas | Characterization of reticulate networks based on the coalescent with recombination[END_REF]. Let v be a child of u. Assume it is a tree vertex and stable. Since v is stable, then it is a stable ancestor of some network leaf . Since v is a tree vertex, u is the unique parent of v. Taken together, both facts imply that all paths from ρ N to must contain v and hence u. Therefore, u is also stable on .

(2). The sufficiency follows from [START_REF] Arenas | Characterization of reticulate networks based on the coalescent with recombination[END_REF]. To prove the necessity, we assume that u is a reticulation stable on a leaf and let x denote its unique child. Since every path from ρ N to goes through u, each such path must also go through x, which is therefore stable on .

We now show by contradiction that x is a tree vertex: if x is a reticulation, it has another parent v different from u. For a path from ρ N to passing u, it also passes x and so joining a path from ρ N to v, the edge (v, x) and a path from x to gives a path from ρ N to avoiding u, contradicting the fact that u is stable on . Therefore, x must be a tree vertex.

(3) The fact follows from the fact that both u and v must be within every path from ρ N to w.

We refer to leaves resulting from the removal of edges or vertices as dummy leaves (i.e. leaves that were not leaves in the original network). A network is tree-based if there is an edge set E that contains an incoming edge for each reticulation vertex such that N -E is a spanning tree of N without dummy leaves [START_REF] Francis | Which phylogenetic networks are merely trees with additional arcs?[END_REF]. In [START_REF] Gambette | Locating a tree in a phylogenetic network in quadratic time[END_REF], we used the following result to establish the first upper bound on the size of reticulation-visible network. Although a better bound can be obtained using a different approach, this result is interesting in its own right and therefore presented below. Proof. Let N be a reticulation-visible network and E ⊂ E(N ). If E contains two edges coming out of the same tree vertex, there will be a dummy leaf in N -E. Similarly, if E contains two edges entering the same reticulation vertex, this reticulation vertex will become a vertex of indegree 0 in N -E. Therefore, N -E is a spanning tree of N without dummy leaves if and only if E is a matching covering every reticulation vertex in N .

Since N is reticulation-visible, by the part (2) of Proposition 2.2, the parents of each reticulation vertex are tree vertices. The existence of such a matching can be found by

The tree containment problem

Let (u, v) ∈ E(N ). The contraction of (u, v) in N transforms N into the network with the vertex set V(N )\{v} and the following edge set:

(x, y) ∈ E(N ) | x = v = y ∪ (x, u) | (x, v) ∈ E(N )\{(u, v)} ∪ (u, y) | (v, y) ∈ E(N ) .
Given a phylogenetic tree G and a network N , we say that N displays G if there is a spanning tree T of N such that G is a contraction of T , i.e. T has the same vertex set as N and G can be obtained from T by repeatedly applying contraction to all edges entering either the "dummy" leaves or the vertices of both outdegree and indegree one, where a dummy leaf is a leaf in T but not a leaf in N . Figure 2 shows an example of a network N and a phylogenetic tree that is displayed by N .

The tree containment (TC) problem is to determine whether a given phylogenetic network displays a given phylogenetic tree. We shall discuss the TC problem for network class defined using vertex stability, namely the nearly stable networks.

Nearly stable and genetically stable networks

Inclusion Relationship

A network is tree-child if each of its internal vertices has a child that is a tree vertex [START_REF] Cardona | Comparison of tree-child phylogenetic networks[END_REF].

A binary network is tree-sibling if every reticulation vertex has a sibling that is a tree vertex [START_REF] Cardona | A distance metric for a class of tree-sibling phylogenetic networks[END_REF][START_REF] Nakhleh | Phylogenetic networks[END_REF]. Cordue et al. [START_REF] Cordue | Phylogenetic networks that display a tree twice[END_REF] investigated reticulation-visible networks in which each reticulation has at least a parent p that is connected to some leaf by a path consisting of only tree vertices. Here, such networks are defined to be nearly tree-child networks.

Huson et al. [17, page 164] noted that if a network is tree-child, then all its vertices are stable. We strengthen their result by proving the other direction. Proposition 3.1. A network is tree-child if and only if every vertex is stable in the network.

Proof. The sufficiency follows from Proposition 2.2(2) and Corollary 2.1.

To extend tree-child networks, we introduced two subclasses of phylogenetic networks. A network is nearly stable if for every vertex, either the vertex or its parents are stable [START_REF] Gambette | Locating a tree in a phylogenetic network in quadratic time[END_REF]. It is genetically stable if every reticulation vertex is stable and has at least one stable parent [START_REF] Gambette | Solving the tree containment problem for genetically stable networks in quadratic time[END_REF]. Proposition 3.2.

(1) Every genetically stable network is tree-sibling.

(2) Every tree-child network is nearly stable.

(3) Every nearly tree-child network is genetically stable.

Proof. (2) and (3) follow from the definitions. For (1), let N be a genetically stable network and let p ∈ R(N ). Since N is genetically stable, p has a stable parent p . By Proposition 2.2(2), p is a tree vertex, so it must have another child c. By Corollary 2.1, c is a tree vertex, and N is therefore tree-sibling.

Based on Proposition 3.2, we summarize the relationships between the classes we study and the other network classes for which the complexity of the TC problem is known in

Class sizes

Recombination histories of viruses, hybridization histories of plants, and histories of horizontal gene transfers reported in the literature are often found to be nearly stable or reticulation-visible (see e.g. the networks given in [START_REF] Jenkins | Genealogy-based methods for inference of historical recombination and gene flow and their application in saccharomyces cerevisiae[END_REF][START_REF] Marcussen | Inferring species networks from gene trees in high-polyploid north american and hawaiian violets (viola, violaceae)[END_REF] which are available at http: //phylnet.info/recophync/networkDraw.php).

In order to evaluate whether the class of nearly stable networks is relevant in practice, especially combined with the class of reticulation-visible networks for which there also exists a polynomial-time algorithm solving the TC problem, we used a set of phylogenetic networks randomly generated using a simulation program [START_REF] Arenas | Characterization of reticulate networks based on the coalescent with recombination[END_REF] and calculated the proportion of those networks belonging to the classes1 . Figure 5 summarizes the results of our simulation study. This experiment shows that among networks generated with the coalescent with recombination model, the proportions of reticulation-visible and especially nearly stable networks are significantly larger than that of tree-child networks. Furthermore, the proportion of networks which are reticulation-visible or nearly stable is also significantly larger than the proportion of reticulation-visible networks.

How large can nearly stable and genetically stable networks be?

A network with n leaves may contain an arbitrary large number of non-leaf vertices and hence, unlike phylogenetic trees, its size is not bounded from above by a function of the number of leaves. In [START_REF] Gambette | Locating a tree in a phylogenetic network in quadratic time[END_REF], we proved that a reticulation-visible network with n leaves has at most 10n -9 vertices (including leaves). Later, the tight size bound 8n -7 was proved A network which is reticulation-visible and tree-sibling, but not genetically stable. (B) A network which is genetically stable but neither nearly stable nor nearly tree-child. (C) A network which is nearly tree-child and nearly stable but not tree-child. (D) A network which is nearly tree-child but not nearly stable. Here, the filled vertices are unstable. [3]. In this section, using the decomposition theorem introduced below, we shall first give a short proof of this tight bound. We also show that nearly stable networks have the same tight size bound as reticulation-visible networks, whereas genetically stable networks with n leaves have the tight size bound 6n -5.

A decomposition theorem

Consider a network N . After the removal of all reticulations, N becomes a forest N -R(N ). One connected component of the forest is rooted at ρ N , whereas the other components are each rooted at the child of a reticulation (Figure 6). Since components consist of tree vertices of N , they are called tree vertex components of N . We call them big tree vertex components if they contain more than one vertex.

A reticulation is said to be inner if its two parents belong to the same tree vertex components. Otherwise, it is said to be cross.

We now prove the following decomposition theorem for nearly stable networks, which is similar to Theorem 1 of [START_REF] Gunawan | A decomposition theorem and two algorithms for reticulation-visible networks[END_REF] for reticulation-visible networks.

Theorem 4.1. Let N be a nearly stable or reticulation-visible network with tree vertex components C 0 , C 1 , C 2 , . . . , C r . Then, (1) Each component C j is rooted at a stable tree vertex. Additionally, a vertex is a component root if and only if it is either the network root or the child of a stable reticulation.

(2) Each component C j contains either a network leaf or the two parents of an inner reticulation.

(3) Each component C j contains at least two tree vertices if C j = { } for any leaf ∈ L(N ).

Proof. (1) By definition of a tree vertex component, its root r must be a tree vertex. If r is the root of N , then it is obviously stable. Otherwise, as r is a tree vertex, then its parent p is a reticulation (otherwise r is not a component root). If p is unstable, then r must be stable as N is a nearly stable network, but this contradicts Proposition 2.2(1). Therefore,

A B C Figure 6: (A)
The decomposition of a nearly stable network into ten tree vertex components. Seven components consist of a single leaf. The remaining three "big" components are C 0 , C 1 , and C 2 , where ρ i denotes the root of C i for each i = 1, 2, 3. (B) A network with 3 leaves and 6 reticulations that is both nearly stable and reticulation-visible. (C) A genetically stable network with 4 leaves and 6 reticulations.

Here the filled vertices are unstable ones.

p is a stable reticulation vertex and r is a stable tree vertex according to the part (2) of Proposition 2.2. Clearly, every child of a stable reticulation is a tree vertex, and thus is a component root as well.

(2) For a component C j that does not contain a network leaf, each leaf of C j is a parent of some reticulation below C j . If for any reticulation below C j not all parents are in C j , then, the set of the reticulations satisfies the conditions in Proposition 2.1 and hence the root of C j is not stable, contradicting (1).

(3) Suppose for contradiction that C j contains exactly one tree vertex v and v is not a leaf. Then both children of v are reticulation vertices, and so v is unstable according to Corollary 2.1(1), contradicting the condition (1) above (i.e. v is stable).

For a tree vertex component C of N , we denote its root by ρ C . A tree vertex component

C is below another component D, if there is a path from ρ D to ρ C in N . A lowest big tree
vertex component is a component such that every other component below it contains exactly a single leaf. Such component is always guaranteed to exist, see [START_REF] Gunawan | Locating a tree in a reticulation-visible network in cubic time[END_REF].

Three size bounds

Let N be a network. In this subsection, we use r and t to denote the number of reticulations and non-leaf tree vertices in N . (ii.) If N is reticulation-visible and tree-sibling, r ≤ 2(n -1). In particular, the bound holds for genetically stable networks.

(iii.) If N is nearly stable, then r ≤ 3(n -1).

Proof. (i.) Ignoring the open-edge attached to the root, the network root is of indegree 0 and outdegree 2, the other tree vertices are of indegree 1 and outdegree 2 if they are not leaves, and each reticulation vertex is of indegree 2 and outdegree 1. By the handshaking lemma, 2t + r = t -1 + 2r + n, which is further simplified into:

t = r + n -1. (1)
Additionally, we let c be the number of tree vertex components of N for the rest of the proof. By Theorem 4.1(1), c = r + 1.

Consider a component C. Since N is reticulation-visible, by Theorem 4.1(3), C contains two distinct parents of an inner reticulation if it does not contain a network leaf. Hence,

r + 1 = c ≤ n + t/2. ( 2
)
Replacing t with r + n -1 in Equation ( 2), we obtain that r ≤ 3(n -1).

(ii.) Assume N is reticulation-visible and tree-sibling. We distinguish three types of tree vertices of N by using T i to denote the set of tree vertices with exactly i children being also tree vertices for i = 0, 1, 2, respectively.

Since N is tree-sibling, each reticulation vertex x has a parent v x such that v x is a tree vertex and has x and another tree vertex as its children. Therefore, mapping x to v x is an injective map from R(N ) to T 1 and thus:

r ≤ |T 1 |. (3)
r + 1 = c ≤ |T 0 | + n. (4)
Combining Inequalities (3) and (4) with Equation (1), we have:

2r + 1 ≤ |T 1 | + |T 0 | + n ≤ t + n = r + 2n -1,
and thus r ≤ 2(n -1).

(iii.) Let N be a nearly stable network. Given that each reticulation vertex may or may not be stable, we use r s and r u to denote the numbers of stable and unstable reticulation vertices of N , respectively.

First, for an unstable reticulation vertex, its parents are both stable tree vertices, as N is nearly stable. By Corollary 2.1, a tree vertex with two reticulation children is unstable. This implies that any two different unstable reticulation vertices have distinct parents. Therefore, there are at least 2r u stable tree vertices that have an unstable reticulation child (Fig 7 .B). unstable. This implies that:

c -n ≤ t u , (5)
as there are at most n components that contain at least a network leaf. Additionally, since N is nearly stable, the parent u of v has to be a stable tree vertex. Since v has two reticulation children, by Corollary 2.1, the stability of u implies that the other child of u has to be either a tree vertex (Fig. 7.A) or a child of v (Fig. 7.C). Since there are at least c -n tree vertex components that do not contain any network leaf, there are at least c -n stable tree vertices such that their children are either two tree vertices or a tree vertex and one (stable) reticulation vertex.

In summary, we have shown that (i) N contains at least 2r u stable tree vertices that have an unstable reticulation child and (ii) there are at least c -n stable tree vertices that have no unstable reticulation child. Hence,

t s ≥ (c -n) + 2r u .
By Inequality [START_REF] Cardona | Comparison of tree-child phylogenetic networks[END_REF],

t = t u + t s ≥ 2(c -n) + 2r u .
Since each tree vertex component is rooted at either the network root or the child of a stable reticulation vertex, then, c = r s + 1. Replacing c with r s + 1 and r s + r u with r in the last inequality, we have:

t ≥ 2r + 2 -2n.
This inequality and Eqn. 1 imply that 3(n -1) ≥ r. This completes the proof.

Fig. 6.B gives a nearly stable and reticulation-visible network with 3 leaves and 6 reticulation vertices. Fig. 6.C gives a genetically stable network with 4 leaves and 6 reticulations.

Hence, the second and third bounds in Theorem 4.2 are also tight.

Finally, it is not hard to see that in nearly tree-child network, each tree-vertex component contains at least a network leaf and thus we have r = c -1 ≤ n -1.

A linear-time TC algorithm for nearly stable networks

In this section, we present a recursive linear-time algorithm for TC on nearly stable networks.

Stable tree vertices

Let N be a nearly stable network. Proof. Let x be an unstable tree vertex and y be a child of x in C. Assume y is a tree vertex.

If y was stable, then x would also be stable (Proposition 2.2(1)), a contradiction. Therefore both y and x should be unstable, which contradicts the fact that N is nearly stable, so y cannot be a tree vertex.

In the example given in Figure 8, the stable subtree has four leaves

Proof. Let x ∈ S(C).

Suppose by contradiction that x has no child in C. Then x has two reticulation children r 1 and r 2 . Thus, by Corollary 2.1, x is unstable: contradiction. Then let y be a child of x in C. By definition, y is unstable and thus is not a network leaf. If y is not a leaf of C, there is an unstable tree vertex below y, contradicting that N is nearly stable.

Conversely, let y be a leaf of C but not a network leaf. Then, y has two reticulation children. Thus, by Corollary 2.1, y is unstable. Since N is nearly stable, the parent of y (i.e. the vertex x) must be stable. If the sibling of y is either a reticulation or a leaf of C but not a network leaf, its parent is then a lowest stable vertex in C and hence is in S(C).

Two key lemmas

Let N and G be the given network and phylogenetic tree. We assume that N does not contain any parallel edge nor a vertex with indegree and outdegree one. has only three possible mini-structures given in Figure 9.

Proof. Assume s is stable on a leaf s . The leaf s cannot be in C. Otherwise all the vertices in the path from s to s are stable, contradicting the fact that s ∈ S(C). Thus, s is the unique child of an inner reticulation r below s. Let u be a parent of r. If u is a reticulation, it is then unstable and its parents are two tree vertices equal to or below s in C. Since s ∈ S(C), u and each of its parents below s are unstable, contradicting that N is nearly stable. Hence the parents of r are two tree vertices below s in C.

Since N does not contain parallel edges, at least a parent of r is not s. Let a be such a parent of r. Note that a is a child of s, otherwise, since s ∈ S(C), any parent of the tree vertex a below s in C would not be a leaf of C, therefore contradicting Proposition 5.2. The fact that s ∈ S(C) also implies that a is unstable. Since N is nearly stable, there are no two unstable vertices that appear consecutively in a path. This implies that a must also be a child of s and the other child b of a is a stable reticulation for which the child is a network leaf , as C is a lowest component of N .

Let d be the other parent of r. If d = s, we obtain the mini-structure (1) in Fig. 9. If d = s, the other child of d is also a stable reticulation with a network leaf as its child, as N is nearly stable. If a and d have distinct child other than r, we obtain the mini-structure (2) in Fig. 9. If a and d have the same children, we obtain the mini-structure (3) in Fig. 9.

This completes the proof. Now, we consider network leaves in C. For a network leaf in C, let p be the parent of . The following lemma gives all possible mini-structures of N [p] if the sibling of is not a stable tree vertex. Lemma 5.2. If the sibling of is not a stable tree vertex in C, N [p] has only three possible mini-structures given in Figure 10.

Proof. Let v be the sibling of . It is either a tree vertex or a reticulation vertex.

If v is a stable reticulation, the child of v must be a network leaf. Then, we obtain the mini-structure (1) in Figure 10.

If v is an unstable reticulation, then its child w is a stable reticulation. Clearly, the child of w is a leaf. This gives the mini-structure (2) in Figure 10.

Finally, if v is an unstable tree vertex, the children of v must be stable, as N is nearly stable. By the part (1) of Proposition 2.2, the children of v are stable reticulation vertices, for which the unique child is a network leaf. Otherwise, v is stable. Thus, we obtain the mini-structure (3) in Figure 10. Figure 10: Three possible mini-structures below a tree vertex for which one child is a network leaf and the other is not a stable tree vertex in a lowest component. The vertices q, y and x have undetermined vertex type.

Dissolving the lowest components

In the rest of this discussion, we use x ∧ G y (resp. x -∧ G y) to denote that x and y are (resp. not) siblings in G. We also use par G (v) to denote the parent of v in G.

First, we consider the mini-structure (1) in Figure 10, which is named the "uncle-nephew structure" in [START_REF] Gambette | Locating a tree in a phylogenetic network in quadratic time[END_REF], where two leaves and have the uncle and nephew relationship and q is either a tree or reticulation vertex.

Lemma 5.3. If N contains the mini-structure (1) in Figure 10, define

E = (q, v) if ∧ G ; (p, v) otherwise.
Then N displays G if and only if N -E displays G.

Proof. Let N = N -E. If N displays G, then N also displays G, as N is a subnetwork of N .
To prove the necessity, we assume that N displays G with a spanning tree T such that G is a contraction of T . There are two possible cases.

1. ∧ G : note that T contains either (p, v) or (q, v) exclusively. If T contains (p, v), N displays G, as T is also a spanning tree of N .

If T contains (q, v), let h be the lowest common ancestor of and in T . Since any path to must contain p, p must be in the path from h to p in T and T [h] only has two labeled leaves, namely and .

Define T = T -(q, v)+(p, v). Then, the vertex p becomes the lowest common ancestor of and in T , so T [h] and T [h] do not contain any network leaves other than and . Any edge of T that is not below h is also an edge in T and conversely, so G is a contraction of both T and T . The tree T is a spanning tree of N -(q, v), and thus is the evidence that N -(q, v) displays G.

2. -∧ G : if (p, v) is an edge in T , then and has p as their lowest common ancestor in T , contradicting that and are not sibling in G. Thus, T does not contain (p, v)

and T is also a spanning tree of N -(p, v), implying that N also displays G.

Using the above lemma, we can prove the following facts. These facts suggest that we can dissolve the subnetwork below each s ∈ S(C) by using the structural information on G.

Lemma 5.4. Let s ∈ S(C). Define N as follows.

(i) If N [s] has the mini-structure (1) in Figure 9,

N = N - {(a, r), (c, b)} if ∧ G s , {(a, r), (a, b)} otherwise. ( 7
) (ii) If N [s]
has the mini-structure (2) in Figure 9,

N = N -            {(a, b), (a, r), (d, e)} if neither 1 ∧ G s nor 2 ∧ G s , {(c, b), (d, r), (f, e)} if 1 ∧ G s and par G ( s ) ∧ G 2 , {(c, b), (d, r), (d, e)} if 1 ∧ G s but par G ( s ) -∧ G 2 , {(c, b), (a, r), (f, e)} if 2 ∧ G s and par G ( s ) ∧ G 1 , {(a, b), (a, r), (f, e)} if 2 ∧ G s but par G ( s ) -∧ G 1 . ( 8
) (iii) If N [s] has the mini-structure (3) in Figure 9, N = N -{(a, b), (d, r)}.
Then N displays G if and only if N displays G. (ii) In Eqn. ( 8), the fourth and fifth cases are symmetric to the second and third cases, respectively. Hence, we only consider the first three cases. (iii) In this case, deleting which edge entering at r and b makes no difference. Therefore,

Proof. Since N is a subnetwork of N in each case, N displays G if N displays G.
N displays G if and only if N displays G.
After we modify N [s] according to the rules suggested in Lemma 5.4 for every s ∈ S(C), the subtree below each s consists of network leaves, vertices of degree 2 and/or dummy vertices in the resulting network N (Figure 11). We can further replace N [s] and the corresponding subtree in G by the same leaf s , if they are compatible. Otherwise, we conclude that N does not display G and stop the algorithm.

In summary, the procedure for simplifying the subnetwork below a lowest stable vertex in C is given in Algorithm 1. 1) and ( 2) for the two cases of the mini-structure (1). ( 3) for the mini-structure (3). ( 4)-( 6) for the first three cases of the mini-structure (2). The cases 4 and 5 of the mini-structure (2) are symmetric to the cases 2 and 3, respectively.

Note that no stable reticulation vertex becomes unstable after removing reticulation edges in a network if at least one reticulation edge is kept for each reticulation vertex, which is the case for all the rules of this simplification process. Therefore, after the simplification process terminates, N is still nearly stable. Each of the components different from C may be simplified into a smaller one in N . Additionally, two big tree vertex components may even be merged into one component in N . If N [s] has the mini-structure (2) in Figure 9, calling the procedure first on s affects

N [s] only if V(N [s]) ∩ V(N [s ]
) is equal to {b, 1 }, {e, 2 }, or {b, e, 1 , 2 }. The first two cases are symmetric and thus we consider the following two cases.

CASE 1. V(N [s]) ∩ V(N [s ]) = {b, 1 } (resp. {e, 2 }).
Running the procedure on s may alter N [s] in two possible ways. One possibility is that If some edge entering x or y is deleted when N [s] is modified for some s ∈ S(C), then the involved child of u is contracted and thus u becomes either a dummy leaf or the parent of a network leaf. By Proposition 5.2, u is not in S(C), a contradiction. Now S(C) = ∅. However, there may be reticulation vertices below C. We further simplify C using each of the rules in the following lemma.

Lemma 5.5. Let be a network leaf in C and p be the parent of such that the sibling of is not a stable tree vertex in C. Define N as follows.

4: All the first three cases are not true.

As shown in the third case, either both (v, x) and (v, w) are both in T or none of them is in T . If (v, x) and (v, w) are both in T , then and are sibling and their parent is a sibling of in G, contradiction. Therefore, T is a spanning tree of N . Hence, N also display G. for the two cases of the mini-structure (2) in Fig. 10. ( 3)-( 6) for the four cases of the mini-structure (3) in Fig. 10.

By Lemma 5.5, we can simplify the subnetwork below the parent of each network leaf in C using the following procedure called Dissolve SubntkNearNtkLeaf, which is illustrated in Fig. 12. When the procedure is called on a network leaf, it may alter the subnetwork below the parent of another network leaf. Because of this, when a network leaf is examined, the subnetwork below its parent may have one of the degenerated structures listed in Fig. 13.

For this case, Dissolve DegeneratedCases is called.

By repeatedly simplifying the subnetwork below the parent of each network leaf through the removal of edges entering reticulations and contraction of edges, we will further transform the component into a single vertex or else we will discover that the input network does not display the tree G.

The algorithm

We are now ready to describe a linear-time TC algorithm (Algorithm 4) for nearly stable networks. It is divided into the pre-processing and simplification parts. Roughly speaking, the algorithm first topologically sorts the big tree vertex components and then dissolves these components one by one in a bottom-up manner. Each component is dissolved in two stages.

In the first stage , Dissolve Lowest Stable Vertices is called for each s ∈ S(C). In the second stage, Dissolve SubntkNearNtkLeaf and Dissolve DegenerateCases are repeatedly called. In the rest of this section, we discuss the correctness and running time of the algorithm step by step.

Let N and G be the input nearly stable network and phylogenetic tree with the same set S(C) is empty when line 10 starts. Then, either an internal tree vertex or its parent is in the path from ρ(C) to a network leaf. Moreover, if an internal tree vertex is stable, as assumed in the beginning of this step, its left child is also a stable tree vertex.

Let u be an internal tree vertex in the current component C. Assume at least one child of u ∈ V(C) is a network leaf. Since the vertices in C are traversed in post-order, a network leaf child of u must be visited before u. In particular, line 12 always starts with a network leaf, which is the leftmost leaf of C.

Assume the currently visited vertex = u i is a network leaf and it is the left child of its parent p. Let v be the other child of p in N . There are the following four cases. Clearly, the second foreach loop takes constant operations in each execution.

Taken together, the above facts show the following theorem.

Conclusion

In this paper, we have studied nearly stable and genetically stable networks, two classes that were introduced in the study of the tree containment problem. In particular, we have proved that each nearly (resp. genetically) stable network with n leaves contains at most 3(n -1) (resp. 2(n -1)) reticulation vertices. We have also designed a linear-time TC algorithm for binary nearly stable networks.

This study arises several problems for future study. The cluster containment (CC) problem asks whether or not a given cluster appears in some phylogenetic tree displayed by a given network. Gunawan et al. [START_REF] Gunawan | Locating a tree in a reticulation-visible network in cubic time[END_REF] designed a linear-time algorithm for the CC problem. Now, we have obtained a linear-time algorithm for the TC problem. Is there a linear-time TC algorithm for reticulation-visible networks? If the answer to this question is negative, is there a linear-time TC problem for genetically stable networks?

In each binary nearly stable network, there are at most 3(n -1) reticulation vertices. This is also true for reticulation-visible networks. Is it possible to define a superclass of networks that contains both reticulation-visible networks and nearly stable networks for which the TC and CC problems are still polynomial-time solvable?

Binary nearly stable networks have simple local structures compared with reticulationvisible networks. Hence, it is also interesting to investigate how to efficiently reconstruct nearly stable network models from gene trees or sequence data.

Acknowledgments

The project was financially supported by the 2013 Merlion Programme. ADMG and LXZ were also supported by a Singapore MOE Tier-1 grant R-146-000-238-114.

Figure 1 :

 1 Figure 1: Two types of unstable tree vertices in a network.

Theorem 2 . 1 .

 21 Every reticulation-visible network is tree-based.

Figure 3 .

 3 Figure 3. A reticulation-visible and tree-sibling network is not necessarily genetically stable (Figure 4.A). A genetically stable network is not necessarily nearly tree-child (Figure 4.B). A nearly stable and nearly tree-child network is not necessarily tree-child (Figure 4.C). A nearly tree-child network is not necessarily nearly stable (Figure 4.D).

Figure 3 :

 3 Figure 3: Inclusion relationships between classes of binary phylogenetic networks: an arrow from class A to class B means that A contains B. Class inclusions involving nearly stable and genetically stable are justified in this article (Proposition 3.2); for the other ones, references are available at http://phylnet. info/isiphync/. The boxes of classes where the TC problem is NP-complete are colored gray, the ones where the TC problem is solvable in polynomial time are colored white.

Figure 4 :

 4 Figure 4: (A)A network which is reticulation-visible and tree-sibling, but not genetically stable. (B) A network which is genetically stable but neither nearly stable nor nearly tree-child. (C) A network which is nearly tree-child and nearly stable but not tree-child. (D) A network which is nearly tree-child but not nearly stable. Here, the filled vertices are unstable.

Figure 5 :

 5 Figure 5: Percentage of binary phylogenetic networks on n leaves generated with the coalescent with recombination model (recombination rate r) in each class of phylogenetic networks. The corresponding data is available at http://phylnet.info/recophync/.

Theorem 4 . 2 .

 42 (i.) ([3]) If N is reticulation-visible, then r ≤ 3(n -1).

  Consider a tree vertex component C of N that does not contain any network leaf. By the fact (3) of Theorem 4.1, C contains a leaf v that differs from ρ C . The children of v must be reticulation vertices, and hence v ∈ T 0 (Fig 7.A). Since there are at most n tree vertex components that contain one or more network leaves,

Figure 7 :

 7 Figure 7: Illustration of three types of tree vertices in a nearly stable network. (A) An unstable tree vertex v with two reticulation children and a stable tree vertex u with two tree children. (B) A stable tree vertex u for which a child is an unstable reticulation vertex. (C) A stable tree vertex u that has a common reticulation child with its tree vertex child.

Proposition 5 . 1 .

 51 Consider a lowest big tree vertex component C of N , and let ρ C denote the root of C. Let u be a vertex in C. If u is stable, then all vertices in the path from ρ C to u are stable by Proposition 2.2(1). Therefore, the stable vertices in C span a subtree of C with the same root ρ C (Figure 8.A), called the stable subtree of C. The following proposition characterizes vertices outside the stable subtree. Let N be a nearly stable network, and C be a lowest big tree vertex component of N . Then every unstable tree vertex in C has two reticulation children.

Figure 8 :

 8 Illustration of the idea of our algorithm. A tree-vertex component C of a nearly stable network, where filled vertices are unstable ones and open edges have their end in other components. The orange subtree is the subtree spanned by the stable vertices with four leaves s 1 , s 2 , s 3 , and 9 .

Figure 9 :

 9 Figure 9: Three possible mini-structures below a vertex s ∈ S(C) in a lowest component C. Here, the vertices c and f have undetermined vertex type, each of them can be a tree or reticulation vertex.

  Now, we show how to dissolve a lowest big tree vertex component C by working one by one on the subnetworks below the vertices in S(C) and then the parents of network leaves in C.

  To prove the other direction, assume that N displays G. There is a spanning tree T of N such that G is a contraction of T . (i) The reticulation edge (a, r) is redundant. N -(a, r) is essentially an uncle-nephew structure. Hence by Lemma 5.3, we have N displays G only if N defined in Eqn. (7) displays G.

CASE 1 .

 1 Neither 1 ∧ G s nor 2 ∧ G s . Clearly, neither (a, b) nor (d, e) are in T . Otherwise, either 1 or 2 is the sibling of s , contradicting the assumption. So T is a spanning tree of N -{(a, b), (d, e)}. If (d, r) is in T , then, T is also a spanning tree of N . If (a, r) is in T , then T -{(a, r)} + {(d, r)} also displays G and is a spanning tree of N . Thus, N displays G only if N displays G. CASES 2 and 3. 1 ∧ G s . We first claim that N -(d, r) displays G. If (d, r) is not in T , then the claim is true. If (d, r) is in T , then (d, e) is not in T . Otherwise, s and 2 are siblings in T . Hence, G is also a contraction of T -(d, r) + (a, r), and N -(d, r) displays G. Next, note that there is essentially an uncle-nephew structure on the leaves 1 and s in N -(d, r). Hence, the assumption that 1 ∧ G s implies that N -{(d, r), (c, b)} displays G. Finally, in N -{(d, r), (c, b)}, we have essentially an uncle-nephew structure after contraction of the subtree below a. Therefore, if 2 is the sibling of the parent of 1 and s in G, N -{(d, r), (c, b), (f, e)} displays G. Otherwise, N -{(d, r), (c, b), (d, e)} displays G.

Figure 11 :

 11 Figure 11: The resulting networks after N [s] is simplified. (1) and (2) for the two cases of the mini-structure (1). (3) for the mini-structure (3). (4)-(6) for the first three cases of the mini-structure (2). The cases 4 and 5 of the mini-structure (2) are symmetric to the cases 2 and 3, respectively.

Proposition 5 . 3 .

 53 When working on N [s ] for some s ∈ S(C), we may transform another N [s] into a subtree or a subnetwork of different mini-structure through the elimination of the reticulation vertices that have a parent in both N [s] and N [s ]. The following result describes the possible modifications on the subnetwork N [s] below s ∈ S(C). Let s, s ∈ S(C) such that V(N [s]) ∩ V(N [s ]) = ∅. Calling Dissolve Lowest Stable Vertices on s first will change N [s] into (i) a subnetwork of the ministructure in Figure 9.1, (ii) a three-vertex tree with two network leaves, (iii) a length-2 path from s to a network leaf on which s is stable, or (iv) a subnetwork in which at least a child of s is a stable tree vertex. Proof. To distinguish N [s] before and after the procedure Dissolve Lowest Stable Vertices is called on s , we use N [s] to denote the subnetwork obtained when the procedure terminates. The existence of s such that V(N [s])∩V(N [s ]) = ∅ implies that N [s] has the mini-structure either (1) or (2) in Figure 9. If N [s] has the mini-structure (1) in Figure 9, calling the procedure first on s affects N [s] only if V(N [s]) ∩ V(N [s ]) = {b, }. Therefore, calling the procedure on s may alter N [s] in two possible ways. One possibility is that (a, b) is deleted and then (s, a) is contracted, resulting in N [s] equivalent to a path: s → r → s . The second possibility is that (c, b) is deleted and (a, b) is then contracted, changing the tree vertex a into a tree vertex stable on in N [s] and hence making s not in S(C).

  (a, b) (resp. (d, e)) is deleted and then (s, a) (resp. (s, d)) is contracted, simplifying N [s] into a subnetwork of the mini-structure (1) in Figure 9. The second possibility is that (c, b) (resp. (f, e)) is deleted and (a, b) (resp. (d, e)) is then contracted. This changes the vertex a from an unstable tree vertex into a stable tree vertex. As such, N [s] contains an uncle-nephew structure and s is no longer in S(C).

CASE 2 .

 2 V(N [s]) ∩ V(N [s ]) = {b, e, 1 , 2 }.In this case, N [s ] has the same mini-structure[START_REF] Bondy | Graph Theory[END_REF] inFigure 9. Running the procedure on s may alter N [s] in three possible ways. One possibility is that both (a, b) and (d, e) are deleted and thus both (s, a) and (s, d) are contracted. This makes N [s] equivalent to the path s → r → s . Another possibility is that (a, b) and (f, e) (resp. (c, b) and (d, e)) are deleted and thus (s, a) and (d, e) (resp. (a, b) and (s, d)) are contracted. This makes N [s] essentially equivalent to a 3-vertex tree (s, ( 1 , s )) (resp. (s, ( 2 , s ))). The third possibility is that both (c, b) and (f, e) are deleted and thus both (a, b) and (d, e) are contracted. This changes the vertices a and d from unstable tree vertices into stable tree vertices, making s not in S(C). In N , each vertex of S(C) becomes a new network leaf. Importantly, the following fact is true for the simplified component, which is still called C for convenience. It says that the simplification process will not create new elements for S(C). Proposition 5.4. S(C) = ∅ in N .Proof. Assume the resulting stable subtree of the component contains a leaf u that is not a network leaf of N . Then, u must be an unstable tree vertex in N . Otherwise, either u has a stable tree child in N (and thus in N ), or u is in S(C) and thus becomes a leaf in N , a contradiction. By Proposition 5.1, u has two reticulation children x and y. Since C is a lowest component of N , the unique child for x and y must be a network leaf. If the reticulation edges entering x and y have never been removed, u could not become stable.

Figure 12 :

 12 Figure 12: The resulting networks after N [p] is simplified using each of the rule in Lemma 5.5. (1) and (2) for the two cases of the mini-structure (2) in Fig. 10. (3)-(6) for the four cases of the mini-structure (3) in Fig. 10.

Figure 13 :

 13 Figure 13: The possible degenerated structures of the subnetwork below the parent of a network leaf in a lowest tree component C. In (2) and (4), v can be either an unstable tree vertex or a reticulation vertex.

C1.

  The vertex v is also a network leaf. Then v = u i+1 and p = u i+2 . If and v are not siblings in G, we have the evidence that G is not displayed and hence the algorithm terminates. If and v are siblings in G, then, the algorithm simply moves on to process v = u i+1 . At v, the algorithm will replace p with v and also replace the parent of and v with v in G. As such, when the algorithm processes u i+2 , it has become a network leaf now and {u i+2 , . . . , u t } is still the vertex set of the modified component, listed in the post-order. This explain why the algorithm simply does not act when visiting in this case.C2. The vertex v is not in C, that is, a reticulation vertex. Then, u i+1 = p. If N [p] has the mini-structures (1) and (2) in Fig.10, the procedure Dissolve SubntkNearNtkLeaf is called on . Otherwise, Dissolve DegenerateCases is called on . After p is replaced with a network leaf, then {p = u i+1 , . . . , u t } is the vertex set of the modified component listed in the post-order. C3. The vertex v is a tree vertex but unstable. Then, v = u i+1 and N [p] has the ministructure (3) in Fig.10or a degenerated structure in Fig.13. Similar to the case C2, after Dissolve SubntkNearNtkLeaf or Dissolve DegenerateCases is called on , {p = u i+2 , . . . , u t } is the vertex set of the modified component listed in the post-order. C4. The vertex v is an internal, stable tree vertex in C. This indicates that the subnetwork N [v] contains at least one stable tree vertex and possibly some reticulation vertices.In this case, u i+1 is the leftmost network leaf in C[v]. The algorithm will move on to simplify C[v] into a network leaf and then contracting the parent of both and v into a network leaf. In order to simplify C[v] first, the algorithm simply skips at .

Theorem 5 . 1 .

 51 Algorithm 4 uses O(|L(N )|) operations to solve the TC problem for nearly stable networks N .

A Python script for class recognition as well as the data and the obtained results are available at http://phylnet.info/recophync/, and an online demo is provided at http://phylnet.info/tools/.

else output "G is not displayed" and exit;

contract

has the mini-structure (1) in Figure 10,

(ii) If N [p] has the mini-structure (2) in Figure 10,

has the mini-structure (3) in Figure 10,

Then, N displays G if and only if N displays G.

Assume that N displays G. There exists a spanning tree T of N such that G is a contraction of T .

By Lemma 5.2, there are three possible mini-structures for N [p] shown in Fig. 10. The mini-structure ( 1) is an uncle-nephew structure and thus the sufficiency follows from Lemma 5.3. The sufficiency for the mini-structure (2) in Fig. 10 can be proven similarly.

Suppose N [p] has the mini-structure (3) in Fig. 10, the first and second case in the definition of N are symmetric, so we only need to consider the cases 1, 3 and 4.

1: ∧ G : since T must contain p, T does not contain (v, w). Otherwise, is the sibling of either or depending whether or not (v, x) is in T , contradicting the assumption in this case. This implies that T is a spanning tree of N -(v, w).

is essentially an uncle-nephew structure. By Lemma 5.3,

Notice that T contains p. If T contains exactly one of (v, x) and (v, w), is a sibling of either or in G, contradicting the assumption in this case.


Jean-Bernard Chatelain
email: jean-bernard.chatelain@univ-paris1.fr

Kirsten Ralf
email: kirsten.ralf@esce.fr.

Imperfect Credibility versus No Credibility of Optimal Monetary Policy

Keywords: JEL classi…cation numbers: C61, C62, E31, E52, E58 Ramsey optimal policy under imperfact commitment, zero-credibility policy, Impulse response function, Welfare, New-Keynesian Phillips curve

When the probability of not reneging commitment of optimal monetary policy under quasi-commitment tends to zero, the limit of this equilibrium is qualitatively and quantitatively di¤erent from the discretion equilibrium assuming a zero probability of not reneging commitment for the classic example of the new-Keynesian Phillips curve. The impulse response functions and welfare are di¤erent. The policy rule parameter have opposite signs. The in ‡ation auto-correlation parameter crosses a saddlenode bifurcation when shit…ng to near-zero to zero probability of not reneging commitment. These results are obtained for all values of the elasticity of substitution between goods in monopolistic competition which enters in the welfare loss function and in the slope of the new-Keynesian Phillips curve.

Introduction

The degree of credibility of policy makers, measured by their probability of not reneging their commitment, is a key determinant of the e¢ ciency of stabilization policy. This paper shows that when the probability of not reneging commitment of optimal monetary policy under quasi-commitment [START_REF] Schaumburg | An investigation of the gains from commitment in monetary policy[END_REF], [START_REF] Debortoli | Monetary regime switches and central bank preferences[END_REF]) tends to zero, the limit of this equilibrium is di¤erent from the discretion equilibrium assuming a zero probability of not reneging commitment ("discretionary policy" according to Gali (2015)) for the classic example of the new-Keynesian Phillips curve. These results are obtained when varying the elasticity of substitution between goods in monopolistic competition which enters into the slope of the new-Keynesian Phillips curve and the welfare loss function.

The impulse response functions and welfare are di¤erent. The policy rule parameter have opposite signs. The initial anchor (or jump) of in ‡ation are di¤erent. The in ‡ation auto-correlation (or growth factor) parameter crosses a saddle-node bifurcation when shifting from near-zero to zero probability of not reneging commitment. This is a major qualitative change of stability properties of the economy dynamic system with respect to the robustness to misspeci…cation of stabilization policy. As soon as there is a slight imperfect knowledge of structural parameters by the private sector and by the policy maker, the initial jump of in ‡ation leads to in ‡ation or de ‡ation spirals with discretion equilibrium with a probability equal to one. By contrast, the welfare loss remains moderate for optimal monetary policy under commitment, which leans against in ‡ation spirals even with the same imperfect knowledge of some structural parameters than in ‡ation spirals originated by the complete lack of credibility of the central bank.

Section 2 presents Ramsey optimal policy under imperfect commitment and discretionary policy. Section 3 computes eigenvalues, policy rule parameters, initial anchors of in ‡ation on the cost-push shock, impulse response functions, welfare and robustness to misspeci…cation, in particular for the limit case of near-zero probability versus zero probability of not reneging commmitment. The last section concludes.

2 Limited Credibility versus Zero Credibility For Ever

New-Keynesian Phillips Curve

The reference new-Keynesian Phillips curve is the monetary policy transmission mechanism [START_REF] Gali | Monetary Policy, In ‡ation, and the Business Cycle[END_REF]):

t = E t [ t+1 ] + x t + u t where > 0, 0 < < 1 (1)
where x t represents the welfare-relevant output gap, i.e. the deviation between (log) output and its e¢ cient level. t denotes the rate of in ‡ation between periods t 1 and t. u t denotes a cost-push shock. denotes the discount factor. E t denotes the expectation operator. The cost push shock u t includes an exogenous auto-regressive component: u t = u t 1 + u;t where 0 < < 1 and u;t i.i.d. normal N 0; 2 u (2) Gali (2015) chooses = 0:8 for the calibration of the auto-correlation of the costpush shock. The disturbances u;t are identically and independently distributed (i.i.d.) according to a normal distribution with constant variance 2 u . The reduced-form parameter (denoted ) of the slope of the new-Keynesian Phillips curve relates in ‡ation to marginal cost or to the output gap. It is a non-linear function of four preferences and two technology parameters:

lim "!+1 = 0 < = + ' + L 1 L (1 ) (1 ) (1 L ) (1 L + L ") < max = lim "!1 + (3) with " > 1, 0 < ; L ; < 1, > 0, ' > 0. max = lim "!1 + = + ' + L 1 L (1 ) (1 ) (1 L )
Gali's (2015, chapter 3) calibration of structural parameter is as follows. The representative household discount factor = 0:99. It is also assumed = 1 (log utility) and ' = 1 (a unitary Frisch elasticity of labor supply). For the production functions of the …rms, the measure of decreasing returns to scale of labor is 0

< L = 1=3 < 1 (the pro- duction function is Y = A t L 1 L
where Y is output, L is labor, A t represents the level of technology and 1 L = 2=3). The proportion of …rms who do not reset their price each period 0 < = 2=3 < 1 which corresponds to an average price duration of three quarters. The household's elasticity of substitution between each di¤erentiated intermediate goods is " = 6 > 1, which is assumed to be larger than one. The maximal value of the slope of the new-Keynesian Phillips curve when varying the elasticity of substitution between intermediate goods, max = 0:34 is obtained when the elasticity of substitution tends to one. In what follows, we provide [START_REF] Gali | Monetary Policy, In ‡ation, and the Business Cycle[END_REF] numerical values besides general solution in order to keep insights on orders of magnitude.

= 1 + 1 + 1 3 1 1 3 1 2 3 1 0:99 2 3 2 3 1 1 3 1 1 3 + 1 3 " = 1:02 2 + "
(" = 6) = 0:1275 < max = 0:34:

Welfare loss function

In a monetary policy regime indexed by j, a policy maker has a period loss function

1 2 ( 2 t + x;j x 2 t ).
If the policy maker is maximizing welfare, its preferences x depend on structural parameters of the transmission mechanism [START_REF] Gali | Monetary Policy, In ‡ation, and the Business Cycle[END_REF]:

0 < x = " = + ' + L 1 L (1 ) (1 ) (1 L
) (1 L + L ") 1 " < < max x = 1:02 2 + " 1 " = 0:02125 < if " = 6
For example, with Gali's (2015) calibration of structural parameters: = 1:02 2+" and " = 6, the relative weight of the variance of the policy instrument (output gap) is a very low proportion (2:125%) of the weight on the variance of the policy target (in ‡ation). This is a very low relative cost of changing the policy instrument which implies a fast convergence of the policy target. Both the slope of the monetary transmission mechanism and the policy maker's preferences are decreasing functions of the household's elasticity of substitution between each di¤erentiated goods, whose values varies in " 2 ]1; +1[ (…gures 1 and 2).

Figure 1: Slope of the new-Keynesian Phillips curve (solid curve, = 1:02 2+" ) and relative welfare cost of changing the policy instrument (dash curve, x = 1:02 2+" ") as a function of the elasticity of substitution between di¤erentiated goods.

Elasticity of substitution

Slope, Weight

When the elasticity of substitution tends to one, the slope of the new Keynesian Phillips curve is equal to the relative welfare weight on output gap in proportion of the weight on the variance of the policy target (in ‡ation) in the loss function at its maximal value ( max = 0:34 = x;max with Gali's calibration).

When the elasticity of substitution of di¤erentiated goods tends to in…nity (all other parameters being unchanged), the convergence to zero of the relative welfare weight of the policy instrument in the loss function is faster than the one of the slope of the new-Keynesian Phillips curve.

Limited Credibility with Ramsey optimal policy under quasicommitment

In a monetary policy regime indexed by j, a policy maker may re-optimize on each future period with exogenous probability 1 q strictly below one ("quasi commitment" by Schaumburg and Tambalotti, 2007 and Debortoli and Nunes, 2014)). Following Schaumburg and Tambalotti (2007), we assume that the mandate to minimize the loss function is delegated to a sequence of policy makers with a commitment of random duration. The degree of credibility is modelled as if it is a change of policy-maker with a given probability of reneging commitment and re-optimizing optimal plans. The length of their tenure or "regime" depends on a sequence of exogenous i.i.d. Bernoulli signals f t g t 0 with E t [ t ] t 0 = 1 q, with 0 < q < 1. If t = 1; a new policy maker takes o¢ ce at the beginning of time t. Otherwise, the incumbent stays on. A higher probability q can be interpreted as a higher credibility. As seen below, this leads to use a "credibility adjusted" discount factor q in the policy maker's optimal behavior. Secondly, in this new monetary policy regime indexed by k, there may be a switch of the transmission mechanism parameter (the slope of the Phillips curve) k including in particular, a switch of the representative household's elasticity of substitution between each di¤erentiated goods " k . This implies a switch of welfare preferences x;j = j (" j ) " j . Because structural parameters may change for a new regime k, long run equilibrium values may also change. Under regime j, policy plans solve the following problem (omitting subscript j for the central bank preferences x , transmission mechanism parameter , the auto-correlation of the cost-push shock and its variance of its disturbances " t ):

V jk (u 0 ) = E 0 t=+1 X t=0 ( q) t 1 2 2 t + " x 2 t + (1 q) V jk (u t ) (4)
s.t. t = x t + qE t t+1 + (1 q) E t k t+1 + u t (Lagrange multiplier t+1 ) u t = u t 1 + u;t ,8t 2 N, u 0 given.
The utility the central bank obtains is next period objectives change is denoted V jk . Since when objectives change, the central bank loses its commitment, this value function depends on the policies of the alternative regime. In ‡ation expectations are an average between two terms. The …rst term, with weight q is the in ‡ation that would prevail under the current regime upon which there is commitment. The second term with weight 1 q is the in ‡ation that would be implemented under the alternative regime, which is taken as given by the current central bank. The key change is that the narrow range of values for the discount factor around 0:99 for quarterly data (4% discount rate) is much wider for the "credibility weighted discount factor" of the policy maker: q 2 ]0; 0:99].

Di¤erentiating the Lagrangian with respect to the policy instrument (output gap x t ) and to the policy target (in ‡ation t ) yields the …rst order conditions:

@L @ t = 0 : t + t+1 t = 0 @L @xt = 0 : " x t t+1 = 0 ) x t = x t 1 " t x t = " t+1 = "( t t )
that must hold for t = 1; 2; ::: The central bank's Euler equation ( @L @ t = 0) links recursively the future or current value of central bank's policy instrument x t to its current or past value x t 1 , because of the central bank's relative cost of changing her policy instrument is strictly positive x = " > 0. This non-stationary Euler equation adds an unstable eigenvalue in the central bank's Hamiltonian system including three laws of motion of one forward-looking variable (in ‡ation t ) and of two predetermined variables (u t ; x t ) or (u t ; t ).

The natural boundary condition 0 = 0 minimizes the loss function with respect to in ‡ation at the initial date:

0 = 0 ) x 1 = " 0 = 0 so that 0 = 1 "
x 0 or x 0 = " 0 It predetermines the policy instrument which allows to anchor the forward-looking policy target (in ‡ation). The in ‡ation Euler equation corresponding to period 0 is not an e¤ective constraint for the central bank choosing its optimal plan in period 0. The former commitment to the value of the policy instrument of the previous period x 1 is not an e¤ective constraint. The policy instrument is predetermined at the value zero x 1 = 0 at the period preceding the commitment. Combining the two …rst order conditions to eliminate the Lagrange multipliers yields the optimal initial anchor of forward in ‡ation 0 on the predetermined policy instrument x 0 .

Ljungqvist and Sargent (2012, chapter 19) seek the stationary equilibrium process using the augmented discounted linear quadratic regulator solution of the Hamiltonian system (Hansen and Sargent (2007)) as an intermediate step (Chatelain and Ralf (2017) algorithm). This amount to seek a stable subspace of dimension two in a system of three equations including the marginal condition on the policy instrument (or on the Lagrange multiplier on in ‡ation). The policy instrument is exactly correlated with private sectors variables:

x t = F t + F u u t : (5)
with solutions (see appendix) followed by their values using Gali (2015) calibration ( = 0:99 and q = 1):

F = 1 " = 4:58 and F u = 1 q 1 F = 1:51F = 6:83 = 1 q q F = 1 2 1 + 1 q + " q s 1 4 1 + 1 q + " q 2 1 q = 0:43
We denote the in ‡ation eigenvalue instead of in [START_REF] Gali | Monetary Policy, In ‡ation, and the Business Cycle[END_REF]. It is the solution of the following characteristic polynomial:

2 1 + 1 q + " q + 1 q = 0
The optimal stable dynamics in dimension two are given by (adding Gali (2015) calibration = 0:99 and q = 1):

E t [ t+1 ] u t = 1 q q F = 1 q q F u 0 t u t + 0 1 t E t [ t+1 ] u t = 0:43 0:13 0 0:8 t u t + 0 1 t
The dynamics are unique with an initial optimal anchor of forward-looking in ‡ation on the cost-push forcing variable, which is enforced by the optimal initial anchor of in ‡ation on the policy instrument 0 = 1 " x 0 . This optimal anchor rules out sunspot equilibria:

0 = 1 q u 0 = F u F + " u 0 because x 0 = F 0 + F u u 0 and 0 = 1 " x 0
The policy instrument (output gap) (which can be substituted by the Lagrange multiplier of in ‡ation) is optimally predetermined. The auto-regressive cost-push forcing variable is also predetermined. The optimal solution of the Hamiltonian system indeed satis…es Blanchard and Kahn (1980) determinacy condition with two stable eigenvalues: the in ‡ation persistence parameter and the auto-regressive parameter of the cost-push forcing variable.

This closed loop Ramsey optimal policy is in sharp contrast with the open loop dynamic system before policy intervention where the policy rule parameters are set to zero:

E t [ t+1 ] u t+1 = 1 1 0 t u t + 0 1 t = 1:01 1:01 0 0:8 t u t + 0 1 t
The open loop system has an unstable in ‡ation eigenvalue leading to in ‡ation spirals and a large negative correlation of expected future in ‡ation with current cost-push shock. Both e¤ects are hugely dampened because the elasticity of substitution between di¤erentiated goods is large (" = 6) which implies a small relative cost of changing the policy instrument (output gap) of 2% of the cost of the volatility of in ‡ation in the loss function.

Zero Credibility For Ever

With quasi-commitment, the probability of not reneging commitment could be in…nitely small (near-zero credibility), but it remains strictly positive: for example, q = 10 7 > 0 with q 2 ]0; 1], hence q 2 ]0; 0:99]. An in…nite horizon zero-credibility policy holds when the policy maker re-optimizes with certainty for all future periods: q = 0. This zero-credibility policy is mentioned as "discretionary policy" by [START_REF] Gali | Monetary Policy, In ‡ation, and the Business Cycle[END_REF].

The central bank minimizes its loss function subject to the new-Keynesian Phillips curve and such that private sector and the central bank policy instrument reacts only to the contemporary predetermined variable u t at all periods t with a perfect correlation. Following [START_REF] Gali | Monetary Policy, In ‡ation, and the Business Cycle[END_REF], each period the monetary authority is assumed to choose in ‡ation and output gap in order to minimize the period losses

2 t + " x 2 t (6)
subject to the constraint of the new-Keynesian Phillips curve where the expectation of future in ‡ation is taken as given by the policy maker, because it is a function about future policy instruments (output gaps) and future cost-push shocks which cannot be currently in ‡uenced by the policy maker who has zero credibility for ever.

t = x t + E t [ t+1 ] + u t (7)
The optimality condition implies a policy rule with perfect negative correlation of the policy instrument (output gap) with the policy target (in ‡ation) with constant parameter given by the opposite of the household's elasticity of substitution between goods (with Gali (2015) calibrated value):

x t = " t = 6 t for t = 0; 1; 2; ::: with " > 1.

(

) 8
Using this policy rule to substitute for output gap in the new-Keynesian Phillips curve yields the …rst equation, besides the auto-regressive equation of the cost-push shock:

E t [ t+1 ] u t = 1 + " 1 0 t u t + 0 1 t = 1:78 1:01 0 0:8 t u t + 0 1 t (9)
Assuming that both the policy instrument and the policy target are forward-looking and that the cost-push shock is the only predetermined variable, [START_REF] Blanchard | The solution of linear di¤erence models under rational expectations[END_REF] determinacy condition forces a unique solution which is given by the unique slope of the eigenvectors of the given stable eigenvalue 0 < < 1 of the cost-push shock:

1 + " 1 0 t u t = t u t ) 1 + " t = 1 u t ( 10
)
This slope is the parameter of the exact positive correlation between in ‡ation and the cost-push shock:

t = 1 1 + " u t = 1 1 0:99 0:8 + 0:1275 6 u t = 1:028u t (11)
Combining this equation with the policy rule leads to the exact negative correlation between output gap and the cost-push shock is:

x t = " 1 1 + " u t = 6:166u t ( 12
)
The policy maker lets the output gap and in ‡ation deviate from their targets in exact proportion of the current value of the cost-push shock.

The expected loss function is for zero probability of not reneging commitment (q = 0) with numerical result for Gali's calibration and impulse response functions (u 0 = 1):

W (q = 0) = 1 2 t=+1 X t=0 t 2 t + " x 2 t = 1 2 1 + " " 2 1 1 + " 2 t=+1 X t=0 t t u 0 2 W (q = 0) = 1 2 1 + " (1 + " ) 2 u 2 0 1 2 = 1 2 5:09
3 Bifurcation

In ‡ation eigenvalue

We demonstrate that shifting from limited credibility to zero credibility implies a saddlenode bifurcation of the dynamic system for the new-Keynesian Phillips curve transmission mechanism. The Lagrange multiplier on forward-looking in ‡ation or the policy instrument is optimally predetermined for Ramsey optimal policy. The policy instrument is forward-looking with in…nite horizon zero-credibility policy. This implies an additional stable eigenvalue for Ramsey optimal policy with respect to zero-credibility policy, according to Blanchard and Kahn (1980) determinacy condition. Proposition 1. Saddle-node bifurcation. There is a saddle-node bifurcation on the in ‡ation eigenvalue when shifting from limited credibility q 2 ]0; 1] (stable eigenvalue ) to zero credibility for ever q = 0 (unstable eigenvalue ZC ). Proof: For " 2 ]1; +1[, we seek the limits of " which is an increasing function of ".

lim "!1 + " = + ' + L 1 L (1 ) (1 ) (1 L ) = max = 0:34: lim "!+1 " = + ' + L 1 L (1 ) (1 ) (1 L ) L = max L = 1:02 with 0 < L < 1 ) max < " < max L
Zero-credibility in ‡ation eigenvalue is an increasing function of ". Its boundary conditions are:

1 < 1 < 1 + 1 max < ZC = 1 + 1 " < 1 + 1 max L 1 < 1:01 < 1: 35 < ZC = 1 + 1 " < 2: 04
By contrast, for limited credibility q 2 ]0; 1], is obtained solving a linear quadratic regulator model so that the in ‡ation eigenvalue is necessarily within the range [ 1; 1]. However, the unit root case which is not necessarily excluded in the general linear quadratic regulator solution (Hansen and Sargent (2007)). More precisely, for the new-Keynesian Phillips curve transmission mechanism, limited credibility in ‡ation eigenvalue is a decreasing function of ", of ", of q and of q. To prove that their is a saddle-node bifurcation when shifting from limited credibility q 2 ]0; 1] (stable eigenvalue ) to zero credibility for ever q = 0 (unstable eigenvalue ZC ), it is su¢ cient to prove:

lim q!0 + lim "!1 + = 1 2 1 + 1 q + " q s 1 4 1 + 1 q + " q 2 1 q = 1 1 + max < 1
That is:

lim q!0 + 1 2 1 + 1 q + 1 q max s 1 4 1 + 1 q + 1 q max 2 1 q = 1 1 + max = 0:746 < 1
because when q ! 0 + :

1 + 2 q 1 s 1 4 q (1 + ) 2 ! 1 + 2 q 1 2 4 q (1 + ) 2 = 1 1 +
One also checks that there is no ‡ip bifurcation within the regimes of limited credibility q 2 ]0; 1], seeking the lower bound of the in ‡ation eigenvalue:

lim q!1 lim "!+1 = 1 2 1 + 1 q + " q s 1 4 1 + 1 q + " q 2 1 q = min > 1 min = 1 2 1 + 1 + 1 max L s 1 4 1 + 1 + 1 max L 2 1 = 0:379 > 0 > 1
Hence we demonstrated the saddle-node bifurcation when shifting from limited credibility q 2 ]0; 1] (stable eigenvalue ) to zero credibility for ever q = 0 (unstable eigenvalue ZC ).

0 < min < < 1 1 + max < 1 < 1 + max < ZC < 1 + 1 max L QED.
Figure 2: In ‡ation eigenvalue 1 F as functions of the elasticity of substitution between di¤erentiated goods for " 2 [0; 6] in the case where q = 0 (zero credibility for ever, dash line with its upper asymptote min ) and in the case of limited credibility in four cases: q = 0:001 and q = 10 7 (overlap on the top solid line below one), q = 0:5 (intermediate solid line), and …nally q = 1 (bottom solid line, with a dash line below for its bottom asymptote ). The dash line for 1 corresponds to the saddle-node bifurcation value separating discretion eigenvalue from eigenvalues with limited credibility.

Figure 3: In ‡ation eigenvalue as a decreasing function of credibility for q 2 ]0; 1] and of the elasticity of substitution between goods for di¤erent values: " = 1 (top decreasing line), 6, 20 and …nally 100 and 10 7 which overlap on the bottom decreasing line.

Credibility Eigenvalue

On …gures 1 and 2, the limited credibility eigenvalue has an upper bound equal to 1 1+ max = 0:746 for near zero credibility q and near one elasticity of substitution between goods ". The larger the credibility q, the lower the eigenvalue and the faster the convergence of in ‡ation to equilibrium. The limit eigenvalues obtained with a near-zero probability of not reneging commitment q = 10 7 are widely di¤erent from the eigenvalues obtained with a zero probability of reneging commitment q = 0 for all values of the elasticity of substitution larger than one.

Policy rule response to in ‡ation

This bifurcation between the case where q = 0 (zero credibility for ever) versus the case of limited credibility where q 2 ]0; 1] is caused by opposite feedback mechanism in the policy rule. The in ‡ation rule parameter is an a¢ ne and decreasing function of the in ‡ation eigenvalue according to 1 q for limited credibility or according to 1 ZC for zero credibility.

Proposition 2. For limited credibility, the in ‡ation policy rule parameter F is positive. For zero-credibility, the in ‡ation policy rule is negative and below -1.

Proof. One has:

1 < F ;ZC = " < 1 < 0 < F (13)
For limited credibility:

1 < F ;ZC = " < 1 < 0 < F (14)
For limited credibility, the policy rule parameter of the response to in ‡ation is a decreasing function of credibility q and an increasing function of the elasticity of substitution ". To prove that the policy rule is positive, it is su¢ cient to prove:

lim q!1 lim "!1 + 1 q 0 @ 1 2 1 + 1 q + " q s 1 4 1 + 1 q + " q 2 1 q 1 A > 0 When q ! 1 and when " ! 1 + F 1 0 @ 1 2 1 + 1 + s 1 4 1 + 1 + 2 1 1 A
In this case, one shows in the appendix that F > 0 is equivalent to + > which is true because ! max > 0 (see appendix 4A). Figure 4. Policy rule parameters for di¤erent values of credibility q: 0 (dash line); 10 7 and 10 3 (overlap on the upper solid line); 0:5 (intermediate solid line); 1 (bottom solid line):

Initial anchor of in ‡ation on cost-push shock

Proposition 3. The initial anchor (or jump) of in ‡ation on the cost-push shock is a decreasing function of the elasticity of substitution between goods for both limited credibility and zero credibility policy regimes. It is an increasing function of the limited credibility of the policy maker.

Proof. Output gap and in ‡ation are exactly linearly related at the initial date x 0 = " 0 for limited and zero-credibility case. The anchor of in ‡ation on the cost-push shock are generally di¤erent between limited credibility versus zero credibility:

0 = 1 q u 0 versus 0;ZC = 1 1 + " u 0
For zero credibility, the anchor of in ‡ation is a decreasing function of " which is an increasing function of ". As max < " < max L , the zero credibility initial anchor of in ‡ation ( 0 =u 0 ) is bounded:

0:81 = 1 1 + max L < 1 1 + " < lim "!1 1 1 + " = 1 1 + max = 1: 82 (15)
For limited credibility, the anchor of in ‡ation is a decreasing function of " which is an increasing function of ". As max < " < max L , the zero credibility initial anchor of in ‡ation ( 0 =u 0 ) upper bound.

lim q!1 lim "!1 1 q = lim q!1 lim "!1 1 = 1:02 With: lim q!1 lim "!1 = 1 2 1 + 1 + max s 1 4 1 + 1 + max 2 1 = 0:56
The initial anchor of near-zero credibility is always strictly smaller than the initial anchor in the case of zero credibility. The gap tends to zero when the auto-correlation of the forcing variable tends to zero and when the elasticity of substitution tends to one: 11 ! 0 and " ! 1.

lim q!0 + 1 q = lim q!0 + 1 1 + < 1 1 + " QED.
For Gali (2015) calibration with = 0:8 (which is far from ! 0), for any elasticity of substitution and for any probability of not reneging commitment, the zero credibility initial anchor of in ‡ation is much higher (+80%) than the limited credibility initial anchor of in ‡ation (…gure 5).

Figure 5: Initial anchor of in ‡ation as a decreasing function of the elasticity of substitution for q = 0 (dash line top), q = 1 (solid line, second line from top), q = 0:5 (solid line, third curve from top), q = 10 7 with a value equal to the in ‡ation eigenvalue (solid line, bottom curve) . Figure 6: Initial anchor of in ‡ation as an increasing function of credibility q 2 ]0; 1] for " = 1 (top line), 6 (intermediate line) and 10 7 (bottom line).

Credibility Anchor

As seen in …gure 6, there is a potential trade-o¤ within the cases of limited credibility: more credibility (a higher q 2 ]0; 1]) implies faster convergence on subsequent period over a longer expected duration measured by the in ‡ation eigenvalue, but it allows a higher initial anchor of in ‡ation which slows convergence. Which e¤ect o¤set the other is found computing impulse response functions and welfare losses in the next section.

Impulse response functions and welfare

Impulse response function are shown on …gure 7 for four di¤erent degrees of credibility q: 0 (for ever discretion), 10 7 (limit-discretion), 0:5, 1 (in…nite horizon commitment). The …rst impulse response of zero credibility a markedly over the impulse response functions of in ‡ation with limited credibility. This is re ‡ected in the evaluation of the relative welfare loss. Using table 3 formulas, we replicate Gali (2015) impulse response functions for " = 6.

Table 3: Expected impulse response functions. Credibility Impulse response functions following u 0

F F u q 2 ]0; 1] t u t = 1 q q F = 1 q q F u 0 t 1 q 1 u 0 " 1 1 q F q = 0 t u t = 1 + " 1 0 t 1 1 + " 1 u 0 " 0
Welfare losses for di¤erent elasticity and di¤erent credibility computation are reported in table 4 for [START_REF] Gali | Monetary Policy, In ‡ation, and the Business Cycle[END_REF] calibration. By contrast to discretion equilibrium, we did not …nd a closed form formula for welfare losses in the case of limited credibility. Hence, we simulate the model over 200 periods in order to compute welfare. For comparison with the welfare of in…nite horizon regimes, the limited credibility welfare is arbitrarily computed using a discount factor of = 0:99 instead of q in order to take into account in a approximation the regimes which appears with probability 1 q.

Table 1: Welfare loss in percentage of welfare loss with in…nite horizon commitment (w( q) = W ( q) W (0:99) 1, = 0:99, q = 1).

x "

= " x 2W (0:99) w(0) w(10 7 ) w(0:1) w(0:5) w(0:8) As seen with the impulse response functions in the case " = 6, the gap between discretion and limited commitment is very large. The loss of welfare by comparison between in…nite horizon credibility versus discretion is gigantic ranging from 60% to 118% increases of welfare losses.

When considering limited credibility taking into account the probability of not reneging commitment, the losses are relatively modest (at most an increase of 24% of welfare losses in the limit case of the elasticity of substitution tending to 1) for a wide range of probabilities from 10 7 to 0:8. The welfare gap between limited credibility with a probability of not reneging commitment near zero: q = 10 7 versus q = 0 for discretion model is gigantic. For welfare evaluation, limited credibility is a very distinct model than zero credibility (discretion).

Robustness to misspeci…cation

We assume that there is a misspeci…cation by the private sector and the policy maker on their exact knowledge of parameters ; ; ; "; u 0 so that the initial anchor of in ‡ation 0 deviates from 10% with respect to its value with exact knowledge of parameters. This assumption is grounded by a number of major measurement issues:

1. In ‡ation 0 is not measured with exact precision. This error is related to consumer price index versus core in ‡ation, quality adjusted bias and the revisions of national accounts.

2. A major source of new-Keynesian uncertainty is the measurement of the unobservable cost-push shock initial value u 0 depending on its past value u 1 , on its autocorrelation and on the disturbance 0 . The cost-push shock is indirectly measured an auto-correlated residual. It faces identi…cation issues when an additional lag is included for in ‡ation in hybrid Phillips curve. As a residual, it varies widely depending on misspec…cation of in ‡ation dynamics.

3. The estimated slope ( ; "; L ; ; ; ') of the new-Keynesian Phillips curve in only known with a standard error. It sign is even uncertain (Mavroeidis et al. ( 2015)). It is itself a function of six not so precisely known structural parameters ( ; "; ; ; ; '), in particular the proportion of …rms who do not reset their price at each quarter.

4. The elasticity of substitution between di¤erentiated inputs " in monopolistic competition which enters into welfare relative weight is not precisely known. Some authors may refer to the measurement of Lerner index which are themselves lacking precision, with a calibration of " = 11 instead of Gali (2015) calibration of " = 6.

5. The policy maker discount factor may vary much more with a adjusted discount factor q depending on the probability q of not reoptimizing. For example, Debortoli and Lakdawala (2016) point estimate is b q = 0:81 in a 95% con…dence interval [0:777; 0:851]. Using table 3 formulas, we compute two impulse response functions of out of equilibrium path when facing 10% error on the initial anchor of in ‡ation using using Gali's (2015) calibration.

For near zero credibility (q = 10 7 ), the error gap of 10% with respect to the perfect knowledge optimal path at the initial date is reduced to less than 1% after eight quarters (…gure 8).

For zero credibility (q = 0), the error gap of 10% with respect to the perfect knowledge optimal path at the initial date is increased to 110% after four quarters and to 270% after eight quarters (…gure 9) with in ‡ation or de ‡ation spirals. After six quarters, the divergence of in ‡ation reaches +1% additional in ‡ation with +10% error or 2% additional de ‡ation with 10% error with respect to the perfect knowledge impulse response function.

In the perfect knowledge case, which has a probability zero for practitioners of stabilization policy, the expected impulse response function may suggest that discretionary policy leans against in ‡ation spirals, while using in ‡ation rule parameters destabilizing the in ‡ation eigenvalue. By contrast, in the imperfect knowledge case with zero credibility, the outcome of discretionary policy is a probability equal to one of in ‡ation or de ‡ation spirals. The core behavioral hypothesis that a policy maker sticks to an exactly zero probability of not reneging commitment for ever is also an assumption with a probability zero for practitioners of stabilization policy.

Conclusion

Even in the most favorable case of an elasticity of substitution between goods tending to one, the limited-credibility equilibrium when the probability to renege commitment tends to zero is never the limit of the zero credibility for ever equilibrium: positive sign versus negative sign of the response of the policy instrument to in ‡ation, stability versus instability of the in ‡ation eigenvalue, small versus large initial anchor of in ‡ation, small versus large magnitude of welfare loss, robustness versus lack of robustness to a large range of misspeci…cation and measurement error.

The bifurcation between zero credibility versus limited credibility is a general result for any linear model of the private sector with any number of lags and any number of variables including at least one forward-looking variable with a policy maker quadratic loss function. With limited credibility, the policy maker's Lagrange multipliers of each private sector forward-looking variables are predetermined variables which are eliminated by assumption in the zero credibility model (e.g. Chatelain and Ralf (2017a)). Hence, [START_REF] Blanchard | The solution of linear di¤erence models under rational expectations[END_REF] determinacy condition implies more stable eigenvalues with limited credibility model with respect to zero credibility. For example, including the private sector consumption Euler equation besides the new-Keynesian Phillips curve leads to a Hopf bifurcation [START_REF] Chatelain | Hopf bifurcation from new-Keynesian Taylor rule to Ramsey optimal policy[END_REF]). This also implies that the number of non-collinear variables in a vector auto-regressive representation is smaller with zero credibility than with limited credibility [START_REF] Chatelain | Can we Identify Fed's preferences? Paris School of Economics and SSRN working paper[END_REF]). Adding more variables, more lags and and more parameters in the transmission mechanism may give the illusion that the zero credibility model may …t the data. But this result is obtained in neglecting exact and weak identi…cation issues and the parsimony criterion for the number of parameters when comparing models (Chatelain and Ralf (2018)).

Appendix 1: Augmented Discounted Linear Quadratic Regulator

The new-Keynesian Phillips curve can be written as a function of the Lagrange multiplier where > 0, 0 < < 1 and 0 < q < 1 (Debortoli and Nunes (2014, appendix A). We keep Gali (2015) chapter 5 t+1 notation of the Lagrange multiplier with one step ahead subscript: it corresponds to Debortoli and Nunes (2014) notation t . Our notation for the stable eigenvalue corresponds to Debortoli and Nunes (2014) notations " y = 1= ".

E t t+1 + " q t+1 = 1 q t 1 q u t 1 q q E t j t+1
In what follows, refers to q to simplify notations. The solution of the Hamiltonian system are based on the demonstrations of the augmented discounted linear quadratic regulator in Anderson, Hansen, McGrattan and Sargent [1996], following the steps in Chatelain and Ralf (2017a): 0 @ 1 " 0 0 1 0 0 0 1 The characteristic polynomial of this upper square matrix is:

2 1 + 1 + " + 1 = 0
The Hamiltonian matrix has two stable roots and ( is denoted in Gali (2015)) and one unstable root 1 . The determinant of the matrix is 1 = 1 . Then < q 1 < 1 . The trace of the matrix is

= 1 2 0 @ 1 + 1 + " s 1 + 1 + " 2 4 1 A
Policy rule parameter function of (") and ":

(1 ) 1 1 = " =) 1 1 = " =)

F = 1 = 1 "
Hamiltonian system function of the stable eigenvalue (eliminating "):

Inflation q=0

Error +10%

Error -10%

Figure 7 :

 7 Figure 7: Impulse response function of inflation with q=1, 0.5, 10 -7 and q=0 top curve.

Figure 8

 8 Figure 8 Impulse response of inflation: q=10 -7 and out of equilibrium path +/-10% error.

Figure 9 .

 9 Figure 9. Impulse response of inflation: q=0 and out of equilibrium path +/-10% error.

Proposition A1: Solution of Ricatti and Sylvester equation: Rule parameters P u and P z of the response of the Lagrange multiplier on in ‡ation to exogenous variables:

Demonstration: We use the method of undetermined coe¢ cients of Anderson, Hansen, McGrattan and Sargent's (1996), section 5. The solution is the one that stabilizes the state-costate vector for any initialization of in ‡ation 0 and of the exogenous variables u 0 in a stable subspace of dimension two within a space of dimension three ( t ; t ; u t ) of the Hamiltonian system. We seek a characterization of the Lagrange multiplier t of the form:

To deduce the control law associated with vector (P ; P u ), we substitute it into the Hamiltonian system:

(1 ) 1

We write the last two equations in this system separately:

It follows that:

The …rst equation is such that:

The method of undetermined coe¢ cients implies for the …rst term:

For the second term:

(1

)

QED Proposition A2: Optimal policy rule parameters formulas:

Demonstration:

The …rst order condition relates Lagrange multiplier to the policy instrument:

Proposition A3: From LQR to Gali (2015) vector basis (replace policy target by policy instrument).

One has:

One has:

One has:

Which is Gali (2015) representation of the solution: (1 + + ) 2 ( 1 + + ) 2 = 4 ( + ) > 4 + > which is true.