where e is the void ratio, C c is the compression index and the subscript 0 and 1 denote two arbitrary states.

Actually, even in the basic case of a composite made of saturated clay and rigid sand grains, such a non-linear physics including volume variations as an essential feature leads to homogenization problems of high theoretical and numerical complexity. For this reason, simplifying physically based assumptions are of interest to make the up-scaling problem manageable, while catching the key mechanisms at the local scale.

This study aims at clarifying this question by a twofold approach that consists in, [START_REF] Kacprzak | Etude du comportement mécanique des mélanges sable/argile[END_REF]):

• first, to produce and analyze experimental data in order to identify the key mechanisms of compaction hardening at the inter-granular scale and to derive reasonable assumptions in view of homogenization. For the sake of simplicity, only unidirectional experiments have been performed. Moreover, as linear homogenization is well established, experiments involving both linear (viscous flow) and nonlinear phenomena (consolidation hardening) will be conducted in order to point out the specificity induced by the non-linearity.

• second, to identify up to which extent some usual homogenization processes are able to describe reasonably the mixture behaviour, and, using experiments for comparison, to point out their main limitations.

The paper is divided into four sections. First, the basic principles taken in consideration to develop this study are given. Then, the fabrication procedure of the saturated sand-clay mixtures and the testing program of oedometric and permeability measurements are described.

The third section is focused on the experimental results and their physical interpretations. Finally, by using classical and tangent homogenization approaches in association with simplifying assumptions, basic modelling of the mixture permeability and non-linear oedometric compressibility are presented and discussed.

GUIDELINES OF THE STUDY

This study is devoted to saturated mixtures made of the three following constituents:

• Hostun's sand grains (G), having a density ρ g equal to 2650 kg/m 3 , and quasi-uniform size distribution with a D 50 close to 0.5 mm. The minimum and maximum void ratio of this sand are respectively of e min = 0.65; e max = 1.04.

• Kaolin (C), having a density ρ c equal to 2650 kg/ m 3 and typical size of platelets equal to 5μm. The water content at the liquid and plastic limits is equal to w L = 0.51 and w P = 0.24, respectively.

• Water (W) having a density ρ w equal to 1000 kg/ m 3 . Note that the use of kaolin avoids or greatly minimizes any phenomena of swelling induced by water, whatever is its ionic concentration.

The mixtures are macroscopically homogeneous, and the characteristic size of their Representative Elementary Volume (REV) is much smaller than the size of the samples tested for this study.

TRIANGULAR REPRESENTATION OF SATURATED MIXTURES

For saturated mixtures, the volume ratio of grains G, clay platelets C, and water W , defined by:

C = V C V C + V G + V W ; G = V G V C + V G + V W ; W = V W V C + V G + V W , (2)
are related by:

C + G + W = 1, (3)
and the water volume ratio W is the usual porosity n.

Conveniently, any mixture may by represented by a point M in an equilateral triangle {C, G, W} whose summits C, G, W correspond respectively to C = 1, G = 1, W = 1, and the opposite basis, e.g. GW, corresponds to C = 0, (and CW to G = 0; CG to W = 0). The three volume ratios of the mixture represented by M are provided by the three orthogonal projections of M on the three altitudes (Fig. 1 on the left).

The clay content ratio R c that determines the grains size distribution of the mixture (either in terms of mass or volume, since the grains and platelets specific gravities are identical) is defined by:

R c = C C + G (4)
Graphically, R c is obtained by the intersection of the line WM with the base CG. (Fig. 1 right). Note that all mixtures located on the line WM have the same clay content ratio, i.e., the same constitution of solid particles (and, therefore, same grain size distribution). For this reason, during its oedometric consolidation, a mixture necessarily evolves on the line WM.

The void ratio e of the saturated mixture is given by:

e = W C + G = W 1 -W . ( 5
)
It is obtained in the triangular graph -with a non-linear scale -by the projection of M on the altitude issued from the vertex W, perpendicular to CG. Thus, all mixtures located on a line parallel to CG have an identical void ratio e, or also the same porosity n = W .

The two control parameters e c and e g

Because of the great difference of size between sand grains and kaolin platelets, such mixtures can be considered as bi-composite materials made of sand grains embedded in a matrix of saturated clay paste (i.e., kaolin and water). These two components present highly contrasted properties, since the grains are rigid and impervious while the clay paste is deformable and permeable.

The mechanical properties of the clay paste strongly depend of its water content w c . The behaviour ranges from that of a quasi-liquid suspension for w c > w L (undrained shear strength c u typically less than 2 kPa, [START_REF] Wood | Soil behaviour and critical state soil mechanics[END_REF])) to that of a plastic paste for w L > w c > w P (undrained shear strength typically comprised between 2 and 200 kPa), and reaches a solid behaviour for w c < w P (c u typically higher than 200 kPa). When the shrinking limit w S < w P is reached, the arrangement of the clay platelets cannot adapt anymore to the weak amount of water and the saturation is no more possible. In this state, the behaviour of the material is progressively affected by other mechanism such as suction by desaturation, and cracks start to develop.

The density of the mixture obeys moreover to restrictions imposed by the sand skeleton. Sand grain arrangement in the mixture cannot be denser than the densest arrangement of pure sand alone (R c = 0), but oppositely, can be looser than the loosest arrangement of pure sand. Then, considering the paste to grain volume ratio, e g = (C + W )/G, [START_REF] Mitchell | Fundamentals of soil behaviour[END_REF]):

• necessarily e g > e min ;

• when e max > e g > e min , one may infer that the grains are in contact and constitute a skeleton;

• the larger the grain volume ratio e g (> e max ), the lower the contacts among grains will be. As a consequence, grains do not build a skeleton and the mixture turns to a clay paste matrix embedding dispersed grains.

These observations lead to the use of the two volumetric control parameters e c and e g for specifying the mechanical behaviour of the mixtures:

• the clay paste void ratio defined by:

e c = W C , (6)
is related to the water content of the paste (defined in terms of mass ratio) by e c = (ρ c /ρ w )w c = 2.65w c . In the triangular graph, e c is obtainedwith a non-linear scale -by the intersection of the line GM with the base CW (Fig. 1 on the right).

Note that all mixtures located on the line GM have the same clay void ratio, i.e., the same clay behaviour at the initial state.

• the granular "void" ratio related to the concentration in grains. By analogy with pure sand, the granular void ratio is the ratio of the volume in-between sand grains divided by the volume of grains in a unit volume of mixture. Its expression is:

e g = C + W G = 1 -G G . (7)
As e g is a function of G, its representation in the triangular graph lies on the same axis than G (i.e., the projection of M on the line perpendicular to the base CW, Fig. 1 on the right), but with a nonlinear scale (Fig. 1 on the left). Consequently, all the mixtures located on a line parallel to CW have identical granular void ratio.

MIXTURE COMPOSITION AND MECHANICAL BEHAVIOUR

By crossing the features of sand (e min , e max ) and of clay paste (w L , w P , w S ), one may define different morphologies of the mixtures (Fig. 2). Three regions are defined by the two lines parallel to CW corresponding to e g = e min and e g = e max . Mixtures of e g < e min are impossible to happen, between the lines e g = e min and e g = e max they present a granular skeleton, and between e g = e max and CW, their morphology turns progressively to dispersed grains into a clayed matrix.

The lines GL, GP, GS corresponding to w c = w L , w P , w S define four sectors. In between GW and GL, the clay paste behaves as a quasi-liquid suspension; in between GL and GP, the clay paste behaves as a plastic paste; in between GP and GS, the clay paste is solid. Finally, in between GS and GC, it is impossible to saturate the clay and therefore, the mixture. The shaded regions in Figure 2 below e min and w S indicate the impossible states of saturated sand-clay mixtures.

From this representation it is clear that, by modifying the amount of water, mixtures made of the same sandy clay material may range from a quasi-liquid suspension of clay with dispersed sand grains (that may even be unstable because of the sand grains sedimentation) to a sand skeleton surrounded by a plastic paste. Similarly, at the same porosity (or void ratio), by changing the sand content, the mixture may vary from a clayed sand made of a solid clay matrix embedding sand grains, to a sandy clay having a grain skeleton surrounded by a plastic paste.

These two examples show that, when varying independently the usual soil mechanics parameters e (or W ) and R c , both clay water content and sand content are modified. Thus, the links between the behaviour of the constituents and the one of the mixture would be difficult to identify. For this reason, in this study, the mixtures have been created in view of controlling the paste behaviour -by w c or e c -and the sand content, by e g .

TESTED MIXTURES AND EXPERIMENTS

More than twenty mixtures have been done [START_REF] Kacprzak | Etude du comportement mécanique des mélanges sable/argile[END_REF]. Three initial water contents (w ci ) were selected to study mixtures made of paste either at the liquid limit (w ci = w L = 0.51; c u ≈ 2k Pa), at an intermediate water content (w ci = 0.35; c u ≈ 31k Pa), and close to the plastic limit (w ci = 0.30 > w P = 0.24; c u ≈ 73k Pa), Figure 3. The grain size distribution of the tested mixtures is shown in Figure 4. Values of e g close to e g ≈ 1 ≈ e max , 1.5, 2, 3, 4, 6 and ∞ (no sand) have been chosen to investigate mixtures where grains may be in contact or are dispersed in the paste in a "dense" or more diluted concentration.

FABRICATION PROCEDURE

A reliable fabrication procedure has been defined and followed cautiously for all tested mixtures. First, the kaolin powder is mixed thoroughly with distilled water added progressively in a 5 litres mechanical mixer. The combined effects of mixing and slowly water impregnation yields easily to homogeneous saturated pastes with the target initial water content (w ci ). Then, an appropriate amount of Hostun sand was added progressively to this clay paste at the required state (w ci ) and slowly mixed to reach a target value of e g . Observations indicated that this procedure leads to a mixture formed by sand particles uniformly coated by the clay paste. However, air remains in between the spheroid coated grains (except in the case of liquid paste and small amount of sand).

Material is finally compacted using a Proctor dynamical compaction (only half of the standard number of blows were applied to avoid a high level of pre-consolidation (AFNOR 1993)). The reproducibility of the tests results further carried out on these samples let us be confident about the homogeneity of each specimen and the uniformity of sample population.

