E Bévillon

J P Colombier

V Recoules

R Stoian

First-principles calculations of heat capacities of ultrafast laser-excited electrons in metals

Keywords: Ultrashort laser, Femtosecond laser-excited electrons, First-Principles calculations, Electronic Heat Capacities

Ultrafast laser excitation can induce fast increases of the electronic subsystem temperature. The subsequent electronic evolutions in terms of band structure and energy distribution can determine the change of several thermodynamic properties, including one essential for energy deposition; the electronic heat capacity. Using density functional calculations performed at finite electronic temperatures, the electronic heat capacities dependent on electronic temperatures are obtained for a series of metals, including free electron like, transition and noble metals. The effect of exchange and correlation functionals and the presence of semicore electrons on electronic heat capacities are first evaluated and found to be negligible in most cases. Then, we tested the validity of the free electron approaches, varying the number of free electrons per atom. This shows that only simple metals can be correctly fitted with these approaches. For transition metals, the presence of localized d electrons produces a strong deviation toward high energies of the electronic heat capacities, implying that more energy is needed to thermally excite them, compared to free sp electrons. This is attributed to collective excitation effects strengthened by a change of the electronic screening at high temperature.

Introduction

Material response to intense laser excitation is the subject of important research activities, and recent advances have revealed the determinant role of primary excitation events. Their accurate comprehension is necessary to correctly describe ultrafast structural dynamics [START_REF] Cavalleri | Femtosecond electron crystallography reveals the atomic structural changes that underpin a light-induced insulator-metal transition[END_REF][START_REF] Gamaly | The physics of ultra-short laser interaction with solids at non-relativistic intensities[END_REF], phase transitions [START_REF] Povarnitsyn | Phase transitions in femtosecond laser ablation[END_REF][START_REF] Recoules | Effect of intense laser irradiation on the lattice stability of semiconductors and metals[END_REF], nanostruture formation [START_REF] Colombier | Effects of electron-phonon coupling and electron diffusion on ripples growth on ultrafast-laser-irradiated metals[END_REF], ablation dynamics [START_REF] Lorazo | Thermodynamic pathways to melting, ablation, and solidification in absorbing solids under pulsed laser irradiation[END_REF][START_REF] Colombier | Guiding heat in laser ablation of metals on ultrafast timescales: an adaptive modeling approach on aluminum[END_REF], or strong shock propagation [START_REF] Zhakhovsky | Two-zone elastic-plastic single shock waves in solids[END_REF]. The interplay between ultrafast excitation and resulting excited material response still requires a comprehensive theoretical description for highly excited solid materials. Ultrashort laser irradiation produces a strong inhomogeneous heating of electrons that rapidly exchange energy through electron-electron collisions, leading the electronic subsystem to a thermalized state which is intimately related to the electronic structure of the material. This fast heating of the electronic subsystem leads in turn to a significant electron-phonon nonequilibrium, as the energy of the laser pulse is deposited before relaxation takes on and the material starts dissipating energy by thermal or mechanical ways.

During intense laser exposition, the irradiated material undergoes successive stages of extreme constraints, starting from the inhomogeneous excitation of electrons, the swift rise of electronic temperature and electronic pressure after thermalization of the electronic subsystem on the tens of femtosecond timescale [START_REF] Mueller | Relaxation dynamics in laser-excited metals under nonequilibrium conditions[END_REF]. These rapid processes are followed by the rise of the ionic temperature associated to thermally-triggered phase transitions, before ablating or returning to ambient conditions from further energy dissipations occurring at larger timescale. The accurate knowledge of these rapidly evolving conditions, in intensity and time, is of importance as they modify material properties. Evolution of electronic and ionic temperatures, T e and T i respectively, are generally calculated with the two-temperature model [START_REF] Kaganov | Relaxation between electrons and crystalline lattices[END_REF][START_REF] Anisimov | Non-Hamiltonian approach to conformal quantum field theory Sov[END_REF] which involved transient parameters such as electronic heat capacity, electron-phonon coupling strength, thermal conductivity, electronic pressure and material absorptivity.

The basic underlying assumption in the two-temperature model is that the electron subsystem consists of a thermalized population of a certain amount of electrons, a condition easily fulfilled in ablation processes conditioned by high electronic temperatures [START_REF] Colombier | Guiding heat in laser ablation of metals on ultrafast timescales: an adaptive modeling approach on aluminum[END_REF]. The energy evolution is determined by photon absorption, energy accumulation and thermal/mechanical transport (involving electron-electron and electron-phonon interaction) based on nonequilibrium dynamics. The effective number of charge carriers taking part in absorption, storage and dissipation of the energy has to be carefully evaluated to give a correct description of the evolution of the corresponding transient properties.

A certain amount of free electrons responds collectively to the laser field through intraband transitions, associated to one-electron excitation corresponding to interband transitions. Modelling this absorption stage is rather complex, particularly for ultrashort laser irradiation as it initiates a strong charge disorder. The consequence of a nonthermal electron-ion population on the electronic energy storage is also of major importance. Finally, thermal and mechanical transports are often described by the concept of "free carriers", since mobility is required for these processes. Electronic pressure has been seen to follow a free electron like behavior at high T e , even at solid density [START_REF] Bévillon | Free-electron properties of metals under ultrafast laser-induced electron-phonon nonequilibrium: a first-principles study[END_REF]. The electronic heat capacity C e plays an important role since it connects the quantity of absorbed energy to the rise of the electronic temperature of the system, regardless to energy dissipation processes. Electronic heat capacities have been derived from post-treatment of first-principles calculations where electronic excitation was not fully taken into account [START_REF] Lin | Temperature dependences of the electron-phonon coupling, electron heat capacity and thermal conductivity in Ni under femtosecond laser irradiation[END_REF][START_REF] Lin | Electron-phonon coupling and electron heat capacity of metals under conditions of strong electron-phonon nonequilibrium[END_REF]. Further, these quantities have been refined from density functional calculations dependent on the electronic temperature [START_REF] Bévillon | Free-electron properties of metals under ultrafast laser-induced electron-phonon nonequilibrium: a first-principles study[END_REF][START_REF] Sinko | Thermodynamic functions of the heated electron subsystem in the field of cold nuclei[END_REF].

In this paper, the electronic heat capacity of a series of transition metals is discussed in detail, first according to various modelling conditions, considering the effect of the exchange and correlation energy functionals and then the effect of semicore electrons. C e are then discussed in the framework of a free electron approach in order to evaluate the impact of d electrons of transition metals on this crucial thermodynamic quantity.

Calculation details

The modelling of Al, Ni, Cu, Au, Ti and W metals is performed with the code Abinit [START_REF] Gonze | ABINIT: First-principles approach to material and nanosystem properties[END_REF], which is based on plane-waves description of the wavefunctions. Calculations are carried out within the density functional theory [START_REF] Hohenberg | Inhomogeneous electron gas[END_REF][START_REF] Kohn | Self-consistent equations including exchange and correlation effects[END_REF] extended to finite electronic temperatures [START_REF] Mermin | Thermal properties of the inhomogeneous electron gas[END_REF]. Projector augmented-waves atomic data [20] are used to take into account the effects of nuclei and core electrons. A cutoff energy of 40 Ha is applied to restrict the number of plane-waves and the Brillouin zone is meshed with a 30 × 30 × 30 k-point grid using the Monkhorst-Pack method [START_REF] Monkhorst | Special points for Brillouin-zone integrations[END_REF]. The local density approximation (LDA) [START_REF] Perdew | Accurate and simple analytic representation of the electron-gas correlation energy[END_REF] and the generalized gradient approximations (GGA) [START_REF] Perdew | Generalized gradient approximation made simple[END_REF] are used with or without semicore electrons depending on the metals, in order to evaluate effects of semicore electronic states on computed properties. Computations are realized at the theoretical equilibrium lattice parameter of the crystal phase obtained at T i = 0 K. Thus, electronic temperatures from 10 -2 to 10 5 K are applied through a Fermi-Dirac distribution of electrons within a cold lattice. Such high T e are conjectural and interrogate about phase stabilities. As we need to achieve a high temperature asymptotic behavior in this study, we will assume here that time and spatial conditions are not fulfilled for phase transitions to occur.

