{'fraction_non_alphanumeric': 0.0385025313082867, 'fraction_numerical': 0.010769162447819522, 'mean_word_length': 4.229563399907106, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cooperative Precoding/Resource Allocation Games under Spectral Mask and Total Power Constraints

The use of orthogonal signaling schemes such as time-, frequency-, or code-division multiplexing (T-, F-, CDM) in multi-user systems allows for power-efficient simple receivers. It is shown in this paper that by using orthogonal signaling on frequency selective fading channels, the cooperative Nash bargaining (NB)-based precoding games for multi-user systems, which aim at maximizing the information rates of all users, are simplified to the corresponding cooperative resource allocation games. The latter provides additional practically desired simplifications to transmitter design and significantly reduces the overhead during user cooperation. The complexity of the corresponding precoding/resource allocation games, however, depends on the constraints imposed on the users. If only spectral mask constraints are present, the corresponding cooperative NB problem can be formulated as a convex optimization problem and solved efficiently in a distributed manner using dual decomposition based algorithm. However, the NB problem is non-convex if total power constraints are also imposed on the users. In this case, the complexity associate with finding the NB solution is unacceptably high. Therefore, the multi-user systems are categorized into bandwidth- and power-dominant based on a bottleneck resource, and different manners of cooperation are developed for each type of systems for the case of two-users. Such classification guarantees that the solution obtained in each case is Pareto-optimal and actually can be identical to the optimal solution, while the complexity is significantly reduced. Simulation results demonstrate the efficiency of the proposed cooperative precoding/resource allocation strategies and the reduced complexity of the proposed algorithms.


I. INTRODUCTION
In multi-user systems, all users compete for resources and can cause interference to each other. This makes it impossible for any user to gain more profit without harming other users.
The traditional information-theoretic studies of multi-user systems are mainly focused on finding the corresponding rate regions and do not advise how to actually achieve the best rates for all users simultaneously (see [1]- [4] and the references therein). It is, however, evident that the performance of multi-user systems depends on the balance among the users in the competition for resources. Moreover, the points in the achievable rate region are not all stable, or even feasible if the selfish nature of the users is taken into account. Indeed, it is reasonable to assume that all users will compete for the maximum achievable benefits at all times, which may render difficulties to the implementation of any prescribed regulations against the selfishness of users.
For example, although an outcome corresponding to the case when one user is forced to sacrifice its performance for the benefit of other users can be theoretically justified, it is hard to make sure in practice that the sacrificed user will not deviate from the regulation which is unfair for him.
Recently, game theory has been recognized as an appropriate tool for studying multi-user systems [5]- [20]. It studies the actions of decision makers (players, here wireless users) with conflicting objectives, and predicts the users' decisions on future actions (strategies) and the outcome of the game. If users compete with each other, the existence of "stable" outcomes, corresponding to the so-called equilibria, can be analyzed [8]- [10]. On the other hand, if there is a voluntary cooperation among users, the extra benefits for all users can be obtained. The corresponding games are called cooperative games and one of the most popular approaches developed for cooperative games is the Nash bargaining (NB) approach [21].
Although the use of cooperative game theory to recourse allocation in multi-user wireless systems is a recent research topic, there are some results available. A two-user power allocation game on a flat fading channel (FFC) is investigated in [13]. It is argued that certain points in the utility space of the game (i.e., the information-theoretic rate region of the multi-user system) are not achievable from a game-theoretic perspective. It is also shown that the NB solution based on time division multiplexing (TDM) increases the benefits of all users as compared to the noncooperative Nash equilibrium (NE) solution. The study is extended in [14] to N-user systems with frequency selective fading channels (FSFCs) for the case when only spectral mask constraints (SMCs) are imposed on the users. The NB solution is derived based on joint TDM/frequency division multiplexing (TDM/FDM) scheme. Unlike the FFC case, the allocation of frequency bins becomes a major problem on the FSFC. A more complex resource allocation game on the FSFC with only total power constraints (TPCs) limiting the total transmission power of each user is considered in [15]. A water-filling based algorithm is proposed to search for the NB solution in a two-user version of the game. The proposed algorithm bargains in many different convex subspaces of the original utility space and obtains one NB solution in each subspace. Then, the NB solution with the largest outcome is selected. However, the TPCs render the complexity of the algorithm high.
One more application area of cooperative game theory is beamforming in multiple-input singleoutput (MISO) systems [16]- [20]. A two-user game on interference channel is investigated in [16], where user strategies are defined as the choices of beamforming vectors. The superiority of the cooperative NB solution over the non-cooperative NE solution is demonstrated, and some special points such as sum-rate and zero-forcing points are shown to be unstable from a gametheoretic viewpoint. Kalai-Smorodinsky-type solutions of cooperative beamforming games are further derived in [18]. For the games on two-user MISO systems, it is also shown in [19] and [20] that any Pareto-optimal point in the game's utility space can be realized through a certain balance between competition and cooperation among the users.
Game theory has been also used for precoding design. A non-cooperative precoding game is analyzed in [9] under SMCS and TPCs, in which a multi-user FSFC is considered and the optimal precoding matrices are derived based on the NE. It is shown that the matrix-valued precoding games boil down to equivalent vector-valued power allocation games, and the resulted precoding matrices adopt a diagonal structure. 1 The existence and uniqueness of the NE is guaranteed if the communication links are sufficiently far away from each other, and the NE is more efficient when the interference power is relatively low as compared to the noise power. Although non-cooperative games do not coordinate users and, therefore, allow for low-complexity and distributed solutions, they often lead to quite inefficient results for all users due to the lack of coordination. 1 The precoding matrices were mistakenly expressed in [9] as a product of the inverse fast Fourier transform (IFFT) matrices and power allocation diagonal matrices, while they should be expressed only as power allocation diagonal matrices.
In this paper, we develop cooperative NB-based precoding strategies for the multi-user wireless systems using cooperative game theory. 2 The main contribution of this paper is threefold. First, it is shown that cooperative precoding games boil down to cooperative resource allocation games under orthogonal signaling set up, that is, the TDM-based cooperation among users for FFCs or the TDM/FDM-based cooperation for FSFCs. The precoding matrices adopt a strictly diagonal structure in these cases. Second, we show that the process of bargaining among users can be physically realized in a distributed and efficient manner with very low information overhead if only SMCs are imposed on the users. Third, efficient algorithms for the precoding/resourse allocation games are developed for the case when both SMCs and TPCs are imposed on the users. Although the bargaining problem appears to be non-convex, efficient algorithms are designed based on a proposed classification of the multi-user systems into bandwidth-and power-dominant. Then, different manners of cooperation are developed for each type of the systems. Such classification guarantees that the solution obtained for each type of the systems is Pareto-optimal and actually can be identical to the optimal solution. Moreover, the complexity is significantly reduced as compared to the complexity required for solving the original problem using exact algorithms.
The rest of this paper is organized as follows. The signal model is introduced and the cooperative precoding/resource allocation game is formulated in Section II. The precoding/resource allocation strategies for cooperative games with SMCs are studied in Section III. Section IV deals with the two-user games with both SMCs and TPCs. Section V demonstrates our simulation results. It is followed by Section VI that concludes the paper. All proofs for Sections II, III, and IV are summarized in Appendices A, B, and C, respectively. This paper is reproducible research [25] and the software needed to generate the numerical results can be obtained from www.ece.ualberta.ca/∼vorobyov/ ProgNB.zip.

A. System model
Consider an M-user wireless system in which all users transmit on the same wideband FSFC with channel length L where L depends on the channel delay spread and the signal symbol duration [27]. 3 Assuming block transmission with block length N for all users, the general signal model for user i can be written as where s i is the N × 1 information symbol block of user i, F i is the N × N precoding matrix of user i, G i is the N × N decoding matrix of user i, H ji is the N × N channel matrix between users j and i, n i is the N × 1 zero-mean additive white Gaussian noise vector with covariance i is the variance of s i , and (·) H , E{·}, and I stand for the Hermitian transpose, expectation operation, and identity matrix, respectively. The information symbols are assumed to have unit-energy and be uncorrelated to each other and to noise, i.e., E{s i s H i } = I and E{s i n H i } = 0, where 0 denotes the matrix of zeros. In order to decompose a wideband FSFC to flat fading frequency bins, orthogonal frequency division multiplexing (OFDM) is adopted. Specifically, assuming that the block length N is larger than the channel length L, introducing cyclic prefix (CP), and performing IFFT and fast Fourier transform (FFT) at the transmitter and receiver sides, respectively, the signal model can be written as [9], [26], [27] whereñ i = M j=1,j =i Φ ji F j s j + Dn i is the N × 1 interference plus noise vector of user i before the decoder, D is the FFT matrix, Φ ji is the N × N diagonalized channel matrix between users j and i with its kth element being the sampled frequency response of the kth frequency bin.
Both the desired communication channel H ii and the interference channels H ji (∀j, j = i) are diagonalized due to the CP insertion and the multiplication by matrices D H and D at the transmitter and receiver sides, respectively.
Considering the general case when all users treat the interference as additive noise, the noise covariance for user i before the decoder can be expressed as Then, the Wiener filter is the optimal capacity-lossless linear receiver [28], [29]. Thus, the decoding matrix G i can be found as and the mutual information (information rate) that user i can achieve is expressed as [30] where F −i is the set of the precoding matrices of all users except user i and det(·) denotes the determinant.
In practice, all users attempt to maximize their information rates under certain power constrains. For the case of FSFC, SMCs are usually considered to limit the powers that the users can allocate on different frequency bin. These power limits are denoted as p max where Ω M = {1, · · · , M} is the set of user indexes, Ω N == {1, · · · , N} is the set of frequency bin indexes. Although SMCs also bound the total power by the value for user i, such bound may be loose compared to possibly imposed total power limit P max i .
Thus, TPCs may also be needed. The aforementioned SMCs and TPCs can be mathematically expressed, correspondingly, as where [·] kk and Tr{·} denotes the kth diagonal element and the trace of a square matrix.

B. Cooperative Precoding/Resourse Allocation Game
Considering the wireless users as players, the choices of precoding matrices as user strategies, and the corresponding information rates R i 's as user utilities, the game model of the precoding problem can be written as In the non-cooperative case, when the game players (wireless users) do not collaborate, the NE is a stable strategy combination of the game that satisfies where F NE i is the precoding strategy of user i in the NE, F NE −i is the combination of precoding strategies of all users except user i in the NE, and F ′ i stands for any possible precoding strategy for user i.
In the cooperative scenario, all users are willing to cooperate with each other and agree on a common principle in sharing the resources. If the users choose the NB approach as a cooperation principle, they aim at maximizing the Nash function (NF) defined in the cooperative utility space (rate region) as [31] where R ′ i is the information rate (the utility) that user i can achieve in the predefined disagreement point which the users will resort to if the cooperation breaks up.
In the NB game, the users need to specify also a manner of cooperation according to which the bargaining is performed. It is required that a particular manner of cooperation results in a convex utility space. In the literature, the users are assumed to cooperate with each other using orthogonal signaling schemes such as TDM for FFCs and joint TDM/FDM for FSFCs [13]- [15]. It allows no interference among the users. The main technical reason for considering orthogonal signaling is that the rate region of a general interference channel is yet unknown. Moreover, the use of orthogonal signaling allows for power-efficient simple receives, while it is indeed reasonable to assume that the users are equipped with simple matched-filter-based receivers. In addition, if the users are allowed to interfere with each other, they need to exchange the interference information to achieve a desirable performance. It may significantly increase the overhead in the system as well as it also significantly complicates the transceiver design. Therefore, orthogonal signaling is indeed a reasonable choice which is also adopted here. It is worth mentioning, however, that orthogonal signaling may be inefficient when the interference among the users is low [32]. In this case, the resulted rate region may be a small subset of the actual rate region.
However, it is proved in [32] that the cooperative bargaining problem becomes convex even without orthogonal signaling when the interference among users is small (as compared to the channel noise), which renders the problem simpler in this case. Moreover, the NE solution has a satisfactory performance in the low-interference situation, and cooperation may not be the best choice in this case considering the price paid for coordinating the users [9], [10]. Therefore, we focus on the case of high-interference in which orthogonal signaling schemes are efficient, i.e., the cooperative solutions based on orthogonal signaling achieves better performance than the non-cooperative solutions.
It has been shown in [9] that the non-cooperative precoding game can be simplified to a power allocation game under orthogonal signaling. The following theorem shows that the cooperative precoding game can be also simplified to a resource allocation game if orthogonal signaling is used, i.e., TDM is used in the case of FFCs or joint TDM/FDM is used in the case of FSFCs.

Theorem 1:
If the cooperation among users is based on orthogonal signaling, the precoding matrix of each user in the cooperative precoding game (8) which maximize the NF (10) under the constraints (6) and optionally (7) adopts a strictly diagonal structure.
Theorem 1 can be interpreted as follows. In order to maximize the utilities of all users in the cooperative precoding game, the users must adjust their precoding matrices to achieve the following two tasks: (i) coordinating the utilization of frequency bins (the public resources); (ii) allocating powers (the individual user resources) across the frequency bins. Therefore, the cooperative precoding game is more complex compared to the non-cooperative precoding game of [9] where the game is solved by performing only individual power allocations among frequency bins.
For further developments, two general assumptions need to be made: (i) The channel information of the desired channel H ii is known at both the transmitter and receiver sides of user i only; (ii) The TPCs are tight when they are taken into account, i.e., P max

III. COOPERATIVE PRECODING/RESOURCE ALLOCATION GAMES WITH SMCS
The following NB precoding/resource allocation problem with only SMCs is considered

A. Cooperative strategies for two-user game
The cooperative NB precoding/recourse allocation game (11) is first considered for two-users only, i.e., M = 2 and Ω M = Ω 2 . Any stable point in the utility region can be selected as a disagreement point. Since the NE point given by [9] is stable, it can be selected as a disagreement point. In (12), the N × 1 vector of power limits on different frequency bins, i.e., the spectral mask vector, and (·) T and diag(·) stand for the transpose and the operator that forms a square diagonal matrix by writing the elements of a vector in the main diagonal, respectively. It can be seen from (12) that each user exploits maximum allowed power on all frequency bins to maximize its rate.
Knowing the disagreement point, the manner of cooperation between users can be chosen as the joint TDM/FDM for FSFCs (see the arguments in the previous section). The joint TDM/FDM prescribes that any frequency bin can be used by only one user at any time instant, but it may be shared by different users throughout the operation time. The joint TDM/FDM can be implemented with low complexity and the corresponding rate region is guaranteed to be convex.
The following theorem about the structure of the optimal precoding matrices of the two-user TDM/FDM cooperative game (11) on FSFCs is in order.

Theorem 2:
The NB-based precoding/resource allocation optimal strategies for the twouser TDM/FDM-based cooperative precoding/resource allocation game (11) on the FSFCs are obtained through time sharing of at most two sets of diagonal precoding matrices denoted as The following conditions must be satisfied where i ∈ Ω 2 , l ∈ Ω 2 , k ∈ Ω N , and Theorem 2 states that the joint TDM/FDM-based cooperation on N frequency bins can be realized by the time sharing of two diagonal precoding matrices under SMCs. It can be also seen from the proof of Theorem 2 (see Appendix B) that only one frequency bin needs to be shared. Denote this frequency bin as k ⋆ and assume that [ Assuming that user 1 shares frequency bin k ⋆ for α portion of time (0 ≤ α ≤ 1), the information rate of user i ∈ Ω 2 can be written as Therefore, the two-user cooperative NB precoding/recourse allocation game (11) with the joint TDM/FDM cooperation scheme can be converted to the problem of finding k ⋆ and α and be simplified as follows. The information rate for user i given in (14) is the summation of user i's information rates on all frequency bins, and thus, can be rewritten as is the information rate that user i obtains on frequency bin k by using it exclusively for all times, and α i (k) is the time portion during which the frequency bin k is allocated to user i. Note that in the NB solution of the game, 0 < α i (k) < 1 (i ∈ Ω 2 ) hold only for k = k ⋆ . Then, taking the logarithm of the NF, the NB solution can be found by solving the following convex optimization problem where R NE i is the rate that user i obtains based on the NE solution. It is worth noting that the last constraint in (16) guarantees that both users can achieve higher rates than R NE through the joint TDM/FDM-based cooperation. Otherwise the users resort to the disagreement point and the cooperation breaks up.

B. Cooperative strategies for M-user game
Unlike the two-user case, where the NB solution of the cooperative precoding/resource allocation game can be formulated as a time sharing between two sets of precoding matrices, it is much more complex to coordinate the users' precoding matrices in the M-user game. The structure used for the two-user game can not be directly applied here, especially when the number of users is large. Therefore, to solve the M-user game, we first partition time into time slots each of length T to make it easier for the users to perform time sharing. Moreover, considering the case when the number of users or the channel states change over time, the time partitioning enables a timely update of the bargaining solution as long as time slots are small enough. In this case, the cooperative solution can be obtained through the procedure summarized in Table I. In the following we focus on the second step of the procedure in Table I.
As an extension of Theorem 2, the following theorem is in order. 3. Implementation: Implement the NB solution for one time slot. If any changes of the number of users or the channel states are detected during this time slot, go back to step 1 in the next slot; otherwise, repeat step 3.

Theorem 3: Precoding matrices corresponding to the NB solution of the TDM/FDM-based
M-user cooperative game on the FSFCs have the form with b i (k) and e i (k) representing, respectively, the starting and ending time moments between which frequency bin k is allocated to user i in a time slot [0, T ]. The following conditions are where t ∈ [0, T ] is the time instant in a current time slot.
The proof of Theorem 3 is similar to the proof of Theorem 2 and is omitted here. It is worth noting, however, that the difference is that unlike the two-user game in which at most one frequency bin needs to be shared, different groups of users may share different frequency bins in the M-user game. The first condition in (19) states that no frequency bin should be vacant at any time, while the second condition in (19) requests that no frequency bin be used by more than one user at any time. Moreover, it is the length of rather than the specific values of b i (k) and e i (k), that affects the rates of the users. Once the time portions α i (k) (∀i ∈ Ω M , ∀k ∈ Ω N ) are fixed, the order of using frequency bins is not important to the users. Thus, the key problem is to calculate the time portions that user i obtains on a frequency bin k. Mathematically, this problem can be formulated as the following optimization problem where R i is the sum of information rates that user i obtains on all frequency bins, that is, To avoid a centralized channel estimation and information exchange overhead among users on the cooperation stage, a distributed algorithm for solving (20) is developed next.

C. Distributed algorithm for finding the NB solution
The problem (20) is a convex optimization problem with a coupling constraint. Therefore, it can be solved in a distributed manner using the dual decomposition method.
The Lagrange dual problem to (20) is given as where λ(k) (∀k ∈ Ω N ) are the positive Lagrange multipliers.
The problem (22) can be further converted into a two-level optimization problem with the following lower level subproblems for each user i ∈ Ω M , and the higher level master problem where U i (λ) is the maximum value of the objective function in (23) given λ = [λ(1), . . . , The dual problem (23)- (24) can be solved based on a distributed structure with a coordinator.
Since the original problem is convex, strong duality holds and the solutions of the dual problem (22) and the original problem (20) are the same if Slater's condition is satisfied [33]. For our specific problem, we have the following result.

Theorem 4:
The Slater's condition is guaranteed to be satisfied for the problem (20) as long as the NB solution exists.
Theorem 4 can be used to further simplify the lower level problem (23). Substituting (21) into the objective function of the sub-problem (23), the latter can be rewritten as is the rate on frequency bin k for user i. The lower level subproblems are solved distributively by the corresponding users.
The Hessian of the objective function of the problem (25) can be written as Note that the coefficients λ(k) (k ∈ Ω N ) have specific physical meaning. Indeed, λ(k) represents the risk that cooperation among users breaks up due to a conflict on sharing frequency 1. The coordinator initializes λ = λ 0 = [λ 0 (1), λ 0 (2), ..., λ 0 (N )] T and broadcasts it to all users.
2. Each user solves (25) according to the present value of λ and transmits its solutions for α i (k), k ∈ Ω N to the coordinator.
3. The coordinator updates λ according to the gradient of the master problem (24) N ) where (·) + denotes the projection onto non-negative sub-space and δ is the step length of the algorithm.
Here, ξ is the stopping threshold of the algorithm. bin k. Thus, in the lower level subproblems, the objective for each user consists of two parts.
On one hand, a larger α i (k) is preferred to increase the total information rate of user i. On the other hand, if α i (k) becomes too large, the cooperation may break up and the utility of user i will return to the inferior competitive solution.

IV. COOPERATIVE PRECODING/RESOURCE ALLOCATION GAMES WITH SMCS AND TPCS
The following NB precoding/resource allocation problem with both SMCs and TPCs is con- Unlike the problem (11) considered in the previous section, the diagonal elements of the precoding matrices F i (∀i ∈ Ω M ) in (27) do not necessarily satisfy [F i ] k,k = p max (k) when frequency bin k is allocated to user i because of the total power constraint. However, if the joint TDM/FDM cooperation scheme is used, Theorem 1 applies, and F i (∀i ∈ Ω M ) can be written as Using the same train of arguments as in the previous section, (27) can be simplified as where p i = [p i (1), p i (2), . . . , p i (N)] is the power allocation vector for user i, R ′ i is the disagreement point for user i, and R i = is the sum information rate that user i can obtain. Unlike the problem (20) in the previous section, it can be seen that p i (i ∈ Ω M ) are also optimization variables in (29). Moreover, (29) is non-convex. Indeed, the Hessian matrix H f i of can be written as Thus In the following studies, the two-user case is considered and the disagreement point is chosen at the origin of the rate region, i.e., R ′ i = 0 (∀i ∈ Ω M ), instead of the NE point since finding the NE solution, in this case, is itself a complicated problem.

A. Bandwidth-dominant and power-dominant systems
Finding the TDM/FDM-based NB solution of the problem (29) requires joint power and frequency bin allocation for each user, and the resulting complexity of the two-user game can be unacceptably high. Moreover, the TDM/FDM-based cooperation can be inefficient in some cases when TPCs are present. To overcome these problems, we categorize systems into two types and deal with each type separately. Toward this end, two definitions need to be given first.

Definition 1:
A point x is Pareto-optimal in space S if and only if y = x for all y satisfying y x in S.
A Pareto-optimal point corresponds to an efficient allocation of system resources. The NB solution is one of the Pareto-optimal points in a utility space (rate region).
For the two-user cooperative game, there is a well known algorithm for obtaining the TDM/FDM-based NB solution if only SMCs are imposed on the users [13], [34]. According to this algorithm, the frequency bins are first arranged such that is the rate that user i can achieve on frequency bin k by using p max i (k) and allowing no interference from other users. Given any integerk ∈ Ω N , let Then the point R = [R 1 , R 2 ] is guaranteed to be Pareto-optimal in the rate region for any 0 ≤ β ≤ 1. Varyingk and β, all Pareto-optimal points can be obtained including the NB solution of the game with only SMCs.

Definition 2:
All Pareto-optimal points in a convex space S form the Pareto-boundary of S.
The NB solution for the two-user cooperative precoding/resource allocation game with only SMCs can be found by searching on the Pareto-boundary instead of the entire utility space of the game. The algorithm of [13] is based on the principle that frequency bins which are "better" for a certain user should be allocated to this user prior to the other frequency bins which are Ω 2 ) are used to derive the TDM/FDM coefficients α 1 (2) = (P max 1 − p max 1 (1)α 1 (1))/p max 1 (2) = 0.5 and α 2 (3) = (P max 2 −p max 2 (4)α 2 (4))/p max 2 (3) = 0.5. The resulting rates are R 1 = 1.5 and R 2 = 2.5, and the point (1.5, 2.5) is obviously not Pareto-optimal. For example, the strategies according to which frequency bin 2 is allocated to user 1 and frequency bin 3 is allocated to user 2 for the whole time provide higher rates than the allocation performed according to the aforementioned principle. It is because the principle in [13] considers only comparative advantages between the users, but not the absolute advantages.
It follows from the above discussion that the presence of TPCs renders a different bargaining problem since there is a need to coordinate between the power allocation and the frequency bin allocation. Therefore, a different approach has to be developed. Toward this end, note that we can first consider the solutions for the bargaining game with only SMCs (denoted as game G1), and then add TPCs to the game (denoted as game G2).
Observation 1: TPCs do not enlarge the utility space of the game. The Pareto-optimal solutions for game G1 are also Pareto-optimal for game G2 if they are achievable.
Denote the Pareto-boundary of the TDM/FDM utility space of game G1 as P. Then, the following proposition is in order.

Theorem 5:
Assume that the frequency bins are ordered such that

non-empty subset P can be achieved in game G2 under both SMCs and
TPCs if and only if there exist 1 ≤k ≤ N and 0 ≤α ≤ 1 such that Proof: See Appendix C.
According to (32), all multi-user systems can be categorized into bandwidth-and power-

Observation 2:
Beginning as a bandwidth-dominant, a multi-user system gradually changes towards a power-dominant as the number of available frequency bins increases.

B. Bandwidth-dominant systems: TDM/FDM based bargaining
In the bandwidth-dominant systems, the TDM/FDM-based cooperation is efficient in the sense that a non-empty subset P can be achieved in game G2. Denote the Pareto-boundary of the TDM/FDM utility space of G2 as P 2 . Then, for the bandwidth-dominant systems, the bargaining can be restricted in the set P ′ = P 2 ∩ P only. The resulted NB solution, denoted as S ′ N B , can be sub-optimal as compared to the optimal solution of the non-convex optimization problem (29). It is because the power allocation (which is not the dominant factor in this case) is not optimized jointly with frequency bins allocation.
Denote the optimal NB solution of game G2 as S opt N B . Also denote the TDM/FDM utility spaces of games G1 and G2 as U 1 and U 2 , respectively. Then, the following theorem regarding the optimality of S ′ N B is in order.
Theorem 6 leads to the following two conclusions about the optimality of S ′ N B in the bandwidthdominant systems: (i) S ′ N B can be identical to the optimal TDM/FDM based NB solution; (ii) S ′ N B is guaranteed to be Pareto-optimal in U 1 (which is larger than U 2 ) even if the optimal NB solution is not Pareto-optimal.

C. Power-dominant systems: FDM/sampled time sharing-based bargaining
Let us now consider the case of power-dominant systems. The example given in Subsection IV-A is, in fact, an example of a power-dominant system. From this example, we can make the following observation. , and the general term water-filling is used to represent the specific meaning of finding the solution of the following convex problem which is a single-user multi-channel power allocation problem with constant ε i (j) = |[Φ ii ] jj | 2 /σ 2 i being a measure of the channel j for user i, which depends on the channel gain and channel noise. 1. Both users i ∈ Ω2 perform the water-filling (33) on B and obtain two sets of frequency binsBi (i ∈ Ω2).
Then, Bc =B1 TB 2 is the set of frequency bins under competition. 2. In the first round of this step, user 1 is allocated the set of frequency binsB1 and user 2 performs water-filling on B −B1. In round j (j goes from 2 to L = |Bc| where |Bc| denotes the cardinality of the set Bc), user 1 selects a subset, denoted as B j s , of j − 1 frequency bins with smallest channel gains from the set Bc and performs water-filling on B −B j s . Then, user 2 performs water-filling on the remaining frequency bins. After the Lth round, L points in the utility space are obtained.  Table III.
Let WF i (X ) denotes the water-filling operator for user i on the set of frequency bins X .
It returns the maximum rate that user i can obtain by optimizing its power allocation on X .
Let also the vector of rates R opt corresponding to the FDM/TS-based NB solution S opt N B be obtained by time sharing of two points (R opt1  TABLE IV   THE OVERALL ALGORITHM FOR THE TWO-USER NB GAME WITH SMCS AND TPCS. 1. Check the condition (32): If it is satisfied, go to step 2, otherwise, go to step 3. (λR opt1

System is bandwidth-dominant:
. Denote the sets of frequency bins allocated to the users in the points (R opt1 correspondingly. Then, the following theorem is in order.
Proof: See Appendix C.
The following conclusions can be drawn regarding S ′′ N B in the power-dominant systems: (i) S ′′ N B is the optimal FDM/STS based NB solution. Thus, it is a Pareto-optimal solution in the FDM/STS utility space; (ii) S ′′ N B can be identical to S opt N B ; (iii) The efficiency of S ′′ N B depends on the ratios ω 1 and ω 2 , where ω i = WF i (B opt i )/WF i (B −B i ).

D. The two-user algorithm
The overall algorithm, which combines both the bandwidth-dominant and power-dominant cases, for the two-user cooperative NB game is given in Table IV.
In the bandwidth-dominant case, the complexity of searching on P ′ is O(N). In the powerdominant case, the complexity of the algorithm in Table III is determined by the time sharing part, which is O(L 2 ), i.e., the complexity reduction as compared to O(4 N ) for the optimal FDM/TS based solution (where the time consumed on water-filling is neglected in both cases) is dramatically significant, especially for large N.

A. Cooperative precoding/resource allocation games with SMCs
In the first example, we assume that two users share four available frequency bins. The noise power σ 2 is 0.01 for both users on all frequency bins. The channel gains of the desired channels Φ 11 and Φ 22 are generated as Rayleigh random variables with mean 1. The channel gains of the interference channels Φ 12 and Φ 21 are generated as Rayleigh random variables with means 0.7 and 0.2, respectively. The elements of the spectral mask vector p max are also Rayleigh random variables with mean 1.
In Fig. 1, the NB solution computed according to Theorem 2 is shown together with the NE solution. The boundary of the TDM/FDM rate region is also included in the figure. Fig. 2 displays the values of the logarithm of the NF under different TDM/FDM frequency bin allocation schemes. In this figure, k is the frequency bin being shared and α is the fraction of time that user 1 uses the frequency bin k. It can be seen in Fig. 1 that the NB solution lies on the boundary of the TDM/FDM rate region and provides significantly larger rates to both users than the NE solution. Moreover, the NB solution is fair to both users. It can be also seen in Fig. 2 that the largest value of the logarithm of the NF corresponds to the optimal scheme that provides the NB solution.
In the second example, the distributed algorithm for the M-user game developed in Sec- tion III-C is tested. It is assumed that four users share six frequency bins. As in the previous example, channel gains of the desired and interference channels are generated as Rayleigh random  Table V for one of the runs. It can be seen from Fig. 3 and Table V that     It can be seen that the algorithm is time-efficient with a good choice of the step length.  In our last example, the power-dominant two-user system is considered. 4 The number of frequency bins varies from 4 to 9 (50 runs for each case). The total power limits of the users are set as P i = 2 (i ∈ Ω 2 ) for each user, and the power limits on different frequency bins are set to

VI. CONCLUSIONS
Cooperative NB-based precoding/resource allocation strategies on FSFCs are studied under SMCs and optionally TPCs. First, it is shown that the optimal precoding matrices adopt a strictly diagonal structure and the NB-based precoding game is equivalent to a corresponding resource allocation game if the users are not allowed to interfere with each other, i.e., orthogonal signaling is used. The use of orthogonal signaling is practically important since it significantly simplifies transceiver design and allows for significant reduction of the system overhead during user cooperation. Second, it is shown that the NB solution of the cooperative precoding/resource allocation game with only SMCs can be obtained efficiently in a distributed manner (a simple coordinator is required) with inevitable information exchanges among users. The developed twolevel user cooperation procedure avoids a large system overhead by enabling users to perform most of the computations individually using their local information. Third, it is shown that the cooperative NB-based precoding/resource allocation game with both SMCs and TPCs is nonconvex and finding its optimal solution requires joint optimization of the frequency bins (which is the public resource) and each user's transmit power (which is the individual resource) allocations.
The complexity of finding the optimal solution is unacceptably high in this case. Therefore, it is i I when the cooperation among users is based on orthogonal signaling such as, for example, TDM for FFCs or joint TDM/FDM for FSFCs. 5 Thus, The Hadamard's inequality (det(A) ≤ i a ii for a Hermitian positive semidefinite matrix A) suggests that the determinant in (35) is maximized when F i is diagonal. Moreover, the power constraints given in (6) and (7) are irrelevant to the non-diagonal elements of F i . Therefore, the optimal precoding matrices must be diagonal.

Proof of Theorem 2
As follows from Theorem 1, the optimal F l 1 and F l 2 (l ∈ Ω 2 ) are diagonal. The three conditions in (13) are based on the fact that the joint TDM/FDM is used. First, consider the FDM part.
Given any division of the frequency bins, both users will use maximum allowed power on all frequency bins allocated to them. Thus, the first condition in (13) follows.
The second condition in (13) is based on the fact that only one user is allowed on any given frequency bin at any time. Thus, there must be a user which allocates zero power on any given frequency bin at any time.
The third condition in (13) is based on the fact that the NB solution can be obtained by sharing at most a single frequency bin between both users. 6 The proof of the latter fact can be given by contradiction using the optimality of the NB solution.
Assume that the NB solution can be obtained only by sharing two or more frequency bins between both users and consider the case when two frequency bins m and n are shared. In the sharing scheme, user 2 uses a fraction α 1 of the time in frequency bin m and a fraction α 2 of the time in frequency bin n. Let R i (m) and R i (n) be the rates that user i can obtain by exclusively using frequency bins m and n, respectively. Without loss of generality, we assume that R 2 (m)/R 1 (m) ≥ R 2 (n)/R 1 (n). Then either of the following cases must happen: (i) if α 1 R 2 (m) + α 2 R 2 (n) ≥ R 2 (m), there exists γ ∈ [0, 1) such that α 1 R 2 (m) + α 2 R 2 (n) = R 2 (m) + γR 2 (n); (ii) if α 1 R 2 (m) + α 2 R 2 (n) < R 2 (m), there exists γ ∈ [0, 1) such that α 1 R 2 (m) + α 2 R 2 (n) = γR 2 (m).
Case (i) corresponds to the sharing scheme according to which only frequency bin n is shared between both users, and user 2 exploits a fraction γ of time on frequency bin n. According to this new sharing scheme, user 2 obtains the same rate on frequency bins m and n as that in the original scheme. Then the rate that user 1 can obtain on frequency bins m and n in the new scheme is The last inequality follows from the assumption that R 2 (m)/R 1 (m) ≥ R 2 (n)/R 1 (n). It can be seen from (36) that the rate that user 1 can obtain using the new sharing scheme is equal to or larger than that in the original scheme. This contradicts the assumption that the NB solution can be achieved only by sharing of two frequency bins between both users.
A similar result can be derived for Case (ii). Moreover, when more than two frequency bins are shared, the above proof can be used iteratively to obtain the same result. Therefore, the optimal solution can be obtained by sharing at most a single frequency bin between both users.
Thus, F 1 i (i ∈ Ω 2 ) can be obtained by adding/deleting a single diagonal element of F 2 i (i ∈ Ω 2 ) and the third condition in (13) follows.

Proof of Theorem 4
Since the constraints of the problem (20) are all linear, the Slater's condition reduces to two parts with the first part requiring that the feasible domain of i ) be open and the second part requiring that the feasible domain of the whole problem be non-empty.
It is straightforward to verify that the first part is satisfied. The second part is equivalent to the requirement of the existence of the NB solution. This completes the proof.

Proof of Theorem 5
First note that in game G1 any resource allocation scheme satisfying (31) results in a Paretooptimal point in the utility space, and vice versa. Thus, the statement of the theorem is equivalent to the statement that (32) is the sufficient and necessary condition to guarantee that at least one set of {k, β} satisfies the conditions (31). To prove the sufficiency, let (32) is satisfied,k =k, and β =α in (31). Then the resulting total powers used by the users are P ′ 1 =k for user 1 and P ′ 2 = N k=k+1 p max 2 (k) + (1 −α)p max 2 (k) for user 2. Using (32), it is easy to verify that P max 1 ≥ P ′ 1 and P max 2 ≥ P ′ 2 . Therefore, the sufficiency is proved. The necessity can be proved similarly using contradiction.

Proof of Theorem 6
The first part of the theorem follows from the independence on irrelevant alternatives property of the NB [35]. This property states that bargaining in a convex subset which contains the NB solution of the original set results in the same NB solution. Thus, it is clear that if S ′ N B = S opt N B , then S opt N B / ∈ P ′ . Since P ′ is the achievable subset of P in game G2, it is impossible that S opt N B ∈ P and S opt N B / ∈ P ′ simultaneously. Thus, if S opt N B / ∈ P ′ , then S opt N B / ∈ P as well. This completes the proof.

Proof of Theorem 7
Let R opt1 due to the Pareto-optimality. Let also R 1 = (R 1 1 , R 1 2 ) and R 2 = (R 2 1 , R 2 2 ) be two points generated in steps 2 and 3 of the algorithm summarized in Table III  . Denote the sets of frequency bins allocated to the users in the points R 1 and R 2 as (B 1 1 , B 1 2 ) and (B 2 1 , B 2 2 ), respectively. Recalling that R ′ i = 0 (∀i ∈ Ω 2 ), i.e., the disagreement point is the origin, the difference between the logarithm of the NF for R opt and the logarithm of the NF for R 1 can be obtained as .
where the inequalities hold because log λR opt1 ) and R 1 2 = WF 2 (B − B j 1 ). Here 1 ≤ j ≤ L stands for the index of the round in which R 1 2 is obtained by user 2. Furthermore, using the fact that WF 2 (B − B j 1 ) ≥ WF 2 (B −B 2 ), (37) can be simplified as It can be derived in a similar way that the difference d 2 between the logarithm of the NF for R opt and the logarithm of the NF for R 2 obeys the following inequality Finally, note that neither R 1 nor R 2 have been assumed to be the rates corresponding to the optimal FDM/STS-based NB solution. Indeed, R 1 and R 2 are just two of 2L points generated in steps 2 and 3 of the algorithm summarized in Table III, respectively. Thus, the rates corresponding to the actual solution returned by the algorithm are expected to be superior to the rates corresponding to the points R 1 and R 2 , or even equal to the rates in the optimal solution R opt . 7 Therefore, d ≤ min(d 1 , d 2 ) and d can be equal to zero. This completes the proof.