Hugo Gimbert
email: hugo.gimbert@labri.fr

Jérôme Renault
email: jerome.renault@tse-fr.eu.

Sylvain Sorin

Xavier Venel
email: xavier.venel@gmail.com

Wies Law Zielonka

On the values of repeated games with signals *

We study the existence of different notions of values in two-person zero-sum repeated games where the state evolves and players receive signals. We provide some examples showing that the limsup value and the uniform value may not exist in general. Then, we show the existence of the value for any Borel payoff function if the players observe a public signal including the actions played. We prove also two other positive results without assumptions on the signaling structure: the existence of the sup-value and the existence of the uniform value in recursive games with non-negative payoffs.

Introduction

The aim of this article is to study two-player zero-sum general repeated games with signals (sometimes called "stochastic games with partial observation"). At each stage, both players choose some actions. This generates a stage payoff then a new state and new signals are randomly chosen according to a transition function. Shapley [START_REF] Shapley | Stochastic games[END_REF] studied the special case of stochastic games where the players observe, at each stage, the current state and the past actions.

There are several ways to analyze these games. In this article, we will first use a point of view coming from the literature of "game determinacy" (Gale and Stewart [START_REF] Gale | Infinite games with perfect information[END_REF]). One defines an evaluation on the set of infinite histories and then study the existence of the value in the normal form game. Several evaluations will be considered.

In the initial model of Gale and Stewart [START_REF] Gale | Infinite games with perfect information[END_REF] of two-person zero-sum dynamic game with perfect information, there is no state variable. The players choose, one after the other, an action from a finite set and both observe the previous choices. Given a subset A of the set of plays (infinite sequences of actions), player 1 wins if and only if the actual play belongs to the set A: the payoff function is the indicator function of A. Gale and Stewart proved that the game is determined: either player 1 has a winning strategy or player 2 has a winning strategy, if A is open or closed with respect to the product topology. This result was then extended to more and more general classes of sets until Martin [START_REF] Martin | Borel determinacy[END_REF] proved the determinacy for every Borel set. When A is an arbitrary subset of plays, Gale and Stewart [START_REF] Gale | Infinite games with perfect information[END_REF] showed that the game may be not determined.