The calculated electronic heat capacity is derived from the variation of the internal energy E with respect to the electronic temperature as C e = ∂E/∂T e . This thermodynamic quantity is computed for a series of metals at various T e using LDA or GGA functionals with or without semicore electrons. Results are provided in Fig. 1 alongside the values of Lin et al. obtained from electronic structures calculated at T e = 0 K [START_REF] Lin | Electron-phonon coupling and electron heat capacity of metals under conditions of strong electron-phonon nonequilibrium[END_REF]. At a first glance, the agreement between their results and ours is rather good for the low temperature range, the deviations appear at T e above 4 × 10 4 K, where electronic structures start to react significantly to the heating of the electronic subsystem. In particular, transition and noble metals having a d-block within their valence band are sensitive to Fermi smearing, impacting d electron population, that induces a change of the electronic screening which in turn produces a significant energy shift of the d-block [START_REF] Recoules | Effect of intense laser irradiation on the lattice stability of semiconductors and metals[END_REF][START_REF] Bévillon | Free-electron properties of metals under ultrafast laser-induced electron-phonon nonequilibrium: a first-principles study[END_REF]. At high temperature, this produces a significant effect on the band structure, with consequences on the electronic heat capacities. The effect of exchange and correlation functional appears to be weak on computed C e .

The LDA method generally provides lower equilibrium parameters than the GGA, leading to slightly higher electronic electronic heat capacities per unit of volume.

The effect of semicore electronic states are also evaluated and Fig. 1(f) shows clearly that 4 f semicore electrons of W have an impact at high T e . Despite the fact that the 14 f electrons lie on deep states, around 19 eV below the valence band, they are significantly impacted by the increase of T e starting from 4 × 10 4 K. For Al, Ni and Cu, the highest semicore electronic states correspond to 2p ones, they are located 50 eV below the valence band and are weakly impacted, even at high T e . Nevertheless, a small effect of semicore electronic states is noticeable, with stronger C e values for Al and Ni and lower values for Cu, compared to calculations where semicore states are not considered. With first semicore electronic states located at -27 eV for Ti, a significant effect of semicore electronic states is likely effective at high T e . A deeper investigation of the evolution of the electronic semicore states when T e increases shows that they are as sensitive as the d band to changes of the electronic screening. Depopulation or population of the d band with T e , induces either a decrease or an increase of the electronic screening which is signalled by changes of the Hartree energy, and which is effective on localized electrons of the system, from d electrons to semicore electrons. As an example, at 10 5 K the energy of the electronic semicore states are shifted for -3 eV for 2p 6 electrons of Ni, -8 eV for 2p 6 electrons of Cu, 2 eV for 2p 6 and -4 eV for 4 f 14 electrons of W. Semicore states are not shifted for Al, since this metal does not have a d block in its valence band. The shifts of these deep electronic states follow the changes of the electronic screening as discussed in Ref. [START_REF] Bévillon | Free-electron properties of metals under ultrafast laser-induced electron-phonon nonequilibrium: a first-principles study[END_REF]. This indicates that the evolution of the electronic screening, induced by changes of the electronic population of the d block, propagate to the localized charge density corresponding to semicore electronic states.

Nonetheless, due to the low energy of electronic semicore states and their corresponding electronic densities more localized around the nucleus, semicore electrons thermalize slower than valence electrons [START_REF] Fisher | Core holes, charge disorder, and transition from metallic to plasma properties in ultrashort pulse irradiation of metals[END_REF]. According to this consideration, the following part of this study relies on PAW atomic data without semicore electrons, at least when they are not needed for a good description of general properties. This implies that the GGA functional is used for Al, Ni, Cu and the LDA for Au, neglecting the effects of semicore electrons. For Ti and W, the GGA functional is used with semicore electrons but without the 4 f 14 electrons of W.

Electrons involved in C e

In the framework of a free electron model, C e has a linear behavior at low temperature that can be modelled by a low temperature limit C l e = π 2 N f n i k 2 B T e /2ε F and saturates at high temperature to a non-degenerate limit C h e = 3/2N f n i k B . Here, N f represents the number of free electrons per atom, n i the ionic density, k B the Boltzmann constant and ε F the Fermi level. In Fig. 2, C e is plotted for all the studied metals, and free electron like limits are presented at low and high temperatures. These limits are fitted to C e with an effective number of electrons N e f f e , provided in the figure, such as N f = N e f f e . At low temperature, the fit is performed up to an electronic temperature of 5 × 10 3 K, while at higher temperature, the corresponding number of electrons is a rough estimation since the asymptotic limit is not reached for most of the studied systems.

In order to facilitate the comparison between the number of effective electrons N e f f e required to fit C e and classical free electron numbers, their respective values are reported in Table 1. N f from Ref. [START_REF] Ashcroft | Solid State Physics[END_REF] are not designed to evolve with the increase of T e due to the rigid definition of this number, which is based on the most extended orbitals of the electronic configuration of the isolated atoms. On the contrary, temperature dependent N f (T e ) are obtained from extended-orbital overlapping considerations based on temperature-dependent electronic structure calculations [START_REF] Bévillon | Free-electron properties of metals under ultrafast laser-induced electron-phonon nonequilibrium: a first-principles study[END_REF], that allows electronic transfer between bands and Fermi-Dirac redistribution of electrons. Unsurprisingly, both free electron numbers remain quite close at low temperature, with a significant increase of N f (T e ) compared to N f when the temperature increases. This originates in the redistribution of electrons from localized d electronic states to delocalized electronic states of higher energies.

As expected, both low and high temperature approaches perfectly catch the limit behaviors of the free electron metal Al, with an effective number of electrons equals to 3, in agreement with the numbers of free electrons expected for this element. However, the number of effective electrons, needed to correctly fit the complex evolution of electron heat capacities of transition metals, can be very high and somewhat unrealistic. At low electronic temperature, an important gap is observed between N e f f e and expected N f for transition metals. For W, the number of effective electrons equals the number of electrons in the valence band, while for Ti N e f f e is even higher than available electrons in the valence band. Reducing the temperature interval where the fit is applied does not modify significantly N e f f e , except in the case of Ni where this number reaches 19 electrons to catch the particularly strong slope of C e at T e = 300 K [START_REF] Lin | Temperature dependences of the electron-phonon coupling, electron heat capacity and thermal conductivity in Ni under femtosecond laser irradiation[END_REF]. In all cases, N e f f e remains remarkably high compared to the number of free electrons classically used. Table 1. Typical free electron numbers N f from Ref. [START_REF] Ashcroft | Solid State Physics[END_REF] and temperature-dependent free electrons numbers N f (T e ) from Ref. [START_REF] Bévillon | Free-electron properties of metals under ultrafast laser-induced electron-phonon nonequilibrium: a first-principles study[END_REF], with estimated number of effective electrons N e f f e required to fit C e in the low and high temperature regimes. From the low temperature to the high temperature regime, N e f f e values evolve differently from a material to an other, remaining constant for Ni, Ti and W, while increasing for Cu and Au. These values still strongly exceed typical values of N f , even if the temperature dependence is considered, signalling a collective effect of d-electrons.

