Jean-Louis Dufresne
email: jean-louis.dufresne@lmd.jussieu.fr

Positive feedback in climate: stabilization or runaway, illustrated by a simple experiment

The response of the various climatic processes to climate change can amplify (positive feedback) or damp (negative feedback) the initial temperature perturbation. An example of a positive feedback is the surface albedo feedback: when the surface temperature rises, part of the ice and snow melts leading to an increase in the solar radiation absorbed by the surface and to an enhanced surface warming. Positive feedbacks can lead to instability. On Venus for example, a positive feedback is thought to have evolved into a runway greenhouse effect. However, positive feedbacks can exist in stable systems. This paper presents a simple representation of a positive feedback in both a stable and an unstable system. A simple experimental device based on a scale principle is introduced to illustrate the positive feedback and its stabilization or runaway regimes. Stabilization can be achieved whether the amplitude of the positive feedback declines (e.g. "saturation" of the feedback) or remains constant. The device can also be used to illustrate the existence of tipping points, which are threshold values beyond which the amplification due to feedbacks or the stability of the system suddenly changes. The physical equations of the device are established in the framework of the feedback analysis. Key features to understand why a positive feedback does not necessarily lead to a runaway effect are described. The analogy between the different components of the device and those of the climate system is established. Finally, the contribution of individual feedbacks to the total climate response is addressed. (Capsule Summary)To illustrate the concepts of positive feedback, stability, instability, tipping point and saturated feedback we conceive a very simple device based on a scale with two water reservoirs.

Introduction

At the end of the 19 th century, Joseph Fourier established that the Earth's surface temperature is primarily driven by a fundamental law, the law of conservation of energy [START_REF] Burgess | Remarques générales sur les températures du globe terrestre et des espaces planétaires[END_REF][START_REF] Fourier | General remarks on the temperature of the terrestrial globe and the planetary spaces[END_REF][START_REF] Pierrehumbert | Greenhouse effect: Fourier's concept of planetary energy balance is still relevant today[END_REF]). More specifically, he established that the surface temperature adjusts until the energy budget at the surface reaches equilibrium. He also established that any change of the energy budget at the surface has a direct impact on the surface temperature. A few decades later, Svante Arrhenius used the single-layer model framework suggested by Fourier to quantify each term of the energy budget at the surface and to estimate the energy imbalance due to a change in the atmospheric CO 2 concentration [START_REF] Arrhenius | On the influence of carbonic acid in the air upon the temperature of the ground[END_REF]. He also identified that the major physical phenomenon driving the energy budget adjustment was the Stefan-Boltzmann radiation emission law. Arrhenius also analyzed how water vapor, clouds and snow may vary with the surface temperature and may impact the energy budget. These estimates were very crude and a major improvement was achieved 70 years later when [START_REF] Manabe | Thermal equilibrium of the atmosphere with a given distribution of relative humidity[END_REF] estimated the temperature response to an atmospheric CO 2 increase using a single-column radiative-convective model. These studies and many following ones emphasize the importance of changes in water vapor, clouds, snow and ice extent to estimate the surface temperature change.

The atmospheric water vapor amount, for example, increases with temperature following the Clausius-Clapeyron law assuming fixed relative humidity. As water vapor is a powerful greenhouse gas, such an increase contributes to a further warming of the climate. This positive 'feedback' loop amplifies a given perturbation of the surface temperature by about a factor two [START_REF] Manabe | Thermal equilibrium of the atmosphere with a given distribution of relative humidity[END_REF][START_REF] Dufresne | An assessment of the primary sources of spread of global warming estimates from coupled Atmosphere-Ocean models[END_REF]. This feedback is amplified as the climate warms due to the increase in the tropopause height [START_REF] Meraner | Robust increase in equilibrium climate sensitivity under global warming[END_REF]. Depending on the conditions, this feedback amplification can eventually turn into a runaway greenhouse effect [START_REF] Kasting | Runaway and moist greenhouse atmospheres and the evolution of Earth and Venus[END_REF]Gold-blatt et al. 2013): as the temperature rises, the moist convective layer becomes optically thicker and absorbs more and more infrared radiation. A tipping point is reached when the layer becomes fully opaque and the tropopause acquires a fixed temperature [START_REF] Goldblatt | Low simulated radiation limit for runaway greenhouse climates[END_REF]. The surface temperature then increases without modifying the outgoing radiative flux until the planet is so warm that it emits near-visible radiations. A runaway greenhouse effect is thought to have happened on Venus, explaining its current atmospheric composition and its high density [START_REF] Kasting | Runaway and moist greenhouse atmospheres and the evolution of Earth and Venus[END_REF].

Another climate feedback is due to surface albedo: a surface cooling, for example, increases ice and snow cover, which leads to an increased surface albedo and to a further cooling of the surface [START_REF] Budyko | The effect of solar radiation variations on the climate of the Earth[END_REF][START_REF] Sellers | A global climate model based on the energy balance of the Earth-atmosphere system[END_REF]. For a very cold Earth, an extra cooling perturbation can trigger a runaway regime and the Earth can eventually be totally covered by snow: this is the so-called snowball Earth hypothesis [START_REF] Stern | Evidence for the snowball earth hypothesis in the arabian-nubian shield and the east african orogen[END_REF][START_REF] Kopp | The paleoproterozoic snowball Earth: A climate disaster triggered by the evolution of oxygenic photosynthesis[END_REF].

It could be intuitively stated that a positive feedback "never stops" and is necessarily associated with a runaway regime. This actually may happen in some cases defined as unstable, but this is not necessarily the case. The aim of this paper is to illustrate how systems (e.g. the climate) with positive feedbacks can be stable. When a system is stable, the positive feedback simply amplifies a given perturbation without triggering a runaway regime. The system then stabilizes and reaches a new equilibrium. The physical environment of the system in each of its equilibria is similar. This paper also illustrates how systems with positive feedbacks can be or can become unstable. In this case the positive feedback triggers a runaway regime and the system evolves and reaches a very different state. To investigate positive feedbacks in both a stable and an unstable system, a simple mechanical device is used. This device is based on a scale where a positive feedback can be added. When a weight is added to one side of the scale, the scale either slightly tilts and stabilizes or it turns over, depending on the setup. Simple developments of this device further illustrate the existence of tipping points (i.e. thresholds at which the amplitude of the feedback and potentially the stability are abruptly modified).

The experimental device, its stability, and the interpretation of the results are presented in section 2. The analogy between the experiment and the climate system is presented in section 3, first using a very simple model and then using the classical approach used to analyze comprehensive climate models. Some more details on climate feedbacks and on the question of individual contribution of feedbacks to the temperature change are addressed in section 4. Complementary discussions are given in section 5.

The mechanical device and the experiment a. Description of the device

The device is shown in Fig. 1 and Fig. 2 gives a simplified schematic of it. The simplifications of the schematic aim at facilitating the mathematical expressions to model the device. The device is a cross attached to a fixed pillar through its intersection O, so that the cross can rotate around this fixed axis. Initially, the cross is vertical with a long vertical bar and a shorter horizontal bar. One cylindrical water container is hung on each side of the horizontal bar, equidistant from O and separated by the distance l 2 (note that the containers stay vertical in this simplified schematic whereas in reality they rotate with the device).

The containers are about half filled with water and have the same mass. They can communicate through a pipe with a tap at their bottom and another pipe at their top, so that the circulation system is closed. A mass m 3 is at the bottom of the vertical bar, at the distance l 3 from O.