In 1969, Blackwell [START_REF] Blackwell | Infinite G δ games with imperfect information[END_REF] introduced a model where the players play simultaneously (and are still told their choices). Due to the lag of information, the determinacy problem is not well defined. Instead, one investigates the probability that the play belongs to A. When A is a G δ -set, a countable intersection of open sets, Blackwell proved that there exists a real number v, the value of the game, such that for each ε > 0, player 1 can ensure that the probability to be in A is greater than vε, whereas player 2 can ensure that the probability is less than v + ε. Following this literature of determinacy, Maitra and Sudderth studied stochastic games (in the framework of Shapley's model) and the largest payoff obtained infinitely often. They prove the existence of a value, called limsup value, in the countable framework [START_REF] Maitra | An operator solution of stochastic games[END_REF], in the Borelian framework [START_REF] Maitra | Borel stochastic games with lim sup payoff[END_REF] and in a finitely additive setting [START_REF] Maitra | Finitely additive and measurable stochastic games[END_REF]. In the two first cases, they assume some finiteness assumption at least on the action space on one side. Their result especially applies to finite stochastic games where the payoff is the limsup of the mean expected payoff.

The result of Blackwell was extended by Martin [START_REF] Martin | The determinacy of Blackwell games[END_REF] to any Borel-measurable evaluation function defined on the set of plays, whereas Maitra and Sudderth [START_REF] Maitra | Finitely additive stochastic games with Borel measurable payoffs[END_REF] extended to Borelmeasurable evaluation function their own result in the finitely additive setting. In all these results, the players observe past actions and the current state.

Another notion used in the study of stochastic games (where a play generates a sequence of stage payoffs) is the uniform value where some uniformity condition is required. Basically one looks at the largest amount that can be obtained by a given strategy for a family of evaluations (corresponding to longer and longer games). There are examples where the uniform value does not exist : Lehrer and Sorin [START_REF] Lehrer | A uniform Tauberian theorem in dynamic programming[END_REF] describe such a game with a countable set of states and only one player having a finite action set. On the other hand, Rosenberg, Solan and Vieille [START_REF] Rosenberg | Blackwell optimality in Markov decision processes with partial observation[END_REF] proved the existence of the uniform value in partial observation Markov Decision Processes (one player) when the set of states and the set of actions are finite. This result was extended by Renault [START_REF] Renault | Uniform value in dynamic programming[END_REF] to general action space.

The case of stochastic games with standard signaling, i.e. where the players observes the state and the actions played has been solved by Mertens and Neyman [START_REF] Mertens | Stochastic games[END_REF]. They proved the existence of a uniform value for games with a finite set of state and finite sets of actions. In fact, their proof also shows the existence of a value for the limsup of the mean payoff, as studied in Maitra and Sudderth and that both values are equal.

The aim of this paper is to provide new existence results when the players are observing only signals on state and actions. In Section 2, we define the model and present several specific Borel evaluations. We prove the existence of a value in games where the evaluation of a play is the largest stage payoff obtained along it, called sup evaluation and study several examples where the limsup value does not exist. Section 3 is the core of this paper. We focus on the case of symmetric signaling structure: repeated games where both players have the same information at each stage, and prove that a value exists for any Borel evaluation. For the proof, we introduce an auxiliary problem where the player observes the state and the actions played and we apply the generalization of Martin's result to (standard) stochastic games. Finally, in Section 4, we introduce formally the notion of uniform value and prove its existence in recursive game with non-negative payoff.

Repeated game with signals and Borel evaluation {model}

Given a set X, we denote by ∆ f (X) the set of probabilities with finite support on X. For any element x ∈ X, δ x stands for the Dirac measure concentrated on x.

Model

A repeated game form with signals Γ = (X, I, J, C, D, π, q) is defined by a countable set of states X, two finite sets of actions I and J, two finite sets of signals C and D, an initial distribution π ∈ ∆ f (X × C × D) and a transition function q from X × I × J to ∆ f (X × C × D). A repeated game with signals (Γ, g) is a pair of a repeated game form and a stage payoff function g from X × I × J to [0, 1]. This corresponds to the general model of repeated game introduced in Mertens, Sorin and Zamir [START_REF] Mertens | Repeated games. CORE Discussion Paper[END_REF].

The game is played as follows. First, a triple (x 1 , c 1 , d 1 ) is drawn according to the probability π. The initial state is x 1 , player 1 learns c 1 whereas player 2 learns d 1 . Then, independently, player 1 chooses an action i 1 in I and player 2 chooses an action j 1 in J. A new triple (x 2 , c 2 , d 2 ) is drawn according to the probability distribution q(x 1 , i 1 , j 1 ), the new state is x 2 , player 1 learns c 2 , player 2 learns d 2 and so on. At each stage n players choose actions i n and j n and a triple (c n+1 , d n+1 , x n+1 ) is drawn according to q(x n , i n , j n ), where x n is the current state, inducing the signals received by the players and the state at the next stage.

For each n 1, we denote by

H n = (X × C × D × I × J) n-1 × X × C × D the set of finite histories of length n, by H 1 n = (C × I) n-1
× C the set of histories of length n for player 1 and by H 2 n = (D × J) n-1 × D the set of histories of length n for player 2. Let H = ∪ n 1 H n . Assuming perfect recall, a behavioral strategy for player 1 is a sequence σ = (σ n ) n 1 , where σ n , the strategy at stage n, is a mapping from H 1 n to ∆(I), with the interpretation that σ n (h) is the lottery on actions used by player 1 after h ∈ H 1 n . In particular, the strategy σ 1 at stage 1 is simply a mapping from C to ∆(I) giving the law of the first action played by player 1 as a function of his initial signal. Similarly, a behavorial strategy for player 2 is a sequence τ = (τ n ) n 1 , where τ n is a mapping from H 2 n to ∆(J). We denote by Σ and T the sets of behavioral strategies of player 1 and player 2, respectively.

If for every n 1 and h ∈ H 1 n , σ n (h) is a Dirac measure then the strategy is pure. A mixed strategy is a distribution over pure strategies.

No additional measurability assumptions on the strategies are needed since the set of states is countable and the sets of actions and signals are finite. It is standard that a pair of strategies (σ, τ ) induce a probability P σ,τ on the set of plays H ∞ = (X × C × D × I × J) ∞ endowed with the σ-algebra H ∞ generated by the cylinders above the elements of H. We denote by E σ,τ the corresponding expectation.

Note also that since the initial distribution π has finite support and the sets of actions are finite, there exists a finite subset H 0 n ⊂ H n such that for all strategies (σ, τ ) the set of histories that are reached at stage n with a positive probability is included H 0 n . Historically, the first models of repeated games assumed that both c n+1 and d n+1 contain (i n , j n ) (standard signalling on the moves also called "full monitoring"). A stochastic game corresponds to the case where the state is known: both c n+1 and d n+1 contain x n+1 . A game with incomplete information corresponds to the case where the state is fixed : x 1 = x n , ∀n, but not necessarily known by the players. Several extensions have been proposed and studied, see e.g. Neyman and Sorin [START_REF]Stochastic Games and Applications[END_REF] in particular Chapters 3, 21, 25, 28. It has been noticed since Kohlberg and Zamir [START_REF] Kohlberg | Repeated games with incomplete informations: The symmetric case[END_REF] that games with incomplete information could be analyzed like stochastic games when the information is symmetric: c n+1 = d n+1 and contains (i n , j n ). Since then this approach has been extended, see e.g. Sorin [START_REF] Sorin | Symmetric incomplete information games as stochastic games[END_REF] and the analysis in the current article shows that general repeated games with symmetric information are the natural extension of standard stochastic games. However the state variable is no longer x n ∈ X but the (common) conditional probability computed by the players: the law of x n in ∆(X).

Borel evaluation and results

We now describe several ways to evaluate each play and the corresponding concepts. We follow the game determinacy literature and define an evaluation function f on infinite plays. Then we study the existence of the value of the normal form game (Σ, T , f ). We will consider especially four evaluations: the general Borel evaluation, the sup evaluation, the limsup evaluation and the limsup-mean evaluation.

An evaluation is a H ∞ -measurable function from the set of plays H ∞ to [0, 1]. Definition 1. Given an evaluation f , the game Γ has a value if

sup σ inf τ E σ,τ (f ) = inf τ sup σ E σ,τ (f ) .
This real is called the value and denoted by v(f ).

Given a repeated game (Γ, g), we will study several specific evaluations defined through the stage payoff function g.

Borel evaluation: sup-evaluation {bor2}

The first evaluation is the supremum evaluation where a play is evaluated by the largest payoff obtained along it. Definition 2. γ s is the sup evaluation defined by

∀h ∈ H ∞ , γ s (h) = sup n 1 g(x n , i n , j n ).
In (Σ, T , γ s ), the max min, the min max, and the value (called the sup-value if it exists) are respectively denoted by v s , v s and v s .

The specificity of this evaluation is that for every n 1, the maximal stage payoff obtained before n is a lower bound of the evaluation on the current play. We prove that the sup value always exists. {sup} Theorem 3. A repeated game (Γ, g) with the sup evaluation has a value v s .

In order to prove this result, we use the following result. We call strategic evaluation a function F from Σ × τ to [0, 1]. It is clear that an evaluation f induces naturally a strategic evaluation by F (σ, τ ) = E σ,τ (f ) . {FF} Proposition 4. Let (F n ) n 1 be an increasing sequence of strategic evaluations from Σ × τ to [0, 1] that converges to some function F . Assume that • Σ and τ are compact convex sets, • for every n 1, F n (σ, .) is lower semicontinuous and quasiconvex on τ for every σ ∈ σ, • for every n 1, F n (., τ ) is upper semicontinuous and quasiconcave on Σ for every τ ∈ τ . Then the normal form game (Σ, τ , F ) has a value v.

A more general version of this proposition can be found in Mertens, Sorin and Zamir [START_REF] Mertens | Repeated games. CORE Discussion Paper[END_REF] (Part A, Exercise 2, section 1.f. p.10).

Proof of Theorem 3. Let n 1 and define the strategic evaluation F n by:

F n (σ, τ ) = E σ,τ sup t n g(x t , i t , j t ) .
Players remember their own previous actions so by Kuhn's theorem, there is equivalence between mixed strategies and behaviorial strategies. The sets of mixed strategies are naturally convex. The number of histories of length n having positive probability is included in a finite set and therefore the set of pure strategies is finite. For every n 1, the function F n (σ, τ ) is thus the linear extension of a finite game. In particular F n (σ, .) is lower semicontinuous and quasiconvex on τ for every σ ∈ Σ and upper semicontinuous and quasiconcave on Σ for every τ ∈ τ .

Finally, the sequence (F n ) n∈N is increasing to

F (σ, τ ) = E π,σ,τ sup t g(x t , i t , j t ) .
It follows from Proposition 4 that the game Γ with the sup-evaluation has a value.

Borel evaluation: lim sup evaluation

Several authors have especially focused on the lim sup evaluation and the lim sup-mean evaluation.

Definition 5. γ * is the limsup evaluation defined by

∀h ∈ H ∞ , γ * (h) = lim sup n g(x n , i n , j n ).
In (Σ, T , γ * ), the max min, the min max, and the value (called the limsup value, if it exists) are respectively denoted by v * , v * and v * . Definition 6. γ * m is the limsup-mean evaluation defined by

∀h ∈ H ∞ , γ * m (h) = lim sup n 1 n n t=1 g(x t , i t , j t ).
In (Σ, T , γ * m ), the max min, the min max, and the value (called the limsup-mean value, if it exists) are respectively denoted by v * m , v * m and v * m . The limsup-mean evaluation is closely related to the limsup evaluation. Indeed, the analysis of the limsup-mean evaluation of a stochastic game can be reduced to the study of the limsup evaluation of an auxiliary stochastic game having as set of states the set of finite histories of the original game.

These evaluations were especially studied by Maitra and Sudderth [8] [9]. They proved the existence of the limsup value in a stochastic game with a countable set of states and finite sets of actions when the players observe the state and the actions played. Next they extended in [START_REF] Maitra | Borel stochastic games with lim sup payoff[END_REF] this result to a Borel measurable evaluation.

In general, a repeated game with signals has no value with respect to the limsup evaluation as shown in the following three examples. In each case, we also show that the limsup-mean value does not exist. {guess} Example 1. We consider a recursive game where the players observe neither the state nor the action played by the other player. We say that the players are in the dark.

This example, due to Shmaya, is also described in Rosenberg, Solan and Vieille [START_REF] Rosenberg | Protocols with no acknowledgment[END_REF] and can be interpreted as "pick the largest integer".

The set of states is finite X = {s 1 , s 2 , s 3 , 0 * , 1 * , -1 * , 2 * , -2 * }, the action set of player 1 is I = {T, B}, the action set of player 2 is J = {L, R}, and the transition is given by

L R L R L R T B s 1 -2 * s 1 -2 * s 2 1/2(-1 * ) + 1/2(s 3 ) 1/2(1 * ) + 1/2(s 1 ) 0 * s 3 s 3 2 * 2 * s 1 s 2 s 3
The payoff is 0 in states s 1 ,s 2 , and s 3 . For example, if the state is s 2 and if player 1 plays T and player 2 plays R then with probability 1/2 the payoff is -1 forever, and with probability 1/2 the next state is s 3 .

Claim: The game which starts in s 2 has no limsup value:

v * = -1/2 < 1/2 = v * .
Since the game is recursive, the limsup-mean evaluation and the limsup evaluation coincide, so there is no limsup-mean value either. It also follows that the uniform value, defined formally in Section 4, does not exist.

Proof: The situation is symmetric, so we consider what player 1 can guarantee. Given a strategy σ of player 1, let ε n be the probability that player 1 plays B for the first time at stage n (afterwards the game is essentially over from player 1's viewpoint), and ε * be the probability that player 1 plays T forever. Player 2 can reply as follows: fix ε > 0, and consider N such that ∞ n=N ε n ε. Define the strategy τ which plays L until stage N -1 and R at stage N . For any n > N , we have:

E s2,σ,τ (g(x n , i n , j n )) ε * (-1/2) + N -1 n=1 ε n (-1/2) + ε (1/2) -1/2 + ε.
It follows that player 1 can not guarantee more than -1/2 in the limsup sense. {semiguess} Example 2. We consider a recursive game where one player is more informed than the other: player 2 observes the state variable and the past actions played whereas player 1 observes neither the state nor the actions played.

This structure of information has been studied for example by Rosenberg, Solan, and Vieille [START_REF] Rosenberg | Stochastic games with a single controller and incomplete information[END_REF], Renault [START_REF] Renault | The value of repeated games with an informed controller[END_REF], and Gensbittel, Oliu-Barton, and Venel [START_REF] Gensbittel | Existence of the uniform value in repeated games with a more informed controller[END_REF]. They proved the existence of the uniform value under the additional assumption that the more informed player controls the evolution of the beliefs of the other player on the state variable.

The set of states is finite X = {s 1 , s 2 , s 3 , 0 * , 1/2 * , -1 * , 2 * }, the action set of player 1 is I = {T, B}, the action set of player 2 is J = {L, R}, and the transition is given by

L R L R T B s 2 1/2(-1 * ) + 1/2(s 3 ) (-1/2) * 0 * s 3 s 3 2 * 2 * s 2 s 3
We focus on the game which starts in s 2 . Both players can guarantee 0 in the sup evaluation by playing respectively T and L forever. Since the game is recursive, the limsup-mean evaluation and the limsup evaluation are equals.

Claim: The game which starts in s 2 has no limsup value:

v * = -1/2 < -1/6 = v * .
Proof: The computation of the max min with respect to the limsup-mean evaluation is similar to the computation of Example 2. The reader can check that player 1 cannot guarantee more than -1/2. We now prove that the min max is equal to -1/6. Contrary to Example 2, player 2 observes the state and actions, nevertheless the game is from his strategical point of view finished as soon as B or R is played. Therefore a strategy of player 2 is defined by the probability ε n that he plays R for the first time at stage n and the probability ε * that he plays L forever.

Fix ε > 0, and consider N such that ∞ n=N ε n ε. Player 1's replies can be reduced to the two following strategies: σ 1 which plays T forever and, σ 2 which plays T until stage N -1 and B at stage N . All the other strategies are yielding a payoff smaller with an ε-error. The strategy σ 1 yields 0 ε * + (1ε * )(-1/2) and the strategy σ 2 yields (-

1/2)ε * + (1 -ε * )1/2 -ε.
The previous payoff functions are almost the payoff of the two-by-two game where player 1 chooses σ 1 or σ 2 and player 2 chooses either never to play R or to play R at least once.

0 -1/2 -1/2 1/2
The value of this game is -1/6, giving the result. {bigmatch} Example 3. In the previous examples, the state is not known by both players. Notice that in a game with absorbing payoffs the knowledge of the state is irrelevant, We consider now a stochastic game where both players observe the state. In addition player 2 observes the past actions played whereas player 1 observes only the state. This game is a variant of the Big Match introduced by Blackwell and Ferguson [START_REF] Blackwell | The big match[END_REF]. In the original version, both player 1 and player 2 were observing the state and past actions.

L R T B 1 * 0 * 0 1
Claim: The game with the sup evaluation has a value v s = 1. The game with the limsup evaluation and the game with the limsup-mean evaluation do not have a value:

v * = v * m = 0 < 1/2 = v * m = v * .
Proof: We first prove the existence of the value with respect to the sup evaluation. Player 1 can guarantee the payoff 1. Let ε > 0, and σ be the strategy which plays T with probability ǫ and B with probability 1ǫ. This strategy yields a sup evaluation greater than 1ε. Since 1 is the maximum payoff, it is the value: v s = 1.

We now focus on the limsup evaluation and the limsup-mean evaluation. The reader can check that player 1 can not guarantee more than 0 with a proof similar to the one in Example 1 and Example 2 both in the limsup evaluation and the limsup-mean evaluation.

Let us compute what player 2 can guarantee with respect to the limsup evaluation. The computation is similar for the limsup-mean evaluation. First, player 2 can guarantee 1/2 by playing the following mixed strategy: with probability 1/2, play L at every stage and with probability 1/2, play R at every stage.

We now prove that it is the best payoff that player 2 can achieve. Fix a strategy τ for player 2 and consider the induced law P on the set H ∞ = {L, R} ∞ of infinite sequences of L and R induced by τ when player 1 plays B at every stage. Denote by β n the probability that player 2 plays L at stage n. If there exists a stage N such that β N 1/2, then playing B until N -1 and T at stage N yields a payoff greater than 1/2 to player 1. If for every n, β n 1/2, then the payoff at every stage is in expectation smaller than 1/2 and therefore the expected limsup payoff is greater than 1/2.

Symmetric repeated game with Borel evaluation {sec:symmetric}

Contrary to the sup-evaluation, in general the existence of the value for a given evaluation depends on the signaling structure. In Section 2, we analyzed three games without lim supmean value. In this section, we prove that if the signaling structure is symmetric as defined next, the value always exists for every evaluation.

Define α from H to [0, 1] where for h n = (x 1 , s 1 , i 1 , j 1 , . . . , x n , s n ):

α(h n ) = π(x 1 , s 1 )Π n-1
t=1 q(x t , i t , j t )(x t+1 , s t+1 ) and similarly, β from V to [0, 1] where for v n = (s 1 , i 1 , j 1 , . . . , s n ):

β(v n ) = hn∈Hn;Θ(hn)=vn α(h n ).
Let H n = {h n ∈ H n ; α(h n ) > 0} and V n = Θ(H n ) and recall that these sets are finite. We introduce now the set of plays that can occur during the game as

H ∞ = ∩ n H + n and V ∞ = Θ(H ∞ ) = ∩ n V n .
Remark that both are measurable subsets of H ∞ and V ∞ respectively.

For every pair of strategies (σ, τ ), we denote by P σ,τ the probability distribution induced over the set of plays (H ∞ , H ∞ ) and by Q σ,τ the probability distribution over the set of observed plays (V ∞ , V ∞ ). Thus Q σ,τ is the image of P σ,τ under Θ. Note that supp(P σ,τ ) ⊂ H ∞ .We denote respectively by E Pσ,τ and E Qσ,τ the corresponding expectations.

It turns out that for technical reasons it is much more convenient to work with the space V ∞ rather than with V ∞ ( and with H ∞ rather than with H ∞ ). And then, abusing slightly the notation, V ∞ and V n will tacitly denote the restrictions to V ∞ of the corresponding σ-algebras defined on V ∞ . On rare occasions this can lead to a confusion and then we will write for example

V n to denote the σ-algebra {U ∩ V ∞ | U ∈ V n } the restriction of V n to V ∞ .

Regular conditional probability of finite time events with respect to finite observed histories {sec:finite}

For m n

1 we define Φ n,m from H ∞ × V ∞ to [0, 1] by: Φ n,m (h, v) =      h ′ ,h ′ |n=h|n,Θ(h ′ |m)=v|m α( h ′ | m ) β( v| m ) if Θ( h| n ) = v| n 0 otherwise.
This corresponds to the joint probability of the players on the realization of the history h up to stage n, given the observed history v up to stage m. Since Φ n,m (h, v) depends only on h| n and v| m we can see Φ n,m as a function defined on H n ×V m and note that its support is included in H n ×V m . On the other hand, since each set U ∈ H n is a finite union of cylinders h + n for h n ∈ H n such that h + n ⊂ U , Φ n,m can be seen as a mapping from

H n × V ∞ into [0, 1], where Φ n,m (U, v) = hn,h + n ⊆U Φ n,m (h n , v).
Bearing this last observation in mind we have:

{lem:kernel} Lemma 10. For every m n 1, Φ n,m is a probability kernel from (V ∞ , V m ) to (H ∞ , H n ). Proof. Since hn∈Hn Φ n,m (h n , v) = 1 for v ∈ V ∞ , Φ n,m (•, v) defines a probability on H n . Moreover, for any U ∈ H n , Φ n,m (U, v) is a function of the m first components of v hence is V m -measurable.
{link} Lemma 11. Let m n 1 and (σ, τ ) be a pair of strategies. Then, for every

v m ∈ V m such that Q σ,τ (v + m ) = P σ,τ (v * m ) > 0, and every h n ∈ H n : P σ,τ (h + n |v * m ) = Φ n,m (h n , v m ). Proof. Let v m = (s 1 , i 1 , j 1 , ..., s m ) and h n ∈ H n . P σ,τ (h + n |v * m ) = P σ,τ (h + n ∩ v * m ) P σ,τ (v * m ) =      h ′ ,h ′ |n=hn,θ( h ′ | m )=vm α( h ′ | m )W (i 1 , j 1 , ..., j m-1 ) β(v m )W (i 1 , j 1 , ..., j m-1 ) if Θ(h n ) = v m | n 0 otherwise where W (i 1 , j 1 , ..., j m-1 ) = Π t m-1 σ(v m | t )(i t )τ (v m | t )(j t ).
After simplification, we recognize on the right the definition of Φ n,m (v m , h n ).

We deduce the following lemma:

{phi-m-n} Lemma 12. For every pair of strategies (σ, τ ), each W ∈ V m and U ∈ H n we have:

P σ,τ (U ∩ Θ -1 (W )) = W Φ n,m (U, v)Q σ,τ (dv).
(1) {eq:mn}

Proof. Clearly it suffices to prove (1) for cylinders

U = h + n and W = v + m with β(v m ) > 0. We have v + m Φ n,m (h n , v)Q σ,τ (dv) = Φ n,m (h n , v m )Q σ,τ (v + m ) = P σ,τ (h + n |v * m )Q σ,τ (v + m ) = P σ,τ (h + n |v * m )P σ,τ (v * m ) = P σ,τ (h + n ∩ v * m ).
Note that (1) can be equivalently written as: for every pair of strategies (σ, τ ), each

W * ∈ V * m and U ∈ H n P σ,τ (U ∩ W * ) = W * Φ n,m (U, Θ(h))P σ,τ (dh).
(2) {eq:mn^*}

Regular conditional probability of finite time events with respect to infinite observed histories {sec:dwa}

In this paragraph, we prove that instead of defining one application Φ n,m for every pair (m, n) such that m n 1, one can define a unique probability kernel

Φ n from (Ω n , V ∞ ) to (H ∞ , H n ), with Q σ,τ (Ω n ) = 1
, for all (σ, τ ), such that the extension of Lemma 12 holds. For h ∈ H ∞ , let

Ω h = {v ∈ V ∞ | Φ n,m (h, v) converges as m ↑ ∞}.
The domain Ω h is measurable (see Kallenberg [START_REF] Kallenberg | Foundations of Probability[END_REF] p.6 for example). Recall that Ω h depends only on h| n and write also Ω h|n for Ω h . Let then

Ω n = hn∈Hn Ω hn . We define Φ n : H ∞ × V ∞ → [0, 1] by Φ n = lim m→∞ Φ n,m on H ∞ × Ω n and 0 otherwise.
As a limit of a sequence of measurable mappings Φ n is measurable (see Kallenberg [START_REF] Kallenberg | Foundations of Probability[END_REF] p.6 for example).

{phi-n}

Lemma 13. (i) For each pair of strategies

(σ, τ ), Q σ,τ (Ω n ) = 1. (ii) For each v ∈ Ω n , hn∈Hn Φ n (h n , v) = 1. (iii) For each U ∈ H n the mapping v → Φ n (U, v) is a measurable mapping from (V ∞ , V ∞ ) to R.
(iv) For each pair of strategies (σ, τ ), for each U ∈ H n and each

W ∈ V ∞ P σ,τ (U ∩ Θ -1 (W )) = W Φ n (U, v) Q σ,τ (dv). ( 3
= P σ,τ [ h + n | V * m ] .
As a conditional expectation of a bounded random variable with respect to an increasing sequence of σ-algebras, Z hn,m is a martingale (with respect to P σ,τ ), hence converges P σ,τalmost surely and in L 1 to the random variable

Z hn = P σ,τ [h + n |V * ∞ ]. For m n, we define the mappings ψ n,m [h n ] : H ∞ → [0, 1], ψ n,m [h n ](h) = Φ n,m (h n , Θ(h)).

Let us show that for each h

n ∈ H n , ψ m,n [h n ] is a version of the conditional expectation E Pσ,τ [1 hn |V * m ] = P σ,τ [ h + n | V * m ]. First note that ψ n,m [h n ] is (H ∞ , V * m ) measurable. Lemma 11 implies that, for h ∈ supp(P σ,τ ) ⊂ H ∞ , ψ n,m [h n ](h) = Φ n,m (h n , Θ(h)) = P σ,τ (h + n | v| * m ) = P σ,τ (h + n | V * m )(h), where v = Θ(h). Hence the claim. Since ψ n,m [h n ] is a version of P σ,τ (h + n |V * m ), its limit ψ n [h n ] exists and is a version of P σ,τ (h + n |V * ∞ ), P σ,τ -almost surely. In particular (C1) the set Θ -1 (Ω hn ) = {h ∈ H ∞ | lim m ψ n,m [h n ](h) exists} is V * ∞ measurable and has P σ,τ -measure 1, (C2) for each W * ∈ V * ∞ , W * ψ n [h n ](h) P σ,τ (dh) = W * E[1 h + n |V * ∞ ] P σ,τ = P σ,τ (W * ∩ h + n ). Note that (C1) implies that Q σ,τ (Ω n ) = 1. (ii) If v ∈ Ω n then, for all h n ∈ H n , Φ n,m (h n , v) converges to Φ n (h n , v). But, by Lemma 10, hn∈Hn Φ n,m (h n , v) = 1.
The sum being with finitely many non-zero terms one has hn∈Hn Φ n (h n , v) = 1.

(iii) was proved before the Lemma.

(iv) Since W Φ n (h n , v) Q σ,τ (dv) = Θ -1 (W ) ψ n [h n ](h) P σ,τ (dh) for W ∈ V ∞ , using (C2) we get P σ,τ (h + n ∩ Θ -1 (W )) = W Φ n (h n , v) Q σ,τ (dv)
for U ∈ V ∞ .

Regular conditional probability of infinite time events with respect to infinite observed histories {sec:trzy}

In this section, using Kolmogorov extension theorem we construct from the sequence Φ n of probability kernels from

(Ω n , V ∞ ) to (H ∞ , H n ), one probability kernel Φ from (Ω ∞ , V ∞ ) to (H ∞ , H n ), with Q σ,τ (Ω ∞ ) = 1, for all (σ, τ ).
{phi} Lemma 14. There exists a measurable subset Ω ∞ of V ∞ such that, for all strategies σ, τ ,

• Q σ,τ (Ω ∞ ) = 1 and • there exists a probability kernel Φ from (Ω ∞ , V ∞ ) to (H ∞ , H ∞ ) such that for each W ∈ V ∞ and U ∈ H ∞ P σ,τ (U ∩ Θ -1 (W )) = W Φ(U, v) Q σ,τ (dv). ( 4

) {eq:final}

Before proceeding to the proof some remarks are in order. A probability kernel having the property given above is called a regular conditional probability.

For given strategies σ and τ the existence of a transition kernel

κ α,β from (V ∞ , V ∞ ) to (H ∞ , H ∞ ) such that for each U ∈ V ∞ and A ∈ H ∞ P σ,τ (A ∩ Θ -1 (U )) = U κ σ,τ (A, v) Q σ,τ (dv)
is well known provided that V ∞ is a Polish space and V ∞ is the Borel σ-algebra. In the current framework it is easy to introduce an appropriate metric on V ∞ such that this condition is satisfied thus the existence of κ σ,τ is immediately assured.

The difficulty in our case comes from the fact that we look for a regular conditional probability which is common for all probabilities P σ,τ , where (σ, τ ) range over all strategies of both players.

Proof. We follow the notations of the proof of Lemma 13 and define

Ω ∞ = ∩ n 1 Ω n . Let (σ, τ ) be a couple of strategies. For every n 1, Q σ,τ (Ω n ) = 1, hence Q σ,τ (Ω ∞ ) = 1. By Lemma 13(ii), given v ∈ Ω ∞ , the sequence {Φ n (•, v)} n 1 of probabilities on {(H ∞ , H n )} n 1 is
well defined. Let us show that this sequence satisfies the condition of Kolmogorov's extension theorem.

In fact Φ n,m (•, v) is defined on the power set of H n by

∀A ⊂ H n , Φ n,m (A, v) = hn∈A Φ n,m (h n , v).
Thus for every h n ∈ H n , we have

Φ n,m (h n , v) = P σ,τ (v| * m ∩ h + n ) P σ,τ (v| * m ) = P σ,τ (v| * m ∩ (h n × I × J × X × S) + ) P σ,τ (v| * m ) = Φ n+1,m (h n × (I × J × X × S), v).
Taking the limit, we obtain the same equality for Φ n and Φ n+1 hence the compatibility condition. By the Kolmogorov extension theorem for each v ∈ Ω there exists a measure Φ(

•, v) on (H ∞ , H ∞ ) such that, Φ(h + n , v) = Φ n (h + n , v) for each n and each h n ∈ H n .
Let us prove that, for each

U ∈ H ∞ , the mapping v → Φ(U, v) is V ∞ -measurable on Ω ∞ .
Let C be the class of sets A ∈ H ∞ such that Φ(A, •) has this property. By Lemma 13, C contains the π-system consisting of cylinders generating H ∞ . To show that H ∞ ⊆ C it suffices to show that C is a λ-system. Let A i be an increasing sequence of sets belonging to C.

Since, for each v ∈ V ∞ , Φ(•, v) is a measure, we have Φ(∪ n A n , v) = sup n Φ(A n , v). However, v → sup n Φ(A n , v) is measurable as a supremum of measurable mappings v → Φ(A n , v). Let A ⊃ B be two sets belonging to C. Then Φ(A \ B, v) + Φ(B, v) = Φ(A, v) by additivity of measure and v → Φ(A \ B, v) = Φ(A, v) -Φ(B, v
) is measurable as a difference of measurable mappings.

To prove (4), take a measurable subset W of V ∞ and consider the set function

H ∞ ∋ U → W Φ(U, dv)Q σ,τ (dv).
Since Φ(•, v) is nonnegative this set function is a measure on (H ∞ , H ∞ ). However by Lemma [START_REF] Martin | Borel determinacy[END_REF] this mapping is equal to U → P σ,τ (U ∩ Θ -1 (W )) for U belonging to the π-system of cylinders generating H ∞ . But two measures equal on a generating π-system are equal, which terminates the proof of (4).

A standard property of probability kernels and the fact that Ω ∞ has measure 1 imply:

{cor:transfer} Corollary 15. Let f : H ∞ → [0, 1] be H ∞ -measurable mapping. Then the mapping f : V ∞ → [0, 1] defined by:

f (v) = H∞ f (h)Φ(dh, v) if v ∈ Ω ∞ , 0 otherwise is V ∞ -measurable and E Pσ,τ [f ] = E Qσ,τ [ f ],
∀σ, τ.

Conclusion {sec:conclusion}

Given a symmetric signaling repeated game Γ we define a stochastic game Γ. The sets of actions I and J are the same as in Γ. The set of states is V = ∪ n 1 V n and the transition q from V × I × J to ∆(V ) is given by

∀v n ∈ V n , ∀i ∈ I, ∀j ∈ J, q(v n , i, j) = s∈S ψ(v n , i, j, s)δ vn,i,j,s ,
where

ψ(v n , i, j, s) = β(v n , i, j, s) β(v n ) . Note that if v n ∈ V n then the support of q(v n , i, j) is included in V n+1 , in particular is finite. Moreover, if q(v n , i, j)(v n+1 ) > 0 then v n+1 | n = v n . The initial distribution of Γ is the marginal distribution π S of π on S, if s ∈ S = V 1 , then π S (s) = x∈X π(x, s) and π S (v) = 0 for v ∈ V \ V 1 .
Let us note that the original game Γ and the auxiliary game Γ have the same sets of strategies.

Indeed a behavioral strategy in Γ is a mapping from V to probability distributions over actions. Thus each behavioral strategy in Γ is a stationary strategy in Γ. On the other hand however, each state of Γ "contains" all previously visited states and all played actions thus, for all useful purposes, in Γ behavioral strategies and stationary strategies coincide. Now suppose that (v 1 , i 1 , j 1 , v 2 , i 2 , j 2 , • • • ) is a play in Γ. Then v n+1 | n = v n for all n and there exists v ∈ V ∞ such that v| n = v n for all n. Thus defining a payoff on infinite histories in Γ amounts to defining a payoff on V ∞ . Given a Borel function f on H ∞ consider the function f defined in Corollary 15. It satisfies

E Pσ,τ (f ) = E Qσ,τ f , (5) {eq_final}
i.e. the result of playing in Γ with strategies (σ, τ ) and payoff f is the same as playing in Γ with the same strategies and payoff f . By Martin [START_REF] Martin | The determinacy of Blackwell games[END_REF] or Maitra and Sudderth [START_REF] Maitra | Stochastic games with Borel payoffs[END_REF], the stochastic game Γ with payoff f has value implying that Γ with payoff f has value.

Remark 1. The same proof applies for an N -person game form with symmetric signaling: the players know the previous moves and a common public signal on the state and have Borel payoff functions f m , m = 1, • • • , N .

Uniform value in recursive games with non-negative payoffs {uniform}

In Section 2 and Section 3, we focused on Borel evaluations. In this last Section, we focus on the family of mean average of the n first stage payoffs and the corresponding uniform value.

Definition 16. For each n 1, the mean expected payoff induced by (σ, τ ) during the first n stages is:

γ n (σ, τ ) = E σ,τ 1 n n t=1 g(x t , i t , j t ) .
{stoc_uni_1} {stoc_uni} Definition 17. Let v be a real number.

A strategy σ * of player 1 guarantees v in the uniform sense in (Γ, g) if for all η > 0 there exists n 0 1 such that

∀n n 0 , ∀τ ∈ T , γ n (σ * , τ ) v -η. (6)
Player 1 can guarantee v in the uniform sense in (Γ, g) if for all ε > 0 there exists a strategy σ * ∈ Σ which guarantees vε in the uniform sense.

A symmetric notion holds for player 2.

Definition 18. The uniform max min, denoted by v ∞ , is the supremum of all the payoff that player 1 can guarantee in the uniform sense. A uniform min max denoted by v ∞ is defined in a dual way.

If both players can guarantee v in the uniform sense, then v is the uniform value of the game (Γ, g) and denoted by v ∞ .

Many existence results have been proven in the literature concerning the uniform value and uniform max min and min max, see e.g. Mertens, Sorin and Zamir [START_REF] Mertens | Repeated games. CORE Discussion Paper[END_REF] or Sorin [START_REF] Sorin | A First Course on Zero-Sum Repeated Games[END_REF]. Mertens and Neyman [START_REF] Mertens | Stochastic games[END_REF] proved that in a stochastic game with a finite state space and finite actions spaces, where the players observe past payoffs and the state, the uniform value exists. Moreover the uniform value is equal to the limsup-mean value and for every ε > 0 there exists a strategy which guarantees v ∞ε both in the limsup-mean sense and in the uniform sense.

In general the uniform value does not exist (either in games with incomplete information on both sides or in stochastic games with signals on the actions) and in particular it depends upon the signaling structure.

Remark 2. For n 1, the n-stage game (Γ n , g) is the zero-sum game with normal form (Σ, T , γ n ) and value v n . It is interesting to note that in the special case of symmetric signaling repeated games with a finite set of states and finite set of signals, a uniform value may not exist, since even the sequence of values v n may not converge (Ziliotto [27]), but there exists a value for any Borel evaluation by Theorem 8.

We focus now on the specific case of recursive games with non-negative payoff defined as follows.

Definition 19. A state is absorbing if the probability to stay in this state is 1 for all actions and the payoff is also independent of the actions played. A repeated game is recursive if the payoff is equal to 0 outside the absorbing states. If all absorbing payoffs are non negative, the game is recursive and non negative. [START_REF] Solan | Uniform value in recursive games[END_REF] have shown the existence of a uniform value in non-negative recursive games where the players observe the state and past actions played. We show that the result is true without assumption on the signals to the players.

Solan and Vieille

In a recursive game, the limsup-mean evaluation and the limsup evaluation coincide. If the recursive game has non-negative payoffs, the sup-evaluation, the limsup evaluation and the limsup-mean evaluation both coincide. So Theorem 3 implies the existence of the value with respect to these evaluations. Using a proof similar to the proof of Theorem 3, we obtain the stronger theorem. {recursive} Theorem 20. A recursive game with non-negative payoffs has a uniform value v ∞ , equal to the sup value and the limsup value. Moreover there exists a strategy of Player 2 that guarantees v ∞ .

The proof of the existence of the uniform value is similar to the proof of Proposition 4 while using a specific sequence of strategic evaluations.

Proof of Theorem 20. The sequence of stage payoffs is non decreasing on each history: 0 until absorption occurs and then constant, equal to some non negative real. In particular, the payoff converges and the lim sup can be replaced by a limit.

Let σ be a strategy of player 1 and τ be a strategy of player 2, then γ n (σ, τ ) is non decreasing in n. This implies that the corresponding sequence of values (v n ) n∈N is non decreasing in n. Denote v = sup n v n and let us show that v is the uniform value.

Fix ε > 0, consider N such that v N vε and σ * a strategy of player 1 which is optimal in Γ N . We have for each τ and, for every n N ,

γ n (σ * , τ ) γ N (σ * , τ ) v N v -ε.
Hence the strategy σ * guarantees vε in the uniform sense. This is true for every positive ǫ, thus player 1 guarantees v in the uniform sense. Using the monotone convergence theorem, we also have

γ * (σ * , τ ) = E σ * ,τ lim n 1 n n t=1 g(x t , i t , j t ) = lim n E σ * ,τ
1 n n t=1 g(x t , i t , j t ) vε.

We now show that player 2 can also guarantee v in the uniform sense. Consider for every n, the set: K n = {τ, ∀σ, γ n (σ, τ ) v}.

K n is non empty because it contains an optimal strategy for player 2 in Γ n (since v n v). The set of strategies of player 2 is compact, hence by continuity of the n-stage payoff γ n , K n is itself compact. γ n γ n+1 implies K n+1 ⊂ K n hence ∩ n K n = ∅: there exists τ * such that for every strategy of player 1, σ and for every positive integer n, γ n (σ, τ ) v. It follows that both players can guarantee v, thus v is the uniform value. By the monotone convergence theorem, we also have

γ * (σ, τ * ) = E σ,τ * lim n 1 n n t=1 g(x t , i t , j t ) = lim n E σ,τ * 1 n n t=1 g(x t , i t , j t ) v.
Hence v is the sup and limsup value.

Remark 3. The fact that the sequence of n-stage values (v n ) n 1 is non decreasing is not enough to ensure the existence of the uniform value. For example, consider the Big Match [START_REF] Blackwell | The big match[END_REF] with no signals: v n = 1/2 for each n but there is no uniform value.

Remark 4. The theorem states the existence of a 0-optimal strategy for player 2 but player 1 may only have ε-optimal strategies. For example, in the following MDP, there are two absorbing states, two non-absorbing states with payoff 0 and two actions T op and Bottom:

1/2(s 1 ) + 1/2(s 2 ) 0 * s 2 1 * s 1 s 2
The starting state is s 1 and player 1 observes nothing. A good strategy is to play T op for a long time and then Bottom. While playing Bottom, the process absorbs and with a strictly positive probability the absorption occurs in state s 1 with absorbing payoff 0. So player 1 has no strategy which guarantees the uniform value of 1.

  ) {eq:n} Proof. (i) For h n ∈ H n and each pair of strategies σ, τ we define on H ∞ a sequence of random variables Z hn,m , m n, Z hn,m

This research was supported in part by the PEPS project. Sorin was partially supported by the European Union under the 7th Framework Programme "FP7-PEOPLE-2010-ITN", grant agreement number 264735-SADCO. Renault and Venel acknowledge the support of the Agence Nationale de la Recherche, under grant ANR JEUDY, ANR-10-BLAN 0112. Venel acknowledges the support of the the Israel Science Foundation under Grant ♯1517/11.

Model and Results

Definition 7. A symmetric signaling repeated game form is a repeated game form with signals Γ = (X, I, J, C, D, π, q) such that there exists a set S with C = D = I × J × S satisfying ∀(x, i, j) ∈ X × I × J, s,x ′ q(x, i, j)(x ′ , (i, j, s), (i, j, s)) = 1. and the initial distribution π is also symmetric: π(x, c, d) > 0 implies c = d.

Intuitively, at each stage of a symmetric signaling repeated game form the players observe both actions played and a public signal s. It will be convenient to write such a game form as a tuple Γ = (X, I, J, S, π, q) and since for such a game: q(x, i, j)(x ′ , (i ′ , j ′ , s ′ ), (i ′′ , j ′′ , s ′′ )) > 0 only if i = i ′ = i ′′ and j = j ′ = j ′′ and s ′ = s ′′ , without loss of generality, we can and will write q(x, i, j)(x ′ , s) as a shorthand for q(x, i, j)(x ′ , (i, j, s), (i, j, s)). With this notation q(x, i, j) and the initial distribution π are elements of ∆ f (X × S). The set of observed plays is then

{theo3} Theorem 8. Let Γ be a symmetric signaling repeated game form. For every evaluation f , the game Γ has a value. {corotheo3} Corollary 9. A symmetric signaling repeated game (Γ, g) has a limsup value and a limsup-mean value.

Proof of Theorem 8

Let us first give an outline of the proof. Given a symmetric signaling repeated game form Γ and a Borel evaluation f , we construct an auxiliary standard stochastic game Γ (where the players observe the state and the actions) and a Borel evaluation f on the corresponding set of plays. We use the existence of the value in the game Γ with respect to the evaluation f to deduce the existence of the value in the original game. The key idea is to define a conditional probability with respect to the σ-algebra of observed plays, compatible with the family of probability distributions generated by the players (Sections 3.2.1-3.2.3). Then we define the function f and the game Γ (Section 3.2.4) and conclude.

Let Γ be a symmetric signaling repeated game form, we do not assume the Borel evaluation to be fixed for the moment.

Let H n = (X × S × I × J) n-1 × X × S, H = ∪ n 1 H n , the set of histories and H ∞ = (X × S × I × J) ∞ , the set of plays. For all h ∈ H ∞ , define h| n ∈ H n as the projection of h on the n first stages. For all h n ∈ H n , denote by h + n the cylinder generated by h n in H ∞ :

We denote by Θ the application from H ∞ to V ∞ which forgets all the states: more precisely, Θ(x 1 , s 1 , i 1 , j 1 , . . . , x n , s n , i n , j n , . . .) = (s 1 , i 1 , j 1 , . . . , s n , i n , j n , . . .). We use the same notation for the corresponding application defined from H to V . We denote by V

n are the corresponding σ-algebras and V * ∞ the σ-algebra generated by their union. Any V n (resp. V ∞ )-measurable function ℓ on V ∞ induces a V * n (resp. V * ∞ )-measurable function ℓ • Θ on H ∞ .


Victor Magron

Didier Henrion

Jean-Bernard Lasserre

Approximating Pareto Curves using Semidefinite Relaxations

Keywords: Parametric Polynomial Optimization Problems, Semidefinite Programming, Multicriteria Optimization, Sums of Squares Relaxations, Pareto Curve, Inverse Problem from Generalized Moments

We consider the problem of constructing an approximation of the Pareto curve associated with the multiobjective optimization problem min x∈S {(f 1 (x), f 2 (x))}, where f 1 and f 2 are two conflicting polynomial criteria and S ⊂ R n is a compact basic semialgebraic set. We provide a systematic numerical scheme to approximate the Pareto curve. We start by reducing the initial problem into a scalarized polynomial optimization problem (POP). Three scalarization methods lead to consider different parametric POPs, namely (a) a weighted convex sum approximation, (b) a weighted Chebyshev approximation, and (c) a parametric sublevel set approximation. For each case, we have to solve a semidefinite programming (SDP) hierarchy parametrized by the number of moments or equivalently the degree of a polynomial sums of squares approximation of the Pareto curve. When the degree of the polynomial approximation tends to infinity, we provide guarantees of convergence to the Pareto curve in L 2 -norm for methods (a) and (b), and L 1 -norm for method (c).

Introduction

Let P be the bicriteria polynomial optimization problem min x∈S {(f 1 (x), f 2 (x))}, where S ⊂ R n is the basic semialgebraic set:

S := {x ∈ R n : g 1 (x) ≥ 0, . . . , g m (x) ≥ 0} , (1)
for some polynomials f 1 , f 2 , g 1 , . . . , g m ∈ R[x]. Here, we assume the following:

1 CNRS; LAAS; 7 avenue du colonel Roche, F-31400 Toulouse; France. 2 Université de Toulouse; LAAS, F-31400 Toulouse, France. 3 Faculty of Electrical Engineering, Czech Technical University in Prague, Technická 2, CZ-16626 Prague, Czech Republic Assumption 1.1. The image space R 2 is partially ordered with the positive orthant R 2 + . That is, given x ∈ R 2 and y ∈ R 2 , it holds x ≥ y whenever xy ∈ R 2 + .

For the multiobjective optimization problem P, one is usually interested in computing, or at least approximating, the following optimality set, defined e.g. in [START_REF] Jahn | Vector Optimization: Theory, Applications, and Extensions[END_REF]Definition 11.5].