Al Ni Cu Au Ti

W T e = 5 × 10 3 K N f 3 2 1 1 2 2 N f (T e ) 3.

Discussion

The significant differences between N e f f e and the typical values of N f at low and high temperatures, demonstrate the inability of asymptotic limits derived from free electron approaches to grasp the complex behavior of transition metals, which relies on the presence of localized d electrons. Indeed, these localized electrons also contribute to the change of the electronic heat capacity, through the change of free energy in the system as T e increases. The electronic heat capacity informs about the amount of energy needed to rise the electronic temperature of a given system. The fast deviation toward high values of C e observed for transition metals, which is illustrated by values of N e f f e much higher than the classical values of N f , implies that the energy required to heat the localized d electrons is higher than the energy needed to heat free electrons. Moreover, non-linear evolution of N e f f e with the increase of T e also indicates a complex impact of d electron contribution to C e . Finally, previous studies showed that the change of d electron numbers with T e modifies the electronic screening that in turn induces an energy shift of the d-block affecting all localized d electrons [START_REF] Recoules | Effect of intense laser irradiation on the lattice stability of semiconductors and metals[END_REF][START_REF] Bévillon | Free-electron properties of metals under ultrafast laser-induced electron-phonon nonequilibrium: a first-principles study[END_REF]. Consequently, the effect of d electrons on C e has to be considered as a collective effect of the overall localized d electrons. Thus, the number of electrons to be considered in the electronic heat capacity limits at low and high temperature should be reevaluated, according to an activity coefficient applied to the different types of electrons:

N e f f e = α f N f + α d N d + α sc N sc ( 1
)
where N f represents the number of free electrons as defined before, N d = N v -N f is the number of d electrons, with N v being the number of valence electrons, and N sc is the number of semicore electrons. α i stands for the activity coefficient for each category of electrons. α f is set to the value of 1 for all metals as it corresponds to the free electron approaches. Since PAW atomic data used here exclude most of the semicore electrons and N sc is set to 0. Considering that N e f f e is equal to the values provided in Fig. 2 it is then possible to deduce the activity coefficients of d electrons for all the transition metals at low and high temperatures from α d = (N e f f e -N f )/N d . This is solved within a temperature dependence of free electron numbers and d electrons numbers that are presented in Table 2. The corresponding activity coefficients of d electrons are provided in Fig. 3.

As expected, α d for Al remains equal to 0 due to the absence of d electrons. For Ni, Cu and Au, the coefficient values are in the range of 0.2-0.5, with an increase for Cu and Au and a decrease for Ni when T e increases. These Table 2. Temperature-dependent free electron numbers N f (T e ) from Ref. [START_REF] Bévillon | Free-electron properties of metals under ultrafast laser-induced electron-phonon nonequilibrium: a first-principles study[END_REF] and corresponding number of localized d electrons N d (T e ) = N v -N f (T e ) in the low and high temperature regime. significant activity coefficients of d electrons -that applies on all localized d electrons -imply that the response of these electrons is strong, even when the Fermi smearing weakly affects them at low temperature, as for Cu and Au. On the contrary, α d reach high values for Ti and W, around 2 and 1 respectively and slowly evolve with T e . The strong values obtained for Ti and W originate from the fact that the Fermi level lies within the d block, even when T e increases. Excitation effects directly involves population or depopulation of localized d electronic states with strong impact on C e . With a Fermi energy located on the top of the d block at low electronic temperature, a similar effect should also be observed for Ni, but this is actually hidden by the fit on large range of electronic temperatures. As we will see later, this phenomenon becomes visible when the fit is performed at lower temperatures. For W, once α d is obtained from calculations that neglect the effect of semicore electrons, it is then possible to use this value to derive α sc from the C e curve obtained by taking into account the 4 f 14 electrons (GGAsc curve in Fig. 1(f)). This leads to a new fit in the high temperature limit, with N e f f e being equal to 9. Accordingly, α sc equals to 0 at low temperature and reaches the value of 0.2 at high temperature, confirming the effect of these electrons on C e , assuming they are thermalized.

Since C e is supposed to evolve linearly in the low temperature regime, it is often characterized by the electronic heat capacity coefficient γ = C e /T e . Values at 5 × 10 3 K are provided in Table 3, where a relative good agreement is found between calculated values and the low temperature free electron limit γ l based on N e f f e . However, for Ni the linear evolution of C e is not respected, and a strong change of the slope occurs at low temperature. At T e equals to 300 and 10 3 K, the corresponding γ values reach 1183.3 and 631.1 J K -2 m -3 respectively. In the low temperature limit, this involves very high values of N e f f e , 19 and 10 respectively, leading to activity coefficients of d electrons of 2.1 and 1.0 respectively. This strong change of C e slope at low temperature corresponds to a major difference in the behavior of Ni compared to Cu and Au. This difference of behavior originates from the position of the Fermi level, at the top of the d block for Ni while it is higher for Cu and Au, due to difference in their number of valence electrons. Thus, at low temperature, depopulation of the d block is direct for Ni, while the d block is not impacted yet for Cu and Au. When T e increases, the Fermi level shift toward energies higher than the d block for both elements, inducing a strong changes of α d in case of Ni, that progressively tends toward the values of Cu and Au. As in the case of Ti and W, a direct impact of the Fermi smearing on the d block has a strong effect on C e which is signalled by important activity coefficient of localized d electrons. To a lower degree, a similar deviation is observed for Ti around T e = 10 3 K, with a γ coefficient reaching the value of 466.3 J K -2 m -3 . This is fitted by a value of N e f f e equals to 8 and leads to an even higher α d with the value of 2.5. For these elements, the non-linear evolution of C e at low electronic temperatures leads to strong modifications of subsequent derived quantities. Thus, beyond these general observations, the evolution of these activity coefficients remains difficult to be evaluated accurately and values cannot be extrapolated to other elements or temperature regime.

Conclusion

In this paper, the electronic heat capacities are obtained from first-principles calculations performed at finite electronic temperatures. The effect of exchange and correlation functional on this thermodynamic quantity is first discussed. At high electronic temperature a small difference is observed between LDA and GGA functionals that was attributed to different equilibrium lattice parameters. The impact of semicore electrons, is also tested and demonstrated at high temperature for 4 f 14 electrons of tungsten. This is dependent on the energy depth of the corresponding semicore electronic states and is mostly negligible even at high temperatures, except for W. Assuming negligible effects or lower thermalization times for these electrons, effect of semicore electrons were neglected in the present study. Electronic heat capacities are also compared to previous theoretical predictions obtained from electronic structures not relaxed with the electronic temperature, with a very good agreement up to 4 × 10 4 K. Beyond this temperature, the response of the electronic structure exhibits differences.

