Salam Akoum
email: salam.akoum@mail.utexas.edu.

Marie Zwingelstein-Colin

Robert W Heath
email: rheath@mail.utexas.edu.

Merouane Debbah

Cognitive Cooperation for the Downlink of Frequency Reuse Small Cells

Keywords: Small cell networks, Downlink, Frequency reuse, Virtual MIMO, Cooperation, Space diversity, Frequency diversity, Distributed space time code, Golden code

We develop a cooperative diversity protocol that is coded over space, time and frequency to achieve improved quality of service for mobile users in the downlink of small cells frequency reuse networks. The proposed protocol, called Cooperative Frequency Reuse (CFR), leverages the cellular frequency reuse concept to create space and frequency diversity among pairs of collaborating adjacent base stations. The CFR protocol is compatible with the half-duplex mode, and is distributed in the sense that each base station acts in autonomy, without the need of a centralized entity. It is implemented in two phases. During the first phase, each base station independently serves its own users on its dedicated frequency band. It simultaneously listens to the symbols transmitted by neighboring base stations. Cognitive cooperation is introduced in the second phase, where each base station transmits on two frequency bands to the scheduled users in both base stations, by means of an appropriately chosen distributed space time code based on the Golden code. We analyze and discuss the performance of the proposed protocol in terms of bit error-rate, probability of outage and ergodic sum-rate under different scenarios. Simulation results show that the proposed protocol yields considerable improvement over the classical direct transmission frequency reuse strategies.

I. INTRODUCTION

Small cells wireless networks provide increased capacity and higher area spectral efficiency [START_REF] Alouini | Area spectral efficiency of cellular mobile radio systems[END_REF]- [START_REF] Ramanath | Asymptotic analysis of precoded small cell networks[END_REF]. The benefits reaped from these networks come, however, at the expense of increased co-channel interference, especially at the cell edge. Conventional cellular networks manage the interference problem by requiring adjacent base stations (BSs) to transmit on different frequency bands. This mechanism is called frequency reuse (FR). It increases the reliability of the cellular networks while at the same time incurring a poor spatial reuse of the expensive frequency spectrum [START_REF] Alouini | Area spectral efficiency of cellular mobile radio systems[END_REF]. Fractional Frequency Reuse (FFR) achieves a higher spatial reuse of the spectrum, and is suggested for next generation cellular systems [START_REF] Wang | Mobile WiMAX systems: performance and evolution[END_REF], [START_REF]Further advancements for E-UTRA physical layer aspects," 3rd Generation Partnership Project; Technical specification Group Radio Access Network[END_REF]. It divides the frequency bands into subchannels, to be shared orthogonally among BSs to serve users that are interference limited. It maintains, however, universal frequency reuse in the cell center. Small cell networks encounter conflicting requirements between providing an increased area spectral efficiency and maintaining quality of service for their mobile users. One way to resolve this tradeoff is through combining frequency reuse with cooperation between adjacent BSs. Implementing a cooperation algorithm that leverages the FFR concept of cellular systems achieves the dual benefit of higher reliability and higher spectral efficiency.

Cooperation in cellular networks, depending on the level of data and channel state information (CSI) shared between BSs, can be implemented in several ways [START_REF] Laneman | Cooperative diversity in wireless networks: Efficient protocols and outage behavior[END_REF]- [START_REF] Song | Relay station shared by multiple base stations for inter-cell interference mitigation[END_REF]. Cooperative space diversity [START_REF] Laneman | Cooperative diversity in wireless networks: Efficient protocols and outage behavior[END_REF], [START_REF] Sendonaris | User cooperation diversity part I: System description[END_REF] is one such method. It exploits spatial diversity by implementing a virtual antenna array between adjacent BSs, and distributed space time codes can be constructed over the formed virtual array to increase the reliability of the system [START_REF] Laneman | Distributed space-time-coded protocols for exploiting cooperative diversity in wireless networks[END_REF]- [START_REF] Hucher | AF and DF protocols based on Alamouti ST code[END_REF]. In this paper, we design a cooperation protocol based on space and frequency diversity, for cooperation between a pair of adjacent BSs. The proposed protocol, called Cooperative Frequency Reuse (CFR), leverages the frequency reuse concept of cellular systems, creating a virtual Multiple-Input Single-Output (MISO) system based on the sharing of OFDM frequency bands among adjacent BSs. It can be applied to cellular systems that use FFR, such as WiMAX and LTE, in a straightforward manner. It is cognitive in the sense that the BSs use, opportunistically in time, the frequency bands allocated to their adjacent BSs to transmit to the mobile users, hence creating cognitive diversity on the downlink of the cellular system.

In contrast to the cooperative multicell transmission strategies available in the literature [START_REF] Shamai | Enhancing the cellular downlink capacity via co-processing at the transmitting end[END_REF], [START_REF] Jing | Downlink macro-diversity in cellular networks[END_REF], [START_REF] Shamai | Multi-cell communications: An information theoretic perspective[END_REF], where base stations jointly process the downlink signals of the mobile users, thereby creating a multiple-input multiple-output (MIMO) broadcast channel, the proposed CFR protocol implements cooperation through a distributed space time code. It is thus especially suitable for mobile flexible networks [START_REF] Debbah | Mobile Flexible Networks: The challenges ahead[END_REF], where the BSs have limited or no wired backhaul communication.

The proposed strategy is different from the cooperative transmit diversity in the multihop relay specification for WiMAX, the IEEE 802.16j standard [START_REF] Peters | The future of WiMAX: multihop relaying with IEEE 802.16 j[END_REF]. In the latter, distributed space time codes are implemented across antennas of the deployed relays and the BS, in the same cell, over the same time and frequency resources. It is also different from the shared relay concept proposed in IEEE 802.16m [START_REF] Song | Relay station shared by multiple base stations for inter-cell interference mitigation[END_REF], where a relay is placed at the intersection of two or more cells, and used to decode the signals from the intersecting BSs. The CFR protocol also differs from other cooperative protocols proposed in the literature, such as [START_REF] Sendonaris | User cooperation diversity part I: System description[END_REF]- [START_REF] Badr | Distributed space time codes for the Amplify-and-Forward multiple-access relay channel[END_REF], [START_REF] Janani | Coded cooperation in wireless communications: space-time transmission and iterative decoding[END_REF]. The latter protocols are applied for cooperation among mobiles nodes on the uplink of cellular systems, and can be used for communication between terminals in ad-hoc networks.

Assuming a half-duplex mode, whereby nodes cannot transmit and receive at the same time on the same frequency band, the CFR protocol is implemented, for a pair of adjacent BSs, in two phases. During the first phase, each BS serves its own users in a protected band, orthogonal to the frequency bands that the adjacent base stations transmit on. The BS listens, during the same phase, to the signal sent by the cooperating BS on another frequency band. The underlying assumption here is that the wireless link between the pair of adjacent BSs is reliable, which is generally the case in practice, when the BSs have a line of sight channel. In the second phase, the BSs divide their transmit power between two frequency bands: they use one band to serve their own users, and the other band for cooperation by relaying the signal of the other BS.

During the second phase, the CFR protocol implements a distributed space time code between the cooperating base stations, based on the Golden code [START_REF] Belfiore | The golden code: a 2 x 2 full-rate space-time code with nonvanishing determinants[END_REF]. The Golden code is a full rate space time code that achieves the optimal Diversity Multiplexing Tradeoff (DMT). It has been applied in the cooperative communication literature [START_REF] Yang | Optimal space time codes for the MIMO amplify-and-forward cooperative channels[END_REF], where it was proven to be optimal for the single-input single-output (SISO) amplify and forward (AF) cooperative channel.

In this paper, we establish the benefits of the CFR protocol in terms of bit error-rate, probability of outage and achievable ergodic sum-rate, through extensive numerical simulations. We first consider the ideal case of an isolated pair of collaborating BSs, where the BS to BS link is assumed perfect. We then extend the analysis to incorporate the imperfections in the BS to BS link, for the isolated two base station case. We finally consider the effect of other cell interference from neighboring non-cooperating base stations. The rest of the paper is organized as follows.

We describe the multicell downlink transmission model in section II. In section III, our CFR protocol is presented and discussed. The performances of the CFR protocol in terms of bit errorrate, probability of outage and ergodic sum-rate are evaluated in section IV-A for the case of isolated collaborating pair of base stations. Section IV-B analyses the CFR protocol for the case of an infinite number of adjacent base stations, where each collaborating pair acts as an interferer for the other cooperating pairs in the network. Numerical results are presented in Section V.

Concluding remarks and insights into future work are given in Section VI.

Throughout the paper, the following notation is used. Bold lowercase letters x are used to denote column vectors, bold uppercase letters X are used to denote matrices, non bold letters x are used to denote scalar values, and caligraphic letters X are used to denote sets or functions of sets. Using this notation, |x| is the magnitude of a scalar, x is the vector 2-norm, X H is the conjugate transpose of X. We use E to denote expectation. I n is the identity matrix of size n × n, and the probability of event E is P (E). i = √ -1, Z is the ensemble of relative integers and ⊗ is the Kronecker product for matrices.

II. MULTICELL DOWNLINK TRANSMISSION MODEL

In this section, we present the system model, shown in Figure 1, for the downlink of the multi-cell network of interest. The BSs and the user terminals are assumed to be equipped with a single antenna. The BSs employ OFDM modulation with N subchannels per OFDM frequency band. They implement fractional frequency reuse, such that the users at the celledge are protected against inter-cell interference. In order for the model to be consistent with practical considerations, we assume that the base stations operate in half-duplex mode, i.e. they cannot transmit and receive at the same time on the same frequency band. We also assume Time Division Multiple Access (TDMA) as the multiple access scheme. We further consider slow fading, such that the coherence time of the channel is larger than the maximum delay tolerated by the application. We do not account for scheduling, resource allocation or fairness among users. Only global performance over the OFDM frequency band is considered.

