4.1 Introduction

The essence of smart pricing is exploiting the price responsiveness of the demand side to achieve objectives such as obtaining higher profit, improving customer experience, and sustaining reliable operation. The enormous pace of advances in technology and engineering and new economic practices cause rapid changes in consumer behavior that create new dynamics as well as problems affecting the physical infrastructures and the corresponding markets. Hence, more sophisticated and novel smart pricing methods are required to control and take advantage of the demand-side dynamics.

Smart pricing refers to various techniques such as charging consumers depending on the service usage time, setting location-based tariffs, and imposing prices based on consumer activity levels. For instance, hourly and daily fluctuations in demand are striking patterns that are common to both the Internet and the electricity grid as seen in Figure 4.1. Considering this pattern, Internet service providers and mobile operators charge their subscribers based on the amount of data communicated or the time of communication in order to alleviate congestion in the network [1, 2]. Similarly, electricity usage also can be priced based on the amount or the time of consumption so that daily fluctuations of the grid load are reduced [3].

The driving factors for smart pricing are the consumer characteristics and consumers’ economic incentives. Consumption amount, service usage time, demand patterns over certain periods of time, and randomness of the load are several aspects of the overall consumer behavior and they consequently affect the price setters’ strategies. On the other hand, consumer behavior is naturally responsive to the pricing decisions because humans oversee their own economic welfare. Therefore, the resulting closed loop interactions are critical to the operation of the physical infrastructure and the corresponding market in terms of reliability, stability, and efficiency.

Demand-side characteristics are increasingly exposed to the market because of sophisticated control methods, ubiquitous communication capabilities, and innovative market practices. For instance, the trend for deregulation in energy markets, smart power meters for households, or advanced data gathering, tracking, and management methods over the Internet causes the consumers to be more active, more controllable, and more predictable. Therefore, the producers and intermediaries have more incentives and possibilities to influence or directly control the consumer behavior via smart pricing strategies in order to reduce costs and sustain stable operation. In this chapter, we focus on demand-side flexibilities and the predictability of consumer activities and discuss the means of exploiting these aspects of consumer behavior by using smart pricing techniques.

Demand-side flexibilities usually comprise temporal elasticities involving deferring loads until a specified deadline, shifting consumption within a certain period of time, and using a service intermittently. Consumers, who are motivated by their economic needs, are capable of exercising these flexibilities owing to technologies such as intelligent devices with two-way communication capabilities and sophisticated software applications that are able to manage user demand. Hence, consumers can be incentivized to defer or shift their demand by time- and consumption-dependent smart pricing methods as investigated in Section 4.2.

Predictability of consumer activities is a powerful capability reaped through the significant advancement of machine learning algorithms and sophisticated statistical modeling tools [7–11]. It captures the correlated and repeated user behavioral patterns over time, as well as the statistically anticipated future demand. The ability of suppliers/service providers to harness such an opportunity has a significant potential in smoothing-out demand fluctuations over time, reducing commodity costs, and enhancing the consumer satisfaction with high quality services. Essentially, suppliers/service providers can proactively serve portions of the peak-hour load, ahead of time, particularly during the off-peak hour, based on the anticipated demand of each consumer. Hence, at the actual peak-demand instant, a considerable amount of load will be already served and excessive costs will be avoided. Such a capability is referred to as proactive service.

In the rest of this chapter, demand-side flexibility features are introduced in Section 4.2, followed by an example design of pricing policies for theday-ahead electricity markets with flexible demand in Section 4.2.1. In Section 4.3, the notion of predictable user demand and proactive data service is discussed. Section 4.3.1 provides an example optimization of smart pricing policies for demand shaping and proactive data services.

4.2 Pricing Under Demand Flexibilities

Flexibilities and responsiveness to price are intimately related aspects of consumer behavior that have been present in almost all types of markets. In its simplest form, consumers, who have the elasticity to be served earlier or later than their intended time, can observe the market prices and decide on their time of consumption to obtain economic benefits. Recently, consumers have more ground to exhibit their temporal flexibilities in various markets, thanks to the rapid advances in technology and engineering. For example, energy consumption controllers can manage the electricity usage of households by deferring tasks like using washing machines to late night hours when the electricity price is lower [12]. Furthermore, as an increasingly common measure in mobile software industry, smart applications have the ability to regulate a mobile data user's downloads considering the type of network connection (e.g., Wi-Fi and 4G) so that user's payments are reduced or data plan limits are not exceeded [13, 14]. It should also be noted that consumers, who are economically driven entities, will have more motivation to employ their existing as well as emerging flexibilities in order to obtain economic benefits.

Although the increased elasticity of the demand side brings in advantages to the market, it also raises concerns that can be critical to the physical infrastructures and the corresponding markets. The closed-loop system resulting from supply demand interactions and the random fluctuating demand behavior have already created issues such as existence of equilibrium prices and system stability under random variations. These issues are further amplified by the increasing flexibility of the demand side. As an example, consider the electricity grid that exhibits daily load fluctuations as shown in Figure 4.1. It is beneficial for the grid to have shiftable demand that can be activated during low demand hours to shave the peak load. As discussed earlier, smart pricing policies can achieve this goal by incentivizing consumers to use their devices during late night hours. However, higher penetration of demand flexibilities into the market and increased price responsiveness of consumers may cause undesirable peaks in the grid load. Moreover, market prices may not reach equilibrium or equilibria because of the high responsiveness of flexible consumers. Consequently, the closed-loop dynamic system can exhibit increased volatility in price, supply, and demand [15, 16].

Smart pricing strategies are anticipated to exploit the increased flexibility of demand as well as alleviate the issues created by these flexibilities. Hence, smart pricing is essential in influencing consumers and incentivizing them to practice their flexibilities in order to cut down supplier costs and maintain reliable marketoperation by lessening abrupt changes in prices and system load. For instance, time-dependent pricing can be implemented to decrease the variability of the total load in mobile data networks by establishing peak and off-peak prices and communicating them to the subscribers to incentivize them to change their time of use and consumption amounts [17]. In this section, we focus on the smart electricity grid to explore demand-side flexibilities deeper with more specific examples. In the rest of the section, we study two smart pricing methods that harness the temporal flexibilities of consumers to obtain smoother grid load.

4.2.1 The Day-Ahead Electricity Market with Flexible Consumers

The smart electrical grid is coming into prominence as one of the systems that will be extensively reaping the benefits of flexibilities in the demand side. The penetration of information and communication technologies into the operation of the electrical network transforms it into the smart grid [18]. This evolution turns the demand side into a more controllable entity so that the resulting demand-side flexibilities can be intensively exploited for more efficient grid operation [19–21].

The flexibilities of electricity consumers such as end users and distributers arise in different forms. Changing the amount of consumption, shaping the demand profile over a day or a week, delaying the activation of electric loads such as household appliances or factory machines, and shifting the time of use of electricity throughout the day are the type of flexibilities that can be harnessed for various objectives [12, 22–24]. For example, smart meters in households can communicate to the load aggregators or electricity retailers the usage preferences and load requirements of consumers in response to electricity prices. Then, via energy consumption controllers the electricity usage of household appliances can be administered by changing the time of the activation of the individual devices as seen in Figure 4.2. In such a scenario, the objective of the operator would be to decrease its costs while preserving consumer satisfaction, and the consumers would benefit from lower prices or rewards for their contribution [12, 25].

The methods that take advantage of demand-side flexibilities for efficient and reliable grid operation can be collected under demand-side management or demand response, which have recently drawn considerable attention in the engineering community [20, 21, 26, 27]. The common objective of these techniques is to alleviate the fluctuations of the grid load in order to decrease the capital, operational, and maintenance costs and increase robustness and reliability of the electrical grid. For example, as a demand response technique, load aggregators and companies can participate in the grid operation; they help the grid operator in smoothing out the grid load profile by shedding their load when the operator signals them to do so [28]. It should be noted that the parties involved in demand response are economically driven entities. Therefore, a viable way to implement sophisticated smart pricing schemes is to incentivize the participants to expose their flexibilities such as the ability to shift or delay load or to change consumption levels.

In the literature, there are numerous works that utilize optimization and game theoretic techniques to exploit the demand-side flexibilities in the electrical grid by the help of smart pricing, For example, [12, 23, 24, 29–33]. In various works, it is the key concept to build practically useful demand response models and to devise corresponding distributed smart pricing algorithms [23, 30]. In general, the objective is to achieve optimum social welfare, which is measured as the aggregate system utility minus the total costs incurred. Toward this objective, pricing algorithms are designed to incentivize the participating units to shift their demand while maximizing their own utilities. In these problems, the presence of supply uncertainty as well as the dynamics of the day-ahead and the real-time planning can also be taken into account [24, 32]. Furthermore, game theoretic approaches are also employed by formulating games between subscribers of utility companies in order to develop distributed algorithms to reach the Nash equilibrium [29, 31].

Although envisioned to significantly improve the grid efficiency, demand-side flexibilities and economic incentives of consumers can have adverse effects on the electrical grid operation [15]. For instance, the consumers with shiftable loads can act opportunistically and greedily by purchasing the maximum amount of electricity that they can at lower prices [16, 25, 34]. If a large number of such consumers schedule their loads in the hour of the day with the lowest price, the total load in the grid significantly deviates from its predicted daily pattern. In this case, the supply deficit should be settled in a balancing market that incurs additional costs to both suppliers and consumers [35]. Furthermore, if the market price quickly responds to changes in load, intelligent consumer behavior creates high supply and price volatility giving rise to a closed-loop system with stability problems [36].

Including the consumers with flexible demand together with the suppliers in the electricity market is a feasible strategy to mitigate the adverse effects of the demand-side flexibilities [35]. In the following, two smart pricing strategies are presented for the day-ahead electricity market comprising multiple number of suppliers and consumers where consumers can flexibly shift some of their total dailydemand within a day.

4.2.1.1 Day-Ahead Electricity Market

Day-ahead electricity market is implemented 1 day before the procurement of electric power. It involves transactions between generator companies as suppliers and intermediaries such as load aggregators, distributors, and retailers as consumers. At the termination of the market, the day-ahead prices are established.

The market is operated by a nonprofit third party called Independent System Operator (ISO). The ISO is responsible for administering the transactions between the market participants, setting the day-ahead prices, determining generation and consumption schedules, and ensuring the critical constraint of matching supply and load at all times. The day-ahead schedules for the load, supply, and the price are computed for the duration of a day that is divided into T time slots. The slotted time structure models the appropriate durations, possibly ranging from minutes to hours, over which the load-supply matching will be performed by establishing the day-ahead schedules.

The intermediaries are economically driven parties, so they naturally seek ways of attaining lower prices. In order to increase their profit, the intermediary parties exploit the demand-side flexibilities of their customers. Consequently, intermediaries appear as flexible consumers to the day-ahead market by reflecting the flexibilities of the end users. For instance, a load aggregator can shape its load by moving its customers’ shiftable loads to the times of the day with lower market prices. Hence, the load aggregator becomes more price responsive as seen by the market operator.

We consider M generator companies (suppliers) and N intermediaries (consumers) with flexible loads in the day-ahead market that is operated by an ISO.

1. 1. Suppliers. At each time slot, generator m is required to provide the amount of power that is determined by its supply schedule . By generating amount of power over the time horizon, company m obtains of revenue from the market, but it also pays for generation costs. Given the market prices, the goal of each generator company is to offer the supply schedule to the market that maximizes the company's profit. Accordingly, the optimization problem for generator company m is formulated as
   4.1
2. 2. Consumers. Consumer n has a total amount of load that has to be served completely by the end of the time horizon. The load schedule of consumer n is defined over the time slots as , and it has to satisfy . By consuming amount of power, consumer n pays to the market and obtains amount of utility. Consumer n aims to allocate its total daily load at the most favorable time slots based on its utility functions and market price. This objective is formulated as the following optimization problem
   4.2
   4.3
   Demand-Side Flexibilities. The flexibility of consumer demand is modeled by the utility function together with the constraint to satisfy the predetermined demand over the scheduling horizon T. In particular, for the first algorithm, the utility function is separable and additive over time, that is, , whereas for the second algorithm the utility function is arbitrary, that is, no structure such as convexity is assumed. For example, if a demand needs to be served over a limited interval, say between slots and , we can set for . As another example, if a consumer has a higher preference for time slot than for time slot t, we set . Such ordering over time between utility functions can be utilized to model the scenario where a user wants its demand to be served at and a disutility is imposed for every time slot in which the serving time is delayed, as depicted in Figure 4.3.

   

3. 3. ISO. The ISO's objective is to maximize the social welfare, which is defined as thetotal utility obtained by the participating entities in the market minus the total costs incurred. While maximizing social welfare, the ISO is also responsible for matching supply to load. This objective is formulated as
   4.4
   4.5
   4.6
   4.7

   where the constraint (4.5 ) is for matching supply to load and the constraint (4.6 ) is for satisfying each consumer's demand over the time horizon.

Next, two distributed algorithms that achieve the optimum solution of the social welfare problem are presented under different sets of assumptions. In the first algorithm, we assume that the cost and the utility functions possess various convexity and smoothness properties. In the second algorithm, on the contrary, we do not restrict ourselves to any particular class of cost and utility functions. Instead, we simply assume that the feasible set of the social welfare problem is finite and discrete.

4.2.3 Optimal Bundle Pricing under Discreteness Assumptions

Although the cost and utility structures of Section 4.2.2 cover a wide range of supplier and consumer characteristics, convexity assumptions can be quite restrictive as well. For instance, power plants usually consist of multiple generating units; hence, activation and deactivation costs introduce discontinuities to the total cost [39]. On the other hand, obtaining zero utility when a task is not processed and obtaining a constant level of utility when a task is processed are a common consumer characteristics that result in discontinuous and nonconcave utility functions. Therefore, in this setup, the utility and cost functions are not assumed to have any particular structure. Instead, the following assumption facilitates the development.

This assumption is practically meaningful because the amount of supplied and demanded power can be well approximated by quantization with sufficiently small bins. For instance, the production bids from the generating units can be easily enforced to be multiples of kilowatt or megawatt.

The idea leading to the distributed bundle pricing algorithm is based on linearizing the problem (4.4 ) and then solving the linear program with distributed primal-dual methods. Note that the linearized problem would be still difficult to solve because of the arbitrary structures of the cost and utility functions. However, optimality of the primal-dual solutions for a linear problem can be established via complementary slackness (CS) conditions, which introduce further simplifications. In particular, the market participants’ common objective is maximizing their own welfare;hence, the local solutions possess certain properties on the maximal values of the primal and dual variables. The reader is referred to References 37 and 38 for the detailed derivations of the algorithm presented here and to References 40 and 41 for a thorough study of primal-dual methods for linear programs.

The distributed bundle pricing algorithm, which achieves the optimal value of the problem (4.4 ), is depicted in Figure 4.4. In the algorithm, and are the surplus terms for consumer n and supplier m, respectively; is the surplus term for the overall market transactions; and and are the bundle prices for the production and consumption schedules and , respectively. Bundle prices are for the schedules over the whole optimization horizon T, and they are specific to market participants. The initialization step of the algorithm and the fact that the market participants solve their own local problems simplifies the process of verifying CS conditions for the ISO [38].