The obtained electronic heat capacities are then discussed in the framework of low and high temperature limits of a free electron approach. Both are based on a free electron number, which is modified up to an effective number of electrons in order to fit the theoretical values of C e . This approach applies correctly to Al as a free electron metal, but a significant overestimation of free electron numbers is found for the transition metals. Assuming a collective contribution of localized electrons on the C e evolution, d electrons where considered associated to an activity coefficient. The high values obtained for this coefficient tend to corroborate the fact that d electrons respond collectively to the electronic excitation. A strong effect is observed from the impact of Fermi smearing on d electrons, as showed for Ni at low temperature and Ti and W in the whole range of temperature. For W, at very high temperature, an important contribution of semicore electrons 4 f is also deduced from this approach, assuming that they are thermalized. At high temperature, the change of the electronic screening is found to affect significantly the localized d electrons, with a global shift of the d-block, strengthening the collective behavior of these electrons.

Additionally, the non-linear effect of d electrons, which is shown by an important dispersion of their activity coefficient, illustrates their non-free behavior and their interactive nature. The large numbers of electrons needed to fit C e evolution in the low and high temperature regime is a signature of localized electron influence, mostly d electrons but also semicore electrons at very high temperature. Consequently, an unique free electron number cannot encompass the complex evolution of the electronic heat capacity and localized electrons, especially d ones, have to be considered. This shows that the free electron number is only one of the components on the energy storage of an irradiated material, and that localized electrons contribute as well, to various degrees depending on the electronic temperature.

T e = 5 ×

 5 10 3 K T e = 10 5 K N f (T e ) N d (T e ) N f (T e ) N d (T e

Figure 1 .Figure 2 .Figure 3 .

 123 Figure 1. (Color online) Evolution of the electronic heat capacity with T e for Al (a), Ni (b), Cu (c), Au (d), Ti (e), W (f), using different LDA and GGA exchange and correlation functionals. GGAsc and LDAsc indicate that the effect of semicore electrons are taken into account. The dotted black curves represent data of Lin et al. [14].

Table 3 .

 3 Coefficient of electronic heat capacity (γ = C e /T e , J K -2 m -3 ), at 5 × 10 3 K.

		Al	Ni	Cu	Au	Ti	W
	γ 110.4 320.0 243.9 141.1 340.9 266.8
	γ l	96.2 309.3 262.5 172.8 328.7 342.2

Acknowledgments

This work was supported by the ANR project DYLIPSS (ANR-12-IS04-0002-01) and by the LABEX MANUTECH-SISE (ANR-10-LABX-0075) of the Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). Numerical calculations have been performed using resources from GENCI, project gen7041.


Konstantin Avrachenkov
email: konstantin.avratchenkov@inria.fr

Giovanni Neglia
email: giovanni.neglia@inria.fr

Vikram Vikas

Singh

Network Formation Games with Teams

Keywords: Network Formation Games, Teams, Network stability, AS Network Les Jeux, Stabilité du Réseau, Réseau AS

Network formation games have been proposed as a tool to explain the topological characteristics of existing networks. They assume that each node is an autonomous decision-maker, ignoring that in many cases different nodes are under the control of the same authority (e.g. an Autonomous System) and then they operate as a team. In this paper we introduce the concept of network formation games for teams of nodes and show how very different network structures can arise also for some simple games studied in the literature. Beside extending the usual definition of pairwise stable networks to this new setting, we define a more general concept of stability toward deviations from a specific set C of teams' coalitions (C-stability). We study then a trembling-hand dynamics, where at each time a coalition of teams can create or sever links in order to reduce its cost, but it can also take wrong decisions with some small probability. We show that this stochastic dynamics selects in the long run C-stable networks or closed cycles as the error probability vanishes.

Introduction

Network formation games are nowadays a consolidated branch of game theory (see for example the recent books [START_REF] Dutta | Networks and Groups: Models of Strategic Formation[END_REF], [START_REF] Demange | Group Formation in Economics: Networks, Clubs, and Coalitions[END_REF], [START_REF] Jackson | Social and Economic Networks[END_REF], [START_REF] Goyal | Connections: An Introduction to the Economics of Networks[END_REF]). They study which networks' structures arise when nodes are selfish rational players, who can sever or create some links in order to increase the utility they perceive from the network. In particular, it is usually assumed that each node can unilaterally sever a link to one of its neighbors, while the creation of a new link requires the approval of both the participating nodes. This idea has lead to the concept of pairwise-stable networks, i.e. networks for which every existent link is beneficial to both the connected nodes and every inexistent link is not beneficial to at least one of the two nodes it would connect. Different dynamics for links' creation/destruction have been studied. Specific network formation games have been proposed to explain the topological characteristics of existing networks, including the Autonomous Systems' (ASs') network taking for example into account both costs for routing traffic and for a lack of end-to-end connectivity [START_REF] Corbo | An economically-principled generative model of AS graph connectivity[END_REF], [START_REF] Anshelevich | Strategic network formation through peering and service agreements[END_REF], [START_REF] Johari | A contract-based model for directed network formation[END_REF]. They also have been used to investigate the distributed formation of overlay topologies on top of the Internet [START_REF] Elias | A game theoretic analysis of network design with socialy-aware users[END_REF], or routing topologies among relay stations in future cellular networks [START_REF] Saad | Network formation games among relay stations in next generation wireless networks[END_REF], or among nodes in multi-hop wireless networks to prevent eavesdropping [START_REF] Saad | Network formation games for wireless multi-hop networks in the presence of eavesdroppers[END_REF].

Network formation games consider that each node is an autonomous decision-maker, ignoring that in many cases different nodes are under the control of the same authority (e.g. an AS) and then they constitute a team. We observe that by introducing teams in a simple network formation game proposed in [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF], gives different stable network structures. This motivates us to study network formation games with teams and define new stability notions for this new class of games. To the best of our knowledge this paper is the first to introduce teams in network formation games and aims to open a new interesting research direction. Although, the concept of teams in game theory has been studied before in different contexts. For instance, there is a recent work on team formation games by Boncinelli and Pin [START_REF] Boncinelli | Efficiency and stability in a process of teams formation[END_REF], where each agent can be the part of different teams that are involved in specific projects.

Our first contribution is then to define network formation games for teams of nodes and define teampairwise stability analogous to pairwise stability in standard network formation games. The second contribution of our paper is to provide a more general concept of stability toward the deviations from a specific set C of teams' coalitions (we talk then about C-stability). This idea can capture the fact that some groups of teams are more likely to cooperate than others. For example, ASs located in far-away regions may have no incentive to connect directly. Apart from above static stability notions we also consider the dynamic formation of networks in the presence of trembling (mutations). We then discuss the dynamic stability notion called as stochastic stability for networks, i.e., which networks are selected by the dynamics as trembling vanishes. So, as a final contribution we define a general trembling-hand dynamics for which we prove that only C-stable networks or closed cycles are selected with non-zero probability on the long term when the trembling vanishes. Jackson and Watts [START_REF] Jackson | The evolution of social and economic networks[END_REF] are the first ones to consider trembling-hand dynamics in standard network formation games for the case of pairwise interaction between nodes.

The paper is organized as follows. We start providing the basic definitions for network formation games with teams in Section 2. Then, in Section 3 we provide a simple network formation game proposed in [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF] showing that different network structures arise in the presence of teams. We move then to introduce the general concept of C-stability and our trembling-hand dynamics in Section 4. We show some numerical results for specific games in Section 5. Finally, we conclude our paper in Section 6.

Network Formation Games with Teams: basic definitions

In this section we define network formation games for teams and we start extending some usual concepts for network formation games to our setting. In particular we define the notion of team-pairwise stability to characterize meaningful equilibria.

Let