The tilt ∆θ of the cross is driven by the sum of the moments of force, which are given here by the product between the mass weight and the horizontal projection of the pivot-mass vector.

The construction of the device is of no practical difficulty and very common materials may be used. Feeders for small rodents have been used for the reservoirs and the pipe and tap have been found in aquarium stores.

b. The experiment

Initially, the system is vertically straight as illustrated in Figs. 1a and2a and the tap between the two containers is closed. At equilibrium, the sum of the moments of force is null. A small mass m 1 is added to one extremity of the horizontal bar, and this leads to a tilt of the device by a small angle ∆θ i (subscript i stands for initial change) (Figs. 1b and2b). The angle is small because of the counterweight of the mass m 3 , which generates a return moment.

If the tap is now opened, the water follows gravity and flows from the upper reservoir to the lower one (Figs. 1c and2c). As the lower container becomes heavier and the upper one lighter, the initial tilt of the device is amplified. The height between the two reservoirs increases, more water flows down, and the tilt is further amplified. This is a positive feedback.

How can this amplification loop be stopped? When the tilt increases, the return moment of the counterweight m 3 also increases and balances the growth of the "horizontal bar moment" (i.e. the sum of the moments generated by the masses on the horizontal bar) due to the water transfer. The return moment then stabilizes the device with a final tilt ∆θ .

To understand why the device eventually stabilizes and which conditions need to be met for this, the experiment is described using a simple mathematical model (see details in the supplementary material). When the stabilization is reached, the final tilt ∆θ is the sum of the initial tilt ∆θ i due to the addition of m 1 and its amplification ∆θ f due to the feedback (subscript f stands for feedback). This amplification ∆θ f depends on the water mass transferred from the upper reservoir to the lower one. The latter depends on the height between the two containers, which depends on the total tilt ∆θ . In other words, the tilt amplification ∆θ f depends on the final tilt ∆θ and can be written as ∆θ f = g∆θ where g is a function of the containers cross section S, the water density ρ, and the device parameters presented above (see supplementary material):

g = ρS l 2 2 2 l 3 m 3 (1)
The final tilt can be written:

∆θ = ∆θ i + ∆θ f = 1 1 -g ∆θ i (2)
where g, defined by Eq. 1, is now the feedback gain as defined in the classical feedback literature. If g is positive and smaller than 1, the final tilt at equilibrium ∆θ is larger than the initial tilt without feedback ∆θ i , as it can be tested using the described experiment. Indeed, according to Eq. 1, g is necessarily positive, and smaller than 1 as long as the counterweight m 3 is heavy enough. Note that the gain g can also be increased with the distance between the containers and with their cross section, or decreased with the length of the vertical bar. These parameters are chosen from the beginning and stay fixed once the device is built, while the mass m 3 can easily be adjusted by using a bottle and filling it as much as needed.

When the feedback gain g becomes close to 1, the final tilt ∆θ becomes infinitely greater than ∆θ i (cf. Eq. 2), meaning that the system is unstable. In the experiment, this happens if the counterweight m 3 is suppressed or if its mass is too small: the device is not able to stabilize and it keeps on tilting until it eventually turns over, reaching a very different equilibrium (Fig. 1d). In practical terms, the mathematical expression of g is only valid for small tilts. When g is close to 1, the mathematical expression of g points out that the system is unstable, but the value of g cannot describe the final state of the device, as the linear equations describing the system are not valid anymore. The instability consists in a change of regime, as illustrated by the experiment: in the unstable case, the positive feedback generates a runaway from the initial state into a different regime, in which the device can reach a very different equilibrium.

c. Possible extensions

The device can be adapted to illustrate more complex situations.

Saturation The positive feedback loop can be stopped by saturation processes. For example if the upper reservoir becomes empty, the positive feedback stops. On the contrary, if there is too much water, the lower reservoir fills up, which also interrupts the positive feedback loop.

Tipping point

The containers of the device now have a varying section as illustrated in Fig. 3. The cylindrical containers are narrower at their center than at their extremities. Eq.1 shows that increasing the section amplifies the feedback gain. If the water level is initially in the middle of both containers and if the added perturbation is strong enough, the tilt can make the water reach the level of changing section in both containers. This would amplify the feedback. In some cases, this amplitude change can be so large that it can make the system unstable. On the contrary, if the cylindrical containers are widened at their center, the feedback is reduced if the water reaches the level of changing section.

Analogy with climate a. Example of the surface albedo feedback

Let us consider an idealized climate system with only one positive feedback, the so-called albedo feedback. The Earth is considered as a simple isothermal sphere that can be described by global variables (e.g. temperature, radiative fluxes) that do not depend on latitude. There is no atmosphere, no ocean and the surface albedo is assumed to change with the temperature in order to mimic the ice or snow cover change. If the device would represent this climate system, the angle θ would be the surface temperature, T , and the horizontal bar moment would be the absorbed solar flux at the surface, F. The latter can be perturbed by some external process, as represented by the addition of the mass m 1 in the experiment. The first-order response of the surface temperature to the absorbed solar flux follows the black body emission T = (F/σ ) 1/4 (Planck law), where σ is the Stefan-Boltzmann constant. This is the "Planck response". By analogy, the inclination of the device responds to the horizontal bar moment following the balance with the return moment of the counterweight m 3 .

As the surface warms up, part of the ice or snow covered area melts, reducing the surface albedo, α, increasing the solar flux absorbed by the surface. Absorbed solar radiation and surface temperature variations thus reinforce each other via a positive feedback. A feedback gain g α can be computed (see supplementary material for details):

           g α = - λ α λ P λ α = -I ∂ α ∂ T λ P = -4σ T 3 (3)
where I is a quarter of the solar constant, ∂ α ∂ T is the sensitivity of the surface albedo α to the temperature, and λ α and λ P are called the albedo response parameter and the Planck response parameter respectively. The albedo decreases with temperature, meaning that λ α > 0 and g α > 0 (i.e. the feedback is positive). This system is stable if g α < 1, i.e. if the additional absorbed solar energy induced by the decreasing albedo (λ α ) is smaller than the additional energy loss via radiative emission at the surface (-λ P ). For current climate conditions, the former is about 0.3 Wm -2 K -1 and the latter about 3 Wm -2 K -1 [START_REF] Dufresne | An assessment of the primary sources of spread of global warming estimates from coupled Atmosphere-Ocean models[END_REF], indicating that the idealized climate system with only surface albedo feedback is clearly stable. The basic phenomenon that stabilizes the climate, in this very simple model but also in the real climate on Earth and on other planets, is the black body emission as given by the Planck law. The analogue of the Planck law for the device is the return moment of the mass m 3 .

Saturation and tipping point

The examples of saturated feedback and tipping point presented with the experiment illustrate well some climatic processes that can come into play with the albedo feedback. For example, the albedo feedback saturates if -in case of a surface warming -there is no more ice or snow on Earth. A tipping point may exist if -in case of a surface cooling -the ice-sheet extends equatorward beyond a critical latitude [START_REF] Budyko | The effect of solar radiation variations on the climate of the Earth[END_REF][START_REF] Sellers | A global climate model based on the energy balance of the Earth-atmosphere system[END_REF]. Indeed, little variations in albedo have stronger impacts in the tropics than in the polar regions. Passing this tipping point can trigger a snowball Earth state.

b. Feedback analysis for the climate system