It is worth mentioning that, despite the saturation of the clay paste in the first fabrication stage, air bubbles remain trapped during compaction. The checking and loading tests further carried out evidenced the presence of a volume of air around 10% of the overall volume of the mixture. In the following, to avoid any ambiguity, the term "mixture" systematically specifies the saturated clay, water and sand media (on which the parameter and notations introduced above apply), when "soil" denotes the mixture together with the air bubbles (whose associated parameters are indexed by "s"). The term "pure" refers solely to one constituent of the mixture, i.e., pure sand means only sand in the mixture (R c = 0).

PREVIOUS STUDIES

Surprisingly, there are relatively few systematic studies on the response of clay-sand mixtures for different mixture density, water content and clay-sand ratio. Georgianou et al. ( 1990) study the response of Ham river sands merged in a very liquid speswhite kaolin slurry (5w L ), and found that the mixture behaves almost as a sand saturated by pure water. This result indicates that, for such a high level of clay paste liquidity, suspensions of sand grains are unstable, so that mixtures necessarily present a skeleton of sand grains. [START_REF] Kumar Gv | Experimental observation of behaviour in heterogeneous soils[END_REF] investigate mixtures made of a liquid kaolin clay (1.5w L ) and coarse sand. They establish two kinds of behaviour: the behaviour of stable suspensions of grains, mainly controlled by the clay paste, and the behaviour of skeletons of grains in contact filled by the clay paste, mainly controlled by the grains. The conclusions drawn in this study are, however, limited to the case of clay paste with a water content higher than the liquid limit, that is with a very low shear strength. As a consequence, the clay paste cannot carry shear forces and cannot consequently act as bridges in-between the sand particles. The aim of the present study is to provide some insights into the behaviour of clay-sand mixtures where the stiffness and the strength of the clay paste range from low values to values close to that of the sand skeleton.

EXPERIMENTS

From the Proctor mould (inner diameter of 10.19 cm, height of 11.65 cm), three cylindrical samples (diameter of 7.14 cm, thickness of 2.0 cm) are extracted. One sample was used for checking the values of targeted e c and e g . The two others were submitted to identical oedometric tests (AFNOR 1997) and permeability measurements (AFNOR 2005). A fairly good reproducibility of the experimental results is systematically noticed.

The oedometric experiments follow the standard procedure, doubling the load every 24 hours, from 35 kPa, to 1120 kPa. Including the intermediate (280-70 kPa) unloading-reloading, and final unloading steps (1120-35 kPa), the experiments took 14 days. The settlement of the sample was measured automatically by LVDT sensors.

The permeability measurements have been performed straightforwardly on the samples in the oedometric cell before each additional loading step using the variable head method. The ambient temperature was also monitored in the oedometric cell.

ANALYSIS AND TREATMENT OF EXPERIMENTAL DATA

RESULTS FROM OEDOMETER LOADING

The record of the settlements observed during all the oedometer tests and for all the loading stages systematically evidence three different steps (Fig. 5).

Initially, an instantaneous high deformation is observed. Further unloading indicates that this deformation is irreversible. Because clay, grain and water are weakly compressible, an instantaneous seepage is impossible. Moreover, the adjustment of mechanical gaps in the apparatus only concerns the first loading step. Thus, this systematic quick volume variation results from the compression of the very deformable air bubbles captured inside the soil during the sample preparation: under a load increment, the paste instantaneously yields, compresses the air bubbles, and the soil reaches a more compact configuration that supports the total applied load.

In a second step, the classical phase of consolidation starts to develop. It corresponds to the transfer of load from the fluid to the solid, associated with the expulsion of water that induces the volume variation. In good agreement with the consolidation theory, it has been observed that the duration of the primary consolidation and the magnitude and rate of settlements increased for samples with a higher void ratio of the clay paste and a lower granular void ratio.

The third step consists in the secondary consolidation, characterized by a linear evolution of the settlements with Log(t). By testing the different mixtures, it has been noticed that the amplitude of this phase increases with the void ratio of the clay paste. Moreover, when e g is close to e max (i.e., when the grains are in contact and forms a continuous skeleton), the magnitude of the secondary and primary consolidation have been observed to be comparable.

MEAN CLAY PASTE VOID RATIO < e c > AND APPARENT CLAY COMPRESSIBILITY

It can be deduced from Figure 6 that all the tested soils follow the classical one dimensional consolidation behaviour as all the compression curves are straight lines in the e s -Log(σ ) diagram. However, they do not allow for a good discrimination of the behaviour of the different soils. A better insight into this question is presented hereinafter by drawing the compression curve of the mixture and the apparent compression curve of the clay paste within the mixture.

At each loading stage, the effective volume variation of the saturated sand clay mixture is calculated by subtracting the instantaneous settlement (due only to air bubbles compression) from the total settlement of the soil. This procedure enables the derivation of the average void ratio of the saturated mixture, denoted < e >:

< e >= W C + G (8)
and the drawing of the mixture compression curve < e > versus Log(σ ). Now, the average void ratio of the clay paste < e c > can be obtained by dividing < e > by the clay content R c , which is constant during each oedometric tests:

< e > R c = W C + G C + G C = W C =< e c > (9)
Then, the apparent compression curve (Log(σ );<e c >) of the clay paste within the mixture, can be deduced as shown in Figure 7. The term "apparent" underlines that, in most of the cases, the effective stress σ applied on the mixture is not the stress supported by the clay itself.

The following paragraphs address the analysis of the behaviour of the different mixtures from the analysis of the apparent compression curve of the clay paste only. The discussion is organized by distinguishing the effect of the initial water content of the clay paste (from the liquid to the plastic limit) and the granular void ratio (from dilute to dense).

Mixtures made of clay paste at the liquid limit

Figure 7(a) shows the apparent compression curve of the clay paste within a mixture at the liquid limit and for different granular void ratio (e g = 1, 1.2, 1.7, 3, 5, 9), and the compression curve of the pure clay paste. Mixtures with e g ≥ 2e max , that is with sand grains dispersed in the clay paste, have the same apparent compression curve than the pure clay paste. This suggests that the effective stress applied to the mixture (σ ) is merely transferred to the clay paste that supports (at least in average) the load applied to the mixture (< σ c >= σ ). Two reasons can be argued for the negligible effect of rigid sand inclusions on the clay paste. The first reason relies on the fact that the grains are too distant to interact significantly.

The second reason relies on the low shear strength of the clay paste that avoids the development of shear stresses in the paste. As a result, the stress state inside the clay is very close to be uniformly hydrostatic within all the sample. Both the local vertical stress < σ c > and the local void ratio of the clay paste are homogeneous in the sample and equal, respectively, to the vertical applied load < σ > and average void ratio of the clay paste < e c >. Thus, σ c = σ and < e c >= e c , the compression curves (Log(σ ); < e c >) and (Log(σ ); e c ) coincide.

Oppositely, the mixture that presents a skeleton of grains, e g = 1 = e max , shows an apparent compression curve close to that of the loose sand, much less compressible than the pure clay paste. The reason is that the grain skeleton -significantly stiffer than the liquid clay paste -supports most of the stress applied to the mixture (σ sk ≈ σ ). Thus, the clay paste undergoes locally small stresses (σ c σ ) and its volume variation is essentially governed by the grain rearrangement. Consequently, the volume variations of the pure clay paste are much smaller than those that would have suffered by carrying the whole mixture stress.

Finally, the apparent compression curve of the mixture with a granular void ratio e g = 1.2 lies in between those of the pure clay paste and the mixture of loose sand (e g = e max ) -clay paste. In this intermediary case, despite of a sand skeleton being in formation (not all the grains are in contact as e g > e max ) the mixture is able to carry a load that the clay paste alone could not support. This stiffening effect is interpreted as due to the existence of a tenuous skeleton made of sand grains already in contact and clay bridges that undergo stresses of the same order (σ k ≈ σ c ). Due to load partly carried by the tenuous skeleton and partly by the clay paste, both having comparable stiffnesses, the stress within the paste differs from that applied to the mixture and the apparent compression curve differs from that of pure clay paste.

These results are qualitatively identical to those obtained by [START_REF] Kumar Gv | Experimental observation of behaviour in heterogeneous soils[END_REF] for mixtures of similar constitution. Both studies indicate that the behaviour "jumps" from that driven by the clay paste to that driven by the grain skeleton for a limited increase in granular void ratio. The connection threshold of the grains is the determining factor. The present study indicates that, for the case of a clay paste at the liquid limit, the connection threshold takes place for a granular void ratio ranging between 1.5e max and 2e max . 5,2,3,4,6), made of clay paste at water content w c = 0.30, an intermediate value between the liquid and plastic limits. They are regularly distributed, ranging from that of pure clay paste and that of loose sand, as the sand concentration increases, i.e., e g decreases. It is worth mentioning that, in all the cases, the presence of sand modifies the apparent compression curve, even at a very low concentration (e g = 6). This last case is particularly interesting as it provides keys about the homogeneity of the stress state inside the clay paste. Indeed, as mentioned above, when the grains are dispersed, the clay paste undergoes in average the load applied to the mixture (< σ c >= σ ). If the stress state would be homogeneous, then, there would be a uniform volume variation of the clay paste and the average void ratio < e c > would be equal to that of the pure clay paste e c . As a consequence, the apparent and the pure clay paste compression curves would coincide. As it is not case, one can conclude that the stress state and the volume variations within the clay paste are heterogeneous.

Mixtures made of clay at an intermediate state

By comparing with the previous case, the explanation for the occurence of heteregeneous stress and strain states can be found in the higher shear strength of the clay paste. It allows the clay to carry the shear forces induced by the presence of the grains: compression zones can develop between two grains along the direction of the load and shear zones between grains shifted one each other with respect to this direction. As (i) the representative elementary volume (REV) undergoes a uniform vertical displacement, and (ii) the grains are rigid, the local axial deformation of the clay paste tends to be in inverse proportion of the inter-grains distance in the loading direction. Because the clay can support shear, this deformation is not compensated by an equivalent lateral deformation. Thus, the clay paste is more loaded in the narrow inter-grains spaces than in larger spaces. As a result of this mechanism, locally denser zones will be created in the clay. Such heterogeneous local stress distributions in heterogeneous media have been already put forward in particular for elastic composites (Sanchez-Palencia 1980). It explains why, even in absence of a skeleton, the apparent behaviour -related to a local het-erogeneous state -is stiffer than that of the pure clay paste under homogeneous load.