The cellular layout that we consider corresponds to the linear Wyner cellular model [START_REF] Wyner | Shannon-theoretic approach to a Gaussian cellular multiple-access channel[END_REF]. Albeit simple and analytically tractable, this model provides considerable insight into the working of real cellular networks [START_REF] Jing | Multicell downlink capacity with coordinated processing[END_REF]- [START_REF] Somekh | Shannon-theoretic approach to a Gaussian cellular multi-access channel with fading[END_REF] in the absence of a more realistic tractable approach to other cell interference. It allows for representation of the cellular interference using only one parameter.

The linear model is illustrated in Figure 1, where the cells are indexed in increasing order from left to right. The FR factor between adjacent cells is set to 2, that is 2 OFDM bands, band I and band II, are allocated alternatively to the cells in the linear array. For simplicity, we focus on the cell-edge users, and thus, for fractional frequency reuse, only consider the regions in the cells with frequency reuse greater than 1.

The downlink channel gains account for the effects of path loss as well as Rayleigh fading.

The effect of log-normal shadowing is ignored. The path loss is assumed to be invariant to frequency, whereas a different and independent realization of Rayleigh fading is assumed on each OFDM subchannel. In the following, we respectively denote by B k and M k the BS and the user terminal in cell k. To make the analysis analytically tractable, we set the average channel gain between each base station B k and its user M k to 1. The average channel gain between

B k and a user in an adjacent cell M k+1 or M k-1 is set to α, and that between B k and M k+2 or M k-2 is set to α 2 , and so on. The link between adjacent base stations is assumed to be an additive white Gaussian noise (AWGN) channel free of fading, with a line of sight component whose gain is denoted by β.

The signal received by user k at time slot m on OFDM subchannel n can be expressed as

y k (m, n) = h k,k (m, n)x k (m, n) + l =k h ℓ,k (m, n)x ℓ (m, n) + w k (m, n), (1)
where x k (m, n) is the symbol transmitted by BS k at time slot m and subchannel n, h ℓ,k (m, n)

is the instantaneous channel gain from BS ℓ to user k at time slot m and subchannel n and w k (m, n) is the AWGN with variance σ 2 w = N 0 . The channel gain h ℓ,k (m, n) accounts for the effects of Rayleigh fading (independent for each value of n), and path loss (the same for all n).

Assuming a slow fading scenario, the frame length T is less than the coherence period of the channel (quasi-static assumption), hence, the time index m is, hereafter, omitted in the channel gain notation. We write h ℓ,k (n) instead of h ℓ,k (m, n). The signal to noise ratio is defined as

SNR ∆ = E N 0 where E = E{|x k | 2 }
is the average energy for transmitting a symbol across the link, and N 0 is the variance of the thermal noise observed at the receiver.

The signal received by base station k at time slot m on subcarrier n is

z k (m, n) = ℓ =k β ℓ,k x ℓ (m, n) + v k (m, n), (2)
where x ℓ (m, n) is the symbol transmitted by base station ℓ at time slot m and subchannel n, β ℓ,k

is the (deterministic) gain of the link between base station ℓ and base station k, and v k (m, n)

is the AWGN at base station k with variance σ 2 v . The channel gain β ℓ,k is modeled as

β ℓ,k = β a+1 , ( 3
)
where a is the number of base stations separating base station ℓ and base station k. In the following, we will consider two cases for the base station to base station link.

1) Ideal base station to base station link, with β = 1 and σ 2 v = 0. 2) Non-ideal link, with 0 ≤ β < 1 and σ 2 v = N 0 . The channel coefficients are assumed to be perfectly known at the receiver, whereas two different scenarios are considered for the channel state information at the transmitter (CSI-T):

1) No CSI-T.

2) Partial (statistical) CSI-T, where only the statistics of the channel gains are known at the transmitter (the coefficient α).

III. COOPERATIVE FREQUENCY REUSE

In this section, we present the cooperative diversity protocol we propose for improving the quality of service at the cell-edge of a small cell network. The protocol is to be implemented between pairs of adjacent base stations, based on the realistic assumption that the link between two adjacent base stations is, in general, a line-of-sight link that does not manifest severe attenuation.

Assuming fractional frequency reuse and operation in half-duplex mode, each base station transmits information to the scheduled users inside its cell, while at the same time, but on a different frequency band, listening to the signal transmitted by its neighboring base station to the users in the adjacent cell. With some incurred delay, whose effect is neglected in the following analysis, both base stations learn each other's transmitted information, and become, thereafter, able retransmit this information in a collaborative manner, creating a virtual MISO system. Based Band II listen to base station 1 transmit to user 0

Base Station 1 Band I listen to base station 0 transmit to user 1

Band II transmit to user 1 transmit to user 0 on this key idea, the proposed protocol is implemented using a distributed space time code that optimally exploits the available degrees of freedom.

The cooperative protocol is called Cooperative Frequency Reuse (CFR), as it leverages the frequency reuse cellular concept, and allows for cooperation between adjacent base stations.

Instead of serving the users in their respective cells independently, as is done under classical frequency reuse, the CFR protocol allows neighboring base stations to implement a distributed space time code to jointly communicate their transmission to their users. The CFR protocol consists of two phases, of duration T /2 each. During the first phase, each base station transmits to its own user on its dedicated OFDM band, and listens to the signal intended to the user of its neighboring base station on the other OFDM band. During the second phase, cooperation is introduced, and each base station transmits to both users on both OFDM bands following the distributed space time code in table I.

The CFR protocol can be thought of as a virtual MISO system, where each collaborating BS pair uses a space time code to increase the reliability of the network. In order not to hinder the achievable rate of the system, we use a full rate space time code based on the Golden code 1 [START_REF] Belfiore | The golden code: a 2 x 2 full-rate space-time code with nonvanishing determinants[END_REF].

The Golden code is a full rate, full diversity, information lossless and DMT achieving space time code for two transmit and two or more receive antennas. For information symbols s 1 , s 2 , s 3 and s 4 , the Golden code codeword is

X =   φ (s 1 + θs 2 ) φ (s 3 + θs 4 ) i φ s 3 + θs 4 φ s 1 + θs 2   = diag   M   s 1 s 2     + diag   M   s 3 s 4       0 1 i 0   ,
1 The Golden code is chosen here because it achieves the diversity multiplexing tradeoff. Other space time codes can be used in the CFR protocol. The Alamouti code for a 2 × 2 MIMO system can be used for example, at the expense of a loss in the achievable sum rate.

m = 2p m = 2p + 1 m = 2p + 2 m = 2p + 3 Base Station A Band I (n) a1 a3 √ γ0bz0(2p, n + N ) √ γ0bz0(2p + 1, n + N ) Band II (n + N ) z0(2p, n + N ) z0(2p + 1, n + N ) √ γ0ia4 √ γ0a2 Base Station B Band I (n) z1(2p, n) z1(2p + 1, n) √ γ1ib4 √ γ1b2 Band II (n + N ) b1 b3 √ γ1bz1(2p, n) √ γ1bz1(2p + 1, n) transmit receive where M = 1 √ 5   φ φθ φ φθ   is the Golden matrix, θ = (1+ √ 5)/2 is the golden number, θ = 1-θ, φ = 1 + i(1 -θ), and φ = 1 + i 1 -θ .
Let the collaborating base station pair, and their respective users, be denoted by

B 0 , B 1 , M 0 , M 1 .
The Golden code is adapted to the CFR protocol in the following manner. Prior to transmission, the information symbols s = [s 1 s 2 s 3 s 4 ] and t = [t 1 t 2 t 3 t 4 ], intended for users M 0 and M 1 respectively, are first precoded by the Golden matrix M as follows

  a 1 a 2   = M   s 1 s 2   ,   a 3 a 4   = M   s 3 s 4   ,   b 1 b 2   = M   t 1 t 2   ,   b 3 b 4   = M   t 3 t 4   .
After applying Golden code precoding, the symbols Amplify and Forward (AF) is chosen as the relaying protocol, as depicted in table II. The amplifying parameter b is used to satisfy the energy constraint

E{|bz k | 2 } ≤ E i.e. b ≤ E β 2 E + N 0 .
The coefficients γ 0 , γ0 = 1γ 0 , γ 1 and γ1 = 1γ 1 account for the power control. In case of no CSI-T, they are set equal to 1 2 to reflect the fact that power is equally allocated to the two OFDM bands. In case of partial (statistical) CSI-T at the transmitter, they can be optimized based on the channel gains statistics.

The distributed space time code is expected to provide a diversity order of 3 (observe from Table II that each symbol is transmitted through 3 channel realizations, due to spatial and frequency diversity). Furthermore, in the event of failure of the cooperating links, the Golden code codewords X 0 and X 1 are still transmitted to users 0 and 1, but as frequency time codewords (over the 4 time slots of the CFR protocol), instead of space frequency time codewords (implemented over the last 2 time slots over the CFR protocol). Consequently, in case of cooperation failure, the diversity order is reduced to 2, but the benefits of using the Golden code are preserved. The analysis in sections IV-A and IV-B discusses the performance of the CFR protocol in terms of bit error rate, probability of outage and average achievable sum-rate, and compares the CFR with the classical, non cooperative, frequency reuse transmission scheme.