N = {1, 2, • • • , n} be a finite set of nodes. Let P = {T 1 , T 2 , • • • , T m }, m
≤ n be a partition of N . Undirected edges can be formed both between nodes belonging to the same set T i (called internal links) as well as belonging to different sets T i and T j (called external links). The edge between nodes k and l is denoted by kl. We say that there is a link between T i and T j if there is at least one link kl with k ∈ T i and l ∈ T j . The collection of edges defines a network g.

The cost of each set T i (c(T i , g)) depends in general on the structure of the whole network g. In usual network formation games, each node k has its own cost c k (g). In network formation games with teams we consider that nodes belonging to each set T i share the same cost c(T i , g). As a consequence, they will form or sever links only if this is beneficial for the whole set T i , i.e. if the cost of T i is reduced. For this reason we refer to each T i i = 1, 2 . . . , m as a team. In particular, nodes in a team will agree to create an internal link kh with k, h ∈ T i , if c(T i , g + kh) < c(T i , g), and will agree to sever an internal link kh if c(T i , g -kh) < c(T i , g). This leads to following definition of internal stability: Definition 2.1 (Internal stability). A network g is internally stable in team T i if no further link can be created or severed within the nodes from T i , i.e., if g is a network which is obtained from g via the addition of new links within the nodes of T i or destruction of existing links within the nodes of T i then c(T i , g ) > c(T i , g). A network is internally stable if it is internally stable in all the teams.

The destruction of an external link is unilateral: any of the two nodes can sever the link if this is beneficial for its team. On the contrary, the creation of an external link requires the agreement of both the teams involved, as it is often considered in literature. The link will then be created only if it does not increase the cost of any of the two teams and it decreases the cost of at least one of them. These link formation rules leads to the following notion of equilibria for network formation games with teams: Definition 2.2 (Team-pairwise stability). A network g is said to be team-pairwise stable if 1. g is internally stable, and 2. for all pair (T i , T j ) if kl ∈ g, k ∈ T i and l ∈ T j then c(T i , g) ≤ c(T i , g-kl) and c(T j , g) ≤ c(T j , g-kl), and 3. for all pair (T i , T j ) if kl / ∈ g, k ∈ T i and l ∈ T j and if c(T i , g + kl) < c(T i , g) then c(T j , g + kl) > c(T j , g).

Network Creation Game with Teams: A Motivating Example

We introduce teams in a network creation game considered by Corbo and Parkes [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF] and we observe that some different stable network structure arises even for very simple cases. This shows the usefulness of new stability notions defined in Section 2 and it is worth studying this new class of network formation games. In this section we use the cost function given in [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF]. But, in Section 2 and in general in the whole paper we consider the general cost function unless mentioned otherwise.

Fabrikant et al. [START_REF] Fabrikant | On a network creation game[END_REF] introduced a network creation game where each node can add as well as sever links unilaterally. While in network creation game by Corbo and Parkes [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF] the link creation is bilateral and link destruction is unilateral. We consider network creation game by Corbo and Parkes because we are interested in pairwise interaction among teams. First we give the description of the bilateral network creation game given in [START_REF] Corbo | The price of selfish behavior in bilateral network formation[END_REF]. Let N = {1, 2, • • • , n} be a finite set of players (nodes). The action set of player i is A i = 2 N -{i} , i.e., each player chooses a subset of players with whom he wants to create a link. For each i ∈ N , the action set A i can be represented as A i = {(a ij ) j =i |a ij ∈ {0, 1}}. Player i seeks contact with player j if a ij = 1. Player i and player j are connected with a link if a ij = a ji = 1. Let a i = (a ij ) j =i denotes an action of player i and |a i | = j =i a ij which is the number of connections player i establishes with other players. Players simultaneously announce the list of the players with whom they wish to be connected. Each action profile a = (a i ) n i=1 gives an undirected network g(a). The shortest distance between nodes i and j in a network g(a) is defined as the minimal number of hops along a path connecting them and it is denoted by d g(a) (i, j). At action profile a the cost incurred by player i is

c i (a) = α • |a i | + j∈N ;j =i d g(a) (i, j), (1)
The above cost function implies a sunk cost for player i for provisioning for links that may not actually form (since the link formation is bilateral). It is clear that the sunk cost is absent at equilibrium. At Inria network g if ij ∈ g then both the nodes i and j incur cost α for creating this link, i.e., the total cost of creating the link ij is 2α. The cost of a network g is the sum of the cost of all its nodes. A network g is said to be efficient if the cost of g is minimum among all the networks. Corbo and Parkes showed that for α < 1 the complete network is unique efficient and pairwise stable network and for α > 1 the star network is only efficient network which is also pairwise stable but not unique. We consider the network creation game defined above. We assume that the nodes are divided into disjoint sets {T i } m i=1 and the cost of a link between two nodes from a same set is α and the cost of a link between two nodes from different sets T i and T j is 2α, i.e., there is a cost heterogeneity among links. Let the nodes from each set form a team. So, each team incurs cost α for forming internal links and also incurs cost α for forming external links. For a given network g the cost of a team T i is defined as

c(T i , g) = α E(T i ) + Tj ∈P j =i E(T i T j ) + k∈Ti j∈N j =k d g (k, j), (2)
where E(T i ) is the total number of internal links of T i and E(T i T j ) is the total number of external links between T i and T j . The cost of a network g is defined as the sum of the cost of all the teams. For illustration purpose, let us first consider a simple case when 1 < α < 2 and see which network is a team-pairwise stable and whether that network is also pairwise stable if there are no teams. Proposition 3.1. Consider a bilateral network creation game with teams and 1 < α < 2, then a network g is internally stable if all the nodes from each team form a complete network internally.

Proof. We prove this result by contradiction. Let g be an internally stable network. Assume that there exist a team T i whose nodes do not form a complete network internally, i.e., there exist two nodes k and l such that they do not have a link between them. Let g = g + kl, the cost of team T i at g is increased by α due to the creation of link kl but the cost is reduced by at least 2 > α units due to the distance between k and l, so c(T i , g ) < c(T i , g). This implies that g is not internally stable in T i which gives a contradiction. Hence, at internally stable network the nodes of each team form a complete network internally.

Similarly to the star network in standard network formation games, we define a star network at team level which we call as a team-star. A network is a team-star if each team has at least two nodes and all the nodes of each team form a complete network internally and there is a central team with a node called central node such that all the nodes of other teams are connected to the central node.

Proposition 3.2. A team-star network is a team-pairwise stable in a bilateral network creation game with teams but it is not a pairwise stable if each node is an independent rational player.

Proof. Let g be a team-star network, then by definition g is internally stable. From the definition of g it is clear that the distance between any two nodes of g is at most 2. Now consider a pair of non-central teams (T i , T j ) then both teams have no incentive to create a link between them because it will cost each team α > 1 but their cost due to distance can be reduced only by 1. Now consider a pair of teams (T i , T j ) such that T i is the central team then consider a link kl between a central node k of T i and a node l of T j then this link cannot be deleted by both the teams because the cost of both the teams get reduced only by α but the cost due to distance is increased by at least 2 > α. No further links between a node of T i other than central node k and a node of T j can be added because it will increase the cost by α > 1 but the cost due to distance is reduced only by 1. So, team-star is a team-pairwise stable.