Definition 1.2. Let Assumption 1.1 be satisfied. A point x ∈ S is called an Edgeworth-Pareto (EP) optimal point of Problem P, when there is no x ∈ S such that f j (x) ≤ f j (x), j = 1, 2 and f (x) = f (x). A point x ∈ S is called a weakly Edgeworth-Pareto optimal point of Problem P, when there is no x ∈ S such that f j (x) < f j (x), j = 1, 2.

In this paper, for conciseness, we will also use the following terminology:

Definition 1.3. The image set of weakly Edgeworth-Pareto optimal points is called the Pareto curve.

Given a positive integer p and λ ∈ [0, 1] both fixed, a common workaround consists in solving the scalarized problem:

f p (λ) := min x∈S {[(λf 1 (x)) p + ((1 -λ)f 2 (x)) p ] 1/p } , (2)
which includes the weighted sum approximation (p = 1)

P 1 λ : f 1 (λ) := min x∈S (λf 1 (x) + (1 -λ)f 2 (x)) , (3)
and the weighted Chebyshev approximation (p = ∞)

P ∞ λ : f ∞ (λ) := min x∈S max{λf 1 (x), (1 -λ)f 2 (x)} . ( 4
)
Here, we assume that for almost all (a.a.) λ ∈ [0, 1], the solution x * (λ) of the scalarized problem (3) (resp. ( 4)) is unique. Non-uniqueness may be tolerated on a Borel set B ⊂ [0, 1], in which case one assumes image uniqueness of the solution. Then, by computing a solution x * (λ), one can approximate the set {(f * 1 (λ), f * 2 (λ)) : λ ∈ [0, 1]}, where