IV. PERFORMANCE ANALYSIS

In this section, we derive expressions for the performance evaluation of the CFR protocol based on three metrics, the bit error rate, the probability of outage, and the average achievable sum rate. We first consider the CFR protocol for the ideal case of two isolated adjacent base stations, we then extend the analysis to include other cell interference from non-cooperating adjacent base stations, employing the Wyner linear cellular model.

For the classical non-cooperative (NC-FR) scheme, the signal received by user M k in time slot m on subchannel n is written as

y NC-FR k (m, n) = h k,k (n)x k (m, n) + w k (m, n), k = 0, 1. (4)
The instantaneous capacity of user M k on subchannel n assuming Gaussian transmitted signals thus follows as

C NC-FR k = log 2 1 + E N 0 |h k,k (n)| 2 bpcu, ( 5
)
where bpcu is the capacity unit in bits per channel use.

The joint probability of outage for users M 0 and M 1 , served by BSs B 0 and B 1 , respectively, is

P NC-FR O (R) = P C NC-FR 0 < R , C NC-FR 1 < R , ( 6
)
where R is the target spectral efficiency of the system.

And the ergodic sum-rate is further given by

R NC-FR = E C NC-FR 0 + C NC-FR 1 = E C NC-FR 0 + E C NC-FR 1 , (7)
To decode x k under the assumption of equally likely transmitted constellation points, the maximum likelihood (ML) receiver for the classical scheme is given by

xNC-FR k = arg min x k ∈N NC-FR y NC-FR k -h k,k x k * y NC-FR k -h k,k x k , (8)
where N NC-FR is the set of all possible transmitted symbols. The bit error rate (BER) under ML decoding is computed from the probability of symbol error, depending on the constellation used for symbol mapping at the base station.

A. The CFR protocol for two isolated base stations

In this section, we characterize the performance of the CFR protocol presented in section III in comparison with the classical, non cooperative, FR scheme, in the ideal case of N = 2 isolated base stations. We assume that the cells outside the collaborating pair of interest are not a source of interference.

For the CFR protocol, the received signal at user M k is written, in vector form, as

y CFR k = H k x k + v k + w k , k = 0, 1. (9)
For the user terminal M 0 , it follows from Section III, as shown in Table II, that

y CFR 0 = [y 0 (2p, n) y 0 (2p + 1, n) y 0 (2p + 2, n + N y 0 (2p + 3, n + N )] T , (10)
where the transmitted signal vector x 0 is

x 0 = [a 1 a 3 ia 4 a 2 ] T , (11)
the channel matrix H 0 is written as

H 0 =   h 0,0 (n) 0 √ γ1 h 1,0 (n + N )bβ √ γ 0 h 0,0 (n + N )   ⊗   1 0 0 1   , (12)
and the noise components, v 0 , received during the first phase, and amplified by the AF relaying protocol in the second phase are given by

v 0 =        0 0 √ γ1 h 1,0 (n + N ) bv 1 (2p, n) √ γ1 h 1,0 (n + N ) bv 1 (2p + 1, n)        . ( 13
)
The AWGN noise vector is finally written as,

w 0 =        w 0 (2p, n) w 0 (2p + 1, n) w 0 (2p + 2, n + N ) w 0 (2p + 3, n + N )        . ( 14
)
Similarly, for user terminal M 1 , in cell 1, the received signal vector y CFR 1 is given by

y CFR 1 = [y 1 (2p, n + N ) y 1 (2p + 1, n + N ) y 1 (2p + 2, n) y 1 (2p + 3, n)] T (15)
where

x 1 = [b 1 b 3 ib 4 b 2 ] T , (16)
H 1 =   h 1,1 (n + N ) 0 √ γ0 h 0,1 (n)bβ √ γ 1 h 1,1 (n)   ⊗   1 0 0 1   , (17)
v 1 =        0 0 √ γ0 h 0,1 (n) bv 0 (2p, n + N ) √ γ0 h 0,1 (n) bv 0 (2p + 1, n + N )        , (18)
and

w 1 =        w 1 (2p, n + N ) w 1 (2p + 1, n + N ) w 1 (2p + 2, n) w 1 (2p + 3, n)        . ( 19
)
The instantaneous capacity of user M k under the CFR protocol follows as

C CFR k = 1 4 log 2 det I 4 + H k E x k x H k H H k E -1 (v k + w k ) (v k + w k ) H bpcu, k = 0, 1. (20)
The joint probability of outage for users M 0 and M 1 is

P CFR O (R) = P C CFR 0 < R , C CFR 1 < R ( 21
)
where R is the target spectral efficiency. The average sum-rate is given by

R CFR = E C CFR 0 + C CFR 1 . (22)
To analyse the bit error rate of the CFR protocol, ML decoding is implemented

xCFR k = arg min x k ∈N y CFR k -H k x k ) * y CFR k -H k x k , ( 23
)
where N is the set of all possible transmitted Golden code codewords.

To analyze the performance of the CFR protocol in terms of probability of outage, ergodic sum rate, and bit error rate, we numerically evaluate the expressions in ( 21), [START_REF] Jing | Multicell downlink capacity with coordinated processing[END_REF], and ( 23)

respectively, for the QAM constellation of interest. We compare them to the results obtained from the classical NC-FR protocol in ( 6), [START_REF] Shamai | Enhancing the cellular downlink capacity via co-processing at the transmitting end[END_REF], and (8). To account for the effect of CSI-T at the base stations, we analyze the performance of the CFR algorithm with and without channel state information at the transmitter. When channel state information is available at the transmitter, the fractional power control factors γ k are adusted to optimize the performance metric in question.

For instance, the problem of minimizing the joint probability of outage, for M 0 and M 1 is written as Problem 1: Find the optimal γ0 , γ1 such that the probability that both users are in outage

P C CFR 0 < R, C CFR 1 < R is minimized. In other words, (γ 0 , γ1 ) = arg min γ 0 ,γ 1 C CFR 0 < R, C CFR 1 < R) = arg min γ 0 ,γ 1 P(C CFR 0 < R)P(C CFR 1 < R) . (24)
Finding the fractional power allocations that minimize the joint probability of outage requires finding the probability distribution of the instantaneous capacities C CFR 0 and C CFR 1 in terms of γ k and γ k+1 . When channel state information is not available at the transmitter, the fractional power factors are equally allocated between the two frequency bands γ 0 = γ 1 = 1 2 . Unfortunately, closed form expressions for these optimization problems cannot be evaluated for finite signal to noise ratio levels.

For the link between the base stations, we consider, as discussed in Section III, both the ideal case, and the non-ideal case with the line of sight channel with AWGN noise. Numerical results in Section V show the performance of the CFR protocol for all the cases of interest, using Monte Carlo simulations.

B. The CFR protocol for N base stations

We extend the analysis in Section IV-A to the more realistic case of a network consisting of N > 2 base stations. For this scenario, the base stations still collaborate on a pair basis, but the interference from the non-cooperating pair on the user terminals is taken into account.

The collaborating pairs are assumed static, in the sense that if base station B k collaborates with adjacent base station B k+1 , the collaborating pair remains fixed throughout the duration of the cooperative protocol, and does not change based on received signal strength at the user terminals.

For simplicity, we consider the performance of the base station pairs (B k , B k+1 ) = (B 0 , B 1 ) with interference from the pairs . . . (B -4 , B -3 ), (B -2 , B -1 ), (B 2 , B 3 ), (B 4 , B 5 ) . . . (see Figure 1).

The received signal at user M k , in cell B k is written in vector form as

y CFR,N k = H k x k + u k + v k + w k , k = 0, 1, (25)
where x k , H k , v k and w k are given by equations ( 11), ( 12), ( 13), ( 14) respectively, and

u k =                     i∈Z i =k h 2i-k,k (n + kN )x 2i-k (2p, n + kN ) i∈Z i =k h 2i-k,k (n + kN )x 2i-k (2p + 1, n + kN ) i∈Z i =0 i =1 h i,k (n + (1 -k)N )x i (2p + 2, n + (1 -k)N ) i∈Z i =0 i =1 h i,k (n + (1 -k)N )x i (2p + 3, n + (1 -k)N )                     , k = 0, 1 (26)
corresponds to the vector of interfering signals from the base stations outside the collaborating pair.

The performance of the CFR protocol for the linear Wyner model with N base stations is evaluated, similarly to Section IV-A, based on Monte Carlo simulations in Section V. Expressions for the performance metrics such as bit error rate, joint probability of outage and ergodic sum rate are derived using y CFR,N k , and the effect of the additional interference term u k is evaluated for the ideal and the non-ideal CSI-T cases of interest.

V. NUMERICAL RESULTS AND DISCUSSION

We provide numerical results to evaluate the performance of the proposed cooperative frequency reuse algorithm in terms of achievable bit error rate, probability of outage and ergodic sum rate. For our simulations, we consider a linear Wyner model cellular setup, where all cells have the same radius and users are uniformly distributed inside each cell, assuming one sector per cell.

When partial (statistical) CSI-T is available at the transmitter, the power factors γ 0 and γ 1 are chosen from the discrete set (γ 0 , γ 1 ) ∈ {0, 0.25, 0.5, 0.75, 1} in order to optimize the performance metric in question (i.e. the bit error-rate, the probability of outage or the ergodic sum rate). For the case of no CSI-T, the power factors γ 0 = γ 1 = 1 2 are allocated equally between the two frequency bands.