In addition, because of the non-linear hardening behaviour of the clay paste, the denser zones are stiffer than the less compacted zones. This creates a mechanism of local structuring of the clay paste in the REV as bridges of stiffer clay develop in-between the sand grains along the direction of load. This mechanism gets amplified at each loading stage, as the stresses tend to transit through the paths of higher stiffness , i.e., through the already denser local zones of the clay paste, and leaves the other zones less loaded. The structuring process will, thus, lead to the development of stable chains of forces -even in the absence of contacts among sand grainsthat will carry more and more effort as the external stress increases. The zones within the chain of forces know a local stress σ c higher than the stress externally applied σ and a local void ratio e c lower than the average void ratio of the clay paste < e c >, meanwhile other clay zones remain weakly loaded (σ c σ ), then weakly compacted (e c > < e c >). Clearly, the effect of such a structuring process is to increase the apparent stiffness of the mixture. One may infer from the test results that the higher is the grain concentration, local denser zones become more and more stressed and, consequently, more and more compact and stiffer, and the more plastic is the paste (i.e., more able to sustain deviatoric stress), the more dominating will be this effect.

One may finally notice that the higher stiffness observed in Figure 7(b) for the mixture e g = 1, possibly results from the presence of a loose skeleton. The explanation is similar to that proposed for the liquid clay paste. 7(d) shows the variation of the apparent compression curves for a mixture made of a clay paste close to the plastic limit w ci = 0.30 and granular void ratios ranging between e max and 6e max . It evidences that the apparent compressibility decreases as the granular void ratio increases, in a qualitative way similar to that observed in the other tests. However, the effect of granular void ratio seems to be much more limited. This can be attributed to the higher stiffness of the clay paste, close to that of the sand skeleton. As the stiffness of the mixture can vary only between that of the pure clay and the pure sand, its variation is necessarily limited.

Mixtures made of clay close to the plastic limit

TANGENT OEDOMETRIC MODULUS OF MIXTURES

An alternative analyse of the mixture behaviour is to relate the tangent oedometric modulus of mixture E oed to the mean clay paste void ratio < e c > for different values of e g . At each loading stage characterized by σ i and e i = R c . < e c > i , E oed (e i ) is classically deduced from the mixture compression curve (e; Log(σ )) by:

E oed (e i ) = σ e (1 + e i ). (10)
The results given on Figure 8 show that, for a fixed e g , Log(E oed ) is a linear decreasing function of < e c >. Moreover, as e g increases, Log (E oed ) increases. This remarkable linearity indicates that the roles played by e c and e g on the mixture behaviour can be expressed in the general empirical form:

Log(E oed ) = a(e g ) -b(e g ). < e c >, or E oed = F(e g ).10 -<e c >.b(e g ) (11)

The coefficient b(e g ) ranges from 4 for very compressible pure clay pastes, e g = ∞ to 10 for stiff mixtures (presenting a grain skeleton, e g ≈ e max ).

For mixtures free of skeleton (e g > 2e max ), the relation ( 11) can be specified more precisely from Figure 8. Almost independently of the clay paste state, the value of Log(E oed ) can straightforwardly be deduced from that of the pure clay paste E paste (< e c >) by a translation factor depending on e g :

Log(E oed ) = a(e g ) + Log(E paste (< e c >)), i.e. E oed = F(e g ).E paste (< e c >) (12)
The empirical equation ( 12) uncouples the rheological effect (clay paste response) and the geometrical effect (distance in-between sand grains related to their concentration) in the expression of the stiffness of the mixture. Note that < e c > represents the average void ratio of the clay paste computed during loading for a given mixture, and is not representative of the initial water content of the clay. As well, Figure 8 indicates that F(e g ) and E paste (< e c >) take different forms depending of the initial state of the clay paste. For instance, in the case of paste prepared at the liquid state, E paste is found to follow the relationship:

E paste (< e c >) = 10 5 10 4(1-<e c >)
and F(e g ) ranges from 1 for e g = ∞, to 3 for e g = 2.

For the mixtures with skeleton and/or possible structuring effect (e g < 2e max ), the roles of e g and < e c > are systematically coupled. This illustrates the interdependences of the rheological and geometrical effects that exist in most of non-linear material.

ANALYSIS OF THE RESULTS ON PERMEABILITY

A similar analysis has been performed to relate the mixture permeability K (m/s) to the pure clay paste permeability K paste and the sand content. Because of the small amount of air (around 10%, as previously discussed), its influence on the water flow is considered negligible and the mixture permeability is assimilated to the soil permeability. Figure 9 shows the variation of Log(K ) with < e c > for different e g . A linear trend is observed with a slope that decreases as e g increases, according to the physical intuition. It is interesting to note that the curves present the same general trends as observed for the tangent oedometric modulus.

E1- 1.25i E2- 1.25i E1-1.5i E2-1.5i E1-3i E2-3i E1-6i E2-6i E1-Ci E2-Ci E2- 1.75i E1- 1.75i E2-2i E1-2i E1-4i E2-4i (
For mixtures with dispersed grains (e g > 2e max ) or made of paste at the liquid state, Log(K ) can be reasonably deduced from Log(K paste ) by a translation factor depending on e g only, following the expression:

K = H (e g ) • K paste (e c ) (13)
Consequently, as for the constrained modulus, the mixture permeability can be decoupled into the product of the clay paste permeability by a pure geometrical factor related to grain concentration. For instance, considering mixtures prepared with paste at the liquid state:

K paste = 10 -9 10 2(1-e c )
H (e g ) lies in between 1 and 3. Mixtures with closer grains (e g < 2e max ) and less liquid paste are much less permeable, and the influence of < e c > and e g cannot be decoupled. In those cases, the experimental results may be summarized by the following empirical relationships:

Log(K ) = a (e g ) -b (e g )Log(K paste ); or K = G (e g )[K paste ] b (e g ) , (14)
with 1/3 < b (e g ) < 1. The strong reduction of permeability and its interdependence with the grain concentration, argues in favour of a structuring process previously mentionned. Indeed, the significant reduction in permeability can be interpreted as being caused by the presence of a network of denser (and, thus, less permeable) zones within the clay paste.

BASIC MODELLING IN THE FRAMEWORK OF HOMOGENIZATION

Phenomena in heterogeneous media can be upscaled and formulated in terms of macroscopic behaviour, provided that a condition of scale separation is fulfilled. This latter condition requires that the medium morphology is sufficiently regular to be described by a Representative Elementary Volume REV and that the characteristic size of the phenomena is much larger than the REV size. These two conditions are respected in the present work.

For linear phenomena, the homogenization of periodic media (Sanchez-Palencia 1980) -based on a two scale asymptotic expansions of both physical variables and differential operators -provides a rigorous theoretical framework to justify the existence of the macroscopic behaviour and to determine its features and limits of validity.

Non-linear phenomena drastically increase the theoretical difficulties, so that only sparse results for specific cases are available [START_REF] Suquet | Continuum micromechanics[END_REF]. A way to relax this difficulty without missing the theoretical tools of the periodic homogenization is to linearize the problem. At the expense of simplifying assumptions, the homogenization can, then, be applied to determine the incremental tangent macroscopic properties.

This section aims at identify up to which extent the usual and tangent homogenization techniques are able to describe reasonably the mixture permeability and tangent compressibility. A corollary aim is also to point out the domain of interest and the limitations of such approaches by using the experiments described in this work for qualitative and quantitative comparisons.

MODELLING OF PERMEABILITY

The determination of the permeability of a composite material made of a permeable media (the clay paste characterized by K paste ) and impervious grains at a granular void ratio e g is a classical linear problem of homogenization. By assimilating the mixture to a bi-composite with K paste constant and isotropic (implying that e c is considered homogeneous in the REV, i.e. e c , = < e c >), and assuming in addition the mixture being isotropic, the homogenization procedure leads to express the permeability of the mixture K as:

K = K paste • H (15)
where H depends only on the cell geometry. In absence of more details about grain arrangement in the REV, H will be expressed as a function of the most basic geometrical information: the volume ratio between the two constituents e g . To estimate H (e g ), assumptions must be done on the microstructure. For simplicity, two cases will be considered (Fig. 10):

• the idealized case of a 1D stratified sand-clay paste microstructure. In this case, the permeability in the direction of the clay layers is given by:

K = K paste • (1 -G) = K paste e g 1 + e g
• a more realistic 3D geometry suggested by the observation that the microstructure is essentially made of grains coated by the clay paste. For such configuration, the form factor corresponding to spherical grains dispersed in the clay paste can be assessed by using a self-consistent approach based on a pattern formed by a bi-composite sand/paste sphere (Hashin 1968). The expression is:

K = K paste e g 3 2 + e g
The similarity between Equation ( 15) and the empirical equation ( 13) indicates that the assumption of constant e c within the REV is in accordance with the experience for the case of mixture with e g > 2e max .

Conversely, the discrepancy between Equation (15) and the power law observed experimentally (Equation 14) indicates that the assumption of an homogeneous clay paste within the REV is missed for e g < 2e max . For quantitative purpose, a comparison of the theoretical and experimental laws are drawn in Figure 10. The progressive departure of the curves as e g decreases confirms the previous remark and suggests the occurrence of structuring phenomena for e g < 2e max .

From a theoretical point of view, the structuring effect can be modelled by representing the mixture by a composite with inhomogeneous matrix (instead of a bicomposite). However, the necessity to known the local values of the permeability within the REV makes the problem much more complex in practice.

MODELLING OF OEDOMETRIC TANGENT MODULUS

As already mentioned, the mixture compression behaviour relies on a non-linear hardening mechanism in the clay paste surrounding the grains. A rigorous treatment by homogenization would be extremely complex since, at each loading stage, the inhomogeneous stress distribution modifies the local properties of the clay paste within the REV. Thus, the derivation of the macroscopic behaviour would require an incremental homogenization procedure. A new step of calculation requires the construction of a new REV with properties determined by the previous steps and accounting for the heterogeneous state of the clay paste. Note also that, conversely to the linear case, there is no proof of the uniqueness of the local solution in the REV until now.

In this context, no theoretical derivation of the uniqueness of the local solution will be looked for, but one will rely on the fairly good experimental repeatability to assume its existence. Notice that this assumption is necessary to justify the search of a macroscopic description.

To reduce the complexity of the local problem, three successive simplifying assumptions will be introduced.

• First, the tangent homogenization approach is considered. It considers a fictitious REV made of elastic materials whose properties matches the tangent properties of the real material in the REV. The application of the homogenization method on the fictitious REV leads to the derivation of the tangent macroscopic properties of the real media. Although simplified, this tangent method remains complex because of the general anisotropy of the tangent behaviour. As a matter of fact, if the non linear constitutive law is expressed by:

σ = L(E) : E
where E is the strain tensor, the tangent behaviour reads:

dσ = L t (E) : dE
And, from the tensor representation theorem, [START_REF] Boelher | Applications of Tensor Functions in Solid Mechanics[END_REF], as E is generally anisotropic, the tangent tensor L t (E) is also anisotropic.

• The second simplifying assumption is that the non-linear behaviour only depend on the isotropic invariant of E, i.e., on the volume variation, so that the tangent behaviour can be considered isotropic.

In this case, the tangent macroscopic properties could be derived from calculations on a REV with heterogeneous but isotropic and elastic matrix. However, the necessity to specify the local elasticity tensor within the REV makes the problem still complex.

• The third simplifying assumption states an homogeneous volume variation within the clay paste (then e c equals < e c >). Then, the macroscopic tangent behaviour can be estimated from the basic homogenization of a bi-composite made of rigid inclusions and an homogeneous isotropic matrix. This leads to express the oedometric modulus in the form [START_REF] Kacprzak | Etude du comportement mécanique des mélanges sable/argile[END_REF]):