Over the last few decades, the feedback framework has been used to analyze the climate system (e.g. [START_REF] Hansen | Climate sensitivity: Analysis of feedback mechanisms[END_REF][START_REF] Soden | An assessment of climate feedbacks in coupled ocean atmosphere models[END_REF][START_REF] Bony | How well do we understand and evaluate climate change feedback processes?[END_REF]). This feedback analysis focuses on radiative and short-term feedbacks, as it assumes the climate system is at equilibrium. Some key aspects are presented here to link the experiment with the climate system, where many feedback processes are at play. To do so, the response of the whole climate system to an external perturbation is first considered. This response is then decomposed into a no-feedback response and an additional response due to feedbacks. Finally the feedback gain is introduced.

(i) State equation. The classical climate feedback analysis is rooted in a simple non-dimensional linear energy budget model, that gives the global mean temperature change ∆T at equilibrium in response to a radiative forcing ∆Q (Fig. 4-a):

∆T = - ∆Q λ (4)
where ∆Q (Wm -2 ) is positive downward (i.e. when it heats the climate system) and λ (Wm -2 K -1 ) represents how all the processes of the climate system modify the net flux at the tropopause (positive downward) when the surface temperature is changed. λ is thus negative, as an increase in the surface temperature decreases the net flux at the tropopause. This parameter is called the "climate response parameter".

(ii) Introducing a feedback loop. Based on the current physical understanding of the climate system, the climate response parameter is split into two parts. A classical decomposition consists in isolating the Planck response λ P as was done in the previous section. This choice will be discussed later. The response parameter λ f of the remaining processes is then:

λ f = λ -λ P . (5)
This decomposition allows the introduction of a feedback loop. When only the Planck response is considered, the temperature response to a variation ∆F of the incoming flux at the tropopause reads:

∆T = - ∆F λ P (6)
The flux variation at the tropopause ∆F is the sum of the radiative forcing ∆Q and a complementary contribution ∆F f due to the feedback processes (included in the response parameter λ f ):

∆F = ∆Q + ∆F f (7) ∆F f = λ f ∆T (8)
Equations 5 to 8 are equivalent to Eq. 4. They describe the whole system after a feedback loop has been introduced as represented on Fig. 4-b.

(iii) Introducing the feedback gain. Without any feedback (i.e. when only the Planck response is considered) the temperature change in response to the radiative forcing ∆Q is:

∆T p = - ∆Q λ p (9)
The temperature increase ∆T is the sum of the Planck response ∆T P and the additional response due to feedbacks ∆T f (Fig. 4-c). The previous equations (5 to 8) can be rewritten to introduce the feedback gain g used in classical feedback analysis:

∆T = ∆T f + ∆T P (10) ∆T f = g ∆T (11) g = - λ f λ P (12)
The description of the system using this set of equations is represented on Fig. 4-c and the classical expression of the temperature response using the feedback gain reads:

∆T = 1 1 -g ∆T P (13)
The analog of this equation in the experiment is Eq. 2. The initial tilt ∆θ i is analog to the Planck response, as it corresponds to the initial response when only the counterweight m 3 (analog to the Planck law) acts. The gain g quantifies how all the feedbacks (i.e. all the processes except those included in the Planck response parameter) reinforce or oppose the Planck response ∆T P .

(iv) Non linearity of the feedback response. When the response parameter due to feedbacks is doubled (i.e. λ f = 2 * λ f ) the feedback gain is also doubled (Eq. 12). But this is not the case for the total response (Eq. 13) nor for the additional response due the feedbacks (Eq. 11). This can be verified with the experimental device by adding a new pair of identical containers that can communicate through an independent pipe (see supplementary material). When the feedback gain g is doubled, the response due to a positive feedback (i.e. the increase of the tilt) is multiplied by more than a factor of two. This is a direct consequence of Eq.2. The amplitude of the additional response due to the feedback depends on the value of g and is larger as g becomes closer to one.

Climate feedbacks

An overview of how results from climate models are usually analyzed is provided here to understand and quantify the main physical phenomena driving the amplitude of the surface temperature change in response to an external forcing.

a. Forcings

The radiative forcing ∆Q (Wm -2 ), introduced in section 3, is defined as the perturbation of the net radiative flux at the tropopause before any surface temperature takes place. The change in the net radiative flux at the tropopause is close to the one at the top of the atmosphere [START_REF] Hansen | Climate sensitivity: Analysis of feedback mechanisms[END_REF][START_REF] Stuber | Stratosphere adjusted radiative forcing calculations in a comprehensive climate model[END_REF]. This forcing was originally computed assumming no changes in the troposphere and could therefore be computed using radiation-only models. The adjustment of the troposphere to the forcing while the surface temperature remains constant has been recently included in the computation (Gregory and Webb 2008; [START_REF] Andrews | CO 2 forcing induces semi-direct effects with consequences for climate feedback interpretations[END_REF][START_REF] Boucher | Clouds and aerosols. Climate Change 2013: The Physical Scientific Basis. Contribution of Working Group I to the Fifth Assessment Report of the Intergovernmental Panel on Climate Change[END_REF][START_REF] Vial | On the interpretation of inter-model spread in CMIP5 climate sensitivity estimates[END_REF], modifying the exact value of the forcing but not the global climate response. As an example, the current estimate of the radiative forcing for a doubling of the CO 2 concentration is about 3.7 Wm -2 [START_REF] Myhre | Anthropogenic and natural radiative forcing. Climate Change 2013: The Physical Scientific Basis. Contribution of Working Group I to the Fifth Assessment Report of the Intergovernmental Panel on Climate Change[END_REF][START_REF] Dufresne | An assessment of the primary sources of spread of global warming estimates from coupled Atmosphere-Ocean models[END_REF].

b. Response parameters and climate feedbacks

In classical climate feedback analyses, the Planck response parameter λ P is chosen as the no-feedback response. In the previous sections where atmosphere and ocean have not been considered, the Planck response was the first-order response of the outgoing radiative flux to the surface temperature. The Planck response was thus defined unambiguously as the no-feedback response. The choice of this no-feedback response is extended to the real climate and the Planck response is usually defined as the change in the net radiative flux at the tropopause, assuming that the temperature change is vertically uniform from the surface to the tropopause. This choice is arbitrary. It determines the expression and magnitude of the feedbacks, without changing the response of the whole system to a given forcing. Many other choices of the no-feedback parameter can be made. For instance [START_REF] Held | Using relative humidity as a state variable in climate feedback analysis[END_REF] suggest using a new reference response, where the humidity change required to maintain a fixed relative humidity is considered in addition to the classical troposphere and surface temperature change. The feedback gain, and more generally the analysis of any feedback loop, is not an intrinsic property of the system but the result of how the response of the system has been decomposed into a no-feedback response (or open loop) and an additional response due to feedbacks (i.e. due to closing the loop), and this choice is arbitrary [START_REF] Ingram | A very simple model for the water vapour feedback on climate change[END_REF][START_REF] Held | Using relative humidity as a state variable in climate feedback analysis[END_REF][START_REF] Lahellec | A formal analysis of the feedback concept in climate models, part I: exclusive and inclusive feedback analyses[END_REF]. However, the system will always become unstable when g becomes close to 1, assuming that the initial perturbation with no feedback is stable.

In classical climate feedback analysis:

λ = λ P + λ f λ f = λ w + λ L + λ c + λ α ( 14
)
which are respectively the water vapor (w), the temperature lapse rate (L), the cloud (c) and the surface albedo (α) response parameters.

These feedbacks have been analyzed in many studies (e.g. [START_REF] Hansen | Climate sensitivity: Analysis of feedback mechanisms[END_REF][START_REF] Soden | An assessment of climate feedbacks in coupled ocean atmosphere models[END_REF][START_REF] Bony | How well do we understand and evaluate climate change feedback processes?[END_REF][START_REF] Bates | Some considerations of the concept of climate feedback[END_REF][START_REF] Soden | Quantifying climate feedbacks using radiative kernels[END_REF][START_REF] Boucher | Clouds and aerosols. Climate Change 2013: The Physical Scientific Basis. Contribution of Working Group I to the Fifth Assessment Report of the Intergovernmental Panel on Climate Change[END_REF] and are briefly presented here:

• Water vapor feedback (w) and lapse rate feedback (L): The water vapor amount in the atmosphere increases with temperature, leading to an increased absorption of longwave (and shortwave to a lesser extent) radiation and to a decrease of the outgoing flux at the tropopause. The water vapor feedback is thus positive (λ w > 0). The temperature in the upper troposphere increases more than the surface temperature in the tropical regions and over most of the globe, which increases the radiation emitted by the upper troposphere to space and contributes to cool the climate. The lapse rate feedback is negative (λ L < 0). These two feedbacks are closely linked, particularly in the upper troposphere, owing to the dependence of moist adiabats on temperature in the tropics. They are strongly anti-correlated and it is relevant to consider their sum [START_REF] Soden | An assessment of climate feedbacks in coupled ocean atmosphere models[END_REF]. [START_REF] Held | Using relative humidity as a state variable in climate feedback analysis[END_REF] have suggested computing the temperature and the temperature lapse rate feedbacks together at fixed relative humidity, with an additional separate relative humidity feedback term

• Surface albedo feedback (α): As detailed in section 3-a, the surface albedo feedback is positive (λ α > 0).

• Cloud feedback (c): A change of cloud fraction has an effect on radiation, which is generally opposite in shortwave and longwave domains. On the one hand, a smaller cloud fraction increases the incoming solar radiation and thus warms the surface. On the other hand, it increases the outgoing longwave radiation and thus cools the surface. On average, models simulate, with a large spread, a decrease of the cloud radiative effect and an increase of incoming radiative flux due to the cloud response (λ c > 0) when the surface temperature increases [START_REF] Soden | An assessment of climate feedbacks in coupled ocean atmosphere models[END_REF][START_REF] Boucher | Clouds and aerosols. Climate Change 2013: The Physical Scientific Basis. Contribution of Working Group I to the Fifth Assessment Report of the Intergovernmental Panel on Climate Change[END_REF][START_REF] Zelinka | Contributions of different cloud types to feedbacks and rapid adjustments in CMIP5[END_REF][START_REF] Vial | On the interpretation of inter-model spread in CMIP5 climate sensitivity estimates[END_REF] c. Contribution of individual feedbacks to the climate response

The definition of the individual contribution of each feedback to the total response (λ ) of the climate to a given forcing (∆Q) is challenging. The individual contribution of a feedback is not simply given by the difference between the responses and without this feedback. Indeed, if this addition is performed it is found the sum does not equal the total response. The individual response of a feedback x has been shown [START_REF] Dufresne | An assessment of the primary sources of spread of global warming estimates from coupled Atmosphere-Ocean models[END_REF][START_REF] Lu | A new framework for isolating individual feedback processes in coupled general circulation climate models. Part I: formulation[END_REF][START_REF] Lahellec | A formal analysis of the feedback concept in climate models, part I: exclusive and inclusive feedback analyses[END_REF]) to be usefully defined as:

∆T x = g x 1 -g ∆T P (15)
g x = - λ x λ P (16)
Given this definition, the response of all feedbacks together is the sum of the individual responses of each feedback (∆T f = ∑ x ∆T x ) and the total feedback gain is the sum of the individual feedback gains (g = ∑ x g x ).

Figure 5a illustrates how the surface warming in response to a doubling of the atmospheric CO 2 concentration can be decomposed into a Planck response and additional responses due to the three following feedbacks: water vapor plus lapse rate, surface albedo and clouds. The results are those obtained with 12 CMIP3 models and have been published by [START_REF] Dufresne | An assessment of the primary sources of spread of global warming estimates from coupled Atmosphere-Ocean models[END_REF]. The Planck response is about 1.2 • C and the total response is 3.1 • C. Climate feedbacks account for two-thirds of the total surface temperature variation. According to model averages, the water vapor plus lapse rate feedback increase the temperature by 0.9 • C. The cloud feedback increases it by 0.7 • C. The surface albedo feedback has the smallest contribution with 0.3 • C.

The ratio between the response of feedback x and the total response does not depend on the other feedbacks. It only depends on the no-feedback response parameter as shown by combining equations 13 and 15:

∆T x ∆T = g x . (17)
For the water vapor plus lapse rate feedback, this ratio is 0.3 (Fig. 5b). This feedback contributes to 30% of the global mean temperature response regardless of the other feedbacks. The clouds contribute to 22% and the surface albedo to 8% of the total climate response. Note that for scenarios where the amplitude of the forcing smoothly increases in time, the ocean heat uptake can be included, with some assumptions, in the same equilibrium feedback framework as the one presented here [START_REF] Dufresne | An assessment of the primary sources of spread of global warming estimates from coupled Atmosphere-Ocean models[END_REF].

Summary and discussion

An experimental device based on very simple mechanical phenomena has been presented. It illustrated the fact that a system can be stable even if it includes a positive feedback. When describing the processes leading to a positive feedback, the other processes, in particular those ensuring the stability of the whole system, can sometimes be omitted giving the false impression that the positive feedback will never stop and will necessary leads to a runaway regime. In the experimental device, the stability comes from the moment of force of the counterweight. Suppressing it (say by reducing or removing the counterweight) makes the system unstable. In the climate system, the stability comes from the increase of radiative emission with temperature (Planck law). The climate system is currently stable as long as the amplitude of the forcing is not too large.

The classical feedback analysis framework is valid only when the response of the system is linear (i.e. proportional to the forcing, see Eq. 4). The device may also be used to illustrate some non linearities. When the amount of water in the two containers is low, the positive feedback can saturate and become non-existent for larger tilt amplitudes. On Earth, the magnitude of the snow albedo feedback decreases in a warmer climate as the snow cover decreases. When the containers are narrower at their center than at their extremities, the magnitude of the positive feedback may increase when the amplitude of the perturbation increases. This possibly leads to instability. The snow ball Earth and the runaway greenhouse effect on Venus are example of such possible instabilities.

A feedback is not an intrinsic property of a system but rather the result of how the system has been decomposed into a no-feedback response (or open loop response) and a response with feedbacks (or closed-loop response). This decomposition is driven by our understanding of the system and by the issues to be addressed. For the climate system, the response to a forcing is commonly split into 5 response parameters, each of them being associated to variables that directly influence the radiative flux at the top of the atmosphere. These response parameters can be used to estimate the no-feedback response, the feedback gain and the individual contribution of each feedback to the total response. The Planck law is often used to define the no-feedback response. The contribution of feedbacks depends on all feedbacks but the ratio between the individual contribution and the total response has been shown not to depend on the other feedbacks, even though it depends on the no-feedback response parameter. This is therefore an interesting and useful way of quantifying the individual contribution of the feedbacks. It is noteworthy that this individual contribution of the feedbacks cannot be simply defined as the difference between the responses with and without the feedback.

Climate is a complex system and understanding how it changes in response to some forcing is a major challenge. Part of the difficulty originates from the strong interactions between the many processes that exist in the climate system. The feedback analysis is a useful framework as it allows to quantify how the different parts of the climate system contribute to its global response. We hope the experiment proposed in this article help understanding the feedback analysis framework, the interplay of the different parts of coupled systems and the fact that positive feedbacks do not necessarily lead to runaway effects. As long as the additional mass is not too heavy, the water remains in the narrow part of the containers and the feedback gain is small, as illustrated by the small tilt difference between (a) and (b). When the additional mass is large enough, the water reaches the wide part of the containers and the feedback gain becomes large as illustrated by the large tilt difference between (c) and (d).

Positive feedback in climate: stabilization or runaway, illustrated by a simple experiment. c)) and the tilt that would be if the additional tilt increase when opening the second tap was identical to the additional tilt increase when opening the first tap (blue line). The difference between the blue line and the actual tilt illustrate that the tilt increase due to two feedbacks is more than two times the tilt increase due to one feedback.

  FIG. 4. Three steps in understanding the feedback analysis formalization: (a) considering the change of T in direct response to the perturbation of F, (b) introducing a feedback loop, and (c) introducing a feedback gain. Blue fonts indicate the response parameters.

FIG. 1 .

 1 FIG. 5. For a CO 2 doubling, (a) equilibrium temperature change (∆T ) and contributions to this temperature change due to the Planck response, combined water vapor and lapse-rate (WV + LR) feedback, surface albedo feedback, and cloud feedback; (b) relative contribution of each feedback to the equilibrium temperature change ∆T reported in (a). The multi-model mean and the +/-1 standard deviation for 12 CMIP3 models are shown, using results of[START_REF] Dufresne | An assessment of the primary sources of spread of global warming estimates from coupled Atmosphere-Ocean models[END_REF]

FIG. 2 .

 2 FIG.2. Schematic of the experimental device and its three states in the stable linear case: (a) initial state, (b) perturbed state with closed tap describing the direct response to an external perturbation, and (c) perturbed state with opened tap describing the response with feedbacks. Unlike the actual device (Fig.1), the containers remain vertical to facilitate the mathematical formulation.

  FIG.3. Modified experimental device shown in Fig.1where the two containers are narrower at their center than at their extremities, to illustrate a tipping point. The additional mass is larger in (c,d) than in (a,b). The tap are closed in (a, c) and open in (b, d). As long as the additional mass is not too heavy, the water remains in the narrow part of the containers and the feedback gain is small, as illustrated by the small tilt difference between (a) and (b). When the additional mass is large enough, the water reaches the wide part of the containers and the feedback gain becomes large as illustrated by the large tilt difference between (c) and (d).

Figures

  Figures

