Daniel Le Berre
email: leberre@cril.univ-artois.fr

Pierre Marquis
email: marquis@cril.univ-artois.fr

Meltem Öztürk
email: ozturk@cril.univ-artois.fr

Aggregating Interval Orders by Propositional Optimization

Keywords: Interval orders, preference modelling and aggregation, propositional reasoning, Boolean optimization

Aggregating preferences for finding a consensus between several agents is an important issue in many fields, like economics, decision theory and artificial intelligence. In this paper we focus on the problem of aggregating interval orders which are special preference structures allowing the introduction of tresholds for the indifference relation. We propose to solve this problem by first translating it into a propositional optimization problem, namely the Binate Covering Problem, then to solve the latter using a MAX-SAT solver. We discuss some properties of the proposed encoding and provide some hints about its practicability using preliminary experimental results.

Introduction

Aggregating preferences for finding a consensus between several agents is an important issue in many fields, like economics, decision theory, and artificial intelligence. Given the preferences of a set of agents (or voters) over a set of alternatives (or candidates), where preferences are generally formulated as binary relations such as strict preference, indifference, etc., preference aggregation aims at determining a collective preference relation representing as much as possible the individual preferences.

However many works have shown through paradoxes and impossibility theorems that preference aggregation is not an easy task, the famous ones are Condorcet's paradox [START_REF] De | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF], Arrow's theorem [START_REF] Arrow | Social choice and individual values[END_REF] .

A common approach is to consider a preference relation as a complete preorder (i.e., a reflexive and transitive relation). In the above results each voter is supposed to present a complete preoder over the set of alternatives. However, such a model for preferences does not prove adequate to all situations, and other models (generalizing the complete preorder one) have been pointed out. In particular, different structures have been introduced for defining thresholds as in the famous example given by Luce [START_REF] Luce | Semi-orders and a theory of utility discrimination[END_REF] about a cup of coffee. Indeed, in contrast to the strict preference relation, the indifference relation induced by such structures is not necessarily transitive. Semiorders may form the simplest class of such structures and they appear as a special case of interval orders. The axiomatic analysis of what we call now interval orders has been given by Wiener [START_REF] Wiener | A contribution to the theory of relative position[END_REF], then the term "semiorders" has been introduced by Luce [START_REF] Luce | Semi-orders and a theory of utility discrimination[END_REF] and many results about their representations are available in the literature (for more details see [START_REF] Fishburn | Interval Orders and Interval Graphs[END_REF][START_REF] Pirlot | Semi Orders[END_REF]). Roughly speaking, within an interval order, alternative x 1 is strictly preferred to alternative x 2 if and only if the evaluation of x 1 is greater than the evaluation of x 2 plus a threshold. It is easy to see that preorders are special cases of interval orders where the value of threshold is fixed to zero.

In this paper we consider the interval order aggregation problem; to solve it, we propose a method based on the Kemeny distance which makes use of a translation into the Binate Covering Problem [START_REF] Coudert | On solving covering problems[END_REF]. More precisely, we consider the case where the preferences of voters are interval orders and we try to find a final interval order which will be "as close as possible" to the set of voter's preferences. Let us note that having an interval order as a result of an aggregation is not a drawback for pointing out an undominated alternative since it is known that when the asymmetric part of a binary relation is transitive, which is the case of interval orders, there is always at least one such undominated alternative [START_REF] Sen | Collective Choice and Social Welfare[END_REF]. Moreover it is natural to ask an interval order as a result when preferences of voters are interval orders. Finally, as we will show it, even when the input preferences are preorders, focusing on interval orders as outputs is a way to get an aggregation which is closer to the given preferences than when preorders are targeted (just because the set of all interval orders over the! alternatives is a superset of the set of all preorders over the alternatives).

Aggregation as Optimisation

In this paper, we consider a finite set of alternatives A on which preference relations are applied (|A| = n), we represent with a, b, c, ... specific elements of A and x 1 , x 2 , ... or x, y, z, . . . variables ranging over the set A. We have a finite set of voters V = {v 1 , . . . , v m } (|V | = m). Voters express their preferences by the help of two binary relations represented in an explicit way as n 2 -matrices: the notation aP i b (resp. aI i b) means that the voter v i prefers strictly alternative a to b (resp. is indifferent between a and b). #p(a, b) (resp. #i(a, b)) is the number of voters v i for whom aP i b (resp. aI i b) holds. We call a profile, the set of voter's preference relations and denote it by X = { P 1 , I 1 , P 2 , I 2 , . . . , P m , I m }; its size is in O(m.n 2 ).

The result of the agregation is also expressed by two relations that we denote by P and I (P -1 represents the inverse of P : ∀x, y ∈ A, xP -1 y iff yP x). aP b (resp. aIb) means that alternative a is preferred to alternative b (resp. a and b are indifferent) in the resulting order. We denote it as f ( P 1 , I 1 , P 2 , I 2 , . . . , P m , I m ) = P, I .

The pair P, I is called a preference structure if and only if P is asymmetric, I is reflexive and symmetric, P ∪ I is complete and P ∩ I is empty. Such a pair is an interval order if and only if it is a preference structure and satisfies a property called Ferrers relation. 1 Definition 1. Let P and I be binary relations on A × A, P, I is an interval order if and only if i) P ∪ I ∪ P -1 = A × A (completeness) , ii) P ∩ I = (exclusivity), iii) P is asymmetric, I is symmetric and reflexive, iv) P.I.P ⊂ P (Ferrers relation).

The numerical representation of interval orders is as in the following: Proposition 1. [START_REF] Fishburn | Interval Orders and Interval Graphs[END_REF] Let P and I be binary relations on A × A, P, I is an interval order if and only if there exist a mapping g from A to IR and a mapping q from IR to IR + such that for any x, y ∈ A, we have:

xP y ⇔ g(x) > g(y) + q(g(y)). xIy ⇔ g(x) ≤ g(y) + q(g(y)).

Interval orders are quasi-orders (i.e., orders with a transitive asymmetric part). Gibbard ( [START_REF] Gibbard | Social choice and the arrow conditions[END_REF]) has showed that Arrow's theorem can be generalized to the case of quasiorders, hence we have this impossibility result for interval orders. Pirlot and Vincke ( [START_REF] Pirlot | Semi Orders[END_REF]) have focused also on this theorem with a special attention to interval orders. Before presenting this theorem we first need the following definitions in order to state it formally:

weak unanimity an aggregation procedure satisfies the weak unanimity condition if and only if, for all voters v i ∈ V and for all a, b ∈ A, aP i b =⇒ aP b; non-dictatorship an aggregation procedure satisfies the non-dictatorship condition if and only if, for no voter v i ∈ V such that for all possible preferences of other voters and for all alternatives a and b aP i b =⇒ aP b; independence of irrelevant alternatives an aggregation procedure satisfies the independence of irrelevant alternatives condition if and only if ∀( P 1 , I 1 , . . . , P m , I m ), ( P 1 , I 1 , . . . , P m , I m ), ∀a, b ∈ A, ( P 1 , I 1 , . . . , P m , I m )/{a, b} = ( P 1 , I 1 , . . . , P m , I m )/{a, b} =⇒ ( P, I ), /{a, b} = ( P , I )/{a, b} where P, I is the result on ( P 1 , I 1 , . . . , P m , I m ) , and P, I /{a, b} is the restriction of P, I to {a, b}, etc.

