We consider noncooperative energy-efficient resource allocation in the interference channel. Energy efficiency is achieved when each system pays a price proportional to its allocated transmit power. In noncooperative game-theoretic notation, the power allocation chosen by the systems corresponds to the Nash equilibrium. We study the existence and characterize the uniqueness of this equilibrium. Afterwards, pricing to achieve energy-efficiency is examined. We introduce an arbitrator who determines the prices that satisfy minimum QoS requirements and minimize total power consumption. This energy-efficient assignment problem is formulated and solved. We compare our setting to that without pricing with regard to energy-efficiency by simulation. It is observed that pricing in this distributed setting achieves higher energy-efficiency in different interference regimes.
1. Introduction
Power management and energy-efficient communication is an important topic in future mobile communications and computing systems. Currently, 0.14% of the carbon emissions are contributed by the mobile telecommunications industry [1]. In order to improve the situation, we study new algorithms at physical and multiple-access layers. This includes resource allocation and power allocation. A common mobile communication scenario is where several communication system pairs utilize the same frequencies and are within interference range from one another. This setting is modeled by the interference channel (IFC). The transmitter-receiver pairs could belong to different operators and these are not necessarily connected. Therefore, noncooperative operation of the systems is assumed.
In a noncooperative scenario without pricing, systems transmit at highest possible powers to maximize their data rates. Transmitting at high powers, however, is detrimental to other users, because it induces interference which reduces their data rates. In such settings, spectrum sharing might lead to suboptimal operating points or equilibria [2]. The case of distributed resource allocation and the conflicts in noncooperative spectrum sharing are best analyzed using noncooperative game theory (e.g., for CDMA uplink in [3] and usage of auction mechanisms in [4]). An overview of power control using game theory is presented in [5]. Moreover, analysis of noncooperative and cooperative settings using game theory are performed in [6].
Anzeige
Studies have shown that the point of equilibrium in a noncooperative game is inefficient but can be improved by introducing a linear pricing [7]. Linear pricing means that each system has to pay an amount proportional to its transmit power. This encourages transmission at lower powers, which reduces the amount of interference and at the same time leads to a Pareto improvement in the users' payoffs. Pricing in multiple-access channels has also been investigated with respect to energy-efficiency in [8]. Studies in an economic framework demonstrates other advantages of proper implementation of pricing, for example, it provides incentives to service providers to upgrade their resources [9] or increase revenue [10].
In [11], the energy-efficiency of point-to-point communication systems is improved by sophisticated adaptation strategies. A coding theoretic approach is proposed in [12] where "green codes" for energy-efficient short-range communications are developed. Recent proposals define a utility function which incorporates the cost of transmission, for example, the price of spending power is considered in a binary variable in [13] and as an inverse factor in [14].
A similar utility function as in this paper is proposed in [15] for single-antenna systems and used to characterize the Nash equilibrium for the noncooperative power control game. Later in [16], the approach is extended to multiple-antenna channels in a related noncooperative game-theoretic setting. In [17], distributed pricing is introduced for power control and beamforming design to improve sum rate.
Different from previous works, we apply linear pricing to improve the energy-efficiency of an IFC with noncooperative selfish links to enable distributed implementation. Our objectives also include global stability and fairness. Compared to the work in [3], we do not assume that the channel states are chosen such that a unique global stable Nash equilibrium (NE) exists. Instead, we constrain the prices such that uniqueness and global stability follows. We derive the largest set of prices in which both the uniqueness of the NE and concurrent transmission are guaranteed, which is then utilized as a constraint in the optimization problem. The contribution is the derivation of the optimal pricing for transmit power minimization under minimum utility requirements and spectrum sharing constraints. If the utility requirements are feasible (Section 4.4), we derive a closed-form expression for the optimal prices (Proposition 6). Another relevant case is to minimize transmit powers such that rate requirements and global stability as well as fairness are achieved. These optimal power allocation and prices are presented in Section 5.3 and feasibility is checked in Proposition 8.
Anzeige
This paper is organized as follows. In Section 2, the system, channel, and the game models are presented. The game described is then studied in Section 3. Based on uniqueness analysis of the Nash equilibrium, we formulate and solve the energy-efficient optimization problem with minimum utility requirements and with minimum rate requirements constraints in Sections 4 and 5, respectively. In Section 6, simulations comparing the setting with and without pricing are presented. Section 7 concludes this paper.
2. Preliminaries
2.1. System Model
Two wireless links communicate on the same frequency band at the same time. Transmitter intends to transmit its signal to its corresponding receiver , (Figure 1). On simultaneous transmission, each receiver obtains a superposition of the signals transmitted from both transmitters. Assuming single-user decoding, the interfering signal is treated as additive noise. This system model can be extended to multiple system pairs. For convenience, we focus our analysis on two pairs.
Figure 1
System model.
×
The described competing links belong to different operators or wireless service providers. We assume that there exists an entity which can control the operators indirectly by rules or by changing their utility functions. We could think of this entity as a national or international regulatory body. In contrast to common long-term regulation, the utility function here changes on a smaller time-scale. The role of the arbitrator which represents this authority is discussed in Section 2.3.
A similar model is presented in the context of cognitive radios in [18], where the primary user decides on the prices which the secondary users have to pay for their transmission. The choice of the prices is not only for interference control but also for revenue maximization. The model in [19] involves multiple entities, that is, the primary users, who determine the prices imposed on secondary users to limit their aggregate and per-carrier interference in a distributed fashion.
2.2. Channel Model
We consider a quasistatic block-flat fading IFC in standard form [20]. The direct channel coefficients are unity. The cross-channel coefficients (CCC), which are the squared amplitudes of the channel gains, from to are denoted as . The noise at the receivers is independent additive white Gaussian with variance . The inverse noise power is denoted by , that is, . The transmitters and receivers are assumed to have perfect channel state information (CSI). The maximum achievable rate at receiver , analogously , is written as
(1)
where , , is the transmit power of . We assume no power constraint on the transmitters, that is, . It is shown later that the maximum power that would be utilized is nevertheless bounded due to a pricing factor.
2.3. Game Model
A game in strategic form consists of a set of players, a set of strategies that each player chooses from, and the payoffs which each player receives on application of a certain strategy profile. The players of our game are the communication links and are denoted by the corresponding subscript. The pure strategy of each player , , is the transmission power . The corresponding payoff is expressed in the utility function
(2)
where is given in (1) and is the power price for player . The second term in (2) is a pricing term, which linearly reduces the utility. This means that a payment is demanded from the player for the amount of power used. Without pricing, each user would use as much power as possible to transmit his signal [21]. The game is written as
(3)
We assume all players are rational and individually choose their strategies to maximize their utilities. The game is assumed to be static, which means that each player decides for one strategy once and for all. The outcome of this game is a Nash equilibrium (NE). An NE is a strategy profile in which no player can unilaterally increase his payoff by deviating from his NE strategy, that is, for player 1,
(4)
and similarly for player 2.
The best response, , of a player is the strategy or set of strategies that maximize his utility function for a given strategy of the other player. Since the player's utility function is concave in his own strategy, the best response is unique and given as the solution of the first derivative being zero. The best response for player 1 is written as
(5)
where denotes . The highest power a transmitter may allocate is given as
(6)
which is achieved when the counter transmitter allocates no power, that is, . Thus, the strategy region of player could be confined to .
The authority that can control the elements of the game is assumed to determine the power prices, and . It receives either utility or rate demands from the users and checks if they are feasible. If they are, it calculates the prices and informs the system pairs about the prices imposed on them. The links will have to pay costs proportional to their transmit power, that is, and (Figure 1). In game-theoretic notation, this entity is called the arbitrator [22]. The arbitrator is not a player in the game and chooses the equilibrium that meets certain criteria. In our case, these criteria would be fairness, energy-efficiency, and minimum utility requirements or minimum rate requirements. We assume that the arbitrator also has complete game information.
In contrast to the case in which a central controller decides on the power of the users, the arbitrator imposes prices such that the users voluntarily set their powers. Thereby, the arbitrator indirectly determines the power allocation. In this paper, we study short-term price adaptation based on perfect CSI where prices depend on the instantaneous channel state. Long-term price adaptation based on partial CSI can also be implemented but is not considered here but left for future work.
3. Noncooperative Game
In this section, we study the game described in Section 2.3. This is done by investigating the existence of pure strategy NEs and characterizing the conditions for uniqueness.
3.1. Existence of Nash Equilibrium
There exists a pure strategy NE in a game if the following two conditions are satisfied [23]. First, the strategy spaces of the players should be nonempty compact convex subsets of an Euclidean space. Second, the utility functions of the players should be continuous in the strategies of all players and quasiconcave in the strategy of the corresponding player.
The first condition is satisfied in our game given in (3) because the strategy space of player is . The second condition is satisfied for the following reasons. First, it is obvious that the utility functions are continuous in the players' strategies. Second, knowing that all concave functions are quasi-concave functions [24], we can prove the concavity of our utility function with respect to the corresponding player's strategy by showing that
(7)
This condition is satisfied for player 1 and similarly for player 2. Next, we analyze the number of NEs that exist and state the related conditions.
3.2. Uniqueness of Nash Equilibrium
In this section, we study the conditions that lead to a unique NE. Under these conditions and considering only the case where the spectrum is simultaneously utilized by the two systems, we prove that the best response dynamics are globally convergent. Under these conditions, the noncooperative systems are guaranteed to operate in the NE if they iteratively apply their best response strategies.
Proposition 1.
There exists a unique NE if and only if the following condition is satisfied:
(8a)
or
(8b)
Proof.
The proof is given in Appendix .
Following the conditions in (8a) and (8b), we can easily characterize the sufficient conditions for the existence of a unique NE.
Corollary 2.
There exists a unique NE if .
If the conditions in (8a) and (8b) are fulfilled simultaneously, both transmitters would be transmitting at the same time. We denote this case as the concurrent transmission case. Next, we consider only this case since it is the fair case where both systems operate simultaneously. The other cases in which a unique NE exists correspond to one transmitter allocating maximum transmit power and the other not transmitting. The concurrent transmission case satisfies , which is the sufficient condition for the existence of a unique NE given in Corollary 2.
In the concurrent transmission case, the transmitters operate in the unique NE which is a fixed point of the best response function. In order to reach the NE, the best response dynamics must globally converge.
Proposition 3.
The best response dynamics globally converge to the NE in the concurrent transmission case, that is, when (8a) and (8b) hold simultaneously.
Proof.
The proof is given in Appendix .
In comparison to the IFC without pricing, the sufficient conditions for global convergence of the best response dynamics are identical. The reason for that is, however, not obvious. The linear pricing in our utility function leads to a translation of the best response function but as well changes the interference conditions where concurrent transmission takes place. This is seen in the conditions in (8a) and (8b) where the bounds depend on the prices. Therefore, proving the sufficient conditions for global convergence of the best response dynamics is necessary in our case.
3.3. Admissible Power Prices
Given , and , there exists a set of pricing pairs that achieves the concurrent transmission case described above. We define the admissible power pricing set , which directly follows from the simultaneous fulfillment of conditions (8a) and (8b),
(9)
All prices achieve NEs in the concurrent transmission case. In the case that , the set is, however, empty, that is, there exists no power prices that achieve the concurrent transmission case. This happens since the upper bound on would be less than the lower bound for any , that is, . Another observation is that the set is convex only in the case if and both hold. This corresponds to the weak interference case. In the case if one CCC is larger than one, but still the condition holds, the set is not convex.
The unique NE in the concurrent transmission case as a function of the power prices is calculated as
(10a)
(10b)
where and . Note that the can be omitted because the concurrent transmission implies that the power allocation of both systems are nonzero.
From the arbitrator's point of view, all price tuples lead to stable operating points in terms of user strategies. By choosing different prices, the arbitrator can optimize a certain social welfare function. In the next section, we propose to minimize the total transmit power under utility requirements.
4. Energy-Efficient Assignment with Utility Requirements
In this section, we investigate how the power prices are chosen such that energy-efficiency as well as minimum utility requirements are satisfied.
4.1. Optimization Problem
The arbitrator decides on the power prices such that the outcome satisfies the following conditions.
(C1)The best response dynamics globally converge to the unique NE.
(C2)Spectrum sharing (concurrent transmission) is ensured so that it is fair for all users.
(C3)Users transmit at the lowest powers possible satisfying minimum utility requirement , to promote efficient energy usage.
If , conditions (C1) and (C2) are automatically fulfilled. Condition (C3) can be achieved by optimization. Hence, determining the optimal prices () is done by solving the following programming problem:
(11a)
(11b)
(11c)
The objective function is calculated as
(12)
The function in (12) is convex in only in the weak interference channel case, that is, , Similarly, the constraint set is also only convex in the weak interference channel case. Thus, the problem in (11a), (11b) and (11c) is in general not a convex optimization problem. However, a closed-form solution is possible, which will be shown in Section 4.3. Before that, we will investigate some interesting properties of the inverse power prices which will facilitate the proof of the solution.
4.2. Analysis in Inverse Price Space
In the following, we will substitute the power prices with their inverse to ease the analysis with regard to the power allocation and utility. The power allocation at NE is then written as
(13a)
(13b)
The sum power at NE is expressed as
(14)
The upper and lower bounds corresponding to and in (9) are
(15a)
(15b)
The admissable inverse power prices are contained in the region within the bounds, depicted as in Figure 2 which corresponds to in -space, defined as the following:
(16)
Note that the region has a simple shape since and are affine functions of . The regions where or are not of interest because they only yield zero powers. Equations (15a) and (15b) are linear functions of and can be generalized as
(17)
that represents a linear curve that has a slope (e.g., of the upper and lower bounds are and , resp.) which crosses the point at .
Figure 2
denotes the region of admissable inverse power priceswhereasdenotes the region where utility requirementsare fulfilled. The optimal inverse power prices is at the bottom tip of . See text for more explanation.
×
We will now look at an important property of the sum power in the -space. We substitute (17) into (14) and find its derivative to as
(18)
We see that by inserting any between and , (18) is always positive if . This implies the following. There is always an increase in as are increased along a line with slope that takes any value between and .
Definition 4 (Dominating vector by inclination ).
A vector is said to dominate a vector by an inclination of if is nonnegative and .
Corollary 5.
For a region where all dominate by an inclination of , where , . This also means that is the point with the least sum power for this region.
Next, we will consider the properties of the utility in the inverse power price space. By inserting (13) into the utility functions (2) and setting ,
(19)
where , is the Lambert-W function and . The Lambert function satisfies [25]. increases rapidly from towards zero as increases from zero. Thus, decreases towards a positive constant as increases. Analogously, by setting the following holds:
(20)
It is noteworthy that both equations here are again linear and have positive slopes, as illustrated in Figure 2. The region below the curve specified by (19) is where holds. Similarly, the region above the line defined by (20) is where holds. Thus, requiring both conditions yields the region , which is defined as the following:
(21)
Setting and in (19) and (20) would return the upper and the lower bounds as in (15a) and (15b), making . As ( resp.) is increased, the slope of the upper (lower) bound decreases (increases). The point of intersection of these two curves is where both utility requirements are fulfilled with equality, as indicated by in Figure 2. The region forms an open triangle which is found within . This implies that is a subset of ().
4.3. Solution
From the properties we have considered above, it is quite intuitive to conclude that the solution to problem (11a), (11b) and (11c) is the pair that corresponds to , where the utility requirements (11b) are fulfilled with equality.
Proposition 6.
The optimal power prices which solve programming problem (11a), (11b) and (11c) are given as
(22a)
(22b)
These expressions are found by calculating and when (19) equals (20) and then inverting them.
Proof.
The constraint (11b) is satisfied in . Furthermore, for (11c) to hold, must be a subset of . This is only fulfilled if the slopes of the upper and lower bounds of are within and . Otherwise, they would cross or , making contain regions outside . Because of this property, Corollary 5 holds. Therefore, for any and that yields a nonempty set , the intersection of (19) and (20) yields the inverse power prices with the least sum power in region , which correspond to .
4.4. Feasible Minimum Utility Requirements
We assume that the arbitrator supports reasonable requirements such that . Given minimum utility requirements, and , the arbitrator should be able to determine if this pair is feasible, that is, whether there exists a power pricing pair that leads to a unique NE that fulfills these requirements simultaneously. They are infeasible if all pricing pairs lead to either nonunique NE or a unique NE whose utility tuple does not fulfill the utility requirements.
Proposition 7.
A minimum utility requirement chosen under the conditions above is feasible if and only if the optimal power prices calculated in (22a) and (22b) are in the admissible power prices set given in (9), that is, .
Proof.
The proof is given in Appendix .
Therefore, according to Proposition 7, the arbitrator checks if in order to determine the feasibility of the minimum utility requirements.
In Section 6, we give numerical simulations on energy-efficiency comparing the noncooperative setting with pricing and that without pricing as well as the cooperative setting with pricing. Before that, we analyze the case with minimum rate requirements in the next section.
5. Energy-Efficient Assignment with Rate Requirements
In contrast to the previous section, we now investigate how the power prices are chosen such that energy-efficiency as well as minimum rate requirements are satisfied.
5.1. Optimization Problem
The arbitrator decides on the power prices such that the outcome satisfies the same conditions as in Section 4.1 with a modification in (C3), which we state as following.
(C3)Users transmit at the lowest powers possible satisfying minimum rate requirement .
As before, if , conditions (C1) and (C2) are automatically fulfilled. Condition (C3) can be achieved by solving the following programming problem:
(23a)
(23b)
(23c)
where is defined as in (12). Before we come to the solution, we present some analysis that will simplify its derivation.
5.2. Analysis and Feasibility
Unlike in the previous section, where both power allocation and prices have a direct influence on whether the utility requirements are fulfilled, only the power allocation has a direct influence on the fulfillment of the rate requirements. Therefore, we take a different approach by first determining the power allocation that fulfills the rate requirements and simultaneously minimizes the total power, and then calculate the optimal power prices that lead the users to this NE.
The relationship between the rate and the transmission power of every user in (1) can be expressed in matrix form as the following:
(24)
where . This can be formulated as
(25)
where is the identity matrix, ,
(26)
The power vector that yields the rates is
(27)
or explicitly expressed as
(28a)
(28b)
However, may be negative. For given rate requirements and channel coefficients, we can verify if there exists a feasible unique power vector (i.e., , , where the inequality is componentwise) that fulfills the rate requirements using the following proposition.
Proposition 8.
The rate vector is feasible if and only if .
Proof.
According to Theorem A.51 in [26], for any , there exists a unique vector if and only if . , which is the spectral radius, where are the eigenvalues of the matrix . is calculated as . This implies that the requirements are feasible if and only if .
Proposition 9.
The power allocation that minimizes with rate requirements is given by in (27), which fulfills the requirements with equality.
Proof.
The derivatives of to and are always positive, that is,
(29)
(30)
This implies that for any , .
Assuming that the powers are feasible and known, it is straight-forward to determine the prices that should lead the players to this NE. At NE, where each player chooses the strategy that maximizes its utility, the necessary condition is . This implies that
(31)
or explicitly,
(32a)
(32b)
However, these prices do not necessarily lead to a unique NE. We insert (31) into (9) to derive the condition such that . Since , is always valid whereas
(33)
(34)
is only valid if . Therefore, to ensure that both feasibility and the uniqueness of the NE are simultaneously fulfilled, has to be satisfied.
Suppose , for example, . There are some values of , for example, , which are feasible but there are no corresponding prices that lead the players to a unique NE that fulfills the requirements with equality. This scenario corresponds to strong interference [27]. Therefore, one solution could be to consider another decoding strategy which is more complex and leads to a different achievable rate expression, which has a different game model.
5.3. Solution
The prices that solve (23a), (23b) and (23c) are given by as in (32a) and (32b), provided that , which ensures the feasibility of the solution and the constraint (23c), guaranteeing the uniqueness of the NE. The corresponding NE strategy is , which fulfills (23b) with equality. Using Proposition 9, we can conclude that this power allocation also fulfills (23a).
6. Simulations and Discussions
Here, we present numerical simulations on energy-efficiency comparing the noncooperative setting with pricing and that without pricing as well as the cooperative setting with pricing with minimum utility requirements.
The Pareto boundaries for various pairs are plotted in Figure 3 for the noncooperative case with pricing. It shows the feasible utility regions, given , , , and the corresponding optimal power prices . This was done by first obtaining points in the utility region according to (2) by randomly varying the powers and , where and . The scattered points are then grouped into equally spaced bins in the axis. Using the points with the highest for every bin, the Pareto boundary is plotted. Changing only does not have any effect on the Pareto boundaries or the NE. Practically, the operating points along the Pareto boundary are achievable when the systems cooperate or by repeated game (Folk theorem) [28].
Figure 3
The Pareto boundaries for various () as shown in round brackets in the legend,anddB. The corresponding optimal prices as shown in square brackets. The NE and are in the identical position.
×
As expected, the NE in the utility region, which is calculated by inserting into (2), is found exactly at the utility requirements, independently of the CCC values . The NE is very close to the Pareto boundaries, indicating that it is indeed very close to being a Pareto-efficient operating point for various CCCs. By increasing simultaneously, the utility region is expanded in that the intersections at the and axes increase. The region is also observed to change from being convex to being nonconvex as the product becomes larger. The reason for this is that prices are reduced so that systems can reach the utility requirements at higher CCCs. Lower prices mean that the maximum utility of a system is higher, which is achieved when the other system pair does not transmit. In this case, cooperation among systems is more advantageous than noncooperation in achieving a higher sum utility. Note that for a nonconvex utility region, time-sharing between single-user operating points could be used to improve the utilities. This requires the knowledge of the time-sharing schedule at the transmitters and can be considered in future work.
With regard to the optimal prices, which is shown in the legend of Figure 3, we observe that the system with the smaller CCC has to pay less than the one with the larger. However, if both systems have large CCCs, both pay less. We regard this pricing scheme as fair. On the one hand, the system that causes more interference to the other is charged with a higher price; on the other hand, if both systems suffer from high interference from each other, both are encouraged to transmit more power by means of price reduction so that the utility requirements are met.
An appropriate metric for comparing energy-efficiency is defined as
(35)
where is the transmission rate, as in (1), of system and the corresponding power allocation. A similar function is used to measure energy-efficiency for ad hoc MIMO links in [29]. Figure 4 shows a comparison between energy-efficiency in the following settings.
(S1)The NE achieved with pricing.
(S2)The NE achieved without pricing. The power allocation is upper bounded by as in (6) for a fair comparison.
(S3)Both systems cooperatively choose their strategies to achieve the highest sum utility, that is, . The power allocation here is also upper bounded by for a fair comparison.
Figure 4
Comparison of energy-efficiencywith various CCCs. The noncooperative case with pricing (S1) is plotted with blue circles, the noncooperative case without pricing (S2) with green diamonds, and the cooperative case with pricing (S3) with red squares.
×
The operating point for the cooperative case was determined by numerically finding the power allocation that yields the highest sum utility. The reason for maximizing the sum utility instead of the energy-efficiency in (35) is that the former leads to zero transmit powers.
The systems are to cooperate to maximize energy-efficiency, the result is where both transmit powers are zero.
We see that in the noncooperative case, pricing improves the energy-efficiency significantly. The amount of improvement increases as the CCCs increase. The results with cooperation prove to be superior when the CCCs are large, whereas for low CCCs, noncooperation with pricing yields better energy-efficiency. One might expect the outcome of cooperation to be always superior to that of noncooperation. This is not true here because in the case of cooperation, the sum utility is maximized instead of . In our scenario, systems are only interested in maximizing their sum utility but not energy-efficiency when cooperating.
7. Conclusions
In this work, we consider two communication system pairs that operate in a distributed manner in the same spectral band. In order to improve the system energy-efficiency, we employ linear pricing to the utility of the systems. Following that, we study the setting from a noncooperative game-theoretic perspective, that is, we analyze the existence and uniqueness of the Nash equilibrium. Based on the assumption that there exists an arbitrator that chooses the power prices, we considered the problem of minimizing the sum transmit power with the constraint of satisfying minimum utility requirements and minimum rate requirements, respectively. We derived analytical solutions for the optimal power prices that solve these problems. Simulation results show that the noncooperative operating points with pricing are always more energy-efficient than those without pricing. A further extension of this work is to consider the case with more than two users. This is much more involved because there is no closed-form characterization of the prices that induce a globally stable NE. However, sufficient conditions for a unique NE can be used to define the set for users. For this case, similar programming problems as in (11a), (11b) and (11c) and (23a), (23b) and (23c) should be solved.
Appendcies
A. Proof of Proposition 1
The analysis for the uniqueness of the NE in a game can be done by studying the reaction curves of the players. Here, we give a simple and geometric derivation.
The reaction curve of a player is a function that relates the strategy of player , , to the best response of player in case the best response is a singleton [30]. The best response of player 1 and analogously player 2 is given in (5) from which the reaction curve for player 1 can be written as
(A1)
where represents the Euclidean projection of on the interval . These bounds are required because the strategy space of a player is constrained to . The reaction curve is similarly calculated for the second player as
(A2)
where . An intersection point of the reaction curves, and , consists of mutual best responses which would be a NE strategy profile. Hence, the number of intersections of the curves is the number of NEs in the game. Next, we define an unbounded reaction curve by removing the bound in (A.1) and (A.2):
(A3)
(A4)
These curves can aid us in the analysis of the number of intersection points of the bounded reaction curves and thus the number of NEs. To do this we would study the position of the intersection points of the unbounded reaction curves with the axes. Each unbounded reaction curve intersects the axes in two points. One point corresponds to and , . The other point corresponds to and defined as
(A5)
where . These points are illustrated in Figure 5. Utilizing these points, we can characterize geometrically the number of NEs in studying the position of with respect to , . In Table 1, all possible positions of the intersection points are listed with the corresponding number of NEs.
Table 1
Conditions for the number of NEs.
Case
Condition
Number of NEs
()
Unique NE
()
Unique NE
()
Unique NE
()
2 NEs
()
2 NEs
()
3 NEs
()
Infinitely many NEs
Figure 5
Illustration of the arrangement of the reaction curves. The solid blue line is given in (A.1) and the double solid red line is given in (A.2). The dashed lines are the corresponding unbounded reaction curves. According to Table 1, (a) corresponds to case . (b) corresponds to case and analogously to case . (c) corresponds to case and analogously to case . (d) corresponds to case . Case occurs when the curves overlap.
×
The arrangement of the reaction curves that resemble the cases in Table 1, are illustrated in Figure 5. Accordingly, the condition that fulfills cases one till three in Table 1 is the one given in (8a) and (8b). In Figure 6, an illustration shows the number on NEs that exist in dependence on the CCCs. The region below the dashed line designates where a unique NE always exists. Moreover, the case of interest in this paper is marked as "concurrent transmission" which lies below this dashed line.
Figure 6
Illustration of the number of NEs in different interference regions.
×
B. Proof of Proposition 3
In the case of concurrent transmission which is achieved for the conditions that (8a) and (8b) hold simultaneously, each bounded reaction curve in this case is a linear function and is not piece-wise linear as in the other cases. Therefore, we can write the best response of player as
(B1)
and for player 2 as
(B2)
This can be written as a system of linear equations in the form
(B3)
and then transformed to an algorithm [31, Section ]
(B4)
where is the outcome at the th iteration and is the identity matrix. The algorithm is globally convergent if the spectral radius of is less than one [31, Proposition ]. The condition, , satisfies this requirement. Since the concurrent transmission case satisfies , the best response dynamics are then globally convergent.
C. Proof of Proposition 7
We first define as the NE utility region which is achievable for all
(C1)
where denotes , which is the utility tuple at the unique NE corresponding to . All points in achieve concurrent transmission. That is, for as explained above in Section 3.3. As we see, any is feasible by definition.
From Proposition 1, we see that the only region that leads to a unique NE with concurrent transmission is when conditions (8a) and (8b) are satisfied, provided that . Since is the equivalent formulation of the price region where these conditions are satisfied, any would either lead to nonunique NE or to a unique NE without concurrent transmission. The tuple that leads to a unique NE without concurrent transmission never satisfies the utility requirements because for any is never chosen as a requirement. Therefore, any will lead to infeasible utilities.
Hence, any price tuple leads to feasible utilities at NE since all tuples map to , and any leads to infeasible utilities.
Acknowledgments
The authors thank Prof. Jens Zander for fruitful discussions. This work is supported in part by the Deutsche Forschungsgemeinschaft (DFG) under Grant Jo 801/4-1 and by the German Federal State of Saxony in the excellence cluster Cool Silicon in the framework of the project Cool Cellular under Grant no. 14056/2367. Part of this work [32] has been presented at the 5th International Conference on Cognitive Radio Oriented Wireless Networks and Communications (CrownCom) 2010.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
intends to transmit its signal to its corresponding receiver
,
(Figure 1). On simultaneous transmission, each receiver obtains a superposition of the signals transmitted from both transmitters. Assuming single-user decoding, the interfering signal is treated as additive noise. This system model can be extended to multiple system pairs. For convenience, we focus our analysis on two pairs.
to
are denoted as
. The noise at the receivers is independent additive white Gaussian with variance
. The inverse noise power is denoted by
, that is,
. The transmitters and receivers are assumed to have perfect channel state information (CSI). The maximum achievable rate at receiver
, analogously
, is written as
,
, is the transmit power of
. We assume no power constraint on the transmitters, that is,
. It is shown later that the maximum power that would be utilized is nevertheless bounded due to a pricing factor.
,
, is the transmission power
. The corresponding payoff is expressed in the utility function
is given in (1) and
is the power price for player
. The second term in (2) is a pricing term, which linearly reduces the utility. This means that a payment is demanded from the player for the amount of power used. Without pricing, each user would use as much power as possible to transmit his signal [21]. The game is written as
in which no player can unilaterally increase his payoff by deviating from his NE strategy, that is, for player 1,
, of a player
is the strategy or set of strategies that maximize his utility function for a given strategy of the other player. Since the player's utility function is concave in his own strategy, the best response is unique and given as the solution of the first derivative being zero. The best response for player 1 is written as
denotes
. The highest power a transmitter
may allocate is given as
. Thus, the strategy region of player
could be confined to
.
and
. It receives either utility or rate demands from the users and checks if they are feasible. If they are, it calculates the prices and informs the system pairs about the prices imposed on them. The links will have to pay costs proportional to their transmit power, that is,
and
(Figure 1). In game-theoretic notation, this entity is called the arbitrator [22]. The arbitrator is not a player in the game and chooses the equilibrium that meets certain criteria. In our case, these criteria would be fairness, energy-efficiency, and minimum utility requirements or minimum rate requirements. We assume that the arbitrator also has complete game information.
is
. The second condition is satisfied for the following reasons. First, it is obvious that the utility functions are continuous in the players' strategies. Second, knowing that all concave functions are quasi-concave functions [24], we can prove the concavity of our utility function with respect to the corresponding player's strategy by showing that
.
, which is the sufficient condition for the existence of a unique NE given in Corollary 2.
, and
, there exists a set of pricing pairs that achieves the concurrent transmission case described above. We define the admissible power pricing set
, which directly follows from the simultaneous fulfillment of conditions (8a) and (8b),
achieve NEs in the concurrent transmission case. In the case that
, the set
is, however, empty, that is, there exists no power prices that achieve the concurrent transmission case. This happens since the upper bound on
would be less than the lower bound for any
, that is,
. Another observation is that the set
is convex only in the case if
and
both hold. This corresponds to the weak interference case. In the case if one CCC is larger than one, but still the condition
holds, the set
is not convex.
and
. Note that the
can be omitted because the concurrent transmission implies that the power allocation of both systems are nonzero.
lead to stable operating points in terms of user strategies. By choosing different prices, the arbitrator can optimize a certain social welfare function. In the next section, we propose to minimize the total transmit power under utility requirements.
such that the outcome satisfies the following conditions.
, to promote efficient energy usage.
, conditions (C1) and (C2) are automatically fulfilled. Condition (C3) can be achieved by optimization. Hence, determining the optimal prices (
) is done by solving the following programming problem:
only in the weak interference channel case, that is,
,
Similarly, the constraint set
is also only convex in the weak interference channel case. Thus, the problem in (11a), (11b) and (11c) is in general not a convex optimization problem. However, a closed-form solution is possible, which will be shown in Section 4.3. Before that, we will investigate some interesting properties of the inverse power prices which will facilitate the proof of the solution.
to ease the analysis with regard to the power allocation and utility. The power allocation at NE is then written as
and
in (9) are
in Figure 2 which corresponds to
in
-space, defined as the following:
region has a simple shape since
and
are affine functions of
. The regions where
or
are not of interest because they only yield zero powers. Equations (15a) and (15b) are linear functions of
and can be generalized as
(e.g.,
of the upper and lower bounds are
and
, resp.) which crosses the point at
.
denotes the region of admissable inverse power prices
whereas
denotes the region where utility requirements
are fulfilled. The optimal inverse power prices
is at the bottom tip of
. See text for more explanation.
in the
-space. We substitute (17) into (14) and find its derivative to
as
between
and
, (18) is always positive if
. This implies the following. There is always an increase in
as
are increased along a line with slope
that takes any value between
and
.
).
is said to dominate a vector
by an inclination of
if
is nonnegative and
.
dominate
by an inclination of
, where
,
. This also means that
is the point with the least sum power for this region.
,
,
is the Lambert-W function and
. The Lambert
function satisfies
[25].
increases rapidly from
towards zero as
increases from zero. Thus,
decreases towards a positive constant as
increases. Analogously, by setting
the following holds:
holds. Similarly, the region above the line defined by (20) is where
holds. Thus, requiring both conditions yields the region
, which is defined as the following:
and
in (19) and (20) would return the upper and the lower bounds as in (15a) and (15b), making
. As
(
resp.) is increased, the slope of the upper (lower) bound decreases (increases). The point of intersection of these two curves is where both utility requirements are fulfilled with equality, as indicated by
in Figure 2. The region
forms an open triangle which is found within
. This implies that
is a subset of
(
).
pair that corresponds to
, where the utility requirements (11b) are fulfilled with equality.
which solve programming problem (11a), (11b) and (11c) are given as
and
when (19) equals (20) and then inverting them.
. Furthermore, for (11c) to hold,
must be a subset of
. This is only fulfilled if the slopes of the upper and lower bounds of
are within
and
. Otherwise, they would cross
or
, making
contain regions outside
. Because of this property, Corollary 5 holds. Therefore, for any
and
that yields a nonempty set
, the intersection of (19) and (20) yields the inverse power prices with the least sum power in region
, which correspond to
.
. Given minimum utility requirements,
and
, the arbitrator should be able to determine if this pair is feasible, that is, whether there exists a power pricing pair
that leads to a unique NE that fulfills these requirements simultaneously. They are infeasible if all pricing pairs lead to either nonunique NE or a unique NE whose utility tuple does not fulfill the utility requirements.
chosen under the conditions above is feasible if and only if the optimal power prices
calculated in (22a) and (22b) are in the admissible power prices set
given in (9), that is,
.
in order to determine the feasibility of the minimum utility requirements.
such that the outcome satisfies the same conditions as in Section 4.1 with a modification in (C3), which we state as following.
.
, conditions (C1) and (C2) are automatically fulfilled. Condition (C3) can be achieved by solving the following programming problem:
is defined as in (12). Before we come to the solution, we present some analysis that will simplify its derivation.
that lead the users to this NE.
. This can be formulated as
is the identity matrix,
,
is
may be negative. For given rate requirements and channel coefficients, we can verify if there exists a feasible unique power vector (i.e.,
,
, where the inequality is componentwise) that fulfills the rate requirements using the following proposition.
is feasible if and only if
.
, there exists a unique vector
if and only if
.
, which is the spectral radius, where
are the eigenvalues of the matrix
.
is calculated as
. This implies that the requirements
are feasible if and only if
.
with rate requirements
is given by
in (27), which fulfills the requirements with equality.
to
and
are always positive, that is,
,
.
are feasible and known, it is straight-forward to determine the prices that should lead the players to this NE. At NE, where each player chooses the strategy that maximizes its utility, the necessary condition is
. This implies that
. Since
,
is always valid whereas
. Therefore, to ensure that both feasibility and the uniqueness of the NE are simultaneously fulfilled,
has to be satisfied.
, for example,
. There are some values of
, for example,
, which are feasible but there are no corresponding prices that lead the players to a unique NE that fulfills the requirements with equality. This scenario corresponds to strong interference [27]. Therefore, one solution could be to consider another decoding strategy which is more complex and leads to a different achievable rate expression, which has a different game model.
as in (32a) and (32b), provided that
, which ensures the feasibility of the solution and the constraint (23c), guaranteeing the uniqueness of the NE. The corresponding NE strategy is
, which fulfills (23b) with equality. Using Proposition 9, we can conclude that this power allocation also fulfills (23a).
pairs are plotted in Figure 3 for the noncooperative case with pricing. It shows the feasible utility regions, given
,
,
, and the corresponding optimal power prices
. This was done by first obtaining points in the utility region
according to (2) by randomly varying the powers
and
, where
and
. The scattered points are then grouped into equally spaced bins in the
axis. Using the points with the highest
for every bin, the Pareto boundary is plotted. Changing only
does not have any effect on the Pareto boundaries or the NE. Practically, the operating points along the Pareto boundary are achievable when the systems cooperate or by repeated game (Folk theorem) [28].
) as shown in round brackets in the legend,
and
dB. The corresponding optimal prices as shown in square brackets. The NE and
are in the identical position.
into (2), is found exactly at the utility requirements, independently of the CCC values
. The NE is very close to the Pareto boundaries, indicating that it is indeed very close to being a Pareto-efficient operating point for various CCCs. By increasing
simultaneously, the utility region is expanded in that the intersections at the
and
axes increase. The region is also observed to change from being convex to being nonconvex as the product
becomes larger. The reason for this is that prices are reduced so that systems can reach the utility requirements at higher CCCs. Lower prices mean that the maximum utility of a system is higher, which is achieved when the other system pair does not transmit. In this case, cooperation among systems is more advantageous than noncooperation in achieving a higher sum utility. Note that for a nonconvex utility region, time-sharing between single-user operating points could be used to improve the utilities. This requires the knowledge of the time-sharing schedule at the transmitters and can be considered in future work.
is the transmission rate, as in (1), of system
and
the corresponding power allocation. A similar function is used to measure energy-efficiency for ad hoc MIMO links in [29]. Figure 4 shows a comparison between energy-efficiency in the following settings.
as in (6) for a fair comparison.
. The power allocation here is also upper bounded by
for a fair comparison.
with various CCCs. The noncooperative case with pricing (S1) is plotted with blue circles, the noncooperative case without pricing (S2) with green diamonds, and the cooperative case with pricing (S3) with red squares.
. In our scenario, systems are only interested in maximizing their sum utility but not energy-efficiency when cooperating.
for
users. For this case, similar programming problems as in (11a), (11b) and (11c) and (23a), (23b) and (23c) should be solved.
of a player
is a function that relates the strategy of player
,
, to the best response of player
in case the best response is a singleton [30]. The best response of player 1 and analogously player 2 is given in (5) from which the reaction curve for player 1 can be written as
represents the Euclidean projection of
on the interval
. These bounds are required because the strategy space of a player is constrained to
. The reaction curve
is similarly calculated for the second player as
. An intersection point of the reaction curves,
and
, consists of mutual best responses which would be a NE strategy profile. Hence, the number of intersections of the curves is the number of NEs in the game. Next, we define an unbounded reaction curve by removing the bound in (A.1) and (A.2):
and
,
. The other point corresponds to
and
defined as
. These points are illustrated in Figure 5. Utilizing these points, we can characterize geometrically the number of NEs in studying the position of
with respect to
,
. In Table 1, all possible positions of the intersection points are listed with the corresponding number of NEs. 
)
)
)
)
)
)
)
given in (A.1) and the double solid red line is
given in (A.2). The dashed lines are the corresponding unbounded reaction curves. According to Table 1, (a) corresponds to case
. (b) corresponds to case
and analogously to case
. (c) corresponds to case
and analogously to case
. (d) corresponds to case
. Case
occurs when the curves overlap.
as
is the outcome at the
th iteration and
is the identity matrix. The algorithm is globally convergent if the spectral radius of
is less than one [31, Proposition
]. The condition,
, satisfies this requirement. Since the concurrent transmission case satisfies
, the best response dynamics are then globally convergent.
as the NE utility region which is achievable for all
denotes
, which is the utility tuple at the unique NE corresponding to
. All points in
achieve concurrent transmission. That is,
for
as explained above in Section 3.3. As we see, any
is feasible by definition.
. Since
is the equivalent formulation of the price region where these conditions are satisfied, any
would either lead to nonunique NE or to a unique NE without concurrent transmission. The tuple that leads to a unique NE without concurrent transmission never satisfies the utility requirements because
for any
is never chosen as a requirement. Therefore, any
will lead to infeasible utilities.
leads to feasible utilities at NE
since all tuples
map to
, and any
leads to infeasible utilities.