4.2.4 Numerical Examples and Insights

For the numerical experiments, consumer utility functions of the form are used, where is strictly concave in x for . For the generator company, functions for generation costs and for ramp costs are used, where is strictly convex in s for .

In the numerical setup, which represents a typical urban area and its surroundings, there are consumers (load aggregators) with flexible loads, generator companies, and the schedules are determined for the next 20 time slots. Parameters , , and are selected randomly for each participant such that the convexity assumptions are satisfied. For simplicity, the generator cost parameters are set identical for all time slots, that is, and for all t. On the other hand, to model the flexibilities a preferred time slot is randomly chosen for each consumer n and value is assigned randomly. Then, for other time slots, is increased as the difference gets larger, that is, with . With this construction, for all is obtained. The described characteristics of the utility functions used in the numerical examples are demonstrated in Figure 4.3. It is worth noting that the specific flexibilities of different loads or devices that belong to a single consumer are not considered in this utility model.

Furthermore, in order to model a realistic market environment and to investigate the effects of the flexible load on electricity market, inflexible load, which does not shift between time slots, is introduced. Inflexible load has a sinusoidal pattern that effectively models fluctuations in electric load during the course of a day. In the numerical example, the total flexible load is set to approximately of the inflexible load.

Figure 4.5a displays the load allocation achieved by the time-dependent distributed pricing algorithm. As expected, the flexible consumers are incentivized to shift their demand to the time slots where inflexible load has the lowest concentration and, hence, the lowest prices occur. Moreover, prices at these time slots show a fairly smooth behavior. This is similar to the desired output of demand response mechanisms (e.g., [30]) that stack more load or shed load when a surplus or deficit in supply, respectively, is predicted.

For comparison, a baseline day-ahead pricing scheme is also examined in which flexible consumers do not participate; price schedule is determined based on the inflexible load. In this scheme, each flexible consumer decides on its load schedule that maximizes its utility based on the already-settled day-ahead prices. Resulting price schedule and load allocation are presented in Figure 4.5b, where it is observed that the flexible load concentrates at the time slots where the lowest prices are witnessed. Nevertheless, this is an expected outcome because all the flexible consumers can opt to serve their demand at time slots with low price as long as their flexibilities are loose enough. Furthermore, although the consumers with flexible demand maximize their welfare, the generator companies suffer high production costs that are not compensated by the market price.

4.3 Pricing Under Predictable Demand

Recent studies on human behavioral patterns have asserted that the activities of humans are highly predictable [7–11, 42]. These findings are strengthened by the success of existing machine learning and statistical modeling tools that harness such a predictability in characterizing customer interests and preferences. Yet, several prediction capabilities are considerably underutilized in the direction of resource allocation and demand management.

In data networks, for example, service providers incur a proportional cost because of the resources harnessed in data delivery. These costs typically vary on a timely basis depending on the consumer activities. For instance, Figure 4.1 a shows that the demand on data services consistently drops to minimum levels during late night and early morning hours. Peak demand, however, occurs during the noon and early night hours. Coupling this observation with the fact that energy costs grow superlinearly with the total load (see, e.g., [43–48]), service providers are urged to substantially shape the users demand over time in order to render it evenly distributed and minimize excessive peak costs. This can be realized through proactive data services, a resource allocation paradigm that utilizes the predictability of the user demand in load balancing as follows.

Essentially, data items with high popularity can be partially delivered and stored on the devices of respective consumers during the off-peak hour, that is, when the demand levels are reasonably low. These portions can then be pulled directly from the devices at the actual instant of demand, which is projected to occur during the peak hour. Thus, only the unserved parts will need to be supplied as actual demand during the peak hour, and service providers effectively cut down extreme peak-hour costs, while attaining a higher level of consumer satisfaction [49–55]. Besides cost minimization, consumers will experience a better quality of service (QoS) performance in terms of service delays, and buffering. Figure 4.6 provides an illustration of the load patterns under proactive data service.

The quality of proactive service, however, relies heavily on the accuracy of predictions made. While the randomness associated with the demand patterns may result in an undesired confusion at the service provider, pricing incentives can be offered so as to enhance the certainty about future demands. While the direct approach for demand shaping offers discounts on the original price at the off-peak time to regulate the demand fluctuations (cf. [1, 17]), the pricing approach considered in this section aims to render the users demand more deterministic, rather than changing their activity times.

Such indirect approach yields price allocation strategies over data items and varies from a user to another, that is, user and data-item-dependent pricing. With proactively served items receiving lower prices, consumer demand can be efficiently shaped to increase the likelihood of these items [50, 51], as discussed in the following sections.

4.3.1 Pricing for Demand Shaping and Proactive Download in Data Networks

This section is concerned with the joint design of proactive data service strategies and pricing policies to minimize the expected service provider costs and to enhance of the certainty about the random user demand.

To utilize the predicable demand capabilities, service providers need to have sufficient knowledge regarding several aspects of their respective customers, a requirement that can be fulfilled through intelligent learning and tracking of the user interactions. Such interactions include the following.

1. 1. Activity Patterns. Each user has an intrinsic activity profile determined by the time instants at which he/she requests data. Such activities depend on a variety of elements, including age, type of work, education level, economical status, and so on. The aggregation of user activity patterns by the service providers allows for a strong acquaintance with the load levels over time (like in Fig. 4.1) and gives meaningful estimates about the cost dynamics. This can particularly be captured by the parameter , whichis the probability that user n will remain silent at time t. Thus, the user requests a data item with probability .
2. 2. Interests and Preferences. These represent a key element that characterizes the demand of each user when active. For instance, between two lectures, a student may decide to watch a YouTube video, thus becoming active with respect to the YouTube service provider. Now, among the available collection of YouTube videos, he/she selects a specific comedy movie. Such a choice is governed by the user's perception of this video, which ultimately is tied to his/her own interests and preferences. Several service providers, such as Netflix, Hulu, and YouTube, already employ sophisticated collaborative filtering techniques (cf. [56–59]) in order to infer these quantities. Nevertheless, they can further be utilized in proactive data services, as discussed in the following section. In the sequel, the vector , with , represents the valuation (or rating) of data item m () as recognized by user n.
3. 3. Economical Responsiveness. As users belong to a variety of economic classes, their responses to a service price differs from one to another, even though they might share the same interest in such a service. Rich users, for example, may pay for an expensive data item as long as it is well preferred. On the other hand, the rest of the users, who equally prefer this data item, may decide not to buy this item in favor of buying another cheaper one with a similar or slightly less quality. Service providers can leverage the economical responsiveness to enhance the proactive service performance.

The responsiveness of user n at time t depends on the price vector , where is the price of data item m as set by the service provider to user n, and time t. The maximum allowable price for a data item is . Now, the economical responsiveness is measured by a function that maps pricing vectors into demand profiles. An example mapping considered here is

4.10

The ratio of quantifies the utility of choosing item m, while dividing by the sum of utilities for all data items captures the relative utility of choosing item m among the M data items.

Figure 4.7 displays the above three aspects on a diagram illustrating the high level operation of cost minimization and demand shaping through: proactive services and pricing. While each user has a wide set of characteristics such as culture, age, education, work, and economic state, the service provider can only observe his/her demand and payments.

Examples for such service provider networks are Netflix and YouTube, which are supposed to have a collection of M data items and N end users.

4.3.1.1 Demand Profiles

The service provider can divide the operational time axis into numerable time slots, to facilitate the cost optimization process and efficiently enable proactive data services. To each time slot t, a demand profile for user n () is constructed and denoted by , where is a collection of probabilities quantifying the demand of this user over the set of M data items, at that specific time slot. Further,

Thus, is the probability that user n requests item m at time t when offered a pricing vector . Naturally, the mapping decreases in and depends implicitly on and as manifested in Eq. (4.10).

The random variable describes the demand of user n to data item m at time t, which is equal to 1 if such an event happens and is 0 otherwise. That given, the distribution of is

As a number of works suggest (cf. [9, 11, 17, 51]), the user activity patterns exhibit a periodic behavior that typically repeats itself over a course of a single day, a result that has been further manifested by the measurements depicted in Figure 4.1a and extended in References 4 and 5. The service provider can divide the day into a cycle of T time slots over which varies from one slot to another, but with , for any positive integer k and time slot . In other words, the activity profile for every user n is cyclostationary with a period of T slots.

Following Remark 4.4, the demand profiles satisfy for any user n, time t, and nonnegative integer k. Figure 4.8 illustrates the periodic nature of user demand statistics over time. With the introduced notation, the total load encountered at slot t for a nonproactive network is given by

4.11

with being the size of data item m.

In the following, the constructed demand profiles are harnessed in cost minimization. Section 4.3.2 addresses the cost profile and proactive data service allocation, while Section 4.3.3 discusses the pricing strategies leveraged to attain the new profiles.

4.3.2 Cost Minimization via Proactive Data Service and Demand Shaping

The service provider seeks an optimal allocation of proactive data services, demand profiles, and pricing policies attaining the optimized profiles to minimize the time average cost of data delivery. The cost at each slot is typically a superlinear function of the aggregate load denoted by C. Proactive downloads constitute a key enabling parameter to the optimization framework and are modeled as follows. The proactive download value of data item m at time is denoted by and served to user n at time slot t. Such proactive downloads are assumed to take place only for the one-slot-ahead data; hence, take into account the potential items receiving fast updates (as some YouTube channels, and social networks experience fast update rates). The vector captures all the proactive downloads made to user n at time t.

The resulting aggregate load at the service provider in time slot t can be written in terms of as

4.12

Figure 4.9 illustrates the dynamics of proactive downloads for some user n at time t.

The service provider now can optimize over the proactive downloads , demand profiles , and pricing policies to minimize its time average expected cost as

4.13

4.14

4.15

The following remarks about the above formulation can be made.

To elaborate further on the user flexibility, one can think of a service provider that targets all users demand to be directed to the data item with the smallest size. It can substantially raise the prices of the rest of data items. This will lead to a major change in the demand profiles of those users who do not essentially prefer such an item. Thus, users will feel unsatisfied about the quality of the cheap data items, with the rest being overpriced.

One of the potential metrics that capture the user flexibility is the entropy of his/her initial profile [60]. Given that user n is active at time t, then the initial probability of requesting item m is denoted by , with the normalized profile . The entropy of such a profile quantifies the certainty about the users demand. High values of entropy reflect an indeterministic user who equally prefers any of the offered data items. On the other hand, small values of entropy reveal a deterministic user, who is more specific about the content to choose. Hence, high entropy users exhibit more flexibility to change their demand in response to pricing policies, whereas low entropy ones are typically less flexible.

Coupling this observation with the notion that deterministic users facilitate proactive data downloads, the user flexibility measure can be realized by an M-dimensional ball centered at the initial normalized profile with a radius proportional to the entropy of that profile [51]. This is called the entropy-ball constraint (EBC). Figure 4.10 depicts an illustrating shape for the EBC with .

Price allocation strategies that utilize the economical responsiveness knowledge are addressed in more detail in Section 4.3.3.

Detailed proof of this result is detailed in Reference 50.

In Reference 50 the cost reduction via proactive downloads only is proven to scale with the number of users at least as the first derivative of the cost function does. Figure 4.11 depicts the effect of proactive downloads on the network load. The expected load is considerably balanced through optimal proactive services as compared to that of reactive allocation strategies.

In Reference 51, an iterative algorithm has been developed, under a convex cost function C. The algorithm starts with a point , where is the initial demand profiles and is the associated globally optimal¹ proactive download. In other words, the initial point is the result of optimal proactive downloads only without demand shaping.

The algorithm applies a series of successive solutions to approximate convex optimization problem, until it converges to a locally optimal solution of the original problem , with a strictly lower cost than that of . That is, with demand shaping, the system can leverage a strictly reduced cost beyond that of proactive downloads only. A numerical example on this algorithm is provided in the following section.

4.3.3 Pricing Policies Attaining Modified Profiles

Upon the calculation of the optimized profiles , the service provider assigns new pricing policies, , so that the users adjust their demand accordingly. Figure 4.12 illustrates this step for some user n at time slot t.

Generally, the mapping functions capturing the economical responsiveness can fit the optimized profiles through multiple pricing policies. The service provider then needs to carefully select the best of such policies. One possible objective is the maximization of the proportionally fair price allocation over all data items, users, and time slots. That is,

4.16

The optimization (4.16) can further be decoupled across time and users. With the instance realization in Eq. (4.10), the service provider may solve a geometric programming problem per user n and time slot t.

The following example illustrates smart pricing for proactive download and demand shaping under a quadratic cost function.

References

