{'fraction_non_alphanumeric': 0.03864780628146727, 'fraction_numerical': 0.006281467274035004, 'mean_word_length': 4.034033309196235, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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}}
Market-Based Power Allocation for a Differentially Priced FDMA System

In this paper, we study the problem of differential pricing and QoS assignment by a broadband data provider. In our model, the broadband data provider decides on the power allocated to an end-user not only based on parameters of the transmission medium, but also based on the price the user is willing to pay. In addition, end-users bid the price that they are willing to pay to the BTS based on their channel condition, the throughput they require, and their belief about other users' parameters. We will characterize the optimum power allocation by the BTS which turns out to be a modification of the solution to the well-known water-filling problem. We also characterize the optimum bidding strategy of end-users using the belief of each user about the cell condition.


I. INTRODUCTION
The exponential growth of the demand for broadband data in recent years and the high cost of network expansion led broadband data providers to revise their policies and prices imposed on content providers and end-users. An evidence of such trend is the increasing incentive of broadband data providers to change their flat-rate pricing scheme with a more complex one to control the congestion on the network and to increase their profit [1].
In this paper, we study the problem of differential pricing and QoS assignment by a broadband data provider. In our model, the broadband provider decides on the resources allocated to an end-user, and subsequently the QoS seen by that user, not only based on parameters of the transmission medium, but also based on the price the user is willing to pay. An FDMA system with a single Base Transceiver Station (BTS) is considered. The BTS has a limited downlink power budget, and is willing to allocate the available power such that to maximize the gross profit. An end-user bids the price that she is willing to pay to the BTS based on her own channel condition, the throughput she require, and her belief about other users' parameters. Subsequently, the BTS decides on the amount of power she allocates to end-users based on the price they bid, their channel quality, and the throughput needed by users.
Although the bidding scheme is not convenient to use by an end-user in everyday data usage, this scheme can be used by users with a bad channel quality and high valuation for data to increase their throughput through appropriately adjusting their price. In addition, this gives an end-user with a good channel quality the ability to use data for a cheaper price. Another application in which this scheme can be used is primary/secondary markets [3].
In this paper, we will characterize the optimum power allocation by the BTS. We will show that the solution to this problem is a modification of the solution to the well-known water-filling [4] problem. We also characterize the optimum bidding strategy of end-users using the belief of each user about the cell condition. Furthermore, we will investigate the relation between the communication parameters of a user and the price she pays and subsequently the allocated power to her through simulations. The social welfare of end-users is also compared in two cases: (i) the mentioned differential QoS and pricing scheme and (ii) the flat-rate pricing scheme.
The problem of resource allocation through pricing in wired and wireless networks has received a lot of attention [5] - [9]. In most of the works about pricing-based power control in wireless networks, such as [5]- [7], the problem of power control in uplink of a cellular network is considered. However, [8] and [9] investigated the problem of downlink power allocation in a CDMA system. The closest work to ours is [9]. In [9], authors investigated a bidding scheme in which users bid for a time-frame, and the BTS allocates the time-frame based on prices and channel qualities. Authors focused on the macro-level view of the interaction between the BTS and endusers, and do not involve wireless intricacies in the model. The decisions of users are considered to be made independent of each other and based on a demand function. They mainly focus on the optimal allocation and revenue given the price vector, and do not characterize the optimum bidding strategies of users. By characterizing the demand function, we capture the nature of end-user's optimization, and characterize both the optimum allocation and bidding strategies.
Another distinction of our work with previous works is to consider more strategic users that only pay for the amount of data that they need. In other words, users have a desired throughput that needs to be met, and they only pay for the data up to their desired throughput and not more.
The paper is organized as follows. In Section II, we describe the model and formulate a two stage optimization problem. In Section III, we solve the optimization problems and characterize the optimum power allocation and bidding strategies.
Simulation results are presented in Section IV. We conclude the paper, and present future works in Section V.

