1
14 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

1

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
14 Pages
English

Description

1 Incentive Mechanisms for Internet Congestion Management: Fixed-Budget Rebate versus Time-of-Day Pricing Patrick Loiseau, Member, IEEE, Galina Schwartz, Member, IEEE, John Musacchio, Saurabh Amin and S. Shankar Sastry, Fellow, IEEE, Abstract—Mobile data traffic has been steadily rising in the pricing, many ISPs are now interested in moving to tiered past years. This has generated a significant interest in the deploy- pricing schemes [2], [3]. However, experiments have shown ment of incentive mechanisms to reduce peak-time congestion. that users prefer flat-rate pricing, and will pay a premium Typically, the design of these mechanisms requires information to avoid being metered [4], [5]. This makes the adoption ofabout user demand and sensitivity to prices. Such information real-time pricing particularly challenging. Thus, novel pricingis naturally imperfect. In this paper, we propose a fixed-budget rebate mechanism that gives each user a reward proportional mechanisms that balance the conflict between the need for to his percentage contribution to the aggregate reduction in network decongestion and the users’ preference for flat prices peak time demand. For comparison, we also study a time-of- are of great practical interest. day pricing mechanism that gives each user a fixed reward per Network bandwidth (and hence the level of congestion) isunit reduction of his peak-time demand.

Informations

Published by
Published 03 June 2013
Reads 4
Language English

Exrait