Acknowledgments. This work was partly supported by the French "Agence Nationale de la Recherche" Clima-Conf project (grant #ANR-10-CEPL-0003). MSL was funded by the "Cimate-KIC". We thank the anonymous reviewers for their many valuable suggestions and Audine Laurian for editing the English.

Supplementary material

APPENDIX A

Mathematical model of the experiment

A simple model of the device is now presented to better understand and describe the behavior of the experiment. Each cylindrical water container is initially of mass m 2 . The "horizontal bar moment" is M H , and the "return moment" is M R . Other definitions are given in the text.

At equilibrium, the sum of the moments of force is null: M H + M R = 0. Initially, as the system is vertically straight, the moments are nulls. Given the definition of the moment of force, if the device is tilted by ∆θ compared to this initial state, the corresponding change in the vertical bar moment is ∆M R = -g grav l 3 m 3 sin(∆θ ), where g grav is the gravitational acceleration (absolute value). Considering that ∆θ is relatively small, this simplifies to ∆M R ≈ -g grav l 3 m 3 ∆θ . Therefore, at equilibrium, the tilt change ∆θ in response to any change ∆M H of the horizontal bar moment reads:

a. No-feedback response to an external perturbation Adding a mass m 1 to one extremity of the horizontal bar makes the device tilt by ∆θ i (i for initial) (Fig. 4b) and adds the moments ∆M H i = g grav l 1 m 1 cos(∆θ i ), which simplifies to ∆M H i = g grav l 1 m 1 when considering ∆θ small:

The next step consists in opening the tap between the two containers, allowing the positive feedback process between tilt and moment (Fig. 4c). The total variation ∆M H of the horizontal bar moment is given by:

where ∆M i H is the initial perturbation and ∆M H f = g grav l 2 ∆m (subscript f for feedback) is the amplification due the mass ∆m of water which has passed from the upper container to the lower one (with ∆θ small so that cos(∆θ ) ≈ 1). This mass variation is given by the difference Z = l 2 sin(∆θ ) ≈ l 2 ∆θ between the height of the two containers:

with ρ the water density, S the cross section of the containers. It follows:

The variable M H is thus a function of θ (Eq. A5) and θ is a function of M H (Eq. A1). Combining Eqs. A1, A2 and A5, it follows:

where g is the feedback gain and k is the feedback amplification factor. To further understand the meaning of the gain g, it is worth noting that Eq.A6 can also be written ∆θ = ∆θ i + g∆θ , with ∆θ i the no-feedback response and g∆θ the additional response due to feedbacks.

APPENDIX B

Mathematical model of the albedo feedback

The solar flux F absorbed by the surface is

where I is a quarter of the solar constant and α the albedo. At equilibrium, the flux absorbed by the surface is equal to that emitted by the surface and the surface temperature is given by T = (F/σ ) 1/4 assuming an emissivity of 1, where σ is the Stefan-Boltzmann constant. For small variations, this equation may be linearized and the temperature varies with the absorbed solar flux as follows:

As a comparison with the experiment, T is the analog of the tilt θ of the device, F is the analog of the moment of force M H , and Eq. B2 is the analog of Eq. A1.

a. No-feedback response to an external perturbation

The absorbed solar flux is assumed to be perturbed by ∆Q (positive or negative) by some external process. In response to this perturbation, the surface temperature directly increases or decreases by ∆T i according to Eq. B2:

This perturbation corresponds to adding the mass m 1 and keeping the tap closed in the experiment and Eq. B4 is an analog to Eq.A2.

b. Response with feedback

The resulting variation ∆F of the absorbed solar flux can be decomposed into a first part due the external perturbation ∆Q and a second part due to the albedo feedback amplification ∆F α :

∆F α depends on the surface albedo variation (Eq. B1) and may be expressed as a function of the surface temperature ∆T as:

where λ α > 0 as the albedo α decreases when the surface temperature increases. Combining Eq.B2 and Eqs.B4 to B6, it follows:

The feedback is positive as λ α > 0 and therefore g α > 0. Equation B8 is an analog to Eq.A6 and Eq. B9 is an analog to Eq.A7.

APPENDIX C

Experiment where the gain is doubled

Experimental device with two identical pairs of containers that communicate through two independent pipes. The two taps can be opened one after the other to observe that the tilt increase due to two feedbacks is more than two times the tilt increase due to one feedback.


domain: info math

text:
A simple algorithm for computing Nash-equilibria in

We present a simple projection-free primal-dual algorithm for computing approximate Nash-equilibria in two-person zero-sum sequential games with incomplete information and perfect recall (like Texas Hold'em Poker). Our algorithm is numerically stable, performs only basic iterations (i.e matvec multiplications, clipping, etc., and no calls to external first-order oracles, no matrix inversions, etc.), and is applicable to a broad class of two-person zero-sum games including simultaneous games and sequential games with incomplete information and perfect recall. The applicability to the latter kind of games is thanks to the sequence-form representation which allows one to encode such a game as a matrix game with convex polytopial strategy profiles. We prove that the number of iterations needed to produce a Nashequilibrium with a given precision is inversely proportional to the precision. We present experimental results on matrix games on simplexes and Kuhn Poker.

Introduction

The sequence-form representation for two-person zero-sum games with incomplete information was introduced in [START_REF] Koller | The complexity of two-person zero-sum games in extensive form[END_REF], and the theory was further developed in [START_REF] Koller | Fast algorithms for finding randomized strategies in game trees[END_REF][START_REF] Stengel | Efficient computation of behavior strategies[END_REF][START_REF] Stengel | Equilibrium Computation for Two-player Games in Strategic and Extensive Form[END_REF] where it was established that for such games, there exist sparse matrices A ∈ R n1×n2 , E 1 ∈ R l1×n1 , E 2 ∈ R l2×n2 , and vectors e 1 ∈ R l1 , e 2 ∈ R l2 such that n 1 , n 2 , l 1 , and l 2 are all linear in the size of the game tree (number of states in the game) and such that Nash-equilibria correspond to pairs (x, y) of realization plans which solve the primal LCP (Linear Convex Program) minimize (y,p)∈R n 2 ×R l 1 e T 1 p, subject to: y ≥ 0, E 2 y = e 2 , -Ay

+ E T 1 p ≥ 0, (1)
and the dual LCP maximize (x,q)∈R n 1 ×R l 2 -e T 2 q, subject to:

x ≥ 0, E 1 x = e 1 , A T x + E T 2 q ≥ 0. (2)
The vectors p = (p 0 , p 1 , . . . , p l2-1 ) ∈ R l2 and q = (q 0 , q 1 , . . . , q l1-1 ) ∈ R l1 are dual variables. A is the payoff matrix and each E k is a matrix whose entries are -1, 0 or 1, with exactly 1 entry per row which equals -1 except for the first whose whose first entry is 1 and all the others are 0. Each of the vectors e k is of the form (1, 0, . . . , 0) ∈ R l k .

The LCPs above have the equivalent saddle-point formulation minimize

y∈Q2 maximize x∈Q1 x T Ay, (3)
where the compact convex polytope

Q k := {z ∈ R n k |z ≥ 0, E k z = e k } ⊆ [0, 1]
n k is identified with the strategy profile of player k in the sequence-form representation [START_REF] Koller | The complexity of two-person zero-sum games in extensive form[END_REF][START_REF] Koller | Fast algorithms for finding randomized strategies in game trees[END_REF][START_REF] Stengel | Efficient computation of behavior strategies[END_REF][START_REF] Stengel | Equilibrium Computation for Two-player Games in Strategic and Extensive Form[END_REF]. As a special case, the above formulation matrix games with complete information in which the strategy profiles are simplexes. Now, at a feasible point (y, p, x, q) for the LCPs, the duality gap G(y, p, x, q) is given by G(y, p, x, q

) := e T 1 p -(-e T 2 q) = p 0 + q 0 = max{u T Ay -x T Av|(u, v) ∈ Q 1 × Q 2 } =: G(x, y) ≥ 0. ( 4
)
29th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain.

In (4), the quantity G(x, y) is nothing but the primal-dual gap for the equivalent saddle-point problem [START_REF] Chambolle | On the ergodic convergence rates of a first-order primal-dual algorithm[END_REF]. It was shown (see Theorem 3.14 of [START_REF] Stengel | Equilibrium Computation for Two-player Games in Strategic and Extensive Form[END_REF]) that a pair (x, y) ∈ Q 1 × Q 2 of realization plans is a solution to the LCPs (1) and (2) (i.e is a Nash-equilibrium for the game) if and only if there exist vectors p and q such that

-Ay + E T 1 p ≥ 0, A T x + E T 2 q ≥ 0, x T (-Ay + E T 1 p) = 0, y T (A T x + E T 2 q) = 0. (5)
Moreover, at equilibria strong duality holds and G(y, p, x, q) = G(x, y) = 0.

Definition 1 (Nash -equilibria). Given > 0, a Nash -equilibrium is a pair (x * , y * ) of realization plans for which there exists dual vectors p * and q * for problems (1) and (2) such that the duality gap at (y * , p * , x * , q * ) does not exceed . That is, 0 ≤ G(y * , p * , x * , q * ) ≤ .

Quick sketch of our contribution. It should be noted that the class of games considered here (sequential games with incomplete information), the LCPs (1) and ( 2) are exceedingly larger than what state-of-the-art LCP and interior-point solvers can handle (see [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF][START_REF] Gilpin | First-order algorithm with O(ln(1/ )) convergence for -equilibrium in two-person zero-sum games[END_REF]). Developing on an alternative notion of approximate equilibria (see Definition 2) homologous to that presented in Definition 1, we device in section 3 a simple numerically stable primal-dual algorithm Alg. 1 for computing approximate Nash-equilibria in sequential two-person zero-sum games with incomplete information and perfect recall. On each iteration, the only operations performed by our algorithm are of the form A T x, Ay, E T 1 p, E T 2 q, and (x) + := (max(0, x j )) j . We also prove (Theorem 1) that -in an ergodic / Cesàrio sense-the number of iterations required by the algorithm to produce an approximation equilibrium to a precision is O(1/ ), with explicit values for the constants involved.

Related work

In [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF], a nested iterative procedure using the Excessive Gap Technique (EGT) [START_REF] Nesterov | Excessive gap technique in nonsmooth convex minimization[END_REF] was used to solve the equilibrium problem [START_REF] Chambolle | On the ergodic convergence rates of a first-order primal-dual algorithm[END_REF]. The authors reported a O(1/ ) convergence rate (which derives from the general EGT theory) for the outer-most iteration loop. [START_REF] Gilpin | First-order algorithm with O(ln(1/ )) convergence for -equilibrium in two-person zero-sum games[END_REF] proposed a modified version of the techniques in [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF] and proved a O (( A /δ) log (1/ )) convergence rate in terms of the number of calls made to a first-order oracle. Here δ = δ(A, E 1 , E 2 , e 1 , e 2 ) > 0 is a certain condition number for the game. The crux of their technique was to observe that (3) can further be written a the minimization of the duality gap function G(x, y) (defined in (4)) for the game1 , viz

minimize{G(x, y)|(x, y) ∈ Q 1 × Q 2 }, (6)
and then show there exists a scalar δ > 0 such that for any pair of realization plans (x, y)

∈ Q 1 × Q 2 ,
"distance between (x, y) and set of equilibria" ≤ G(x, y)/δ.

However, there are a number of issues, most notably: (a) The constant δ > 0 can be arbitrarily small, and so the factor A /δ in the O (( A /δ) log (1/ )) convergence rate can be arbitrarily large for ill-conditioned games. (b) The reported linear convergence rate is not in terms of basic operations (addition, multiplication, matvec, clipping, etc.), but in terms of the number of calls to a first-order oracle. Most notably, projections onto the polytopes Q k are computed on each iteration.

Recently, [START_REF] Kroer | Faster First-Order Methods for Extensive-Form Game Solving[END_REF] proposed accelerations to first-order methods for computing Nash-equilibria (including those just discussed), by an appropriate choice of the underlying Bregman distance and the distance generating function (essential ingredients in EGT-type algorithms). These modifications provably gain a constant factor in the worst-case convergence rate over the original algorithm.

Generalized Saddle-point Problem (GSP) for Nash-equilibrium

In the next theorem, we show that the LCPs (1) and ( 2) can be conveniently written as a GSP in the sense of [START_REF] He | Accelerating block-decomposition first-order methods for solving generalized saddle-point and Nash equilibrium problems[END_REF]. The crux of idea is to "dualize" the linear constraints in the definitions of the strategy polytopes Q k , by augmenting the payoff matrix to yield an equivalent saddle-point problem, involving only very simple functions like ReLUs and matvecs. We elaborate this construction in the following theorem, whose proof is provided in Appendix A.

Theorem 1. Define two proper closed convex functions

g 1 : R n2 × R l1 → (-∞, +∞], g 1 (y, p) := i y≥0 + e T 1 p g 2 : R n1 × R l2 → (-∞, +∞], g 2 (x, q) := i x≥0 + e T 2 q Also define two bilinear forms Ψ 1 , Ψ 2 : R n2 × R l1 × R n1 × R l2 → R by letting K := A -E T 1 E 2 0 , Ψ 1 (y, p, x, q) := x q T K y p ,
with Ψ 2 = -Ψ 1 , and define the functions Ψ1 , Ψ2 : ∞, +∞] by Ψ1 (y, p, x, q) := Ψ 1 (y, p, x, q) + g 1 (y, p) if y ≥ 0, Ψ1 (y, p, x, q) = ∞ otherwise, Ψ2 (y, p, x, q) := Ψ 2 (y, p, x, q) + g 2 (x, q) if x ≥ 0, Ψ2 (y, p, x, q) = ∞ otherwise.

R n2 × R l1 × R n1 × R l2 → (-
Finally, define the sets

S 1 := R n2 + × R l1 and S 2 := R n1 + × R l2
, and consider the GSP(Ψ 1 , Ψ 2 , g 1 , g 2 ): Find a quadruplet (y * , p * , x * , q * ) ∈ S 1 × S 2 s.t ∀(y, p, x, q) ∈ S 1 × S 2 , we have Ψ1 (y * , p * , x * , q * ) ≤ Ψ1 (y, p, x * , q * ), and Ψ2 (y * , p * , x * , q * ) ≤ Ψ2 (y * , p * , x, q). (

) 7
Then GSP(Ψ 1 , Ψ 2 , g 1 , g 2 ) is equivalent to the LCPs (1) and (2), i.e a quadruplet (y

* , p * , x * , q * ) ∈ R n2 × R l1 × R n1 × R l2 solves the LCPs (1) and (2) iff it solves GSP(Ψ 1 , Ψ 2 , g 1 , g 2 ).

The Algorithm

By Theorem 1, solving for a Nash-equilibrium for the game is equivalent to solving the GSP [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF], which as it turns out, is simpler conceptually: e.g, we no longer need to compute the complicated orthogonal projections proj Q k .

Definition 2 (Nash ( 1 , 2 )-equilibria [START_REF] He | Accelerating block-decomposition first-order methods for solving generalized saddle-point and Nash equilibrium problems[END_REF]). Given tolerance levels 1 , 2 > 0, a Nash ( 1 , 2 )equilibrium for the GSP (7) is any quadruplet (y * , p * , x * , q * ) for which there exists a perturbation vector v * such that v * ≤ 1 and v * ∈ ∂ 2 [ Ψ1 (., ., x * , q * ) + Ψ2 (y * , p * , ., .)](y * , p * , x * , q * ), where

∂ (f ) : x → {v ∈ H|f (z) ≥ f (x) + v T (z -x)
-, ∀z ∈ H} denotes the -enlarged subdifferential of a function f . Such a vector v * above is called a Nash ( 1 , 2 )-residual at the point (y * , p * , x * , q * ).

The above definition is a generalization of the notion of Nash-equilibrium since: (a) exact Nashequilibria correspond to Nash (0, 0)-equilibria, and (b) Nash -equilibria (in the sense of Definition 1) correspond to Nash (0, )-equilibria. Putting things together and using results from [START_REF] He | Accelerating block-decomposition first-order methods for solving generalized saddle-point and Nash equilibrium problems[END_REF], we obtiain Alg. 1 below which solves [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF], and therefore the original LCPs (1) and ( 2).

Algorithm 1 Primal-dual algorithm for computing Nash ( , 0)-equilibria for ( 7)

Require: > 0; (y (0) , p (0) , x (0) , q (0) ) ∈ R n2 × R l1 × R n1 × R l2 .
Ensure: A Nash ( , 0)-equilibrium (y * , p * , x * , q * ) ∈ S 1 × S 2 for the GSP [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF], with precision > 0.

1: Initialize: v (0) ← 0, k ← 0, λ ← 1/ K (See Appendix B.) 2: while k = 0 or 1 kλ v (k) ≥ do 3: y (k+1) ← (y (k) -λ(A T x (k) + E T 2 q (k) )) + , p (k+1) ← p (k) -λ(e 1 -E 1 x (k) ) 4: x (k+1) ← (x (k) + λ(Ay (k+1) -E T 1 p (k+1) )) + , ∆x (k+1) ← x (k+1) -x (k)
5:

∆q (k+1) ← λ(E 2 y -e 2 ), q (k+1) ← q (k) + ∆q (k+1)
6: k+1) , ∆p (k+1) , ∆x (k+1) , ∆q (k+1) )