Assume that there are no teams, i.e., the nodes belonging to each set T i , i = 1, 2, • • • , m is an independent player. Then the network g is not a pairwise stable because the central node k from the central set T i will form maximum one link from each set T j , j = i. Remark 3.3. Introducing teams in a standard network formation game leads to a team-pairwise stable network which is not a pairwise stable network even for very simple cases. Now there is an interesting question: which network is pairwise stable when nodes belonging to sets {T i } m i=1 do not form a team. To get an idea how a pairwise stable network looks like, we consider an instance of bilateral network creation game with 9 nodes that are divided into 3 sets, i.e., N = {1, 2, 3, 4, 5, 6, 7, 8, 9} and T 1 = {1, 2, 3}, T 2 = {4, 5, 6}, T 3 = {7, 8, 9}. The team-star network given in Figure 1 is a team-pairwise stable but not pairwise stable from Proposition 3.2. A pairwise stable network in this case when nodes from T 1 , T 2 and T 3 does not form a team is given in Figure 2. The cost of the team-star network from Figure 1 is c(team-star) = 21α + 114 and the cost of network g from Figure 2 is c(g) = 27α + 108. It is easy to check that for α > 1, c(team-star) < c(g). For these simple cases of network creation game the introducing teams give us a team-pairwise stable network which is not a pairwise stable and it is more efficient than a pairwise stable network. This shows that in general introducing teams in standard network formation games may give team-pairwise stable networks which are completely different from pairwise stable networks and more efficient. Unlike in team-pairwise stability where at a time only one link between two teams can be changed we consider a general situation where two or more teams form a coalition and they can make all possible changes in a given network by creating new links or severing existing links in such a way that a resulting network is at most as costly, for all the teams that are the part of the coalition, as in the current network and there exists at least one team whose cost is strictly less. We define the stability concept of networks against the deviation of teams' coalitions. In some situations, it may not be possible to form all types of teams' coalitions, e.g. some ASs may not form coalition due to geographical constraints, so, let C ⊂ 2 P denotes the set of all possible teams' coalitions. Under this constraint on the coalition formation there will be a restriction on the set of all possible networks, e.g., if there exists a pair of teams such that both of them cannot be the part of a coalition together, then there cannot exist a link between them. Let G(C) be the set of all possible networks. The stability notions against the deviation of coalitions in the standard network formation games has been considered in literature before (see [START_REF] Jackson | A strategic model of social and economic networks[END_REF], [START_REF] Jackson | Strongly stable networks[END_REF]). Definition 4.1. A network g is obtainable from g via deviation by a coalition S ∈ C as denoted by g → S g , if 1. kl ∈ g and kl / ∈ g such that k ∈ T i and l ∈ T j , then {T i , T j } ⊂ S.

2. kl ∈ g and kl / ∈ g such that k ∈ T i and l ∈ T j then {T i , T j } ∩ S = φ.

Inria

The condition (i) of above definition requires that new links can be added only between the teams which are the part of a coalition S. The condition (ii) requires that at least one team of any deleted link has to be the part of S. We denote G(S, g) as a set of all networks which are obtainable from g via deviation by S, i.e., G(S, g) = {g ∈ G(C)|g → S g }.

Definition 4.2. A deviation by a coalition S from a network g to a network g is said to be improving if 1. g → S g , 2. c(T, g ) ≤ c(T, g), ∀ T ∈ S (with at least one strict inequality).

We denote G f (S, g) as a set of all networks g which are obtainable from g by an improving deviation of S, i.e.,

G f (S, g) = g ∈ G(S, g)|c(T, g ) ≤ c(T, g), ∀ T ∈ S, c(T , g ) < c(T , g) for some T ∈ S .
It is clear that g / ∈ G f (S, g). We denote G nf (S) = G(S, g) \ G f (S, g) is the set of networks g which are obtainable from g by taking the wrong decision and it is always nonempty because g ∈ G nf (S, g) for all S ∈ C.

Definition 4.3. A network g ∈ G(C) is C-stable if it
is not possible for any coalition S ∈ C to make an improving deviation from a network g to some other network g .

A C-stable network need not always exist and in that case there exist some set of networks lies on a closed cycle and all the networks in a closed cycle can be reached from each other via an improving path. We next give the definitions of an improving path and closed cycle.

Definition 4.4 (Improving Path

). An improving path from g to g is a sequence of networks and coalitions

g 1 , S 1 , g 2 , • • • , g n-1 , S n-1 , g n such that g 1 = g, g n = g and g k+1 ∈ G f (S k , g k ) for all k = 1, 2, • • • , n -1.
Definition 4.5 (Closed Cycles). A set of networks Q form a closed cycle if for any g, g ∈ Q there exists an improving path connecting g and g and no network in Q lies on an improving path leading to a network that is not in Q.

Theorem 4.6. There exists at least one C-stable network or a closed cycle of networks.

Proof. The proof follows in similar lines to the proof given in [START_REF] Jackson | The evolution of social and economic networks[END_REF] for pairwise stable network. Now, we consider a situation where networks are formed dynamically over time. Since, at each time teams are allowed to form a coalition and they can make all possible changes in a given network, so we consider the network formation rules by Jackson and van den Nouweland [START_REF] Jackson | Strongly stable networks[END_REF] as given below:

• Link addition is bilateral, i.e., forming a link between the teams T i and T j requires the consent of both teams.

• Link destruction is unilateral, i.e., severing a link between the teams T i and T j requires the consent of team T i or team T j .

• At a time more than one link can be created and severed by the teams.

Jackson and Watts [START_REF] Jackson | The evolution of social and economic networks[END_REF] considered dynamic formation of networks in standard network formation games without teams, where at each time only a pair of players are selected and only a link between them can be changed.

A Stochastic Dynamic Process

We consider a situation where at each time t = 1, 2, • • • a group of teams form a coalition and discuss whether it is possible to make some changes in a current network such that at resulting network the cost of each team in the coalition is at most as much as it is in the current network and at least one team has strictly less cost. The selected coalition makes a move to such an improving network from a current network. If there are more than one improving networks for selected coalition then the probability of selection of each improving network is positive. That is the above dynamics is stochastic. If there are no improving networks that can be reached by a selected coalition then at next stage the network will be same. The same thing repeats at next stage and this continues for infinite periods. We assume that the coalition formation is random and at a time only one coalition can be formed. We assume that at each time a selected coalition makes some error in calculation whether making a move is at most as costly as before for all the teams in the coalition with at least one team has strictly less cost. This happens with small probability that depends on the size of the coalition. As a consequence at next stage there will be a network with small probability at which all the teams in the coalition are not better off. Here we study the evolution and persistence of network in the long run when the probability of error tends to zero. The above situation can be modeled as a Markov chain over the set of networks G(C). We first consider the case when coalition of teams does not make error over time and in that case we have unperturbed Markov chain. Next, we consider the case where at each time selected coalition makes error with small probability. So, in this case there will be a perturbed Markov chain. We first assume that coalition does not make mistakes, i.e., at each time t = 1, 2, • • • , a coalition S t ∈ C is randomly selected with probability p St > 0 who can make all the possible improving deviations from the current network g t . As a consequence at time t + 1 the network is g t+1 ∈ G f (S t , g t ) with probability p f (g t+1 |S t , g t ). If it is not possible to make an improving deviation by a coalition S t then g t+1 = g t . The transition law P 0 of the Markov chain over finite set G(C) is defined as:

P 0 (g |g) = S∈C;G f (S,g) =φ p S p f (g |S, g)1 G f (S,g) (g ) + S∈C;G f (S,g)=φ p S 1 {g =g} (g ), (3)
where p f (•|S, g) is a probability measure over G f (S, g) and 1 B (•) is an indicator function on a given set B. It is clear that aC-stable network is an absorbing state and a closed cycle is a recurrent class of P 0 that contains more than one network. Now, we assume that at each time t, there is an error made by a coalition S t with small probability. This adds mutations as well as another level of stochasticity in the dynamics. The chance of making error by a coalition increases with its size because the number of possible network choices for coalition increases with its size. We assume that coalition S t makes error with |S t |ε probability for sufficiently small 0 < ε < In the situation where there is no improving move by coalition S t , the network g t+1 = g t with probability 1 -|S t |ε and g t+1 ∈ G nf (S t , g t ) \ {g t } with probability |S t |εp nf \gt (g t+1 |S t , g t ). If G nf (S t , g t ) = {g t }, which arises when S t has single team with only one node which is isolated in the network g t , then g t+1 = g t . The transition law P ε of the perturbed Markov chain of P 0 is defined as below:

P ε (g |g) = S∈C;G f (S,g) =φ p S (1 -|S|ε)p f (g |S, g)1 G f (S,g) (g ) + |S|εp nf (g |S, g)1 G nf (S,g) (g ) + S∈C;G f (S,g)=φ,|G nf (S,g)|>1 p S (1 -|S|ε)1 {g =g} (g ) + |S|εp nf \g (g |S, g)1 G nf (S,g)∩{g =g} (g ) + S∈C;G f (S,g)=φ,|G nf (S,g)|=1 p S 1 {g =g} (4)
for all g, g ∈ G(C), where p nf (•|S, g) is a probability measure over set G nf (S, g) and p nf \g (•|S, g) is a probability measure over set G nf (S, g) \ {g}.

The Markov chain P ε is irreducible because given nonzero mutations it is possible to reach all the networks starting from any network in finite steps. It is also aperiodic because with positive probability Markov chain makes self transition. Hence, there exists a unique stationary distribution µ ε of Markov chain P ε . We are interested in the networks to which stationary distribution µ ε assigns positive probability as ε → 0. This leads to the definition of stochastic stability: Definition 4.7. A network g is stochastically stable relative to process P ε if lim ε→0 µ ε g > 0. If P ε (g |g) > 0 then we define one step resistance from network g to g , which is denoted by r(g, g ), as minimum number of mutations which are required for Markov chain to make a transition from g to g in one step. From (4) it is clear that the transition from a network g to g has the probability of order ε if g / ∈ G f (S, g) for all S and thus has resistance 1 and is of order 1 otherwise, so has resistance 0, i.e., r(g, g ) ∈ {0, 1} for all g, g ∈ G(C). A zero resistance between two nodes corresponds to transition with positive probability under P 0 . Since P ε is an irreducible Markov chain then there must exist at least one directed path between any two recurrent classes G i and G j of P 0 which starts from G i and ends at G j . The resistance of any path is defined as the sum of the resistances of the corresponding edges. The resistance of an edge in a directed path represents one step resistance from starting network to end network of an edge. The resistance of a path which is minimum among all paths from G i to G j is called as resistance from G i to G j and it is denoted by r ij . The resistance from any network g i ∈ G i to any network g j ∈ G j is r ij because inside G i and G j networks are connected with a path of zero resistance. Now we recall the concept known as stochastic potential of a recurrent class G i of P 0 from [START_REF] Young | The evolution of conventions[END_REF]. Construct a graph G where total number of nodes are the number of recurrent classes of P 0 (one network from each recurrent class) and a directed edge from g i to g j is weighted by r ij . Take a node g i ∈ G and consider all the spanning trees such that from every node g j ∈ G, g j = g i , there is a unique path directed from g j to g i . Such spanning trees are called as g i -trees. The resistance of a g i -tree is the sum of the resistances of its edges. The stochastic potential of g i is the resistance of a g i -tree having minimum resistance among all g i -trees. The stochastic potential of each node in G i is same [START_REF] Young | The evolution of conventions[END_REF], which is a stochastic potential of G i . Theorem 4.8. A stochastically stable network is either a C-stable network or a closed cycle having minimum stochastic potential.

Proof. We know that the Markov chain P ε is aperiodic and irreducible. From (3) and (4) it is easy to see that lim ε→0 P ε (g |g) = P 0 (g |g), ∀ g, g ∈ G(C).

From (4) it is clear that, if P ε (g |g) > 0 for some ε ∈ (0, ε 0 ], then we have

0 < ε -r(g,g ) P ε (g |g) < ∞.
So, Markov chain P ε is a regular perturbed process because it satisfies all three conditions given in [START_REF] Young | The evolution of conventions[END_REF]. Hence it follows from Theorem 4 of Young [START_REF] Young | The evolution of conventions[END_REF] that as ε → 0, µ ε converges to a stationary distribution µ 0 of P 0 and a network g is stochastically stable, i.e., µ 0 g > 0 if and only if g is contained in a recurrent class of P 0 having minimum stochastic potential. We know that the recurrent classes of Markov chain P 0 are C-stable networks or closed cycles. So, a stochastically stable network is either a C-stable network or a closed cycle having minimum stochastic potential.

Strong stability

We consider the case where there are no restrictions on the formation of teams' coalitions, i.e., C = 2 P . In this case C-stability is called as strong stability which is analogous to strong stability in standard network formation games [START_REF] Jackson | Strongly stable networks[END_REF].

Corollary 4.9. All the strongly stable networks and closed cycles are stochastically stable.

Proof. Since, we have no restrictions on the coalition formation, then all types of networks are possible to form among teams. Now, the recurrent classes of P 0 are the strongly stable networks or the closed cycles. From Theorem 4.8 a stochastically stable network is either a strongly stable network or a closed cycle having minimum stochastic potential. The resistance between any two distinct classes G i and G j is always 1 because under P ε it is always possible to reach one network from another network by at most one mutation when all types of teams' coalitions are allowed. Then the resistance of each g i -tree is J -1, where J is the total number of recurrent classes of P 0 . Hence, the stochastic potential of each recurrent class of P 0 is J -1. So, from Theorem 4.8 all the strongly stable networks and closed cycles are stochastically stable.

Simulation Results

In the previous section we have characterized which networks are selected on the long run by the usual trembling-hand network dynamics, when the error probability ε converges to 0. Studying the dynamics itself for a finite ε is a harder problem, so we resort to simulations to investigate i) which networks appear more frequently during the dynamics and ii) which quasi-stable networks arise and how fast. By quasistable networks we mean networks that appear for a long period of time before a random error let them disappear. We cannot be sure that such networks are indeed stable with respect to the set of coalitions we consider in the specific experiment (in general only a direct inspection of all the possible deviations could reach such conclusion). Nevertheless, specially for larger values ε quasi-stable networks can appear over time durations comparable with those of stable networks, so that practically speaking, they are as important as stable networks. The dynamics clearly depends on the value of ε, but also on the specific set C of coalitions we consider: we are going to explore the effect of both.

As case study, we consider a simple instance of the bilateral network creation game with teams defined in Section 3. Let the set of nodes be N = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Nodes are split in three teams, T 1 = {1, 2, 3}, T 2 = {4, 5, 6} and T 3 = {7, 8, 9}. The cost of link creation is α = 1.5. For any experiment the initial network topology is selected uniformly at random among all the possible networks. Moreover, for any set C considered in the experiments, every coalition in C is equally likely to be selected at any iteration, i.e., for all t, p St = 1

|C| for every S t ∈ C. Also the probability measures over the set G f (S t , g t ) and G nf (S t , g t ) are uniform, i.e., any network g ∈ G f (S t , g t ) is equally likely to be selected as an improving deviation at any iteration and any network g ∈ G nf (S t , g t ) is equally likely to be selected when coalition S t makes error at any iteration. We know that in this game at internally stable network all the teams form a complete network internally. So, in the dynamics we update the networks in such a way that the internal stability of networks is preserved.