1. 1. C. Joe-Wong, S. Ha, and M. Chiang. “Time-dependent broadband pricing: feasibility and benefits. In 2011 31st International Conference on Distributed Computing Systems (ICDCS). IEEE, 2011, pp. 288–298.
2. 2. S. Sen, C. Joe-Wong, S. Ha, and M. Chiang, “Incentivizing time-shifting of data: a survey of time-dependent pricing for internet access,” IEEE Communications Magazine, 50(11), 2012, 91–99.
3. 3. A. J. Wood and B. F. Wollenberg, Power generation, operation, and control. Wiley-Interscience, Hoboken NJ, 2012.
4. 4. IIT Wireless Services, Illinois Institute of Technology, 2013 [online]. Available: http://www.iit.edu/ots/wireless.shtml
5. 5. RRDtool Gallery, RRDtool, 2013 [online]. Available: http://oss.oetiker.ch/rrdtool/gallery/index.en.html
6. 6. Iso New England, historical data. Available at: http://www.iso-ne.com/markets/hstdata/index.html
7. 7. N. Eagle and A. Pentland. “Reality mining: sensing complex social systems,” Personal and Ubiquitous Computing, 10, 2006, 255–268.
8. 8. K. Farrahi and D. Gatica-Perez. Discovering human routines from cell phone data with topic models. In The 12th IEEE International Symposium on Wearable Computers, pp. 29–32, 2008.
9. 9. B. S. Jensen, J. E. Larsen, K. Jensen, J. Larsen, and L. K. Hansen. “Estimating human predictability from mobile sensor data. 2010 IEEE International Workshop on Machine Learning for Signal Processing (MLSP), pp. 196–201, Sept. 2010.
10. 10. R. Kwok. “Personal technology: phoning in data,” Nature, 458, 2009, 959–961.
11. 11. C. Song, Z. Qu, N. Blumm, and A. Barabas. “Limits of predictability in human mobility,” Science, 327, 2010, 1018–1021.
12. 12. C. Joe-Wong, S. Sen, S. Ha, and M. Chiang, “Optimized day-ahead pricing for smart grids with device-specific scheduling flexibility,” IEEE Journal on Selected Areas in Communications, 30(6), 2012, 1075–1085.
13. 13. S. Higginbotham, “Mobile operators want to charge based on time and apps,” gigaOm, December 14 2010.
14. 14. “The Mother of Invention: Network Operators in the Poor World Are Cutting Costs and Increasing Access in Innovative Ways,” Special Report, The Economist, September 24 2009.
15. 15. D. Materassi, M. Roozbehani, and M. A. Dahleh. Equilibrium price distributions in energy markets with shiftable demand. In 2012 IEEE 51st Annual Conference on Decision and Control (CDC). IEEE, 2012, pp. 3183–3188.
16. 16. M. Roozbehani, A. Faghih, M. I. Ohannessian, and M. A. Dahleh, The intertemporal utility of demand and price elasticity of consumption in power grids with shiftable loads. In 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC). IEEE, 2011, pp. 1539–1544.
17. 17. S. Ha, S. Sen, C. Joe-Wong, Y. Im, and M. Chiang. Tube: time-dependent pricing for mobile data. In Proceedings of the ACM SIGCOMM 2012 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. ACM, 2012, pp. 247–258.
18. 18. H. Farhangi. “The path of the smart grid,” IEEE Power and Energy Magazine, 8(1), 2010, 18–28.
19. 19. D. Kirschen. “Demand-side view of electricity markets,” IEEE Transactions on Power Systems, 18(2), 2003, 520–527.
20. 20. P. Palensky and D. Dietrich. “Demand side management: demand response, intelligent energy systems, and smart loads,” IEEE Transactions on Industrial Informatics, 7(3), 2011, 381–388.
21. 21. G. Strbac. “Demand side management: benefits and challenges,” Energy Policy, 36(12), 2008, 4419–4426.
22. 22. A. Papavasiliou and S. S. Oren. “Supplying renewable energy to deferrable loads: algorithms and economic analysis,” In 2010 IEEE Power and Energy Society General Meeting. IEEE, 2010, pp. 1–8.
23. 23. N. Li, L. Chen, and S. Low. Optimal demand response based on utility maximization in power networks. In 2011 IEEE Power and Energy Society General Meeting. IEEE, 2011, pp. 1–8.
24. 24. L. Jiang and S. Low. Multi-period optimal energy procurement and demand response in smart grid with uncertain supply. In 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC). IEEE, 2011, pp. 4348–4353.
25. 25. S. Chen, N. Shroff and P. Sinha. Heterogeneous Delay Tolerant Task Scheduling and Energy Management in the Smart Grid with Renewable Energy. Selected Areas in Communications, IEEE Journal on, 31(7), 2013, 1258–1267.
26. 26. M. H. Albadi and E. El-Saadany. Demand response in electricity markets: an overview. In IEEE Power Engineering Society General Meeting, 2007. IEEE, 2007, pp. 1–5.
27. 27. F. Rahimi and A. Ipakchi, “Demand response as a market resource under the smart grid paradigm,” IEEE Transactions on Smart Grid, 1(1), 2010, 82–88.
28. 28. R. Faranda, A. Pievatolo, and E. Tironi, “Load shedding: a new proposal,” IEEE Transactions on Power Systems, 22(4), 2007, 2086–2093.
29. 29. A. Mohsenian-Rad, V. Wong, J. Jatskevich, and R. Schober. Optimal and autonomous incentive-based energy consumption scheduling algorithm for smart grid. In Innovative Smart Grid Technologies (ISGT), 2010. IEEE, 2010, pp. 1–6.
30. 30. L. Chen, N. Li, S. Low, and J. Doyle. Two market models for demand response in power networks. In IEEE SmartGrid Comm, 2010.
31. 31. A. Mohsenian-Rad, V. Wong, J. Jatskevich, R. Schober, and A. Leon-Garcia, “Autonomous demand-side management based on game-theoretic energy consumption scheduling for the future smart grid,” IEEE Transactions on Smart Grid, 1(3), 2010, 320–331.
32. 32. P. Samadi, A. Mohsenian-Rad, R. Schober, V. Wong, and J. Jatskevich. Optimal real-time pricing algorithm based on utility maximization for smart grid. In 2010 First IEEE International Conference on Smart Grid Communications (SmartGridComm). IEEE, 2010, pp. 415–420.
33. 33. M. He, S. Murugesan, and J. Zhang. Multiple timescale dispatch and scheduling for stochastic reliability in smart grids with wind generation integration. In 2011 Proceedings IEEE INFOCOM. IEEE, 2011, pp. 461–465.
34. 34. A. Faghih, M. Roozbehani, and M. Dahleh. Optimal utilization of storage and the induced price elasticity of demand in the presence of ramp constraints. In 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC). IEEE, 2011, pp. 842–847.
35. 35. C. Su and D. Kirschen, “Quantifying the effect of demand response on electricity markets,” IEEE Transactions on Power Systems, 24(3), 2009, 1199–1207.
36. 36. M. Roozbehani, M. A. Dahleh, and S. K. Mitter. “Volatility of Power Grids Under Real-Time Pricing,” IEEE Transactions on Power Systems, 27(4), 2012, 1926–1940.
37. 37. O. Dalkilic, O. Candogan, and A. Eryilmaz. Pricing algorithms for the day-ahead electricity market with flexible consumer participation. In The 2nd IEEE International Workshop on Smart Data Pricing (SDP). IEEE, 2013.
38. 38. O. Dalkilic, O. Candogan, and A. Eryilmaz. Pricing Algorithms for the Day-Ahead Electricity Market with Flexible Consumer Participation. Available at: http://www2.ece.ohio-state.edu/ dalkilio/pricealg2012.pdf, Tech. Rep., 2012 [online]. The Department of Electrical and Computer Engineering, The Ohio State University.
39. 39. N. P. Padhy. “Unit commitment-a bibliographical survey,” IEEE Transactions on Power Systems, 19(2), 2004, 1196–1205.
40. 40. C. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, New York, 1998.
41. 41. D. Acemoglu, O. Candogan, A. Ozdaglar, and P. Parrilo. “Iterative auction design for graphical valuations,” 2012.
42. 42. H. Yu, D. Zheng, B. Y. Zhao, and W. Zheng. Understanding user behavior in large-scale video-on-demand systems. In EuroSys’06, 2006.
43. 43. A. Nag, M. Tornatore, and B. Mukherjee. “Energy-efficient and cost-efficient capacity upgrade in mixed-line-rate optical networks,” IEEE/OSA Journal of Optical Communications and Networking, 4(12), 2012, 1018–1025.
44. 44. Y. Wu, P. A. Chou, and S.-Y. Kung. “Minimum-energy multicast in mobile ad hoc networks using network coding,” IEEE Transactions on Communications, 53(11), 2005, 1906–1918.
45. 45. K. Bicakci, H. Gultekin, and B. Tavli. “The impact of one-time energy costs on network lifetime in wireless sensor networks,” IEEE Communications Letters, 13(12), 2009, 905–907.
46. 46. M. K. Karray. “Analytical evaluation of QoS in the downlink of OFDMA wireless cellular networks serving streaming and elastic traffic,” IEEE Transactions on Wireless Communications, 9(5), 2010, 1799–1807.
47. 47. L. Z. Ribeiro and L. A. DaSilva. “A framework for the dimensioning of broadband mobile networks supporting wireless Internet services,” IEEE Wireless Communications, 9(3), 2002, 6–13.
48. 48. X. Zheng and Y. Cai. Reducing electricity and network cost for online service providers in geographically located internet data centers. In IEEE/ACM International Conference on Green Computing and Communications (GreenCom), 2011, pp. 166–169, 4–5 Aug. 2011.
49. 49. J. Tadrous, A. Eryilmaz, and H. El Gamal. “Proactive resource allocation: harnessing the diversity and multicast gains,” IEEE Transactions on Information Theory, 2013, DOI: 10.1109/TIT.2013.2257911.
50. 50. J. Tadrous, A. Eryilmaz, and H. El Gamal. “Proactive data download and user demand shaping for data networks,” IEEE Transactions on Information, 59(8), 2013, 4833–4854. submitted. Also available on: http://arxiv.org/pdf/1304.5745.pdf.
51. 51. J. Tadrous, A. Eryilmaz, and H. El Gamal. Pricing for demand shaping in proactive data networks. In The 2nd IEEE International Workshop on Smart Data Pricing (SDP), April 2013.
52. 52. J. Tadrous, A. Eryilmaz, and H. El Gamal. Proactive content distribution for dynamically changing content. In Proceedings of 2013 IEEE International Symposium on Information Theory (ISIT), July 2013.
53. 53. J. Tadrous, A. Eryilmaz, and H. El Gamal. Proactive resource allocation in cognitive radio networks. 2011 Conference Record of the Forty Fifth Asilomar Conference on Signals, Systems and Computers (ASILOMAR), pp. 1425–1429, 6–9 Nov. 2011.
54. 54. J. Tadrous, A. Eryilmaz, and H. El Gamal. Proactive multicasting with predictable demands. 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 239–243, July 31 2011-Aug. 5 2011.
55. 55. H. El Gamal, J. Tadrous, and A. Eryilmaz. Proactive resource allocation: Turning predictable behavior into spectral gain. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 427–434, Sept. 29 2010-Oct. 1 2010.
56. 56. Z. Huang, D. Zeng, and H. Chen. “A comparison of collaborative-filtering recommendation algorithms for e-commerce,” IEEE Intelligent Systems, 22(5), 2007, 68–78.
57. 57. T. L. Wickramarathne, K. Premaratne, M. Kubat, and D. T. Jayaweera. “CoFiDS: a belief-theoretic approach for automated collaborative filtering,” IEEE Transactions on Knowledge and Data Engineering, 23(2), 2011, 175–189.
58. 58. J. Salter and N. Antonopoulos. “CinemaScreen recommender agent: combining collaborative and content-based filtering,” IEEE Intelligent Systems, 21(1), 2006, 35–41.
59. 59. L. Kozma, A. Ilin, and T. Raiko. Binary principal component analysis in the Netflix collaborative filtering task. In IEEE International Workshop on Machine Learning for Signal Processing, 2009. MLSP 2009, pp. 1–6, 1–4 Sept. 2009.
60. 60. T. Cover and J. Thomas. Elements of Information Theory. Wiley Interscience, Hoboken NJ, 2006.
61. 61. S. Boyd and L. Vandenberge. Convex Optimization. Cambridge University Press, United Kingdom, Cambrdige, 2004.