E oed = E paste (< e c >) A(e g , ν) (16)
where A is a dimensionless factor depending on the cell geometry (in that case on e g ) and on the Poisson ratio ν.

The modulus of a 1D idealized stratified sand-clay paste microstructure is, in the direction perpendicular to the clay layers:

E oed = E paste 1 -G = E paste 1 + e g e g
For spherical grains dispersed in the clay paste, the form factor can be assessed analytically by a self-consistent approach based on a pattern constituted by a bi-composite sand/paste sphere (Christiensen and Lo 1979). The theoretical value of A(e g , ν) slightly depends on the Poisson ratio, [START_REF] Kacprzak | Etude du comportement mécanique des mélanges sable/argile[END_REF]). These estimates of tangent modulus ( 16) are qualitatively in accordance with the experimental results established for mixtures with sufficiently dispersed grains (e g > 2e max ), over the whole loading range. From a quantitative point of view, a reasonable agreement is also observed (Fig. 11) for granular void ratio above the threshold 2e max . However, this rudimentary analysis does not give neither qualitative nor quantitative results in agreement with the experimental results obtained on the mixtures with e g < 2e max . As for the permeability, this fact is an indication of the effect played by both structuring and skeleton effects.

CONCLUSION

The response of mixtures of sand and saturated kaolin paste has been studied in the oedometer for different states of the clay paste (function of the initial water content) and different sand concentrations. Results have been drawn as a function of two volumetric state param-eters, the clay void ratio e c and the granular void ratio e g , instead of the overall void ratio parameter classically used in soil mechanics. Results have been interpreted by considering the material as a composite made of a non-linear and permeable matrix (the kaolin paste) and rigid and impervious inclusions (the sand grains). The final aim of this study is to investigate the possibility to build by homogenization a macroscopic description related to a strongly non-linear local behaviour where volume variation is an essential feature.

Oedometric loading and permeability test results highlight the key role of the deviatoric strength of the clay paste in the perturbations introduced by the grains. They also point out a threshold of granular void ratio of about 2e max , below which both structuring and skeleton effect influences the modulus and the permeability. In addition, it has been shown that, as its constituents, the mixtures respect the classical logarithmic compression behaviour. Finally, the good repeatability of the results provides, in some way, an experimental proof of the uniqueness of the solution at the local scale (at least statistically), which justifies the search of a macroscopic description.

Incidentally, the structuring effect explains possibly the higher inefficiency of the static uniaxial compaction with respect to the dynamic one. Indeed, the rotation of the principal stresses associated to the dynamic or rolling compaction imposes the stress paths to move and, thus, avoid the construction of stable hardening force chains that channel the stress flux. Location and orientation of the denser zones are constantly redistributed in the material and there is, consequently, no creation of stiffer material response in the preferential direction of the load.

At the light of these experiments, the usual and tangent homogenization processes (with strongly simplifying assumptions to make the problem manageable) have been applied to estimate the mixture permeability and tangent compressibility. Qualitative and quantitative comparisons with experiments show that this approach reasonably succeeds to capture the macroscopic properties over the whole range of loading when the granular void ratio is larger than the threshold of 2e max , but fails in other cases. For these latter cases, the and/or skeleton effect plays a significant role and must be taken into account at the local scale. Palavras-chave: homogeneização, comportamento nãolinear, misturas de areia-argila, permeabilidade, módulo tangente, compactação, endurecimento.

Fig. 1 -

 1 Fig. 1 -Triangular representation of saturated sand clay mixtures. On the left, determination of the mixture composition with of the volume ratio parameters C, W , G. On the right, identification of the two control parameters e c and e g . The extended line WM corresponds to mixtures of identical R c and indicates the consolidation path in oedometer testing.

Fig. 2 -Fig. 3 -

 23 Fig. 2 -Possible morphology of saturated sand-clay mixtures.W

Fig. 4 -

 4 Fig. 4 -Range of variation of grain size distribution of mixtures.

Fig. 5 -

 5 Fig. 5 -Typical record of settlement versus Log(t) for a single loading stage, separated into three mechanisms decoupled in time.

Fig. 6 -

 6 Fig.6-Compression curves (e s ; Log(σ )) obtained for the soil samples prepared with w c = 0.30 and e g = 1.25, 1.5, 1.75, 2, 3, 4, 6, and the pure clay paste. The superimposed curves are an evidence of the good repeatability of the results.

Figure 7

 7 Figure 7(b) shows the apparent compression curves of mixtures of different granular void ratio (e g = 1, 1.5, 2, 3, 4, 6), made of clay paste at water content w c = 0.30, an intermediate value between the liquid

Fig. 7 -

 7 Fig. 7 -Apparent compression curves < e c > versus Log(σ ) of the clay within the mixture. Mixtures initially made of clay paste at the liquid state: w c = 0.51; e g = 1, 1.2, 1.7, 3, 5, 9, (a), at an intermediate state: w c = 0.35, e g = 1, 1.5, 2, 3, 4, 6, (b) and at a quasi-plastic state: w c = 0.30, e g = 1.25, 1.5, 1.75, 2, 3, 4, 6, (d). The data of all samples are plotted together on (c).

Figure

  Figure 7(d) shows the variation of the apparent compression curves for a mixture made of a clay paste close to the plastic limit w ci = 0.30 and granular void ratios ranging between e max and 6e max . It evidences that the apparent compressibility decreases as the granular void ratio increases, in a qualitative way similar to that observed in the other tests. However, the effect of granular void ratio seems to be much more limited. This can be attributed to the higher stiffness of the clay paste, close to that of the sand skeleton. As the stiffness of the mixture can vary only between that of the pure clay and the pure sand, its variation is necessarily limited.

Fig. 8 -

 8 Fig. 8 -The oedometric tangent modulus Log(E oed ) of the mixtures versus the average void ratio of the clay paste < e c > parameterized by e g . The three groups of curves correspond to mixtures initially made of clay paste at the liquid state (a), at an intermediate state (b), at a quasi-plastic state (c). The data of all samples are plotted together on (d).

Fig. 9 -

 9 Fig. 9 -Permeability of the mixtures versus < e c > parameterized by e g . Mixture initially made of clay paste at the liquid state (a), at an intermediate state (b), at a quasi-plastic state (c). The data of all samples are plotted together on (d).

Fig. 10 -

 10 Fig. 10 -Permeability versus the granular void ratio: comparison between theoretical expressions (assimilating the mixture to a 1D or 3D bi-composite) and experimental values.

Fig. 11 -

 11 Fig. 11 -Oedometric tangent modulus. Comparison of the ratio E oed /E paste deduced from experimental data with those given by tangent homogenization.

RESUMOO

  estudo lida com o comportamento de misturas compostas por areia e uma pasta de caulinita considerada um material composto feito de uma matriz (caulinita) permeável e deformável (com comportamento não-linear) com inclusões rígidas e impermeáveis (grãos de areia). Testes de permeabilidade e odométricos conduzidos nestas misturas enfatizam o papel chave de estado da pasta argilosa e mostram a existência de uma concentração critica de grãos de areia com efeito estruturante que influencia o modulo e a permeabilidade. Sob a luz destes experimentos o processo de homogeneização usual e tangente (com hipóteses simplificadoras para tornar o problema tratável) foi aplicado para estimar a permeabilidade da mistura e a compressibilidade tangente. Comparações qualitativas e quantitativas com dados experimentais apontam o domínio de interesse bem como a limitação destas abordagens.


David Auger
email: david.auger@uvsq.fr

Pierre Coucheney
email: pierre.coucheney@uvsq.fr

Yann Strozecki
email: yann.strozecki@uvsq.fr

Finding Optimal Strategies of Almost Acyclic Simple Stochatic Games

Keywords: algorithmic game theory, stochastic games, FPT algorithms

The optimal value computation for turned-based stochastic games with reachability objectives, also known as simple stochastic games, is one of the few problems in NP ∩ coNP which are not known to be in P. However, there are some cases where these games can be easily solved, as for instance when the underlying graph is acyclic. In this work, we try to extend this tractability to several classes of games that can be thought as "almost" acyclic. We give some fixed-parameter tractable or polynomial algorithms in terms of different parameters such as the number of cycles or the size of the minimal feedback vertex set.

Introduction