II. SYSTEM MODEL AND PROBLEM FORMULATION
We consider an FDMA system with parallel broadcast Gaussian channels in a single cell with one Base Transceiver Station (BTS). The base station has a down-link power budget of Φ. Without loss of generality, the total power budget is assumed to be one unit, i.e. Φ = 1, otherwise, simply normalize all power quantities, including noise, by Φ. Consider a group of n ≥ 2 mobile end-users indexed by i. The channel attenuation to the user i is denoted by h i , and each user i has a desired throughput of b i bits/s. In order to have a non-trivial problem, suppose that the BTS is overloaded with the demand, i.e., the power budget is not sufficient to satisfy the demand of all end-users.
Users bid a price, c i , that they are willing to pay for one unit of data to the BTS. Subsequently, the BTS decides on the fraction of power she will assign to the user i depending on the price this user bids (c i ), the channel quality, and the desired throughput (b i ). Thus, we formulate the problem as a two-stage optimization problem: (1) In the first stage, the end-user i decides to bid a price c i per bit of data to maximize her expected utility function: where v i > 0 is the valuation of the end-user i for one bit of data, and T i (c i , c −i ) is the expected throughput of i when she bids the price c i per bit and other users bid the vector of price c −i . By Shannon formula, where q := hi Ni is the channel quality. Note that in the Shannon formula, without loss of generality, the bandwidth is taken to be 1. Furthermore, in (2), SN R i is the signal to noise ratio of the user i. In addition, N i and P * i are the power of noise for i and the expected dedicated downlink power of the BTS to the end-user i, respectively.
Note that we assumed that each end-user is assigned a distinct frequency channel and the interference between channels are assumed to be negligible. In addition, P i is dependent on the price a user bids and is determined by the BTS in the second stage of the optimization problem.
In this paper, we assume that an end-user is aware of her own channel quality and throughput she needs, and holds a belief over other users' parameters.
(2) In the second stage, the BTS decides on the optimum power allocation knowing the channel quality of end-users, throughput they need, and the price they bid. The goal of the BTS is to maximize her revenue. The revenue of the BTS depends on the price a user pays per bit, c i , times the number of bits of data she uses. Thus, the revenue of the BTS is i c i log 2 (1 + SN R i ). This expression should be maximize by the BTS given the prices that end-users bid in the previous stage and the channel quality of users. Therefore, the following optimization problem is solved by the BTS: The constraint (4) reflects the desired throughput of a user. Thus, in the optimum allocation, the BTS provides at most b i bits for i. The constraint (6) resulted from the power budget of the BTS and the assumption that the system is overloaded.
In the next section, we characterize the optimum power allocation strategy for the base station and the optimum bidding strategy for end-users.

III. OPTIMUM ALLOCATION AND BIDDING STRATEGIES
We proceed to solve the problem in a reverse order. First we start with the BTS problem (Section III-A) for allocating the power. Then we characterize the optimum bidding strategies for end-users using the optimum allocation strategy obtained by solving the BTS problem (Section III-B).

A. BTS Problem
The optimization problem (3)-(6) is a modified version of the conventional water-filling problem. In the conventional water-filling the objective function is merely the sum of throughputs, while in (3) the objective function is the weighted sum of the throughput of end-users in which the weights are the price per bit that a user is willing to pay. In addition, (4) is an extra constraint to ensure that the allocated throughput to a user does not exceed the demand of that user. We will prove that the solution to this optimization problem is also a modified version of the conventional solution to the waterfilling problem.
Similar to the water-filling problem, the BTS problem is a convex programming problem. Thus KKT conditions provides the necessary and sufficient conditions for an optimal solution, i.e. P * . The stationarity condition in KKT is as follows: where γ i , λ i , and η are Lagrange multipliers associated with (4), (5), and (6), respectively. λ * i works similar to a slack variable. Thus On the other hand, if which is dependent on dual parameters η * and γ * i . Thus, Theorem III.1. The solution to the minimization problem is slightly different from water-filling, in the sense that the flood level ( ci η * ) is different for each user, and is dependent on c i , i.e. the price the user pays.
Either the end-user i receives the desired throughput, i.e., In the latter case, γ * i = 0, and the throughput of the user i is . Thus in this case, the throughput is Therefore the throughput of the end-user is a non-decreasing function of c i and q i : Discussion: There exists a saturation level for each user. In the saturation level, log 2 (1 + q i P * i ) = b i . In other words, the saturated level of the allocated power occurs when the desired throughput is met.
Note that the dual parameter η * (7) depends on all players' prices (including i) and their channel quality. This parameter is important in determining the flood level. Intuitively from (6) and (8), we can say that a higher η * is associated with a more congested cell, users that are willing to pay more for data, or lower quality of channels 1 . From this point on, we call η * the cell condition. In section III-B, we will observe that the belief of end-users about this parameter is important in their decision making about the price they bid.