We start by examining the performance of the CFR protocol for the case of two isolated base stations. We present in Figures 2, 3 and4, respectively, the bit error rate, the probability of outage and the average sum rate as a function of the signal to noise ratio, for the CFR protocol with the following scenarios. 1) No CSI-T, ideal link between the base stations (β = 1 and σ 2 v = 0). 2) No CSI-T, non ideal (worst case) link quality between the base stations (β = α, and

σ 2 v = N 0 ).
3) CSI -T, ideal link between the base stations.

4) CSI -T, non ideal (worst case) link quality between the base stations.

Figure 2 plots the bit error rate versus SNR, for symbols s and t chosen from a 4-QAM and a 16-QAM constellation. The link quality between the adjacent base stations and the user terminal is set equal to α = 0.1. For comparison, we include in the figure the bit error rate for the classical frequency reuse FR 2 scheme, as well as the bit error rate for the universal frequency reuse, FR 1 scheme, where the latter symbols are taken from a BPSK and a 4-QAM constellation, respectively, for fairness of comparison. It can be observed from Figure 2, that even in the absence of CSI-T, for the case of the worst case non-ideal link, the CFR protocol outperforms the classical FR 2 protocol, for all signal to noise ratio values. The FR 1 scheme outperforms the CFR protocol at low SNR, where the distributed space time code does not perform well.

At high SNR values, the diversity obtained from the CFR protocol outperforms that of the FR 1 direct transmission protocol, and the CFR protocol achieves the best performance. The good performance of the CFR protocol at high SNR can be well invested for application in the small cells scenario. Due to the proximity of the base station from its intended receiver in a small cell environment, the signal to noise ratio at the receiver is expected to be high, and the quality of the link α is expected to be large. Hence, the CFR protocol is most suitable for cooperation in small cell environments.

The CFR protocol with CSI-T and ideal link between the cooperating base stations achieves the best performance, among the CFR protocol setups. The presence of channel state information at the transmitter improves the bit error rate performance by 1 dB at high SNR. When the link between the base stations is non-ideal, in the worst case (β = α), the performance degradation is negligible. It is .5 dB on average at high SNR for the case of no CSI-T, and non-discernable for the case of when CSI-T is available at the base station.

In Figure 3, we compare the joint probability of outage performance of the CFR protocol to that of the FR 1 and FR 2 direct transmission schemes, for assumed spectral efficiencies R = 2 and R = 4 bps/Hz, respectively. The joint probability of outage metric indicates the effect of the channel and the interference on the reliability of the system. It can be observed from Figure 3 that, similarly to Figure 2, the CFR protocol outperforms the FR2 and FR1 direct transmissions at high SNR. For the case of R = 2 bps/Hz, the CFR protocol with CSI-T achieves the best performance for all the SNR values, with comparable performance to the FR 2 protocol at SNR below 5 dB. The crossing point between the FR 1 protocol and the CFR protocol with CSI-T occurs at 10 dB for R = 2 bps/Hz. For a higher spectral efficiency, namely R = 4 bps/Hz, the crossing point occurs at medium values of SNR, around 15 dB. The effect of the presence of CSI-T and the errors in the base station to base station links follow similarly to the bit error rate performance in Figure 2. In particular, the presence of CSI-T incurs a gain of around 1 dB at high SNR, and the effect of the non-ideality in the link is negligible, especially with CSI-T.

Figure 4 plots the average sum-rate for various signal to noise ratio levels, when α = 0.1. It can be observed from the figure that the CFR protocol with CSI-T achieves the same average sum rate as the FR 2 scheme with direct transmission, which is in accordance to the fact that diversity does not change the pre-log factor in the capacity expressions. This average sum rate degrades when channel state information is not present at the transmitter. The effect of CSI-T is on average 1 dB increase in sum-rate. The effect of the errors in the base station to base station link is again negligible in the presence of CSI-T at the base station.

The effect of α, the quality of the adjacent base station link is important for small cells scenarios, as it gives us an indication on how the CFR protocol would behave as the radius of the cell decreases and the base stations become closer to the mobile users they are serving.

Figures 5, 6 and7 plot respectively, the bit error rate, the joint probability of outage and the average achieved sum rate as a function of signal to noise ratio, for α = 0.25. It can be observed from the figures, that the CFR protocol performance improves as α increases. In particular, the crossing points between the FR 1 direct transmission curves and those of the CFR protocol shift to the left by 5 dB for 16-QAM modulation and 2 dB for 4-QAM modulation in the bit error rate curves. For the sum rate curves, the crossing point between the FR 1 direct transmission and the CFR protocol is shifted by 8 dB to the left. As expected, as the value of α is increased, the value of the cooperation increases, and the CFR protocol performance becomes superior to direct transmission for most values of signal to noise ratio at the mobile station. For small cell scenarios, where the received signal power at the mobile station is higher than that in a macro base station environment, because of the proximity of the base station to the mobile user, the CFR protocol is the winning strategy.

To further investigate the effect of α on the performance of the schemes investigated in this paper, we plot, in Figures 8 and9, respectively, the bit error rate of the 4-QAM modulation scheme and the joint probability of outage for a target spectral efficiency R = 2 bps/Hz, as a function of increasing α, 0 < α < 1, for a medium SNR value of 15 dB. The direct transmission classical FR 2 scheme is shown in the Figures for comparison as well as the FR1 direct transmission.

It can be observed from Figure 8 that the bit error rate of the CFR protocol exhibits a generally decreasing behavior as α increases. For α < 0.5, in the absence of CSI-T, the bit error rate remains unchanged as α increases, this can be explained by the fact that the collaboration link does not have the sufficient quality to increase the benefit. The bit error rate thus remains constant, but at a value that is lower than the classical FR 2 scheme. For α > 0.5, the slope of decay of the bit error rate with α increases. The gap between the ideal and the non-ideal worst case link between the base stations increases, as α increases. This makes sense since we set the worst case link quality between the base stations to β = α. In practice, the performance achieved by the CFR protocol with no CSI-T occurs between the two curves, as they correspond to two extreme cases of β. When statistical CSI-T is available at the base station, the effect of α is not as discernible as the case with no CSI-T. In fact, the bit error rate for CSI-T with non-ideal link starts decreasing for very high values of α ≈ 0.9. Knowing the statistics of the channels at the transmitters shields the base stations against the effect of α. The link quality has no effect on the bit error rate achieved by the FR 2 classical transmission scheme as the base stations transmit on orthogonal frequency bands with no cooperation between base stations and no interference. The value of α has however an effect on the universal frequency reuse scheme FR 1, where both base stations transmit at the same time on the same frequency band. As the value of α increases, the link quality between the adjacent base station and the mobile user improves, causing the co-channel interference from the adjacent base stations to increase, and hence the probability of bit error to increase.

The joint probability of outage, for R = 2 bps/Hz, shown in Figure 9, exhibits the same behavior as that of the bit error rate curves. The FR 1 direct transmission scheme is, however, always worse than the FR 2 schemes and the CFR schemes, even for small values of α. The joint probability of outage of the CFR protocol with CSI-T decreases with α starting at α = 0.7 for the ideal case, and α = 0.8 for the non-ideal base station to base station link.

We finally examine the performance of the CFR protocol when the interference from the base stations outside the collaborating pair of interest is taken into account. We consider a linear array of N = 10 base stations, that form 5 collaborating pairs. Figures 10, 11 and 12 present, respectively, the bit error-rate, the joint probability of outage and the achievable average sum rate, for the collaborating pair, given the interference from neighboring base stations. For the bit error-rate, the symbols are taken from a 4-QAM constellation, and the target spectral efficiency for the probability of outage is set to R = 2 bps/Hz. The link quality is set to α = 0.1. The figures compare the performance of the CFR protocol, without channel state information at the transmitter, for both an ideal link between the base stations, and a worst case base station to base station link degradation. It can be observed from the figures that the effect of the interference from adjacent base stations is negligible and only discernible at high SNR, as the SNR increases, the reliability (bit error rate and joint probability of outage) as well as the average sum rate of the CFR protocol decreases with interference. The effect of the quality of the base station to base station link for the N base stations is the same as that for the two isolated base stations case. The performance of the CFR protocol decreases in the presence of error on the base station to base station link.

VI. CONCLUSION AND FUTURE WORK

In this paper, we proposed a novel distributed cooperation protocol called Cooperative Frequency Reuse that is used on the downlink of frequency reuse small cell systems. Collaboration between pairs of adjacent base stations enables the use of space as well as frequency diversity, at full rate, while keeping the half-duplex mode asumption. The protocol is based on a distributed space time code derived from the Golden code. We discussed the performances of the protocol in terms of bit error-rate, joint probability of outage and ergodic sum-rate under different scenarios.

Simulation results showed that the CFR protocol increases the reliability of the cellular system, especially at high SNR, without incurring additional complexity overhead.

Future work includes an analytical analysis of power control optimization problems under partial (statistical) channel state information. It also includes accounting for fractional frequency reuse in the network model, and optimizing the fractional part of the OFDM band under the CFR protocol. Finally, we will consider optimizing the duration of each phase within the frame to increase the reliability of the CFR protocol.

a 1 a 3 ia 4 a 2  b 1 b 3 ib 4 b 2 

 3232 [a 1 a 2 a 3 a 4 ] and [b 1 b 2 b 3 b 4 ] are transmitted as shown in table II. During the first phase (time slots 2p and 2p + 1), base station B 0 transmits symbols a 1 and a 3 to its user on its dedicated OFDM band (band I), and listens to the symbols b 1 and b 3 transmitted by base station B 1 on base station B 2 ' dedicated OFDM band (band II). BS 2 transmission of b 1 and b 3 follows similarly. During the second phase (time slots 2p + 1 and 2p + 2), a space time Golden code codeword is transmitted to each user through cooperation between the two base stations, i.e. the Golden code codeword X 0 =   is transmitted to user M 0 on band II, and the Golden code codeword X 1 =  is transmitted to user M 1 on band I.

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Cellular system layout (Wyner model).