A simple stochastic game, SSG for short, is a zero-sum, two-player, turn-based version, of the more general stochastic games introduced by Shapley [START_REF] Lloyd | Stochastic games[END_REF]. SSGs were introduced by Condon [START_REF] Condon | The complexity of stochastic games[END_REF] and they provide a simple framework that allows to study the algorithmic complexity issues underlying reachability objectives. A SSG is played by moving a pebble on a graph. Some vertices are divided between players MIN and MAX: if the pebble attains a vertex controlled by a player then he has to move the pebble along an arc leading to another vertex. Some other vertices are ruled by chance; typically they have two outgoing arcs and a fair coin is tossed to decide where the pebble will go. Finally, there is a special vertex named the 1-sink, such that if the pebble reaches it player MAX wins, otherwise player MIN wins. Player MAX's objective is, given a starting vertex for the pebble, to maximize the probability of winning against any strategy of MIN. One can show that it is enough to consider stationary deterministic strategies for both players [START_REF] Condon | The complexity of stochastic games[END_REF].

Though seemingly simple since the number of stationary deterministic strategies is finite, the task of finding the pair of optimal strategies, or equivalently, of computing the so-called optimal values of vertices, is not known to be in P.

SSGs are closely related to other games such as parity games or discounted payoff games to cite a few [START_REF] Andersson | The complexity of solving stochastic games on graphs[END_REF]. Interestingly, those games provide natural applications in model checking of the modal µ-calculus [START_REF] Stirling | Bisimulation, modal logic and model checking games[END_REF] or in economics. While it is known that they can be reduced to simple stochastic games [START_REF] Chatterjee | A reduction from parity games to simple stochastic games[END_REF], hence seemingly easier to solve, so far no polynomial algorithm are known for these games either.

Nevertheless, there are some very simple restrictions for SSGs for which the problem of finding optimal strategies is tractable. Firstly, if there is only one player, the game is reduced to a Markov Decision Process (MDP) which can be solved by linear programming. In the same vein, if there is no randomness, the game can be solved in almost linear time [START_REF] Daniel Andersson | Deterministic graphical games revisited[END_REF].

As an extension of that fact, there is a Fixed Parameter Tractable (FPT) algorithm, where the parameter is the number of average vertices [START_REF] Gimbert | Simple stochastic games with few random vertices are easy to solve[END_REF]. The idea is to get rid of the average vertices by sorting them according to a guessed order. Finally, when the (graph underlying the) game is a directed acyclic graph (DAG), the values can be found in linear time by computing them backwardly from sinks.

Without the previous restrictions, algorithms running in exponential time are known. Among them, the Hoffman-Karp [START_REF] Hoffman | On nonterminating stochastic games[END_REF] algorithm proceeds by successively playing a local best-response named switch for one player, and then a global best-response for the other player. Generalizations of this algorithm have been proposed and, though efficient in practice, they fail to run in polynomial time on a well designed example [START_REF] Friedmann | An exponential lower bound for the parity game strategy improvement algorithm as we know it[END_REF], even in the simple case of MDPs [START_REF] Fearnley | Exponential lower bounds for policy iteration[END_REF]. These variations mainly concern the choice of vertices to switch at each turn of the algorithm which is quite similar to the choice of pivoting in the simplex algorithm for linear programming. This is not so surprising since computing the values of an SSG can be seen as a generalization of solving a linear program. The best algorithm so far is a randomized sub-exponential algorithm [START_REF] Ludwig | A subexponential randomized algorithm for the simple stochastic game problem[END_REF] that is based on an adaptation of a pivoting rule used for the simplex.

Our contribution

In this article, we present several graph parameters such that, when the parameter is fixed, there is a polynomial time algorithm to solve the SSG value problem. More precisely, the parameters we look at will quantify how close to a DAG is the underlying graph of the SSG, a case that is solvable in linear time. The most natural parameters that quantify the distance to a DAG would be one of the directed versions of the tree-width such as the DAG-width. Unfortunately, we are not yet able to prove a result even for SSG of bounded pathwidth. In fact, in the simpler case of parity games the best algorithms for DAG-width and clique-width are polynomials but not even FPT [START_REF] Obdržálek | Clique-width and parity games[END_REF][START_REF] Berwanger | The dag-width of directed graphs[END_REF]. Thus we focus on restrictions on the number of cycles and the size of a minimal feedback vertex set.

First, we introduce in Section 2 a new class of games, namely MAX-acyclic games, which contains and generalizes the class of acyclic games. We show that the standard Hoffman-Karp algorithm, also known as strategy iteration algorithm, terminates in a linear number of steps for games in this class, yielding a polynomial algorithm to compute optimal values and strategies. It is known that, in the general case, this algorithm needs an exponential number of steps to compute optimal strategies, even in the simple case of Markov Decision Processes [START_REF] Fearnley | Exponential lower bounds for policy iteration[END_REF][START_REF] Friedmann | An exponential lower bound for the parity game strategy improvement algorithm as we know it[END_REF].

Then, we extend in Section 3 this result to games with very few cycles, by giving an FPT-algorithm where the parameter is the number of fork vertices which bounds the number of cycles. To obtain a linear dependance in the total number of vertices, we have to reduce our problem to several instances of acyclic games since we cannot even rely on computing the values in a general game.

Finally, in Section 4, we provide an original method to "eliminate" vertices in an SSG. We apply it to obtain a polynomial time algorithm for the value problem on SSGs with a feedback vertex set of bounded size (Theorem 8).

Definitions and standard results

Simple stochastic games are turn-based stochastic games with reachability objectives involving two players named MAX and MIN. In the original version of Condon [START_REF] Condon | The complexity of stochastic games[END_REF], all vertices except sinks have outdegree exactly two, and there are only two sinks, one with value 0 and another with value 1. Here, we allow more than two sinks with general rational values, and more than an outdegree two for positional vertices.

Definition 1 (SSG).

A simple stochastic game (SSG) is defined by a directed graph G = (V, A), together with a partition of the vertex set V in four parts V MAX , V MIN , V AV E and V SIN K . To every x ∈ V SIN K corresponds a value Val(x) which is a rational number in [0, 1]. Moreover, vertices of V AV E have outdegree exactly 2, while sink vertices have outdegree 1 consisting of a single loop on themselves.

In the article, we denote by n M , n m and n a the size of V MAX , V MIN and V AV E respectively and by n the size of V . The set of positional vertices, denoted V P OS , is V P OS = V MAX ∪ V MIN . We now define strategies which we restrict to be stationary and pure, which turns out to be sufficient for optimality. Such strategies specify for each vertex of a player the choice of a neighbour.

Definition 2 (Strategy

). A strategy for player MAX is a map σ from V MAX to V such that ∀x ∈ V MAX , (x, σ(x)) ∈ A.
Strategies for player MIN are defined analogously and are usually denoted by τ . We denote Σ and T the sets of strategies for players MAX and MIN respectively.

Definition 3 (play).

A play is a sequence of vertices x 0 , x 1 , x 2 , . . . such that for all t ≥ 0, (x t , x t+1 ) ∈ A.

Such a play is consistent with strategies σ and τ , respectively for player MAX and player MIN, if for all t ≥ 0,

x t ∈ V MAX ⇒ x t+1 = σ(x t ) and x t ∈ V MIN ⇒ x t+1 = τ (x t ).
A couple of strategies σ, τ and an initial vertex x 0 ∈ V define recursively a random play consistent with σ, τ by setting:

• if x t ∈ V MAX then x t+1 = σ(x t ); • if x t ∈ V MIN then x t+1 = τ (x t ); • if x t ∈ V SIN K then x t+1 = x t ;
• if x t ∈ V AV E , then x t+1 is one of the two neighbours of x t , the choice being made by a fair coin, independently of all other random choices.

Hence, two strategies σ, τ , together with an initial vertex x 0 define a measure of probability P x0 σ,τ on plays consistent with σ, τ . Note that if a play contains a sink vertex x, then at every subsequent time the play stays in x. Such a play is said to reach sink x. To every play x 0 , x 1 , . . . we associate a value which is the value of the sink reached by the play if any, and 0 otherwise. This defines a random variable X once two strategies are fixed. We are interested in the expected value of this quantity, which we call the value of a vertex x ∈ V under strategies σ, τ : Val σ,τ (x) = E x σ,τ (X) where E x σ,τ is the expected value under probability P x σ,τ . The goal of player M AX is to maximize this (expected) value, and the best he can ensure against a strategy τ is

Val τ (x) = max σ∈Σ Val σ,τ (x)
while against σ player MIN can ensure that the expected value is at most

Val σ (x) = min τ ∈T Val σ,τ (x).
Finally, the value of a vertex x, is the common value

Val(x) = max σ∈Σ min τ ∈T Val σ,τ (x) = min τ ∈T max σ∈Σ Val σ,τ (x). (1)
The fact that these two quantities are equal is nontrivial, and it can be found for instance in [START_REF] Condon | The complexity of stochastic games[END_REF]. A pair of strategies σ * , τ * such that, for all vertices x,

Val σ * ,τ * (x) = Val(x)
always exists and these strategies are said to be optimal strategies. It is polynomialtime equivalent to compute optimal strategies or to compute the values of all vertices in the game, since values can be obtained from strategies by solving a linear system. Conversely if values are known, optimal strategies are given by greedy choices in linear time (see [START_REF] Condon | The complexity of stochastic games[END_REF] and Lemma 1). Hence, we shall simply write "solve the game" for these tasks. We shall need the following notion:

Definition 4 (Stopping SSG). A SSG is said to be stopping if for every couple of strategies all plays eventually reach a sink vertex with probability 1.

Condon [START_REF] Condon | The complexity of stochastic games[END_REF] proved that every SSG G can be reduced in polynomial time into a stopping SSG G ′ whose size is quadratic in the size of G, and whose values almost remain the same.

Theorem 1 (Optimality conditions, [START_REF] Condon | The complexity of stochastic games[END_REF]). Let G be a stopping SSG. The vector of values (Val(x)) x∈V is the only vector w satisfying:

• for every x ∈ V MAX , w(x) = max{w(y) | (x, y) ∈ A}; • for every x ∈ V MIN , w(x) = min{w(y) | (x, y) ∈ A}; • for every x ∈ V AV E w(x) = 1 2 w(x 1 ) + 1 2 w(x 2
) where x 1 and x 2 are the two neighbours of x;

• for every x ∈ V SIN K , w(x) = Val(x).

If the underlying graph of an SSG is acyclic, then the game is stopping and the previous local optimality conditions yield a very simple way to compute values. Indeed, we can use backward propagation of values since all leaves are sinks, and the values of sinks are known. We naturally call these games acyclic SSGs.

Once a pair of strategies has been fixed, the previous theorem enables us to see the values as solution of a system of linear equations. This yields the following lemma, which is an improvement on a similar result in [START_REF] Condon | The complexity of stochastic games[END_REF], where the bound is 4 n instead of 6 na 2 .

Lemma 1. Let G be an SSG with sinks having rational values of common denominator q. Then under any pair of strategies σ, τ , the value Val σ,τ (x) of any vertex x can be computed in time O(n ω a ), where ω is the exponent of the matrix multiplication, and n a the number of average (binary) vertices. Moreover, the value can be written as a rational number a b , with

0 ≤ a, b ≤ 6 na 2 × q.
Proof. We sketch the proof since it is standard. First, one can easily compute all vertices x such that Val σ,τ (x) = 0.

Let Z be the set of these vertices. Then:

• all AVE vertices in Z have all their neighbours in Z;

• all MAX (resp. MIN) vertices x in Z are such that σ(x) (resp. τ (x)) is in Z.

To compute Z, we can start with the set Z of all vertices except sinks with positive value and iterate the following

• if Z contains an AVE vertex x with a neighbour out of Z, remove x from Z; • if Z contains a MAX (resp. MIN) vertex x with σ(x) (resp. τ (x)) out of Z, remove x from Z.
This process will stabilize in at most n steps and compute the required set Z. Once this is done, we can replace all vertices of Z by a sink with value zero, obtaining a game G ′ where under σ, τ , the values of all vertices will be unchanged.

Consider now in G' two corresponding strategies σ, τ (keeping the same names to simplify) and a positional vertex x. Let x ′ be the first non positional vertex that can be reached from x under strategies σ, τ . Clearly, x ′ is well defined and Val σ,τ (x) = Val σ,τ (x ′ ).

This shows that the possible values under σ, τ of all vertices are the values of average and sink vertices. The same is true if one average vertex has its two arcs towards the same vertex, thus we can forget those also. The value of an average vertex being equal to the average value of its two neighbours, we see that we can write a system

z = Az + b (2)
where

• z is the n a -dimensional vector containing the values of average vertices

• A is a matrix where all lines have at most two 1 2 coefficients, the rest being zeros • b is a vector whose entries are of the form 0, pi 2q or pi+pj 2q , corresponding to transitions from average vertices to sink vertices.

Since no vertices but sinks have value zero, it can be shown that this system has a unique solution, i.e. matrix I -A is nonsingular, where I is the n adimensional identity matrix. We refer to [START_REF] Condon | The complexity of stochastic games[END_REF] for details, the idea being that since in n -1 steps there is a small probability of transition from any vertex of G ′ to a sink vertex, the sum of all coefficients on a line of A n-1 is strictly less than one, hence the convergence of

k≥0 A k = (I -A) -1 . Rewriting (2) as 2(I -A)z = 2b,
we can use Cramer's rule to obtain that the value z v of an average vertex v is

z v = det B v det 2(I -A)
where B v is the matrix 2(I -A) with the column corresponding to v replaced by 2b. Hence by expanding the determinant we see that z v is of the form

1 det 2(I -A) w∈VAV E ±2b w det(2(I -A) v,w )
where 2(I -A) v,w is the matrix 2(I -A) where the line corresponding to v and the column corresponding to w have been removed.

Since 2b w has either value 0, pi q or pi+pj q

for some 1 ≤ i, j ≤ n a , we can write the value of z v as a fraction of integers

w∈v ±2b w q • det(2(I -A) v,w ) det 2(I -A) • q
It remains to be seen, by Hadamard's inequality, that since the nonzero entries of 2(I -A) on a line are a 2 and at most two -1, we have

det 2(I -A) ≤ 6 na 2 ,
which concludes the proof.

The bound 6 na 2

is almost optimal. Indeed a caterpillar tree of n average vertices connected to the 0 sink except the last one, which is connected to the 1 sink, has a value of 1 2 n at the root. Note that the lemma is slightly more general (rational values on sinks) and the bound a bit better ( √ 6 instead of 4) than what is usually found in the literature.

In all this paper, the complexity of the algorithms will be given in term of number of arithmetic operations and comparisons on the values as it is customary. The numbers occurring in the algorithms are rationals of value at most exponential in the number of vertices in the game, therefore the bit complexity is increased by at most an almost linear factor.

MAX-acyclic SSGs

In this section we define a class of SSG that generalize acyclic SSGs and still have a polynomial-time algorithm solving the value problem.

A cycle of an SSG is an oriented cycle of the underlying graph.

Definition 5. We say that an SSG is MAX-acyclic (respectively MIN-acyclic) if from any MAX vertex x (resp. MIN vertex), for all outgoing arcs a but one, all plays going through a never reach x again.

Therefore this class contains the class of acyclic SSGs and we can see this hypothesis as being a mild form of acyclicity. From now on, we will stick to MAX-acyclic SSGs, but any result would be true for MIN-acyclic SSGs also. There is a simple characterization of MAX-acyclicity in term of the structure of the underlying graph. Lemma 2. An SSG is MAX-acyclic if and only if every MAX vertex has at most one outgoing arc in a cycle.

Let us specify the following notion. Definition 6. We say that an SSG is strongly connected if the underlying directed graph, once sinks are removed, is strongly connected. Lemma 3. Let G be a MAX-acyclic, strongly connected SSG. Then for each MAX x, all neighbours of x but one must be sinks.

Proof. Indeed, if x has two neighbours y and z which are not sinks, then by strong connexity there are directed paths from y to x and from z to x. Hence, both arcs xy and xz are on a cycle, contradicting the assumption of MAXacyclicity.

From now on, we will focus on computing the values of a strongly connected MAX-acyclic SSG. Indeed, it easy to reduce the general case of a MAX-acyclic SSG to strongly connected by computing the DAG of the strongly connected components in linear time. We then only need to compute the values in each of the components, beginning by the leaves.

We will show that the Hoffman-Karp algorithm [START_REF] Hoffman | On nonterminating stochastic games[END_REF][START_REF] Condon | On algorithms for simple stochastic games[END_REF], when applied to a strongly connected MAX-acyclic SSG, runs for at most a linear number of steps before reaching an optimal solution. Let us remind the notion of switchability in simple stochastic games. If σ is a strategy for MAX, then a MAX vertex x is switchable for σ if there is an neighbour y of x such that Val σ (y) > Val σ (σ(x)). Switching such a vertex x consists in considering the strategy σ ′ , equal to σ but for σ ′ (x) = y.

For two vectors v and w, we note v ≥ w if the inequality holds componentwise, and v > w if moreover at least one component is strictly larger.

Lemma 4 (See Lemma 3.5 in [START_REF] Tripathi | On strategy improvement algorithms for simple stochastic games[END_REF]). Let σ be a strategy for MAX and S be a set of switchable vertices. Let σ ′ be the strategy obtained when all vertices of S are switched. Then

Val

σ ′ > Val σ .
Let us recall the Hoffman-Karp algorithm:

1. Let σ 0 be any strategy for MAX and τ 0 be a best response to σ 0 2. while (σ t , τ t ) is not optimal:

(a) let σ t+1 be obtained from σ t by switching one (or more) switchable vertex (b) let τ t+1 be a best response to σ t+1

The Hoffman-Karp algorithm computes a finite sequence (σ t ) 0≤t≤T of strategies for the MAX player such that

∀0 ≤ t ≤ T -1, Val σt+1 > Val σt .
If any MAX vertex x in a strongly connected MAX-acyclic SSG has more than one sink neighbour, say s 1 , s 2 , • • • s k , then these can be replaced by a single sink neighbour s ′ whose value is

Val(s ′ ) := max i=1..k Val(s i ).
Hence, we can suppose that all MAX vertices in a strongly connected MAXacyclic SSG have degree two. For such a reduced game, we shall say that a MAX vertex x is open for a strategy σ if σ(x) is the sink neighbour of x and that x is closed otherwise.

Lemma 5. Let G be a strongly connected, MAX-acyclic SSG, where all MAX vertices have degree 2. Then the Hoffman-Karp algorithm, starting from any strategy σ 0 , halts in at most 2n M steps. Moreover, starting from the strategy where every MAX vertex is open, the algorithm halts in at most n M steps. All in all, the computation is polynomial in the size of the game.

Proof. We just observe that if a MAX vertex x is closed at time t , then it remains so until the end of the computation. More precisely, if s := σ t-1 (x) is a sink vertex, and y := σ t (x) is not, then since x has been switched we must have Val σt (y) > Val σt (s).

For all subsequent times t ′ > t, since strategies are improving we will have

Val σ t ′ (y) ≥ Val σt (y) > Val σt (s) = Val σ t ′ (s) = Val(s),
so that x will never be switchable again. Thus starting from any strategy, if a MAX vertex is closed it cannot be opened and closed again, and if it is open it can only be closed once.

Each step of the Hoffman-Karp algorithm requires to compute a best-response for the MIN player. A best-response to any strategy can be simply computed with a linear program with as many variables as vertices in the SSG, hence in polynomial time. We will denote this complexity by O(n η ); it is well known that we can have η ≤ 4, for instance with Karmarkar's algorithm. Theorem 2. A strongly connected MAX-acyclic SSG can be solved in time O(n M n η ).

Before ending this part, let us note that in the case where the game is also MIN-acyclic, one can compute directly a best response to a MAX strategy σ without linear programming: starting with a MIN strategy τ 0 where all MIN vertices are open, close all MIN vertices x such that their neighbour has a value strictly less than their sink. One obtains a strategy τ 1 such that Val σ,τ1 < Val σ,τ0 , and the same process can be repeated. By a similar argument than in the previous proof, a closed MIN vertex will never be opened again, hence the number of steps is at most the number of MIN vertices, and each step only necessitates to compute the values, i.e. to solve a linear system (see Lemma 1).

