Juli Án Mestre
email: jmestre@mpi-inf.mpg.de

LAGRANGIAN RELAXATION AND PARTIAL COVER (EXTENDED ABSTRACT)

Keywords: 1998 ACM Subject Classification: G.2.1 Lagrangian Relaxation, Partial Cover, Primal-Dual Algorithms

Lagrangian relaxation has been used extensively in the design of approximation algorithms. This paper studies its strengths and limitations when applied to Partial Cover.

We show that for Partial Cover in general no algorithm that uses Lagrangian relaxation and a Lagrangian Multiplier Preserving (LMP) α-approximation as a black box can yield an approximation factor better than 4 3 α. This matches the upper bound given by Könemann et al. (ESA 2006, pages 468-479).

Faced with this limitation we study a specific, yet broad class of covering problems: Partial Totally Balanced Cover. By carefully analyzing the inner workings of the LMP algorithm we are able to give an almost tight characterization of the integrality gap of the standard linear relaxation of the problem. As a consequence we obtain improved approximations for the Partial version of Multicut and Path Hitting on Trees, Rectangle Stabbing, and Set Cover with ρ-Blocks.

Introduction

Lagrangian relaxation has been used extensively in the design of approximation algorithms for a variety of problems such as k-MST [START_REF] Garg | A 3-approximation for the minimum tree spanning k vertices[END_REF][START_REF] Chudak | Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation[END_REF][START_REF] Garg | Saving an epsilon: a 2-approximation for the k-MST problem in graphs[END_REF], k-median [START_REF] Jain | Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation[END_REF][START_REF] Charikar | Improved combinatorial algorithms for the facility location and k-median problems[END_REF], MST with degree constraints [START_REF] Könemman | A matter of degree: Improved approximation algorithms for degreebounded minimum spanning trees[END_REF] and budgeted MST [START_REF] Ravi | The constrained minimum spanning tree problem (extended abstract)[END_REF].

In this paper we study the strengths and limitations of Lagrangian relaxation applied to the Partial Cover problem. Let S be collection of subsets of a universal set U with cost c : S → R + and profit p : U → R + , and let P be a target coverage parameter. A set C ⊆ S is a partial cover if the overall profit of elements covered by C is at least P . The objective is to find a minimum cost partial cover.

The high level idea behind Lagrangian relaxation is as follows. In an IP formulation for Partial Cover, the constraint enforcing that at least P profit is covered is relaxed: The constraint is multiplied by a parameter λ and lifted to the objective function. This relaxed IP corresponds, up to a constant factor, to the prize-collecting version of the underlying covering problem in which there is no requirement on how much profit to cover but a penalty of λ p(i) must be paid if we leave element i ∈ U uncovered. An approximation algorithm for the prize-collecting version having the Lagrangian Multiplier Preserving (LMP) property 1 is used to obtain values λ 1 and λ 2 that are close together for which the algorithm produces solutions C 1 and C 2 respectively. These solutions are such that C 1 is inexpensive but unfeasible (covering less than P profit), and C 2 is feasible (covering at least P profit) but potentially very expensive. Finally, these two solutions are combined to obtain a cover that is both inexpensive and feasible.

Broadly speaking there are two ways to combine C 1 and C 2 . One option is to treat the approximation algorithm for the prize-collecting version as a black box, only making use of the LMP property in the analysis. Another option is to focus on a particular LMP algorithm and exploit additional structure that it may offer. Not surprisingly, the latter approach has yielded better approximation guarantees. For example, for k-median compare the 6-approximation of Jain and Vazirani [START_REF] Jain | Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation[END_REF] to the 4-approximation of Charikar and Guha [START_REF] Charikar | Improved combinatorial algorithms for the facility location and k-median problems[END_REF]; for k-MST compare the 5-factor to the 3-factor approximation due to Garg [START_REF] Garg | A 3-approximation for the minimum tree spanning k vertices[END_REF].

The results in this paper support the common belief regarding the inherent weakness of the black-box approach. First, we show a lower bound on the approximation factor achievable for Partial Cover in general using Lagrangian relaxation and the black-box approach that matches the recent upper bound of Könemann et al. [START_REF] Könemann | A unified approach to approximating partial covering problems[END_REF]. To overcome this obstacle, we concentrate on Kolen's algorithm for Prize-Collecting Totally Balanced Cover [START_REF] Kolen | Location problems on trees and in the rectilinear plane[END_REF]. By carefully analyzing the algorithm's inner workings we identify structural similarities between C 1 and C 2 , which we later exploit when combining the two solutions. As a result we derive an almost tight characterization of the integrality gap of the standard linear relaxation for Partial Totally Balanced Cover. This in turn implies improved approximation algorithms for a number of related problems.

Related Work

Much work has been done on covering problems because of both their simple and elegant formulation, and their pervasiveness in different application areas. In its most general form the problem, also known as Set Cover, cannot be approximated within (1 -) ln |U | unless N P ⊆ DTIME(|U | log log |U | ) [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF]. Due to this hardness, easier, special cases have been studied.

A general class of covering problems that can be solved efficiently are those whose element-set incidence matrix is balanced. A 0, 1 matrix is balanced if it does not contain a square submatrix of odd order with row and column sums equal to 2. These matrices were introduced by Berge [START_REF] Berge | Balanced matrices[END_REF] who showed that if A is balanced then the polyhedron {x ≥ 0 : Ax ≥ 1} is integral. A 0, 1 matrix is totally balanced if it does not contain a square submatrix with row and column sums equal to 2 and no identical columns. Kolen [START_REF] Kolen | Location problems on trees and in the rectilinear plane[END_REF] gave a simple primal-dual algorithm that solves optimally the covering problem defined by a totally balanced matrix. A 0, ±1 matrix is totally unimodular if every square submatrix has determinant 0 or ±1. Although totally balanced and totally unimodular matrices are subclasses of balanced matrices, the two classes are neither disjoint nor one is included in the other.

Beyond this point, even minor generalizations can make the covering problem hard. For example, consider the vertex cover problem: Given a graph G = (V, E) we are to choose a minimum size subset of vertices such that every edge is incident on at least one of the chosen vertices. If G is bipartite, the element-set incidence matrix for the problem is totally unimodular; however, if G is a general graph the problem becomes NP-hard [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. 1 The definition of the LMP property is outlined in Section 2.

Numerous approximation algorithms have been developed for vertex cover [START_REF] Hochbaum | Approximation Algorithms for NP-hard Problems[END_REF]. The best known approximation factor for general graphs is 2o(1) [START_REF] Bar-Yehuda | A local-ratio theorem for approximating the weighted vertex cover problem[END_REF][START_REF] Halperin | Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs[END_REF][START_REF] Karakostas | A better approximation ratio for the vertex cover problem[END_REF]; yet, after 25 years of study, the best constant factor approximation for vertex cover remains 2 [START_REF] Clarkson | A modification of the greedy algorithm for vertex cover[END_REF][START_REF] Bar-Yehuda | A linear time approximation algorithm for approximating the weighted vertex cover[END_REF][START_REF] Hochbaum | Approximation algorithms for the set covering and vertex cover problems[END_REF]. This lack of progress has led researchers to seek generalizations of vertex cover that can still be approximated within twice of optimum. One such generalization is the multicut problem on trees: Given a tree T and a collection of pairs of vertices, a cover is formed by a set of edges whose removal separates all pairs. The problem was first studied by Garg et al. [START_REF] Garg | Primal-dual approximation algorithms for integral flow and multicut in trees[END_REF] who gave an elegant primal-dual 2-approximation.

A notable shortcoming of the standard set cover formulation is that certain hard-tocover elements, also known as outliers [START_REF] Charikar | Algorithms for facility location problems with outliers[END_REF], can render the optimal solution very expensive. Motivated by the presence of outliers, the unit-profit partial version calls for a collection of sets covering not all but a specified number k of elements. Partial Multicut, a.k.a. k-Multicut, was recently studied independently by Levin and Segev [START_REF] Levin | Partial multicuts in trees[END_REF] and by Golovin et al. [START_REF] Golovin | Approximating the k-multicut problem[END_REF], who gave a 8 3 + approximation algorithm. This scheme was generalized by Könemann et al. [START_REF] Könemann | A unified approach to approximating partial covering problems[END_REF] who showed how to design a 4 3 α + approximation for any covering problem using Lagrangian relaxation and an α-LMP approximation as a black box. (Their algorithm runs in time polynomial on |U |, |S| 1 and the running time of the α-LMP approximation.)

Our Results and Outline of the Paper

Section 3 shows that for Partial Cover in general no algorithm that uses Lagrangian relaxation and an α-LMP approximation as a black box can yield an approximation factor better than 4 3 α. In Section 4 we give an almost tight characterization of the integrality gap of the standard LP for Partial Totally Balanced Cover, settling a question posed by Golovin et al. [START_REF] Golovin | Approximating the k-multicut problem[END_REF]. Our approach is based on Lagrangian relaxation and Kolen's algorithm. We prove that IP ≤ 1 + 1 3 k-1 LP + k c max for any k ≥ 1, where IP and LP are the costs of the optimal integral and fractional solutions respectively and c max is the cost of the most expensive set in the instance. The trade-off between additive and multiplicative error is not an artifact of our analysis or a shortcoming of our approach. On the contrary, this is precisely how the integrality gap behaves. More specifically, we show a family of instances where IP > 1 + 1 3 k-1 LP + k 2 c max . In other words, there is an unbounded additive gap in terms of c max but as it grows the multiplicative gap narrows exponentially fast.

Finally, we show how the above result can be applied, borrowing ideas from [START_REF] Gaur | Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem[END_REF][START_REF] Hassin | Rounding to an integral program[END_REF][START_REF] Golovin | Approximating the k-multicut problem[END_REF], to get a ρ + approximation or a quasi-polynomial time ρ-approximation for covering problems that can be expressed with a suitable combination of ρ totally-balanced matrices. This translates into improved approximations for a number of problems: a 2 + approximation for the Partial Multicut on Trees [START_REF] Levin | Partial multicuts in trees[END_REF][START_REF] Golovin | Approximating the k-multicut problem[END_REF], a 4 + approximation for Partial Path Hitting on Trees [START_REF] Parekh | Path hitting in acyclic graphs[END_REF], a 2-approximation for Partial Rectangle Stabbing [START_REF] Gaur | Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem[END_REF], and a ρ approximation for Partial Set-Cover with ρ-blocks [START_REF] Hassin | Rounding to an integral program[END_REF]. In addition, the can be removed from the first two approximation guarantees if we allow quasi-polynomial time. It is worth noting that prior to this work, the best approximation ratio for all these problems could be achieved with the framework of Könemann et al. [START_REF] Könemann | A unified approach to approximating partial covering problems[END_REF]. In each case our results improve the approximation ratio by a 4 3 multiplicative factor. Due to lack of space these results only appear in the full version2 of the paper.

Lagrangian relaxation

Let S = {1, . . . , m} be a collection of subsets of a universal set U = {1, . . . , n}. Each set has a cost specified by c ∈ R m + , and each element has a profit specified by p ∈ R n + . Given a target coverage P , the objective of the Partial Cover problem is to find a minimum cost solution C ⊆ S such that p(C) ≥ P , where the notation p(C) denotes the overall profit of elements covered by C. The problem is captured by the IP below. Matrix A = {a ij } ∈ {0, 1} n×m is an element-set incidence matrix, that is, a ij = 1 if and only if element i ∈ U belongs to set j ∈ S; variable x j indicates whether set j is chosen in the solution C; variable r i indicates whether element i is left uncovered.

Lagrangian relaxation is used to get rid of the constraint bounding the profit of uncovered elements to be at most p(U ) -P . The constraint is multiplied by the parameter λ, called Lagrange Multiplier, and is lifted to the objective function. The resulting IP corresponds, up to the constant λ (p(U ) -P ) factor in the objective function, to the prizecollecting version of the covering problem, where the penalty for leaving element i uncovered is λp i .

min c • x Ax + Ir ≥ 1 p • r ≤ p(U ) -P r i , x j ∈ {0, 1} Lagrangian Relaxation min c • x + λp • r -λ (p(U ) -P ) Ax + Ir ≥ 1 r i , x j ∈ {0, 1}
Let OPT be the cost of an optimal partial cover and OPT-PC(λ) be the cost of an optimal prize-collecting cover for a given λ. Let A be an α-approximation for the prizecollecting variant of the problem. Algorithm A is said to have the Lagrangian Multiplier Preserving (LMP) property if it produces a solution C such that

c(C) + α λ p(U ) -p(C) ≤ α OPT-PC(λ).
(2.1)

Note that OPT-PC(λ) ≤ OPT + λ (p(U ) -P ). Thus,

c(C) ≤ α OPT + λ p(C) -P . (2.2)
Therefore, if we could find a value of λ such that C covers exactly P profit then C is α-approximate. However, if p(C) < P , the solution is not feasible, and if p(C) > P , equation (2.2) does not offer any guarantee on the cost of C. Unfortunately, there are cases where no value of λ produces a solution covering exactly P profit. Thus, the idea is to use binary search to find two values λ 1 and λ 2 that are close together and are such that A(λ 1 ) covers less, and A(λ 2 ) covers more than P profit. The two solutions are then combined in some fashion to produce a feasible cover.

Limitations of the black-box approach

A common way to combine the two solutions returned by the α-LMP is to treat the algorithm as a black box, solely relaying on the LMP property (2.1) in the analysis. More formally, an algorithm for Partial Cover that uses Lagrangian relaxation and an α-LMP approximation A as a black box is as follows. First, we are allowed to run A with as many different values of λ as desired; then, the solutions thus found are combined to produce a feasible partial cover. No computational restriction is placed on the second step, except that only sets returned by A may be used. Theorem 3.1. In general, the Partial Cover problem cannot be approximated better than 4 3 α using Lagrangian relaxation and an α-LMP algorithm A as a black box.

Let A 1 , . . . A q and B 1 , . . . B q be sets as depicted on the

B q A 1 A 2 A q . . . . . . right.
For each i and j the intersection A i ∩B j consists of a cluster of q elements. There are q 2 clusters. Set A i is made up of q clusters; set B i is made up of q clusters and two additional elements (the leftmost and rightmost elements in the picture.) Thus |A i | = q 2 and |B i | = q 2 + 2. In addition, there are sets O 1 , . . . , O q , which are not shown in the picture. Set O i contains one element from each cluster and the leftmost element of B i . Thus

|O i | = q 2 + 1. The cost of O i is 1
q , the cost of A i is 2 α 3 q , and the cost of B i is 4 α 3 q . Every element has unit profit and the target coverage is P = q 3 + q. It is not hard to see that O 1 , . . . , O q is an optimal partial cover with a cost of 1.

The α-LMP approximation algorithm we use has the unfortunate property that it never returns sets from the optimal solution. Lemma 3.2. There exists an α-LMP approximation A that for the above instance and any value of λ outputs either ∅ or A 1 , . . . , A q or B 1 , . . . , B q .

The proof that such an algorithm exists is given in the full version of the paper. Hence, if we use A as a black box we must build a partial cover with the sets A 1 , . . . , A q and B 1 , . . . , B q . Note that in order to cover q 2 + q elements either all A-sets, or all B-sets must be used. In the first case q 2 additional B-sets are needed to attain feasibility, and the solution has cost 4 3 α; in the second case the solution is feasible but again has cost 4 3 α. Theorem 3.1 follows.

One assumption usually made in the literature [START_REF] Arora | A 2+ approximation algorithm for the k-MST problem[END_REF][START_REF] Gandhi | Approximation algorithms for partial covering problems[END_REF][START_REF] Könemann | A unified approach to approximating partial covering problems[END_REF] is that c max = max j c j ≤ OPT, for some constant > 0, or more generally an additive error in terms of c max is allowed. This does not help in our construction as c max can be made arbitrarily small by increasing q.

Admittedly, our lower bound example belongs to a specific class of covering problem (every element belongs to at most three sets) and although the example can be embedded into a partial totally unimodular covering problem (see full version), it is not clear how to embed the example into other classes. Nevertheless, the 4 3 α upper bound of Koneman et el. [START_REF] Könemann | A unified approach to approximating partial covering problems[END_REF] makes no assumption about the underlying problem, only using the LMP property (2.1) in the analysis. It was entirely conceivable that the 4 3 α factor could be improved using a different merging strategy-Theorem 3.1 precludes this possibility.

Partial Totally Balanced Cover

In order to overcome the lower bound of Theorem 3.1, one must concentrate on a specific class of covering problems or make additional assumptions about the α-LMP algorithm. In this section we focus on covering problems whose IP matrix A is totally balanced. More specifically, we study the integrality gap of the standard linear relaxation for Partial Totally Balanced Cover (P-TBC) shown below.

Theorem 4.1. Let IP and LP be the cost of the optimal integral and fractional solutions of an instance of P-TBC. Then IP ≤ 1 + 1 3 k-1 LP + k c max for any k ∈ Z + . Furthermore, for any large enough k ∈ Z + the exists an instance where

IP > 1 + 1 3 k-1 LP + k 2 c max . min c • x Ax + Ir ≥ 1 p • r ≤ p(U ) -P r i , x e ≥ 0 LP Duality max 1 • y -(p(U ) -P ) λ A T y ≤ c y ≤ λp y i , λ ≥ 0
The rest of this section is devoted to proving the upper bound in Theorem 4.1, the lower bound is left for the full version of the paper. Our approach is based on Lagrangian relaxation and Kolen's algorithm for Prize-Collecting Totally Balanced Cover (PC-TBC). The latter exploits the fact that a totally balanced matrix can be put into greedy standard form by permuting the order of its rows and columns; in fact, the converse is also true [START_REF] Hoffman | Totally-balanced and greedy matrices[END_REF]. A matrix is in standard greedy form if it does not contain as an induced submatrix

1 1 1 0 (4.1)
There are polynomial time algorithms that can transform a totally balanced matrix into greedy standard form [START_REF] Spinard | Doubly lexical ordering of dense 0-1 matrices[END_REF] by shuffling the rows and columns of A. Since this transformation does not affect the underlying covering problem, we assume that A is given in standard greedy form.

Kolen's algorithm for Prize-Collecting Totally Balanced Cover

For the sake of completeness we describe Kolen's primal-dual algorithm for PC-TBC. The algorithm finds a dual solution y and a primal solution C, which is then pruned in a reverse-delete step to obtain the final solution C. The linear and dual relaxations for PC-TBC appear below.

min c • x + λp • r Ax + Ir ≥ 1 r i , x e ≥ 0 LP Duality max 1 • y A T y ≤ c y ≤ λp y i ≥ 0
The residual cost of the set j w.r.t. y is defined as c j = c ji:a ij =1 y i . The algorithm starts from the trivial dual solution y = 0, and processes the elements in increasing column order of A T . Let i the index of the current element. Its corresponding dual variable, y i , is increased until either the residual cost of some set j containing i equals 0 (we say set j becomes tight), or y i equals λp i (Lines 3-5).

Let C = {j | c j = 0} be the set of tight sets after the dual update is completed. As it stands the cover C may be too expensive to be accounted for using the lower bound provided by 1 • y because a single element may belong to multiple sets in C. The key insight is that some of the sets in C are redundant and can be pruned. A,c,p,λ))

