SHUQIN LI and JIANWEI HUANG
Pricing is important for the design, operation, and management of communication networks. Pricing has been used with two different meanings in the area of communication networks. One is the “optimization-oriented” pricing for network resource allocation: it is made popular by Kelly's seminal work on network congestion control [2, 3]. For example, the Transmission Control Protocol (TCP) has been successfully reverse engineered as a congestion-pricing-based solution to a network optimization problem [4, 5]. A more general framework of network utility maximization (NUM) was subsequently developed to forward-engineer many new network protocols (see a recent survey in Reference [6]). In various NUM formulations, the “optimization-oriented” prices often represent the Lagrangian multipliers of various resource constraints and are used to coordinate different network entities to achieve the maximum system performance in a distributed manner. The other is the “economics-based” pricing, which is used by a network service provider to various objectives including revenue maximization. The proper design of such a pricing becomes particularly challenging today because of the exponential growth of data volume and applications in both wireline and wireless networks. In this chapter, we focus on studying the “economics-based” pricing schemes for managing communication networks.
Economists have proposed many sophisticated pricing mechanisms to extract surpluses from the consumers and maximize revenue (or profits) for the providers. A typical example is the optimal nonlinear pricing (e.g., [7, 8]). In practice,however, we often observe simple pricing schemes deployed by the service providers. Typical examples include flat-fee pricing and (piecewise) linear usage-based pricing. One potential reason behind the gap between “theory” and “practice” is that the optimal pricing schemes derived in economics often has a high implementational complexity. Besides a higher maintenance cost, complex pricing schemes are not “customer friendly” and discourage customers from using the services [9, 10]. Furthermore, achieving the highest possible revenue with complicated pricing schemes requires knowing the information (identity and preference) of each customer, which can be challenging in large-scale communication networks. It is then natural to ask the following two questions:
This chapter tries to answer the above two questions with some stylized communication network models. Different from some previous work that considered a flat-fee pricing scheme in which the payment does not depend on the resource consumption (e.g., [9, 11, 12]), here we study the revenue maximization problem with the linear usage-based pricing schemes, where a user's total payment is linearly proportional to allocated resource. In wireless communication networks, the usage-based pricing scheme has become increasingly popular because of the rapid growth of wireless data traffic. In June 2010, ATT in the United States switched from the flat-free-based pricing (i.e., unlimited data for a fixed fee) to the usage-based pricing schemes for 3G wireless data [13]. Verizon followed up with similar plans in July 2011. Similar usage-based pricing plans have been adopted by major Chinese wireless service providers including China Mobile and China UniCom. Thus, the research on the usage-based pricing is of great practical importance.
In this chapter, we consider the revenue maximization problem of a monopolist service provider facing multiple groups of users. Each user determines its optimal resource demand to maximize the surplus, which is the difference between its utility and payment. The service provider chooses the pricing schemes to maximize his/her revenue, subject to a limited resource. We consider both complete information and incomplete information scenarios and design different pricing schemes with different implementational complexity levels.
Our main contributions are as follows.
It is often quite challenging to design a practical pricing schemes in communication networks. The main difficulties including dealing with the incomplete information structure and limiting the implementational complexity. Under incomplete network information, customers have the private information that is unknown by the service providers. The study of incomplete information is a significant part of microeconomics, especially in several important branches, such as incentive theory [14], information economics [15], organization theory [16], and contract theory [17]. In particular, there exists a rich body of literature on monopoly revenue maximization with incomplete information, for example, [7, 8, 18–26]. Mussa and Rosen in Reference [7] and Maskin and Riley in Reference [8] proposed the optimal price differentiation strategies based on product qualities and quantities, respectively. Armstrong in Reference [22], Bakos and Brynjolfsson in Reference [23], and Geng et al. in Reference [24] studied the optimal multiproduct bundling schemes. Stokey Reference [18], Baron and Besanko in [19], Hart and Tirole in Reference [20], and Acquisti and Varian in Reference [21] focused on multistage price differentiation. Cabral et al. in Reference [25] and Aoyagi in Reference [26] studied the pricing and revenue maximization problem with network externalities. Although these existing results on pricing provide theoretical optimal solutions under incomplete information, they are seldom directly applied in practice, mainly because of their highimplementational complexity. In a practical system, a service provider often needs to constrain the number of pricing choices for the customers, either due to implementation complexity constraint or users’ aversion to too many choices [27].
However, the issue of optimal pricing design subject to complexity constraint is less understood in the literature. One related analytical result is Reference [9], where the authors discussed complexity issue in flat-fee pricing. To the best of our knowledge, our study about partial price differentiation is the first result about the optimal design of limited price choices in usage-based pricing schemes. It is interesting to compare our results on partial price differentiation with results in References [9] and [28]. Shakkottai et al. in Reference [9] showed that the revenue gain of price differentiation is small with a flat entry-fee-based Paris Metro Pricing (e.g., [29]), and a complicated differentiation strategy may not be worthwhile. Chau et al. [28] further derived the sufficient conditions of congestion functions that guarantee the viability of these Paris Metro Pricing schemes. By contrast, our results show that the revenue gain of price differentiation can be substantial for a usage-based pricing system.
Some recent work of usage-based pricing and revenue management in communication network includes References [30–38]. Basar and Srikant in Reference [30] investigated the bandwidth allocation problem in a single-link network with the single pricing scheme. Shen and Basar in Reference [31] extended the study to a more general nonlinear pricing case with the incomplete network information scenario. They discussed the single pricing scheme under incomplete information with a continuum distribution of users’ types. In contrast, our study on the incomplete information focuses on the linear pricing with a discrete setting of users’ types. We also show that, besides the single pricing scheme, it is also possible to design differentiation pricing schemes under incomplete information. Daoud et al. [32] studied an uplink power allocation problem in a CDMA system, where the interference among users are the key constraint instead of the limited total resource considered in this chapter. Jiang et al. in Reference [33], Hande et al. in Reference [34], and Ha et al. in Reference [35] focused on the study of the time-dependent pricing. He and Walrand in Reference [36], Shakkottai and Srikant in Reference [37], and Gajic et al. in Reference [38] focused on the interaction between different service providers embodied in the pricing strategies, rather than the design of the pricing mechanism. Besides, none of the related work considered the partial differential pricing as in this chapter.
We consider a network with a total amount of S limited resource (which can be in the form of rate, bandwidth, power, time slot, etc.). The resource is allocated by a monopolistic service provider to a set of user groups. Each group has Ni homogeneous users1 with the same utility function
where si is the allocated resource to one user in group i and represents the willingness to pay of group i. The logarithmic utility function is commonly used to model the proportionally fair resource allocation in communication networks (see Reference [30] for detailed explanations). The analysis of the complete information case can also be extended to more general utility functions (see Appendix 8.A.1). Without the loss of generality, we assume that . In other words, group contains users with the highest valuation, and group I contains users with the lowest valuation.
We consider two types of information structures:
The interaction between the service provider and users can be characterized as a two-stage Stackelberg model shown in Figure 8.1.
The service provider publishes the pricing scheme in Stage 1, and users respond with their demands in Stage 2. The users want to maximize their surpluses by optimizing their demands according to the pricing scheme. The service provider wants to maximize its revenue by setting the right pricing scheme to induce desirable demands from users. As the service provider has a limited total resource, it must guarantee that the total demand from users is no larger than what it can supply.
The details of pricing schemes depend on the information structure of the service provider. Under complete information, because the service provider can distinguish different groups of users, it announces the pricing and the admission control decisions to different groups of users. It can choose from the complete price differentiation scheme, the single pricing scheme, and the partial price differentiation scheme to realize a desired trade-off between the implementational complexity and the total revenue. Under incomplete information, it publishes a common price menu to all users and allows users to freely choose a particular price option in this menu. All these pricing schemes are discussed one by one in the following sections.
We first consider the complete information case. As the service provider knows the utility and the identity of each user, it is possible to maximize the revenue by charging a different price to each group of users. The analysis will be based on backward induction, starting from Stage 2 and then moving to Stage 1.
If a user in group i has been admitted into the network and offered a linear price pi in Stage 1, then it solves the following surplus maximization problem,
which leads to the following unique optimal demand
In Stage 1, the service provider maximizes its revenue by choosing the price pi and the number of admitted users ni for each group i subject to the limited total resource S. The key idea is to perform a complete price differentiation (CP) scheme, that is, charging each group with a different price.
where , , and . We use bold symbols to denote vectors in the sequel. Constraint (8.5 ) is the solution of the Stage 2 user surplus maximization problem in Eq. (8.3 ). Constraint (8.6 ) denotes the admission control decision, and constraint (8.7 ) represents the total limited resource in the network.
The CP problem is not straightforward to solve, because it is a nonconvex optimization problem with a nonconvex objective function (summation of products of and ), a coupled constraint (8.7 ), and integer variables . However, it is possible to convert it into an equivalent convex formulation through a series of transformations, and thus the problem can be solved efficiently.
First, we can remove the sign in constraint (8.5 ) by realizing the fact that there is no need to set pi higher than for users in group i; users in group i already demand zero resource and generate zero revenue when . This means that we can rewrite constraint (8.5 ) as
Plugging Eq. (8.8 ) into Eq. (8.4 ), the objective function becomes . We can further decompose the CP problem in the following two subproblems:
Denote the solution of as . We further maximize the revenue of the integer admission control variables .
Let us first solve the subproblem in . Note that it is a convex optimization problem. By using Lagrange multiplier technique, we can get the first-order necessary and sufficient condition:
where is the Lagrange multiplier corresponding to the resource constraint (8.9 ).
Meanwhile, we note the resource constraint (8.9 ) must hold with equality, because the objective is a strictly increasing function in . Thus, by plugging Eq. (8.11 ) into (8.9 ), we have
This weighted water-filling problem (where can be viewed as the water level) in general has no closed-form solution for . However, we can efficiently determine the optimal solution by exploiting the special structure of our problem. Note that because , then must satisfy the following condition:
for a group index threshold value satisfying
In other words, only groups with index no larger than will be allocated the positive resource. This property leads to the following simple Algorithm 8.1 to compute and group index threshold : we start by assuming and compute . If Eq. (8.14 ) is not satisfied, we decrease by one and recompute until Eq. (8.14 ) is satisfied.
As , Algorithm 8.1 always converges and returns the unique values of and . The complexity is , that is, linear in the number of user groups (not the number of users).
With and , the solution of the resource allocation problem can be written as
For the ease of discussion, we introduce a new notion of the effective market, which denotes all the groups allocated nonzero resource. For resource allocation subproblem , the threshold describes the size of the effective market. All groups with indices no larger than are effective groups, and users in these groups as effective users. An example of the effective market is illustrated in Figure 8.2.
Now let us solve the admission control subproblem . Denote the objective Eq. (8.10 ) as , by Eq. (8.15 ), then . We first relax the integer domain constraint of ni as . As Eq. (8.13 ), by taking the derivative of the objective function with respect to ni, we have
Also from Eq (8.13 ), we have , thus , for , and , for . This means that the objective is strictly increasing in ni for all , thus it is optimal to admit all users in the effective market. The admission decisions for groups not in the effective market are irrelevant to the optimization, because those users consume zero resource. Therefore, one of the optimal solutions of the subproblem is for all . Solving and subproblems leads to the optimal solution of the CP problem:
Theorem 8.1 provides the right economic intuition: the service provider maximizes its revenue by charging a higher price to users with a higher willingness to pay. It is easy to check that for any . The users with low willingness to pay are excluded from the markets.
Here we summarize some interesting properties of the optimal complete price differentiation scheme:
The threshold-based resource allocation means that higher willingness to pay groups have higher priories of obtaining the resource at the optimal solution.
To see this clearly, assume the effective market size is under parameters and S. Here the superscript (1) denotes the first parameter set. Now consider another set of parameters and S, where for each group i and the new effective market size is . By Eq. (8.13 ), we can see that . Furthermore, we can show that if some high willingness to pay group has many more users under the latter system parameters, that is, is much larger than for some , then the effective size will be strictly decreased, that is, . In other words, the increase of high willingness to pay users will drive the low willingness to pay users out of the effective market.
Theorem 8.1 shows the explicit admission control is not necessary at the optimal solution. Also from Theorem 8.1, we can see that when the number of users in any effective group increases, the price, , for all increases and resource, , for all decreases. The prices serve as the indications of the scarcity of the resources and will automatically prevent the low willingness to pay users to consume the network resource.
In Section 8.3, we showed that the CP scheme is the optimal pricing scheme to maximize the revenue under complete information. However, such a complicated pricing scheme is of high implementational complexity. In this section, we study the single pricing scheme. It is clear that the scheme will in general suffer a revenue loss comparing with the CP scheme. We will try to characterize the impact of various system parameters on such revenue loss.
Let us first formulate the single pricing (SP) problem.
Comparing with the CP problem in Section 8.3, here the service provider charges a single price p to all groups of users. After a similar transformation as in Section 8.3, we can show that the optimal single price satisfies the following weighted water-filling condition
Thus we can obtain the following solution that shares a similar structure as complete price differentiation.
The SP scheme shares several similar properties as the CP scheme (Section 8.3.3), including the threshold structure and admission control with pricing. Similarly, we can define the effective market for the SP scheme.
It is more interesting to notice the differences between these two schemes. To distinguish solutions, we use the superscript “cp” for the CP scheme, and “sp” for the SP scheme.
The proof is given in Appendix 8.A.2. An illustrative example is shown in Figures 8.3 and 8.4.
It is easy to understand that the SP scheme makes less revenue, because it is a feasible solution to the CP problem. A little bit more computation sheds more light on this comparison. We introduce the following notations to streamline the comparison:
On the basis of Theorem 8.1, the revenue of the CP scheme is
where
On the basis of Theorem 8.1, the revenue of the SP scheme is
From Eqs. (8.17 ) and (8.19 ), it is clear to see that because of two factors: one is the nonnegative term in Eq. (8.18 ) and the other is : a higher level of differentiation implies a no smaller effective market. Let us further discuss them in the following two cases:
Finally, we note that the CP scheme in Section 8.3 requires the complete network information. The SP scheme here, on the other hand, works in the incomplete information case as well. This distinction becomes important in Section 8.6.
For a service provider facing thousands of user types, it is often impractical to design a price choice for each user type. The reasons behind this, as discussed in Reference [10], are mainly high system overheads and customers’ aversion. However, as we have shown in Section 8.4, the single pricing scheme may suffer a considerable revenue loss. How to achieve a good trade-off between the implementational complexity and the total revenue? In reality, we usually see that the service provider offers only a few pricing plans for the entire users population; we term it as the partial price differentiation scheme. In this section, we answer the following question: if the service provider is constrained to maintain a limited number of prices, , , then what is the optimal pricing strategy and the maximum revenue? Concretely, the partial price differentiation (PP) problem is formulated as follows.
Here denotes the set . As we consider the complete information scenario in this section, the service provider can choose the price charged to each group, thus constraints (8.20 )–(8.22 ) are the same as in the CP problem. Constraints (8.23 ) and (8.24 ) mean that pi charged to each group i is one of J choices from the set . For convenience, we define cluster , which is a set of groups charged with the same price . We use superscript j to denote clusters and subscript i to denote groups through this section. We term the binary variables as the partition, which determines which cluster each group belongs to.
The PP problem is a combinatorial optimization problem and is more difficult than the previous CP and SP problems. On the other hand, we notice that this PP problem formulation includes the CP scheme () and the SP scheme scenario () as special cases. The insights we obtained from solving these two special cases in Sections 8.3 and 8.4 will be helpful to solve the general PP problem.
To solve the PP problem, we decompose and tackle it in three levels. In the lowest level 3, we determine the pricing and resource allocation for each cluster, given a fixed partition and fixed resource allocation among clusters. In level 2, we compute the optimal resource allocation among clusters, given a fixed partition. In level 1, we optimize the partition among groups.
For a fix partition and a cluster resource allocation , we focus the pricing and resource allocation problems within each cluster , :
The level-3 subproblem coincides with the SP scheme discussed in Section 8.4, because all groups within the same cluster are charged with a single price . We can then directly apply the results in Algorithm 8.2 to solve the level-3 problem. We denote the effective market threshold2 for cluster as , which can be computed in Algorithm 8.2. An illustrative example is shown in Figure 8.5, where the cluster contains four groups (groups 4–7), and the effective market contains groups 4 and 5, thus . The service provider obtains the following maximum revenue obtained from cluster :
For a fix partition , we then consider the resource allocation among clusters.
We will show in Section 8.5.2 that subproblems in level 2 and level 3 can be transformed into a complete price differentiation problem under proper technique conditions. Let us denote its optimal value as .
Table 8.1 Numerical Examples for Feasible Set Size of the Partition Problem in Level 1
Number of Groups | |||||
Number of Prices | |||||
511 | 9330 | ||||
9 | 36 | 99 | 4851 | 999 |
Finally, we solve the cluster partition problem.
This partition problem is a combinatorial optimization problem. The size of its feasible set is , Stirling number of the second kind [39, Chap.13], where is the binomial coefficient. Some numerical examples are given in the third row of Table 8.1. If the number of prices J is given, the feasible set size is exponential in the total number of groups I. For our problem, however, it is possible to reduce the size of the feasible set by exploiting the special problem structure. More specifically, the group indices in each cluster should be consecutive at the optimum. This means that the size of the feasible set is as shown in the last row of Table 8.1 and thus is much smaller than .
Next we discuss how to solve the three-level subproblems. A route map for the whole solution process is given in Figure 8.6.
The optimal solution (8.25 ) of the level-3 problem can be equivalently written as
The equality (a) in Eq. (8.26 ) means that each cluster can be equivalently treated as a group with homogeneous users with the same willings to pay . We name this equivalent group as a super group (SG). We summarize the above result as the following lemma.
On the basis of Lemma 8.1, the level-2 and level-3 subproblems together can be viewed as the CP problem for SGs. As a cluster and its SG from a one-to-one mapping, we will use the two words interchangeably in the sequel.
However, simply combining Theorems 8.1 and 8.2 to solve level-2 and level-3 subproblems for a fixed partition can result in a very high complexity. This is because the effective markets within each SG and between SGs are coupled together. An illustrative example of this coupling effective market is shown in Figure 8.7, where is the threshold between clusters and has three possible positions (i.e., between group 2 and group 3, between group 5 and group 6, or after group 6); and and are thresholds within cluster and , which have two or three possible positions, respectively. Thus, there are possible thresholds possibilities in total.
The key idea resolving this coupling issue is to show that the situation in Figure 8.7 cannot be an optimal solution of the PP problem. The results in Sections 8.3 and 8.4 show that there is a unified threshold at the optimum in both the CP and SP cases, for example, Figure 8.2. Next we will show that a unified single threshold also exists in the PP case.
The proof of Lemma 8.2 can be found in Appendix 8.A.3. The intuition is that the resource should be always allocated to high willingness to pay users at the optimum. Thus, it is not possible to have Figure 8.7 at an optimal solution, where high willingness to pay users in group 2 are allocated zero resource while low willingness to pay users in group 3 are allocated positive resources.
On the basis of Lemma 8.2, we know that there is a unified effective market threshold for the PP problem, denoted as . As all groups with indices larger than make zero contribution to the revenue, we can ignore them and only consider the partition problem for the first groups. Given a partition that divides the groups into J clusters (SGs), we can apply the CP result in Section 8.3 to compute the optimal revenue in the level 2 based on Theorem 8.1.
On the basis of the previous results, we first simplify the level-1 subproblem and prove the following theorem.
The level-1 subproblem is still a combinatorial optimization problem with a large feasible set of (similar to the original level 1). The following result can help us to reduce the size of the feasible set.
The proof of Theorem 8.4 is given in Appendix 8.A.4. We first prove that this result is true for the level-1 subproblem without constraint (8.29 ) and further show that this result will not be affected by Eq. (8.29 ). The intuition is that high willingness to pay users should be allocated positive resources with priority. It implies that groups with similar willingness to pays should be partitioned in the same cluster, instead of several far away clusters. Or equivalently, the group indices within each cluster should be consecutive.
We define as the set of all partitions with consecutive group indices within each cluster, and is the value of objective of the level-1 subproblem for a partition . Algorithm 8.3 finds the optimal solution of the level-1 subproblem. The main idea for this algorithm is to enumerate every possible partition in set , and then check whether the threshold condition (8.29 ) can be satisfied. The main part of this algorithm is to enumerate all partitions in set of feasible partitions. Thus the complexity of Algorithm 8.3 is no more than .
We know the optimal market threshold is upper bounded, that is, . Thus we can first run Algorithm 8.1 to calculate the effective market size for the CP scheme . Then, we search the optimal iteratively using Algorithm 8.3 as an inner loop. We start by letting and run Algorithm 8.3. If there is no solution, we decrease by one and run Algorithm 8.3 again. The algorithm will terminate once we find an effective market threshold where Algorithm 8.3 has an optimal solution. Once the optimal threshold and the partition of the clusters are determined, we can further run Algorithm 8.1 to solve the joint optimal resource allocation and pricing scheme. The pseudo-code is given in Algorithm 8.4 as follows.
In Algorithm 8.4, it invokes two functions: Resource-Allocation-CP (, S) as described in Algorithm 8.1 and Level-1 () as in Algorithm 8.3.
The above analysis leads to the following theorem.
Next we discuss the complexity of Algorithm 8.4. The complexity of Algorithm 8.1 is , and we run it twice in Algorithm 8.4. The worst case complexity of Algorithm 8.3 is , and we run it no more than times. Thus the whole complexity of Algorithm 8.4 is no more than , which is polynomial of I.