Corollary 1. A strongly connected MAX and MIN-acyclic SSG can be solved in time O(n M n m n ω ), where ω is the exponent of matrix multiplication.

SSG with few fork vertices

Work on this section has begun with Yannis Juglaret during his Master internship at PRiSM laboratory. Preliminary results about SSGs with one simple cycle can be found in his report [START_REF] Juglaret | Étude des simple stochastic games[END_REF]. We shall here obtain fixed-parameter tractable (FPT) algorithms in terms of parameters quantifying how far a graph is from being MAX-acyclic and MIN-acyclic, in the sense of section 2. These parameters are: We say that an SSG is POS-acyclic (for positional acyclic) when it is both MAX and MIN-acyclic. Clearly, parameter k p counts the number of edges violating this condition in the game. Similarly, we say that the game is AVE-acyclic when average vertices have at most one outgoing arc in a cycle. We call fork vertices, those vertices that have at least two outgoing arcs in a cycle. Since averages vertices have only two neighbours, k a is the number of fork average vertices.

k p =
Note that:

1. When k p = 0 (respectively k a = 0), the game is POS-acyclic (resp. AVEacyclic).

2. When k a = k p = 0, the strongly connected components of the game are cycles. We study these games, which we call almost acyclic, in detail in subsection 3.1.

3. Finally, the number of simple cycles of the SSG is always less than k p + k a , therefore getting an FTP algorithm in k p and k a immediately gives an FTP algorithm in the number of cycles.

We obtain:

Theorem 3. There is an algorithm which solves the value problem for SSGs in time O(nf

(k p , k a )), with f (k p , k a ) = k a !4 ka 2 kp .
As a corollary, by remark 3 above we have:

Theorem 4.
There is an algorithm which solves the value problem for SSGs with k simple cycles in time

O(ng(k)) with g(k) = (k -1)!4 k-1 .
Note that in both cases, when parameters are fixed, the dependance in n is linear.

Before going further, let us explain how one could easily build on the previous part and obtain an FPT algorithm in parameter k p , but with a much worse dependance in n.

When k p > 0, one can fix partially a strategy on positional fork vertices, hence obtaining a POS-acyclic subgame that can be solved in polynomial time according to Corollary 1, using the Hoffman-Karp algorithm. Combining this with a bruteforce approach looking exhaustively through all possible local choices at positional fork vertices, we readily obtain a polynomial algorithm for the value problem when k p is fixed: Theorem 5. There is an algorithm to solve the value problem of an SSG in time O(n M n m n ω 2 kp ).

We shall conserve this brute-force approach. In the following, we give an algorithm that reduces the polynomial complexity to a linear complexity when k a is fixed. From now on, up to applying the same bruteforce procedure, we assume k p = 0 (all fork vertices are average vertices). We also consider the case of a strongly connected SSG, since otherwise the problem can be solved for each strongly connected component as done in Section 2. We begin with the baseline k a = 0 and extend the algorithm to general values of k a . Before this, we provide some preliminary lemmas and definitions that will be used in the rest of the section.

A partial strategy is a strategy defined on a subset of vertices controlled by the player. Let σ be such a partial strategy for player MAX, we denote by G[σ] the subgame of G where the set of strategies of MAX is reduced to the ones that coincide with σ on its support. According to equation (1), the value of an SSG is the highest expected value that MAX can guarantee, then it decreases with the set of actions of MAX: Lemma 6. Let G be an SSG with value v, σ a partial strategy of MAX, and G[σ] the subgame induced by σ with value v ′ . Then v ≥ v ′ .

In strongly connected POS-acyclic games, positional vertices have at least one outgoing arc to a sink. Recall that, in case the strategy chooses a sink, we say that it is open at this vertex (the strategy is said open if it is open at a vertex), and closed otherwise. We can then compare the value of an SSG with that of the subgame generated by any open strategy. Proof. Since it is optimal to open x in G, the value of its neighbour sink is at least that of any neighbour vertex, say y. But, in view of Lemma 6, the value of y in G[σ] is smaller in G, and then it is again optimal to play a strategy open at x in the subgame. This lemma allows to reduce an almost acyclic SSG (resp. an SSG with parameter k a > 0) to an acyclic SSG (resp. an SSG with parameter k a -1).

if the optimal MAX strategy is open at vertex x, then the optimal strategy of the subgame open at any MAX vertex will be open at x. A solution to find x once the subgame is solved (and then to reduce the parameter k a ) consists in testing all the open MAX vertices. But it may be the case that all MAX vertices are open which would not yield a FPT algorithm. In Lemma 8 (resp. Lemma 9), we give a restriction on the set of MAX vertices that has to be tested when k a = 0 (resp. k a > 0) which provides an FPT algorithm.

Almost acyclic SSGs

We consider an SSG with k a = 0. Together with the hypothesis that it is POSacyclic and strongly connected, its graph, once sinks are removed, consists of a single cycle. A naive algorithm to compute the value of such SSG consists in looking for, if it exists, a vertex that is open in the optimal strategy, and then solve the acyclic subgame: 2. If optimal strategies have not been found, return the value when all vertices are closed.

This naive algorithm uses the routine that computes the value of an SSG with only one cycle. When the strategies are closed, the values can be computed in linear time as for an acyclic game. Indeed, let x be an average vertex (if none, the game can be solved in linear time) and s 1 . . . s ℓ be the values of the average neighbour sinks in the order given by a walk on the cycle starting from x. Then the value of x satisfies the equation Val

(x) = 1 2 s 1 + 1 2 ( 1 2 s 2 + 1 2 (• • • + 1 2 ( 1 2 s ℓ + 1 2 Val(x)))), so that Val(x) = 2 ℓ 2 ℓ -1 ℓ i=1 2 -i s i , (3)
which can be computed in time linear in the size of the cycle. The value of the other vertices can be computed by walking backward from x, again in linear time. Finally, since solving an acyclic SSG is linear, the complexity of the algorithm is O(n 2 ) which is still better than the complexity O(n M n m n ω ) obtained with the Hoffman-Karp algorithm (see Theorem 5).

Remark that this algorithm readily be extended to a SSG with k cycles with a complexity O(n k+1 ). Hence it is not an FPT algorithm for the number of cycles. However, we can improve on this naive algorithm by noting that the optimal strategy belongs to one of the following subclasses of strategies: The trick of the algorithm is that, knowing which of the three classes the optimal strategy belongs to, the game can be solved in linear time. Indeed: (i) If the optimal strategy is closed at every vertex, the value can be computed in linear time as shown before. Proof. Let x be a MAX vertex that is open when solving G. From Lemma 7, there is an index i such that x i = x (in particular there exists an open MAX vertex when solving G[σ]). If ℓ = 1 then x 0 = x so that the optimal strategies of G[σ] and G coincide. Otherwise, if i = 1, the result is immediate. At last, if i > 1, x i has the same value in G and G[σ] (the value of its sink), and so has the vertex just before if it is different from x 0 . Going backward from x i in the cycle, all the vertices until x 0 (not included) have the same value in G and G[σ]. In particular, if i > 1, this is the case for x 1 whose value is then the value of its sink. So it is optimal to open x 1 in G as well.

All in all, a linear algorithm that solves a strongly connected almost-acyclic SSG G is:

1. Compute the values of the strategies closed everywhere. If optimal, return the values. 3. Else apply the same procedure to any MIN vertex.

Theorem 6. There is an algorithm to solve the value problem of a strongly connected almost-acyclic SSG in time O(n) with n the number of vertices.

Fixed number of non acyclic average vertices

Again, we assume that the SSG is strongly connected and POS-acyclic. The algorithm for almost-acyclic games can be generalized as follow. Firstly, it is possible to compute the values of the strategies closed everywhere in polynomial time in k a and check if this strategy is optimal. Indeed the value of each fork vertex can be expressed as an affine function of the value of all fork vertices in the spirit of Eq. ( 3). Then the linear system of size k a can be solved in polynomial time, and the value of the remaining vertices computed by going backward from each fork vertex. This shows that computing the values of a game once strategies are fixed is polynomial in the number of fork average vertices, which slightly improves the complexity of Lemma 1.

Otherwise, the following Lemma allows to find a positional vertex that is open for the optimal strategy. We say that a vertex x is the last (resp. first) vertex in a set S before (resp. after) another vertex y if there is a unique simple path from x to y (resp. y to x) that does not contain any vertex in S, x and y being excluded. Proof. Let x be a MAX vertex that is open when solving G, and i be such that a i is the last vertex in A before x. By Lemma 7, x is open in G[σ] and since σ is not open at a MAX vertex between a i and x, all the vertices between the successor of a i and x have the same value in G[σ] and G, and then the optimal strategy of G[σ] at these vertices is optimal for G. This property holds in particular for the first vertex in S[σ] after a i in the path leading to x. This algorithm computes at most 2k a SSGs with k a -1 average fork vertices. In the worst case, the same algorithm must be run for the MIN vertices. Using theorem 6 for the case k p = k a = 0, we obtain Theorem 3 and its corollary.

Feedback vertex set

A feedback vertex set is a set of vertices in a directed graph such that removing them yields a DAG. Computing a minimal vertex set is an NP-hard problem [START_REF] Michael | Computers and intractability: A guide to the theory of NP-completeness[END_REF], but it can be solved with a FPT algorithm [START_REF] Chen | A fixed-parameter algorithm for the directed feedback vertex set problem[END_REF]. Assume the size of the minimal vertex set is fixed, we prove in this section that we can find the optimal strategies in polynomial time. Remark that, to prove such a theorem, we cannot use the result on bounded number of cycles since a DAG plus one vertex may have an exponential number of cycles. Moreover a DAG plus one vertex may have a large number of positional vertices with several arcs in a cycle, thus we cannot use the algorithm to solve MAX-acyclic plus a few non acyclic MAX vertices.

The method we present works by transforming k vertices into sinks and could thus be used for other classes of SSGs. For instance, it could solve in polynomial time the value problem for games which are MAX-acyclic when k vertices are removed.

The dichotomy method

We assume from now on that all SSGs are stopping. In this subsection, we explain how to solve an SSG by solving it several times but with one vertex less.