B. End-User Problem
Now, consider the bidding problem for end-users. We will characterize the optimum solution(s) for the problem.
In our setting, users want to bid a price to maximize their utility function which is a decreasing function of the price they bid and an increasing function of their expected throughput: )}} (9) In (9), log 2 (q i ci ηi(ci) ) is the expected throughput resulted from the optimum power allocation done by the BTS in the previous section, and η i (c i ) is the belief of player i about the η * in (7). Note that users do not know the actual value of η * , and the belief of a user about the cell condition is dependent on the price paid by that user. We will later discuss more about the belief function.
Bidding the price c i = 0 yields a throughput of zero. Therefore the optimization is on prices greater than zero, and the price that agent i chooses is in the set (0,c i ], wherē c i = inf{c i : log 2 (q i ci ηi(ci) ) = b i }. This happens because . Therefore, player i does not choose a price higher thanc i . In other words,c i is the smallest price by which a user can expect to receive the full throughput she needs. In addition, by choosing c i = v i , a user can secure the payoff of zero. Thus, the optimum price should be in the interval of (0, min{c i , v i }]. We call the interval (0, min{c i , v i }] the feasible price interval. Now, consider the maximization (9) on the feasible interval: The optimum bidding strategy is found by using the first order optimality condition: Let A i denotes the set of solutions to the equation (11). The set of candidate optimum solutions, A * i , is the set of prices that are in the interval (0, min{c i , v i }] and satisfy the second order condition: The optimum bidding price is: we will explain more about the belief function and provide a sample belief function for the end-users.
The Belief Function: The belief function of a user is an important factor in determining the optimum bid by that user. One method by which end-users can obtain this belief function is to guess and update their belief for the cell condition by monitoring the price bid by users and channel qualities of different users for a particular interval of time. This update process is beyond the scope of this paper.
As an another method, the belief function for the cell condition can be provided for end-users by the BTS at the beginning of a time-slot. Note that the BTS is aware of all channel qualities, but is not aware of the bids submitted by users before announcing the belief function. Thus, the BTS can only announce an approximation of η * as the belief function to end-users.
An end-user expects that her belief function be a nondecreasing function of the price she bids. The reason is considered in the following discussion: Discussion: Given the belief finction, η i (c i ), and from (6) is not a strictly increasing function of c i . Therefore, η ′ * ≥ η ′′ * , and P ′belief In other words, the belief of the user about her power quota is increased. In addition the power quota of other users is unchanged or increased, i.e. P ′belief j ≤ P ′′belief j for j = i. Thus j P ′′belief j > 1, which is inconsistent with the belief of a user about the optimization done in the BTS side.
Note that the belief function is determined by the history or is provided by the BTS and potentially can be any function. However, as discussed above, a non-decreasing function is more consistent. Now consider the consistent belief explained above: the belief function which is non-decreasing with respect to c i , and is increasing if the user believes that she will receive a positive power quota and the demand of the user is not met, i.e when 0 < log 2 (1 + q i ( ci ηi(ci) − 1 qi )) < b i . In the following theorem, we present the relation between the price a user bids and her belief about the power quota she gets, when users are provided with a consistent belief.
Theorem III.2. When users are provided with a consistent belief, the belief of a user about the power allocated to her is a non-decreasing function of the price she bids for prices in the feasible interval, and it is an increasing function of the price she bids when the user believes that she will receive a positive power quota and the demand of the user is not met.
Proof: If ( ci ηi(ci) − 1 qi ) + = 0, the result follows from (5). The theorem holds by vacuity if log 2 (1 + q i ci ηi(ci) − 1 qi ) = b i . Now consider the case that 0 < log 2 (1 + q i ( ci ηi(ci) − 1 qi )) < b i . Suppose that P belief i = ci ηi(ci) − 1 qi is not increasing with respect to c i . The demand is consistent, therefore η i (c i ) is increasing function of c i . Thus, P belief j for j = i decreases as c i increases. Therefore k P belief k decreases from one. This is a contradiction with (6). The result follows.
Next, we will present an example for the belief of end-users about the cell condition and characterize the optimum bidding strategy for this belief.
Example III.1. Simple Belief-Let the set Q i denotes the set of users that end-user i believes that they receive a positive throughput. Note that in this simple belief function, Q i is assumed by i to be independent of c i . In general, Q i would be a decreasing set with respect to c i . We introduce parameters C i = j∈Qiĉ ij and B i = j∈Qi 1 qij , whereĉ ij andq ij are the belief of user i about other user's price and channel quality. Using (6), for all i, Therefore the belief function of the user i is: With this belief function, d 2 Ui(ci) dc 2 i < 0 for all feasible c i . This implies that (11) has at most one solution in the feasible interval. The solution to the equation (11) is the unique optimum bidding strategy for end-user i if it is in the interval (0, min{c i , v i }); otherwise, user i bids min{c i , v i }.
A possible implementation scheme for this type of belief function is that the BTS announces C i and B i at the beginning of each time-slot to the end-user i. Subsequently users use these value to calculate their bids.
In the next section, we present some numerical results using the simple belief function for the cell condition.