Kolen((

1 // Dual update 2 y ← 0, C ← ∅, C ← ∅ 3 for i ← 1 to n 4 do δ ← min{c j | a ij = 1} 5 y i ← min{λp i , δ} 6 C ← {j | c j = 0} () 7 // Reverse delete 8 while C = ∅ 9 do j ← largest set index in C 10 C ← C + j 11 C ← C \ { j | j dominates j or j = j } 12 return ( C, y)
Definition 4.2. Given sets j 1 , j 2 we say that j 1 dominates j 2 in y if j 1 > j 2 and there exists an item i such that y i > 0 and i belongs to j 1 and j 2 , that is,

a ij 1 = a ij 2 = 1.
The reverse-delete step iteratively identifies the largest index j in C, adds j to C, and removes j and all the sets it dominates. This is repeated until no set is left in C (Lines 8 -11).

Notice that all sets j ∈ C are tight, thus we can pay for set j by charging the dual variables of items that belong to j. Because of the reverse-delete step if y i > 0 then i belongs to at most one set in C; thus in paying for C we charge covered items at most once. Using the fact A is in standard greedy form, it can be shown [START_REF] Kolen | Location problems on trees and in the rectilinear plane[END_REF] that if i was left uncovered then we can afford its penalty, i.e., y i = λp i . The solution C is optimal for PC-TBC since

j∈ b C c j + i∈U s.t. j∈ b C : a ij =1 λp i = i∈U s.t. ∃ j∈ b C : a ij =1 y i + i∈U s.t. j∈ b C : a ij =1 y i = i∈U y i . (4.2)
If we could find a value of λ such that Kolen(A, c, p, λ) returns a solution ( C, y) covering exactly P profit, we are done since from (4.2) it follows that

j∈ b C c j = i∈U y i -λ (p(U ) -P ). (4.3)
Notice that (y, λ) is a feasible for the dual relaxation of P-TBC and its cost is precisely the right hand side of (4.3). Therefore for this instance IP=DL=LP and Theorem 4.1 follows.

Unfortunately, there are cases where no such value of λ exists. Nonetheless, we can always find a threshold value λ such that for any infinitesimally small δ > 0, λ -= λδ and λ + = λ + δ produce solutions covering less and more than P profit respectively. A threshold value can be found using Megiddo's parametric search [START_REF] Megiddo | Combinatorial optimization with rational objective functions[END_REF] by making O(n log m) calls to the procedure Kolen.

Let y (y -) be the dual solution and C (C -) the set of tight sets when Kolen is run on λ (λ -). Without loss of generality assume C covers more than P profit. (The case where C covers less than P profit is symmetrical: we work with y + and C + instead of y -and C -.)

Our plan to prove Theorem 4.1 is to devise an algorithm to merge C and C -in order to obtain a cheap solution covering at least P profit.

Merging two solutions

Before describing the algorithm we need to establish some important properties regarding these two solutions and their corresponding dual solutions.

For any i, the value of y - i is a linear function of δ for all i. This follows from the fact that δ is infinitesimally small. Furthermore, the constant term in this linear function is y i . Lemma 4.3. For each i ∈ U there exists a ∈ Z, independent of δ, such that y - i = y i + aδ. Proof. By induction on the number of iteration of the dual update step of kolen, using the fact that the same property holds for the residual cost of the sets.

A useful corollary of Lemma 4.3 is that C -⊆ C, since if the residual cost of a set is non-zero in y it must necessarily be non-zero in y -. The other way around may not hold.

At the heart of our approach is the notion of a merger graph G = (V, E). The vertex set of G is made up of sets from the two solutions, i.e., V = C ⊕ C -. The edges of G are directed and given by

E = (j 1 , j 2 ) j 1 ∈ C -\ C, j 2 ∈ C \ C -s.t. j 1 dominates j 2 in y -, or j 1 ∈ C \ C -, j 2 ∈ C -\ C s.t. j 1 dominates j 2 in y (4.4)
This graph has a lot of structure that can be exploited when merging the solutions.

Lemma 4.4. The merger graph G = (V, E) of C -and C is a forest of out-branchings.

Proof. First note that G is acyclic, since if (j 1 , j 2 ) ∈ E then necessarily j 1 > j 2 . Thus, it is enough to show that the in-degree of every j ∈ V is at most one. Suppose otherwise, that is, there exist j 1 , j 2 ∈ V such that (j 1 , j), (j 2 , j) ∈ E. Assume that j 1 < j 2 and j ∈ C (the remaining cases are symmetrical). By definition (4.4), we know that j 1 (j 2 ) ∈ C -and that

i 1 i 2 i 2 i 1 j 1 1 1 1 j 1 1 1 1 j 2 1 1 1
there exists i 1 (i 2 ) that belongs to j and j 1 (j 2 ) such that y - i 1 > 0 (y - i 2 > 0). Since A T is in standard greedy form we can infer that i 2 belongs to j 1 if i 1 < i 2 , or i 1 belongs to j 2 if i 1 > i 2 : The diagram on the right shows how, using the fact that A T does not contain (4.1) as an induced submatrix, we can infer that the boxed entries must be 1. In either case we get that j 2 dominates j 1 in y -, which contradicts the fact that both belong to C -. The procedure merge starts from the unfeasible solution D = C -and guided by the merger graph G, it modifies D step by step until feasibility is attained. The operation used to update D is to take the symmetric difference of D and a subtree of G rooted at a vertex r ∈ V , which we denote by T r . For each root r of an out-branchings of G we set D ← D⊕T r , until p(D ⊕ T r ) > P . At this point we return the solution produced by increase(r, D).

Notice that after setting D ← D ⊕ T r in Line 5, the solution D "looks like" C within T r . Indeed, if all roots are processed then D = C. Therefore, at some point we are bound to have p(D ⊕ T r ) > P and to make the call increase(r, D) in Line 6. Before describing increase we need to define a few terms. Let the absolute benefit of set j, which we denote by b j , be the profit of elements uniquely covered by set j, that is,

b j = p i ∈ U | ∀ j ∈ C ∪ C -: a ij = 1 iff j = j . (4.5)
Let D ⊆ C ∪ C -. Note that if j ∈ D, the removal of j decreases the profit covered by D by at least b j ; on the other hand, if j / ∈ D, its addition increases the profit covered by at least b j . This notion of benefit can be extended to subtrees,

∆(T j , D) = j ∈T j \D b j - j ∈T j ∩D b j . (4.6)
We call this quantity the relative benefit of T j with respect to D. It shows how the profit of uniquely covered elements changes when we take D ⊕ T j . Note that ∆(T j , D) can positive or negative.

Everything is in place to explain increase(j, D). The algorithm assumes the input solution is unfeasible but can be made feasible by adding some sets in T j ; more precisely, we assume p(D) ≤ P and P < p(D) + ∆(T j , D). If adding j to D makes the solution feasible then return D + j (Lines 2-3). If there exists a child c of j that can be used to propagate the call down the tree then do that (Lines 4-5). Otherwise, split the subtree The twin procedure decrease(j, D) is essentially symmetrical: Initially the input is feasible but can be made unfeasible by removing some sets in T j ; more precisely p(D) ≥ P and P < p(D) + ∆(T c , D).

At a very high level, the intuition behind the increase/decrease scheme is as follows. In each call one of three things must occur: Finally, the last case to consider is when Lines 7-9 process two or more children j q for all q ≤ k. In this case Adding the cost of {j ≤k } we get the lemma.

Concluding remarks and open problems

The results in this paper suggest that Lagrangian relaxation is a powerful technique for designing approximation algorithms for partial covering problems, even though the blackbox approach may not be able to fully realize its potential.

It would be interesting to extend this study on the strengths and limitation of Lagrangian relaxation to other problems. The obvious candidate is the k-Median problem. Jain and Vazirani [START_REF] Jain | Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation[END_REF] designed a 2α-approximation for k-Median using as a black box an α-LMP approximation for Facility Location. Later, Jain et al. [START_REF] Jain | Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP[END_REF] gave a 2-LMP approximation for Facility Location. Is the algorithm in [START_REF] Jain | Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation[END_REF] optimal in the sense of Theorem 3.1? Can the algorithm in [START_REF] Jain | Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP[END_REF] be turned into a 2-approximation for k-Median by exploiting structural similarities when combining the two solutions?

  merge(( C -, C)) 1 let G be the merger graph forC -and C 2 D ← C - 3 for each root r in G 4 do if p(D ⊕ T r ) ≤ P 5 then then D ← D ⊕ T r 6else return increase(r, D)

  T j : Add j to D and process the children of c, setting D ← D ⊕ T c until D becomes feasible (Lines 6-9). At this point p(D) > P and p(D ⊕ T c ) ≤ P . If Pp(D ⊕ T c ) < p(D) -P then call increase(c, D ⊕ T c ) else call decrease(c, D) and let D be the cover returned by the recursive call (Lines 10-12). Finally, return the cover with minimum cost between D and D . increase((j, D)) 1 // assume p(D) ≤ P < p(D) + ∆(T j , D) 2 if p(D + j) ≥ P 3 then return D + j 4 if ∃ child c of j : p(D) + ∆(T c , D) > P 5 then return increase(c, D) 6 D ← D + j 7 while p(D) ≤ P 8 do c ← child of j maximizing ∆(T c , D) 9 D ← D ⊕ T c 10 if Pp(D ⊕ T c ) < p(D) -P 11 then D ← increase(c, D ⊕ T c ) 12 else D ← decrease(c, D) 13 return min cost {D, D } decrease((j, D)) 1 // assume p(D) ≥ P > p(D) + ∆(T j , D) 2 if p((D ⊕ T j ) + j) ≥ P 3 then return (D ⊕ T j ) + j 4 if ∃ child c of j : p(D) + ∆(T c , D) < P 5 then return decrease(c, D) 6 D ← D + j 7 while p(D) ≥ P 8 do c ← child of j minimizing ∆(T c , D) 9 D ← D ⊕ T c 10 if p(D ⊕ T c ) -P < Pp(D) 11 then D ← increase(c, D) 12 else D ← decrease(c, D ⊕ T c ) 13 return min cost {D ⊕ T c , D }

  |p(D q ) -P | ≥ 3 min |p(D q ) -P |, |p(D q ) -P | = 3 |p(D q+1 ) -P |, (4.9) which implies |p(D 1 ) -P | ≥ 3 k-1 |p(D k ) -P | ≥ 3 k-1 |p(D k ) -P |. Also, λ(Pp(D 1 )) ≤ DL since all elements i not covered by D 1 must be such that y i = λp i . Hence, as before c D k \ {j ≤k } ≤ DL + p(D k ) -P λ ≤ DL + Pp(D 1

Full version available at http://arxiv.org/abs/0712.3936

& & &

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Acknowledgments: I am indebted to Danny Segev for sharing an early draft of [26] and for pointing out Kolen's work. Also thanks to Mohit Singh and Arie Tamir for helpful discussions and to Elena Zotenko for suggesting deriving the result of Section 3.

Supported by NSF Award CCF 0430650, a University of Maryland Dean's Dissertation Fellowship, and partly by an Alexander von Humboldt Fellowship. c J. Mestre

(i) A feasible cover with a small coverage excess is found (Lines 2-3), or (ii) The call is propagated down the tree at no cost (Lines 4-5), or (iii) A subtree T j is split (Lines 6-9). In this case, the cost c j cannot be accounted for, but the offset in coverage |Pp(D)| is reduced at least by a factor of 3.

If the increase/decrease algorithms split many subtrees (incurring a high extra cost) then the offset in coverage must have been very high at the beginning, which means the cost of the dual solution is high and so the splitting cost can be charged to it. In order to flesh out these ideas into a formal proof we need to establish some crucial properties of the merger graph and the algorithms. Proofs are omitted due to lack of space.

Lemma 4.5. If y i < λ p i then there exist j ∈ C and j ∈ C -such that either j = j or (j , j ) ∈ E or (j , j ) ∈ E.

Lemma 4.6. Let (j, D) be the input of increase/decrease. Then at the beginning of each call we have j ∈ D or j ∈ D for all (j , j ) ∈ E. Furthermore, if j ∈ D and j ∈ D then j or j must have been split in a previous call. Recall that y is also a feasible solution for the dual relaxation of P-TBC and its cost is given by DL = n i=1 y i -(p(U ) -P )λ. The following lemma proves the upper bound of Theorem 4.1. Proof. Let us digress for a moment for the sake of exposition. Suppose that in Line 6 of merge, instead of calling increase, we return D = D ⊕ T r . Notice every arc in the merger graph has exactly one endpoint in D . By Lemma 4.5, any element i not covered by D must have y i = λ p i . Furthermore, if y i > 0 then there exists at most one set in D that covers i; if two such sets exist, one must dominate the other in y and y -, which is not possible. Hence,

In the fortunate case that (p(D ) -P )λ ≤ kc max , the lemma would follow. Of course, this need not happen and this is why we make the call to increase instead of returning D .

Let j q be the root of the q th subtree split by increase/decrease. Also let D q the solution right before splitting T jq , and D q and D q be the unfeasible/feasible pair of solutions after the splitting, which are used as parameters in the recursive calls (Lines 11-12). Suppose Lines 7-9 processed only one child of j q , this can only happen in increase, in which case p(D q ) > P but p(D q )b jq < P . The same argument used to derive (4.7) gives us c D q \ {j ≤q } ≤ i∈U y ip(U )p(D q ) + b jq λ ≤ DL (4.8)

The cost of the missing sets is c({j ≤q }) ≤ q c max , thus if q ≤ k the lemma follows. A similar bound can be derived if the recursive call ends in Line 3 before splitting the k th subtree.


Nicolas Abad
email: nicolas.abad@univ-rouen.fr

Firms' Labor Market Power and Aggregate Instability *

Keywords: Monopsony power, local indeterminacy, expectation-driven business cycles. Journal of Economic Literature Classification Numbers: C62, E32, J42

This work proposes to study the emergence of aggregate instability, in the form of macroeconomic fluctuations due to the volatility of agents' expectations, caused by imperfect competition on the labor market. We consider that firms have some monopsony power which is introduced by a) considering that firms face a finite elasticity of labor supply, b) there is a finite number of firms operating under Cournot competition on the labor market. We show that given a free-entry and zero profit conditions, we obtain local indeterminacy when the elasticity of the sectoral labor supply is sufficiently low and factors are substitutable enough. We illustrate numerically our results with some empirical estimates for OECD countries and we conclude that expectation-driven fluctuations is obtained for plausible values.

Introduction

Although the economic effect of monopsony and oligopsony power in the labor market are well known and studied for some particular labor market, as heavily documented in Manning [START_REF] Manning | Monopsony in Motion: Imperfect Competition in Labor Markets[END_REF], the macroeconomic consequences of firms' market power in the labor market through monopsony are less investigated. One potential reason is that the view of a unique firm on the labor market at the aggregate level seems unplausible. Yet, several arguments tend justify the case for monopsony power on the labor market outside the one firm-one market case. From a theoretical point of view, a group of firms may not face an infinitely-elastic labor supply as in the standard view of labor market but an upward-sloping supply. 1 Also, a labor market may be characterized by a finite number of firms which implies a form of concentration on the demand side. Recent empirical contributions of Azar et al. [START_REF] Azar | Concentration in US Labor Markets: Evidence from Online Vacancy Data[END_REF], [START_REF] Azar | Labor market concentration[END_REF] and also Webber [START_REF] Webber | Firm market power and the earnings distribution[END_REF] supports these features and points out that monopsony power and its macroeconomic effects are more significant than we previously thought.

The present paper proposes to account for firms' market power in the labor market in an otherwise standard general equilibrium model and shed light on a new and less expected effect: monopsony power may cause aggregate instability and be a source of expectation-driven fluctuations. A similar mechanism has been found by Dos Santos Ferreira and Lloyd-Braga [START_REF] Santos Ferreira | Non-linear endogenous fluctuations with free entry and variable markups[END_REF], [START_REF] Santos Ferreira | Business cycles with free entry ruled by animal spirits[END_REF] and Jaimovich [START_REF] Jaimovich | Firm Dynamics and Markup Variations: Implications for Multiple Equilibria and Endogenous Economic Fluctuations[END_REF] where imperfect competition in the product markets and an endogenous markup on price leads to an economy with local indeterminacy and sunspot equilibria. 2 Different from these contributions that assume a perfectly competitive labor market, we exploit the symmetry between the markup on price and the markdown on wage 3 to exhibit this original effect of monopsony power.

To introduce firms' market power, we consider that labor supplied by the households is an imperfect substitute across different labor markets and in which firms are large enough, but low with respect to the economy. As a result, we capture two sources of monopsony power: on the one hand, firms face an upwardsloping labor supply at the individual level, on the other hand, there is some concentration of firms on the labor markets. We assume that firms operate under Cournot competition on labor markets and that the number of firms is endogenous by introducing a symmetric free-entry condition. Accordingly, firms' market power, measured by the size of the markup on wage, depends on the degree of substitutability of labor supply across markets and the level of economic activity. In particular, firms have a significantly large market power when the substitutability is low and the markup on wage is decreasing with the level of activity as suggested by empirical evidence (see Jaimovich [START_REF] Jaimovich | Firm Dynamics and Markup Variations: Implications for Multiple Equilibria and Endogenous Economic Fluctuations[END_REF] and Jaimovich and Floetotto [START_REF] Jaimovich | Firm Dynamics, Markup Variations: and the business cycle[END_REF] for evidence of countercyclical markup, and Hirsch et al. [START_REF] Hirsch | Do Employers Have More Monopsony Power in Slack Labor Markets?[END_REF] for empirical evidence of a countercyclical monopsony power). The rest of the model is standard with respect to the literature: we consider infinitely-lived households with separable preferences supplies an infinitely-elastic amount of total labor and choose an optimal plan over time for capital and consumption. Firms have access to a constant return to scale general production allowing for capital and labor substitution and choose their production plan under monopolistic competition on the product markets.

We show that given a minimal degree of monopolistic competition and a high enough substitutability of labor and capital, local indeterminacy arises if the elasticity of substitution of labor across markets is low enough, i.e. when monopsony power is large. Through a numerical illustration, we conclude that this outcome is plausible for a large set of OECD countries. The reason for the emergence of expectation-driven fluctuations in this economy follows that if there is an optimistic expectation about the future, say households anticipate an increase of the wage rate in the future, there is a boom in investment leading to new profit opportunities, and entry of new firms in the market. Since the markdown is countercyclical, the creation of new firms decreases marginal cost due to a more intense competition which shifts production up and makes the initial expectation self-fulfilling.

The rest of the paper is organized as follows. Section 2 presents the model and define the equilibrium solution of agents' behaviour. In Section 3, we focus on the benchmark case where only oligopsony power is considered and study the local dynamics of this benchmark economy. Section 3 contains our main results, provides a numerical illutrastrion to discuss the plausiblity of our conclusions and gives some economic intuition. In Section 5, we draw some concluding comments and all the proofs are given in the Appendix.

The Model

This section describes the details of an infinite horizon economy characterized by oligopsonistic labor markets and presents the subsequent equilibrium conditions.

Households' behavior

We consider an economy populated by a large number of identical infinitelylived agents. We assume without loss of generality that the total population is constant and normalized to one. At each point in time, an agent supplies an infinitely-elastic amount of labor l(t) ∈ [0, l], with l > 1 his time endowment and chooses the allocation of hours worked in labor market i ∈ I, l(i, t). She derives her intertemporal utility from consumption c(t) and disutility from labor l(t) according to the instantaneous utility function U (c t , l t ) such that:

U (c(t), l(t)) = ln(c(t)) -Bl(t) (1)
Where B is a scaling constant. Households face the following budget constraint:

k(t) + c(t) + δk(t) = w(t) p(t) l(t) + r(t) p(t) k(t) (2)
with k(t) the capital stock, with initial condition k(0) = k 0 , w(t) the wage rate, r(t) the rental rate of capital and δ > 0 the depreciation rate of the capital stock, p(t) the price index. Denote the discount rate by ρ > 0 and λ the shadow price of capital, the current-value Hamiltonian writes:

H = ln(c(t)) -Bl(t) + λ(t) w(t) p(t) l(t) + r(t) p(t) k(t) -δk(t) -c(t) (3)
The first-order conditions are:

c(t) -1 = λ(t) (4)
B = λ(t) w(t) p(t) (5)
λ(t) λ(t) = (ρ + δ) - r(t) p(t) (6)
k(t) = w(t) p(t) l(t) + r(t) p(t) k(t) -δk(t) -c(t) (7)
Any solution needs also to satisfy the transversality condition:

lim t→+∞ e -ρt λ(t)k(t) = 0 (8)
We assume that households' labor supply is imperfectly substitutable among many labor markets indexed by i. In particular, the households' total labor supply takes the form:

l(t) = 1 0 l(i) 1+γ γ di γ 1+γ (9)
where γ ∈ (0, +∞) is the elasticity of substitution of hours worked across markets i. Note that we omit the time variable for all the variable depending on i since they are going to be characterized by static solutions. 4 This specification is considered by Berger, Herkenhoff and Mongey [START_REF] Berger | Labor Market Power[END_REF], Horvath [START_REF] Horvath | Sectoral shocks and aggregate fluctuations[END_REF] and Huang and Meng [START_REF] Huang | Increasing returns and unsynchronized wage adjustment in sunspot models of the business cycle[END_REF] while Cardi and Restout [START_REF] Cardi | Imperfect Mobility of Labor across Sectors: A Reappraisal of the Balassa-Samuelson Effect[END_REF] and Katayama and Kim [START_REF] Katayama | Intersectoral Labor Immobility, Sectoral Comovement, and News Shocks[END_REF] follows an identical formulation but restricts to a two sector economy. When γ tends to infinity, the utility cost of modifying hours worked in labor markets i toward another is low and workers favors move their whole time endowment to the labor market with the highest wage. Hence, firms adjust their labor demand to attract workers which leads to wage equalization across all labors markets. In such case, as will be shown below, firms' labor market power is minimal and close to perfect competition. In constrast, when γ is finite and low, a minimal disutility of labor is obtained when workers share an equal working time between the different markets disregarding wage differences: this configuration implies a large labor market power for the firms.

Households' labor income satisfies w(t)l(t) = 1 0 w(i)l(i)di. Given the latter and equation ( 9), the optimal allocation of sectoral labor supply is:

l(i) l(t) = w(i) w(t) γ (10)
with w(t), the wage index:

w(t) = 1 0 w(i) 1+γ di 1 1+γ (11)
A possible interpretation of equation ( 10) can be done as a labor supply in market i relative to total labor supply. When γ tends to 0, then the households inelastically supply a share of their total labor supply to market i, irrespective the difference of the wage of this market with the wage index. If γ tends toward infinity, labor supply is infinitely elastic between sectors and freely moves between them leading to wage equalization as labor is perfectly substitutable across markets. Hence, γ can be interpreted as a wage elasticity of labor.

The production structure

Firms' decisions

There is a final good y(t) produced using n intermediate goods y j (t) according to a CES technology :

y(t) =   n j=1 y j (t) φ-1 φ   φ φ-1 (12)
where φ > 0 is the elasticity of substitution between the intermediate goods. Denote the price of the intermediate good by p j (t) and p =

n j=1 p j (t) 1-φ 1/(1-φ)
, the demand of the intermediate good is given by :

y j (t) y(t) = p j (t) p(t) -φ (13)
In the industry j, there is a unique firm j which is small with respect to the whole economy and produce the intermediate good y j (t). Each firm j ∈ J has access to a constant return to scale technology y j (t) = Af (k j (t), l j (t)) = Al j (t)f (a j (t)) with f (a j (t)) increasing and concave, f (0) = 0 and f (+∞) = +∞ and where a j (t) = kj (t) lj (t) , the intensive stock of capital used by firm j. We impose the following assumption about the production function : Assumption 1. The function f (a j (t)) is twice differentiable, increasing and concave and satisfies f (0) = +∞, f (+∞) = 0

We define s(a j ) = aj f (aj ) f (aj ) , the elasticity of the production with respect to the intensive stock of capital and σ(a j ) =

-(1-s(aj )f (aj ) aj f (aj )
, the capital-labor elasticity of substitution. The firm also faces a fixed cost F . Furthermore, since there are n(i, t) firms within each labor market i and a unique firm on the n(t) intermediate good markets, we assume Cournot competition over labor but monopolistic competition on the product markets. It follows that firm j takes into account the demand for good j and the labor supply in labor market i as respectively given by equations ( 10) and [START_REF] Horvath | Sectoral shocks and aggregate fluctuations[END_REF]. Hence, the profit maximization program is given by:

π j = max yj ,lj ,kj p(y j (t))y j (t) -w(l(i))l j (t) -r(t)k j (t) s.t. y j (t) = Al j (t)f (a j (t)) -F p(y j (t)) = p(t) yj (t) y(t) -1 φ w(l(i)) = w(t) l(i) l(t) 1 γ l(i) = n j=1 l j (t) (14)
The first-order conditions are :

r(t) pj (t) = (1 -ε p )Af (a(t)) w(i) pj (t) = (1-εp) (1+εw) A[f (a(t)) -a(t)f (a(t))] y j (t) = Al j (t)f (a j (t)) -F (15)
with ε p ≡ 1 φ and ε w ≡ ∂w ∂lj lj w = lj γ J lj which are respectively the markup rule on price and the markdown on the wage rate. It follows that the markup decreases when the substitutability of the intermediate goods while and the markdown decreases when the wage elasticity of labor supply in market i increases.

Symmetric Equilibrium

We consider a symmetric equilibrium n(t) = n(i, t) with the following aggregate variables k(t) = n(t)k j (t), l(t) ≡ l(t) = n(t)l j (t), y(t) = n(t)y j (t), p(t) ≡ p j (t) and w(t) ≡ w(t). It follows that the markdown on the wage is given by ε w ≡ ε w (n(t)) = 1 γn(t) . Note that the latter expression implies that the markdown evolves in an opposite direction with respect to the number of firms: a higher number of firms implies ceteris paribus a tougher competition and reduces the markdown on wage which increases, in return the wage rate.

Given a symmetric equilibrium, we introduce a free-entry restriction which leads to the usual zero profit condition:

n(t)l(t) f (a(t)) - w(t) p(t) - r(t) p(t) a(t) = F (16)
Using the latter condition, the definition of the production technology, y(t) = Al(t)f (a(t) -F , and the first-order conditions (15), we find5

Al(t)f (a(t)) = [1+εw(n(t))]n(t)F [(1-s)(1-εp)εw(n(t))+εp(1+εw(n(t)))] y(t) = (1-εp)[1+s(a(t))εw(n(t))]n(t)F [(1-s)(1-εp)εw(n(t))+εp(1+εw(n(t)))] (17)
From these expressions and the first-order conditions, the interest rate and the wage rate write:

r(t) p(t) = s(a(t))[1+εw(n(t))]y(t) [1(t)+s(a(t))εw(n(t))]k(t) w(t) p(t) = [1-s(a(t))]y(t) [1+s(a(t))εw(n(t))]l(t) (18)
Where the aggregate price index p(t) is normalized to unity from now on. In the next section, we define the intertemporal equilibrium of this economy and derive steady state conclusions.

Intertemporal equilibrium and steady state analysis

Recall that a(t) = k(t) l(t) . We solve the system (17) to get n(k(t), y(t)) and l(k(t), y(t)). It follows that ε w (n(t)) ≡ ε w (k(t), y(t)) and a(t) ≡ a(k(t), y(t)) = k(t) l(k(t),y(t)) from which we derive s(a(t)) ≡ s(k(t), y(t)), w(t) ≡ w(k(t), y(t)), r(t) ≡ r(k(t), y(t)) and σ(a(t)) ≡ σ(k(t), y(t)). 6We combine the first-order conditions ( 4)-( 5) and obtain the equilibrium value of consumption:

Bc(k(t), y(t)) = (1 -s(k(t), y(t)))y(t) [1 + s(k(t), y(t))ε w (k(t), y(t))]l(k(t), y(t)) (19)
We differentiate with respect to time the first-order condition ( 4) and ( 19) to get:

λ(t) λ(t) = ε cy ẏ(t) y(t) + ε ck k(t) k(t) (20)
with ε cy = ∂c(k(t),y(t)) ∂y(t)

y(t) c(k(y(t),k(t)) and ε ck = ∂c(k(t),y(t)) ∂k(t) k(t) c(k(y(t),k(t))
. We substitute this expression in equation ( 6) to write the Euler equation :

ẏ(t) y(t) = s(k(t),y(t))(1+εw(k(t),y(t))y(t) k(t)(1+s(k(t),y(t))εw(k(t),y(t)) -(ρ + δ) -ε ck k(t) k(t) ε cy (21)
From the households' budget constraint, we obtain the aggregat resource constraint:

k(t) = y(t) -δk(t) -c(k(t), y(t)) (22)
An intertemporal equilibrium is a path {k(t), y(t)} t≥0 with k(0) = k 0 > 0, satisfying equations ( 21)-( 22) and the transversality condition [START_REF] De Loecker | The rise of Market Power and the Macroeconomic Implications[END_REF].

A steady state is a solution (k * , a * , c * , y * , n * ), satisfying:

c * = y * -δk * s(a * )(1+εw(n * ))y * [(1+s(a * )εw(n * ))k * ] = (ρ + δ) A k * a * f (a * ) = [1+εw(n * )]n * F [(1-s(a * ))(1-εp)εw(n * )+εp(1+εw(n * )] y * = (1-εp)(1+s(a * )εw(n * ))n * F [(1-s(a * ))(1-εp)εw(n * )+εp(1+εw(n * )] Bc * = (1-s(a * ))a * y * [1+s(a * )εw(n * )]k * (23) with a * = k * /l * , s(a * ) = a * f (a * ) f (a * )
and ε w (n * ) = 1 γn * . Solving the previous system gives:

c * = [ρ+δ(1-s)+sρε(n * )](1-εp)n * F (ρ+δ)[(1-s(a * ))(1-εp)εw(n * )+εp(1+εw(n * )] k * = s(a * )(1+ε(n * ))(1-εp) * F (ρ+δ)[(1-s(a * ))(1-εp)εw(n * )+εp(1+εw(n * )] Af (a * ) = (ρ+δ) (1-εp) y * = (1-εp)(1+s(a * )εw(n * ))n * F [(1-s(a * ))(1-εp)εw(n * )+εp(1+εw(n * )] B [ρ+δ(1-s(a * ))+s(a * )ρ+εw(n * )](1+εw(n * )nF [(1-s(a * ))(1-εp)εw(n * )+εp(1+εw(n * )] = (ρ+δ) 2 a * (1-s(a * )) s(a * )(1-εp) (24)
We can now derive a first result about the steady state: We use the scaling parameters A, B > 0 to ensure the existence of a normalized steady state (NSS) with a * = 1 and n * = n, an arbitrary number of firms, which remains invariant with respect to preferences and technological parameters. Hence, we derive: Proposition 3. Under Assumption 1, the solution (k * , 1, c * , y * , n) of the system (24) is a NSS if and only if A = A * and B = B * with

A * = (ρ+δ) s(1)f (1) B * = (ρ+δ) 2 (1-s(1))[(1-s(1))(1-εp)εw(n)+εp(1+εw(n)] s(1)(1-εp)[ρ+δ(1-s(1))+s(1)ρ+εw(n)](1+εw(n))nF
This normalization procedure allows to use parameters of interest ε w ≡ ε w (n), σ ≡ σ(1) and s ≡ s(1) that are independent of the steady state.

We devote the next section to study the stability of properties of the model. In particular, we analytically derive the main results of this paper, that an economy concerned by a strong monopsony power on the labor market may experience expectation-driven fluctuations through local indeterminacy, then we discuss the likelihood of our results through a quantitative exercise.

Expectation-driven Fluctuations and Aggregate Instability

To study the local dynamics, we linearize the system ( 21)-( 22) around the NSS. The characteristic polynomial of the Jacobian matrix is given by P (λ) = λ 2 -T rλ + Det with:

Det = (ρ+δ)V (εw) P (εw) T r = ρ - (ρ+δ)εpεw(1-s) P (εw)
where :

V (ε w ) = a v ε 2 w + b v ε w + c v , P (ε w ) = a p ε 2 w + b p ε w + c p a v = 1 + sρ ρ+δ(1-s) + εp (1-s)(1-εp) , a p = 1 - 2s(1-εp) σ - sεp σ(1-s) b v = 2 + εp (1-s)(1-εp) , b p = 2s(1-εp) σ + 2sεp σ(1-s) -ε p c v = 2εp (1-s)(1-εp) , c p = -sεp σ(1-s) (25)
Given that we have one predetermined variable, the necessary and sufficient conditions to obtain a sink, and therefore local indeterminacy, are D > 0 and T r < 0 while the NSS displays saddle-path stability if D < 0 and is a source if and only if D > 0 and T r > 0. Furthermore, a Hopf bifurcation occurs when D > 0 and T r = 0. In that case, the economy displays persistent fluctuations through the emergence of period cycles. 7Note that ε w = 1 γ n so that, for any given n, the parameter ε w ∈ (0, +∞) is varying continuously through the parameter γ which measures the substitutability of labor supply across industries and reflects the degree of firms' monopsony power.

We derive first a proposition that ensures saddle-path stability of the NSS:

Proposition 4. Under Assumption 1, there exists σ > 0 such that the NSS is always locally determinate if σ < σ.

Proof: see Appendix 5.5

After deriving when local indeterminacy is ruled out, the following Proposition establishes our main results : Proposition 5. Under Assumption 1, there is a critical value σ > 0, such that for any given value σ > σ and ε p > 0, there exists εw and ε w ∈ (0, εw ) such the NSS is a saddle-path if and only if ε w ∈ (0, ε w ), is a sink if and only if ε w ∈ (ε w , εw ), undergoes a Hopf bifurcation if ε w = εw and is a source if and only ε w > εw .

Proof : see Appendix 5.6 From this Proposition, we derive that local indeterminacy and expectationdriven fluctuations require a low enough γ (i.e. a high monopsonic power from the firms) given that the capital and labor are substitute enough. It is worth noticing that the condition ε w > ε w and σ > σ implies an upward-sloping labor demand as in Benhabib and Farmer [START_REF] Benhabib | Indeterminacy and Increasing Returns[END_REF]. Note that this condition is also equivalent to a positive consumption-output equilibrium relationship as it implies ε cy > 0. The economic mechanism for expectation-driven fluctuations goes as follows. Departing from the steady state, Assume that households have an expectation of a future wage increase and anticipate therefore the labor supply to increase. This makes future interest rate more attractive which leads to a soar in investment. Since the capital stock in the present is predetermined, households must increase their labor supply to provide the necessary additional output. This leads to the creation of new firms and reduces the markdown which results in an increase in the current wage. The initial expectation is therefore self-fulfilling.

To discuss the plausibility of our results, we consider a crude but indicative calibration of the deep parameters our model. We consider the following:

Parameters s ρ δ ε p σ Values 0.3 0.001 0.02 0.05 (0.6,2 .5)
The first three parameters have been chosen according on a quaterly basis and so that to match an annual return of capital of 8 per cent. We also consider a small value of ε p as a benchmark case and to avoid strong deviations from perfect competition on the product markets. Considering a particular value for the capital-labor elasticity of substitution is more problematic: while most recent contributions conclude that capital and labor are complement (σ < 1), the highest estimates found in the literature focus on a value of σ between 1.25 and 3.25 (see Duffy and Papageorgiou [START_REF] Duffy | A Cross-Country Empirical Investigation of the Aggregate Production Function Specification[END_REF] and Karagiannis et al. [START_REF] Karagiannis | Variable Elasticity of Substitution and Economic Growth: Theory and Evidence[END_REF]). We first compute the value of σ = 0.58 implying that for most of the empirical value of σ, the relevant condition is σ > σ.

Given this condition, we find that local indeterminacy occurs for any value of the markdown ε w ∈ (1, 42, 2.27) if σ = 0.8 and ε w ∈ (0.6, 1.16) if σ = 1.5

Assuming n = 2, we plot the critical values of γ leading to local indeterminacy for the relevant range of σ in Figure 3. The lower line is the values of the Hopf bifurcation while the upper line represents the necessary condition on γ.

As shown by figure 3, local indeterminacy occurs for any γ ∈ (0.22, 0.35) if σ = 0.8 and γ ∈ (0.72, 1.70) if σ = 2.5. Furthermore, the interval between the lower and upper bound gets wider as σ increases. Furthermore, an increase in ε p shifts both curve downward Such values have to be compared with known estimates of γ which highly depends on how this parameters is interpreted. If the interpretation of the individual wage elasticity of labor supply is assumed, the literature review by Reichling and Whalen [START_REF] Reichling | Estimates of the Frisch Elasticity of Labor Supply: A Review[END_REF] concludes of a range γ ∈ (0.27, 0.53) with a central tendency around 0.4. The investigations made by Berger, Hergenkoff and Mongey [START_REF] Berger | Labor Market Power[END_REF] and Katayama and Kim [START_REF] Katayama | Intersectoral Labor Immobility, Sectoral Comovement, and News Shocks[END_REF] find a value of γ around unity for the recent years.

A detailed country estimation is provided by Cardi and Restout [START_REF] Cardi | Imperfect Mobility of Labor across Sectors: A Reappraisal of the Balassa-Samuelson Effect[END_REF] in their two sector framework. Using panel techniques, they find that the average value of γ for main OECD countries is around 0.62, with a minimum of 0.216 and a maximum of 1.82. 8 We conclude therefore that monopsony power on the labor market is likely to be a source of destabilization, even with a minimal degree of imperfect competition on the product market.

Concluding Comments

This paper considers firms' monopsony power on the labor market as a potential source of expectation-driven fluctuations in a dynamic general equilibrium model. While the effect of monopsony power on wage and participation are well document, its consequence on dynamic properties, and in particular for the emergence of local indeterminacy, is less, if not, studied. To investigate such properties, we considered a simple model where households' labor supply is imperfectly substitutable across labor markets implying that firms in a labor market face an upward-sloping labor supply. As a result, firms exert a market power by paying a wage that is lower than the marginal product of labor. Given minimal assumptions, we show that local indeterminacy arises as soon as this market power is large enough, capital and labor are substitutes and we find that our results are plausible according a numerical illustration.

These conclusions stands within a wide range of literature. First, it completes and converges to the conclusion of Dos Santos Ferreira and Lloyd-Braga [START_REF] Santos Ferreira | Non-linear endogenous fluctuations with free entry and variable markups[END_REF], [START_REF] Santos Ferreira | Business cycles with free entry ruled by animal spirits[END_REF] and Jaimovich [START_REF] Jaimovich | Firm Dynamics and Markup Variations: Implications for Multiple Equilibria and Endogenous Economic Fluctuations[END_REF] who study the emergence of local indeterminacy and expectation-driven fluctuations under oligopolistic competition and freeentry. It also contributes to the general equilibrium modelling of firms' labor market power in imperfectly competitive economy as recently renewed by Azar and Vives [START_REF] Azar | Oligopoly, Macroeconomic Performance, and Competition Policy[END_REF] or Berger, Herkenhoff and Mongey [START_REF] Berger | Labor Market Power[END_REF]. While the consideration of imperfect substitutability of labor supply has attracted more and more contributions, in particular in the DSGE literature (e.g. Cardi and Restout [START_REF] Cardi | Imperfect Mobility of Labor across Sectors: A Reappraisal of the Balassa-Samuelson Effect[END_REF], Horvath [START_REF] Horvath | Sectoral shocks and aggregate fluctuations[END_REF], Huang and Meng [START_REF] Huang | Increasing returns and unsynchronized wage adjustment in sunspot models of the business cycle[END_REF], Katayama and Kim [START_REF] Katayama | Intersectoral Labor Immobility, Sectoral Comovement, and News Shocks[END_REF]), most of them still consider a perfectly competitive labor market ruling out firms' market power on this market and leaving aside potentially significant effects at the macroeconomic level.

Appendix

Proof of Proposition 1

From the third equation of the system (24) and under Assumption 1, we notice that there is a unique a * . Hence, all the terms in the last equation varies with n * only and we can show that the left-hand side tends to zero when n * = 0 while it tends to +∞ as n becomes arbitrary large. Furthermore, the left-hand side is strictly increasing with respect to n * implying that n * is also unique. Since k * , c * and y * depends only on a * and n * , the rest of the system admits a unique solution.

Proof of Proposition 2

Consider the expression for the share of labor income, α = (1-s(a) * ) (1+s(a * )εw(n * ) . An increase in the market power means that the markdown on wage ε w increases. We easily obtain that the derivative of the latter expression is given by:

dα dε w = -(1 -s(a * )s(a * ) [(1 + s(a * )ε w (n * )] 2 (26)
Although it is trivial to show that ε w is decreasing with respect to n * or γ, there is also a steady state relationship between the n * and γ. From the last equation of the system (24), we can derive implicitly that dn * dγ > 0. We conclude therefore:

dα dγ = (1 -s(a * )s(a * ) [(1 + s(a * )ε w (n * )] 2 (1 + dn * dγ ) (γn * ) 2 (27)

Derivation of the main elasticities

Using equations in [START_REF] Karagiannis | Variable Elasticity of Substitution and Economic Growth: Theory and Evidence[END_REF] and the definition of s = af (a) f (a) with a = k l , we get:

ε ly = (1+εw)∆+(1-s)(1-εp)εw (1-s)E(1+εw)∆ ε lk = -s[E(1+sεw)+(1-1 σ )εw] (1-s)E(1+sεw) ε ny = ∆+(1-1 σ )sεw(1-εp) E∆ ε nk = -s(1-1 σ )εw(1+εw) E(1+sεw)∆ E = 1 -(1 -1 σ ) sεw 1+sεw + (1-s)εw (1+sεw)∆ ) ∆ = [(1 -s)(1 -ε p )ε w + ε p (1 + ε w )] (28)
We also derive the elasticities for w,r and s = af (a) f (a) with a = k l , as a function of the above elasticites. It follows:

ε wy = 1 -ε ly + sεw 1+sεw ε ny + s(1+εw) (1+sεw) (1 -1 σ )εly ε wk = -ε lk + sεw 1+sεw ε nk -s(1+εw) (1+sεw) (1 -1 σ )(1 -εlk) ε ry = 1 - (1-s)εw (1+sεw)(1+εw) ε ny -(1-s) (1+sεw) (1 -1 σ )εly ε rk = -1 - (1-s)εw (1+sεw)(1+εw) ε nk + (1-s) (1+sεw) (1 -1 σ )(1 -εlk)ε sy = -(1 -s)(1 -1 σ )εly ε sk = (1 -s)(1 -1 σ )(1 -εlk) (29)
5.4 Derivation of the determinant and the trace of the Jacobian matrix

Note that form equation [START_REF] Manning | Monopsony in Motion: Imperfect Competition in Labor Markets[END_REF], we find that ε cy = ε wy and ε ck = ε wk . Using the expressions given in (29), we can now linearize the system ( 21)-( 22) in the neighborhood of the steady state to obtain:

d ẏ d k = J dy dk (30)
with J the Jacobian matrix given by:

J =     (

Proof of Proposition 4

Consider the Determinant. The numerator of the determinant is a polynomial of degree two, V (ε w ) with positive coefficient a v , b v , c v > 0. The two roots have the same sign since their product share the same sign than cv av > 0 and are negative since the sign of sum of the two roots satisfies -bv av < 0. Because V (0) > 0, we conclude that V (ε w ) is always positive for any ε w > 0.

The denominator of the Determinant is also a polynomial of degree two. For any σ < σ = s ap < 0, meaning that both roots of P (ε w ) are also negative. Because P (ε) < 0, we find P (ε w ) < 0 for any ε w > 0 and the Determinant is therefore always negative.

Proposition 1 .Proposition 2 .

 12 Under Assumption 1, a steady state (k * , a * , c * , y * , n * ) exists and is unique. Proof : see Appendix 5.1 Exploiting the uniqueness of the steady state, we also find : Define the steady state share of labor income as w * l * y * = (1-s(a) * ) (1+s(a * )εw(n * ) . Then, an increase in monopsony power (due to a decrease in the elasticity of substitution of labor γ or a decrease in n * ) decreases the equilibrium number of firms and the steady state share of labor income. Proof : see Appendix 5.2

Figure 1 :

 1 Figure 1: Plot of destabilizing values of γ for varying σ. Red lines are the Hopf birfucation while blue lines are the necessary conditions. Solid lines are plotted for ε = 0.05, while dashed lines are for ε p = 0.18.

  ρ+δ)εry-y k ε wk (1-εwy c y ) εwy y k(ρ+δ)ε rk + y k ε wk (δ+ε wkAfter some tedious computations, the trace and the determinant of the Jacobian matrix are obtained: beginequationV (ε w ) = a v ε 2 w + b v ε w + c v , P (ε w ) = a p ε 2 w + b p ε w + c p a v = 1 + sρ ρ+δ(1-s) + εp (1-s)(1-εp) , a p = 1 -

( 1 -

 1 s) [(1 -s)(1 -ε p ) + sε p ], we have a p , b p , c p < 0 and therefore, cp ap > 0 and -bp

Note that monopsony power also arises in presence of frictions on the labor markets. This is another way to consider upward-sloping labor supply.

The significance of firms' market power in the product markets at the aggregate level also received recent supports by empirical studies (see for instance De Loecker and Eeckhout[START_REF] De Loecker | The rise of Market Power and the Macroeconomic Implications[END_REF]).

Both markup and markdown have a similar effect on the real wage paid to the workers which is lower than the marginal product of labor and is decreasing with firms' market power.

The assumption of a continuum of labor market is a mere simplification. It is easily shown that our results do not depend on a discrete number of labor markets. As a result, under the present formulation, labor markets can be seen as local geographical markets but could be also seen as sectoral labor markets if a discrete formulation is introduced.

From now on, it is assumed that n(t) evolves continuously.

In Appendix(5.3), we obtain the elasticities of l(t) and n(t) with respect to k(t) and y(t), ε l,k ,ε l,y , ,ε n,k and εn,y

see Beaudry, Galizia and Portier[START_REF] Beaudry | Putting back the Cycle in Business Cycles Analysis[END_REF] for a recent investigation about the empirical relevance of cyclical fluctuations.

The following countries are considered: Belgium, Denmark, Finland, Great Britain, Germany, Ireland, Italy, Japan, Korea, Netherland, Spain, Sweden, US over the period1971-2007.

Proof of Proposition 5

From the previous Proposition and the Trace, we derive that a necessary condition for local indeterminacy is P (ε w ) > 0 and it requires σ > σ. In such case, we find that a p > 0 while b p , c p < 0 and one of the roots is positive while the other is negative. Since P (ε w ) is convex, there exists therefore a critical point ε w > 0 such that we get P (ε w ) < 0 for any ε w ∈ (0, ε w ) and the Determinant is negative while P (ε w ) > 0 for any ε w ∈ (ε w , +∞) which leads to a positive Determinant.

Note that for any ε p = 0, the Trace is positive and equal to ρ. We assumre therefore ε p > 0. The Trace writes:

with

Similarly to P (ε w ), the polynomial H(ε w ) has one positive root, say εw and one negative and non relevant root, and is negative for any ε w ∈ (0, εw ) and positive other.

Hence, without loss of generality, for any ε w ∈ (ε w , εw ), the Trace is negative and the steady state is locally indeterminate (i.e. a sink) while the Trace is positive and the NSS is a source for any ε w > εw . Furthermore, the critical point εw is a Hopf bifurcation and in its neighboorhood, the NSS displays a limit cycle.