First we remark that turning any vertex into a sink of its own value in the original game does not change any value.

Lemma 10. Let G be an SSG and x one of its vertex. Let G ′ be the same SSG as G except that x has been turned into a sink vertex of value Val G (x). For all vertices y, Val G (y) = Val G ′ (y).

Proof. The optimality condition of Theorem 1 are exactly the same in G and G ′ . Since the game is stopping, there is one and only one solution to these equations and thus the values of the vertices are identical in both games.

The values in an SSG are monotone with regards to the values of the sinks, as proved in the next lemma.

Lemma 11. Let G be an SSG and s one of its sink vertex. Let G ′ be the same SSG as G except that the value of s has been increased. For all vertices x, Val G (x) ≤ Val G ′ (x).

Proof. Let fix a pair of strategy (σ, τ ) and a vertex x. We have:

Val (σ,τ ),G (x) = y∈VSINK P (x y) Val G (y) Val (σ,τ ),G (x) ≤ y∈VSINK P (x y) Val G ′ (y) = Val (σ,τ ),G ′ (x) because Val G (x) = Val G ′ (x) except when x = s, Val G (s) ≤ Val G ′ (s)
. Since the inequality is true for every pair of strategies and every vertex, the lemma is proved.

Let x be an arbitrary vertex of G and let G[v] be the same SSG, except that x becomes a SINK vertex of value v. We define the function f by:

   if x is a MAX vertex, f (v) = max{Val G[v] (y) : (x, y) ∈ A} if x is a MIN vertex, f (v) = min{Val G[v] (y) : (x, y) ∈ A} if x is an AVE vertex, f (v) = 1 2 Val G[v] (x 1 ) + Val G[v] (x 2 ) Lemma 12. There is a unique v 0 such that f (v 0 ) = v 0 which is v 0 = Val G (x).
Moreover, for all v > v 0 , f (v 0 ) < v 0 and for all v < v 0 , f (v 0 ) > v 0 .

Proof. The local optimality conditions given in Theorem 1 are the same in G and

G[v] except the equation f (Val G (x)) = Val G (x). Therefore, when f (v 0 ) = v 0 , the values of G[v]
satisfy all the local optimality conditions of G. Thus v 0 is the value of s in G. Since the game is stopping there is at most one such value. Conversely, let v 0 be the value of s in G. By Lemma 10, the values in G[v 0 ] are the same as in G for all vertices. Therefore the local optimality conditions in G contains the equation f (v 0 ) = v 0 .

We have seen that f (v) = v is true for exactly one value of v. Since the function f is increasing by Lemma 11 and because f (0) ≥ 0 and f (1) ≤ 1, we have for all v > v 0 , f (v 0 ) < v 0 and for all v < v 0 , f (v 0 ) > v 0 .

The previous lemma allows to determine the value of x in G by a dichotomic search by the following algorithm. We keep refining an interval [min, max] which contains the value of x, with starting values min = 0 and max = 1.

1. While max -min ≤ 6 -na do: Proof. Let v 0 be the value of x in G, which exists since the game is stopping. By Lemma 12 it is clear that the previous algorithm is such that v 0 is in the interval [min, max] at any time. Moreover, by Lemma 1 we know that v 0 = a b where b ≤ 6 na 2 . At the end of the algorithm, max -min ≤ 6 -na therefore there is at most one rational of denominator less than 6 na 2 in this interval. It can be found exactly with O(n a ) arithmetic operations by doing a binary search in the Stern-Brocot tree (see for instance [START_REF] Graham | Patashnik, concrete mathematics[END_REF]).

(a) v = (min + max)/2 (b) Compute the values of G[v] (c) If f (v) > v then min = v (d) If f (v) < v then max = v
One last call to G[v 0 ] gives us all the exact values of G. Since the algorithm stops when max -min ≤ 6 -na , we have at most O(n a ) calls to the algorithm solving G [v]. All in all the complexity is O(n a C(n) + n a ) that is O(n a C(n)).

In the case where G[v] is an acyclic graph, we can solve it in linear time which gives us the stated complexity.

Feedback Vertex Set of Fixed Size

Let G be an SSG such that X is one of its minimal vertex feedback set. Let k = |X|. The game is assumed to be stopping. Since the classical transformation [START_REF] Condon | The complexity of stochastic games[END_REF] into a stopping game does not change the size of a minimal vertex feedback set, it will not change the polynomiality of the described algorithm. However the transformation produces an SSG which is quadratically larger, thus a good way to improve the algorithm we present would be to relax the stopping assumption.

In this subsection we will consider games whose sinks have dyadic values, since they come from the dichotomy of the last subsection. The gcd of the values of the sinks will thus be the maximum of the denominators. The idea to solve G is to get rid of X, one vertex at a time by the previous technique. The only thing we have to be careful about is the precision up to which we have to do the dichotomy, since each step adds a new sink whose value has a larger denominator.

Theorem 8. There is an algorithm which solves any stopping SSG in time O(n k+1 ) where n is the number of vertices and k the size of the minimal feedback vertex set.

Proof. First recall that we can find a minimal vertex with an FPT algorithm. You can also check every set of size k and test in linear time whether it is a feedback vertex set. Thus the complexity of finding such a set, that we denote by X = {x 1 , . . . , x k }, is at worst O(n k+1 ). Let denote by G i the game G where x 1 to x i has been turned into sinks of some values. If we want to make these values explicit we write G i [v 1 , . . . , v i ] where v 1 to v i are the values of the sinks.

We now use the algorithm of Theorem 7 recursively, that is we apply it to reduce the problem of solving G i [v 1 , . . . , v i ] to the problem of solving G i+1 [v 1 , . . . , v i , v i+1 ] for several values of v i+1 . Since G k is acyclic, it can be solved in linear time. Therefore the only thing we have to evaluate is the number of calls to this last step. To do that we have to explain how precise should be the dichotomy to solve G i , which will give us the number of calls to solve G i in function of the number of calls to solve G i+1 .

We prove by induction on i that the algorithm, to solve G i , makes log(p i ) calls to solve G i+1 , where the value v i+1 is a dyadic number of numerator bounded by p i = 6 (2 i+1 -1)na . Theorem 7 proves the case i = 0. Assume the property is proved for i -1, we prove it for i. By induction hypothesis, all the denominators of v 1 , . . . , v i are power of two and their gcd is bounded by p i . By Lemma 1, the value of x i is a rational of the form a b where b ≤ p i 6 na 2 . We have to do the dichotomy up to the square of p i 6 na 2 to recover the exact value of x i in the game G i (v 1 , . . . , v i-1 ). Thus the bound on the denominator of v i+1 is p i+1 = p 2 i 6 na . That is p i+1 = 6 2(2 i+1 -1)na 6 na = 6 (2 i+2 -1)na , which proves the induction hypothesis. Since we do a dichotomy up to a precision p i+1 , the number of calls is clearly log(p i+1 ).

In conclusion, the number of calls to G k is k-1 i=0 log(6 (2 i+1 -1)na ) ≤ 2 k 2 log(6) k n k a .

Since solving a game G k can be done in linear time the total complexity is in O(n k+1 ).

  x∈VP OS (|{y : (x, y) ∈ A and is in a cycle}| -1) and k a = x∈VAV E (|{y : (x, y) ∈ A and is in a cycle}| -1).

Lemma 7 .

 7 Let x be a MAX vertex of an SSG G with a sink neighbour, and σ the partial strategy open at x. If it is optimal to open x in G, then it is optimal to open it in G[σ].

1 .

 1 For each positional vertex x: (a) compute the values of the acyclic SSG G[σ], where σ is the partial strategy open at x, if the local optimality condition is satisfied for x in G, return the values.

  (i) strategies closed everywhere, (ii) strategies open at least at one MAX vertex, (iii) strategies open at least at one MIN vertex.

(Lemma 8 .

 8 ii) If the optimal strategy is open at a MAX vertex (the MIN case is similar), then it suffices to solve in linear time the acyclic game G[σ] where σ is any partial strategy open at a MAX vertex, and then use the following Lemma to find an open vertex for the optimal strategy of the initial game. Let G be a strongly connected almost-acyclic SSG. Assume that the optimal strategy is open at a MAX vertex. For any partial strategy σ open at a MAX vertex x, let x = x 0 , x 1 . . . x ℓ = x be the sequence of the ℓ open MAX vertices for the optimal strategy of G[σ] listed in the cycle order. Then it is optimal to open x 1 .

2 .

 2 Else compute the optimal strategies of G[σ 1 ] where σ 1 is a partial strategy open at a MAX vertex x; let y be the first open MAX vertex after x; compute the values of G[σ 2 ] where σ 2 is the partial strategy open at y; if the local optimality condition is satisfied for y in G, return the values.

Lemma 9 .

 9 Let G be a strongly connected SSG with a set A = {a 1 , . . . , a ℓ } of fork average vertices and no positional fork vertices. Assume that the optimal strategy of G is open at a MAX vertex. Let σ be a partial strategy open at any vertex that is the last MAX vertex before a vertex in A. Let S[σ] be the set of open MAX vertices when solving G[σ]. Then, there exists x ∈ S[σ] that satisfies • it is optimal to open x in G, • x is the first vertex in S[σ] after a vertex in A.

Figure 1 :

 1 Figure 1: Illustration of Lemma 9: a 1 and a 2 are average fork vertices. Vertices on the top are MAX vertices, labelled from 1 to k, that lead to sinks. max k is the last MAX vertex before a fork vertex. Assume it is optimal to open at least one MAX vertex. Then, the first open MAX vertex (wrt to the labelling) of the optimal strategy of the subgame open at max k is open as well in the optimal strategy of the initial game.

2 . 2 Theorem 7 .

 227 Return the unique rational in [min, max] of denominator less than 6 -na Let G be an SSG with n vertices and x one of its vertex. Denote by C(n) the complexity to solve G[v], then we can compute the values of G in time O(nC(n)). In particular an SSG which can be turned into a DAG by removing one vertex can be solved in time O(n 2 ).

Acknowledgements This research was supported by grant ANR 12 MONU-0019 (project MARMOTE). Thanks to Yannis Juglaret for being so motivated to learn about SSGs and to Luca de Feo for insights on rationals and their representations.