Fig. 4 .

 4 Fig. 4. Average sum-rate of M0 and M1, as a function of the SNR (dB), for two isolated base stations. The link quality is α = 0.1. The non ideal link denotes the case when the base station to base station link gain is β = α.

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig.5. Bit error-rate (BER), as a function of the SNR (dB), for two isolated base stations. The link quality is α = 0.25, and the modulation is 4-QAM and 16-QAM respectively. The FR1 curves denote the direct transmission scheme with BPSK and 4-QAM modulation respectively. The non ideal link denotes the case when the base station to base station link gain is β = α.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Bit error-rate for 4-QAM symbols, as a function of α, 0.1 ≤ α ≤ 1, for two isolated base stations and SNR = 15 dB.

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Bit error-rate for 4-QAM symbols, as a function of the SNR, for N = 10 base stations with collaborating CFR pairs, and N = 2 isolated BSs. α = 0.1.

Fig. 12 .

 12 Fig. 12. Average sum rate, as a function of the SNR, for N = 10 base stations with 5 collaborating CFR paris and N = 2 isolated BSs. α = 0.1 and the modulation scheme is 4-QAM.

TABLE I PROPOSED

 I CFR PROTOCOL, FOR THE PAIR OF BASE STATIONS NUMBER 0 AND 1, OPERATING ON OFDM BANDS I AND II.

			1 st phase	2 nd phase
	Base Station 0	Band I	transmit to user 0	transmit to user 1

TABLE II PROPOSED

 II CFR PROTOCOL BASE ON THE DISTRIBUTED GOLDEN CODE.

	1 st phase	2 nd phase

The work has been supported by the Agence Nationale de la Recherche within the project ANR-09-VERS0: ECOSCELLS. Robert W. Heath, Jr. was supported by the National Science Foundation under grant CNS-626797 and CCF-0830615.


J Elias

F Martignon
email: fabio.martignon@unibg.it

G Neglia

L Petrosyan

Keywords: Network Formation, Cooperative Game Theory, Coalition, Nash bargaining solution, Shapley value

The Network Formation problem has received increasing attention in recent years. Previous works have addressed this problem considering only networks designed by selsh users, which can be consistently suboptimal.

This paper addresses the network formation issue using cooperative game theory, which permits to study ways to enforce and sustain cooperation among agents. Both the Nash bargaining solution and the Shapley value are widely applicable concepts for solving these games. However, we show that the Shapley value presents three main drawbacks in this context: (1) it is non-trivial to dene meaningful characteristic functions for the cooperative network formation game, (2) it can determine for some players cost allocations that can be higher than those at the Nash Equilibrium (and then, if the players refuse to cooperate), and (3) it is computationally very cumbersome.

For this reason, we solve the cooperative network formation game using the Nash bargaining solution (NBS) concept. More specically, we extend the NBS approach to the case of multiple players and give an explicit expression for users' cost allocations. Furthermore, we compare the NBS to the Shapley value and the Nash equilibrium solution, showing its advantages and appealing properties in terms of cost allocation to users and computation time to get the solution.

Numerical results demonstrate that the proposed Nash bargaining solution approach permits to allocate costs fairly to users in a reasonable computation time, thus representing a very eective framework for the design of ecient and stable networks.

A Nash bargaining solution for Cooperative Network Formation Games

Résumé :

Le problème de formation des réseaux a reçu une attention croissante ces dernières années. Les travaux précédents ont abordé ce problème supposant que les réseaux soient créés par des utilisateurs égoïstes ; toutefois, ces réseaux peuvent être systématiquement sous-optimaux.

Cet article aborde le problème de formation des réseaux en utilisant la théorie des jeux coopératifs, qui permet d'étudier les moyens pour faire respecter et soutenir la coopération entre des agents.

La solution de Nash bargaining et la valeur de Shapley sont des concepts largement applicables pour résoudre ces jeux.

Cependant, nous montrons que la valeur de Shapley présente trois inconvénients majeurs dans ce contexte : (1) il nest pas évident de dénir des fonctions caractéristiques signicatives pour le jeu que nous étudions, (2) il peut déterminer pour certains utilisateurs des allocations de coût plus élevées que celles à l'équilibre de Nash (et donc, si les joueurs refusent de coopérer), et (3) le temps de computation est très long.

Pour cette raison, nous résolvons le jeu coopératif de formation de réseau en utilisant le concept de Nash bargaining solution (NBS).

Plus spéciquement, nous étendons cette dernière approche au cas de plusieurs joueurs, et nous donnons une expression explicite pour l'allocation des coûts aux utilisateurs. En outre, nous comparons la NBS à la valeur de Shapley et à l'équilibre de Nash, montrant ses avantages et ses propriétés attrayantes en termes d'allocation des coûts aux utilisateurs et de temps de computation pour obtenir la solution.

Les résultats numériques montrent que l'approche proposée permet d'allouer aux utilisateurs des coûts de manière équitable avec un temps de computation raisonnable, représentant un framework très eectif pour la conception de réseaux ecaces et stables.

Mots-clés : Formation de Réseau, Théorie des Jeux Coopératifs, Coalition, Nash bargaining solution, valeur de Shapley

The Network Formation problem has become increasingly important given the continued growth of computer networks such as the Internet. The design of such networks is generally carried out by a large number of self-interested actors (users, Internet Service Providers . . .)

all of whom seek to optimize the quality and cost of their own operation.

Over the past years, the network formation problem has been tackled almost exclusively from a non-cooperative point of view. Recent works [START_REF] Anshelevich | The price of stability for network design with fair cost allocation[END_REF][START_REF] Chen | Network design with weighted players[END_REF][START_REF] Albers | On the value of coordination in network design[END_REF][START_REF] Epstein | Strong equilibrium in cost sharing connection games[END_REF][START_REF] Chen | Designing networks with good equilibria[END_REF] have modeled how independent selsh agents can build or maintain a large network by paying for possible edges.

Nash equilibria in such games, however, can be much more expensive than the optimal, centralized solution. This is mainly due to the lack of cooperation among network users, which leads to design costly networks.

The underlying assumption in all the above works is that agents are completely noncooperative, isolated entities. However, this assumption could be not entirely realistic, for example when network design involves long-term decisions (e.g., in the case of Autonomous Systems peering relations). It is more natural that agents will discuss possible strategies and, as in other economic markets, form coalitions taking strategic actions that are benecial to all members of the group. Moreover, incentives could be introduced by some external authority (e.g., the network administrator, the government authority) in order to increase the users' cooperation level.

Preliminary works, like [START_REF] Elias | Socially-Aware Network Design Games[END_REF][START_REF] Azad | From Altruism to Non-Cooperation in Routing Games[END_REF], tried to overcome this limitation by incorporating a socially-aware component in the users' utility functions. This solution, though, can be insucient to obtain cost-ecient networks in all scenarios. In fact, it has been demonstrated in [START_REF] Elias | Socially-Aware Network Design Games[END_REF] that, quite surprisingly, highly socially-aware users can form stable networks that are much more expensive than the networks designed by purely selsh users.

To address the above issues, in this paper we formulate the network formation problem as a cooperative game, where groups of players (named coalitions) coordinate their actions and pool their winnings; consequently, one of the problems is how to divide the cost savings among the members of the formed coalition.

The Shapley value and the Nash bargaining solution are widely applicable solution concepts for cooperative games. The former has appealing properties, since it provides a unique and fair solution [START_REF] Aumann | The Shapley Value. Game-Theoretic Methods in General Equilibrium Analysis[END_REF]. The Nash bargaining approach, on the other hand, studies situations where two or more agents need to select one of the many possible outcomes of a joint collaboration [START_REF] Muthoo | Bargaining theory with applications[END_REF][START_REF] Nash | The bargaining problem[END_REF]. Examples include wage negotiation between an employer and a potential employee, or trade negotiation between two countries. Each party in the negotiation has the option of leaving the table, in which case the bargaining will result in a disagreement outcome. The Nash bargaining solution (NBS) is a very eective tool to model interactions among negotiators, and is unique for bargaining games satisfying Pareto optimality, symmetry, scale independence, and independence of irrelevant alternatives [START_REF] Muthoo | Bargaining theory with applications[END_REF][START_REF] Nash | The bargaining problem[END_REF].

However, we will show that the Shapley value presents several drawbacks in this context:

(1) it is non-trivial to dene meaningful characteristic functions for the cooperative network formation game, (2) the cost allocation determined by the Shapley value can be, in some cases, even costlier than that obtained at some Nash equilibrium, and (3) for our network formation game, it cannot be determined in a reasonable computation time.

For these reasons, we propose a Nash bargaining approach to solve the cooperative network formation problem. More specically, as a key contribution, we extend the Nash bargaining solution for the cooperative network formation problem to the case of multiple players with linear constraint, and give explicit expressions for users' cost allocations. To the best of our knowledge, the derived explicit expressions are new.

Furthermore, we perform a thorough comparison of the proposed Nash bargaining solution with other classic approaches like the Shapley value and the Nash equilibrium solutions, using dierent network scenarios.

Numerical results demonstrate that the proposed Nash bargaining solution can compute ecient cost allocations in a short computing time, thus representing a very eective tool to plan ecient and stable networks.

The main contributions of this work can therefore be summarized as follows:

the formulation of the network formation problem as a cooperative game, where players cooperate to reduce their costs.