f * j (λ) := f j (x * (λ)), j = 1, 2.
Other approaches include using a numerical scheme such as the modified Polak method [START_REF] Polak | On the approximation of solutions to multiple criteria decision making problems[END_REF]: first, one considers a finite discretization (y

(k) 1 ) of the interval [a 1 , b 1 ],
where

a 1 := min x∈S f 1 (x), b 1 := f 1 (x) , (5)
with x being a solution of min x∈S f 2 (x). Then, for each k, one computes an optimal solution x k of the constrained optimization problem y

(k) 2 := min x∈S {f 2 (x) : f 1 (x) = y (k)
1 } and select the Pareto front from the finite collection {(y

(k) 1 , y (k)
2 )}. This method can be improved with the iterative Eichfelder-Polak algorithm, see e.g. [START_REF] Eichfelder | Scalarizations for adaptively solving multi-objective optimization problems[END_REF]. Assuming the smoothness of the Pareto curve, one can use the Lagrange multiplier of the equality constraint to select the next point y (k+1) 1

. It allows to combine the adaptive control of discretization points with the modified Polak method. In [START_REF] Das | Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems[END_REF], Das and Dennis introduce the Normal-boundary intersection method which can find a uniform spread of points on the Pareto curve with more than two conflicting criteria and without assuming that the Pareto curve is either connected or smooth. However, there is no guarantee that the NBI method succeeds in general and even in case it works well, the spread of points is only uniform under certain additional assumptions. Interactive methods such as STEM [START_REF] Benayoun | Linear programming with multiple objective functions: Step method (stem)[END_REF] rely on a decision maker to select at each iteration the weight λ (most often in the case p = ∞) and to make a trade-off between criteria after solving the resulting scalar optimization problem.