The case of all coalitions

Here we consider the case where all the 7 coalitions are allowed to form. We start considering a very small error probability ε = 0.00001. Figure 3 shows the time-evolution of the cost of the network selected by the dynamics. After less than 1000 iterations, the cost reaches a constant value equal to 145.5, that is the cost of the team-star network for this specific value of α. The curve then suggests that the network dynamics has selected (very fast) a quasi-stable network and that this network may be a team-star. An inspection of the topologies of the networks selected show that this is actually the case: the dynamics reaches a specific team-star network and then nothing changes until the end of the simulation. Note that we do not know if the team-star is stable with respect to the set of all the possible coalitions, but this experiment (and many others we carried on) suggest that this is the case, because we never observed an improved deviation.

Next, we consider the case of much higher error probability ε = 0.01. We can see from Figure 4 that the evolution of network cost is now very noisy, this is clear because the dynamics jumps to a random network on average every 100 iterations, then the network cost usually decreases because of improving deviations selected by the coalitions until the next error occurs that leads the dynamics to a new random network whose cost is in general higher. Even a stable network would not survive for a long time because of the high error probability. Figure 5 shows the empirical distribution of network costs observed during the simulation. The network dynamics visits now more often networks whose cost is higher than the cost of the team-star. We checked some of these networks which appear more frequently and none of them was stable. In particular, for all of them, the team-star was an improving deviation for the grand coalition. One could then wonder why these networks appear more often than the team-star during the dynamics. The reason behind is that such networks appear in much more "forms" than team-star. In fact there are only 9 team-star networks (in each of them a different node is the center of the star). For example some of the networks appearing more frequently are team-stars with a few more links. There are many different ways to place such extra links in order to have a network with the same cost. Said in other words, the classes of isomorphic networks have different sizes, and frequency with which a representant of the class appears during the network dynamics depends on its stability versus deviations but also simply on the size of the class.

Without the grand coalition

Here we consider the case where the grand coalition cannot form, but only the coalitions of size up to 2 can be formed. We first consider ε = 0.00001. In Figure 6 we observe first an evolution similar to that in Figure 3 with the network dynamics selecting very fast a team-star, but in this case an error after the 70000-th iteration produces a restart. Interestingly, after the restart, the cost reaches a constant value equal to 146.5. In this case the constant cost hides in reality a continuously changing topology. In fact, there are multiple networks with cost 146.5 which can be obtained one from the other by improving deviations from a coalition of size 2 and this is actually what is happening in this simulation. After the second random start, the dynamics keeps selecting different networks but all with the same cost. These networks are not even quasi-stable according to our definition, but from the point of view of the global cost, the situation does not change. As a final remark, we checked that also for these networks the team-star is an improving deviation, but it can only be enforced by the grand coalition, which is not For the larger error probability = 0.01 the dynamics appear to be similar to those when all the coalitions can be selected.

Only single team coalitions

We now move to the case where only coalitions with a single team are considered. Note that the creation of an external link requires a coalition of the two teams, that is excluded here. Hence the only possible change in this case is due to team severing links to other teams if it is beneficial for them or because of a random error. As soon as one of the team will be disconnected from the other, there will be no more improving deviation, and then the network will evolve because of random errors until all the teams are disconnected. This is the absorbing state for the network dynamics. We first consider an error probability ε = 0.001. From Figure 7 it appears that the situation where one team is disconnected from the other two teams is reached after less than 20000 iterations (the cost would be infinite according to [START_REF] Boncinelli | Efficiency and stability in a process of teams formation[END_REF], but in the simulations the cost of a disconnected network is 3000). For small ε like ε = 0.00001, the situation may be very different.

From Figure 8 we see that the dynamics is quite stable and a network with cost 154.5 (quite costly in comparison to what observed in the previous cases) survives for long time. Inspection of the network topology shows that this network is indeed stable to deviations from single teams. This network will then survive until an error will not lead to one team accidentally severing a link.

Figure 1 :

 1 Figure 1: Team-star: A team-pairwise stable network

Figure 2 :

 2 Figure 2: Pairwise stable network

Figure 3 :

 3 Figure 3: Sample path of network dynamics for ε = 0.00001

Figure 4 :

 4 Figure 4: Sample path of network dynamics for ε = 0.01

Figure 5 :

 5 Figure 5: Empirical cost distribution for ε = 0.01

Figure 6 :

 6 Figure 6: Sample path of network dynamics for ε = 0.00001

  -|S t |ε p f (g t+1 |S t , g t ) probability and g t+1 ∈ G nf (S t , g t ) with |S t |εp nf (g t+1 |S t , g t ) probability.

1 |P| ; |B| denotes the cardinality of a given set B. So, at time t + 1 network is g t+1 ∈ G f (S t , g t ) with 1

RR n°8657

Acknowledgement: This research was sponsored by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672.

Conclusions

To the best of our knowledge this is the first paper where the concept of teams is introduced in network formation games. We extend the concept of pairwise stable networks to this new class of games, but also define a new concept of network stability toward deviations from a specific set C of teams' coalitions. We show that C-stable networks (and closed network cycles) are selected by a trembling-hand dynamics when the error probability vanishes. Finally, we resort to simulations to study the evolution of networks in a specific game by using our stochastic dynamic. We think that the idea of teams in network formation games may capture many practical phenomena such as connectivity pattern in the Internet Autonomous systems and it opens new research directions.


Gauss-Markov algorithm [START_REF] Aitken | On least squares and linear combinations of observations[END_REF] is applied to fit the experimental data and identify the 2 unknown parameters κ and τ as shown in Figure 4.

The estimated values of κ and τ for Al, Cu, and Si are reported in Table I.

The maximum thermoreflectance coefficient for a visible wavelength is of the order of 10 -5 K -121 for both metals and Si. Using a millimetric radiation, the measured coefficient κ is 7 × 10 -3 K -1 for Si and about 10 -3 K -1 for metals, those values are 2 order of magnitude higher compared to visible wavelengths. To our knowledge, such high values have never been reported.

IV. CONCLUSION

In this paper, we have broadened the thermoreflectance technique from visible to millimeter wavelengths. We have demonstrated the ability of those millimetric radiations to pass through a thick plate of Teflon opaque to visible wavelengths and perform transient temperature measurements of metallic and semiconductor materials. By monitoring the temperature of the sample, we have estimated the thermoreflectance coefficient of aluminum, copper, and silicon. We report giant thermoreflectance coefficients whose values are a 100 times higher at 2.8 mm compared to optimized coefficient previously reported for visible wavelength. Theoretical studies are currently led to provide a clear explanation of those effects and will be further presented.

The transparency properties and the high sensitivity of millimetric thermoreflectance technique reported in this paper open a wide range of applications in the domain of heat transfer and transient thermal measurement of materials located behind opaque shields like plastics, wood, or concrete.

TABLE I .

 I Measured thermoreflectance coefficients for 2.8 mm compared to value in the visible domain.

		Al	Cu	Si
	κ (K -1 ), at 2.8 mm	-1.4 × 10 -3	1.6 × 10 -3	7 × 10 -3
	κ (K -1 ), average for visible	1 × 10 -5 21	. . .	4.5 × 10 -5 23
	wavelength
	κ (K -1 ), max for visible	1 × 10 -4 21 1.5 × 10 -4 22	. . .
	wavelength
	τ (s)	-2.4	5.5	-1