The proposition of a novel Nash bargaining solution for the n-person cooperative network formation problem, which has appealing properties in terms of planning ecient networks and cost allocations in a reasonable computation time.

A comparison of the proposed approach with classic solutions, like the Shapley value and the Nash equilibrium concepts, in large-size network topologies.

The paper is organized as follows: Section 2 discusses related work. Section 3 introduces the proposed cooperative network formation game, the proposed Nash bargaining solution along with a distributed approach we propose for its computation. Section 4 presents numerical results that demonstrate the eectiveness of the NBS approach in dierent realistic network scenarios. Finally, Section 5 concludes this paper.

Related Work

The network formation problem has been addressed in several recent works, mainly in the context of non-cooperative games [START_REF] Anshelevich | The price of stability for network design with fair cost allocation[END_REF][START_REF] Chen | Network design with weighted players[END_REF][START_REF] Elias | Socially-Aware Network Design Games[END_REF]. The works in [START_REF] Albers | On the value of coordination in network design[END_REF][START_REF] Epstein | Strong equilibrium in cost sharing connection games[END_REF][START_REF] Van Den Nouweland | Models of network formation in cooperative games[END_REF][START_REF] Demaine | The Price of Anarchy in Cooperative Network Creation Games[END_REF] have further considered coordination issues among players.

The so-called Shapley network design game is proposed in [START_REF] Anshelevich | The price of stability for network design with fair cost allocation[END_REF]. In this non-cooperative network formation game, each player chooses a path from its source to its destination, and the overall network cost is shared among the players in the following way: each player pays for each edge a proportional share ce xe of the edge cost c e , where x e is the number of players that choose such edge. In [START_REF] Elias | Socially-Aware Network Design Games[END_REF], the Shapley network design game is extended, adding a socially-aware component to users' utility functions.

The survey article in [START_REF] Van Den Nouweland | Models of network formation in cooperative games[END_REF] presents the most notable works on network formation in cooperative games; furthermore, the existence of networks that are stable against changes INRIA in link choices by any coalition is studied in [START_REF] Jackson | Strongly stable networks[END_REF]. In [START_REF] Andelman | Strong price of anarchy[END_REF], Andelman et al. analyze strong equilibria with respect to players' scheduling as well as a dierent class of network creation games in which links may be formed between any pair of agents. For these latter games, strong Nash equilibria (i.e., equilibria where no coalition can improve the cost of each of its members) achieve a constant Price of Anarchy, which is dened as the ratio between the cost of the worst Nash equilibrium and the social optimum. Strong Nash equilibria ensure stability against deviations by every conceivable coalition of agents. A similar problem is considered in [START_REF] Demaine | The Price of Anarchy in Cooperative Network Creation Games[END_REF], where nodes can collaborate and share the cost of creating any edge in the host graph.

The works in [START_REF] Albers | On the value of coordination in network design[END_REF][START_REF] Epstein | Strong equilibrium in cost sharing connection games[END_REF] study the existence of strong Nash equilibria in network design games under dierent cost sharing mechanisms. More specically, the authors in [START_REF] Albers | On the value of coordination in network design[END_REF] show that there are graphs that do not admit strong Nash equilibria, and then give sucient conditions for the existence of approximate strong Nash equilibria.

The idea of using the Nash bargaining solution in the context of telecommunication networks has been considered in dierent networking scenarios. Such approach was rst presented for packet-switched data networks by Mazumdar et al. [START_REF] Mazumdar | Fairness in network optimal ow control: Optimality of product forms[END_REF]. Yaiche et al. [START_REF] Yaiche | A game theoretic framework for bandwidth allocation and pricing in broadband networks[END_REF] use the concept of Nash bargaining solution to derive a price-based resource allocation scheme that can be applied to the available bit rate service in ATM networks. In [START_REF] Han | Fair Multiuser Channel Allocation for OFDMA Networks Using Nash Bargaining Solutions and Coalitions[END_REF] the authors propose a scheme to allocate subcarrier, rate, and power for multiuser orthogonal frequencydivision multiple-access systems. The approach considers a fairness criterion, which is a generalized proportional fairness based on Nash bargaining solutions and coalitions.

The reader is referred to the next section, to the book by Muthoo [START_REF] Muthoo | Bargaining theory with applications[END_REF] and the paper by Nash [START_REF] Nash | The bargaining problem[END_REF] for a general introduction to the Nash bargaining solution concept.

Cooperative Network Formation Game: Formulation and Solutions

This section illustrates the cooperative network formation game considered in this work, and describes the proposed Nash bargaining solution (NBS). A review of the Shapley value approach is preliminarily proposed for comparison reasons.

Network Model

We are given a directed graph G = (V, E), where each edge e has a nonnegative cost c e ; each player i ∈ I = {1, 2, . . . n} is identied with a source-destination pair (s i , t i ), and wants to connect his source to the destination node with the minimum possible cost. Note that c e represents the total edge cost, which is shared among the players according to the allocation algorithms we will describe in the following.

We consider a cooperative game in strategic form G = I, A, {J i } , where I is the set of players, A i is the set of actions for player i, A = A 1 × . . . × A n , and J i is the objective (cost) function, which player i wishes to optimize (minimize).

In a cooperative game, players bargain with each other before the game is played. If an agreement is reached, players act according to the agreement reached, otherwise players act in a non-cooperative or antagonistic way. Note that the agreements reached must be binding, so players are not allowed to deviate from what is agreed upon.

The Shapley value solution

We now review the Shapley value solution approach, and discuss meaningful denitions for the characteristic function.

The Shapley value is a widely applied concept for solving cooperative games. It is a possible way to allocate the total costs among the members of a coalition, taking into account their dierent importance for the coalition. The main advantage of the Shapley value is that it provides a solution that is both unique and fair: it is unique in the class of subadditive cooperative games (see denition below); it is fair in a sense that it satises a series of axioms intuitively associated with fairness (see [START_REF] Aumann | The Shapley Value. Game-Theoretic Methods in General Equilibrium Analysis[END_REF]). However, while these are both desirable properties, the Shapley value has one major drawback: for many coalition games, including our network formation game, it cannot be determined in a reasonable time. We shall discuss computation aspects in more detail below.

A Shapley function φ is a function that assigns to each possible characteristic function v a vector of real numbers, i.e.,

φ(v) = [φ 1 (v), . . . , φ i (v), . . . , φ n (v)], (1)
where φ i (v) represents the cost of player i in the game.

The characteristic function, v, is a real-valued function that associates with every nonempty subset S of I (i.e., a coalition) a real number v(S), the cost of S; v(S) must satisfy the following properties 1 :

1. v(∅) = 0. 2. (Subadditivity) if S and T are disjoint coalitions (S ∩ T = ∅), then v(S) + v(T ) ≥ v(S ∪ T ).
This latter property means that cooperation can only help but never hurt.

Note that dening the characteristic function is not straightforward for the cooperative network formation game considered in this work, since a natural denition can violate the subadditivity property, as we will discuss in the following.

The three denitions reported hereafter naturally arise in our networking problem as candidate characteristic functions:

1. Players in S and players in I -S form two separate coalitions. Each coalition tries to minimize the total cost for its members, taking into account the selsh behavior of the other coalition. A Nash equilibrium is reached, and v(S) is dened as the total cost for members in S at this equilibrium.

1 The second one is required to guarantee the uniqueness of the Shapley value solution.

INRIA

2. The value of the coalition S is dened as its security level, i.e. as the minimum total cost that S can guarantee to itself when members in I -S act collectively in order to maximize the cost for the coalition S.

3. The value of coalition S is equal to the minimum cost that its members would incur if players in I -S would be absent.

We note that, in our specic game, these three denitions give increasing value to a coalition S. In fact, when players in I -S minimize their own cost (rst denition), their path choices cannot be as bad for S as when they try to maximize the cost for S (second denition). Still, when players in I -S are present, they are obliged to select paths to connect their source-destination pairs, and some of these links may be used also by players in S, so that v(S) is smaller in the second denition than in the third.

To better illustrate the dierences underlying these denitions, let us consider the hexagon network scenario of Figure 1, with 6 links and 3 players having the following sourcedestination pairs: (s 1 , t 1 ), (s 2 , t 2 ) and (s 3 , t 3 ). All link costs are equal to 1, except for link t 3 → t 2 , which has a cost equal to 1 -, being a very small constant.

Figure 1: Hexagon network topology: the 3 players must connect their source-destination nodes (s i , t i ). The optimal solution, which in this case coincides with both the Nash equilibrium point and the Nash bargaining solution, is also illustrated with dashed lines. Theorem 1 In the Cooperative Network Formation Game, the security level and the minimal cost of coalition satisfy the axioms of characteristic function.

Proof: See the Appendix.

To calculate the Shapley function, suppose we form the grand coalition (the coalition containing all n players) by entering the players into this coalition one at a time. As each player enters the coalition, he is charged the cost by which his entry increases the cost of the coalition he has entered. The cost a player pays by this scheme depends on the order in which the players enter. The Shapley value is just the average cost charged to the players if they enter in a completely random order, i.e.

φ i = S⊂I,i∈S (|S| -1)!(n -|S|)! n! (v(S) -v(S -{i})). (2)
Table 1: Hexagon network scenario: characteristic function values, v(S), for denitions (1),

(2) and (3).

Characteristic Function value (v(S ))

Coalition (S ) Denition ( 1) Denition ( 2) Denition ( 3)