So discretization methods suffer from two major drawbacks. (i) They only provide a finite subset of the Pareto curve and (ii) for each discretization point one has to compute a global minimizer of the resulting optimization problem (e.g. ( 3) or ( 4)). Notice that when f and S are both convex then point (ii) is not an issue.

In a recent work [START_REF] Bram | Approximating the pareto set of multiobjective linear programs via robust optimization[END_REF], Gorissen and den Hertog avoid discretization schemes for convex problems with multiple linear criteria f 1 , f 2 , . . . , f k and a convex polytope S. They provide an inner approximation of f (S) + R k + by combining robust optimization techniques with semidefinite programming; for more details the reader is referred to [START_REF] Bram | Approximating the pareto set of multiobjective linear programs via robust optimization[END_REF].

Contribution. We provide a numerical scheme with two characteristic features: It avoids a discretization scheme and approximates the Pareto curve in a relatively strong sense. More precisely, the idea is consider multiobjective optimization as a particular instance of parametric polynomial optimization for which some strong approximation results are available when the data are polynomials and semi-algebraic sets. In fact we will investigate this approach: method (a) for the first formulation (3) when p = 1, this is a weighted convex sum approximation; method (b) for the second formuation (4) when p = ∞, this is a weighted Chebyshev approximation; method (c) for a third formulation inspired by [START_REF] Bram | Approximating the pareto set of multiobjective linear programs via robust optimization[END_REF], this is a parametric sublevel set approximation.