y (k+1) ← y (k+1) -λ(A T ∆x (k+1) + E T 2 ∆q (k+1) ), ∆y (k+1) ← y (k+1) -y (k) 7: p (k+1) ← p (k+1) + λE 1 ∆x (k+1) , ∆p (k+1) ← p (k+1) -p (k) 8: v (k+1) ← v (k) + (∆y (
9:

k ← k + 1 10: end while Theorem 2 (Ergodic / Cesàrio O(1/ ) convergence of Alg. 1). Let d 0 be the euclidean distance between the starting point (y (0) , p (0) , x (0) , q (0) ) of Algorithm 1 and the set of equilibria for the GSP [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF]. Then given any > 0, there exists an index k 0 ≤ 2d0 K such that after k 0 iterations the algorithm produces a quadruplet (y k0 , p k0 , x k0 , q k0 ) and a vector v k0 such that v k0 a ≤ and v k0 a ∈ ∂[ Ψ1 (., ., x k0 , q k0 ) + Ψ2 (y k0 , p k0 , ., .)](y k0 , p k0 , x k0 , q k0 ), where v (k0) a := 1 kλ v (k0) . Thus Algorithm 1 outputs a Nash ( , 0)-equilibrium for the GSP [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF] in at most 2d0 K iterations.

Numerical experiments and results

Experiments. (a) Basic test-bed: Matrix games on simplexes. As in [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF][START_REF] Chambolle | On the ergodic convergence rates of a first-order primal-dual algorithm[END_REF], we generate a 10 3 ×10 3 random matrix whose entries are uniformly identically distributed in the closed interval [-1, 1].

(b) Kuhn Poker, a "toy" incomplete-information sequential game. This game is a simplified form of Poker developed by Harold W. Kuhn in [START_REF] Kuhn | A simplified two-person poker[END_REF]. It already contains all the complexities (sequentiality, imperfection of information, etc.) of a full-blown Poker game like Texas Hold'em, but is simple enough to serve as a proof-of-concept for the ideas developed in this manuscript. The deck includes only three playing cards: a King, Queen, and Jack. One card is dealt to each player, then the first player must bet or pass, then the second player may bet or pass. If any player chooses to bet the opposing player must bet as well ("call") in order to stay in the round. After both players pass or bet, the player with the highest card wins the pot. Results. The results of the experiments are shown in Fig. 1. We stress that the algorithms of Nesterov [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF] and Gilpin [START_REF] Gilpin | First-order algorithm with O(ln(1/ )) convergence for -equilibrium in two-person zero-sum games[END_REF] are included in the plots only indicatively, since this is not meant to be a benchmark. These reference algorithms are easy to have been included where not profiled in the "Kuhn poker" experiment because they are rather difficult to implement mainly due to the the need to project onto the strategy polytopes Q k . One can see the linear (i.e exponentially fast) behavior of the algorithm in [START_REF] Gilpin | First-order algorithm with O(ln(1/ )) convergence for -equilibrium in two-person zero-sum games[END_REF], in-between consecutive breakpoints on the grid (though the rate of linear convergence seems to by quite close to 1 here). As expected, the firstorder smoothing algorithm labeled "Nesterov" [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF] jitters around as the iterations go on because even the smoothed problem becomes heavily ill-conditioned near solutions. On the other hand, for both experiments, our proposed algorithm Alg. 1 behaves empirically as its proven O(1/ ) convergence rate.

Concluding remarks

Making use of the sequence-form representation [START_REF] Koller | The complexity of two-person zero-sum games in extensive form[END_REF][START_REF] Stengel | Efficient computation of behavior strategies[END_REF][START_REF] Stengel | Equilibrium Computation for Two-player Games in Strategic and Extensive Form[END_REF], we have proposed an equivalent Generalized Saddle-Point (GSP) formulation to the Nash-equilibrium problem for sequential games with incomplete information and perfect recall (e.g Texas Hold'em, etc.). Then, we have devised a simple numerically stable primal-dual algorithm for solving the GSP, and so by equivalence, compute (approximate) Nash-equilibria for such games. Our algorithm is simple to implement, with a low constant cost per iteration, and enjoys a rigorous convergence theory with a proven O(1/ ) convergence in terms of basic operations (matvec products, clipping, etc.), to a Nash ( , 0)-equilibrium of the game. On an experimental footing, this is just preliminary works, and in future we plan to run more experiments on real Poker games to measure the practical power of the proposed algorithm compared to state-of-the-art methods like CFR and variants [START_REF] Zinkevich | Regret minimization in games with incomplete information[END_REF][START_REF] Lanctot | Monte Carlo sampling for regret minimization in extensive games[END_REF][START_REF] Bowling | Heads-up limit hold'em poker is solved[END_REF][START_REF] Tammelin | Solving Large Imperfect Information Games Using CFR+[END_REF], and first-order methods like [START_REF] Gilpin | First-order algorithm with O(ln(1/ )) convergence for -equilibrium in two-person zero-sum games[END_REF].

Game abstraction. For many variants of Poker, there has been extensive research in lossy / lossless abstraction techniques (for example [START_REF] Gilpin | Lossless Abstraction of Imperfect Information Games[END_REF] and more recently, [START_REF] Sandholm | Abstraction for solving large incomplete-information games[END_REF][START_REF] Brown | Hierarchical Abstraction, Distributed Equilibrium Computation, and Post-Processing, with Application to a Champion No-Limit Texas Hold'em Agent[END_REF]), wherein strategically equivalent or not-so-different situations in the game tree are lumped together. This can drastically reduce the size of the state space from a player's perspective, and ultimately, the size of the matrices A, E 1 , and E 2 , without significantly deviating much from the true game.

Figure 1 :

 1 Figure 1: Convergence curves of Algorithm 1.In the top plots, we show the modified duality gap defined in Theorem 2. In the top plots, we show the evolution of the value x (k) T Ay (k) of the games across iterations.

The minimizers of G are precisely the equilibria of the game.

A Proofs

Proof of Theorem 1. It suffices to show that at any point (y, p, x, q) ∈ S 1 × S 2 , the duality gap between the primal LCP (1) and the dual LCP (2) equals the duality gap of GSP(Ψ 1 , Ψ 2 , g 1 , g 2 ). Indeed, the unconstrained objective in [START_REF] Bowling | Heads-up limit hold'em poker is solved[END_REF], say a(x, y), can be computed as

= g 1 (y, p) + max

x ,q

x T Ay -x T E T 1 p + q T E 2 y(i x ≥0 + e T 2 q)

= g 1 (y, p)min

x ,q Ψ 2 (y, p, x , q ) + g 2 (x , q ) = g 1 (y, p)min x ,q Ψ2 (y, p, x , q ) φ2(y,p)

= g 1 (y, p) -φ 2 (y, p).

Similarly, the unconstrained objective, say b(x, q), in the dual LCP (2) writes

Thus, noting that -∞ < φ 1 (x, q), φ 2 (y, p) < +∞ (so that all the operations below are valid), one computes the duality gap between the primal LCP (1) and dual the LCP (2) at (y, p, x, q) as a(y, p) -b(x, q) = g 1 (y, p) -φ 2 (y, p) + g 2 (x, q) -φ 1 (x, q) = Ψ 1 (y, p, x, q) + g 1 (y, p) -φ 2 (y, p) + Ψ 2 (y, p, x, q) + g 2 (x, q) -φ 1 (x, q) = Ψ1 (y, p, x, q) -φ 1 (x, q) + Ψ2 (y, p, x, q) -φ 2 (y, p) = duality gap of GSP(Ψ 1 , Ψ 2 , g 1 , g 2 ) at (y, p, x, q), where the second equality follows from Ψ 1 + Ψ 2 := 0. ). With all these ingredients in place, Algorithm 1 is then obtained from Algorithm T-BD of [START_REF] He | Accelerating block-decomposition first-order methods for solving generalized saddle-point and Nash equilibrium problems[END_REF] applied on the GSP [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF] with the choice of parameters:

Proof of

B Practical considerations

Computing K . A major ingredient in the proposed algorithm is K , the 2-norm of the huge matrix K. This can be efficiently computed using the power iteration. Also since K is only used in defining the step-size λ := 1/ K , it may be possible to avoid computing K altogether, and instead use a line-search / backtrack strategy (see [START_REF] O'donoghue | Adaptive restart for accelerated gradient schemes[END_REF], e.g) for setting λ.

Efficient computation of matvec products

Ay and A T x. In Alg. 1, most of the time is spent pre-multiplying vectors by A and A T . For flop-type Poker games like Texas Hold'em and Rhode Island Hold'em, A (and thus A T too) is very big (up 10 14 rows and columns!) but is sparse and has a rich block-diagonal structure (each block is itself the Kronecker product of smaller matrices) which can be carefully exploited, as in [START_REF] Hoda | Smoothing techniques for computing Nash equilibria of sequential games[END_REF]. Also the sampling strategies presented in the recent work [START_REF] Kroer | Faster First-Order Methods for Extensive-Form Game Solving[END_REF] (section 6), for generating unbiased estimates of Ay and A T x would readily convert Algorithm 1 into an online and much scalable solver.