Theorem 1 (Generalized Arrow's Theorem). [START_REF] Pirlot | Semi Orders[END_REF] If |A| ≥ 4, if X is the set of all n-tuples of interval orders on A and if Y is the set of all interval orders on A, then there is no (X-Y )-aggregation procedure2 satisfying simultaneously weak unanimity, non-dictatorship and independence conditions.

Note that if all the considered relations are complete preorders, Theorem 1 is exactly Arrow's theorem with |A| ≥ 3. We need four alternatives for interval orders because of the definition of Ferrers relation.

There exist a number of papers addressing the aggregation issue for binary relations as an optimization problem. Typically, a 0/1 linear program is targeted. Contrastingly, in our approach, we associate to each profile of binary relations an instance of BCP, the so-called Binate Covering Problem [START_REF] Coudert | On solving covering problems[END_REF], where the set of constraints is not any set of 0/1 linear inequations but a SAT instance. This problem has been studied for decades by the circuit community where it is important for logic synthesis (minimizing the number of components needed to perform a given operation).

From a theoretical standpoint, like 0/1 linear programming, BCP is an NP-hard optimization problem (and the associated decision problem is in NP) (see e.g. [START_REF] Papadimitriou | Combinatorial Optimization: algorithms and complexity[END_REF]). In practice, each clause can be translated into an equivalent 0/1 linear inequation, but the converse does not hold. The specific format of the constraints considered in BCP (compared to 0/1 linear programs) enables us to take advantage of the power of existing MAX-SAT solvers in order to solve its instances in a more efficient way from the practical side.

To our knowledge there is a limited number of studies related to the aggregation of interval orders. Pirlot and Vincke [START_REF] Pirlot | Semi Orders[END_REF] have shown that the schemes that work well for complete preorders such as lexicographic procedure or Borda's sum of ranks do not lean themselves easily to the generalization with interval orders. They proposed two types of aggregation procedures: one consisting in aggregating numerical representations into a "global evaluation" function, and the other inspired from pairwise comparison methods.

In this paper we propose a hybrid approach consisting in finding an interval order being optimal in the sense of minimal Kemeny distance [START_REF] Kemeny | Mathematics without numbers[END_REF] to the input profile. Intuitively, ranking the alternatives according to Kemeny's rule can be seen as the best compromise since on average it gives the "closest" social preference to the individual preferences. Our idea can be summarized as in the following:

1. Determine all pairwise comparisons for which all the voters have the same opinion and build a partial order that preserves those comparisons. 2. Search within the set of feasible interval orders in order to find a closest one to the input profile.

The first step can be easily achieved the following way:

∀v i ∈ V, ∀x, y ∈ A, xP i y, =⇒ xP y, ∀v i ∈ V, ∀x, y ∈ A, xI i y, =⇒ xIy.
The resulting P, I is a partial order.

From partial order to interval orders Naturally this step provides in the majority of cases many interval orders. The worst case that we may expect is when the partial order provided in the first step is empty. In this case we have to find all the interval orders containing n objects (n being the cardinality of A). This case gives an idea on the number of interval orders that we may have. Stanley [START_REF] Stanley | Hyperplanes arrangements, interval orders and trees[END_REF] has precised the number of interval orders with n elements; for this he has made use of relations between interval orders and hyperplanes arrangement. The coefficient of the following polynomial provides the number of interval orders:

z = k≥0 c k x k k! z = 1 + x + 3 x 2 2! + 19 x 3 3! + 195 x 4 4! + 2831 x 5 5! + 53703 x 6 6! + 1264467 x 7 7! + . . .
z is the unique power series satisfying z z = y 2 , z(0) = 1 where 1 = y(2 -e xy ). The value c k of the serie z is the number of interval orders on k alternatives. This number grows exponentially on the number of alternatives: for instance, with just 7 alternatives we have more than one million interval orders. However, we will see in the following that we do not need to represent those interval orders explicitly. We denote by P (1) , I (1) , P (2) , I (2) , . . . these interval orders.

Discriminating interval orders In our approach, the distance of an interval order P (i) , I (i) to the input profile X, D( P (i) , I (i) , X), will be calculated as the sum of its distance to each voter's order P j , I j . Let us denote this distance by d( P (i) , I (i) , P j , I j ):

D( P (i) , I (i) , X) = Pj ,Ij ∈X d( P (i) , I (i) , P j , I j )
The distance d is computed using the difference between pairwise comparisons in the following way:

d( P (i) , I (i) , P j , I j ) = (x,y)∈A 2 δ P (i) ,I (i) , Pj,Ij (x, y) δ ( P (i) ,I (i) , Pj ,Ij ) (x, y) =    p2p if (xP (i)
y and yP j x) or (yP (i) x and xP j y) 0 if (xP (i) y and xP j y) or (xI (i) y and xI j y) p2i otherwise Here p2p and p2i are nonnegative constant numbers. The rationale for this definition of d is to put a penalty when there is a discrepancy of preference relation between the comparison given by a voter and the one of the interval order. Naturally, a discrepancy of a strict preference (for instance xP y) to the inverse of this preference (yP x) is at least as problematic as a discrepancy of a strict preference (for instance xP y) to an indifference (xIy) for this reason we suggest that p2p ≥ p2i. Even more one can impose the strict inequality (p2p > p2i) which will guarantee to have as a result aIb when the profile with three voters is aP 1 b, aI 2 b and bP 3 a. Note that the distance used by Hudry ( [START_REF] Hudry | Np-hardness results for the aggregation of linear orders into median orders[END_REF]) imposes p2p = p2i = 1 and provides as a result three interval orders (aP b, bP a and aIb) for this example.

We propose to represent the set of interval orders to be implicitly considered in the second step using propositional constraints (clauses). Then, computing the interval orders closest to the profile is encoded as minimizing an objective function. Accordingly, we reduce our interval order optimization problem to the BCP one.

Translation into the Binate Covering Problem

We first need propositional variables v xP y and v xIy to represent all pairs of the form xP y (∀x = y ∈ A) and xIy (∀x, y ∈ A, x ≤ y). As a consequence, n 2 -n+ n×(n-1)

2 + n = 3×n 2 -n 2
variables must be considered. For instance, for 4 alternatives, we need 22 propositional variables. For 16 alternatives, we need 376 propositional variables.

Implicit representation of interval orders

Structural constraints

The following constraints express that the result of the aggregation must be an interval order. They do not depend on the voters.

-P ∪ I is complete: ∀x < y ∈ A v xP y ∨ v xIy ∨ v yP x , -P is asymmetric: ∀x < y ∈ A, ¬(v xP y ∧ v yP x ) ≡ ¬v
∈ A, v xIx is forced to be true, -P ∪ I is Ferrers: ∀x, y, z, t ∈ A, x = y, z = t, x = t, y = t, x = z (v xP y ∧ v yIz ∧ v zP t ) ⇒ v xP t ,
Note that we need to generate 2n(n -1) + n + n(n -1)(n -2) 2 = n(n 3 -5n 2 + 10n -5) structural constraints plus the unit clauses needed to preserve unanimity (see below). For 4 alternatives, it means at least 76 constraints. For 16 alternatives, it means at least 47536 constraints. The O(n 4 ) space required by the above encoding is clearly dominated by the cost of ensuring Ferrers condition.

Unanimity constraints Those additional constraints encode unanimity for both P and I. They are generated according to the votes. Since they force the truth value of some variables, they simplify in practice the computation of the best interval order.

-Unanimity for P : ∀x = y ∈ A, if #p(x, y) = |V | then xP y is forced to be true, -Unanimity for I: ∀x = y ∈ A, if #i(x, y) = |V | then xIy is forced to be true.

Distance between interval orders and the profile

The coefficient associated to each variable is computed according the individual penalty δ defined earlier and the number of voters that disagree with the interval order.

-∀x, y ∈ A, satisfying I(x, y) entails that voters that strictly prefer x to y or y to x disagree with that fact, with a simple individual penalty of p2i. As a consequence, the coefficient of the variables is exactly p2i(#p(x, y) + #p(y, x)), -∀x, y ∈ A, satisfying P (x, y) entails that voters that are indifferent between x and y disagree with that fact with a simple penalty of p2i, while the voters that strictly prefer y to x disagree with that fact with an individual penalty of p2p. So the coefficient of those variables is exactly p2i#i(x, y) + p2p * #p(y, x).

The objective function of the binate covering problem associated with X is denoted by score X ( P, I ) and is

x≤y∈A p2i(#p(x, y) + #p(y, x))v xIy + x =y∈A (p2i#i(x, y) + p2p * #p(y, x))v xP y .
Thus the space needed to represent the objective function is in O(n 2 .log 2 (m)). Interestingly, the space needed by the encoding (constraints and objective function) is only logarithmic in the number of voters. This renders the approach feasible for a large number of voters. On the other hand, the space needed by the encoding is in O(n 4 ); considering that MAX-SAT solvers are currently able to solve some instances with millions of variables, it might be possible to solve aggregation problems up to roughly 40 alternatives (which leads to 2 millions of clauses using the above encoding).

The result of the aggregation step is any interval order which minimizes the value of the objective function. An important issue is to determine whether it makes sense to use of sophisticated SAT engine (or 0/1 linear program solver) to solve those specific BCP instances stemming from a translation from instances of the aggregation problem. [START_REF] Hudry | Np-hardness results for the aggregation of linear orders into median orders[END_REF] gave a positive answer to this query, by identifying the complexity of the following decision problem: SCORE: Input: A finite profile X of binary relations P, I on A and a nonnegative integer k. Question: Does there exist an interval order P, I on A such that score X ( P, I ) ≤ k?

In a nutshell Hudry showed that SCORE is NP-complete as soon as the number of voters m is "sufficiently" large compared to the number n of alternatives, even in the restricted case when X consists of linear orders only, provided that p2p = p2i = 1. This justifies to take advantage of algorithms running in exponential time (as MAX-SAT solvers) in the worst case, since polynomial time ones are hardly expected.

Hudry's NP-hardness result extends easily to our framework when the parameters p2p and p2i are such that p2p = p2i since linear orders are interval orders; on the other hand, the membership to NP of the SCORE probllem is obvious in our setting: in order to determine that an instance of this decision problem is positive, it is enough to guess a binary relation P, I on A (its size is O(n 2 )), then to check that it is an interval order (this can be easily achieved in polynomial time in the size of the relation), and finally to compute in polynomial time score X ( P, I ) in order to compare it with k.

Our MAX-SAT algorithm for the BCP problem is a branch-and-bound algorithm. During the search, each time a (partial) assignment is found that satisfies all the constraints, the corresponding score is computed (each unassigned variable is set to 0) and a constraint which eliminates all the assignments leading to a greater bound is added, so that whenever a partial assignment leads to a score which is worse than this bound, a backtrack occurs. Its worst-case time complexity is simply exponential in the number of variables under consideration (hence linear in the size of X) and its space complexity is linear in the size of the constraints (hence quadratic in the size of X).

Examples

As a matter of illustration, let us consider the following examples. For these examples we suppose that p2i = 1 and p2p = 2.

Example 1. Consider first a case with 5 voters and 4 alternatives with the preferences of voters shown in Table 1. These preferences of voters can be compactly represented in a matrix where ∀x i , x j , P (x i , x j ) = α means that there are α voters who prefer alternative x i to alternative Table 1. Pairwise comparisons on 4 alternatives given by 5 voters

x j . Table 2 represents the matrix related to the previous example. Accordingly, this matrix contains all the information needed for running our aggregation procedure. Our method find as a result the following interval order: aP b, cP a, dP a, cP b, dP b, cP d (its distance to the profile is 12). Example 2. Here is a second example; Table 3 shows the pairwise comparisons given by three voters on three alternatives (a, b, c). The result of our aggregation procedure provides a unique interval order as close as possible to the input profile. It is not a preorder (a is preferred to b and all the other comparisons are indifference), despite the fact that each preference relation in the input profile is a preorder.

More than one solution is often the case

Clearly enough, there is no guarantee in general that a unique interval order P, I exists, leading to a minimal value s * for the objective function score X ( P, I ). This problem is inherent to the fact that voters may have different preferences, and it may happen in very simple scenarios, for instance when A consists of two alternatives a and b and X consists of two interval orders P 1 , I 1 and P 2 , I 2 on A so that aP 1 b and aI 2 b: in such a case, both P 1 , I 1 and P 2 , I 2 lead to the minimal value s * = p2i, but not to the same sets of undominated alternatives. Nevertheless, this plurality is problematic since decisions made using only one of such optimal interval orders are not necessarily robust, in the sense that the choice of another optimal interval order could question them. Typically decisions are made by comparing alternatives or determining undominated ones. While robustness is a complex notion, a sufficient condition for a comparison to be robust is when it holds for every optimal interval order, and similarly an alternative is robustly undominated when it is undominated for all optimal interval orders. Formally, the following decision problems have to be considered: NEC-COMP(R):

Input: A finite profile X of binary relations P, I on A and alternatives a, b from A.

Question: Is it the case that every interval order P, I on A satisfying score X ( P, I ) = s * is such that aRb? (where R = P or R = I)?

NEC-UNDOM:

Input: A finite profile X of binary relations P, I on A and an alternative a from A. Question: Is it the case that for every interval order P, I on A such that score X ( P, I ) = s * , we have a(P ∪ I)b for every b ∈ A?

Those decision problems are "mildly" hard, since they belong to the complexity class Θ p 2 , consisting of all decision problems which can be solved in deterministic polynomial time using logarithmically many calls to an NP oracle. In order to prove the membership of NEC-COMP(R) and NEC-UNDOM to Θ p 2 , we consider the complementary problems and show them in Θ p 2 as well (this class is closed under complementation). We have already seen that SCORE is in NP. Now, the value of s * can be computed by binary searching it within the bounds 0 and m.n 2 .max(p2p, p2i) which is a (rough) upper bound of s * , and has a value linear in the size of X since max(p2p, p2i) is a constant. Hence, s * can be computed in deterministic polynomial time using logarithmically many calls to an NP oracle (used to solve the SCORE instances encountered during the search, associated to the successive values of k) . Once this is done, it remains to guess a binary relation P, I on A using a last call to the NP oracle, check that it is an interval order such that score X ( P, I ) = s * , and finally check that a Rb (resp. that there exists a b ∈ A such that bP a). We conjecture that NEC-COMP(R) and NEC-UNDOM are Θ p 2 -complete. Noticeably, when s * is part of the input, the complexity of NEC-COMP(R) and NEC-UNDOM falls down to coNP. From the practical side, when several instances of NEC-COMP(R) or NEC-UNDOM sharing the same profile X are to be solved, it can prove useful to compute s * once for all during a pre-processing phase, then to exploit it in order to solve those instances in a more efficient way.

Some Theoretical Results

We analyze here some expected properties for aggregation procedures such as respect of unanimity, independance, majority, etc., and our objective is to determine whether or not our approach satisfies some of them. We begin by the properties at work in Arrow's theorem:

Universality An aggregation procedure is universal if it accepts all configurations for the input profile. Since the input of our procedure can be any finite set of interval orders, we can conclude that our procedure is universal. Transitivity Arrow's theorem imposes the transitivity of the preference and the indifference relation. Our procedure provides an interval order which has a transitive preference relation P but the indifference relation I is not necessarily transitive. However as we mentioned in the introduction, in order to find an undominated alternative, transitivity of P is enough. Weak-unanimity Our procedure satisfies the weak unanimity condition since unanimity is imposed by our formulation as a hard constraint to be respected. Non-dictatorship Our procedure obviously satisfies the non-dictatorship condition. Independence Our procedure does not satisfy the condition of independence of irrelevant alternatives: let us show it on a new example. The set of alternatives is A = {a, b, c, d} and we have two different profiles X and X which have the same votes on the subset A = {c, d} of A:

Example 3. Table 3 shows the compact matrix of each profile. Our procedure con-

X a b c d a 0 0 0 1 b 0 0 6 2 c 4 0 0 6 d 8 6 4 0 X a b c d a 0 3 0 0 b 3 0 0 3 c 8 1 0 6 d 2 2 4 0
Table 4. The compact matrix of profile X and X 4 cludes that for the profile X there are two optimum solutions, in the first one c is indifferent to d and in the second one d is preferred to c. However, even if the profile X has the same votes for the comparison between c and d, our procedure concludes for X that c is preferred to d.

We consider now some other properties that an aggregation procedure should preferably satisfy.

Anonymity

The result of the aggregation depends only on the preferences of voters (and for instance, not on the age, sex or seniority of candidates). Let P be the set of permutations of A, π one element of P. We denote by π(R), the binary relation such as π(a)π(R)π(b) ⇐⇒ aRb. An aggregation procedure is anonymous if and

only if ∀π ∈ P,f (R 1 , R 2 , . . . , R m ) = π(f (π(R 1 ), π(R 2 ), . . . , π(R m ))).
It is easy to see that our procedure is anonymous. Loyalty If there is just one voter the procedure must provide as a result the same preference as her: m = 1 =⇒ f (R 1 ) = {a ∈ A : aR 1 b, ∀b ∈ A}. Again, it is easy to check that our procedure satisfies the loyalty condition

Majority condition

If there is a majority of voters who prefers a to b then the result of the aggregation procedure must agree with this comparison: f satisfies the majority condition if and only if

∀(R 1 , R 2 , . . . , R m ) ∈ X, ∀a, b ∈ A #p(a, b) > #p(b, a) =⇒ aP b, #p(a, b) = #p(b, a) =⇒ aIb.
Our aggregation procedure does not satisfy the majority condition as the following example shows it.

Example 4. Table 5 gives the number of votes for pairwise comparisons between four alternatives given by 11 voters Even if the majority of voters prefer c to a, the result of our procedure concludes that a is preferred to c (the output is the interval order such that aP b, aP c, aId, aIa, bP c, bId, bIb, cId, cIc, dId and its distance to the profile is 39).

Conclusion

In this paper, we have presented an optimization-based approach to interval orders aggregation. In this approach, to every profile of interval orders, one associates an instance of a propositional optimization problem (namely the Binate Covering Problem); solving the latter gives in a straightforward way an interval order (the "closest" to the input profile in some sense), which is considered as the aggregation looked for. Among other things, we have computed an upper bound of the size of the BCP instance associated to every profile (showing that it is only logarithmic in the number of voters), identified some properties satisfied (or not) by the aggregation approach. An interesting feature of such an optimization-based approach to aggregation is that it can be easily tuned to fit with other preference structures (e.g. preorders, semiorders, etc.). Indeed, it is enough to point out the corresponding hard constraints. Investigating in more depth such extensions is a perspective for further research. The Binate Covering Problem can be seen as a very specific case of an Integer Linear Program in which case efficient ILP frameworks exist (e.g. CPLEX). However, it looks that tools dedicated to Boolean reasoning are better suited to solve such problems: Weighted Partial MAX SAT [START_REF] Argelich | The first and second max-sat evaluations[END_REF] and Pseudo Boolean Optimization [START_REF] Manquinho | The first evaluation of pseudo-boolean solvers (pb'05)[END_REF] engines are currently receiving a lot of attention since international evaluations are organized regularly and many systems are freely available for the research community.

We designed a proof of concept tool based on the SAT4J library [START_REF] Le | SAT4J, a SATisfiability library for java[END_REF], a library of Boolean search engines dedicated to solving SAT, MAX SAT and Pseudo Boolean problems. That tool can be downloaded from http://sat4j.ow2.org/.

In order to have an idea of the applicability of our approach on a real scenario, we used the publicly available results of the SAT RACE 2006 3 . It is a competitive event between 16 SAT solvers on a set of 100 benchmarks. Here each benchmark is a voter and each solver is an alternative. A given benchmark b prefers the SAT solver x to the SAT solver y iff x solved b faster than y. A given benchmark b is indifferent between the SAT solvers x and y iff none of x and y solved b or both of them solved b but with a roughly the same CPU time (the difference is less than 1 second). By definition, each vote is an interval order. Computing the aggregation of such votes means solving a binate covering problem with 376 variables and 47536 clauses. Our aggregator takes less than one second to generate the BCP from the compact matrix. SAT4J takes one second to find a solution, but fails to prove it is optimal even after running for several hours.

We plan to test several MAXSAT and Pseudo Boolean engines on aggregation of real interval orders instances (including LP based ones).

  xP y ∨ ¬v yP x , -P and I are exclusive: ∀x = y ∈ A, ¬(v xP y ∧ v xIy ) ≡ ¬v xP y ∨ ¬v xIy , -I is symmetric by construction because a single propositional variable v xIy represents both xIy and yIx. -I is reflexive: ∀x

- 1 P

 1 -1 P -1 I

Table 3 .

 3 The profile of Example 2

Table 2 .

 2 The number of voters agreeing for a strict preference

Table 5 .

 5 The number of voters agreeing for a strict preference

∀x, y, z, t ∈ A, xP y ∧ yIz ∧ zP t ⇒ xP t.

X represents here the set of voter's preferences and Y the resulting order.

http://fmv.jku.at/sat-race-2006/

This work has been supported in part by two Projects: ANR-05-BLAN-0384 and PEPS-09 37. This support is gratefully acknowledged by the autors. The authors also thank anonymous referees for their helpful comments and suggestions.


MD Masatake Kobayashi

MD Nicolas Girerd

João Pedro Ferreira

PhD Duarte Kevin

MD Olivier Huttin

PhD Arantxa González

PhD Erwan Bozec

MD Andrew L Clark

MD Franco Cosmi

MD Joe Cuthbert

MD Javier Diez

MD Mark Hazebroek

MD Stephane Heymans

Beatrice Mariottoni Bsc

MD Pierpaolo Pellicori

MD Johannes Petutschnigg

MD Burkert Pieske

MD Jan A Staessen

MD Job A J Verdonschot

MD Patrick Rossignol

MD John G F Cleland

MD Faiez Zannad
email: f.zannad@chru-nancy.fr

The association between markers of type I collagen synthesis and echocardiographic response to spironolactone in patients at risk of heart failure: findings from the HOMAGE trial

Keywords: collagen markers, myocardial fibrosis, spironolactone, diastolic function, cardiac structural remodeling, heart failure

Background

Procollagen type I C-terminal propeptide (PICP) and procollagen type III N-terminal propeptide (PIIINP) are markers reflecting collagen synthesis in cardiac fibrosis. However, they may be influenced by the presence of noncardiac comorbidities (e.g., ageing, obesity, renal impairment).

Understanding the associations between markers of collagen synthesis and abnormalities of cardiac structure and function is important to screen for myocardial fibrosis and monitor the antifibrotic effect of medications.

Methods

The HOMAGE (Heart OMics in Aging) trial showed that spironolactone decreased serum PICP concentrations and improved cardiac remodeling over 9 months in a population at risk of developing heart failure (HF). We evaluated the associations between echocardiographic variables, PICP, PIIINP and galectin-3 at baseline and during the course of the trial.

Results

Among 527 individuals (74±7years, 26% women), median serum concentrations of PICP, PIIINP and galectin-3 were 80.6µg/L (65.1-97.0), 3.9µg/L (3.1-5.0) and 16.1µg/L (13.5-19.7), respectively.

After adjustment for potential confounders, higher serum PICP was significantly associated with left ventricular hypertrophy, left atrial enlargement, and greater ventricular stiffness (all p-values<0.05), whereas serum PIIINP and galectin-3 were not (all p-values>0.05). In patients treated with spironolactone, a reduction in serum PICP during the trial was associated with a decrease in E/e′ (adjusted-beta [95% CI] =0.93 [0.14-1.73]; p=0.022).

Conclusions

In individuals at high risk of developing HF, serum PICP was associated with cardiac structural and functional abnormalities, and a decrease in PICP with spironolactone was correlated with improved diastolic dysfunction as assessed by E/e′. In contrast, no such associations were present for serum PIIINP and galectin-3.

Introduction

Myocardial fibrosis is often accompanied by increased left ventricular (LV) stiffness, hypertrophy, and diastolic functional abnormalities, all of which may contribute to the development of heart failure (HF) [START_REF] Kobayashi | Machine Learning-Derived Echocardiographic Phenotypes Predict Heart Failure Incidence in Asymptomatic Individuals[END_REF][START_REF] Shah | Contemporary Assessment of Left Ventricular Diastolic Function in Older Adults: The Atherosclerosis Risk in Communities Study[END_REF] . Serum concentrations of procollagen type I C-terminal propeptide (PICP) and procollagen type III N-terminal propeptide (PIIINP) are surrogate markers of systemic and, potentially, myocardial fibrosis generated during the extracellular conversion of procollagen to mature fibril-forming collagen type I and III, respectively [START_REF] López | Circulating Biomarkers of Myocardial Fibrosis: The Need for a Reappraisal[END_REF] . In addition, serum concentration of galectin-3, a mediator of aldosterone-induced cardiac fibrosis [START_REF] Calvier | The impact of galectin-3 inhibition on aldosterone-induced cardiac and renal injuries[END_REF] , correlates with serum markers associated with extracellular matrix turnover [START_REF] Lopez-Andrès | Association of galectin-3 and fibrosis markers with long-term cardiovascular outcomes in patients with heart failure, left ventricular dysfunction, and dyssynchrony: insights from the CARE-HF (Cardiac Resynchronization in Heart Failure) trial[END_REF] .

Whether these markers specifically reflect alterations in cardiac structure and function remains insufficiently established [START_REF] Cleland | A novel treatment for heart failure targets myocardial fibrosis[END_REF] . This is clinically important, as "cardiac-specific" markers could be useful for screening cardiac fibrosis and identifying populations at high risk of developing HF [START_REF] López | Circulating biomarkers of collagen metabolism in cardiac diseases[END_REF] .

Markers of collagen synthesis are commonly used to quantify the severity of myocardial fibrosis in various settings [START_REF] Eschalier | Features of cardiac remodeling, associated with blood pressure and fibrosis biomarkers, are frequent in subjects with abdominal obesity[END_REF][START_REF] López | Diffuse myocardial fibrosis: mechanisms, diagnosis and therapeutic approaches[END_REF] , and predict therapeutic response to cardiac remodeling and cardiovascular events in HF with a preserved ejection fraction (HFpEF) [START_REF] Zile | Plasma Biomarkers Reflecting Profibrotic Processes in Heart Failure With a Preserved Ejection Fraction: Data From the Prospective Comparison of ARNI With ARB on Management of Heart Failure With Preserved Ejection Fraction Study[END_REF][START_REF] Cunningham | Effect of Sacubitril/Valsartan on Biomarkers of Extracellular Matrix Regulation in Patients With HFpEF[END_REF] . Several non-cardiac comorbidities promote fibrosis [START_REF] Rockey | Fibrosis--a common pathway to organ injury and failure[END_REF][START_REF] Weiskirchen | Organ and tissue fibrosis: Molecular signals, cellular mechanisms and translational implications[END_REF] , and thus serum PICP and PIIINP may be potentially influenced by ongoing collagen deposition in many extra-cardiac tissues (e.g., skin, lung, liver, kidney, heart) [START_REF] López | Circulating biomarkers of collagen metabolism in cardiac diseases[END_REF][START_REF] Rockey | Fibrosis -A Common Pathway to Organ Injury and Failure[END_REF] .

In the Heart "OMics" in AGEing (HOMAGE) trial, spironolactone reduced serum PICP and improved cardiac remodeling in people with preclinical HF [START_REF] Cleland | The effect of spironolactone on cardiovascular function and markers of fibrosis in people at increased risk of developing heart failure: the heart 'OMics' in AGEing (HOMAGE) randomized clinical trial[END_REF] . In the present analysis, we (i) explore whether clinical profiles influence serum PICP, PIIINP and galectin-3, (ii) assess the associations between the collagen-related markers, abnormal echocardiographic structure and function, and (iii) assess the associations between changes in collagen-related markers and changes in echocardiographic variables as a consequence of spironolactone treatment.

Methods

Study population

The HOMAGE trial has been described previously [START_REF] Pellicori | Effects of spironolactone on serum markers of fibrosis in people at high risk of developing heart failure: rationale, design and baseline characteristics of a proof-of-concept, randomised, precision-medicine, prevention trial. The Heart OMics in AGing[END_REF]

Laboratory assays

Serum PICP was measured by enzyme immunoassay (METRA; Quidel Corporation ® ), PIIINP by radio-immunoassay (Orion Diagnostica ® ), and galectin-3 by enzyme-linked immunosorbent assay (ELISA), blinded to clinical and echocardiographic data, as previously reported [START_REF] Cleland | The effect of spironolactone on cardiovascular function and markers of fibrosis in people at increased risk of developing heart failure: the heart 'OMics' in AGEing (HOMAGE) randomized clinical trial[END_REF] .

Echocardiogram

Echocardiograms were recorded, de-identified and transferred to the Nancy University Hospital Clinical Investigation Center. LV volumes and LVEF were calculated using the biplane method of disks summation (modified Simpson's rule), while left atrial (LA) volume was assessed using the biplane area-length method from apical views. Diastolic function was assessed from the pattern of mitral inflow by pulsed-wave Doppler. Mitral annular early diastolic velocity (e′) was assessed at the septal and lateral sites of the mitral annulus using tissue Doppler imaging. E/A ratio, average e′ and average E/e′ ratio were calculated [START_REF] Nagueh | Recommendations for the Evaluation of Left Ventricular Diastolic Function by Echocardiography: An Update from the American Society of Echocardiography and the European Association of Cardiovascular Imaging[END_REF] . Tricuspid annular plane systolic excursion (TAPSE) measurement was obtained as recommended [START_REF] Rudski | Guidelines for the echocardiographic assessment of the right heart in adults: a report from the American Society of Echocardiography endorsed by the European Association of Echocardiography, a registered branch of the European Society of Cardiology, and the Canadian Society of Echocardiography[END_REF] .

Baseline measurements were carried out by a single experienced echocardiographer (E.B.), blinded to clinical data, using dedicated software (Echo PAC, GE Healthcare). Measurements were repeated at least two months later, blinded to the first measurement. All recordings with suboptimal images and/or with differences >10% were reviewed by a senior cardiologist (N.G.) to exclude measurement error. Our center's measurement reproducibility by experienced echocardiographers has been previously reported [START_REF] Frikha | Reproducibility in echocardiographic assessment of diastolic function in a population based study (the STANISLAS Cohort study)[END_REF] .

Dilated LV end-diastolic volume (LVEDV) was defined by an indexed LVEDV (LVEDVi) >74ml/m² in men or >61mL/m² in women, decreased LVEF by LVEF <52% in men or LVEF <54% in women, LV hypertrophy by indexed LV mass (LVMi) >115g/m² in men or >95g/m² in women, LA volume enlargement by indexed LA volume (LAVi) >34 mL/m², and abnormal e′ by a septal e′ <7cm/sec or lateral e′ <10cm/sec [START_REF] Nagueh | Recommendations for the Evaluation of Left Ventricular Diastolic Function by Echocardiography: An Update from the American Society of Echocardiography and the European Association of Cardiovascular Imaging[END_REF][START_REF] Lang | Recommendations for cardiac chamber quantification by echocardiography in adults: an update from the American Society of Echocardiography and the European Association of Cardiovascular Imaging[END_REF] .

Statistical analysis

Categorical variables are presented as frequencies (percentages) and continuous variables as mean ± standard deviation or median (25th and 75th percentiles) depending on distribution. Comparisons of baseline characteristics according to tertiles of collagen-related markers were analyzed using Subsequently, logistic regression analyses were performed to study the association between collagenrelated markers, and abnormalities of cardiac structure and function after adjustment for clinical confounders selected from the models above. Linear regression analyses, in addition, were used to assess the associations between changes in collagen-related markers and changes in echocardiographic variables during the follow-up period separately in patients assigned to spironolactone and placebo. The models were adjusted for clinical confounders selected as above plus baseline collagen-related markers and echocardiographic variables.

Statistical analyses were performed using R version 3.4.0 (R Development Core Team, Vienna, Austria). A two-sided p-value <0.05 was considered statistically significant.

Results

Baseline characteristics, and clinical factors associated with collagen synthesis markers

Among the 527 participants included in the study, mean age was 74±7 years, 26% were women, onethird (34 %) had a BMI ≥30kg/m², 78% had hypertension, and median NT-proBNP was 214 pg/mL (25 th and 75 th centiles 137-356 pg/mL). The mean LVEF was 62 ±7%, 29% had LV hypertrophy, 34% had LA enlargement and 87% had decreased e′.

Median serum concentrations of PICP, PIIINP and galectin-3 were 80.6 µg/L (65.1-97.0), 3.9 µg/L (3.1-5.0) and 16.1 µg/L (13.5-19.7), respectively (Supplemental Figure 1), and the correlations between them were weak (Spearman's rho<0.20) (Supplemental Table 1). The baseline characteristics of the patients divided by tertiles of serum PICP and PIIINP are shown in Table 1.

Patients with higher serum PICP were more likely to be women, were more likely to have a history of stroke or TIA, had lower eGFR, and greater LVMi and LAVi. Those with higher serum PIIINP were older, had a higher BMI and waist circumference, were more likely to have a history of hypertension, had lower eGFR and greater LVMi. In addition, those with higher serum galectin-3

were older, were more likely to have a history of hypertension and diabetes, had lower eGFR, greater LVMi, higher E/e′ ratio and higher serum concentrations of collagen type-1 C-terminal telopeptide (CITP). Supplemental Table 2.

Higher BMI and lower eGFR were associated with higher serum PICP, whereas older age and higher BMI were associated with higher serum PIIINP. Older age, a history of diabetes and lower eGFR were associated with higher serum galectin-3 (Table 2).

Associations between collagen synthesis markers and echocardiographic variables

In a multinomial logistic model for serum PICP with the lowest tertile as a reference, those in the upper tertile group were more likely to have LV hypertrophy (adjusted-OR [95%CI] =1.89 [1.08-3.32]; p=0.026), LA enlargement (adjusted-OR=2.01 [1.21-3.37]; p=0.007) and abnormal e′ (adjusted-OR =2.32 [1.12-5.06]; p=0.028). By contrast, serum PIIINP and galectin-3 were not significantly associated with echocardiographic structural or functional abnormalities (all p-value>0.05) (Table 3).

Similar associations were observed regardless of the type of LV mass and LA volume variables considered (i.e., absolute, indexed to body surface area, and height). Supplemental Table 3.

Associations between changes in collagen markers and changes in echocardiographic variables

After adjustment for clinical confounders (selected from the results of 4).

Discussion

In a population at a high risk of developing HF, we found that age and/or comorbidities (particularly obesity and lower eGFR) were associated with increasing concentrations of circulating markers of collagen synthesis; however, independent of these confounders, higher serum PICP was associated with abnormalities of diastolic function (specifically, with greater LA volume indexed for body surface area and lower e′). In contrast, serum PIIINP and galectin-3 were not associated with abnormalities in any of the measures of cardiac structure or function. In addition, in individuals treated with spironolactone, a decrease in serum PICP during follow-up paralleled a decrease in E/e′.

These findings suggest that PICP might be useful in screening individuals for abnormalities in cardiac structure and function associated with cardiac fibrotic remodeling, and that changes in PICP might be used to monitor any subsequent change in diastolic function due to the antifibrotic effect of spironolactone [START_REF] Zannad | Is Sacubitril/Valsartan Antifibrotic?[END_REF] .

In the current analysis of the HOMAGE trial including people with preclinical HF, values of PICP and PIIINP were comparable to those in patients with resistant hypertension [START_REF] Ferreira | Potential spironolactone effects on collagen metabolism biomarkers in patients with uncontrolled blood pressure[END_REF] and lower than those in patients with HFpEF [START_REF] Zile | Plasma Biomarkers Reflecting Profibrotic Processes in Heart Failure With a Preserved Ejection Fraction: Data From the Prospective Comparison of ARNI With ARB on Management of Heart Failure With Preserved Ejection Fraction Study[END_REF][START_REF] Ravassa | Biomarker-based phenotyping of myocardial fibrosis identifies patients with heart failure with preserved ejection fraction resistant to the beneficial effects of spironolactone: results from the Aldo-DHF trial[END_REF] . Higher BMI was associated with higher serum PICP and PIIINP, which is consistent with previous reports [START_REF] Eschalier | Features of cardiac remodeling, associated with blood pressure and fibrosis biomarkers, are frequent in subjects with abdominal obesity[END_REF][START_REF] Kosmala | Left ventricular function impairment in patients with normal-weight obesity: contribution of abdominal fat deposition, profibrotic state, reduced insulin sensitivity, and proinflammatory activation[END_REF] . We also observed that lower eGFR was associated with higher serum PIIINP. This finding is supported by evidence suggesting that pathophysiological mechanisms in chronic kidney disease such as hemodynamic overload, biochemical mediators (for example, angiotensin II and oxidative stress) and inflammation may alter fibroblasts and collagen synthesis as measured by serum PIIINP in the heart or in the kidney [START_REF] Zannad | Cardiorenal Syndrome Revisited[END_REF][START_REF] Romero-González | Heart failure in chronic kidney disease: the emerging role of myocardial fibrosis[END_REF][START_REF] Soylemezoglu | Urinary and serum type III collagen: markers of renal fibrosis[END_REF] .

Consistent with prior reports, we found that serum galectin-3 correlated with echocardiographic measures of diastolic function and serum CITP, a marker of collagen degradation 5, 30 . However, after adjustment for clinical confounders (i.e., old age, diabetes and renal function) as previously reported [START_REF] Aguilar | Levels and Change in Galectin-3 and Association With Cardiovascular Events: The ARIC Study[END_REF][START_REF] Ho | Galectin-3, a marker of cardiac fibrosis, predicts incident heart failure in the community[END_REF] , serum galectin-3 was no longer significantly associated with cardiac structure and function. Interestingly, an increase in serum galectin-3 was associated with a reduction in LAVi in subjects assigned to spironolactone. Galectin-3 is increased directly by aldosterone via mineralocorticoid receptor antagonism [START_REF] Martínez-Martínez | Galectin-3 blockade inhibits cardiac inflammation and fibrosis in experimental hyperaldosteronism and hypertension[END_REF] , and in the main results of the HOMAGE study, spironolactone caused a significant increase in serum galectin-3 , perhaps as a consequence of increases in aldosterone due to mineralocorticoid receptor blockade by spironolactone [START_REF] Cleland | The effect of spironolactone on cardiovascular function and markers of fibrosis in people at increased risk of developing heart failure: the heart 'OMics' in AGEing (HOMAGE) randomized clinical trial[END_REF] . Our observations might be explained by a simultaneous fall in LV filling pressures (as reflected in the LAVi) and rise in serum galectin-3, as co-variates, caused by mineralocorticoid receptor antagonism with spironolactone [START_REF] Martínez-Martínez | Galectin-3 blockade inhibits cardiac inflammation and fibrosis in experimental hyperaldosteronism and hypertension[END_REF] .

Some evidence suggests that both collagen synthesis markers, PICP and PIIINP, are associated with myocardial fibrosis confirmed by endomyocardial biopsies [START_REF] Querejeta | Increased collagen type I synthesis in patients with heart failure of hypertensive origin: relation to myocardial fibrosis[END_REF][START_REF] Querejeta | Serum carboxyterminal propeptide of procollagen type I is a marker of myocardial fibrosis in hypertensive heart disease[END_REF][START_REF] Raafs | The combination of carboxy-terminal propeptide of procollagen type I blood levels and late gadolinium enhancement at cardiac magnetic resonance provides additional prognostic information in idiopathic dilated cardiomyopathy -A multilevel assessment of myocardial fibrosis in dilated cardiomyopathy[END_REF] . However, PICP originates directly from the synthesis of collagen type I, whereas PIIINP originates from partially processed procollagen molecules on the surface of collagen type III fibers [START_REF] López | Circulating Biomarkers of Myocardial Fibrosis: The Need for a Reappraisal[END_REF] . Net release from the heart into the circulation has been reported only for PICP [START_REF] Querejeta | Increased collagen type I synthesis in patients with heart failure of hypertensive origin: relation to myocardial fibrosis[END_REF] . The myocardial collagen matrix consists primarily of type I collagen, which is composed of large-diameter fibres [START_REF] Weber | Cardiac interstitium in health and disease: the fibrillar collagen network[END_REF] . Collectively, these mechanisms may explain our observations that high serum PICP, but not PIIINP, is associated with LV hypertrophy, stiffness, and LA enlargement. Interestingly, we found that a decrease in PICP with spironolactone treatment was significantly and linearly associated with improvements in diastolic function as assessed by changes in E/e′. PICP may also play a key role in the assembly of collagen type I molecules into collagen type I fibrils [START_REF] David | Roles of the procollagen C-propeptides in health and disease[END_REF] . The reduction of serum PICP by spironolactone, therefore, may have double anti-fibrotic beneficial effects: reduced availability of mature collagen type I molecules and reduced assembly of these molecules to form collagen type I fibrils. These data support the hypothesis that serum PICP (rather than serum PIIINP and galectin-3) may be related to abnormalities of cardiac structure and function, and could be used to monitor the anti-fibrotic action of spironolactone involved in its reverse remodeling effect. In support of this possibility, falls in serum PICP with treatment are associated with reduction of fibrosis in endomyocardial biopsies both in non-HF [START_REF] López | Usefulness of serum carboxy-terminal propeptide of procollagen type I in assessment of the cardioreparative ability of antihypertensive treatment in hypertensive patients[END_REF] and HF patients [START_REF] López | Effects of loop diuretics on myocardial fibrosis and collagen type I turnover in chronic heart failure[END_REF] .

Of interest, the impact of myocardial fibrosis is determined by the quantity of collagen deposition (captured by PICP), as well as by the degree of collagen cross-linking, which increases the stiffness and resistance to degradation of collagen fibers. Indeed, previous sub-studies in patients with HFpEF from the Aldosterone Receptor Blockade in Diastolic Heart Failure (ALDO-DHF) trial [START_REF] Ravassa | Biomarker-based phenotyping of myocardial fibrosis identifies patients with heart failure with preserved ejection fraction resistant to the beneficial effects of spironolactone: results from the Aldo-DHF trial[END_REF] and from the HOMAGE trial [START_REF] Ravassa | Biomarker-based assessment of collagen cross-linking identifies patients at risk of heart failure more likely to benefit from spironolactone effects on left atrial remodelling. Insights from the HOMAGE clinical trial[END_REF] showed that baseline collagen type I cross-linking (non-invasively estimated by the ratio of CITP to matrix metalloproteinase [MMP-1]) influenced the beneficial cardioprotective effects of spironolactone, with patients with low collagen cross-linking showing the highest improvement in parameters associated with diastolic dysfunction and remodelling (e.g. E/e′ in ALDO-DHF and LAVi in HOMAGE). Therefore, we cannot discard that the associations reported in the current study between PICP and structural and functional parameters might be influenced by the degree of collagen cross-linking.

Our findings in preclinical HF were not in line with a prior report showing that spironolactone treatment reduced serum PIIINP in patients with severe HF and a reduced LVEF [START_REF] Zannad | Limitation of excessive extracellular matrix turnover may contribute to survival benefit of spironolactone therapy in patients with congestive heart failure: insights from the randomized aldactone evaluation study (RALES). Rales Investigators[END_REF] . The different etiology of HF may partly influence the relevance of collagen type I and type III [START_REF] Díez | Myocardial Interstitial Fibrosis in Nonischemic Heart Disease, Part 3/4: JACC Focus Seminar[END_REF] . Therefore, the substantial differences in population characteristics, comorbidity burden, LVEF and severity of HF are likely responsible for differences in the response to spironolactone treatment between these studies [START_REF] Pellicori | Effects of spironolactone on serum markers of fibrosis in people at high risk of developing heart failure: rationale, design and baseline characteristics of a proof-of-concept, randomised, precision-medicine, prevention trial. The Heart OMics in AGing (HOMAGE) trial[END_REF] . The present study should be regarded as hypothesis generating and larger sample sized studies should be warranted to validate the finding that PICP is more specific for myocardial fibrosis than PIIINP and galectin-3 in other clinical settings.

Our study has several limitations. This is a post-hoc analysis of the HOMAGE trial, hence has the limitations inherent in exploratory analyses. Despite different patterns observed between spironolactone treatment groups, the interaction between changes in serum PICP and changes in E/e′ with regards to spironolactone use was not significant; however, the moderate sample size of our population may limit the statistical power of such interaction test [START_REF] Aguinis | Statistical Power with Moderated Multiple Regression in Management Research[END_REF] . Of note, the interaction was significant when considering galectin-3 and LAVi, which sizably strengthen our pathophysiological perspective. There were no data regarding global longitudinal strain, which better captures subtle systolic impairments; however this echocardiographic variable requires more sophisticated equipment as well as professional skill which can limit its availability [START_REF] Pellicori | Graphical abstract PICP, procollagen type I C-terminal propeptide; PIIINP, procollagen type III N-terminal propeptide; LV, left ventricular[END_REF] .

Conclusions

In individuals at a high risk of developing HF, serum PICP was associated with abnormalities of cardiac structure and function, and a decrease in serum PICP with spironolactone treatment was associated with improvements in diastolic dysfunction as assessed by changes in E/e′. In contrast, no such associations were present for serum PIIINP and galectin-3. These findings support PICP as the marker of choice to assess cardiac fibrosis and response to spironolactone. 1.

Patients with tertile 1 of serum collagen markers as a reference.

Table 3. Associations between baseline serum PICP, PIIINP, galectin-3 and baseline echocardiographic variables in multivariable logistic regression analyses

Each model for abnormalities of echocardiographic function and structure was adjusted for clinical confounders selected in the results of Table 2.

OR, odd ratio; CI, confidence interval; Other abbreviations are presented in Table 1.

Dilated LVEDVi was defined by an LVEDVi>74ml/m² in men or >61ml/m² in women, decreased LVEF by an LVEF<52% in men or <54% in women, LV hypertrophy by a LVMi>115g/m² in men or >95g/m² in women and decreased e′ by a septal e′ <7cm/sec or lateral e′<10cm/sec.

Table 4. Associations between changes in PICP, PIIINP and galectin 3, and changes in echocardiographic variables in multivariable linear regression analyses

*PICP, PIIINP and galectin-3 were transformed using a logarithm function.

Each model was adjusted for clinical confounders selected in the results of Table 2 plus baseline collagen-related marker and baseline echocardiographic variable. CI, confidence interval; Other abbreviations are presented in Table 1.

  . Patients aged ≥65 years (amended to ≥60 years during the course of the trial) with established coronary artery disease or at least two criteria indicating cardiovascular disease (i.e. hypertension, diabetes mellitus, microalbuminuria or an abnormal electrocardiogram), and those with a plasma amino-terminal pro-B-type natriuretic peptide (NT-proBNP) of 125-1,000 pg/mL or B-type natriuretic peptide 35-280 pg/mL were included. Patients with a pre-existing diagnosis of HF, a left ventricular ejection fraction (LVEF)<45%, atrial fibrillation, an estimated glomerular filtration rate (eGFR) 17 <30 mL/min/1.73m 2 or a serum potassium >5.0 mmol/L were excluded. The trial was approved by relevant ethics committees and regulatory bodies. Participants provided written informed consent (ClinicalTrials.Gov Identifier: NCT02556450).

Table 2

 2

	), in subjects treated

p<0.001) but not in those not treated with spironolactone (p for interaction=0.005). No other significant associations between changes in collagen-related markers and changes in echocardiographic variables were observed (Table

Table 1 . Baseline characteristics of subjects according to tertiles of serum concentrations of PICP and PIIINP

 1

	Values are expressed as mean ±SD, n (%) or median (25th to 75th percentile)
	PIIINP, procollagen type-III N-terminal propeptide; PICP, procollagen type-I C-terminal propeptide; CITP,
	collagen type-1 C-terminal telopeptide; MMP-1, matrix metalloproteinase-1; BMI, body mass index; PCI,
	percutaneous coronary intervention; CBAG, coronary artery bypass graft; TIA, transient ischemic attack; COPD,
	chronic obstructive pulmonary disease; ACEi, angiotensin converting enzyme inhibitor; ARB, angiotensin
	receptor blocker; CCB, calcium channel blocker; BP, blood pressure; eGFR, estimated glomerular filtration rate;
	NT-proBNP, amino-terminal B-type natriuretic peptide; LVEDVi, left ventricular end-diastolic volume index;
	LVEF, left ventricular ejection fraction; LVMi, left ventricular mass index; LVH, left ventricular hypertrophy;
	LAVi, left atrial volume index; TAPSE, tricuspid annular plane systolic excursion.

Table 2 . Multinomial logistic model for clinical factors associated with serum concentrations of baseline PICP, PIIINP and galectin -3

 2

OR, odd ratio; CI, confidence interval; Other abbreviations are presented in Table

Table 1 . Baseline characteristics of subjects according to tertiles of serum concentrations of PICP and PIIINP

 1

		PICP T1 (<71.9µg/L) (N=172)	PICP T2 (71.9-91.2µg/L) (N=172)	PICP T3 (>91.2µg/L) (N=172)	p-value	PIIINP T1 (<3.4µg/L) (N=171)	PIIINP T2 (3.4-4.6µg/L) (N=170)	PIIINP T3 (>4.6µg/L) (N=171)	p-value
	Collagen markers
	PIIINP, µg/L	3.6 (3.0 -4.6)	3.9 (3.0 -5.0)	4.3 (3.3 -5.4)	<0.001	2.8 (2.4 -3.1)	3.9 (3.6 -4.3)	5.5 (5.0 -6.5)	<0.001
	PICP, µg/L	60.5 (53.5 -65.1)	80.6 (75.8 -84.8)	105.9 (97.1 -121.7) <0.001	77.3 (62.6 -93.1)	77.2 (64.3 -95.1)	86.4 (70.8 -104.8)	<0.001
	CITP, µg/L	3.4 (2.6 -4.2)	3.7 (2.8 -4.7)	4.3 (3.2 -5.9)	<0.001	3.2 (2.5 -4.1)	3.4 (2.8 -4.5)	4.7 (3.6 -6.2)	<0.001
	PICP/CITP ratio	17.3 (13.4 -22.6)	22.0 (17.3 -28.8)	25.4 (18.1 -34.5)	<0.001	24.0 (18.5 -30.5)	21.5 (16.7 -28.9)	18.1 (13.5 -24.0)	<0.001
	CITP/MMP-1 ratio	1.21 (0.70 -2.02)	1.26 (0.83 -1.95)	1.36 (0.88 -2.27)	0.08	1.04 (0.65 -1.85)	1.32 (0.85 -1.98)	1.53 (0.89 -2.60)	<0.001
	Galectin-3, µg/L	16.0 (13.6 -19.4)	15.6 (12.9 -19.2)	16.5 (13.9 -20.7)	0.18	15.9 (13.1 -19.5)	15.4 (13.2 -19.4)	17.0 (14.1 -21.0)	0.019
	Age, years	73 (68 -77)	72 (69 -78)	74 (69 -79)	0.38	72 (68 -78)	73 (69 -79)	74 (70 -79)	0.032
	Women, N (%)	39 (22.5 %)	36 (20.9 %)	56 (32.6 %)	0.027	53 (31.0 %)	36 (21.2 %)	41 (24.0 %)	0.10
	BMI, kg/m²	28 (25 -31)	28 (26 -32)	28 (25 -32)	0.33	27 (24 -30)	28 (26 -32)	28 (26 -32)	<0.001
	Waist circumference, cm	101 (95 -110)	101 (94 -110)	103 (95 -112)	0.68	99 (92 -107)	103 (96 -112)	104 (97 -112)	<0.001
	Smoking, N (%)	10 (5.8 %)	10 (5.8 %)	22 (12.8 %)	0.023	16 (9.4 %)	15 (8.8 %)	11 (6.4 %)	0.58
	Medical history, N (%)
	Hypertension	137 (79.2 %)	131 (76.2 %)	137 (79.7 %)	0.69	123 (71.9 %)	138 (81.2 %)	141 (82.5 %)	0.035
	Diabetes	78 (45.1 %)	69 (40.1 %)	62 (36.0 %)	0.23	64 (37.4 %)	75 (44.1 %)	71 (41.5 %)	0.45
	Coronary artery disease	126 (72.8 %)	132 (76.7 %)	115 (66.9 %)	0.12	125 (73.1 %)	116 (68.2 %)	125 (73.1 %)	0.52
	Myocardial infarction	70 (40.5 %)	78 (45.3 %)	63 (36.6 %)	0.26	79 (46.2 %)	60 (35.3 %)	68 (39.8 %)	0.12
	Stroke or TIA	5 (2.9 %)	7 (4.1 %)	15 (8.7 %)	0.037	4 (2.3 %)	11 (6.5 %)	13 (7.6 %)	0.079
	COPD	14 (8.1 %)	9 (5.2 %)	9 (5.2 %)	0.44	11 (6.4 %)	14 (8.2 %)	7 (4.1 %)	0.29
	Treatments, N (%)
	ACEi or ARB	135 (78.0 %)	140 (81.4 %)	135 (78.5 %)	0.71	135 (78.9 %)	134 (78.8 %)	136 (79.5 %)	0.99
	Beta-blocker	125 (72.3 %)	123 (71.5 %)	112 (65.1 %)	0.29	122 (71.3 %)	116 (68.2 %)	117 (68.4 %)	0.78
	CCB	29 (16.8 %)	38 (22.1 %)	39 (22.7 %)	0.32	34 (19.9 %)	38 (22.4 %)	36 (21.1 %)	0.86
	Lipid-lowering therapy	145 (83.8 %)	143 (83.1 %)	138 (80.2 %)	0.65	141 (82.5 %)	137 (80.6 %)	144 (84.2 %)	0.68

Table 2 . Multinomial logistic model for clinical factors associated with serum concentrations of baseline PICP, PIIINP and galectin -3 PICP model Tertile 2 (71.9-91.2µg/L)

 2

	Tertile 3
	(>91.2µg/L)

Table 3 . Associations between baseline serum PICP, PIIINP, galectin-3 and baseline echocardiographic variables in multivariable logistic regression analyses PICP model Tertile 2 (71.9-91.2µg/L)

 3

	Tertile 3
	(>91.2µg/L)

Table 4 . Associations between changes in PICP, PIIINP and galectin 3, and changes in echocardiographic variables in multivariable linear regression analyses

 4

		Change in PICP*		Change in PIIINP*		Change in Galectin-3*
		Placebo		Spironolactone	Placebo		Spironolactone	Placebo		Spironolactone
		beta	p-	beta	P-	beta	p-	beta	p-	beta	p-	beta	p-
		(95%CI)	value	(95%CI)	value	(95%CI)	value	(95%CI)	value	(95%CI)	value	(95%CI)	value
	Change in LVEDVi	2.05 (-0.18 -4.27)	0.07	-0.09 (-2.05 -1.86)	0.93	-0.43 (-1.70 -0.84)	0.50	-0.20 (-1.54 -1.15)	0.78	0.11 (-2.53 -2.75)	0.93	0.14 (-2.62 -2.89)	0.92
	Change in LVEF	0.05 (-2.15 -2.26)	0.96	0.45 (-1.49 -2.38)	0.65	-0.30 (-1.53 -0.93)	0.63	0.89 (-0.51 -2.30)	0.21	-1.50 (-4.13 -1.14)	0.26	0.07 (-2.78 -2.92)	0.96
	Change in LVMi	2.49 (-2.74 -7.72)	0.35	-1.85 (-6.65 -2.96)	0.45	0.33 (-2.62 -3.28)	0.83	-1.55 (-5.09 -1.99)	0.39	-0.46 (-6.97 -6.06)	0.89	-2.93 (-9.75 -3.89)	0.40
	Change in LAVi	0.93 (-1.51 -3.37)	0.45	1.66 (-0.39 -3.71)	0.11	0.11 (-1.28 -1.51)	0.87	0.88 (-0.57 -2.33)	0.23	1.75 (-1.35 -4.85)	0.27	-5.69 (-8.58 --2.79)	<0.001
	Change in e′ mean	0.05 (-0.64 -0.73)	0.89	-0.36 (-0.88 -0.17)	0.18	-0.14 (-0.52 -0.25)	0.49	0.19 (-0.21 -0.58)	0.35	0.39 (-0.46 -1.23)	0.37	-0.05 (-0.81 -0.72)	0.90
	Change in E/e′ mean	0.80 (-0.31 -1.92)	0.16	1.07 (0.28 -1.86)	0.008	0.65 (-0.02 -1.32)	0.06	0.03 (-0.58 -0.65)	0.91	-0.75 (-2.20 -0.70)	0.31	-0.85 (-2.06 -0.36)	0.17
	Change in TAPSE	-1.21 (-3.43 -1.02)	0.29	0.83 (-1.18 -2.84)	0.42	-0.94 (-2.16 -0.28)	0.13	0.94 (-0.45 -2.32)	0.19	-3.54 (-6.09 --0.99)	0.007	-1.06 (-4.14 -2.02)	0.50

The research leading to these results has received funding from the European Union Commission's Seventh Framework programme under grant agreement N° 305507 (HOMAGE). SH acknowledge the support from the Netherlands Cardiovascular Research Initiative, an initiative with support of the Dutch Heart Foundation, Dutch Cardiovascular AllianceCVON2016-Early HFPEF, 2015-10, CVON She-PREDICTS, grant 2017-21; Furthermore, we acknowledge the support of FWO G091018N and FWO G0B5930N to S.H. AG was supported by the Instituto de Salud Carlos III (PI18/01469 co-financed by FEDER funds). SH receives personal fees for scientific advice to Astra-Zeneca, Cellprothera and CSL Behring; unrestricted research grant from Pfizer.