When using some weighted combination of criteria (p = 1, method (a) or p = ∞, method (b)) we treat each function λ → f j (λ), j = 1, 2, as the signed density of the signed Borel measure dµ j := f j (λ)dλ with respect to the Lebesgue measure dλ on [0, 1]. Then the procedure consists of two distinct steps:

1. In a first step, we solve a hierarchy of semidefinite programs (called SDP hierarchy) which permits to approximate any finite number s + 1 of moments m j := (m k j ), k = 0, . . . , s where :

m k j := 1 0 λ k f * j (λ)dλ , k = 0, . . . , s , j = 1, 2 .
More precisely, for any fixed integer s, step d of the SDP hierarchy provides an approximation m d j of m j which converges to m j as d → ∞.

2. The second step consists of two density estimation problems: namely, for each j = 1, 2, and given the moments m j of the measure f * j dλ with unknown density f * j on [0, 1], one computes a univariate polynomial h s,j ∈ R s [λ] which solves the optimization problem min h∈Rs[λ] 1 0 (f * j (λ) -h) 2 dλ if the moments m j are known exactly. The corresponding vector of coefficients h s j ∈ R s+1 is given by h s j = H s (λ) -1 m j , j = 1, 2, where H s (λ) is the s-moment matrix of the Lebesgue measure dλ on [0, 1]; therefore in the expression for h s j we replace m j with its approximation.

Hence for both methods (a) and (b), we have L 2 -norm convergence guarantees.

Alternatively, in our method (c), one can estimate the Pareto curve by solving for each λ ∈ [a 1 , b 1 ] the following parametric POP:

P u λ : f u (λ) := min x∈S { f 2 (x) : f 1 (x) ≤ λ } , ( 6
)
with a 1 and b 1 as in [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF]. Notice that by definition f u (λ) = f * 2 (λ). Then, we derive an SDP hierarchy parametrized by d, so that the optimal solution q 2d ∈ R[λ] 2d of the d-th relaxation underestimates f * 2 over [a 1 , b 1 ]. In addition, q 2d converges to f * 2 with respect to the L 1 -norm, as d → ∞. In this way, one can approximate from below the set of Pareto points, as closely as desired. Hence for method (c), we have L 1 -norm convergence guarantees.

It is important to observe that even though P 1 λ , P ∞ λ and P u λ are all global optimization problems we do not need to solve them exactly. In all cases the information provided at step d of the SDP hierarchy (i.e. m d j for P 1 λ and P ∞ λ and the polynomial q 2d for P u λ ) permits to define an approximation of the Pareto front. In other words even in the absence of convexity the SDP hierarchy allows to approximate the Pareto front and of course the higher in the hierarchy the better is the approximation.

The paper is organized as follows. Section 2 is dedicated to recalling some background about moment and localizing matrices. Section 3 describes our framework to approximate the set of Pareto points using SDP relaxations of parametric optimization programs. These programs are presented in Section 3.1 while we describe how to reconstruct the Pareto curve in Section 3.2. Section 4 presents some numerical experiments which illustrate the different approximation schemes.

Preliminaries

Let R[λ, x] (resp. R[λ, x] 2d ) denote the ring of real polynomials (resp. of degree at most 2d) in the variables λ and x = (x 1 , . . . , x n ), whereas Σ[λ, x] (resp. Σ[λ, x] d ) denotes its subset of sums of squares (SOS) of polynomials (resp. of degree at most 2d). For every α ∈ N n the notation x α stands for the monomial x α 1 1 . . . x αn n and for every d ∈ N, let

N n+1 d := {β ∈ N n+1 : n+1 j=1 β j ≤ d}, whose cardinal is s n (d) = n+1+d d . A polynomial f ∈ R[λ, x] is written (λ, x) → f (λ, x) = (k,α)∈N n+1 f kα λ k x α ,
and f can be identified with its vector of coefficients f = (f kα ) in the canonical basis (x α ), α ∈ N n . For any symmetric matrix A the notation A 0 stands for A being semidefinite positive. A real sequence z = (z kα ), (k, α) ∈ N n+1 , has a representing measure if there exists some finite Borel measure µ on R n+1 such that

z kα = R n+1 λ k x α dµ(λ, x), ∀(k, α) ∈ N n+1 .
Given a real sequence z = (z kα ) define the linear functional L z : R[λ, x] → R by:

f (= (k,α) f kα λ k x α ) → L z (f ) = (k,α) f kα z kα , f ∈ R[λ, x] .

Moment matrix

The moment matrix associated with a sequence z = (z kα ), (k, α) ∈ N n+1 , is the real symmetric matrix M d (z) with rows and columns indexed by N n+1 d , and whose entry (i, α), (j,

β) is just z (i+j)(α+β) , for every (i, α), (j, β) ∈ N n+1 d . If z has a representing measure µ then M d (z) 0 because f , M d (z)f = f 2 dµ ≥ 0, ∀ f ∈ R sn(d) .
Localizing matrix With z as above and g ∈ R[λ, x] (with g(λ, x) = ℓ,γ g ℓγ λ ℓ x γ ), the localizing matrix associated with z and g is the real symmetric matrix M d (g z) with rows and columns indexed by N n d , and whose entry ((i, α), (j, β)) is just ℓ,γ g ℓγ z (i+j+ℓ)(α+β+γ) , for every (i, α), (j,

β) ∈ N n+1 d .
If z has a representing measure µ whose support is contained in the set {x :

g(x) ≥ 0} then M d (g z) 0 because f , M d (g z)f = f 2 g dµ ≥ 0, ∀ f ∈ R sn(d) .
In the sequel, we assume that S := {x ∈ R n : g 1 (x) ≥ 0, . . . , g m (x) ≥ 0} is contained in a box. It ensures that there is some integer M > 0 such that the quadratic polynomial g m+1 (x) := M -n i=1 x 2 i is nonnegative over S. Then, we add the redundant polynomial constraint g m+1 (x) ≥ 0 to the definition of S.

Approximating the Pareto Curve

Reduction to Scalar Parametric POP

Here, we show that computing the set of Pareto points associated with Problem P can be achieved with three different parametric polynomial problems. Recall that the feasible set of Problem P is S := {x ∈ R n : g 1 (x) ≥ 0, . . . , g m+1 (x) ≥ 0}.

Method (a): convex sum approximation Consider the scalar objective function

f (λ, x) := λf 1 (x) + (1 -λ)f 2 (x), λ ∈ [0, 1]. Let K 1 := [0, 1] × S. Recall from (3) that function f 1 : [0, 1] → R is the optimal value of Problem P 1 λ , i.e. f 1 (λ) = min x {f (λ, x) : (λ, x) ∈ K 1 }. If the set f (S) + R 2
+ is convex, then one can recover the Pareto curve by computing f 1 (λ), for all λ ∈ [0, 1], see [START_REF] Jahn | Vector Optimization: Theory, Applications, and Extensions[END_REF]Table 11.5]. Lemma 3.1. Assume that f (S) + R 2 + is convex. Then, a point x ∈ S belongs to the set of EP points of Problem P if and only if there exists some weight λ ∈ [0, 1] such that x is an image unique optimal solution of Problem P 1 λ .

Method (b): weighted Chebyshev approximation

Reformulating Problem P using the Chebyshev norm approach is more suitable when the set f (S) + R 2 + is not convex. We optimize the scalar criterion f (λ, x)

:= max[λf 1 (x), (1 -λ)f 2 (x)], λ ∈ [0, 1].
In this case, we assume without loss of generality that both f 1 and f 2 are positive. Indeed, for each j = 1, 2, one can always consider the criterion fj := f j -a j , where a j is any lower bound of the global minimum of f j over S. Such bounds can be computed efficiently by solving polynomial optimization problems using an SDP hierarchy, see e.g. [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF]. In practice, we introduce a lifting variable ω to represent the max of the objective function. For scaling purpose, we introduce the constant