∅ 0 0 0 1 1 1 1 2 2.5- 2.5 - 3- 3 0.5 1 1 12 3 3 3 13 1.5 1.5 2 23 3- 3- 3- 123 4- 4- 4-
It can be proved that the problem of computing the Shapley value is an NP-complete problem. Polynomial methods, based on sampling theory, have been proposed in [START_REF] Castro | Polynomial calculation of the Shapley value based on sampling[END_REF] for approximating the Shapley value; these estimations, though, are ecient only if the worth of any coalition S can be calculated in polynomial time, which is not the case for our problem.

In fact, even using the approximation methods proposed for example in [START_REF] Castro | Polynomial calculation of the Shapley value based on sampling[END_REF], it is necessary to compute the worth of an extremely large number of coalitions, which is computationally very cumbersome, while as we see next, our proposed Nash bargaining solution needs only computing the worth of the grand coalition.

The Nash bargaining solution (NBS)

Since the computation cost of the Shapley value can be extremely high in network scenarios with many players, in this paper we consider another approach to cooperative game: Nash bargaining. We will show that the computation of the Nash bargaining solution is very light.

Let u i denote the maximal acceptable cost that user i is willing to pay. In the present work we suggest the following three options:

1. the cost for user i to connect its source-destination nodes in a purely non-cooperative game (i.e., the Nash equilibrium solution);

2. the cost for user i to connect its source-destination nodes in a zero-sum game where all the other players are trying to maximize the cost of user i;

3. the cost for user i to connect its source-destination nodes when there is no other player.

The vector u = {u 1 , u 2 , . . . u n } is also denoted as the disagreement point of the cooperative network formation game (i.e., what will happen if players cannot come to an agreement).

Clearly, the cost achieved by every player at any agreement point (every possible outcome INRIA of the bargaining game) has to be at most equal to the cost achieved at the disagreement point.

We now derive a Nash bargaining solution for allocating the total network cost to users.

To this aim, we extend the well-known two-player NBS concept to the n-player network formation game, considering transferable network costs, providing explicit expressions. This assumption means that the players or the system administrator can redistribute the total cost among the players.

Let u soc denote the total network cost resulting from social optimization. This can be computed, for example, formulating the generalized Steiner Tree problem [START_REF] Khan | Ecient distributed approximation algorithms via probabilistic tree embeddings[END_REF] with an Integer Linear Program, using a mathematical programming model (like AMPL [START_REF]AMPL: a modeling language for mathematical programming[END_REF]), and solving it with a commercial solver (like CPLEX [START_REF]ILOG Optimization Products[END_REF]). Solving such problem provides the least-cost network topology that connects all source-destination pairs.

Then, the Nash bargaining solution can be given in explicit form.

Theorem 2 The Nash bargaining solution for player i, α i is given by the following expression:

α i = u i -k u k -u soc m , (3)
where m coincides with the number of players n (i.e., m ≡ n) if we allow for negative costs (i.e., some α i values are negative, which means that some players are actually paid to ensure their participation). Otherwise, if only non-negative costs are allowed (or equivalently, if no positive transfers are permitted), m is dened as the largest integer for which the following inequality is satised:

1 m -1 ( m-1 i=1 u i -u soc ) < u m (4)
having assumed, without loss of generality, that players are ordered such that u 1 ≥ u 2 ≥ . . . ≥ u n .

Proof: See the Appendix.

We would like to emphasize that in the rst case α values can be positive or negative, while in the second case α values are non-negative. In particular, m gives the number of nonzero α values, i.e., α 1 , α 2 , . . . α m are positive and given by expression (3), while α m+1 , . . . α n are equal to zero.

Distributed algorithm for computing the NBS

We now outline a distributed algorithm for computing the Nash bargaining solution. The minimal requirements u i , ∀i ∈ I, dened in the previous section, can be easily computed.

In the rst two cases, it can be observed that the computation of the Nash equilibrium solution for a non-cooperative network formation game can be performed in a distributed way, since the best-response dynamics is guaranteed to converge to a pure Nash equilibrium.

RR n°7480

As for the third denition, the problem is simply to compute the least-cost path between all source-destination pairs, for which there exist several distributed algorithms.

In order to compute the Nash bargaining solution given by expression (3), it is necessary to nd the cost of the socially optimal network (u soc ). To this aim, the technique proposed in [START_REF] Khan | Ecient distributed approximation algorithms via probabilistic tree embeddings[END_REF] can be used. This is one of the rst distributed algorithms proposed for the Generalized Steiner tree problem; it is a probabilistic algorithm with O(log n) expected approximation, based on a probabilistic tree embedding due to Fakcharoenphol et al. [START_REF] Fakcharoenphol | A tight bound on approximating arbitrary metrics by tree metrics[END_REF].

Then, each player i to calculate the NBS solution α i needs only to know the disagreement point u of the cooperative game; this can be simply achieved by each player broadcasting its minimal requirement u i to all other players.

Numerical Results

This section reports the numerical results obtained applying our proposed Nash bargaining solution (NBS) to cooperative network design games played in dierent network scenarios, including simple network instances and more complex random topologies. The NBS, computed as illustrated in the previous section, is compared both to the cost allocation provided by the Shapley value, as well as to a Nash equilibrium solution. This latter is determined in the non-cooperative network formation framework proposed in [START_REF] Anshelevich | The price of stability for network design with fair cost allocation[END_REF], revised in Section 2, starting from the empty network and using a best response algorithm where each user greedily minimizes its path cost until an equilibrium is reached.

We assume that positive transfers are allowed. To compute the Shapley value, we further assume that the worth of a coalition S is the minimum cost that its members would incur if players in I -S would be absent (denition 3). This allows us to consider the worst case, i.e. the costlier denition for a coalition, as discussed before. As for the disagreement point u i in the NBS, we reasonably assume that it is the cost for user i to connect its sourcedestination nodes in a purely non-cooperative game (i.e., the Nash equilibrium solution).

However, we underline that our proposed NBS approach is general and can be applied to any problem setting. The investigation of the impact of other characteristic function and disagreement point choices is left as future research issue.

Let us rst consider the simple network scenario already illustrated in Figure 1, with 6 links and 3 players. The optimal network cost is here u soc = 4 -, and coincides with the cost of the network formed at the Nash Equilibrium Point (NEP). The Nash equilibrium and the Shapley value solutions for this scenario are reported in Table 2, together with the Nash bargaining solution, which in this case coincides with the NEP.

Numerical results show that the solution given by the Shapley value for player 3 ( 5-2 6 ≈ 0.83) is costlier than that of the Nash equilibrium, 0.5. We further observe that even dening the value of a coalition as its security level (denition 2, Section 3.2) leads to the same Shapley values reported in Table 2. As a consequence, the Shapley value solution is somehow unstable for all the considered denitions of the characteristic function, since some players (i.e., player 3 in this scenario) can deviate to reduce their cost. This is surprising, because the Shapley value satises the individual rationality property, so that the Shapley value INRIA ≈ 0.83

NBS 1 2.5 - 0.5
allocation is always preferable for each player than playing alone. The apparent paradox originates from the fact that the value of the single player coalition has been dened either as the cost incurred if all other players are absent (denition 3), or as its security value, considering that all the other players are trying to maximize its cost (denition 2). In reality, at the Nash equilibrium, the cost of player i is smaller than such values and, as we have shown, it can be even smaller than the Shapley value imputation.

The same behavior can be observed also in more general topologies. To show this, we considered random network scenarios generated as follows: we randomly extract the position of N nodes, uniformly distributed on a square area with edge equal to 1000. As for the network links, which can be bought by players to connect their endpoints, we consider random geometric graphs, where links exist between any two nodes located within a range R. The link cost is set to its length. Tables 3,[START_REF] Epstein | Strong equilibrium in cost sharing connection games[END_REF] and Figure 2 illustrate the results obtained in a random geometric graph scenario with 50 nodes, range R = 500 (which means approximately more than 1200 links) and, respectively, 5, 10 and 15 source-destination pairs (players). The tables and gure report the costs for the players reached at the Nash equilibrium, the Shapley value as well as our proposed Nash bargaining solution. The total network cost is reported in the last column;

note that such values corresponds, for the Shapley value and the Nash bargaining allocation algorithms, to the socially optimal solution (u soc parameter), which can be obtained as explained in Section 3.)

It can be observed that, in all scenarios, at least 2 players (marked in bold in the tables, with arrows in Figure 2) have a Shapley value that is higher than the Nash equilibrium cost.

However, the cost saving between the NEP and the optimal cost (which is approximately 700 and 1250 for the n = 10 and n = 15 scenarios, respectively) could be re-distributed,

which is what the Nash bargaining solution does, increasing the appeal of the cost sharing solution.

Obviously, since both the Shapley value and the NBS distribute the social cost (u soc ) among the players, there will be players whose allocation is costlier under the NBS than with the Shapley value allocation. This happens, in the numerical example we considered, for players that have a large cost at the Nash equilibrium. However, every player is always better o under the NBS allocation than at the Nash equilibrium, since cost savings are redistributed.

Conclusion

In this paper we proposed a novel and ecient Nash bargaining solution for the cooperative network formation problem with n players. Our solution has very appealing properties in terms of planning ecient networks and determining cost allocations in a very short computation time.

INRIA

We compared our proposed solution to classic approaches, like the Shapley value and the Nash equilibrium concepts, in simple and large-size network topologies, with an increasing number of players.

Numerical results demonstrate that our approach permits to achieve very eective cost allocations, thus representing an ecient an promising framework for the planning of stable networks.

Let us rst consider the charateristic function dened as in [START_REF] Chen | Network design with weighted players[END_REF]. We prove the result directly for pure strategy games, i.e. when players cannot use more paths according to a probability distribution.