IV. NUMERICAL RESULTS
First we consider a cell consists of a BTS and four endusers. We assume that the BTS announces parameters C i and B i to each user i. For more accuracy of the belief function, assume that BTS is aware of q i 's and v i 's and determine C i and B i as follows: The goal of the first set of simulation is to observe the relationship between parameters of a user, i.e. b i , q i , and v i , with the price she bids and the power allocated to her. We consider three cases. In each case, one of the previously mentioned parameters are different among users and others are the same. Note that we normalized the bandwidth and the power budget to one; therefore all other parameters should be scaled appropriately.
Case 1: In this case, v i = 1 and q i = 2 for all end-users. The vector of the desired throughputs is b = [0.1, 0.5, 1, 2]. The price vector bid by users can be found to be c = [0.33, 0.46, 0.53, 0.53] which is non-decreasing with respect to the throughput needed by a user. The allocated power (red part), the reverse of channel quality (blue part), and ci η * (sum of the blue and red parts) are plotted in Figure 1.a. Simulation confirms that since all users have the same quality of channel, higher price bid by a user is associated with more power allocated to that user, and consequently a higher throughput. Thus, users with higher level of desired throughout, bid higher prices to secure higher throughputs.  .55] which is increasing with respect to the valuation each user has for data. As we can see in Figure 1.c, since users with higher valuation for data bid more generously, they obtain a higher fraction of the BTS power budget. Now, we want to investigate the effect of this differential QoS scheme on the social welfare of the cell. We consider a cell with one BTS and 10 end-users. The belief function is as before. The valuation of users for data is distributed uniformly in the interval [0, R], and the simulation is done for R = [0.5, 1, 1.5, 2, 2.5, 3]. We consider b i = 1.5 and q i = 2 for all users. To alleviate the effect of randomness in results, simulation is repeated 50 times for each value of R. The reported social welfare is the average of social welfare values resulted in these 50 iterations.
Here, the social welfare is defined as the sum of the payoffs of all end-users: Two cases are investigated: (i) Differential pricing and QoS scenario. In this case, c i is the the optimum bidding price chosen by the end-user i. (ii) Ordinary Water-Filling Scheme in which the BTS allocates her power merely based on the channel quality of users and charges all users a flat rate of c.
For the sake of comparison, we consider c to be the average price chosen by users in scenario (i).
Results are plotted in figure 2. The social welfare in the differential QoS scenario is larger than the social welfare in ordinary water-filling. Furthermore, the difference between the social welfare of two cases is increasing with the range of user's valuation for data.

V. CONCLUSION AND FUTURE WORKS
We studied the problem of power allocation in the downlink of an FDMA system by a BTS that decides on the allocation based on the price users bid, their desired throughput, and their channel qualities. The optimum power allocation and bidding strategies were characterized.
In the future, we will extend our results to the CDMA-SINR frameworks (where the bandwidth is fully shared). This scenario have a similar form of throughput function to that of the SNR-FDMA framework we have studied. For the CDMA case under overload conditions ( i P i = 1), T i ( c) = log 2 (1 + SINR i ) = − log 2 (1 −q i P i ) whereq i = h i /(h i + N i ) = q i /(1 + q i ), which is increasing in i's channel quality, q i .