C := max(M 1 , M 2 ), with M j := max x∈S f j , j = 1, 2. Then, one defines the constraint set K ∞ := {(λ, x, ω) ∈ R n+2 : x ∈ S, λ ∈ [0, 1], λf 1 (x)/C ≤ ω, (1 -λ)f 2 (x)/C ≤ ω}, which leads to the reformulation of P ∞ λ : f ∞ (λ) = min x,ω {ω : (λ, x, ω) ∈ K ∞ } consistent with (4).
The following lemma is a consequence of [START_REF] Jahn | Vector Optimization: Theory, Applications, and Extensions[END_REF]Corollary 11.21 (a)]. Lemma 3.2. Suppose that f 1 and f 2 are both positive. Then, a point x ∈ S belongs to the set of EP points of Problem P if and only if there exists some weight λ ∈ (0, 1) such that x is an image unique optimal solution of Problem P ∞ λ .

Method (c): parametric sublevel set approximation

Here, we use an alternative method inspired by [START_REF] Bram | Approximating the pareto set of multiobjective linear programs via robust optimization[END_REF]. Problem P can be approximated using the criterion f 2 as the objective function and the constraint set

K u := {(λ, x) ∈ [0, 1] × S : (f 1 (x) -a 1 )/(b 1 -a 1 ) ≤ λ},
which leads to the parametric POP P u λ : f u (λ) = min x {f 2 (x) : (λ, x) ∈ K u } which is consistent with [START_REF] Jahn | Vector Optimization: Theory, Applications, and Extensions[END_REF], and such that f u (λ) = f * 2 (λ) for all λ ∈ [0, 1], with a 1 and b 1 as in [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF]. Proof. Suppose that there exists x ∈ S such that f 1 (x) < f 1 (x) and f 2 (x) < f 2 (x). Then x is feasible for Problem P u λ (since (f 1 (x) -a 1 )/(b 1 -a 1 ) ≤ λ) and f 2 (x) ≤ f 2 (x), which leads to a contradiction.

Note that if a solution x * (λ) is unique then it is EP optimal. Moreover, if a solution x * (λ) of Problem P u (λ) solves also the optimization problem min x∈S {f 1 (x) : f 2 (x) ≤ λ}, then it is an EP optimal point (see [START_REF] Miettinen | Nonlinear Multiobjective Optimization[END_REF] for more details).

A Hierarchy of Semidefinite Relaxations

Notice that the three problems P 1 λ , P ∞ λ and P u λ are particular instances of the generic parametric optimization problem f * (y) := min (y,x)∈K f (y, x). The feasible set K (resp. the objective function f * ) corresponds to K 1 (resp. f 1 ) for Problem P 1 λ , K ∞ (resp. f ∞ ) for Problem P ∞ λ and K u (resp. f u ) for Problem P u λ . We write K := {(y, x) ∈ R n ′ +1 : p 1 (y, x) ≥ 0, . . . , p m ′ (y, x) ≥ 0}. Note also that n ′ = n (resp. n ′ = n+1) when considering Problem P 1 λ and Problem P u λ (resp. Problem P ∞ λ ). Let M(K) be the space of probability measures supported on K. The function f * is welldefined because f is a polynomial and K is compact. Let a = (a k ) k∈N , with a k = 1/(k+1), ∀k ∈ N and consider the optimization problem:

P :        ρ := min µ∈M(K) K f (y, x) dµ(y, x) s.t. K y k dµ(y, x) = a k , k ∈ N. (7)
Lemma 3.4. The optimization problem P has an optimal solution µ * ∈ M(K) and if ρ is as in [START_REF] Lasserre | Convergent sdp-relaxations in polynomial optimization with sparsity[END_REF] then

ρ = K f (y, x) dµ * = 1 0 f * (y) dy . ( 8
)
Suppose that for almost all (a.a.) y ∈ [0, 1], the parametric optimization problem f * (y) = min (y,x)∈K f (y, x) has a unique global minimizer x * (y) and let f *

j : [0, 1] → R be the function y → f * j (y) := f j (x * (y)), j = 1, 2. Then for Problem P 1 λ , ρ = 1 0 λf * 1 (λ) + (1 - λ)f * 2 (λ) dλ, for Problem P ∞ λ , ρ = 1 0 max{λf * 1 (λ), (1 -λ)f * 2 (λ)} dλ and for Problem P u λ , ρ = 1 0 f * 2 (λ) dλ.
Proof. The proof of (8) follows from [9, Theorem 2.2] with y in lieu of y. Now, consider the particular case of Problem P 1 λ . If P 1 λ has a unique optimal solution x * (λ) ∈ S for a.a. λ ∈ We set p 0 := 1, v l := ⌈deg p l /2⌉, l = 0, . . . , m ′ and d 0 := max(⌈d 1 /2⌉, ⌈d 2 /2⌉, v 1 , . . . , v m ′ ). Then, consider the following semidefinite relaxations for d ≥ d 0 :

[0, 1] then f * (λ) = λf * 1 (λ) + (1 -λ)f * 2 (λ)
         min z L z (f ) s.t. M d (z) 0 , M d-v l (p l z) 0, l = 1, . . . , m ′ , L z (y k ) = a k , k = 0, . . . , 2d . ( 9
)
Lemma 3.5. Assume that for a.a. y ∈ [0, 1], the parametric optimization problem f * (y) = min (y,x)∈K f (y, x) has a unique global minimizer x * (y), and let z d = (z d kα ), (k, α) ∈ N n+1 2d , be an optimal solution of (9). Then

lim d→∞ z d kα = 1 0 y k (x * (y)) α dy . ( 10
)
In particular, for s ∈ N, for all k = 0, . . . , s, j = 1, 2,

m k j := lim d→∞ α f jα z d kα = 1 0 y k f * j (y) dy . ( 11
)
Proof. Let µ * ∈ M(K) be an optimal solution of problem P. From [9, Theorem 3.3], lim

d→∞ z d kα = K y k x α dµ * (y, x) = 1 0 y k (x * (y)) α dy ,
which is [START_REF] Miettinen | Nonlinear Multiobjective Optimization[END_REF]. Next, from [START_REF] Miettinen | Nonlinear Multiobjective Optimization[END_REF], one has for s ∈ N:

lim d→∞ α f jα z d kα = 1 0 y k f j (x * (y)) dy = 1 0 y k f * j (y) dy ,
for all k = 0, . . . , s, j = 1, 2. Thus [START_REF] Polak | On the approximation of solutions to multiple criteria decision making problems[END_REF] holds.

The dual of the SDP (9) reads:

           ρ * d := max q,(σ l ) 1 0 q(y) dy (= 2d k=0 q k a k ) s.t. f (y, x) -q(y) = m ′ k=0 σ l (y, x) p l (y, x) , ∀y , ∀x , q ∈ R[y] 2d , σ l ∈ Σ[y, x] d-v l , l = 0, . . . , m ′ . ( 12
)
Lemma 3.6. Consider the dual semidefinite relaxations defined in [START_REF] Waki | Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity[END_REF]. Then, one has:

(i) ρ d ↑ ρ as d → ∞.
(ii) Let q 2d be a nearly optimal solution of (12), i.e., such that 1 0 q 2d (y)dy ≥ ρ * d -1/d. Then q 2d underestimates f * over S and lim d→∞ Note that one can directly approximate the Pareto curve from below when considering Problem P u λ . Indeed, solving the dual SDP [START_REF] Waki | Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity[END_REF] yields polynomials that underestimate the function λ → f * 2 (λ) over [0, 1]. Remark. In [4, Appendix A], the authors derive the following relaxation from Problem P u λ :

     max q∈R[y] d 1 0 q(λ) dλ , s.t. f 2 (x) ≥ q( f 1 (x)-a 1 b 1 -a 1 ) , ∀x ∈ S . ( 13
)
Since one wishes to approximate the Pareto curve, suppose that in (13) one also imposes that q is nonincreasing over [0, 1]. For even degree approximations, the formulation ( 13) is equivalent to

         max q∈R[y] 2d 1 0 q(λ) dλ , s.t. f 2 (λ) ≥ q(λ) , ∀λ ∈ [0, 1] , f 1 (x)-a 1 b 1 -a 1 ≤ λ , ∀λ ∈ [0, 1] , ∀x ∈ S . ( 14
)
Thus, our framework is related to [START_REF] Bram | Approximating the pareto set of multiobjective linear programs via robust optimization[END_REF] by observing that ( 12) is a strengthening of (14).

When using the reformulations P 1 λ and P ∞ λ , computing the Pareto curve is computing (or at least providing good approximations) of the functions f * j : [0, 1] → R defined above, and we consider this problem as an inverse problem from generalized moments.

• For any fixed s ∈ N, we first compute approximations m sd j = (m kd j ), k = 0, . . . , s, d ∈ N, of the generalized moments m k j = 1 0 λ k f * j (λ) dλ, k = 0, . . . , s, j = 1, 2, with the convergence property (m sd j ) → m s j as d → ∞, for each j = 1, 2. • Then we solve the inverse problem: given a (good) approximation (m sd j ) of m s j , find a polynomial h s,j of degree at most s such that m kd j = 1 0 λ k h s,j (λ) dλ, k = 0, . . . , s, j = 1, 2. Importantly, if (m sd j ) = (m s j ) then h s,j minimizes the L 2 -norm 1 0 (h(λ) -f * j (λ)) 2 dλ (see A for more details).

Computational considerations

The presented parametric optimization methodology has a high computational cost mainly due to the size of SDP relaxations ( 9) and the stateof-the-art for SDP solvers. Indeed, when the relaxation order d is fixed, the size of the SDP matrices involved in ( 9) grows like O((n + 1) d ) for Problem P 1 λ and like O((n + 2) d ) for problems P ∞ λ and P u λ . By comparison, when using a discretization scheme, one has to solve N polynomial optimization problems, each one being solved by programs whose SDP matrix size grows like O(n d ). Section 4 compares both methods. Therefore these techniques are of course limited to problems of modest size involving a small or medium number of variables n. We have been able to handle non convex problems with about 15 variables. However when a correlative sparsity pattern is present then one may benefit from a sparse variant of the SDP relaxations for parametric POP which permits to handle problems of much larger size (e.g. with more than 500 variables); see e.g. [START_REF] Waki | Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity[END_REF][START_REF] Lasserre | Convergent sdp-relaxations in polynomial optimization with sparsity[END_REF] for more details.

Numerical Experiments

The semidefinite relaxations of problems P 1 λ , P ∞ λ and P u λ have been implemented in MATLAB, using the Gloptipoly software package [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF], on an Intel Core i5 CPU (2.40 GHz).