1
Incentive Mechanisms for Internet Congestion Management:
Fixed-Budget Rebate versus Time-of-Day Pricing
Patrick Loiseau, Member, IEEE, Galina Schwartz, Member, IEEE, John Musacchio, Saurabh Amin and S. Shankar
Sastry, Fellow, IEEE,
Abstract—Mobile data traffic has been steadily rising in the pricing, many ISPs are now interested in moving to tiered
past years. This has generated a significant interest in the deploy- pricing schemes [2], [3]. However, experiments have shown
ment of incentive mechanisms to reduce peak-time congestion. that users prefer flat-rate pricing, and will pay a premium
Typically, the design of these mechanisms requires information
to avoid being metered [4], [5]. This makes the adoption ofabout user demand and sensitivity to prices. Such information
real-time pricing particularly challenging. Thus, novel pricingis naturally imperfect. In this paper, we propose a fixed-budget
rebate mechanism that gives each user a reward proportional mechanisms that balance the conflict between the need for
to his percentage contribution to the aggregate reduction in network decongestion and the users’ preference for flat prices
peak time demand. For comparison, we also study a time-of- are of great practical interest.
day pricing mechanism that gives each user a fixed reward per
Network bandwidth (and hence the level of congestion) isunit reduction of his peak-time demand. To evaluate the two
not uniform during the course of a day; it drops at nightmechanisms, we introduce a game-theoretic model that captures
the public good nature of decongestion. For each mechanism, after the prime time evening hours. This variability in demand
we demonstrate that the socially optimal level of decongestion is can be exploited to design variable pricing mechanisms. For
achievable for a specific choice of the mechanism’s parameter. We instance, time-of-day pricing mechanisms have been designed
then investigate how imperfect information about user demand
to incentivize users to shift a part of their demand to theaffects the mechanisms’ effectiveness. From our results, the fixed-
off-peak times [6], [7]. However, such mechanisms typicallybudget rebate pricing is more robust when the users’ sensitivity
to congestion is “sufficiently” convex. This feature of the fixed- require information about user demand; in particular, the
budget rebate mechanism is attractive for many situations of knowledge of user preferences about shifting their demand
interest and is driven by its closed-loop property, i.e., the unit from peak to off-peak times. In practice, this information may
reward decreases as the peak-time demand decreases.
be inaccurate or just too difficult to obtain due to privacy
Index Terms—congestion pricing; lottery-based incentive concerns [7]. Thus, robustness to imperfect information about
mechanisms; public good provisioning; probabilistic pricing user preferences must be taken into account in the design of
any practically viable mechanism.
Recently, a fixed-budget rebate mechanism (termed “raffle-I. INTRODUCTION
based scheme”) was proposed for decongestion of a shared
The consumer demand for network bandwidth is steadily
resource [8]. Decongestion is viewed as a public good: when
growing. For instance, mobile data traffic nearly tripled during
a user reduces/shifts his demand away from peak times, his
each of the past three years due to increasing penetration of
contribution benefits all the users sharing the resource. The
mobile devices such as smartphones [1]. Numerous studies
fixed-budget rebate mechanism in [8] is inspired by economic
indicate that this growth will continue as bandwidth intensive
ideas on incentivizing contributions to provision of public
applications like video streaming continue to gain popular-
goods [9]. In this mechanism, each user is entitled a reward
ity [2]. The growing demand for bandwidth forces the Internet
proportional to his percentage contribution to the total demand
Service Providers (ISPs) to adopt congestion management
reduction. An attractive feature of this mechanism is that, in
schemes, including capacity expansion and pricing mech-
practice, it can be implemented via a lottery scheme, where
anisms. Although the ISPs have historically used flat-rate
each participating user wins a prize with a probability equal
to the fraction he contributed to the total demand reduction.Patrick Loiseau is with EURECOM, Sophia-Antipolis, France. E-mail:
patrick.loiseau@eurecom.fr. Part of this work was done while he In this article, we investigate the fixed-budget rebate mech-
was at UC Santa Cruz, CA, USA. anism, and compare it with the more traditional time-of-
Galina A. Schwartz and S. Shankar Sastry are with the department of
day pricing mechanism for reducing Internet congestion. InElectrical Engineering and Computer Science, UC Berkeley, CA, USA. E-
mails: {schwartz, sastry}@eecs.berkeley.edu Sec. III, we introduce a game-theoretic model with a contin-
John Musacchio is with the Technology and Information Management uum of non-atomic users. Each user chooses his peak time
program, UC Santa Cruz, CA, USA. E-mail: johnm@soe.ucsc.edu
and off-peak time demand to maximize his utility. The userSaurabh Amin is with the department of Civil and Environmental Engi-
neering, MIT, MA, USA. E-mail: amins@mit.edu utility models both his benefit from peak time decongestion,
The authors thank the editor and the anonymous referees for their thorough and his willingness to reduce/shift away from the peak time
reviews which lead to significant improvements of the paper.
period. The model allows us to compute the user equilibriumThis research was supported by NSF grant CNS-0910711 and by TRUST
(Team for Research in Ubiquitous Secure Technology), which receives support welfare for both mechanisms: fixed-budget rebate and time-
from the NSF (#CCF-0424422) and the following organizations: AFOSR of-day pricing. We compare their sensitivity to information
(#FA9550-06-1-0244), BT, Cisco, DoCoMo USA Labs, EADS, ESCHER,
imperfections for the case when an ISP with imperfect infor-HP, IBM, iCAST, Intel, Microsoft, ORNL, Pirelli, Qualcomm, Sun, Symantec,
TCS, Telecom Italia, and United Technologies. mation about user demand chooses the mechanism parameters.
arXiv:1305.6971v1 [cs.NI] 29 May 20132
Our results in Sec. IV can be summarized as follows: A few papers have proposed mechanisms with prices depen-
(i) For any given parameters, for each mechanism, a Nash dent on congestion levels. In [20], Paschalidis and Tsitsiklis
equilibrium exists, and it is unique. propose a congestion-based pricing mechanism in the context
of loss networks (i.e., phone). They provide a dynamic pro-(ii) For the case when ISP has perfect information about
gramming formulation of the revenue maximization problemuser demand, for each mechanism, the ISP can choose
and of the welfare maximization problem. Then, they showthe mechanism parameter to achieve the socially optimal
that this dynamic congestion pricing mechanism can be welllevel of decongestion.
approximated by a simpler static time-of-day pricing. An(iii) For the case when ISP has imperfect information about
alternative mechanism called “Trade & Cap”, was recentlyuser preferences, the fixed-budget rebate mechanism is
proposed by Londoño, Bestavros and Laoutaris [21]. It worksmore robust to the time-of-day pricing mechanism a un-
in two phases. First, users engage in a trading game whereder mild condition on the users’ sensitivity to congestion.
they choose an amount of reserved bandwidth slots to buyOur analysis reveals several desirable features of fixed-
for hard-constraints traffic. In the second phase, the remainingbudget rebate mechanism. First, the condition under which it
bandwidth is allocated to users as fluid bandwidth, in pro-is more robust than the time-of-day-pricing can be interpreted
portion of their remaining “buying power”. They show thatas “convex” user sensitivity to congestion (or delay). This
this mechanism smoothes the aggregate demand to a certaincondition is expected to be predominant, especially for today’s
level. In their model, users have a cost function that increasesInternet which supports highly delay-sensitive applications.
linearly with the total demand in a given slot. In this paper,This robustness of the fixed-budget rebate mechanism is driven
we consider simpler one-phase pricing mechanisms with fixedby its closed-loop property: as the aggregate demand shifts
parameters. Our model also differ from these papers in thataway from peak time period, the user reward for his per unit
users have elastic demand and their utility is an arbitrarycontribution decreases. Finally, if an ISP decides to implement
function of the congestion level.the fixed budget rebate mechanism, he knows the total reward
Two recent papers analyze time-of-day pricing mechanisms(or rebate) that he owes to the users even when the information
over n time slots [6], [7]. In [6], Jiang, Parekh and Walrandabout user demand characteristics is imperfect. In contrast,
consider a model where users have unit demand. Each userunder the time-of-day pricing mechanism, the ISP will have
chooses one time-slot in which he transmits its entire demand,to design the mechanism based on an estimate of the total
to maximize his utility. The authors of [6] obtain a bound onexpected reward that he will owe to the users.
the price of anarchy due to users selfishness. In [7], Wong, HaThe rest of the paper is organized as follows. Sec. II
and Chiang consider a model with users transmitting sessionsdiscusses the related literature. We introduce the model in
of random length. Sessions arrive as a Poisson process andSec. III. In Sec. IV, we analyze the two incentive mechanisms
each session is characterized by a waiting function which(Nash equilibrium and social optimum) and compare them in
reflects the willingness of the user to delay his entire sessionterms of robustness to imperfect information. We conclude in
for a given time, in exchange for a reward given by theSec. V. Proofs are relegated to Appendices.
provider. The authors show how to compute the optimal reward
II. RELATED WORK levels in order to maximize the provider profit by balancing
Many pricing mechanisms have been proposed to manage the congestion cost due to demand exceeding capacity and
quality of services (QoS) in networks, see e.g., surveys [10], the reward amount. Further analysis of this mechanism called
[11], [12]. For instance, in [13], Honig and Steiglitz propose a “TUBE”, as well as implementation are provided in [22].
usage-based pricing mechanism, and analyze it using a model However, in their model, users are only sensitive to prices (the
with delay-sensitive users. Their results show how to find effect of congestion on the user utility is not considered) and
the price that maximizes the provider’s revenue by solving the analysis is not game-theoretic. In this paper, we consider
a fixed-point equation. A similar model is used in [14] where a model with two time slots (peak and off-peak). We provide
Bas¸ar and Srikant analyze the many-users limit. They show a game-theoretic analysis. In our model, user utility functions
that, as the number of users increases, the provider’s revenue are the closest to [6] where user cost due to latency is an
per unit of bandwidth increases and conclude that this gives arbitrary (convex) function of the load. However, our setup
providers an incentive to increase their network capacity. In a differs from [6], as each user in our model can shift an arbitrary
number of papers, e.g., [15], [16], [17], pricing mechanisms continuous fraction of his demand from peak time to off-peak
based on multiple classes of customers with different priorities time.
are proposed and analyzed in terms of equilibrium achieved In this paper, we show that the problem of decongesting the
and optimal price per class. In [18], [19], Shen and Bas¸ar peak time can be seen as a public good provision problem.
investigate the performance of non-linear pricing in a model Our model is closely related to the “raffle-based” incentive
similar to [14] and find an improvement of up to 38% over lin- mechanism, which has been recently proposed by Loiseau,
ear pricing in some cases. However, in all the aforementioned Schwartz, Musacchio, Amin and Sastry [8]. That work was
papers, the demand is assumed stationary and the price is fixed inspired by Morgan, who in [9] pioneered the investigation
independently of the instantaneous network congestion or of of using the lotteries for public good provision. The public
the time of the day. In contrast, in this paper, we investigate good perspective has been applied in recent works by Sharma
linear pricing mechanisms that leverage the time variability of and Teneketzis [23], [24] in the context of optimal power
user demand using a single priority class. allocation for wireless networks. The connection of lottery-3
based mechanism with public good provision was originally where the notation y and z is standard: it denotes peak-−θ −θ
noted in [9] and received an extensive attention in economic time and off-peak-time demand choices for all user types but
literature (see [25]). The idea of lotteries has also been used θ. In (1), P (·) and O (·) are the utilities that a user of typeθ θ
in different contexts. For instance, lottery scheduling is a θ ∈ Θ gets for his demand in the peak time and off-peak
widely applied technique in resource scheduling in computer time respectively. L (·) and L (·) are the disutilities due top o
operating systems [26]. Recent interest in the application of congestion in the peak time and off-peak time respectively.
lotteries to congestion management was facilitated by Merugu, These disutilities are per unit of demand, hence they are
Prabhakar and Rama who demonstrated with a field study that multiplied by the demand in each time. Finally, quantityq≥ 0
lottery-based mechanisms can be effectively used to reduce is a fixed usage-based price (which could be zero) and quantity
congestion in transportation systems [27]. In contrast, our p> 0 is a fixed monthly subscription price.
contributions are methodological. We use a game-theoretic We assume that utilities P (·) and O (·) are twiceθ θ
model to analytically study the performance of a lottery-like differentiable increasing strictly concave functions of the
mechanism and compare it to a more standard time-of-day demand. We assume that there is a fixed maximum peak-time
pricing mechanism. demand d (per day) that could correspond for instance to ap
subscription daily peak cap, that could be a maximum usable
III. MODEL demand (determined by technology limitation), or that could
Let us consider a shared Internet access point with capacity be a maximum daily demand determined from empirical
C. Based on the usage patterns, let the day be divided into two data. For simplicity, we assume that this maximum peak-time
time periods: a peak time of durationT and an off-peak time demand is the same for each user, but more general casesp
2of duration T . We assume that each time period corresponds could be handled easily (in that case, user-dependent priceso
to a stationary regime with respective loads ρ and ρ . could also easily be handled). Each user can choose to shiftp o
An access point is typically shared by a finite number of to off-peak time, or to simply not use, part of his maximum
users, each having his own preference for time periods which peak-time demand. Additionally to the shifted peak-time
we model by user type (the type of a user will typically depend demand, each user could have an initial off-peak-time
on the applications that he uses). To account for a large number demand. However, this additional demand does not modify
our analysis as long as the peak time remains more congestedof users, we model the set of users as a continuum of non-
than the off-peak time. For simplicity, we assume that theatomic users; i.e., each user contributes a negligible fraction
initial off-peak-time demand is zero, i.e., the off-peak-timeof the total demand. We use the measure-theoretic framework
similar to [28], [29]. Let (Θ,F) be a measurable space where demand only corresponds to shifted peak-time demand. Then,
Θ is the set of user types. We assume that the user types are we have the following constraint on the demands:
1distributed according to a finite measure µ on (Θ,F) . While y +z ≤d , (θ∈ Θ). (2)θ θ p
simpler modeling assumptions can be used (e.g., considering
We assume that disutilities L (·) and L (·) are increasingp oonly two types), using an arbitrary measure of typesµ gives a
strictly convex functions of the aggregate demand in eachhigher flexibility that can be interesting to fit real populations.
time (a similar assumption is made, e.g., by Jiang, Parekh andNote that for simplicity, we describe the population at the
Walrand [6]). This assumption is realistic and quite general. Asgranularity of types instead of users as in [28], [29]. This
an example, let us focus on the average delay δ as a measureis justified by the strict concavity of the user utilities (see
of the network quality, as in Honig and Steiglitz [13]. Ourassumptions below) which implies that at Nash equilibrium,
assumption holds if (i) the disutility is an increasing convexall users of the same type choose the same action. As a
function of the average delay and (ii) the average delay is anconsequence, although we do require that the measure of users
increasing strictly convex function of the aggregate demand oris non-atomic (as for any non-atomic game), we do not require
equivalently of the load in the corresponding time:Z Zthat the measure of typesµ itself is non-atomic. For instance, if
−1 −1all users have the same type, measureµ is only constituted by ρ = (CT ) y dµ(θ), ρ = (CT ) z dµ(θ).p p θ o o θ
Θ Θone atom. Yet, each user of each type remains infinitesimally
Assumption (i) is natural: an increase of the delay from zerosmall, which means that the action of one user does not affect
to half a second creates no more disutility than from halfthe aggregate outcome.
a second to one second. This assumption is also made in
A. User utility [13]. Assumption (ii) holds for the vast majority of queueing
models considered in the literature. For example, it holds forEach user of type θ∈ Θ chooses his peak-time demand yθ
the processor sharing queue (the most classical model for 3Gand his off-peak time demand z to maximize his utilityθ
Z and 4G networks [30]), for which the average delay is
δ0u (y ,z ,y ,z )=P (y )+O (z )−y L y dµ(θ)θ θ θ −θ −θ θ θ θ θ θ p θ δ(ρ ) = , (3)p
Θ 1−ρpZ
2If users differ by their maximum peak-time demand, each user could be−z L z dµ(θ) −(y +z )q−p, (1)θ o θ θ θ
viewed as an appropriate number of users with identical maximum peak-Θ
time demand. The proposed model still applies with measure µ defined forR
1Throughout the paper, we assume that all functions of θ are measurable. all subset Θ ∈ F by µ(Θ ) = d· ν(Θ , dd) where Δ is the set of1 1 1Δ
In [28], Aumann notes that “the measurability assumption is of technical maximum peak-time demands and measure ν on Θ×Δ represents the joint
significance only and constitutes no real economic restriction.” distribution of types and demand.4
where δ is a constant. It also holds for common models assumption (4), the utility (1) of a user of type θ ∈ Θ can0
of wired networks such as the M/D/1 model considered in be re-written as Z
[13] and the M/M/1 model considered by Shen and Bas¸ar u (y ,z ,y ) =P (y )−y ·L y dµ(θ) −y ·qθ θ θ −θ θ θ θ p θ θ
[18], [19]. Finally, we assume that despite the effect of users Θ
shifting part of their demand, the off-peak time remains +O (z )−z ·q−p. (7)θ θ θ
relatively uncongested so that Z Since we are interested in the reduction of peak time demand,
L z dµ(θ) ≃ 0. (4) we define the difference between the maximum peak-timeo θ
Θ demand and the chosen peak-time demand:
This assumption is not strictly necessary but greatly simplifies
x =d −y , (θ∈ Θ). (8)θ p θthe presentation without affecting the important effects that we
3 This peak-time demand reduction includes both the unusedconsider in this model .
peak-time demand and the peak-time demand shifted to off-For numerical illustrations of our model, we use the follow-
peak time. For a given x ∈ [0,d ], we define the optimalθ ping example of an Internet access point.
shifted demand:
Example 1 (Internet access point). The capacity is C = ∗
z (x ) = argmax[O (z )−z q], (θ∈ Θ).θ θ θ θθ
1 Gbps. Peak-time lasts T = 2 h (e.g., 6pm to 8pm), hencep z ∈[0,x ]θ θ
T = 22 h. Θ = [0,1] with a uniform distribution of typeso A user of type θ∈ Θ maximizing his utility (7) will choose a
3 ∗ 4µ(dθ) = D /d · dθ, where D = 7.2·10 Gbits and d =p p p p couple (x ,z ) such that z = z (x ). As we are interestedθ θ θ θθ
7.2 Gbits (which corresponds to 1,000 users with peak-time in the reduction of congestion at peak-time, we restrict our
capacity 1 Mbps). The latency disutility is L (ρ ) =L δ(ρ )p p 0 p attention to the choice of x . Note that if q = 0, thenθ
∗where δ(ρ ) is given by the PS model (3) and L = 0.065.p 0 z (x ) = x . Indeed, if there is no usage-based cost, off-θ θ
Peak-time utility is P (x ) = (1 +θ)P log(1 +x/d ) withθ θ 0 p peak-time demand always gives higher utility than 0.
P = 130 and off-peak time utility is O = 1/10·P (·). The0 θ θ In the absence of latency, the maximal utility of a user is
subscription price is p = $50 and the usage-base price is zero. ∗ ∗u¯ =P (d −x )−(d −x )q+O (z (x ))−z (x )q, (9)θ θ p p θθ θ θ θ θ θ
for all θ∈ Θ, wherenB. User type distribution
x = argmax P (d −x )−(d −x )qθ p θ p θθOn the timescale of a day, the population is heterogeneous x ∈[0,d ]θ p o
∗ ∗with user types distributed according to measure µ. However, +O (z (x ))−z (x )q , (θ∈ Θ),θ θ θθ θ
we assume that each user has a type that varies randomly
is the baseline peak-time demand reduction which maximizesacross the days of a month, with the same distribution µ.
the latency-free utility. Latency and incentive mechanisms willTherefore, the population is homogeneous in average on the
only result in users using less of their peak-time demand, i.e.,timescale of a month. In particular, with this assumption, the
increasing their choice of x beyond x . Then, we define theθexpected utility of each user on the timescale of a month θ
cost of shifting as the loss of utility incurred by a user whenequals the daily aggregate welfareZ
reducing his peak-time demand:hW = u dµ(θ) (5)θ
c (x ) =u¯ − P (d −x )−(d −x )q (10)Θ θ θ θ θ p θ p θnormalized by µ(Θ).
i
Each user will buy a monthly contract (with subscription ∗ ∗+O (z (x ))−z (x )q , (θ∈ Θ).θ θ θθ θ
price p) to use the service if his expected utility over the
month is positive, i.e., here if (Note that with a slight abuse of terminology, we call c (x )θ θ
W > 0. (6) the cost of shifting whereas the peak-time demand reduction
We assume that without any incentive mechanism, this x can actually correspond to shifted demand and/or to unusedθ
condition is satisfied. Then, our assumption guarantees that demand.) The definition of the baseline (9) guarantees that
with any welfare-improving incentive, each user will continue c (x ) is always positive. Moreover, with our assumptionsθ θ
to participate, i.e., to buy the monthly contract. on functions P (·) and O (·), the cost of shifting c (·) isθ θ θ
Note that if the population cannot be assumed homogeneous differentiable and strictly convex on [0,d ]; and increasingp
at the timescale of a month, it is possible to divide it into on [x ,d ] (see details in Appendix A). Finally, to simplifypθ
subpopulations that can be assumed homogeneous and to apply the proofs, we assume that the marginal cost of shifting is
our incentive mechanisms to each of these subpopulations. bounded by a constant independent of θ.
We view the aggregate peak-time demand reductionZ
C. Model reduction to one-dimensional strategy space G = x dµ(θ) (11)θ
ΘBefore introducing the incentive mechanisms, we show
as a public good to which each user contributes by his choicethat our model can be reduced to a one-dimensional strategy
of x . Indeed, when a user reduces his peak-time demand, theθspace focusing on the peak-time demand reduction. With
benefits of reduced peak-time congestion is shared by all the
3If one wants to consider a non-zero off-peak-time disutility, this assump- users. We define the function
tion could be replaced by the relaxed assumption that when the aggregate
4shifted demand increases, the marginal peak-time disutility reduction is higher A function (x ,z ) corresponding to social welfare maximization also· ·
∗than the marginal off-peak-time disutility increase. satisfies z =z (x ) for all θ∈Θ.θ θθ5
h(G) =−L (D −G), (12) lottery where each user wins the prize R with a probabilityp p
equal to his percentage contribution to the total amount ofwhere D = d µ(Θ) is the aggregate maximum peak-timep p
peak-time demand reduction. In this case, (14) and (15) woulddemand. Function h(·) reflects the notion of how much users
correspond to expected utilities. Other implementations (e.g.,benefit from the network decongestion at peak-time. With our
deterministic) are also possible. To complete the definitionassumptions on L (·), h(·) is an increasing concave functionp R of the fixed-budget rebate mechanism, we assume that if noof the public good level G. The term−y L y dµ(θ) =θ p θΘ
user reduces his peak-time demand then the reward is not(d −x )h(G) in (7) has the interpretation that the benefit ap θ
given. However, if the set of users who reduce their peak-user gets from the peak-time decongestion is the product of his
time demand is nonempty but of measure zero, then eachpeak-time demand(d −x ) times the benefit per unit demandp θ
contributing user receives an infinite reward given in such ah(G). Notice that h(G) is negative, but its most important
way that the integral w.r.t. the measure of users is R. This is acharacteristic is that it is increasing in G, i.e., the disutility
technical assumption for the measure-theoretic setting of thedue to congestion reduces when G increases.
non-atomic game. In practice, it reflects the fact that if only aIn summary, in view of (7)-(12), our peak-time decongestion
finite number of users contribute, their expected reward relativemodel reduces to a public good provision problem similar to
to their fraction of the total demand grows to infinity as the[8]: the utility of a user of type θ∈ Θ is
total number of users goes to infinity.
u (x ,G) =u¯ +(d −x )h(G)−c (x )−p, (13)θ θ θ p θ θ θ We notice here that the fixed-budget rebate mechanism
where h(·) corresponds to the (unit) benefit from the public introduces uncertainty in the users bill as the reward depends
good and c (·) corresponds to the cost of contribution. Fromθ on the amount shifted by the other users. However, this
our assumptions, these functions satisfy: uncertainty is only one-sided: the maximum bill is known and
only the reward amount is uncertain. This asymmetry is crucial(A1) h(·) is twice differentiable, strictly concave and increasing
to ensure good adoption of the mechanism.on [0,D ];p
The time-of-day pricing mechanism corresponds to a fixed(A2) c (·) is positive, differentiable and strictly convex onθ
reward per unit of shifted demand:[0,d ]; and increasing on [x ,d ], (θ∈ Θ);p pθ
′ T(A3) sup c (d )<∞, (θ∈ Θ).pθ∈Θ θ M (x ,G) =r·x −Δp , [time-of-day pricing] (16)θ θ T
Notice that in our model, h(·) does not depend on the type. wherer is a parameter of the mechanism chosen ex-anti by the
All the type-dependency is carried by the cost of shifting. This provider. This mechanism is a variation of a conventional time-
modeling choice ensures tractability of the equilibrium. of-day pricing mechanism, with an off-peak price subsidy. Its
implementation is straightforward.
D. Incentive mechanisms In (15) and (16), Δp denotes the increase in the subscrip-j
tion price that the service provider imposes to finance theIndividual users maximize their own utility (13), which
(eq)reward mechanism. LetG be the equilibrium level of publicdiffers from maximizing (5). Thus, in general, the level of
good (in the next section, we show that the Nash equilibriumpublic good and the aggregate user welfare achieved in the
is unique for both mechanism). We assume that the price Δpindividual maximization and in the social optimum differ. j
is fixed in advance by the service provider to compensate theTo align Nash equilibrium and social optimum objectives, R
j (eq)reward, i.e., such that M (x ,G )dµ(θ) = 0 (note thatthe service provider can design mechanisms to incentivize θΘ
the expression of the aggregate welfare (5) is thus not directlyusers to reduce their peak-time demand. In this paper, we
modified by the mechanisms, but only through the chosencompare two different incentive mechanisms: a fixed-budget
5contributions x ) . Then,rebate mechanism (denoted R or FBR) and a time-of-day θ
d dp ppricing mechanism (denoted T or TDP). Each mechanism (eq)Δp =R· and Δp =rG · . (17)R T
D Dintroduces a reward based on the peak-time demand reduction p p
From (17), we immediately see that the service provider hasx below the maximumd . For the service provider to financeθ p
to know the equilibrium to determine the price Δp for theTthe respective reward, each mechanism also introduces an
time-of-day pricing mechanism. An error in the estimationincrease in the subscription price. However, as we will see
(eq)of G could have important consequences. In contrast,(Corollary 1), each user’s net utility can be improved even
such knowledge is not necessary for the fixed-budget rebatewith this price increase. With mechanism j ∈ {R,T}, the
mechanism where Δp only depends on the parameter RRuser utility becomes
j j chosen by the service provider.u (x ,G) =u (x ,G)+M (x ,G), (θ∈ Θ). (14)θ θ θ θθ
The marginal utility with mechanism j ∈{R,T} is
The fixed-budget rebate mechanism consists in giving each j
∂u ′′ jθuser a reward proportional to his fraction of the total contri- =−h(G)−c (x )+M (G), (θ∈ Θ), (18)θθ∂xθbution, i.e., of the functional form:
wherexθR RM (x ,G) =R· −Δp , [fixed-budget rebate] (15) ′ ′θ R R TM (G) = and M (G) =r. (19)G
Gwhere R is a parameter of the mechanism chosen ex-anti
5If users have different maximum peak-time demand for which they areby the provider. In practice, this mechanism could be imple-
charged different subscription prices, it is also possible to impose a type-
mented via randomization. For example, with a finite number dependent price increase Δp which compensate the reward, i.e., such thatθR
j (eq)of users, it could be implemented by the simplest type of M (x ,G )dµ(θ) = 0 is still satisfied.θΘ6
′ 7000Notice that in (18), there is no h (G) term corresponding to G
(resp)G (FBR)the variation of the aggregate due to the variation of a user’s
6000 (resp)G (TDP)decision. This is because, in the non-atomic game, users are
negligible and do not account for the variation of G induced 5000
by their action when taking their decision. In (18) and in all
4000
future occasions, we abuse notation by denoting with a partial
derivative w.r.t. x the marginal quantities corresponding to 3000θ
variations following the variation of a user’s action.
′ 2000jFor both mechanisms, the marginal rewardM is indepen-
dent of the individual contributionx . Due to the term−h(G) 1000θ
in (18), the marginal utility decreases when G increases.
0
Intuitively, if the congestion is lower at peak time, a user would 0 2000 4000 6000
want to use it more. Hence he would want to reduce less his G
peak-time demand. This decrease of the marginal utility is Fig. 1. Illustration of the fixed-point equation (21) for Example 1. The′Raccentuated by the term M (G) = R/G in the case of the dashdotted line corresponds to the amount G that users shifts (r.h.s. of (21)).
(resp)The dashed and solid lines correspond to the aggregate amount G thatfixed-budget reward mechanism.
users would want to shift (l.h.s. of (21)) givenG has been shifted for the fixed-
budget rebate and time-of-day pricing mechanisms respectively. To obtain
(eq) ∗IV. ANALYSIS G = G = 78,000, parameters were set to R = $5,500 and r =
$9/Gbit. The corresponding subscription price increase is $5.5.6In this section, we show that, for each mechanism, there
Intuitively, for a given level of public good G, eachexists a unique Nash equilibrium. Then, we show that for
user of type θ ∈ Θ chooses his best response contributionappropriate values of the mechanisms parameters, they achieve
(resp)
x (G) ∈ [0,d ] to maximize his utility. Then, integratingpsocial optimum and that for a wide range of parameters, θ
the contribution of each type gives the amount of public goodboth mechanisms are welfare improving. Finally, we compare
(resp)G (G) that users want to provide in response to a givenG.the two mechanisms based on their sensitivity to imperfect
An equilibrium occurs when both quantities are equal, whichinformation about the user utilities.
corresponds to solving the fixed-point equationFor clarity, we will use the following notation:
(resp)Γ (Θ,µ,h,{c } ,R) and Γ (Θ,µ,h,{c } ,r) G (G) =G. (21)R θ θ∈Θ T θ θ∈Θ
are the non-atomic games where users selfishly optimize Fig. 1 illustrates the two terms of the fixed-point equation
their own utility (14) in the fixed-budget rebate mechanism for both mechanisms. As we mentioned, a key feature of our
and in the time-of-day pricing mechanism respectively. We model is that the higher the level of public goodG is (i.e., the
(eq)denote with the superscript the quantities at equilibrium lower peak-time congestion is), the fewer users are willing
in both games and we explicitly write their dependence on r to reduce their peak-time demand (the marginal utility (18)
and R or on other parameters whenever necessary to avoid is decreasing in G). Therefore the aggregate best response
∗ (resp)ambiguity. Similarly, we denote with the superscript the G (G) decrease when G increases and this decrease is
social optimum quantities corresponding to the maximization faster for the fixed-budget rebate mechanism for which the
(resp)of (5), and denote explicitly their dependence on parameters marginal utility decreases faster. Moreover, G (G) is con-
whenever necessary. tinuous, which leads to a unique fixed point. The continuity of
(resp)G (G) is due to assumption (A2) (a linear cost of shifting
could induce discontinuities where a slight modification of GA. Nash equilibrium existence and uniqueness
would make some users switch from not reducing their peak-We define a Nash equilibrium of the non-atomic game Γj
time demand to reducing it by d ).(eq) p(j ∈ {R,T}) as a function x : Θ → [0,d ] such that forp
j (eq) j (eq) (eq)
all θ ∈ Θ, u (x ,x )≤ u (x ,x ),∀x ∈ [0,d ]. Dueθ θ pθ −θ θ θ −θ B. Social optimum
j (eq)to the strict concavity of the utility u , it is equivalent to xθ We now show that the social optimum is unique and
satisfying the first-order conditions (FOCs) coincides with the Nash equilibrium of both mechanisms for
≤ 0, ∀θ : x = 0,j  θ ∗ ∗∂u parameters R and r given in the next theorem.θ = 0, ∀θ : x ∈ (0,d ), (20)θ p
∂x θ ≥ 0, ∀θ : x =d , Theorem 2. The following characterizes the social optimum:θ p
j∂u ∗θ (i) There exists a function x , uniquely determined almost-where is given by (18), and satisfying (11).∂xθ
everywhere, which maximizes the aggregate welfare (5).The first theorem establishes existence and uniqueness of
(ii) For the fixed-budget rebate mechanism, we havethe Nash equilibrium for both incentive mechanisms.
(eq) ∗x (R) = x almost-everywhere (and hence
Theorem 1. For the fixed-budget rebate mechanism, for any (eq) ∗ ∗G (R) =G ) for R =R , where
(eq)R≥ 0, there exists a unique Nash equilibrium x (R). ∗ ∗ ′ ∗ ∗R =G h (G )(D−G ). (22a)
The same result holds for the time-of-day pricing mecha-
nism, for any r≥ 0. The same result holds for the time-of-day pricing mech-
∗anism for r =r , where
6Some of the first results of this section appeared in [8] for the fixed-budget
∗ ′ ∗ ∗
rebate mechanism. They are extended here to handle both mechanisms. r =h (G )(D−G ). (22b)
(resp)
G,G7
TABLE I
such a large reward will not happen in practice, neverthelessEFFECT OF THE INCENTIVE MECHANISMS ON CONGESTION FOR
EXAMPLE 1 (CF. FIG. 1). THE RIGHT COLUMN CORRESPOND TO ANY OF we include it here for completeness of the model analysis.

THE TWO MECHANISM WITH ITS OPTIMAL PARAMETERSR = $5,500 Proposition 1 implies that for large enough parameters, the∗
ANDr =$9/GBIT (I.E., TO SOCIAL OPTIMUM).
equilibrium level of public good will be positive. Let us define,
incentive mechanism
for the fixed-budget rebate mechanism, R as the smallestno incentive mechanism with optimal parameter
(eq)(= social optimum) parameter value such that G (R) > 0 for R > R; and
G 55 Gbits 565 Gbits similarly r for the time-of-day pricing mechanism. Then we
W 28,000 78,000
have the following result characterizing these thresholds.
ρ 0.99 0.92p
δ(ρ ) 130 s 12 sp Proposition 2. For the fixed-budget rebate mechanism, R =
ρ 0.092 0.098 (eq)o 0, i.e., G (R) > 0 for any R > 0 (if the participation
δ(ρ ) 1.10 s 1.11 so
constraint (6) is not imposed).
For the time-of-day pricing mechanism, r≥ 0.
Intuitively, this result holds because the externality faced
′j The intuition behind Proposition 2 is as follows. For theby a user (−h(G)+M ) in the game corresponding to any
fixed-budget rebate mechanism, for any R > 0, the marginalmechanism is independent of his type. Therefore, by fixing a
reward is infinite at G = 0. All users want to contribute hencereward that is also independent of the type, it is possible to
this is not an equilibrium. In contrast, for the time-of-dayachieve social optimum (similarly to a Pigovian tax [31]).
pricing mechanism, the marginal reward is constant. If it isFor Example 1, Tab. I illustrates the effect of the incentive
small enough so that the marginal utility of almost-all usermechanisms with the optimal parameters of Theorem 2: they
types is non-positive at G = 0, then it is the equilibrium.permit a 180% increase of the aggregate welfare which, in
Note that Proposition 2 holds independently of the value ofour model, also correspond to a 180% increase of the average
∗ ∗G and is consistent with Theorem 2. In particular, if G = 0,utility of each user over the timescale of a month. Peak-time
then social optimum is achieved at Nash equilibrium for thecongestion is significantly decreased: the load is decreased by
∗fixed-budget rebate mechanism only forR =R = 0; whereas7% but the average delay drops by 90%. On the other hand,
social optimum is achieved at Nash equilibrium for the time-off-peak time decongestion is hardly increased.
of-day pricing mechanism for any r smaller than r.
The next proposition describes the evolution of the aggre-
C. Nash equilibrium variation with the mechanism parameters gate welfare with the mechanism parameters.
In this section, we investigate the variation of the equilib- Proposition 3. If the participation constraint (6) is not im-
rium quantities when the mechanism parametersr andR vary. posed, for the fixed-budget rebate mechanism, the equilibrium
For ease of exposition, we first assume that the participation (eq) ∗aggregate welfare W (R) is increasing in [0,R ], decreas-
constraint (6) is not imposed (we will come back to the ∗ ¯ ¯ing in [R ,R] and constant for R≥R.
effect of the participation constraint later in this section, see
For the time-of-day pricing mechanism, the equilibrium
Proposition 4). Then, we have the following results on the (eq)aggregate welfare W (r) is constant on [0,r]. For r ≥ r,
variations of the equilibrium contributions. the same results as for the fixed-budget rebate mechanism hold
by changing R to r everywhere.Proposition 1. If the participation constraint (6) is not im-
posed, for the fixed-budget rebate mechanism, we have:
Proposition 3, illustrated on Fig. 2 shows that the welfare
(eq) (eq)′ ′ ∗(i) For any R > R, x (R ) ≥ x (R) (∀θ ∈ Θ); and is unimodal. If G > 0, it increases to its only maximum atθ θ
(eq) ∗ ∗ ∗ ∗R or r and then decreases. If G = 0 (hence R = 0 andthe inequality is strict if 0<x (R)<d .pθ
∗′ (eq) ′ (eq) r = r), the welfare is maximal at R = 0 or r = 0 (i.e.,(ii) For any R > R, G (R ) ≥ G (R); and the
(eq) with no incentive mechanism) and it only decreases (after ainequality is strict if 0<G (R)<D .p
∗¯ constant phase for the time-of-day pricing mechanism).(iii) There exists a threshold R>R such that, for any R≥
(eq) (eq) 7¯ In extreme cases where the reward parameter is too large,R, x (R) =d for all θ∈ Θ and G (R) =D .p pθ
the equilibrium aggregate welfare may become negative. For
The same results hold for the time-of-day pricing mechanism
instance, consider a case where the usage-based price q is
by changing R to r everywhere.
so high compared to the off-peak time utility O (·) that allθ
Intuitively, since the marginal utility (18) increases with the users have zero off-peak time demand. If the reward is larger
¯reward parameters, the equilibrium contributions of each user than R or r¯, then users would not use the service at all and
increases (result (i)); and similarly for the equilibrium level the aggregate welfare would be−pµ(Θ)< 0. In that case, the
of public good (result (ii)). The existence of the thresholds participation constraint is not satisfied, hence users will simply
¯R and r¯ (result (iii)) is a consequence of assumption (A3) not buy the service. The next proposition, which is easily
which means that reducing even the last bit of his peak-time derived using the monotonicity of Proposition 3, describes
demand implies a finite marginal cost for the user, which can how the previous results are changed when introducing the
be compensated by a large-enough reward. Clearly, a case with participation constraint.
7 Proposition 4. If the participation constraint (6) is imposed,¯To avoid ambiguity on the definition of the thresholds r¯,R, we assume
that they are the smallest possible such thresholds. for the fixed-budget rebate mechanism, there exists a threshold8
4∗ x 10R ∈ (R ,∞] such thatmax (a)
(eq)W (R) (FBR)(i) For all R < R , all the users buys the monthly sub-max L
8scription and the results of Proposition 1, Proposition 2
and Proposition 3 hold.
(ii) For allR>R , no user buys the monthly subscription,max 6
hence the welfare is zero.
The same results hold for the time-of-day pricing mechanism
4
by changing R to r everywhere.
The effect of the participation constraint is simple: below a
2
thresholdR orr , all the users participate and above thismax max
threshold, no users participate. This is due to our assumption
that the population is homogeneous at the timescale of a 0

R0 5 10 015month. Since users are offered a monthly subscription, they
∗R∗R/Rwill buy it if they expected utility over the month is positive
4which is equivalent to the aggregate welfare being positive. x 10(b)

(eq)Due to our assumption that the welfare is positive without any W (r) (TDP)T∗incentive mechanism, we have R > R , i.e., the welfaremax 8
∗is positive for any R ≤ R . The threshold R can evenmax
be infinite if the off-peak time utility is high enough and the
6
usage-based price is small enough so that users have positive
utility over the month even without using the peak time.
The last result, which is a direct consequence of the previous 4
results of this section, shows that both mechanisms are welfare
improving for a wide range of parameters.
2
∗Corollary 1. If G > 0, the fixed-budget rebate mechanism
is strictly welfare improving for any parameter R in a range
0∗ (0,R ) where R ∈ (R ,R ]:0 0 max r r0 max0 5 10 15
∗ ∗r r ∗(eq) (eq) r/rW (R)>W (0), ∀R∈ (0,R ).0
Fig. 2. Variation of the equilibrium aggregate welfare with the rewardThe same results hold for the time-of-day pricing mechanism
parameter for Example 1: (a) for the fixed-budget rebate mechanism – (b)
by changing R to r everywhere, and 0 to r¯.
for the time-of-day pricing mechanism.
∗This result is important as it shows that, by implementing Γ (Θ,µ,h,{c } ,r ) correspond to the baseline case ofT θ θ∈Θ
an incentive mechanism with a parameter lying in a wide perfect information considered in the previous sections and
∗ ∗range around an optimal parameter, the provider can increase suppose that R and r have been chosen according to (22)
welfare. Fig. 2 shows that for Example 1, the time-of-day to induce a socially optimal level of public good at equilibrium
∗pricing mechanism with any parameter in (0,2r ) is welfare (eq) ∗ ∗(i.e., G =G ). We assume that G ∈ (0,D ). We analyzep
improving, and the fixed-budget rebate mechanism with any the variations in equilibrium and in social optimum when
∗parameter in (0,14R ) is welfare improving However, a ∗ ∗R and r are maintained for the respective mechanisms and
consequence of Proposition 3 is that both mechanisms can utilities are perturbed (i.e., actual utilities are different from
∗ ∗“overshoot”: if R or r is too large (larger that R or r ), the estimation used by the provider to set the parameters).
(eq) ∗G can be larger than G and the aggregate user welfare is We restrict our analysis to the case where only the cost of
suboptimal. In a competitive environment, a provider would shifting is perturbed and the rest of the utilities is unchanged.
not intentionally choose an overshooting parameter because Indeed, we argue that it is more difficult to obtain data on
it would be a competitive disadvantage as compared to a the time preferences (the willingness to move demand from
provider choosing an optimal parameter. However, if the peak time to off-peak time) than on the total demand or on
provider has imperfect information about user utilities, it may the sensitivity to delay. Therefore, the cost of shifting is more
overshoot unintentionally. Fig. 2 suggests that in this case, the likely to be imperfectly estimated by the provider. We consider
aggregate welfare remains higher for the fixed-budget rebate the following general form of the perturbed cost of shifting:
mechanism than for the time-of-day pricing mechanism. In the
c˜ (·) =c (·)+ǫ·p (·), (23)θ θ θ
next section, we investigate in details the robustness of each
whereǫ is a real number andp : [0,d ]→R is a continuouslyθ pmechanism to imperfect information about user utilities.
differentiable function satisfying
′sup sup |p (x)| <∞.θD. Comparison of the two incentive mechanisms θ∈Θx∈[0,d ]p
In this section, we compare the sensitivity of the Parameterǫ is the perturbation magnitude and functionp (·) isθ
two incentive mechanisms to imperfect information about the direction of the perturbation. For the analysis, we restrict
∗user utilities. Let the games Γ (Θ,µ,h,{c } ,R ) and to small perturbations, i.e.,|ǫ| small. For|ǫ| small enough, theR θ θ∈Θ
(eq) (eq)
W (r) W (R)9
perturbed functions c˜ (·) satisfy assumption (A2-3). We as- r (G) than r (G). It is often the case. The fact that r (G)θ SO T R
sume that the perturbation direction is such that the aggregate decreases whenG increases is the closed-loop effect: the more
best response has a non-zero perturbation at the order one inǫ users reduce their peak-time demand, the lower the incentive
∗at the pointG (the non-perturbed equilibrium). Otherwise, the to reduce it is. However, if r (G) decreases much faster thatR
equilibrium point would not be changed by the perturbation. r (G), r (G) can be closer to r (G). This possibility isSO T SO
For numerical illustrations, we will use the following simple covered by case (ii) of Proposition 5.
perturbation which satisfies the above conditions:p (·) =c (·) Fig. 3 illustrates the result of Proposition 5 with the pertur-θ θ
for all types θ ∈ Θ, i.e., c (·) is scaled by a factor 1 + ǫ bation p (·) =c (·) for all θ∈ Θ. As it turns out, Example 1θ θ θ
independent of the type. (Fig. 3-(a)) falls in case (i) of Proposition 5 (see the unit
(eq) (eq) rewards on Fig. 4); hence the fixed-budget rebate mechanismLet G (ǫ) and G (ǫ) be the equilibrium levelsR T
remains closer to social optimum than the time-of-day pricingof public good in the games with perturbed utilities
∗ ∗ mechanism. This is due to fact that the sensitivity to congestionΓ (Θ,µ,h,{c˜ } ,R ) and Γ (Θ,µ,h,{c˜ } ,r ), re-R θ θ∈Θ T θ θ∈Θ
(eq) (eq) is “strongly convex”, i.e., functionh(·) (12) is far from linear.spectively. Let W (ǫ) and W (ǫ) be the correspondingR T
∗ ∗ Hence, the optimal unit reward (24c) decreases “fast”, as forequilibrium welfares. Let G (ǫ) and W (ǫ) be the socially
the fixed-budget rebate mechanism. For the sole purpose ofoptimal level of public good with perturbed utilities, and the
illustrating numerically case (ii) of Proposition 5, we constructcorresponding welfare resulting from the maximization of (5)
the following example:where c (·) is replaced by c˜ (·). To evaluate the variation ofθ θ
(eq)G with the perturbation, we need to evaluate the variation
Example 2. Everything is defined as in Example 1, but the
(resp) (eq)of the aggregate best response G (recall that G is the
disutility function is artificially contrived to haveh(G) = 1.2·
(resp) ∗fixed-point of G (·), see (21)). (The variation of G is −3 0.95 0.95 −310 · (G −D ). (The factor 1.2· 10 is chosen top
handled similarly since from Theorem 2, the social optimum ∗yield the same social optimum level of public good G than
can also be seen as a Nash equilibrium in a mechanism
in Example 1 when ǫ = 0.)
SO with unit reward given by (24c).) For this purpose, we
Ex. 2 is a contrived example where h(·) is almost linear sointroduce, for each mechanism j ∈ {R,T,SO}, the quantity
(resp) that the optimal unit reward r is almost constant, as in theα equal to the opposite of the slope of G (·) at the SOj
∗ ∗ time-of-day pricing mechanism. As a result, the time-of-daycommon non-perturbed equilibrium point G = G (0) (see
pricing mechanism is closer to social optimum (Fig. 3-(b)).(33)). We define the following conditions: