Description
Abstract—Paris Metro Pricing (PMP) is a simple multi-class
flat-rate pricing scheme already practiced by transport systems,
specifically by the Paris Metro at one time. The name is coined
after Andrew Odlyzko proposed it for the Internet as a simple
way to provide differentiated services. Subsequently, there were
several analytical studies of this promising idea. The central issue
of these studies is whether PMP is viable, namely, whether it
will produce more profit for the service provider, or whether it
will achieve more social welfare. The previous studies considered
similar models, but arrived at different conclusions. In this
paper, we point out that the key is how the users react to
the congestion externality of the underlying system. We derive
sufficient conditions of congestion functions that can guarantee
the viability of PMP, and provide the relevant physical meanings
of these conditions.
1
On the Viability of Paris Metro Pricing for
Communication and Service Networks
Chi-Kin Chau
University of Cambridge
& University College London, UK
[email protected]
Qian Wang
Department of Information Engineering,
The Chinese University of Hong Kong
[email protected]
Dah-Ming Chiu
Department of Information Engineering,
The Chinese University of Hong Kong
[email protected]
Abstract—Paris Metro Pricing (PMP) is a simple multi-class
?at-rate pricing scheme already practiced by transport systems,
speci?cally by the Paris Metro at one time. The name is coined
after Andrew Odlyzko proposed it for the Internet as a simple
way to provide differentiated services. Subsequently, there were
several analytical studies of this promising idea. The central issue
of these studies is whether PMP is viable, namely, whether it
will produce more pro?t for the service provider, or whether it
will achieve more social welfare. The previous studies considered
similar models, but arrived at different conclusions. In this
paper, we point out that the key is how the users react to
the congestion externality of the underlying system. We derive
suf?cient conditions of congestion functions that can guarantee
the viability of PMP, and provide the relevant physical meanings
of these conditions.
I. INTRODUCTION
Modern communication and service networks, such as Inter-
net/wireless broadband services and cloud computing services,
are characterized by large amount of usage from diverse users.
The management of these communication and service net-
works often relies on simple but effective pricing schemes to
balance the trade-off among resource allocation, performance
and users’ utility [1]–[3]. The pricing schemes adopted in
practice are basically the following two types
1
:
1) Flat-rate Pricing: To charge a one-off fee for every user,
regardless the usage of the user.
2) Usage-based Pricing: To charge according to the amount
and pattern of usage of each individual user.
In this broad classi?cation, we also include congestion
pricing as a form of usage-based pricing. Congestion pricing,
levied only when resource demand exceeds supply, can be
argued as economically and theoretically the most optimal
strategy for allocating congested resources. In practice, users
strongly prefer ?at-rate pricing [4]. While Internet service
provider (ISP) settlements on aggregate transited traf?c are
typically based on usage-based pricing, ISP almost always
charge users using ?at-rate pricing for its simplicity. While
?at-rate pricing is simple, it is insuf?cient to control the
desirable performance to satisfy users’ utility. Users who are
intolerant of inferior performance are forced to opt out.
1
One can also apply static pricing strategy (i.e. time-invariant strategy) or
dynamic pricing strategy (i.e. adaptive schemes that contingent on the total
usage or its history) to these pricing schemes.
About ten years ago, Odlyzko proposed an intriguing way
to use the ?at-rate pricing to better satisfy users with different
aversion to effects of congestion, known as Paris Metro
Pricing (PMP) [5]. The scheme is inspired by the following
convention used by Paris metro at one time
2
: The 1st and 2nd
class cars are charged different prices, although physically the
cars are the same (in terms of the number and quality of the
seats). Since fewer people would pay more for the 1st class
fare, it is also less congested. Thus users more concerned about
getting a seat can opt for 1st class, and more cost-conscientious
users can opt for 2nd class.
Up till now, PMP has not seen wide adoption in communi-
cation and service networks. Implementation issues could be a
reason. But the most fundamental theoretical question for the
viability of PMP has also not been settled. That is, whether
PMP will increase the social welfare and provider pro?t from
the ones of ?at-rate pricing. There is in fact some confusion
due to con?icting conclusions in answering this question. On
the one hand, [6], [7] found PMP to be viable
3
; but on the
other hand, based on a similar model, [8] found that PMP may
not be more viable than ?at-rate pricing.
It turns out the answer depends on the nature of the
congestion externality of the underlying communication and
service network. [6], [7] assumed one type of congestion
externality function while [8] assumed another, hence reaching
con?icting conclusions. In this paper, we consider a general
model of congestion externality for PMP, and provide a
suf?cient condition for the viability of PMP, in terms of both
social welfare as well as provider pro?t. Furthermore, we are
able to give physical meanings to our condition. This leads to
the insights on why PMP is or is not viable, understandable
by common practitioners.
This paper is organized as follows. Sec. II provides the
background and related work. Sec. III presents two key
examples that motivate the general results developed in this
paper. Sec. IV formulates the model of PMP, and notions of
equilibrium for later analysis. Sec. V gives the overview of
our results and the associated insights. We conclude in Sec. VI
with further discussion. For readability, we defer the technical
proofs of theorems to the Appendix.
2
This scheme is actually adopted quite widely in many transportation
systems in the world, including the MTR in Hong Kong.
3
In the single provider case.
This paper appears in the proceedings of IEEE INFOCOM 2010.
2
II. BACKGROUND AND RELATED WORK
PMP was ?rst proposed by Odlyzko [5] as a simpler
charging model for an Internet with differentiated services.
Since PMP relies on the spontaneous economics adjustment
of users, the outcome may not align with the goal of network
designers. There has been a number of studies [6]–[8], [10],
[11] in the literature to address the viability of PMP, which
consider the following three major criteria:
(a.1) Social Welfare: The total utility of users, taking into
account the congestion externality.
(a.2) Provider Pro?t without Competition: The total fees col-
lected by the service providers from different service
classes, under the assumption of monopoly.
(a.3) Provider Pro?t under Competition: The pro?ts of multi-
ple service providers, when they face competition among
themselves to set their prices.
Based on the multi-product economics model in [12], [13],
the study in [6] formulates a model of PMP, considering mas-
sive number of in?nitesimal users, and analyzes the viability
of PMP under criteria (a.1)-(a.3). However, [6] considers only
a speci?c model of congestion externality (we call capacity
sharing service) and assumes that no user will opt out.
To extend the results of [6], the study in [10] considers a
general model of congestion externality to study (a.3), but still
under the assumption of no user opt-out and homogeneous
service classes. [7], [11] consider capacity sharing service
with user opt-out, but only studies (a.2)-(a.3). Meanwhile, [8]
studies PMP under a different model of congestion externality
(we call latency based service) for only (a.2).
In the prior work considering capacity sharing service [6],
[7], [11], it reports that PMP is viable under (a.1)-(a.2), but
not under (a.3). Nonetheless, [8] ?nds that PMP is not viable
in latency based service even for (a.2) by numerical analysis.
Different models of congestion externality can give contradic-
tory results. But there are yet any studies to provide a complete
picture considering a general model of congestion externality,
beyond capacity sharing and latency based services.
While the case of competitive service providers (a.3) is
much harder to yield analytical results (and often relies on
numerical analysis), we derive useful analytical results for
the cases of social welfare (a.1) and monopoly provider
pro?t (a.2), under general model congestion externality, in the
presence of user opt-out and heterogeneous service classes.
This paper considers a large continuum of users for large
communication and service networks. We note that a different
model of PMP with ?nite number of users has been studied
in [14], by which there exists a setting wherein a single
service class is strictly better than multiple service classes for
monopoly provider pro?t. Their conclusion agrees with [8],
albeit by a different model.
III. MOTIVATING EXAMPLES
To motivate our results, we present two key examples of
PMP for communication and service networks, and discuss
the subtle consequences of the two examples.
One unique characteristic in communication and service
networks is the presence of congestion externality, by which
the more number of users accessing a certain service the less
favorable performance the users can perceive. The sensitivity
of congestion externality also depends on the resource allo-
cated to the service. Hence, in general, we can characterize
the congestion externality by (1) the total amount of usage,
and (2) the amount of allocated resource.
In this paper, we use a numerical congestion function
K(Q, C) to capture the congestion externality, where C repre-
sents the numerical capacity, and Q represents the total amount
of usage. We assume C > Q. There are two simple examples
of K(Q, C) as follows.
A. Capacity Sharing Service
First, we consider a generic class of services, in which
the total workload Q is distributed among the processors
with some ?xed total capacity C. Hence, the slice of service
received by each user can be regarded as the portion of
capacity per each unit of usage. Examples include processor
sharing policy in time-sharing system and fair queuing in
network services. Thus, we de?ne the congestion function as:
K
cs
(Q, C)
Q
C
(1)
K
cs
(Q, C) is considered in prior work [6], [7], [11]. By using
this function, we assume the service capacity can be perfectly
shared by users. Also, other performance metrics, such as
queuing time and service time, are not major concerns.
B. Latency Based Service
In other services, the latency may be a major concern.
A simple model to capture the latency is by M/M/1 queue.
Assuming the arrival rate is of Q unit, and the service rate is
of C unit. Then the total expected waiting time (i.e. queuing
time + service time) is:
K
lat
(Q, C)
1
C ?Q
(2)
K
lat
(Q, C) has been considered in prior work [8]. Although
simple M/M/1 queue ignores more sophisticated arrival statis-
tics and queuing disciplines, it has been widely used in the
literature to model data communication services.
C. Simple Consequences
The difference of congestion functions in capacity sharing
and latency based services has an immediate consequence. We
consider a simple scenario of partitioning the service by two
identical service classes charged at an identical price, such that
each class is allocated with half of the original capacity. Then
it is likely that the usage will be split between the two identical
service classes. Hence, we de?ne the capacity and usage for
each service class as C
1
= C
2
=
C
2
and Q
1
= Q
2
=
Q
2
.
In capacity sharing service, the congestion functions after
service partitioning become:
K
cs
(Q
1
, C
1
) = K
cs
(Q
2
, C
2
) =
Q
C
= K
cs
(Q, C) (3)
This paper appears in the proceedings of IEEE INFOCOM 2010.
3
Namely, the users will not perceive any difference in terms of
congestion externality, after service partitioning.
On the other hand, for latency based service, the congestion
functions after service partitioning become:
K
lat
(Q
1
, C
1
) = K
lat
(Q
2
, C
2
) =
2
C ?Q
> K
lat
(Q, C) (4)
In this case, the users actually perceive a degradation of service
after service partitioning! Therefore, we may conclude that the
provision of multiple service classes (i.e. service partitioning)
is not a viable option for latency based service, because of
the decrease of total welfare of users, and also the decrease
of provider pro?t as some users may opt out of the services.
The discussion above, however, has not taken into consider-
ation that the different services have different charges. A more
complete discourse requires a model that includes payment as
part of the user utility and a clear description of users’ decision
process for switching between service classes and opting out.
This will be continued in the following sections.
IV. MODEL
In this section, we develop the model for evaluating PMP
based on different possible forms of congestion externality,
generalizing the model from [6]. We also de?ne the notions
of equilibrium (in which users settle their selections of service
classes), and social welfare and provider pro?t at equilibrium.
A. Utility and Services Classes
Suppose that there are m services classes. We consider a
continuum of users, such that each in?nitesimal user is char-
acterized by a one-dimensional valuation parameter ? ? [0, 1].
The consideration of in?nitesimal user is widely used in eco-
nomics literature that concerns massive number of users, such
as in communication and service networks. The distribution of
? is speci?ed by cumulative distribution function F(?) (here
we denote the probability density function by f(?)). A special
case is F(?) = ? representing a uniform distribution.
When user ? uses service class i ? {1, ..., m}, we assume
that its utility is given by:
U
?
(i) V ?p
i
?? · K(Q
i
, C
i
) (5)
These parameters are explained as follows:
• V is the maximum utility of accessing the service.
• Function K : [0, 1] ?R
+
is a congestion function, which
is increasing in Q
i
, but is decreasing in C
i
.
• Q
i
is the total amount of users of accessing the i-th
service class.
• p
i
is the one-off fee charged per user when accessing the
i-th service class. Without loss of generality, we assume
V ? p
1
? p
2
? · · · ? p
m
? 0.
• C
i
is the proportion of total capacity allocated to the i-th
service class, such that
m
i=1
C
i
= 1.
Therefore, user ? will have two options: either (1) to select
the i-th service class to join that gives the highest utility:
i = arg max
j?{1,...,m}
U
?
(j), (6)
or (2) to opt out of all service classes, when joining any service
class will result in a negative utility:
U
?
(i) < 0 for all i ? {1, ..., m} (7)
An immediate implication of utility function U
?
(i)
(Eqn. (5)) is that the larger value of ? means the higher
valuation on the congestion externality, as compared with the
price of each service class. Hence, users with the larger value
of ? will be more likely to opt out of the service, because of
negative utility U
?
(i) < 0 for all i.
We remark that an alternate utility function can be de?ned
as:
˜
U
?
(i) ? ·
˜
K(Q
i
, C
i
) ?p
i
(8)
where
˜
K(Q
i
, C
i
) represents a satisfaction function, which
captures the inverse effect of a congestion function. In this
case, users with the smaller value of ? will be likely to opt
out of the service, because of negative utility. Eqn. (5) was
used in the literature of economics [12], [13]. We consider
utility function as Eqn. (5) in this paper, because there are
special cases used in the prior work in networking research
community [6]–[8], [10], [11]. In any case, the results derived
in this paper can be easily modi?ed to apply to the setting
using Eqn. (8) as utility function. Also, we remark that [12],
[13] consider only homogeneous service classes (i.e. C
i
is
the same constant in all m service classes). We relax this
constraint to include heterogeneous service classes of different
C
i
’s.
B. Equilibrium, Social Welfare and Provider Pro?t
An equilibrium will be attained when no user switches from
his selection. In this paper, we will analyze the viability of
PMP at equilibrium. To understand equilibrium, we note that
K(Q
i
, C
i
) is ?xed for each i-th class at equilibrium. And so
is the price p
i
. Hence, the utility function U
?
(i) (Eqn. (5)) is
a linear function of ?. For the case m = 2, we plot the utility
U
?
(i) against ? in Fig. 1.
Q
1
Q
2
V?p
1
V?p
2
U
?
U (1)
U
?
(2)
?
1
?
2
?
K(Q
2
,C
2
)
K(Q
1
,C
1
)
0
U
?
(1)
Fig. 1. An illustration of equilibrium, we plot the utility U
?
(i) against ? for
the case m = 2. We assume F(?) = ? is a uniform distribution.
Given a set of differentiated prices p = (p
i
)
m
i=1
for the m
service classes, it is clear that there exists a set of cut-off users
at equilibrium, ? = (?
i
)
m
i=1
, such that for i = 2, .., m, each
This paper appears in the proceedings of IEEE INFOCOM 2010.
4
cut-off user ?
i
is indifferent to joining the (i ? 1)-th service
class or the i-th service class (i.e. U
?i
(i ? 1) = U
?i
(i)), and
cut-off user ?
1
is indifferent to joining the ?rst service class or
opting out of these m service classes. Hence, an equilibrium
can be characterized by the tuple (p, ?).
To formally de?ne equilibrium, we rely on some notations.
First, we normalize the total amount of in?nitesimal users to
be 1. Thus, it follows that
0 ? Q
i
? 1 and
m
i=1
(Q
i
) ? 1 (9)
Let Q
0
1 ?
m
i=1
(Q
i
) be the amount of users who opt out
of these m service classes.
De?nition 1: (Equilibrium) The tuple (p, ?) is an equilib-
rium, if the following constraints are satis?ed:
(c.1): ?
1
> ?
2
> · · · > ?
m
> ?
m+1
= 0,
(c.2): K(Q
i
, C
i
) ? K(Q
i+1
, C
i+1
) for i = m, where
Q
i
_
F(?
m
) if i = m
F(?
i
) ?F(?
i+1
) if 1 ? i < m
(10)
(c.3):
p
i?1
?p
i
= ?
i
·
_
K(Q
i
, C
i
) ?K(Q
i?1
, C
i?1
)
_
if 1 < i ? m
p
1
= V ??
1
· K(Q
1
, C
1
) otherwise
(11)
Namely, (c.1) requires the set of cut-off users (?
i
)
m+1
i=1
having a linear order of valuations on congestion externality.
User ?
m+1
= 0 is the least-valuation user who always accepts
the lowest-priced service class (i.e. the m-th service class).
(c.2) follows from V ? p
1
? · · · ? p
m
? 0 and the de?nition
of utility function (Eqn. (5)). (c.3) characterizes the prices of
service classes, based on the fact that each cut-off user ?
i
is
indifferent to joining the (i ? 1) and i-th service classes (i.e.
U
?i
(i ?1) = U
?i
(i)). These are depicted in Fig. 1.
Note that it is possible p
i
= p
i?1
(i.e. K(Q
i
, C
i
) =
K(Q
i?1
, C
i?1
)) for some i. It is easy to see that an equi-
librium always exists given p or ? (see [12] for a rigorous
proof for this fact). To facilitate later analysis, we also assume
F(?) is a well-formed distribution, such that f(?) > 0 for
? ? [0,
¯
?] ? [0, 1], but f(?) = 0 otherwise.
Suppose (p, ?) is an equilibrium. Let the social welfare be
S(p)
m
i=1
_
?i
?i+1
_
V ?? · K(Q
i
, C
i
)
_
· f(?)d? (12)
Note that in Eqn. (12) ? can be viewed as a function of
p. Namely, it is the total utility of all users excluding the
payment. Also, let the (monopoly) provider pro?t be
?(p)
m
i=1
p
i
· Q
i
(13)
Namely, it is the total payment collected from the users.
C. Numerical Studies and Observations
In this section, we illustrate the consequences of PMP, in
terms of social welfare and provider pro?t at equilibrium,
by numerical studies. We consider the two key examples in
Sec. III: capacity sharing and latency based services. Specif-
ically, we compare the case of one single service class with
capacity as C = 2 with the case of two service classes with
the equal capacity (C
1
= C
2
= 1). In the numerical example,
we let the probability distribution of user’s valuation f(?) be
a uniform distribution, and the maximum utility be V = 2.
Fig. 2-3 show the numerical values of social welfare and
provider pro?t respectively at equilibrium for capacity sharing
service K
cs
(Q, C) at different prices p in four settings: (a)
one single service class (m = 1) with ?at-rate price p for the
single class; (b) two service classes (m = 2) with identical
pricing, p
1
= p
2
= p; (c)&(d) two service classes (m = 2)
with differentiated pricing.
Similarly, Figs. 4-5 show the numerical values of social wel-
fare and provider pro?t for latency based service K
lat
(Q, C).
We can make the following observations from Figs. 2-5:
1) For the capacity sharing service, the social welfare for
case (a) and (b) are identical (the curves coincide with
each other). So is the provider pro?ts for the two cases
(a) and (b). But for the latency based service, there is
a gap between (a) and (b). This validates the claim in
Sec. III.
2) For the capacity sharing service, the service provider can
make more pro?t from PMP, albeit rather small in this
example (see Fig 3); but in the latency based service,
PMP is not viable from the provider pro?t’s point of
view! This are exactly the contradictory conclusions
reached by [7] and [8] respectively!
3) For the latency based service, whether PMP or single
class service is better depends on the price setting.
Without differentiated price setting, i.e. only considering
case (a) to (b), PMP is always worse off. But through
differentiated prices, as in cases (c) and (d), it is possible
to achieve high social welfare through PMP.
4) For PMP, in these examples, it is possible to ?nd
differentiated prices p
1
> p
2
(cases (c) and (d) to
achieve higher provider pro?ts than same price (case
(b)). For social welfare, PMP with differentiated prices
seem to be always better off.
The numerical results above motivate the goal for this
study, namely, how to settle the question of when PMP
can be guaranteed to yield higher pro?ts, and achieve more
social welfare. We want to answer this question by deriving
conditions on a general class of congestion functions, beyond
just the cases of capacity sharing and latency based services.
Tactically, we study this problem in two steps, by asking
the following questions:
1) How do we ensure the viability of partitioning a ser-
vice class into multiple service classes under identical
pricing?
2) How do we ensure the viability of differentiated pricing
This paper appears in the proceedings of IEEE INFOCOM 2010.
5
m1
m2 p
1
p
2
p
m2 p
1
p, p
2
0.83p
m2 p
1
p, p
2
0.67p
0.0 0.5 1.0 1.5 2.0
p 0.0
0.5
1.0
1.5
Social Welfare S
Fig. 2. Social welfare for capacity sharing service Kcs(Q, C).
m1
m2 p
1
p
2
p
m2 p
1
p, p
2
0.93p
m2 p
1
p, p
2
0.83p
0.0 0.5 1.0 1.5 2.0
p 0.0
0.2
0.4
0.6
0.8
1.0
Profit ?
Fig. 3. Provider pro?t for capacity sharing service Kcs(Q, C).
m1
m2 p
1
p
2
p
m2 p
1
p, p
2
0.83p
m2 p
1
p, p
2
0.63p
0.0 0.5 1.0 1.5 2.0
p 0.0
0.2
0.4
0.6
0.8
Social Welfare S
Fig. 4. Social welfare for latency based service K
lat
(Q, C).
m1
m2 p
1
p
2
p
m2 p
1
p, p
2
0.8p
m2 p
1
p, p
2
0.74p
0.0 0.5 1.0 1.5 2.0
p 0.0
0.1
0.2
0.3
0.4
0.5
Profit ?
Fig. 5. Provider pro?t for latency based service K
lat
(Q, C).
of multiple service classes, as compared with identical
pricing?
Our answers to these questions are elaborated in Sec. V.
V. RESULTS
The viability of PMP boils down to the properties of conges-
tion function. Difference in congestion function (e.g. capacity
sharing service and latency based service) results in very
different consequences. In this section, we provide general
suf?cient conditions by identifying some key properties of
congestion functions associated with the viability of PMP.
A. Viability of Service Partitioning
We ?rst provide insights for the viability of service parti-
tioning, by which one single service class is partitioned into
two service classes, both are priced as same as the original
service class. And each service class is allocated a portion of
capacity of the original service class.
Let p and C be the price and capacity of the original single
service class. Let
˜
? be the cut-off user at equilibrium, and the
total usage be
˜
Q F(
˜
?). Then, the social welfare becomes:
S(p)
_ ˜
?
0
_
V ?? · K(
˜
Q, C)
_
· f(?)d? (14)
and the respective provider pro?t becomes:
?(p) p
˜
Q (15)
After service partitioning, let C
1
and C
2
be the respective
capacity of each service class, where C
1
+C
2
= C. Let ?
1
and
?
2
be the cut-off users at equilibrium of each service class, and
the respective usage be Q
1
F(?
1
)?F(?
2
) and Q
2
F(?
2
).
Because of identical pricing of each service class at p, the
social welfare for the partitioned service classes is
4
:
S(p, p)
_
?2
0
_
V ?? · K(Q
2
, C
2
)
_
· f(?)d?
+
_
?1
?2
_
V ?? · K(Q
1
, C
1
)
_
· f(?)d?
(16)
and the respective provider pro?t is
5
:
?(p, p) p(Q
1
+Q
2
) (17)
We next provide a general suf?cient condition on K(Q, C)
for the viability of service partitioning.
Theorem 1: Suppose 0 ? ? < 1.
1) (Partition-preferred congestion function):
If K(Q, C) ? K(?Q, ?C) for all ?,
S(p, p) ? S(p) and ?(p, p) ? ?(p) (18)
2) (Multiplexing-preferred congestion function):
If K(Q, C) ? K(?Q, ?C) for all ?,
S(p, p) ? S(p) and ?(p, p) ? ?(p) (19)
The proofs are all in the Appendix, unless otherwise stated.
Intuitively, Theorem 1 is separating congestion functions
into two types. The congestion function favoring service
partitioning is one that sees decreased congestion externality
as we scale down the usage and capacity. Alternatively, the
4
In trying to reduce notations, we are going to slightly abuse our use of
notations here. The social welfare for the case of a single class service with
one price p, and the case of multiple service classes with price p will all
be denoted by a function S(.), with different number of price parameters as
appropriate.
5
Again, the same abuse of notation is applied to the pro?t function.
This paper appears in the proceedings of IEEE INFOCOM 2010.
6
congestion function that favors multiplexing (service merging)
is one that sees decreased congestion externality as we scale
up the usage and capacity. Note that a congestion function
K(Q, C) is by de?nition increasing in usage Q, but decreasing
in capacity C. When we scale up both usage and capacity, one
or the other of these factors is more dominating, giving rise
to the two classes of congestion functions.
We next provide some examples to apply Theorem 1.
Example 1: (Capacity Sharing Service) According to the
above de?nition, the capacity sharing service K
cs
(Q, C) is
indifferent of service partitioning or multiplexing:
K
cs
(Q, C) =
Q
C
=
?Q
?C
= K
cs
(?Q, ?C) (20)
Example 2: (Latency Based Service) On the other hand, we
can show that the latency based service K
lat
(Q, C) prefers
multiplexing to service partitioning:
K
lat
(Q, C) =
1
C ?Q
<
1
?(C ?Q)
= K
lat
(?Q, ?C) (21)
Example 3: (General Latency Based Service) Motivated by
Pollaczek-Khinchine formula for M/G/1 queue, we de?ne a
general congestion function for latency based service as:
K
glat
(Q, C) =
Q(1 +C
2
S
)
2C(C ?Q)
+
1
C
, (22)
where C
2
S
is the coef?cient of variation of service time by
convention. Therefore, similarly, we may conclude that service
multiplexing is preferred:
K
glat
(Q, C) <
1
?
K
glat
(Q, C) = K
glat
(?Q, ?C) (23)
Example 4: (Consumption Based Service) We de?ne a new
congestion function as:
K
cb
(Q, C) ?(C ?Q) (24)
For K
cb
(Q, C) the congestion externality is mainly determined
by the remaining unconsumed capacity. This may be useful to
describe certain storage or memory-based services. We show
that the consumption based service K
cb
(Q, C) prefers service
partitioning to multiplexing:
K
cb
(Q, C) = ?(C?Q) > ??(C?Q) = K
cb
(?Q, ?C) (25)
By Theorem 1, it is easy to see that service partitioning
is viable for both capacity sharing and consumption based
services, but not latency based service. Note that Theorem 1
is suf?ciently general, and can be applied to diverse types of
congestion functions.
The following corollary extends Theorem 1 from two
classes to multiple classes.
Corollary 2: Suppose 0 ? ? < 1, and p = (p
i
= p)
m
i=1
.
1) (Partition-preferred congestion function):
If K(Q, C) ? K(?Q, ?C) for all ?,
S(p) ? S(p) and ?(p) ? ?(p) (26)
2) (Multiplexing-preferred congestion function):
If K(Q, C) ? K(?Q, ?C) for all ?,
S(p) ? S(p) and ?(p) ? ?(p) (27)
The proof is straightforward and omitted. Informally, it can
be proved by construction, by continuingly splitting a m-class
service to 2m-class service, starting with m = 2.
B. Viability of Differentiated Pricing
Although Sec. V-A provides the suf?cient condition for
service partitioning with identical pricing, it does not cover
the case of differentiated pricing. Especially, PMP is not
perceivable by identical pricing. In this section, we compare
the social welfare and provider pro?t between differentiated
pricing and identical pricing. Hence, we will rely on the
following property of congestion functions.
De?nition 2: (Monotonic Preference to Service Classes)
Given a ?xed set {C
i
: i = 1, ..., m}, the set of congestion
functions {K(Q
i
, C
i
) : i = 1, ..., m} are subject to:
1) Each K(Q
i
, C
i
) must be strictly increasing and differen-
tiable in Q
i
. Hence, the partial derivative of K(Q
i
, C
i
)
at Q
i
: k(Q
i
, C
i
)
?K(Q,C)
?Q
|
Q=Qi,C=Ci
exists and is
positive.
2) Either one of the following two cases must be true:
(m.1) Q
i
? Q
j
? k(Q
i
, C
i
) ? k(Q
j
, C
j
) for any
distinct pair i, j ? {1, ..., m}.
(m.2) Q
i
? Q
j
? k(Q
i
, C
i
) ? k(Q
j
, C
j
) for any
distinct pair i, j ? {1, ..., m}.
Namely, Def. 2 implies there is a monotonic order on
the derivatives of the m congestion functions. Such a
monotonic order of the derivatives re?ects a monotonic order
of sensitivity of congestions externality among the congestion
functions. Note that homogenous service classes with the
same convex congestion function (i.e. C
i
= C
j
) obviously
satisfy Def. 2. Here, we also allow distinct C
i
to capture the
heterogeneous capacities among different service classes.
Example 5: (Capacity Sharing Service) We show that ca-
pacity sharing service K
cs
(Q, C) satis?es monotonic prefer-
ence to service classes, if C
1
? C
2
? · · · ? C
m
:
k
cs
(Q
i
, C
i
) =
?Kcs(Q,C)
?Q
|
Q=Qi,C=Ci
=
1
Ci
(28)
? k
cs
(Q
1
, C
1
) ? k
cs
(Q
2
, C
2
) ? · · · ? k
cs
(Q
m
, C
m
) (29)
for all 0 ? Q
1
, Q
2
, ..., Q
m
? 1.
Example 6: (Latency Based Service) However, latency
based service K
lat
(Q, C) does not satisfy monotonic prefer-
ence to service classes, even if C
1
? C
2
? · · · ? C
m
. Because
k
lat
(Q
i
, C
i
) =
?K
lat
(Q, C)
?Q
|
Q=Qi,C=Ci
=
1
(C
i
?Q
i
)
2
(30)
which is not a monotonic function in C
i
or Q
i
. One can show
similarly for general latency based service.
This paper appears in the proceedings of IEEE INFOCOM 2010.
7
Example 7: (Consumption Based Service) We show that
consumption based service K
cb
(Q, C) also satis?es monotonic
preference to service classes:
k
cb
(Q
i
, C
i
) =
?K
cb
(Q,C)
?Q
|
Q=Qi,C=Ci
= 1 (31)
? k
cb
(Q
1
, C
1
) = k
cb
(Q
2
, C
2
) = · · · = k
cb
(Q
m
, C
m
) (32)
for all 0 ? Q
1
, Q
2
, ..., Q
m
? 1.
Theorem 3: Given two service classes that satisfy mono-
tonic preference (Def. 2), the social welfare of identical pricing
at p is strictly inferior to differentiated pricing for some
p
1
= p
2
:
S(p
1
, p
2
) > S(p, p) (33)
One might not be surprised to see that the differentiated
pricing (p
1
= p
2
) could be better than identical pricing
(p
1
= p
2
). But what is remarkable is the strict superiority
of differentiated pricing. This can be extended to the case for
m service classes in the following corollary.
Corollary 4: Given m service classes that satisfy mono-
tonic preference (Def. 2), let p (p
i
= p)
m
i=1
, then there
exists p
(p
i
)
m
i=1
, such that p
i
= p
j
for all distinct
i, j ? {1, ..., m},
S(p
) > S(p) (34)
We can prove the same results for provider pro?t:
Theorem 5: Given two service classes that satisfy mono-
tonic preference (Def. 2), the provider pro?t of identical
pricing at p is strictly inferior to differentiated pricing for some
p
1
= p
2
:
?(p
1
, p
2
) > ?(p, p) (35)
Corollary 6: Given m service classes that satisfy mono-
tonic preference (Def. 2), let p (p
i
= p)
m
i=1
, then there
exists p
(p
i
)
m
i=1
, such that p
i
= p
j
for some distinct
i, j ? {1, ..., m},
?(p
) > ?(p) (36)
Corollary 6 is an immediate consequence of Theorem 5.
Note that Corollary 6 is weaker than Corollary 4.
Finally, we arrive at the point where we can provide a more
complete answer to our original question, on the viability of
PMP. Combining Theorems 1, 3 and 5, we have a suf?cient
condition to guarantee PMP to be viable, in the sense of both
provider pro?t as well as social welfare. This also explains
clearly why PMP is viable for capacity sharing services and
consumption based services, but not for latency based services.
The Theorems 1-5 are suf?ciently general, so that they can also
be applied to answer more questions about PMP.
VI. CONCLUSION AND DISCUSSION
This paper provides general conditions for the viability of
Paris Metro Pricing, based on a general model of congestion
externality. There are two separate messages here, both can
be intuitively stated. The ?rst one says that your system either
prefers multiplexing (having more people share proportionally
more capacity), or not; if you want to guarantee a gain (in
terms of pro?t or social welfare) by dividing your system into
multiple classes with the same price, then your system better
not prefer multiplexing. The second message says that if you
start with a multi-class system with the same price and you
want to move to charging different prices, then the service
classes you set up better generate monotonic preferences
among your users. By combining these two rules together,
we can characterize a large class of systems that can bene?t
from PMP. These observations also help us understand why
sometimes PMP is not viable. Our results help clarify the
confusion caused by con?icting conclusions on the viability of
PMP by previous studies. Our model is general, and the results
are rigorously proved and are applicable to future studies on
network pricing. In the future work, we will extend our study
to a more sophisticated setting with rate control and adaptation
among the users under PMP.
ACKNOWLEDGMENT
The authors would like to thank Richard Gibbens,
Vishal Misra and the reviewers for suggestions. Dah-Ming
Chiu acknowledges the support from NSFC-RGC grant
N CUHK414/06. Chi-Kin Chau is grateful to The Croucher
Foundation for ?nancial support. This research is continuing
through the participation in the International Technology Al-
liance sponsored by the U.S. Army Research Laboratory and
the U.K. Ministry of Defence.
REFERENCES
[1] J. K. MacKie-Mason and H. R. Varian, “Pricing congestible network
resource,” IEEE Journal Selected Areas in Communications, vol. 13,
no. 7, pp. 1141–1149, 1995.
[2] S. Shenker, D. Clark, D. Estrin, and S. Herzog, “Pricing in computer
networks: Reshaping the research agenda,” ACM Computer Communi-
cation Review, vol. 26, no. 2, pp. 19–43, 1996.
[3] C. K. Chau and K. M. Sim, “Analyzing the impact of sel?sh behaviors
of Internet users and operators,” IEEE Communications Letters, vol. 7,
no. 9, pp. 463–465, September 2003.
[4] A. Odlyzko, “Should ?at-rate internet pricing continue?” IT Profes-
sional, vol. 2, pp. 48–51, 2000.
[5] ——, “Paris metro pricing for the internet,” in Proc. ACM Conf. on
Electronic Commerce, 1999, pp. 140–147.
[6] R. Gibbens, R. Mason, and R. Steinberg, “Internet service classes under
competition,” IEEE Journal Selected Areas in Communications, vol. 18,
no. 2, pp. 2490–2498, 2000.
[7] R. Jain, T. Mullen, and R. Hausman, “Analysis of Paris Metro pricing
strategy for QoS with a single service provider,” in Proc. IEEE/IFIP
Intl. Workshop on Quality of Service, 2001, pp. 495–500.
[8] D. Ros and B. Tuf?n, “A mathematical model of the Paris Metro pricing
scheme for charging packet networks,” Computer Networks, vol. 46, pp.
73–85, 2004.
[9] K. Kalevi, Differentiated services for the internet. Macmillan, 1999.
[10] O. Haimanko and R. Steinberg, Price Symmetry in a Duopoly with
Congestion, December 2000, CORE Discussion Paper.
[11] H. Sakurai, S. Kasahara, and N. Adachi, “Internet pricing and user
opt-out strategy under two ISPs competition,” in Proc. Intl. Network
Optimization Conf. (INOC), 2003, pp. 495–500.
[12] P. Chander and L. Leruth, “The optimal product mix for a monopo-
list in the presence of congestion effects,” Intl. Journal of Industrial
Organization, vol. 7, no. 4, pp. 437–449, 1989.
[13] A. de Palma and L. Leruth, “Congestion and game in capacity: A
duopoly analysis in the presence of network externalities,” Annales
d’Economie et de Statistique, no. 15–16, pp. 389–407, 1989.
[14] S. Shakkottai, R. Srikant, A. Ozdaglar, and D. Accemoglu, “The price
of simplicity,” IEEE Journal Selected Areas in Communications, vol. 26,
no. 7, pp. 1269–1276, 2007.
This paper appears in the proceedings of IEEE INFOCOM 2010.
8
VII. APPENDIX
A. Proof for Theorem 1
Proof: First, by Eqn. (11) in Def. 1, for a single service
class, we obtain:
p = V ?
˜
? · K
_
˜
Q, C
_
?
˜
? =
V ?p
K
_
˜
Q, C
_ (37)
Also, for partitioned service classes, we obtain:
_
p ?p =?
2
·
_
K
_
Q
2
, C
2
_
?K
_
Q
1
, C
1
_
_
p =V ??
1
· K
_
Q
1
, C
1
_ (38)
Hence, Eqn. (38) follows that
K
_
Q
2
, C
2
_
= K
_
Q
1
, C
1
_
(39)
?
1
=
V ?p
K(Q
1
, C
1
_ (40)
Using Eqns. (37) and (40), we obtain the following equality:
˜
?
?
1
=
K(Q
1
, C
1
)
K(
˜
Q, C)
=
K(Q
2
, C
2
)
K(
˜
Q, C)
(41)
Step 1: Then, we want to show:
1) If K(Q, C) ? K(?Q, ?C) for all ?, then ?
1
?
˜
?
2) If K(Q, C) ? K(?Q, ?C) for all ?, then ?
1
?
˜
?
Without loss of generality, we assume C
1
? C
2
. Let ?
C1
C
,
and hence, we have ? ? 1 ??.
First, we consider partition-preferred congestion function:
K(Q, C) ? K(?Q, ?C) for all ?. By Eqn. (39), it follows
that:
K(Q
2
, C
2
) = K(Q
1
, C
1
) ? K(
1 ??
?
Q
1
, C
2
) (42)
Because K(Q, C) is increasing in Q, we obtain:
Q
2
?
1 ??
?
Q
1
? Q
1
+Q
2
?
Q
1
?
(43)
Because K(Q, C) ? K(?Q, ?C) for all ?, we obtain:
K(
˜
Q, C) ? K
_
?
˜
Q, ?C
_
= K
_
?
˜
Q, C
1
_
(44)
We next use contradiction to show ?
1
?
˜
?. On the contrary,
we suppose
˜
? > ?
1
. Then, by Eqns. (41) and (44), we obtain:
K
_
Q
1
, C
1
_
> K
_
˜
Q, C
_
? K
_
?
˜
Q, C
1
_
(45)
Hence, Q
1
> ?
˜
Q, because K(Q, C) is increasing in Q.
Also, we note that
˜
? > ?
1
? F(
˜
?) > F(?
1
) ?
˜
Q > Q
1
+Q
2
(46)
Therefore, we derive that
Q
1
> ?
˜
Q > ?(Q
1
+Q
2
) (47)
which is a contradiction to Eqn. (43). Hence, it should be
?
1
?
˜
?. Similarly, we can show for merge effect: K(Q, C) ?
K(?Q, ?C) for all ? implies ?
1
?
˜
?.
Step 2: Finally, we want to show:
1) If ?
1
?
˜
?, then S(p, p) ? S(p) and ?(p, p) ? ?(p).
2) If ?
1
?
˜
?, then S(p, p) ? S(p) and ?(p, p) ? ?(p).
The case of provider pro?t ?(p, p) and ?(p) follows from
Eqns. (14) and (17), and
?
1
?
˜
? ? Q
1
+Q
2
?
˜
Q and ?
1
?
˜
? ? Q
1
+Q
2
?
˜
Q (48)
For the case of social welfare, by Eqn. (39), we obtain:
S(p, p) =
_
?1
0
_
V ?? · K(Q
2
, C
2
)
_
· f(?)d? (49)
From Eqn. (41), we obtain:
?
1
?
˜
? ? K
_
˜
Q, C
_
? K
_
Q
2
, C
2
_
(50)
?
1
?
˜
? ? K
_
˜
Q, C
_
? K
_
Q
2
, C
2
_
(51)
By Eqns. (15) and (48)-(51), we complete the proof.
B. Proof for Theorem 3
Proof: First, we write S = S(p
1
, p
2
). We study how the
total differential of S, dS, changes at p
1
= p
2
. From Eqn. (16),
S = V · F(?
1
) ?K(Q
2
, C
2
)
_
?2
0
? · f(?)d?
?K(Q
1
, C
1
)
_
?1
?2
? · f(?)d?
(52)
Recall that k(Q
i
, C
i
)
?K(Q,C)
?Q
|
Q=Qi,C=Ci
, Q
2
F(?
2
)
and Q
1
F(?
1
) ?F(?
2
).
An equilibrium can be characterized by (p
1
, p
2
), a pair
of independent variables. Similarly, an equilibrium can be
equivalently characterized by (?
1
, ?
2
), by solving Eqn. (11)
in Def. 1. Then (?
1
, ?
2
) are treated as a pair of independent
variables. Thus, we take the total differential of S with respect
to the differentials of variables (?
1
, ?
2
):
dS = V · f(?
1
)d?
1
?
_
_
?2
0
? · f(?)d?
_
· k(Q
2
, C
2
)f(?
2
)d?
2
?K(Q
2
, C
2
) · ?
2
· f(?
2
)d?
2
?
_
_
?1
?2
? · f(?)d?
_
· k(Q
1
, C
1
)
_
f(?
1
)d?
1
?f(?
2
)d?
2
_
?K(Q
1
, C
1
) ·
_
?
1
· f(?
1
)d?
1
??
2
· f(?
2
)d?
2
_
(53)
Then, at identical pricing p
1
= p
2
? K(Q
1
, C
1
) =
K(Q
2
, C
2
). Hence, we obtain:
dS|
p1=p2
= V · f(?
1
)d?
1
?
_
_
?2
0
? · f(?)d?
_
· k(Q
2
, C
2
)f(?
2
)d?
2
?
_
_
?1
?2
? · f(?)d?
_
· k(Q
1
, C
1
)
_
f(?
1
)d?
1
?f(?
2
)d?
2
_
?K(Q
1
, C
1
) · ?
1
· f(?
1
)d?
1
(54)
Next, we pick a vector d?
1
+d?
2
, and show that dS|
p1=p2
will
strictly increase in the direction of d?
1
+ d?
2
. Such a vector
This paper appears in the proceedings of IEEE INFOCOM 2010.
9
indeed exists if we keep ?
1
as a constant (i.e. d?
1
= 0). First,
we obtain:
dS|
p1=p2,d?1=0
=
_
_
_
?1
?2
? · f(?)d?
_
· k(Q
1
, C
1
)
?
_
_
?2
0
? · f(?)d?
_
· k(Q
2
, C
2
)
_
f(?
2
)d?
2
(55a)
> ?
2
·
_
_
_
?1
?2
f(?)d?
_
· k(Q
1
, C
1
)
?
_
_
?2
0
f(?)d?
_
· k(Q
2
, C
2
)
_
f(?
2
)d?
2
(55b)
= ?
1
_
Q
1
· k(Q
1
, C
1
) ?Q
2
· k(Q
2
, C
2
)
_
f(?
2
)d?
2
(55c)
Since the two service classes satisfy monotonic preference
(Def. 2), if we always pick d?
2
> 0 in the case of (m.1),
and d?
2
< 0 in the case of (m.2), then it is always true
that dS|
p1=p2,d?1=0
> 0. Therefore, this shows that the
social welfare S can strictly increase by differentiated pricing
(p
1
= p
2
) from identical pricing (p
1
= p
2
).
C. Proof for Corollary 4
Proof: By Theorem 3, it is true for m = 2. For m = 3,
it follows that p
1
= p
2
= p
3
cannot be optimal. Next, we also
show that p
1
> p
2
= p
3
and p
1
= p
2
> p
3
cannot be optimal.
Then, the total differential of social welfare S becomes:
dS = V · f(?
1
)d?
1
?
_
_
?3
0
? · f(?)d?
_
· k(Q
3
, C
3
)f(?
3
)d?
3
?K(Q
3
, C
3
) · ?
3
· f(?
3
)d?
3
?
_
_
?2
?3
? · f(?)d?
_
· k(Q
2
, C
2
)
_
f(?
2
)d?
2
?f(?
3
)d?
3
_
?K(Q
2
, C
2
) ·
_
?
2
· f(?
2
)d?
2
??
3
· f(?
3
)d?
3
_
?
_
_
?1
?2
? · f(?)d?
_
· k(Q
1
, C
1
)
_
f(?
1
)d?
1
?f(?
2
)d?
2
_
?K(Q
1
, C
1
) ·
_
?
1
· f(?
1
)d?
1
??
2
· f(?
2
)d?
2
_
(56)
For p
1
> p
2
= p
3
(i.e. K(Q
2
, C
2
) = K(Q
3
, C
3
)), setting
d?
1
= d?
2
= 0 will degenerate to the case m = 2. For p
1
=
p
2
> p
3
(i.e. K(Q
1
, C
1
) = K(Q
2
, C
2
)), setting d?
1
= d?
3
=
0 will also degenerate to the case m = 2. Hence, it follows
for m = 3 is true. Using an iterative argument, we can show
that it is true for all m ? 2.
D. Proof for Theorem 5
Proof: Similar to Theorem 3, taking the total differential
of ? with respect to the differentials of variables (p
1
, p
2
):
d? = Q
2
dp
2
+p
2
· f(?
2
)
_
??
2
?p
1
dp
1
+
??
2
?p
2
dp
2
_
+Q
1
dp
1
+p
1
·
_
f(?
1
)
_
??
1
?p
1
dp
1
+
??
1
?p
2
dp
2
_
?f(?
2
)
_
??
2
?p
1
dp
1
+
??
2
?p
2
dp
2
_
_
(57)
Then, at identical pricing (p
1
= p
2
), we obtain:
d?|
p2=p1
= Q
2
dp
2
+Q
1
dp
1
+p
1
· f(?
1
)(
??
1
?p
1
dp
1
+
??
1
?p
2
dp
2
)
(58)
Similar to Theorem 3, we pick a vector dp
1
+dp
2
, and show
that d?|
p1=p2
will strictly increase in the direction of dp
1
+
dp
2
. To achieve so, we keep ?
1
as a constant (i.e. d?
1
=
??1
?p1
dp
1
+
??1
?p2
dp
2
= 0). Hence,
d?|
p1=p2,d?1=0
= Q
1
dp
1
+Q
2
dp
2
(59)
Also, from Eqn. (11) in Def. 1, keeping ?
1
as a constant (i.e.
d?
1
= 0), we obtain the total differentials (p
1
, p
2
) with respect
to ?
2
as:
_
¸
¸
_
¸
¸
_
dp
1
= ?
1
· k(Q
1
, C
1
)f(?
2
)d?
2
dp
1
?dp
2
= ?
2
·
_
k(Q
2
, C
2
) +k(Q
1
, C
1
)
_
· f(?
2
)d?
2
+
_
K(Q
2
, C
2
) ?K(Q
1
, C
1
)
_
d?
2
(60)
where k(Q
i
, C
i
)
?K(Q,C)
?Q
|
Q=Qi,C=Ci
.
Since at identical pricing p
1
= p
2
? K(Q
1
, C
1
) =
K(Q
2
, C
2
), we have
_
dp
1
= ?
1
· k(Q
1
, C
1
)f(?
2
)d?
2
dp
1
?dp
2
= ?
2
·
_
k(Q
2
, C
2
) +k(Q
1
, C
1
)
_
· f(?
2
)d?
2
(61)
Solving Eqn. (61) for (dp
1
, dp
2
), we obtain:
dp
2
=
??
2
· (k(Q
2
, C
2
) +k(Q
1
, C
1
)) +?
1
· k(Q
1
, C
1
)
?
1
· k(Q
1
, C
1
)
dp
1
(62)
Because we keep ?
1
as a constant (i.e. d?
1
= 0), by substitut-
ing Eqn. (62) we obtain:
d?|
p1=p2,d?1=0
= Q
2
dp
2
+Q
1
dp
1
=
_
Q
2
·
_
??
2
· (k(Q
2
, C
2
) +k(Q
1
, C
1
)) +?
1
· k(Q
1
, C
1
)
_
+Q
1
?
1
· k(Q
1
, C
1
)
_
dp
1
?
1
· k(Q
1
, C
1
)
(63a)
=
_
?Q
2
?
2
· (
k(Q
2
, C
2
)
k(Q
1
, C
1
)
) ?Q
2
?
2
+Q
2
?
1
+Q
1
?
1
_
dp
1
?
1
>
_
?Q
2
· (
k(Q
2
, C
2
)
k(Q
1
, C
1
)
) ?Q
2
+Q
2
+Q
1
_
?
2
dp
1
?
1
(63b)
=
_
Q
1
· k(Q
1
, C
1
) ?Q
2
· k(Q
2
, C
2
)
_
?
2
dp
1
?
1
· k(Q
1
, C
1
)
(63c)
Since the two service classes satisfy monotonic preference
(Def. 2), if we always pick d?
2
> 0 in the case of (m.1),
and d?
2
< 0 in the case of (m.2), then it is always true
that d?|
p1=p2,d?1=0
> 0. Therefore, the provider pro?t ?
can strictly increase by differentiated pricing (p
1
= p
2
) from
identical pricing (p
1
= p
2
).
This paper appears in the proceedings of IEEE INFOCOM 2010.
doc_286585872.pdf
Abstract—Paris Metro Pricing (PMP) is a simple multi-class
flat-rate pricing scheme already practiced by transport systems,
specifically by the Paris Metro at one time. The name is coined
after Andrew Odlyzko proposed it for the Internet as a simple
way to provide differentiated services. Subsequently, there were
several analytical studies of this promising idea. The central issue
of these studies is whether PMP is viable, namely, whether it
will produce more profit for the service provider, or whether it
will achieve more social welfare. The previous studies considered
similar models, but arrived at different conclusions. In this
paper, we point out that the key is how the users react to
the congestion externality of the underlying system. We derive
sufficient conditions of congestion functions that can guarantee
the viability of PMP, and provide the relevant physical meanings
of these conditions.
1
On the Viability of Paris Metro Pricing for
Communication and Service Networks
Chi-Kin Chau
University of Cambridge
& University College London, UK
[email protected]
Qian Wang
Department of Information Engineering,
The Chinese University of Hong Kong
[email protected]
Dah-Ming Chiu
Department of Information Engineering,
The Chinese University of Hong Kong
[email protected]
Abstract—Paris Metro Pricing (PMP) is a simple multi-class
?at-rate pricing scheme already practiced by transport systems,
speci?cally by the Paris Metro at one time. The name is coined
after Andrew Odlyzko proposed it for the Internet as a simple
way to provide differentiated services. Subsequently, there were
several analytical studies of this promising idea. The central issue
of these studies is whether PMP is viable, namely, whether it
will produce more pro?t for the service provider, or whether it
will achieve more social welfare. The previous studies considered
similar models, but arrived at different conclusions. In this
paper, we point out that the key is how the users react to
the congestion externality of the underlying system. We derive
suf?cient conditions of congestion functions that can guarantee
the viability of PMP, and provide the relevant physical meanings
of these conditions.
I. INTRODUCTION
Modern communication and service networks, such as Inter-
net/wireless broadband services and cloud computing services,
are characterized by large amount of usage from diverse users.
The management of these communication and service net-
works often relies on simple but effective pricing schemes to
balance the trade-off among resource allocation, performance
and users’ utility [1]–[3]. The pricing schemes adopted in
practice are basically the following two types
1
:
1) Flat-rate Pricing: To charge a one-off fee for every user,
regardless the usage of the user.
2) Usage-based Pricing: To charge according to the amount
and pattern of usage of each individual user.
In this broad classi?cation, we also include congestion
pricing as a form of usage-based pricing. Congestion pricing,
levied only when resource demand exceeds supply, can be
argued as economically and theoretically the most optimal
strategy for allocating congested resources. In practice, users
strongly prefer ?at-rate pricing [4]. While Internet service
provider (ISP) settlements on aggregate transited traf?c are
typically based on usage-based pricing, ISP almost always
charge users using ?at-rate pricing for its simplicity. While
?at-rate pricing is simple, it is insuf?cient to control the
desirable performance to satisfy users’ utility. Users who are
intolerant of inferior performance are forced to opt out.
1
One can also apply static pricing strategy (i.e. time-invariant strategy) or
dynamic pricing strategy (i.e. adaptive schemes that contingent on the total
usage or its history) to these pricing schemes.
About ten years ago, Odlyzko proposed an intriguing way
to use the ?at-rate pricing to better satisfy users with different
aversion to effects of congestion, known as Paris Metro
Pricing (PMP) [5]. The scheme is inspired by the following
convention used by Paris metro at one time
2
: The 1st and 2nd
class cars are charged different prices, although physically the
cars are the same (in terms of the number and quality of the
seats). Since fewer people would pay more for the 1st class
fare, it is also less congested. Thus users more concerned about
getting a seat can opt for 1st class, and more cost-conscientious
users can opt for 2nd class.
Up till now, PMP has not seen wide adoption in communi-
cation and service networks. Implementation issues could be a
reason. But the most fundamental theoretical question for the
viability of PMP has also not been settled. That is, whether
PMP will increase the social welfare and provider pro?t from
the ones of ?at-rate pricing. There is in fact some confusion
due to con?icting conclusions in answering this question. On
the one hand, [6], [7] found PMP to be viable
3
; but on the
other hand, based on a similar model, [8] found that PMP may
not be more viable than ?at-rate pricing.
It turns out the answer depends on the nature of the
congestion externality of the underlying communication and
service network. [6], [7] assumed one type of congestion
externality function while [8] assumed another, hence reaching
con?icting conclusions. In this paper, we consider a general
model of congestion externality for PMP, and provide a
suf?cient condition for the viability of PMP, in terms of both
social welfare as well as provider pro?t. Furthermore, we are
able to give physical meanings to our condition. This leads to
the insights on why PMP is or is not viable, understandable
by common practitioners.
This paper is organized as follows. Sec. II provides the
background and related work. Sec. III presents two key
examples that motivate the general results developed in this
paper. Sec. IV formulates the model of PMP, and notions of
equilibrium for later analysis. Sec. V gives the overview of
our results and the associated insights. We conclude in Sec. VI
with further discussion. For readability, we defer the technical
proofs of theorems to the Appendix.
2
This scheme is actually adopted quite widely in many transportation
systems in the world, including the MTR in Hong Kong.
3
In the single provider case.
This paper appears in the proceedings of IEEE INFOCOM 2010.
2
II. BACKGROUND AND RELATED WORK
PMP was ?rst proposed by Odlyzko [5] as a simpler
charging model for an Internet with differentiated services.
Since PMP relies on the spontaneous economics adjustment
of users, the outcome may not align with the goal of network
designers. There has been a number of studies [6]–[8], [10],
[11] in the literature to address the viability of PMP, which
consider the following three major criteria:
(a.1) Social Welfare: The total utility of users, taking into
account the congestion externality.
(a.2) Provider Pro?t without Competition: The total fees col-
lected by the service providers from different service
classes, under the assumption of monopoly.
(a.3) Provider Pro?t under Competition: The pro?ts of multi-
ple service providers, when they face competition among
themselves to set their prices.
Based on the multi-product economics model in [12], [13],
the study in [6] formulates a model of PMP, considering mas-
sive number of in?nitesimal users, and analyzes the viability
of PMP under criteria (a.1)-(a.3). However, [6] considers only
a speci?c model of congestion externality (we call capacity
sharing service) and assumes that no user will opt out.
To extend the results of [6], the study in [10] considers a
general model of congestion externality to study (a.3), but still
under the assumption of no user opt-out and homogeneous
service classes. [7], [11] consider capacity sharing service
with user opt-out, but only studies (a.2)-(a.3). Meanwhile, [8]
studies PMP under a different model of congestion externality
(we call latency based service) for only (a.2).
In the prior work considering capacity sharing service [6],
[7], [11], it reports that PMP is viable under (a.1)-(a.2), but
not under (a.3). Nonetheless, [8] ?nds that PMP is not viable
in latency based service even for (a.2) by numerical analysis.
Different models of congestion externality can give contradic-
tory results. But there are yet any studies to provide a complete
picture considering a general model of congestion externality,
beyond capacity sharing and latency based services.
While the case of competitive service providers (a.3) is
much harder to yield analytical results (and often relies on
numerical analysis), we derive useful analytical results for
the cases of social welfare (a.1) and monopoly provider
pro?t (a.2), under general model congestion externality, in the
presence of user opt-out and heterogeneous service classes.
This paper considers a large continuum of users for large
communication and service networks. We note that a different
model of PMP with ?nite number of users has been studied
in [14], by which there exists a setting wherein a single
service class is strictly better than multiple service classes for
monopoly provider pro?t. Their conclusion agrees with [8],
albeit by a different model.
III. MOTIVATING EXAMPLES
To motivate our results, we present two key examples of
PMP for communication and service networks, and discuss
the subtle consequences of the two examples.
One unique characteristic in communication and service
networks is the presence of congestion externality, by which
the more number of users accessing a certain service the less
favorable performance the users can perceive. The sensitivity
of congestion externality also depends on the resource allo-
cated to the service. Hence, in general, we can characterize
the congestion externality by (1) the total amount of usage,
and (2) the amount of allocated resource.
In this paper, we use a numerical congestion function
K(Q, C) to capture the congestion externality, where C repre-
sents the numerical capacity, and Q represents the total amount
of usage. We assume C > Q. There are two simple examples
of K(Q, C) as follows.
A. Capacity Sharing Service
First, we consider a generic class of services, in which
the total workload Q is distributed among the processors
with some ?xed total capacity C. Hence, the slice of service
received by each user can be regarded as the portion of
capacity per each unit of usage. Examples include processor
sharing policy in time-sharing system and fair queuing in
network services. Thus, we de?ne the congestion function as:
K
cs
(Q, C)
Q
C
(1)
K
cs
(Q, C) is considered in prior work [6], [7], [11]. By using
this function, we assume the service capacity can be perfectly
shared by users. Also, other performance metrics, such as
queuing time and service time, are not major concerns.
B. Latency Based Service
In other services, the latency may be a major concern.
A simple model to capture the latency is by M/M/1 queue.
Assuming the arrival rate is of Q unit, and the service rate is
of C unit. Then the total expected waiting time (i.e. queuing
time + service time) is:
K
lat
(Q, C)
1
C ?Q
(2)
K
lat
(Q, C) has been considered in prior work [8]. Although
simple M/M/1 queue ignores more sophisticated arrival statis-
tics and queuing disciplines, it has been widely used in the
literature to model data communication services.
C. Simple Consequences
The difference of congestion functions in capacity sharing
and latency based services has an immediate consequence. We
consider a simple scenario of partitioning the service by two
identical service classes charged at an identical price, such that
each class is allocated with half of the original capacity. Then
it is likely that the usage will be split between the two identical
service classes. Hence, we de?ne the capacity and usage for
each service class as C
1
= C
2
=
C
2
and Q
1
= Q
2
=
Q
2
.
In capacity sharing service, the congestion functions after
service partitioning become:
K
cs
(Q
1
, C
1
) = K
cs
(Q
2
, C
2
) =
Q
C
= K
cs
(Q, C) (3)
This paper appears in the proceedings of IEEE INFOCOM 2010.
3
Namely, the users will not perceive any difference in terms of
congestion externality, after service partitioning.
On the other hand, for latency based service, the congestion
functions after service partitioning become:
K
lat
(Q
1
, C
1
) = K
lat
(Q
2
, C
2
) =
2
C ?Q
> K
lat
(Q, C) (4)
In this case, the users actually perceive a degradation of service
after service partitioning! Therefore, we may conclude that the
provision of multiple service classes (i.e. service partitioning)
is not a viable option for latency based service, because of
the decrease of total welfare of users, and also the decrease
of provider pro?t as some users may opt out of the services.
The discussion above, however, has not taken into consider-
ation that the different services have different charges. A more
complete discourse requires a model that includes payment as
part of the user utility and a clear description of users’ decision
process for switching between service classes and opting out.
This will be continued in the following sections.
IV. MODEL
In this section, we develop the model for evaluating PMP
based on different possible forms of congestion externality,
generalizing the model from [6]. We also de?ne the notions
of equilibrium (in which users settle their selections of service
classes), and social welfare and provider pro?t at equilibrium.
A. Utility and Services Classes
Suppose that there are m services classes. We consider a
continuum of users, such that each in?nitesimal user is char-
acterized by a one-dimensional valuation parameter ? ? [0, 1].
The consideration of in?nitesimal user is widely used in eco-
nomics literature that concerns massive number of users, such
as in communication and service networks. The distribution of
? is speci?ed by cumulative distribution function F(?) (here
we denote the probability density function by f(?)). A special
case is F(?) = ? representing a uniform distribution.
When user ? uses service class i ? {1, ..., m}, we assume
that its utility is given by:
U
?
(i) V ?p
i
?? · K(Q
i
, C
i
) (5)
These parameters are explained as follows:
• V is the maximum utility of accessing the service.
• Function K : [0, 1] ?R
+
is a congestion function, which
is increasing in Q
i
, but is decreasing in C
i
.
• Q
i
is the total amount of users of accessing the i-th
service class.
• p
i
is the one-off fee charged per user when accessing the
i-th service class. Without loss of generality, we assume
V ? p
1
? p
2
? · · · ? p
m
? 0.
• C
i
is the proportion of total capacity allocated to the i-th
service class, such that
m
i=1
C
i
= 1.
Therefore, user ? will have two options: either (1) to select
the i-th service class to join that gives the highest utility:
i = arg max
j?{1,...,m}
U
?
(j), (6)
or (2) to opt out of all service classes, when joining any service
class will result in a negative utility:
U
?
(i) < 0 for all i ? {1, ..., m} (7)
An immediate implication of utility function U
?
(i)
(Eqn. (5)) is that the larger value of ? means the higher
valuation on the congestion externality, as compared with the
price of each service class. Hence, users with the larger value
of ? will be more likely to opt out of the service, because of
negative utility U
?
(i) < 0 for all i.
We remark that an alternate utility function can be de?ned
as:
˜
U
?
(i) ? ·
˜
K(Q
i
, C
i
) ?p
i
(8)
where
˜
K(Q
i
, C
i
) represents a satisfaction function, which
captures the inverse effect of a congestion function. In this
case, users with the smaller value of ? will be likely to opt
out of the service, because of negative utility. Eqn. (5) was
used in the literature of economics [12], [13]. We consider
utility function as Eqn. (5) in this paper, because there are
special cases used in the prior work in networking research
community [6]–[8], [10], [11]. In any case, the results derived
in this paper can be easily modi?ed to apply to the setting
using Eqn. (8) as utility function. Also, we remark that [12],
[13] consider only homogeneous service classes (i.e. C
i
is
the same constant in all m service classes). We relax this
constraint to include heterogeneous service classes of different
C
i
’s.
B. Equilibrium, Social Welfare and Provider Pro?t
An equilibrium will be attained when no user switches from
his selection. In this paper, we will analyze the viability of
PMP at equilibrium. To understand equilibrium, we note that
K(Q
i
, C
i
) is ?xed for each i-th class at equilibrium. And so
is the price p
i
. Hence, the utility function U
?
(i) (Eqn. (5)) is
a linear function of ?. For the case m = 2, we plot the utility
U
?
(i) against ? in Fig. 1.
Q
1
Q
2
V?p
1
V?p
2
U
?
U (1)
U
?
(2)
?
1
?
2
?
K(Q
2
,C
2
)
K(Q
1
,C
1
)
0
U
?
(1)
Fig. 1. An illustration of equilibrium, we plot the utility U
?
(i) against ? for
the case m = 2. We assume F(?) = ? is a uniform distribution.
Given a set of differentiated prices p = (p
i
)
m
i=1
for the m
service classes, it is clear that there exists a set of cut-off users
at equilibrium, ? = (?
i
)
m
i=1
, such that for i = 2, .., m, each
This paper appears in the proceedings of IEEE INFOCOM 2010.
4
cut-off user ?
i
is indifferent to joining the (i ? 1)-th service
class or the i-th service class (i.e. U
?i
(i ? 1) = U
?i
(i)), and
cut-off user ?
1
is indifferent to joining the ?rst service class or
opting out of these m service classes. Hence, an equilibrium
can be characterized by the tuple (p, ?).
To formally de?ne equilibrium, we rely on some notations.
First, we normalize the total amount of in?nitesimal users to
be 1. Thus, it follows that
0 ? Q
i
? 1 and
m
i=1
(Q
i
) ? 1 (9)
Let Q
0
1 ?
m
i=1
(Q
i
) be the amount of users who opt out
of these m service classes.
De?nition 1: (Equilibrium) The tuple (p, ?) is an equilib-
rium, if the following constraints are satis?ed:
(c.1): ?
1
> ?
2
> · · · > ?
m
> ?
m+1
= 0,
(c.2): K(Q
i
, C
i
) ? K(Q
i+1
, C
i+1
) for i = m, where
Q
i
_
F(?
m
) if i = m
F(?
i
) ?F(?
i+1
) if 1 ? i < m
(10)
(c.3):
p
i?1
?p
i
= ?
i
·
_
K(Q
i
, C
i
) ?K(Q
i?1
, C
i?1
)
_
if 1 < i ? m
p
1
= V ??
1
· K(Q
1
, C
1
) otherwise
(11)
Namely, (c.1) requires the set of cut-off users (?
i
)
m+1
i=1
having a linear order of valuations on congestion externality.
User ?
m+1
= 0 is the least-valuation user who always accepts
the lowest-priced service class (i.e. the m-th service class).
(c.2) follows from V ? p
1
? · · · ? p
m
? 0 and the de?nition
of utility function (Eqn. (5)). (c.3) characterizes the prices of
service classes, based on the fact that each cut-off user ?
i
is
indifferent to joining the (i ? 1) and i-th service classes (i.e.
U
?i
(i ?1) = U
?i
(i)). These are depicted in Fig. 1.
Note that it is possible p
i
= p
i?1
(i.e. K(Q
i
, C
i
) =
K(Q
i?1
, C
i?1
)) for some i. It is easy to see that an equi-
librium always exists given p or ? (see [12] for a rigorous
proof for this fact). To facilitate later analysis, we also assume
F(?) is a well-formed distribution, such that f(?) > 0 for
? ? [0,
¯
?] ? [0, 1], but f(?) = 0 otherwise.
Suppose (p, ?) is an equilibrium. Let the social welfare be
S(p)
m
i=1
_
?i
?i+1
_
V ?? · K(Q
i
, C
i
)
_
· f(?)d? (12)
Note that in Eqn. (12) ? can be viewed as a function of
p. Namely, it is the total utility of all users excluding the
payment. Also, let the (monopoly) provider pro?t be
?(p)
m
i=1
p
i
· Q
i
(13)
Namely, it is the total payment collected from the users.
C. Numerical Studies and Observations
In this section, we illustrate the consequences of PMP, in
terms of social welfare and provider pro?t at equilibrium,
by numerical studies. We consider the two key examples in
Sec. III: capacity sharing and latency based services. Specif-
ically, we compare the case of one single service class with
capacity as C = 2 with the case of two service classes with
the equal capacity (C
1
= C
2
= 1). In the numerical example,
we let the probability distribution of user’s valuation f(?) be
a uniform distribution, and the maximum utility be V = 2.
Fig. 2-3 show the numerical values of social welfare and
provider pro?t respectively at equilibrium for capacity sharing
service K
cs
(Q, C) at different prices p in four settings: (a)
one single service class (m = 1) with ?at-rate price p for the
single class; (b) two service classes (m = 2) with identical
pricing, p
1
= p
2
= p; (c)&(d) two service classes (m = 2)
with differentiated pricing.
Similarly, Figs. 4-5 show the numerical values of social wel-
fare and provider pro?t for latency based service K
lat
(Q, C).
We can make the following observations from Figs. 2-5:
1) For the capacity sharing service, the social welfare for
case (a) and (b) are identical (the curves coincide with
each other). So is the provider pro?ts for the two cases
(a) and (b). But for the latency based service, there is
a gap between (a) and (b). This validates the claim in
Sec. III.
2) For the capacity sharing service, the service provider can
make more pro?t from PMP, albeit rather small in this
example (see Fig 3); but in the latency based service,
PMP is not viable from the provider pro?t’s point of
view! This are exactly the contradictory conclusions
reached by [7] and [8] respectively!
3) For the latency based service, whether PMP or single
class service is better depends on the price setting.
Without differentiated price setting, i.e. only considering
case (a) to (b), PMP is always worse off. But through
differentiated prices, as in cases (c) and (d), it is possible
to achieve high social welfare through PMP.
4) For PMP, in these examples, it is possible to ?nd
differentiated prices p
1
> p
2
(cases (c) and (d) to
achieve higher provider pro?ts than same price (case
(b)). For social welfare, PMP with differentiated prices
seem to be always better off.
The numerical results above motivate the goal for this
study, namely, how to settle the question of when PMP
can be guaranteed to yield higher pro?ts, and achieve more
social welfare. We want to answer this question by deriving
conditions on a general class of congestion functions, beyond
just the cases of capacity sharing and latency based services.
Tactically, we study this problem in two steps, by asking
the following questions:
1) How do we ensure the viability of partitioning a ser-
vice class into multiple service classes under identical
pricing?
2) How do we ensure the viability of differentiated pricing
This paper appears in the proceedings of IEEE INFOCOM 2010.
5
m1
m2 p
1
p
2
p
m2 p
1
p, p
2
0.83p
m2 p
1
p, p
2
0.67p
0.0 0.5 1.0 1.5 2.0
p 0.0
0.5
1.0
1.5
Social Welfare S
Fig. 2. Social welfare for capacity sharing service Kcs(Q, C).
m1
m2 p
1
p
2
p
m2 p
1
p, p
2
0.93p
m2 p
1
p, p
2
0.83p
0.0 0.5 1.0 1.5 2.0
p 0.0
0.2
0.4
0.6
0.8
1.0
Profit ?
Fig. 3. Provider pro?t for capacity sharing service Kcs(Q, C).
m1
m2 p
1
p
2
p
m2 p
1
p, p
2
0.83p
m2 p
1
p, p
2
0.63p
0.0 0.5 1.0 1.5 2.0
p 0.0
0.2
0.4
0.6
0.8
Social Welfare S
Fig. 4. Social welfare for latency based service K
lat
(Q, C).
m1
m2 p
1
p
2
p
m2 p
1
p, p
2
0.8p
m2 p
1
p, p
2
0.74p
0.0 0.5 1.0 1.5 2.0
p 0.0
0.1
0.2
0.3
0.4
0.5
Profit ?
Fig. 5. Provider pro?t for latency based service K
lat
(Q, C).
of multiple service classes, as compared with identical
pricing?
Our answers to these questions are elaborated in Sec. V.
V. RESULTS
The viability of PMP boils down to the properties of conges-
tion function. Difference in congestion function (e.g. capacity
sharing service and latency based service) results in very
different consequences. In this section, we provide general
suf?cient conditions by identifying some key properties of
congestion functions associated with the viability of PMP.
A. Viability of Service Partitioning
We ?rst provide insights for the viability of service parti-
tioning, by which one single service class is partitioned into
two service classes, both are priced as same as the original
service class. And each service class is allocated a portion of
capacity of the original service class.
Let p and C be the price and capacity of the original single
service class. Let
˜
? be the cut-off user at equilibrium, and the
total usage be
˜
Q F(
˜
?). Then, the social welfare becomes:
S(p)
_ ˜
?
0
_
V ?? · K(
˜
Q, C)
_
· f(?)d? (14)
and the respective provider pro?t becomes:
?(p) p
˜
Q (15)
After service partitioning, let C
1
and C
2
be the respective
capacity of each service class, where C
1
+C
2
= C. Let ?
1
and
?
2
be the cut-off users at equilibrium of each service class, and
the respective usage be Q
1
F(?
1
)?F(?
2
) and Q
2
F(?
2
).
Because of identical pricing of each service class at p, the
social welfare for the partitioned service classes is
4
:
S(p, p)
_
?2
0
_
V ?? · K(Q
2
, C
2
)
_
· f(?)d?
+
_
?1
?2
_
V ?? · K(Q
1
, C
1
)
_
· f(?)d?
(16)
and the respective provider pro?t is
5
:
?(p, p) p(Q
1
+Q
2
) (17)
We next provide a general suf?cient condition on K(Q, C)
for the viability of service partitioning.
Theorem 1: Suppose 0 ? ? < 1.
1) (Partition-preferred congestion function):
If K(Q, C) ? K(?Q, ?C) for all ?,
S(p, p) ? S(p) and ?(p, p) ? ?(p) (18)
2) (Multiplexing-preferred congestion function):
If K(Q, C) ? K(?Q, ?C) for all ?,
S(p, p) ? S(p) and ?(p, p) ? ?(p) (19)
The proofs are all in the Appendix, unless otherwise stated.
Intuitively, Theorem 1 is separating congestion functions
into two types. The congestion function favoring service
partitioning is one that sees decreased congestion externality
as we scale down the usage and capacity. Alternatively, the
4
In trying to reduce notations, we are going to slightly abuse our use of
notations here. The social welfare for the case of a single class service with
one price p, and the case of multiple service classes with price p will all
be denoted by a function S(.), with different number of price parameters as
appropriate.
5
Again, the same abuse of notation is applied to the pro?t function.
This paper appears in the proceedings of IEEE INFOCOM 2010.
6
congestion function that favors multiplexing (service merging)
is one that sees decreased congestion externality as we scale
up the usage and capacity. Note that a congestion function
K(Q, C) is by de?nition increasing in usage Q, but decreasing
in capacity C. When we scale up both usage and capacity, one
or the other of these factors is more dominating, giving rise
to the two classes of congestion functions.
We next provide some examples to apply Theorem 1.
Example 1: (Capacity Sharing Service) According to the
above de?nition, the capacity sharing service K
cs
(Q, C) is
indifferent of service partitioning or multiplexing:
K
cs
(Q, C) =
Q
C
=
?Q
?C
= K
cs
(?Q, ?C) (20)
Example 2: (Latency Based Service) On the other hand, we
can show that the latency based service K
lat
(Q, C) prefers
multiplexing to service partitioning:
K
lat
(Q, C) =
1
C ?Q
<
1
?(C ?Q)
= K
lat
(?Q, ?C) (21)
Example 3: (General Latency Based Service) Motivated by
Pollaczek-Khinchine formula for M/G/1 queue, we de?ne a
general congestion function for latency based service as:
K
glat
(Q, C) =
Q(1 +C
2
S
)
2C(C ?Q)
+
1
C
, (22)
where C
2
S
is the coef?cient of variation of service time by
convention. Therefore, similarly, we may conclude that service
multiplexing is preferred:
K
glat
(Q, C) <
1
?
K
glat
(Q, C) = K
glat
(?Q, ?C) (23)
Example 4: (Consumption Based Service) We de?ne a new
congestion function as:
K
cb
(Q, C) ?(C ?Q) (24)
For K
cb
(Q, C) the congestion externality is mainly determined
by the remaining unconsumed capacity. This may be useful to
describe certain storage or memory-based services. We show
that the consumption based service K
cb
(Q, C) prefers service
partitioning to multiplexing:
K
cb
(Q, C) = ?(C?Q) > ??(C?Q) = K
cb
(?Q, ?C) (25)
By Theorem 1, it is easy to see that service partitioning
is viable for both capacity sharing and consumption based
services, but not latency based service. Note that Theorem 1
is suf?ciently general, and can be applied to diverse types of
congestion functions.
The following corollary extends Theorem 1 from two
classes to multiple classes.
Corollary 2: Suppose 0 ? ? < 1, and p = (p
i
= p)
m
i=1
.
1) (Partition-preferred congestion function):
If K(Q, C) ? K(?Q, ?C) for all ?,
S(p) ? S(p) and ?(p) ? ?(p) (26)
2) (Multiplexing-preferred congestion function):
If K(Q, C) ? K(?Q, ?C) for all ?,
S(p) ? S(p) and ?(p) ? ?(p) (27)
The proof is straightforward and omitted. Informally, it can
be proved by construction, by continuingly splitting a m-class
service to 2m-class service, starting with m = 2.
B. Viability of Differentiated Pricing
Although Sec. V-A provides the suf?cient condition for
service partitioning with identical pricing, it does not cover
the case of differentiated pricing. Especially, PMP is not
perceivable by identical pricing. In this section, we compare
the social welfare and provider pro?t between differentiated
pricing and identical pricing. Hence, we will rely on the
following property of congestion functions.
De?nition 2: (Monotonic Preference to Service Classes)
Given a ?xed set {C
i
: i = 1, ..., m}, the set of congestion
functions {K(Q
i
, C
i
) : i = 1, ..., m} are subject to:
1) Each K(Q
i
, C
i
) must be strictly increasing and differen-
tiable in Q
i
. Hence, the partial derivative of K(Q
i
, C
i
)
at Q
i
: k(Q
i
, C
i
)
?K(Q,C)
?Q
|
Q=Qi,C=Ci
exists and is
positive.
2) Either one of the following two cases must be true:
(m.1) Q
i
? Q
j
? k(Q
i
, C
i
) ? k(Q
j
, C
j
) for any
distinct pair i, j ? {1, ..., m}.
(m.2) Q
i
? Q
j
? k(Q
i
, C
i
) ? k(Q
j
, C
j
) for any
distinct pair i, j ? {1, ..., m}.
Namely, Def. 2 implies there is a monotonic order on
the derivatives of the m congestion functions. Such a
monotonic order of the derivatives re?ects a monotonic order
of sensitivity of congestions externality among the congestion
functions. Note that homogenous service classes with the
same convex congestion function (i.e. C
i
= C
j
) obviously
satisfy Def. 2. Here, we also allow distinct C
i
to capture the
heterogeneous capacities among different service classes.
Example 5: (Capacity Sharing Service) We show that ca-
pacity sharing service K
cs
(Q, C) satis?es monotonic prefer-
ence to service classes, if C
1
? C
2
? · · · ? C
m
:
k
cs
(Q
i
, C
i
) =
?Kcs(Q,C)
?Q
|
Q=Qi,C=Ci
=
1
Ci
(28)
? k
cs
(Q
1
, C
1
) ? k
cs
(Q
2
, C
2
) ? · · · ? k
cs
(Q
m
, C
m
) (29)
for all 0 ? Q
1
, Q
2
, ..., Q
m
? 1.
Example 6: (Latency Based Service) However, latency
based service K
lat
(Q, C) does not satisfy monotonic prefer-
ence to service classes, even if C
1
? C
2
? · · · ? C
m
. Because
k
lat
(Q
i
, C
i
) =
?K
lat
(Q, C)
?Q
|
Q=Qi,C=Ci
=
1
(C
i
?Q
i
)
2
(30)
which is not a monotonic function in C
i
or Q
i
. One can show
similarly for general latency based service.
This paper appears in the proceedings of IEEE INFOCOM 2010.
7
Example 7: (Consumption Based Service) We show that
consumption based service K
cb
(Q, C) also satis?es monotonic
preference to service classes:
k
cb
(Q
i
, C
i
) =
?K
cb
(Q,C)
?Q
|
Q=Qi,C=Ci
= 1 (31)
? k
cb
(Q
1
, C
1
) = k
cb
(Q
2
, C
2
) = · · · = k
cb
(Q
m
, C
m
) (32)
for all 0 ? Q
1
, Q
2
, ..., Q
m
? 1.
Theorem 3: Given two service classes that satisfy mono-
tonic preference (Def. 2), the social welfare of identical pricing
at p is strictly inferior to differentiated pricing for some
p
1
= p
2
:
S(p
1
, p
2
) > S(p, p) (33)
One might not be surprised to see that the differentiated
pricing (p
1
= p
2
) could be better than identical pricing
(p
1
= p
2
). But what is remarkable is the strict superiority
of differentiated pricing. This can be extended to the case for
m service classes in the following corollary.
Corollary 4: Given m service classes that satisfy mono-
tonic preference (Def. 2), let p (p
i
= p)
m
i=1
, then there
exists p
(p
i
)
m
i=1
, such that p
i
= p
j
for all distinct
i, j ? {1, ..., m},
S(p
) > S(p) (34)
We can prove the same results for provider pro?t:
Theorem 5: Given two service classes that satisfy mono-
tonic preference (Def. 2), the provider pro?t of identical
pricing at p is strictly inferior to differentiated pricing for some
p
1
= p
2
:
?(p
1
, p
2
) > ?(p, p) (35)
Corollary 6: Given m service classes that satisfy mono-
tonic preference (Def. 2), let p (p
i
= p)
m
i=1
, then there
exists p
(p
i
)
m
i=1
, such that p
i
= p
j
for some distinct
i, j ? {1, ..., m},
?(p
) > ?(p) (36)
Corollary 6 is an immediate consequence of Theorem 5.
Note that Corollary 6 is weaker than Corollary 4.
Finally, we arrive at the point where we can provide a more
complete answer to our original question, on the viability of
PMP. Combining Theorems 1, 3 and 5, we have a suf?cient
condition to guarantee PMP to be viable, in the sense of both
provider pro?t as well as social welfare. This also explains
clearly why PMP is viable for capacity sharing services and
consumption based services, but not for latency based services.
The Theorems 1-5 are suf?ciently general, so that they can also
be applied to answer more questions about PMP.
VI. CONCLUSION AND DISCUSSION
This paper provides general conditions for the viability of
Paris Metro Pricing, based on a general model of congestion
externality. There are two separate messages here, both can
be intuitively stated. The ?rst one says that your system either
prefers multiplexing (having more people share proportionally
more capacity), or not; if you want to guarantee a gain (in
terms of pro?t or social welfare) by dividing your system into
multiple classes with the same price, then your system better
not prefer multiplexing. The second message says that if you
start with a multi-class system with the same price and you
want to move to charging different prices, then the service
classes you set up better generate monotonic preferences
among your users. By combining these two rules together,
we can characterize a large class of systems that can bene?t
from PMP. These observations also help us understand why
sometimes PMP is not viable. Our results help clarify the
confusion caused by con?icting conclusions on the viability of
PMP by previous studies. Our model is general, and the results
are rigorously proved and are applicable to future studies on
network pricing. In the future work, we will extend our study
to a more sophisticated setting with rate control and adaptation
among the users under PMP.
ACKNOWLEDGMENT
The authors would like to thank Richard Gibbens,
Vishal Misra and the reviewers for suggestions. Dah-Ming
Chiu acknowledges the support from NSFC-RGC grant
N CUHK414/06. Chi-Kin Chau is grateful to The Croucher
Foundation for ?nancial support. This research is continuing
through the participation in the International Technology Al-
liance sponsored by the U.S. Army Research Laboratory and
the U.K. Ministry of Defence.
REFERENCES
[1] J. K. MacKie-Mason and H. R. Varian, “Pricing congestible network
resource,” IEEE Journal Selected Areas in Communications, vol. 13,
no. 7, pp. 1141–1149, 1995.
[2] S. Shenker, D. Clark, D. Estrin, and S. Herzog, “Pricing in computer
networks: Reshaping the research agenda,” ACM Computer Communi-
cation Review, vol. 26, no. 2, pp. 19–43, 1996.
[3] C. K. Chau and K. M. Sim, “Analyzing the impact of sel?sh behaviors
of Internet users and operators,” IEEE Communications Letters, vol. 7,
no. 9, pp. 463–465, September 2003.
[4] A. Odlyzko, “Should ?at-rate internet pricing continue?” IT Profes-
sional, vol. 2, pp. 48–51, 2000.
[5] ——, “Paris metro pricing for the internet,” in Proc. ACM Conf. on
Electronic Commerce, 1999, pp. 140–147.
[6] R. Gibbens, R. Mason, and R. Steinberg, “Internet service classes under
competition,” IEEE Journal Selected Areas in Communications, vol. 18,
no. 2, pp. 2490–2498, 2000.
[7] R. Jain, T. Mullen, and R. Hausman, “Analysis of Paris Metro pricing
strategy for QoS with a single service provider,” in Proc. IEEE/IFIP
Intl. Workshop on Quality of Service, 2001, pp. 495–500.
[8] D. Ros and B. Tuf?n, “A mathematical model of the Paris Metro pricing
scheme for charging packet networks,” Computer Networks, vol. 46, pp.
73–85, 2004.
[9] K. Kalevi, Differentiated services for the internet. Macmillan, 1999.
[10] O. Haimanko and R. Steinberg, Price Symmetry in a Duopoly with
Congestion, December 2000, CORE Discussion Paper.
[11] H. Sakurai, S. Kasahara, and N. Adachi, “Internet pricing and user
opt-out strategy under two ISPs competition,” in Proc. Intl. Network
Optimization Conf. (INOC), 2003, pp. 495–500.
[12] P. Chander and L. Leruth, “The optimal product mix for a monopo-
list in the presence of congestion effects,” Intl. Journal of Industrial
Organization, vol. 7, no. 4, pp. 437–449, 1989.
[13] A. de Palma and L. Leruth, “Congestion and game in capacity: A
duopoly analysis in the presence of network externalities,” Annales
d’Economie et de Statistique, no. 15–16, pp. 389–407, 1989.
[14] S. Shakkottai, R. Srikant, A. Ozdaglar, and D. Accemoglu, “The price
of simplicity,” IEEE Journal Selected Areas in Communications, vol. 26,
no. 7, pp. 1269–1276, 2007.
This paper appears in the proceedings of IEEE INFOCOM 2010.
8
VII. APPENDIX
A. Proof for Theorem 1
Proof: First, by Eqn. (11) in Def. 1, for a single service
class, we obtain:
p = V ?
˜
? · K
_
˜
Q, C
_
?
˜
? =
V ?p
K
_
˜
Q, C
_ (37)
Also, for partitioned service classes, we obtain:
_
p ?p =?
2
·
_
K
_
Q
2
, C
2
_
?K
_
Q
1
, C
1
_
_
p =V ??
1
· K
_
Q
1
, C
1
_ (38)
Hence, Eqn. (38) follows that
K
_
Q
2
, C
2
_
= K
_
Q
1
, C
1
_
(39)
?
1
=
V ?p
K(Q
1
, C
1
_ (40)
Using Eqns. (37) and (40), we obtain the following equality:
˜
?
?
1
=
K(Q
1
, C
1
)
K(
˜
Q, C)
=
K(Q
2
, C
2
)
K(
˜
Q, C)
(41)
Step 1: Then, we want to show:
1) If K(Q, C) ? K(?Q, ?C) for all ?, then ?
1
?
˜
?
2) If K(Q, C) ? K(?Q, ?C) for all ?, then ?
1
?
˜
?
Without loss of generality, we assume C
1
? C
2
. Let ?
C1
C
,
and hence, we have ? ? 1 ??.
First, we consider partition-preferred congestion function:
K(Q, C) ? K(?Q, ?C) for all ?. By Eqn. (39), it follows
that:
K(Q
2
, C
2
) = K(Q
1
, C
1
) ? K(
1 ??
?
Q
1
, C
2
) (42)
Because K(Q, C) is increasing in Q, we obtain:
Q
2
?
1 ??
?
Q
1
? Q
1
+Q
2
?
Q
1
?
(43)
Because K(Q, C) ? K(?Q, ?C) for all ?, we obtain:
K(
˜
Q, C) ? K
_
?
˜
Q, ?C
_
= K
_
?
˜
Q, C
1
_
(44)
We next use contradiction to show ?
1
?
˜
?. On the contrary,
we suppose
˜
? > ?
1
. Then, by Eqns. (41) and (44), we obtain:
K
_
Q
1
, C
1
_
> K
_
˜
Q, C
_
? K
_
?
˜
Q, C
1
_
(45)
Hence, Q
1
> ?
˜
Q, because K(Q, C) is increasing in Q.
Also, we note that
˜
? > ?
1
? F(
˜
?) > F(?
1
) ?
˜
Q > Q
1
+Q
2
(46)
Therefore, we derive that
Q
1
> ?
˜
Q > ?(Q
1
+Q
2
) (47)
which is a contradiction to Eqn. (43). Hence, it should be
?
1
?
˜
?. Similarly, we can show for merge effect: K(Q, C) ?
K(?Q, ?C) for all ? implies ?
1
?
˜
?.
Step 2: Finally, we want to show:
1) If ?
1
?
˜
?, then S(p, p) ? S(p) and ?(p, p) ? ?(p).
2) If ?
1
?
˜
?, then S(p, p) ? S(p) and ?(p, p) ? ?(p).
The case of provider pro?t ?(p, p) and ?(p) follows from
Eqns. (14) and (17), and
?
1
?
˜
? ? Q
1
+Q
2
?
˜
Q and ?
1
?
˜
? ? Q
1
+Q
2
?
˜
Q (48)
For the case of social welfare, by Eqn. (39), we obtain:
S(p, p) =
_
?1
0
_
V ?? · K(Q
2
, C
2
)
_
· f(?)d? (49)
From Eqn. (41), we obtain:
?
1
?
˜
? ? K
_
˜
Q, C
_
? K
_
Q
2
, C
2
_
(50)
?
1
?
˜
? ? K
_
˜
Q, C
_
? K
_
Q
2
, C
2
_
(51)
By Eqns. (15) and (48)-(51), we complete the proof.
B. Proof for Theorem 3
Proof: First, we write S = S(p
1
, p
2
). We study how the
total differential of S, dS, changes at p
1
= p
2
. From Eqn. (16),
S = V · F(?
1
) ?K(Q
2
, C
2
)
_
?2
0
? · f(?)d?
?K(Q
1
, C
1
)
_
?1
?2
? · f(?)d?
(52)
Recall that k(Q
i
, C
i
)
?K(Q,C)
?Q
|
Q=Qi,C=Ci
, Q
2
F(?
2
)
and Q
1
F(?
1
) ?F(?
2
).
An equilibrium can be characterized by (p
1
, p
2
), a pair
of independent variables. Similarly, an equilibrium can be
equivalently characterized by (?
1
, ?
2
), by solving Eqn. (11)
in Def. 1. Then (?
1
, ?
2
) are treated as a pair of independent
variables. Thus, we take the total differential of S with respect
to the differentials of variables (?
1
, ?
2
):
dS = V · f(?
1
)d?
1
?
_
_
?2
0
? · f(?)d?
_
· k(Q
2
, C
2
)f(?
2
)d?
2
?K(Q
2
, C
2
) · ?
2
· f(?
2
)d?
2
?
_
_
?1
?2
? · f(?)d?
_
· k(Q
1
, C
1
)
_
f(?
1
)d?
1
?f(?
2
)d?
2
_
?K(Q
1
, C
1
) ·
_
?
1
· f(?
1
)d?
1
??
2
· f(?
2
)d?
2
_
(53)
Then, at identical pricing p
1
= p
2
? K(Q
1
, C
1
) =
K(Q
2
, C
2
). Hence, we obtain:
dS|
p1=p2
= V · f(?
1
)d?
1
?
_
_
?2
0
? · f(?)d?
_
· k(Q
2
, C
2
)f(?
2
)d?
2
?
_
_
?1
?2
? · f(?)d?
_
· k(Q
1
, C
1
)
_
f(?
1
)d?
1
?f(?
2
)d?
2
_
?K(Q
1
, C
1
) · ?
1
· f(?
1
)d?
1
(54)
Next, we pick a vector d?
1
+d?
2
, and show that dS|
p1=p2
will
strictly increase in the direction of d?
1
+ d?
2
. Such a vector
This paper appears in the proceedings of IEEE INFOCOM 2010.
9
indeed exists if we keep ?
1
as a constant (i.e. d?
1
= 0). First,
we obtain:
dS|
p1=p2,d?1=0
=
_
_
_
?1
?2
? · f(?)d?
_
· k(Q
1
, C
1
)
?
_
_
?2
0
? · f(?)d?
_
· k(Q
2
, C
2
)
_
f(?
2
)d?
2
(55a)
> ?
2
·
_
_
_
?1
?2
f(?)d?
_
· k(Q
1
, C
1
)
?
_
_
?2
0
f(?)d?
_
· k(Q
2
, C
2
)
_
f(?
2
)d?
2
(55b)
= ?
1
_
Q
1
· k(Q
1
, C
1
) ?Q
2
· k(Q
2
, C
2
)
_
f(?
2
)d?
2
(55c)
Since the two service classes satisfy monotonic preference
(Def. 2), if we always pick d?
2
> 0 in the case of (m.1),
and d?
2
< 0 in the case of (m.2), then it is always true
that dS|
p1=p2,d?1=0
> 0. Therefore, this shows that the
social welfare S can strictly increase by differentiated pricing
(p
1
= p
2
) from identical pricing (p
1
= p
2
).
C. Proof for Corollary 4
Proof: By Theorem 3, it is true for m = 2. For m = 3,
it follows that p
1
= p
2
= p
3
cannot be optimal. Next, we also
show that p
1
> p
2
= p
3
and p
1
= p
2
> p
3
cannot be optimal.
Then, the total differential of social welfare S becomes:
dS = V · f(?
1
)d?
1
?
_
_
?3
0
? · f(?)d?
_
· k(Q
3
, C
3
)f(?
3
)d?
3
?K(Q
3
, C
3
) · ?
3
· f(?
3
)d?
3
?
_
_
?2
?3
? · f(?)d?
_
· k(Q
2
, C
2
)
_
f(?
2
)d?
2
?f(?
3
)d?
3
_
?K(Q
2
, C
2
) ·
_
?
2
· f(?
2
)d?
2
??
3
· f(?
3
)d?
3
_
?
_
_
?1
?2
? · f(?)d?
_
· k(Q
1
, C
1
)
_
f(?
1
)d?
1
?f(?
2
)d?
2
_
?K(Q
1
, C
1
) ·
_
?
1
· f(?
1
)d?
1
??
2
· f(?
2
)d?
2
_
(56)
For p
1
> p
2
= p
3
(i.e. K(Q
2
, C
2
) = K(Q
3
, C
3
)), setting
d?
1
= d?
2
= 0 will degenerate to the case m = 2. For p
1
=
p
2
> p
3
(i.e. K(Q
1
, C
1
) = K(Q
2
, C
2
)), setting d?
1
= d?
3
=
0 will also degenerate to the case m = 2. Hence, it follows
for m = 3 is true. Using an iterative argument, we can show
that it is true for all m ? 2.
D. Proof for Theorem 5
Proof: Similar to Theorem 3, taking the total differential
of ? with respect to the differentials of variables (p
1
, p
2
):
d? = Q
2
dp
2
+p
2
· f(?
2
)
_
??
2
?p
1
dp
1
+
??
2
?p
2
dp
2
_
+Q
1
dp
1
+p
1
·
_
f(?
1
)
_
??
1
?p
1
dp
1
+
??
1
?p
2
dp
2
_
?f(?
2
)
_
??
2
?p
1
dp
1
+
??
2
?p
2
dp
2
_
_
(57)
Then, at identical pricing (p
1
= p
2
), we obtain:
d?|
p2=p1
= Q
2
dp
2
+Q
1
dp
1
+p
1
· f(?
1
)(
??
1
?p
1
dp
1
+
??
1
?p
2
dp
2
)
(58)
Similar to Theorem 3, we pick a vector dp
1
+dp
2
, and show
that d?|
p1=p2
will strictly increase in the direction of dp
1
+
dp
2
. To achieve so, we keep ?
1
as a constant (i.e. d?
1
=
??1
?p1
dp
1
+
??1
?p2
dp
2
= 0). Hence,
d?|
p1=p2,d?1=0
= Q
1
dp
1
+Q
2
dp
2
(59)
Also, from Eqn. (11) in Def. 1, keeping ?
1
as a constant (i.e.
d?
1
= 0), we obtain the total differentials (p
1
, p
2
) with respect
to ?
2
as:
_
¸
¸
_
¸
¸
_
dp
1
= ?
1
· k(Q
1
, C
1
)f(?
2
)d?
2
dp
1
?dp
2
= ?
2
·
_
k(Q
2
, C
2
) +k(Q
1
, C
1
)
_
· f(?
2
)d?
2
+
_
K(Q
2
, C
2
) ?K(Q
1
, C
1
)
_
d?
2
(60)
where k(Q
i
, C
i
)
?K(Q,C)
?Q
|
Q=Qi,C=Ci
.
Since at identical pricing p
1
= p
2
? K(Q
1
, C
1
) =
K(Q
2
, C
2
), we have
_
dp
1
= ?
1
· k(Q
1
, C
1
)f(?
2
)d?
2
dp
1
?dp
2
= ?
2
·
_
k(Q
2
, C
2
) +k(Q
1
, C
1
)
_
· f(?
2
)d?
2
(61)
Solving Eqn. (61) for (dp
1
, dp
2
), we obtain:
dp
2
=
??
2
· (k(Q
2
, C
2
) +k(Q
1
, C
1
)) +?
1
· k(Q
1
, C
1
)
?
1
· k(Q
1
, C
1
)
dp
1
(62)
Because we keep ?
1
as a constant (i.e. d?
1
= 0), by substitut-
ing Eqn. (62) we obtain:
d?|
p1=p2,d?1=0
= Q
2
dp
2
+Q
1
dp
1
=
_
Q
2
·
_
??
2
· (k(Q
2
, C
2
) +k(Q
1
, C
1
)) +?
1
· k(Q
1
, C
1
)
_
+Q
1
?
1
· k(Q
1
, C
1
)
_
dp
1
?
1
· k(Q
1
, C
1
)
(63a)
=
_
?Q
2
?
2
· (
k(Q
2
, C
2
)
k(Q
1
, C
1
)
) ?Q
2
?
2
+Q
2
?
1
+Q
1
?
1
_
dp
1
?
1
>
_
?Q
2
· (
k(Q
2
, C
2
)
k(Q
1
, C
1
)
) ?Q
2
+Q
2
+Q
1
_
?
2
dp
1
?
1
(63b)
=
_
Q
1
· k(Q
1
, C
1
) ?Q
2
· k(Q
2
, C
2
)
_
?
2
dp
1
?
1
· k(Q
1
, C
1
)
(63c)
Since the two service classes satisfy monotonic preference
(Def. 2), if we always pick d?
2
> 0 in the case of (m.1),
and d?
2
< 0 in the case of (m.2), then it is always true
that d?|
p1=p2,d?1=0
> 0. Therefore, the provider pro?t ?
can strictly increase by differentiated pricing (p
1
= p
2
) from
identical pricing (p
1
= p
2
).
This paper appears in the proceedings of IEEE INFOCOM 2010.
doc_286585872.pdf