Case 1: f (S) + R 2 + is convex

We have considered the following test problem mentioned in [START_REF] Jahn | Vector Optimization: Theory, Applications, and Extensions[END_REF]Example 11.8]:

Example 1.
Let The weighted sum approximation method (a) being suitable when the set f (S) + R 2 + is convex, one reformulates the problem as a particular instance of Problem P 1 λ . For comparison, we fix discretization points λ 1 , . . . , λ N uniformly distributed on the interval [0, 1] (in our experiments, we set N = 100). Then for each λ i , i = 1, . . . , N, we compute the optimal value f * (λ i ) of the polynomial optimization problem P 1 λ i . The dotted curves from Figure 2 display the results of this discretization scheme. From the optimal solution of the dual SDP (12) corresponding to our method (a), namely weighted convex sum approximation, one obtains the degree 4 polynomial q 4 (resp. degree 6 polynomial q 6 ) with moments up to order 8 (resp. 12), displayed on Figure 2 (a) (resp. (b)). One observes that q 4 ≤ f * and q 6 ≤ f * , which illustrates Lemma 3.6 (ii). The higher relaxation order also provides a tighter underestimator, as expected. Then, for each λ i , i = 1, . . . , 100, we compute an optimal solution x * (λ i ) of Problem P 1

g 1 := -x 2 1 + x 2 , f 1 := -x 1 , g 2 := -x 1 -2x 2 + 3 , f 2 := x 1 + x 2 2 . S := {x ∈ R 2 : g 1 (x) ≥ 0, g 2 (x) ≥ 0} .
λ i and we set f * 1i := f 1 (x * (λ i )), f * 2i := f 2 (x * (λ i ))
. Hence, we obtain a discretization (f * 1 , f * 2 ) of the Pareto curve, represented by the dotted curve on Figure 3. The required CPU running time for the corresponding SDP relaxations is 26sec.

We compute an optimal solution of the primal SDP (9) at order d = 5, in order to provide a good approximation of s + 1 moments with s = 4, 6, 8. Then, we approximate each function f * j , j = 1, 2 with a polynomial h sj of degree s by solving the inverse problem from generalized moments (see Appendix A). The resulting Pareto curve approximation using degree 4 estimators h 41 and h 42 is displayed on Figure 3 (a). For comparison purpose, higher degree approximations are also represented on Figure 3 (b) (degree 6 polynomials) and Figure 3 (c) (degree 8 polynomials). It consumes only 0.4sec to compute the two degree 4 polynomials h 41 and h 42 , 0.5sec for the degree 6 polynomials and 1.4sec for the degree 8 polynomials.

-1 -0.6 -0.2 0.2 0.6 1 -1 We have also solved the following two-dimensional nonlinear problem proposed in [START_REF] Wilson | Efficient Pareto Frontier Exploration using Surrogate Approximations[END_REF]:

0 1 2 3 (h 41 , h 42 ) (f * 1 , f * 2 ) (a) Degree 4 estimators -1 -0.6 -0.2 0.2 0.6 1 -1 0 1 2 3 (h 61 , h 62 ) (f * 1 , f * 2 ) (b) Degree 6 estimators -1 -0.6 -0.2 0.2 0.6 1 -1 0 1 2 3 (h 81 , h 82 ) (f * 1 , f * 2 ) (c) Degree 8 estimators
Example 2. Let In this case, the weighted convex sum approximation of method (a) would not allow to properly reconstruct the Pareto curve, due to the apparent nonconvex geometry of the set f (S) + R 2 + . Hence we have considered methods (b) and (c).

g 1 := -(x 1 -2) 3 /2 -x 2 + 2.5 , f 1 := (x 1 +x 2 -7.5) 2 4 + (x 2 -x 1 + 3) 2 , g 2 := -x 1 -x 2 + 8(x 2 -x 1 + 0.65) 2 + 3.85 , f 2 := 0.4(x 1 -1) 2 + 0.4(x 2 -4) 2 . S := {x ∈ [0, 5] × [0, 3] : g 1 (x) ≥ 0, g 2 (x) ≥ 0} .

Method (b): weighted Chebyshev approximation

As for Example 1, one solves the SDP (9) at order d = 5 and approximate each function f * j , j = 1, 2 using polynomials of degree 4, 6 and 8. The approximation results are displayed on Figure 5. Degree 8 polynomials give a closer approximation of the Pareto curve than degree 4 or 6 polynomials. The solution time range is similar to the benchmarks of Example 1. The SDP running time for the discretization is about 3min. The degree 4 polynomials are obtained after 1.3sec, the degree 6 polynomials h 61 , h 62 after 9.7sec and the degree 8 polynomials after 1min.

Method (c): parametric sublevel set approximation

Better approximations can be directly obtained by reformulating Example 2 as an instance of Problem P u λ and compute the degree d optimal solutions q 2d of the dual SDP [START_REF] Waki | Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity[END_REF]. Figure 6 reveals that with degree 4 polynomials one can already capture the change of sign of the Pareto front curvature (arising when the values of f 1 lie over [START_REF] Miettinen | Nonlinear Multiobjective Optimization[END_REF]18]). Observe also that higher-degree polynomials yield tighter underestimators of the left part of the Pareto front. The CPU time ranges from 0.5sec to compute the degree 4 polynomial q 4 , to 1sec for the degree 6 computation and 1.7sec for the degree 8 computation. The discretization of the Pareto front is obtained by solving the polynomial optimization problems P u λ i , i = 1, . . . , N. The corresponding running time of SDP programs is 51sec.

The same approach is used to solve the random bicriteria problem of Example 3.

Example 3.

Here, we generate two random symmetric real matrices Q 1 , Q 2 ∈ R 15×15 as well as two random vectors q 1 , q 2 ∈ R 15 . Then we solve the quadratic bicriteria problem min x∈[-1,1] 15 {f 1 (x), f 2 (x)}, with f j (x) := x ⊤ Q j x/n 2q ⊤ j x/n, for each j = 1, 2. Experimental results are displayed in Figure 7. For a 15 variable random instance, it consumes 18min of CPU time to compute q 4 against only 0.5sec for q 2 but the degree 4 underestimator yields a better point-wise approximation of the Pareto curve. The running time of SDP programs is more than 8 hours to compute the discretization of the front.

Conclusion

The present framework can tackle multicriteria polynomial problems by solving semidefinite relaxations of parametric optimization programs. The reformulations based on the weighted sum approach and the Chebyshev approximation allow to recover the Pareto curve, defined here as the set of weakly Edgeworth-Pareto points, by solving an inverse problem from generalized moments. An alternative method builds directly a hierarchy of polynomial underestimators of the Pareto curve. The numerical experiments illustrate the fact that the Pareto curve can be estimated as closely as desired using semidefinite programming within a reasonable amount of time for problem still of modest size. Finally our approach could be extended to higher-dimensional problems by exploiting the system properties such as sparsity patterns or symmetries.

A Appendix. An Inverse Problem from Generalized Moments

Suppose that one wishes to approximate each function f * j , j = 1, 2, with a polynomial of degree s. One way to do this is to search for h j ∈ R s [λ], j = 1, 2, optimal solution of min

h∈Rs[λ] 1 0 (h(λ) -f * j (λ)) 2 dλ , j = 1, 2 . ( 15
)
Let H s ∈ R (s+1)×(s+1) be the Hankel matrix associated with the moments of the Lebesgue measure on [0, 1], i.e. H s (i, j) = 1/(i + j + 1), i, j = 0, . . . , s.

Theorem A.1. For each j = 1, 2, let m s j = (m k j ) ∈ R s+1 be as in [START_REF] Polak | On the approximation of solutions to multiple criteria decision making problems[END_REF]. Then (15) has an optimal solution h s,j ∈ R s [λ] whose vector of coefficient h s,j ∈ R s+1 is given by: h s,j = H -1 s m s j , j = 1, 2 .

(16)

Proof. Write

Lemma 3 . 3 .

 33 Suppose that x ∈ S is an optimal solution of Problem P u λ , with λ ∈ [0, 1]. Then x belongs to the set of weakly EP points of Problem P.

  for a.a. λ ∈ [0, 1]. The proofs for P ∞ λ and P u λ are similar.

1 0

 1 |f * (y) -q 2d (y)|dµ = 0. Proof. It follows from [9, Theorem 3.5].

Figure 1

 1 Figure 1 displays the discretization of the feasible set S as well as the image set f (S).The weighted sum approximation method (a) being suitable when the set f (S) + R 2 + is convex, one reformulates the problem as a particular instance of Problem P 1 λ . For comparison, we fix discretization points λ 1 , . . . , λ N uniformly distributed on the interval [0, 1] (in our experiments, we set N = 100). Then for each λ i , i = 1, . . . , N, we compute

Figure 1 :

 1 Figure 1: Preimage and image set of f for Example 1

Figure 2 :

 2 Figure 2: A hierarchy of polynomial underestimators of the Pareto curve for Example 1 obtained by weighted convex sum approximation (method (a))

Figure 3 : 4 . 2

 342 Figure 3: A hierarchy of polynomial approximations of the Pareto curve for Example 1 obtained by the weighted convex sum approximation (method (a))

Figure 4

 4 Figure 4 depicts the discretization of the feasible set S as well as the image set f (S) for this problem. Note that the Pareto curve is non-connected and non-convex.

Figure 4 :

 4 Figure 4: Preimage and image set of f for Example 2

Figure 5 :

 5 Figure 5: A hierarchy of polynomial approximations of the Pareto curve for Example 2 obtained by the Chebyshev norm approximation (method (b))

Figure 6 :

 6 Figure 6: A hierarchy of polynomial underestimators of λ → f * 2 (λ) for Example 2 obtained by the parametric sublevel set approximation (method (c))

Figure 7 :

 7 Figure 7: A hierarchy of polynomial underestimators of λ → f * 2 (λ) for Example 3 obtained by the parametric sublevel set approximation (method (c))

1 0 1 0h

 11 (h(λ) -f * j (λ)) 2 dλ = )f * j (λ)dλ B + (f * j (λ)) 2 dλ C ,and observe thatA = h ⊤ H s h , B = k m k j = h ⊤ m j ,and so, as C is a constant, (15) reduces tomin h∈R s+1 h ⊤ H s h -2h ⊤ m j , j = 1, 2 ,from which (16) follows.

Acknowledgments

This work was partly funded by an award of the Simone and Cino del Duca foundation of Institut de France.