Let µ S be a strategy available to players in S, i.e. µ S ∈ × i∈S A i . Observe that given a strategy for the coalition S ∪ T , µ(S ∪ T ), it can be expressed as product of a strategy of coalition S and a strategy of coalition T . We denote C S the total cost paid by users in S for a given outcome of the game (for a given set of strategies of the players). Then, we can express denition (2) as follows:

v(S) = min µ S max µ(I-S)
C S (µ S , µ(I -S)).

Let us consider then the value of the coalition S ∪ T , we denote by V the set I -(S ∪ T ):

v(S ∪ T ) = min µ(S∪T ) max µ V C S∪T (µ S∪T , µ V ) = = min µ S ,µ T max µ V (C S (µ S , µ T , µ V ) + C T (µ S , µ T , µ V )) ≤ ≤ min µ S ,µ T max µ V ,μ T C S (µ S , μT , µ V ) + max µ V ,μ S C T (μ S , µ T , µ V ) = = min µ S max µ V ,μ T C S (µ S , μT , µ V ) + min µ T max µ V ,μ S C T (μ S , µ T , µ V ) = = min µ S max µ I-S C S (µ S , µ I-S ) + min µ T max µ I-T C T (µ T , µ I-T ) = = v(S) + v(T ).
If we consider also mixed strategies, then the result follows immediately from the following theorem in [START_REF] Petrosyan | Theory of games[END_REF].

is subadditive.

The fact that the function dened by ( 2) is subadditive in the case of mixed strategies follows immediately from the above theorem.

In order to prove that the function dened by ( 3) is also subadditive we modify the network, so that the characteristic function according to (3) in the original game coincides with the characteristic function according to (2) in the modied network. In particular, we introduce auxiliary links with innite cost connecting source and destination nodes of each player. Now, the best strategy for the coalition I -S in the setting (2) is just to choose these auxiliary links, that is equivalent to remove the players in I -S from the game (as required by denition (3)). Thus, subadditivity of the characteristic function (3) follows from above results for function [START_REF] Chen | Network design with weighted players[END_REF].

It is interesting to observe that in this case every player gains an equal share of the dierence between the total cost of the Nash equilibrium and the total socially optimal cost. Some player might actually be reimbursed.

B. [START_REF] Chen | Network design with weighted players[END_REF] The case with the requirement on the positivity of costs

In this case, in addition to the equality constraint [START_REF] Azad | From Altruism to Non-Cooperation in Routing Games[END_REF], we have n inequality constraints α i ≥ 0, i = 1, ..., n. [START_REF] Nash | The bargaining problem[END_REF] This formulation corresponds to the following Lagrangian

L P = n i=1 (u i -α i ) + n i=1 λ i α i + µ( n i=1 α i -u soc ).
The Karush-Kuhn-Tucker condition takes the form:

∂L P ∂α j = - i =j (u i -α i ) + λ j + µ = 0, (11)
λ i ≥ 0, λ i α i = 0, i = 1, ..., n,

plus conditions ( 7) and [START_REF] Nash | The bargaining problem[END_REF].

Without loss of generality, we have ordered the players such that u 1 ≥ u 2 ≥ ... ≥ u n . It follows that α 1 ≥ α 2 ≥ ... ≥ α n . In fact, let us assume that u i > u j (then i < j) and α j > α i : the vector of costs (α 1 , • • • , α i-1 , α i , • • • , α j-1 , α j , • • • , α n ) cannot be a solution of the problem (6), since the vector (α 1 , • • • , α i-1 , α j , • • • α j-1 , α i , • • • , α n ) corresponds to a higher value of the optimization function, being that (u i -α j )(u j -α i ) > (u i -α i )(u j -α j ).

Let us denote by m the number of non-zero α's. In particular, it may happen that m = n. We shall now illustrate how to determine m.

If α 1 , ..., α m > 0, by the complementarity slackness condition λ i α i = 0, we have λ i = 0 for i = 1, ..., m. Similarly to the rst case, multiplying [START_REF] Van Den Nouweland | Models of network formation in cooperative games[END_REF] by (u j -α j ) and dividing by µ, we conclude that u j -α j = δ, j = 1, ..., m.

In addition, from [START_REF] Van Den Nouweland | Models of network formation in cooperative games[END_REF] we have: µ = (u 1 -α 1 )(u 3 -α 3 )...(u m -α m )u m+1 ...u n = δm-1 u m+1 ...u n .

Then, for k such that m + 1 ≤ k ≤ n, the equation [START_REF] Van Den Nouweland | Models of network formation in cooperative games[END_REF] gives

∂L P ∂α k = - i =k (u i -α i ) + λ k + µ = 0,

Figure 2 :

 2 Figure 2: Random geometric network scenario with 15 players. The gure reports the cost paid by each player at the NEP, the Shapley value and the NBS. The total network cost is equal to 5076.0 at the NEP and to 3802.7 for the Shapley value and NBS allocations.

Theorem 3

 3 Denote by C S (µ S , ν I-S ) the cost of the coalition S in the zero-sum game between coalition S and I -S, where µ S is the strategy of coalition S and ν I-S is the strategy of coalition I -S. Then the function v(S) = inf µ S sup ν I-S C S (µ S , ν I-S )

-(u 1 -

 1 α 1 )...(u m -α m )u m+1 ...u k-1 u k+1 ...u n + λ k + µ = 0, RR n°7480

Table 1

 1

reports, for each of the three above denitions, the corresponding characteristic function values.

It can be easily checked that denition

[START_REF] Anshelevich | The price of stability for network design with fair cost allocation[END_REF]

does not lead to a characteristic function, since the subadditivity property is not satised (for example, v(12)+v(3) < v(123)), and therefore it cannot be used to compute Shapley values. Indeed, with such denition, cooperation among players can lead to costlier solutions. On the other hand, denitions (2) and (3) lead to characteristic functions.

Table 2 :

 2 Hexagon network scenario with 3 players. The table reports the cost paid by each player at the Nash Equilibrium Point, the Shapley value and the Nash bargaining solution.The total network cost is equal to 4for all allocation algorithms.

	Algorithm	(s 1 , t 1 )	(s 2 , t 2 )	(s 3 , t 3 )
	NEP	1	2.5 -	0.5
	Shapley value	5+ 6 ≈ 0.83 14-5 6	≈ 2.33 5-2 6

Table 3 :

 3 Random geometric network scenario with 5 players. The table reports the cost paid by each player at the Nash Equilibrium Point, the Shapley value and the Nash bargaining solution. The total network cost is also reported.

	Algorithm	P1	P2	P3	P4	P5	Total cost
	NEP	299.1	149.4	400.0	824.4	580.3	2253.1
	Shapley value	298.9	167.5	380.4	817.3	589.0	2253.1
	NBS	299.1	149.4	400.0	824.4	580.3	2253.1

Table 4 :

 4 Random geometric network scenario with 10 players. The table reports the cost paid by each player at the Nash Equilibrium Point, the Shapley value and the Nash bargaining solution. The total network cost is also reported. Furthermore, we observe that computing the Shapley value for n = 15 players took several weeks of computation on the workstation used to obtain the numerical results reported in this paper, i.e., an Intel Pentium 4 (TM) processor with CPUs operating at 3 GHz and with 1024 Mbyte of RAM. Therefore, computing the Shapley value for a larger number of players is practically infeasible in such network scenario. On the other hand, our proposed

	Algorithm	P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	Total cost
	NEP	283.0	149.4	235.3	824.4	714.8	450.5	674.0	195.6	186.0	266.9	3979.9
	Shapley value	260.5	170.6	253.9	717.1	472.8	387.5	508.0	142.5	183.8	175.6	3272.2
	NBS	212.3	78.6	164.6	753.6	644.0	379.7	603.2	124.8	115.3	196.2	3272.2

n-person Nash bargaining solution is very simple to calculate, and could be computed within a few minutes in all considered network scenarios, thus representing a practical and ecient solution to the network formation problem.

RR n°7480

http://www.inria.fr ISSN 0249-6399

B Proof of Theorem 2

We consider a Nash bargaining solution for the n-players cooperative game with transferable cost. The assumption about the transferable cost means that the players or the system administrator can redistribute the total cost among the players.

Then, the Nash bargaining solution is given by the following optimization problem:

Below we consider two cases: (a) individual costs α i can be negative (this can be interpreted as the coalition pays some members to ensure their participation) and (b) costs cannot be negative, i.e., no positive transfers are allowed; this precludes paying players to participate to the network.

Both scenarios make practical sense.

B.1 The case without the requirement on the positivity of costs

If there are no positivity constraints on α i , the Lagrangian is given by

and the Karush-Kuhn-Tucker condition takes the form:

plus constraint [START_REF] Azad | From Altruism to Non-Cooperation in Routing Games[END_REF]. Multiplying ( 8) by (u j -α j ) and dividing by µ, we obtain

Hence, the dierence u j -α j for the optimal solution does not depend on the index j and we can denote its value by δ. Thus, we have

where the value of δ can be found from condition [START_REF] Azad | From Altruism to Non-Cooperation in Routing Games[END_REF]:

Since according to the Karush-Kuhn-Tucker condition λ i must be non-negative, we obtain the following condition

This condition allows us to determine m. Before proceeding towards this goal, we determine δ from condition [START_REF] Azad | From Altruism to Non-Cooperation in Routing Games[END_REF], which gives us

Then, we have the following algorithm to determine m: rst, check if

If it is the case, then all α i are positive. We note that (

This m gives the number of non-zero α's.

INRIA