# the_competitive_effects_of_variancebased_pricing__28df18fa.pdf

The Competitive Effects of Variance-based Pricing

Ludwig Dierks and Sven Seuken Department of Informatics, University Zurich dierks@iﬁ.uzh.ch, seuken@iﬁ.uzh.ch

In many markets, like electricity or cloud computing markets, providers incur large costs for keeping sufﬁcient capacity in reserve to accommodate demand ﬂuctuations of a mostly ﬁxed user base. These costs are signiﬁcantly affected by the unpredictability of the users demand. Nevertheless, standard mechanisms charge ﬁxed per-unit prices that do not depend on the variability of the users demand. In this paper, we study a variance-based pricing rule in a two-provider market setting and perform a game-theoretic analysis of the resulting competitive effects. We show that an innovative provider who employs variance-based pricing can choose a pricing strategy that guarantees himself a higher proﬁt than using ﬁxed per-unit prices for any individually rational response of a provider playing a ﬁxed pricing strategy. We then characterize all equilibria for the setting where both providers use variance-based pricing strategies. We show that, in equilibrium, the providers proﬁts may increase or decrease, depending on their cost functions. However, social welfare always weakly increases.

1 Introduction In most markets with mostly ﬁxed user bases, providers costs are largely driven by how much buffer capacity they must keep in reserve. This, in turn, depends on the variance of their users demand. However, the predominant pricing mechanisms employed in practice do not take this effect into account. Instead, prices are typically set on a per-unit basis, such that every user pays the same for the same product. In electricity markets, for example, a provider has to make long-term supply decisions. But in real-time, supply and demand always have to be perfectly balanced, which requires a costly buffer infrastructure [Cramton, 2017]. If users would always consume (almost) the same amount of energy, this buffer could be far smaller than with widely varying user demands. Nevertheless, users pay simple per MW/h prices. Next, consider the market for mobile data. Mobile network providers continuously expand their cell tower infrastructure to be able to satisfy their users bandwidth needs under peak demand [L opez-P erez et al., 2009]. However, most end-users

pay a ﬁxed per-gigabyte-price, independent of when they consume it or how variable their demand is.1 Finally, consider cloud computing markets, where cloud providers must keep buffers of idle capacity in each compute cluster to handle changing resource demands of already running jobs. Handling the variance of cloud users is particularly difﬁcult given that the resource needs of an individual job may vary by a factor of 10 or 100 over time (see Dierks et al. [2019]). In this domain, the mixture of user types (i.e., their average demand variance) signiﬁcantly affects the providers need to supply buffer capacity. Nevertheless, most cloud resources are sold for a ﬁxed price per core-hour, without regard to the variability of the users demand.

Managing Demand via Sophisticated Pricing. Classic approaches for dealing with varying demand include dynamic pricing and congestion-based pricing [Muratori and Rizzoni, 2015; Rong et al., 2018; Truong-Huu and Tham, 2014]. These approaches focus on ﬂattening demand peaks. A big downside is that they make it unpredictable for users whether they can obtain the product at a given price when they need it. This puts providers who serve risk-averse users or users with relatively uniform but inelastic demand at a competitive disadvantage. In some markets, like cloud computing, this effect is so strong that providers never consider dynamic pricing for their primary market offerings [Dierks and Seuken, 2019]. The effect even greatly hinders the adoption of dynamic pricing in more suitable domains, like electricity markets [Joskow and Wolfram, 2012], where customers are instead often only exposed to ﬁxed time-of-use tariffs [Urieli and Stone, 2016; Celebi and Fuller, 2012].

Variance-based Pricing. In this paper, we study variancebased pricing, where part of the price the users pay depends on the variance of their demand. Variance-based pricing was recently proposed by Dierks et al. [2019] to reduce costs by improving the demand prediction ability of a monopolistic cloud provider. For a provider, in general markets, variancebased pricing has the advantage that his low-variance users pay lower prices and are thus impacted less by the buffer requirements (which are mainly caused by high-variance users). This is not only fairer, but importantly, it incentivizes users to reduce their variance, which in turn reduces the provider s

1Even in high-GDP countries, less than 10% of customers have unlimited data plans [Ericsson, 2017].

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

costs. In a monopolistic setting, the provider can obviously use variance-based pricing to increase his proﬁts. However, in a competitive market environment, the effects are unclear, because the competitive pricing pressure by other providers may limit what he can achieve with variance-based pricing. Overview of our Approach. We analyze a duopoly of providers who compete for a continuum of user types. We assume that the two providers consider the long-term effect of their pricing strategies on their proﬁts. Since each provider has to provision enough capacity to guarantee service quality even during demand spikes, the cost per unit of a product depends on the average variance of the users he attracts. Each provider either conservatively employs constant perunit prices or is willing to innovate and employ per-unit prices that linearly depend on each user s variance. We restrict ourself to linear prices here, because their simplicity makes them most plausible and marketable in practice. We show that, as long as a provider s costs are not far larger than the costs of his competitor, unilaterally switching to variance-based pricing can be used to obtain a higher proﬁt for any reasonable constant response of the other provider. We then characterize all equilibria that arise if both providers employ variancebased pricing. We also show that, as long as providers are not symmetric in their cost functions, the proﬁts of both providers often increase, as they can attract user types which they can better serve due to their respective cost functions. Finally, we show that the welfare may decrease if only one provider employs variance-based pricing, but that it at least weakly increases if both employ variance-based pricing. Related Work. Variance-based pricing is a type of price discrimination [Varian, 1989; Mussa and Rosen, 1978]. However, in contrast to the classic price discrimination settings [Moorthy, 1984; Blattberg and Wisniewski, 1989; Gallego et al., 2006], variance-based pricing does not discriminate based on user preferences. Furthermore, in our model, there is neither a ﬁxed marginal cost of supplying a given user nor do costs depend solely on the number of supplied products. As long as neither provider charges for variance, they cannot price discriminate at all and the problem becomes similar to a Bertrand competition [Baye and Kovenock, 2017]. In order to isolate the competitive effects caused by variance-based pricing, we assume that both providers offer the same product; thus, product differentiation (e.g., [Feng et al., 2013]) does not take place.

2 Preliminaries We consider a market setting with two providers and a continuum of users to which the providers want to sell their products. We study a simple two-period model: in the ﬁrst period, the providers choose their pricing strategies; in the second period, the users choose a provider to buy the product from.

2.1 Formal Model Each user is associated with a real-valued type t [0, tmax]. We keep this type general, but in practice it can be assumed to encode the variance of a user s demand. To keep the notation simple, we normalize each user s expected demand to 1. For a randomly chosen user, her type is distributed as a continuous

random variable with pdf f(t) and cdf F(t). We do not model ﬂuctuations in the mixture of user types over time. Each provider s strategy space consists of his choice of price function ρi. We restrict ρi = (pf i , pℓ i) to a ﬁxed price pf i per unit of the product (independent of the user type) and a second linearly type-based charge pℓ it per unit of the product.2 The overall payment per unit of the product for a user with type t is given by ρi(t) = pf i + pℓ it. Going forward, we refer to providers that are willing to choose any pf i , pℓ i R as innovative and those who do not adopt the new pricing scheme and restrict themselves to pℓ i = 0 as conservative. Given the provider s price functions, and depending on a user s own type, each user chooses to obtain the product either from provider 1 or 2. We denote a strategy proﬁle for all user types by σ(t) : [0, tmax] {1, 2}. In this paper, we do not model the users values for product consumption.3 Consequently, the users utility function is simply equal to their negative payments. Throughout the paper, given price functions (ρ1, ρ2), we assume that users only play utilitymaximizing (i.e., payment minimizing) user strategy proﬁles. Formally, we assume that σ(t) = argmini {ρi(t)} for all t. As we will see, it is often in a provider s best interest to play essentially the same strategy as their opponent, which makes tie-breaking rules for the user sub-game very important. To avoid that tie breaking for ρ1 = ρ2 gives rise to arbitrary user strategy proﬁles that would not arise in practice, we restrict user strategy proﬁles to those at least one provider can enforce by deviating from (ρ1, ρ2) at only an inﬁnitesimal proﬁt loss. Formally, we say that a user strategy proﬁle σ is enforceable at (ρ1, ρ2) if for one provider i {1, 2} there exists a sequence of pricing functions (ρk i ) k=1 such that σ is the limit of the user strategy proﬁles that are uniquely (up to a null set) utility maximizing for each (ρk i ,ρ i). With linearly type-based prices, this limits the user strategy proﬁles to any form where all users with type greater than some cutoff point ˆt join one provider i and those with lower type join the other provider. To denote this, we also write σ = [0, ˆt] i or σ = [ˆt, tmax] i. Note that this allows for the unique representation of any σ, as all other users choose the other provider. Further, we denote by µ(a, b) the average type of

all users with type in [a, b], i.e., µ(a, b) =

R b a f(t)tdt F (b) F (a). A provider s costs for serving a given user do not only depend on how many units of his product he sells to that user, but also on how many units the provider has to supply for all users. Consequently, a provider s cost function ci(σ) is a function of the whole user strategy proﬁle σ and cannot be separated into independent costs for individual users. We assume that ci(σ) is strictly increasing in the expected type of a randomly drawn user who joins provider i s market under σ.

2As supply decisions (and therefore costs) do not depend on a user s true type but on the type the provider predicts for a user, we assume that providers know each realized user s type. In practice, user bases are often mostly ﬁxed, such that a provider can learn each user s type over time. 3In the markets we study, essentially every user is served by some provider, as costs are very low compared to most users values and competition ensures that prices are close to costs.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Overloading notation, we also write ci(a, b) for provider i s cost if all users in [a, b] (and no other users) choose him. In many applications, splitting a given population of users between two identical providers causes higher overall costs than if one provider would obtain all users, as that one provider could always provision for both sub-populations separately. We call such cost functions that are convex in relation to splitting the market split-convex, i.e. ci() is splitconvex if for all ˆt [0, tmax] it holds that

F(ˆt)c1(0, ˆt) + (1 F(ˆt))c1(ˆt, tmax) c1(0, tmax).

If the inequality is strict for all ˆt [0, tmax], we call the cost function strictly split-convex. A provider s utility is his expected proﬁt πj per customer in a population, which is given by

πj(ρ1, ρ2, σ) = Z

t:σ(t)=j (ρj(t) cj(σ))f(t)dt. (1)

Given this model, we call a strategy ρi for provider i {1, 2} an individually rational response to any given strategy ρ i of the other provider if there exists an enforceable utility-maximizing user strategy proﬁle σ that gives provider i weakly positive proﬁt, i.e., πi(ρi, ρ i, σ) 0.

2.2 Equilibrium Concept We use the following equilibrium concept for our analysis. Deﬁnition 1. A tuple (ρ1, ρ2, σ) is a Bayes-Nash equilibrium (BNE) if σ is utility maximizing for (ρ1, ρ2) and, for i {1, 2}, there exist no ˆρi = ρi and ˆσ such that ˆσ is utility maximizing for (ˆρi, ρ i) and πi(ˆρi, ρ i, ˆσ) > πi(ρi, ρ i, σ). (2) Note that when ρ1 = ρ2, users are indifferent between all user strategy proﬁles, but our equilibrium deﬁnition mandates that tie breaking is done in such a way that no provider has an incentive to deviate inﬁnitesimally only to secure himself a different user strategy proﬁle. In practice, a combination of external factors and bounded rationality imply that providers do not move their prices to a tie or even inﬁnitesimally close to each other, at best achieving ϵ BNEs. Essentially, price differentiations that are too small are not marketable.

3 Proﬁt Analysis with Conservative Providers We ﬁrst analyze the case where both providers are conservative, i.e., restricted to pℓ 1 = pℓ 2 = 0. Since they cannot split the market through pricing differences, the resulting game is similar to a classic Bertrand competition. Thus, if the providers costs for the whole population are symmetric, they cannot extract any proﬁt, while for non-symmetric providers, the provider with lower costs for serving the whole market can potentially extract the cost difference as a proﬁt. Proposition 1. Let both providers be conservative, i.e., pℓ 1 = pℓ 2 = 0. W.l.o.g. assume c1(0, tmax) c2(0, tmax). Then in any BNE (ρ1, ρ2, σ) the following holds:

pf 1 = pf 2 [c1(0, tmax), c2(0, tmax)] (3) and π1(ρ1, ρ2, σ) =pf 1 c1(0, tmax) (4) π2(ρ1, ρ2, σ) =0 (5)

Proof. Note that any tuple (ρ1, ρ2, σ) with pf 1 = pf 2 [c1(0, tmax), c2(0, tmax)] and σ = [0, tmax] 1 is a BNE as neither provider has an advantageous deviation. All users already choose provider 1, so decreasing his price only reduces his proﬁt, while any price increase makes him lose all users. Since all users choose him, his proﬁt is simply π1(ρ1, ρ2, σ) = pf 1 c1(0, tmax). Any lower price for provider 2 on the other hand would lead to all users choosing him, but he would make a negative proﬁt per user. Increasing his price would have no effect on his proﬁt, as no users choose him. Without users, he trivially makes zero proﬁt. As a special case, when c1(0, tmax) = c2(0, tmax), then, by the same argument, pf 1 = pf 2 = c2(0, tmax) with σ = [0, tmax] 2 is an additional BNE, with both providers obtaining zero proﬁt. We now show that these are the only BNEs, by showing that any other potential BNE leads to a contradiction. First, note that when pf 1 < pf 2, every user strictly prefers provider 1. But there always exists a ˆpf 1 with pf 1 < ˆpf 1 < pf 2 for which every user still strictly prefers provider 1, but with a higher payment. Therefore, pf 1 = pf 2 has to hold in equilibrium. If pf 1 = pf 2 < c1(0, tmax), provider 1 would make a loss for every user. On the other hand, if pf 1 = pf 2 > c2(0, tmax), then for any σ = [0, tmax] i, the other provider i would have an advantageous deviation in any ˆpf i with c2(0, tmax) < ˆpf i < pf 1 = pf 2. Taken together, this means that there can be no other BNE than those characterized by the proposition.

Going forward, we denote BNEs with two conservative providers as constant BNEs. Note that, while all pf 1 = pf 2 [c1(0, tmax), c2(0, tmax)] are equilibrium prices, the only reason why any pf 1 = pf 2 < c2(0, tmax) does not lead to a loss for provider 2 is because he obtains no users. This makes pf 1 = c2(0, tmax) the only non-pathological BNE.

4 Proﬁt Analysis with Innovative Providers

In this section, we analyze the proﬁt when one or both providers are innovative. As a ﬁrst step, we show that, given a strategy of provider 2, provider 1 s proﬁt is upper bounded by the proﬁt he could achieve if he would play the same strategy as provider 2 (and if he could select the utility-maximizing user strategy proﬁle that is most favorable to him).

Proposition 2. Assume provider 2 plays strategy ρ2 = (pf 2, pℓ 2). Then, for all ρ1 = ρ2, ρ 1 = ρ2, and all σ that are utility maximizing for ρ1, ρ2, it holds that π1(ρ1, ρ2, σ) = 0 or π1(ρ1, ρ2, σ) < π1(ρ 1, ρ2, σ).

Proof. First note that for any ρ1 = ρ2, by the linearity of the price function, there exists a unique ˆt at which payments in both markets are the same, i.e., pf 1 + ˆtpℓ 1 = pf 2 + ˆtpℓ 2 (note that ˆt can be outside [0, tmax]). For any utility-maximizing σ, users with type below ˆt choose one provider and those above the other. Now consider some ρ1 = ρ2, π1(ρ1, ρ2, σ) > 0 with ˆt being the corresponding cutoff. If pf 1 pf 2, pℓ 1 pℓ 2, then any utility-maximizing user strategy proﬁle is of the

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

form σ = [0, t] 1 for t = min(ˆt, tmax) and it holds that

π1(ρ1, ρ2, σ) = Z t

0 f(t)(pf 1 + tpℓ 1 c1(0, t))dt (6)

0 f(t)(pf 2 + ˆtpℓ 2 ˆtpℓ 1 + tpℓ 1 c1(0, t))dt (7)

0 f(t)(pf 2 + ˆtpℓ 2 c1(0, t))dt (8)

=π1(ρ2, ρ2, σ). (9)

The proof works analogously for pf 1 pf 2, pℓ 1 pℓ 2.

It directly follows that in all BNEs, both providers play the same strategy, even if one provider is conservative. Corollary 1. In all BNEs it holds that ρ1 = ρ2. We now separately consider the cases where either only one or both providers are willing to employ linear pricing.

4.1 One Provider is Innovative Corollary 1 suggests that only one provider being innovative precludes the existence of a BNE. In the following theorem we show that this is indeed true, unless both providers cost functions are very close to each other. Theorem 1. Let provider 2 be conservative, i.e., pℓ 2 = 0, and provider 1 be innovative. Then there exists a BNE if and only if there exists no ˆt [0, tmax] with

c1(0, tmax) F(ˆt)c1(0, ˆt) (10)

(1 F(ˆt))(c1(0, tmax) c2(0, tmax)). (11)

If a BNE exists then it is equal to a constant BNE.

Proof. By Corollary 1, in all BNEs, both providers use constant pricing functions and for any constant pricing functions that are not part of a constant BNE there exist constant deviations. By Proposition 2, any deviation of provider 1 from a constant BNE is worse than him freely choosing the user strategy proﬁle and not changing his pricing function. He can enforce any user strategy proﬁle where he only obtains users with types lower than some ˆt. Thus, if (ρ1, ρ2, [0, tmax] 1) is a constant BNE, then it is still a BNE when provider 1 is innovative as long as there exists no ˆt < tmax such that [0, ˆt] 1 leads to a higher proﬁt than taking the whole market, i.e.,

c1(0, tmax) F(ˆt)c1(0, ˆt) (12)

<(1 F(ˆt))(c1(0, tmax) c2(0, tmax)). (13)

Otherwise [0, tmax] 1 cannot be a BNE user strategy proﬁle. Finally, for all (ρ1, ρ2, [0, ˆt] 1) with ˆt < tmax, the users that choose provider 2 have a higher average variance than the average variance of all users. Consequently, c2(0, tmax) < c2(ˆt, tmax). As prices are constant, provider 2 either makes negative proﬁt (and deviates) or he increases his proﬁt by slightly decreasing his price and taking the whole market.

Theorem 1 means that providers usually have an incentive to become innovative if their competition is conservative. However, becoming innovative and myopically optimizing proﬁt can lead to non-existence of a BNE. In this case,

an innovative provider should consider the additional market power he has due to his larger strategy space when choosing his strategy. Speciﬁcally, he should take a (myopically) nonoptimal action to restrict his competitor s rational responses. We now show that, if provider 1 does so, he can guarantee himself strictly positive payoff whenever there is an interval of users for which his costs are lower than provider 2 s costs for all users (even though this does not constitute a BNE). Theorem 2. Let provider 2 be conservative, i.e., pℓ 2 = 0. If there exists 0 < t < tmax with c1(0, t) < c2(0, tmax) (14) and c1(0, t) < c1(0, tmax) < 2c1(0, t), (15)

then there exists a strategy ρ1 with pℓ 1 > 0 that guarantees provider 1 a non-negative payoff for any pf 2 and a strictly positive payoff for any individually rational response of provider 2.

Proof. Note that for any pf 1 < c2(0, tmax), pℓ 1 > 0, provider 2 can only achieve a positive proﬁt if he plays pf 2 = pf 1 + ˆtpℓ 1 for some ˆt > 0. To guarantee a positive payoff for provider 1 with such a pf 1 it therefore sufﬁces that

π1(ρ1, ρ2, ˆt) = Z ˆt

0 f(t)(pf 1 + tpℓ 1 c1(0, ˆt))dt > 0 (16)

for all ˆt. For 0 < t < tmax with c1(0, t) < c2(0, tmax) and c1(0, t) < c1(0, tmax) < 2c1(0, t) (17)

choose ρ1 such that pf 1 = c1(0, t) and pℓ 1 = c1(0, t) R t 0 f(t)tdt. Then

it holds for ˆt t:

π1(ρ1, ρ2, ˆt) = Z ˆt

0 f(t)(pf 1 + tpℓ 1 c1(0, ˆt))dt (18)

0 f(t)(pf 1 + tpℓ 1 c1(0, t))dt (19)

0 f(t)(tpℓ 1)dt (20)

For ˆt > t it holds that π1(ρ1, ρ2, ˆt) (22)

0 f(t)(pf 1 + tpℓ 1 c1(0, ˆt))dt (23)

0 f(t)(t c1(0, t)

R t 0 f(t)tdt c1(0, ˆt) c1(0, t))dt (24)

0 f(t)(c1(0, t) c1(0, ˆt) c1(0, t))dt (25)

0 f(t)(2c1(0, t) c1(0, ˆt)dt (26)

>0 (27) Therefore, ρ1 guarantees provider 1 positive proﬁt for σ = [0, ˆt] 1 for any ˆt [0, tmax].

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

In words, Theorem 2 says that provider 1 always has a strategy which is individually rational (independent of the other provider s action) and that results in strictly positive proﬁt for all individually rational responses of provider 2. This is especially attractive if provider 1 could only obtain zero proﬁt as a conservative provider. As we can see from the proof, a possible such pricing strategy is given by pf 1 = c1(0, t) and pℓ 1 = c1(0, t) R t 0 f(t)tdt.

This still leaves the question whether a provider who obtains positive proﬁt as a conservative provider should also become innovative. As the following proposition shows, the answer is usually yes. Theorem 3. Let provider 2 be conservative, i.e., pℓ 2 = 0. If provider 1 obtains strictly positive proﬁt in some constant BNE then there exists a strategy ρ1 with pℓ 1 > 0 that, for any individually rational response of provider 2, guarantees provider 1 greater proﬁt than in any constant BNE.

Proof. Recall that by Proposition 1, if provider 1 has positive proﬁt in some constant equilibrium then

c1(0, tmax) < c2(0, tmax). (28)

Let t be a type such that

t = argmint c2(t, tmax) c2(0, tmax)

For any ϵ > 0 with ϵ < µ(0, tmax) c2( t,tmax) c2(0,tmax))

t , let ρ1 = (pf 1, pℓ 1) with pf 1 = c2(0, tmax) ϵ and pℓ 1 = c2( t,tmax) c2(0,tmax)

t . Then for any pf 2 provider 2 obtains no users or there exists a t > ˆt such that he obtains all users with type t > ˆt and his proﬁt is given by

π2(ρ1, ρ2, σ) = Z tmax

ˆt f(t)(pf 2 c2(ˆt, tmax))dt (30)

ˆt f(t)(pf 1 + ˆtpℓ 1 c2(ˆt, tmax))dt (31)

ˆt f(t)(pf 1 + ˆtc2(ˆt, tmax) pf 1 + ϵ ˆt (32)

c2(ˆt, tmax))dt (33)

=0 (F(tmax) F(ˆt))ϵ (34)

Therefore, provider 2 has no individually rational response for which he obtains any users. It follows that for any individually rational response of provider 2 and any ϵ < µ(0, tmax) c2( t,tmax) c2(0,tmax)

t provider 1 s proﬁt is

π1(ρ1, ρ2, σ) (35)

0 f(t)(pf 1 + tpℓ 1 c1(0, tmax))dt (36)

=c2(0, tmax) c1(0, tmax) ϵ (37)

+ µ(0, tmax)c2( t, tmax)) c2(0, tmax)

>c2(0, ˆt) c1(0, ˆt) (39)

By Proposition 1, the proﬁt therefore is greater than the proﬁt in any constant BNE.

Note that, in contrast to the strategies described by the proof of Theorem 2, the strategies described by the proof of Theorem 3 are not guaranteed to be individually rational responses to every possible action provider 2 might play. However, they are guaranteed to be individually rational responses to every constant BNE strategy of provider 2.

4.2 Both Providers are Innovative Once one provider starts to employ linear pricing, the other provider might at some point also want to follow. Consequently, we now look at the case where both providers are innovative. When both providers employ linear pricing, the ﬁrst provider loses much of the additional power he had when the other provider stayed conservative. Consequently, there is no general guarantee that he can still improve his proﬁt. But as long as the cost functions are strictly split-convex, he can still choose a strategy which guarantees him that proﬁts do not decrease compared to any constant BNE (for any individually rational response of the other provider).

Theorem 4. Assume the cost function of provider 2 is strictly split-convex. Then there exists a strategy ρ1 with pℓ 1 > 0 that, for any individually rational response of provider 2, guarantees provider 1 greater or equal proﬁt than in any constant BNE.

Proof. If provider 1 obtains 0 proﬁt in all constant BNEs, nothing has to be shown. Otherwise, assume provider 1 plays ρ1 = (pf 1, pℓ 1) with pℓ 1 = d dt|tmaxc2(0, t) and pf 1 + pℓ 1µ(0, tmax) = c2(0, tmax). By Proposition 2, we know that for all ρ2 with utility-maximizing σ = [0, ˆt] 2 it holds that π2(ρ1, ρ2, σ) π2(ρ1, ρ1, σ) and from strict split-convexity it follows that

c2(0, ˆt) (40) >c2(0, tmax) (41)

dt|tmaxc2(0, t)(µ(0, ˆt) µ(0, tmax)) (42)

=pf 1 + pℓ 1µ(0, tmax) + pℓ 1(µ(0, ˆt) µ(0, tmax)) (43)

=pf 1 + pℓ 1µ(0, ˆt) (44)

and therefore

π2(ρ1, ρ1, σ) = Z ˆt

0 f(t)(pf 1 + tpℓ 1 c2(0, ˆt))dt (45)

0 f(t)(pf 1 + tpℓ 1 pf 1 pℓ 1µ(0, ˆt))dt (46)

0 f(t)(tpℓ 1 pℓ 1µ(0, ˆt))dt (47)

The proof works analogously for σ = [0, ˆt] 1. Therefore, any individually rational response of provider 2 results in user strategy proﬁle σ = [0, tmax] 1. For this strategy proﬁle, provider 1 has proﬁt π1(ρ1, ρ2, σ) = c1(0, tmax) c2(0, tmax), which by Proposition 1 is the highest possible proﬁt for any constant BNE.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

On the other hand, if both providers are symmetric and their costs are split-convex, moving to linear prices cannot lead to any proﬁt in equilibrium.

Proposition 3. Assume providers are symmetric, i.e., c1( ) = c2( ), and costs are split-convex. Then there can be no BNE with strictly positive proﬁt for either provider.

Proof. If, w.l.o.g., all users prefer provider 1 and he obtains strictly positive payoff, provider 2 obtains zero proﬁt but can deviate to pf 2 = pf 1 ϵ, pℓ 2 = pℓ 1 to obtain strictly positive payoff for ϵ > 0 small enough. Therefore, in any potential BNE, the market is split between providers or both obtain zero proﬁt. Assume (ρ1, ρ2, σ) is a BNE and w.l.o.g. σ = [0, ˆt] 1 for some 0 < ˆt < tmax. By Corollary 1 we can assume ρ1 = ρ2. Then, for any ϵ > 0 and ˆρ2 = (pf 2 ϵ, pℓ 2) all users prefer provider 2, resulting in proﬁt

π2(ρ1, ˆρ2, [0, tmax] 2) (49)

0 f(t)(pf 2 ϵ + tpℓ 2 c2(0, tmax))dt (50)

0 f(t)(pf 2 + tpℓ 2)dt ϵ c2(0, tmax) (51)

0 f(t)(pf 2 + tpℓ 2)dt ϵ (52)

(1 F(ˆt))c2(ˆt, tmax) + F(ˆt)c2(0, ˆt) (53) =π2(ρ1, ρ2, σ) + π1(ρ1, ρ2, σ) ϵ (54)

If π2(ρ1, ρ2, σ) > 0 or π1(ρ1, ρ2, σ) > 0, it follows that for ϵ small enough, π2(ρ1, ˆρ2, ˆσ) > π2(ρ1, ρ2, σ), contradicting our assumption that (ρ1, ρ2, σ) is a BNE. Thus, it must hold that π2(ρ1, ρ2, σ) = 0 and π1(ρ1, ρ2, σ) = 0.

When cost functions are not split-convex, symmetric providers still always obtain the same proﬁt in any BNE, even though it can be positive.

Proposition 4. Assume providers are symmetric, i.e., c1( ) = c2( ). Then, in all BNEs it holds that π1(ρ1, ρ2, σ) = π2(ρ1, ρ2, σ).

Proof. To see this, note that for symmetric providers, whoever has lower proﬁts could switch users with the other one by making an inﬁnitesimal change to his price function.

By deﬁnition, whether a tuple (ρ1, ρ2, σ) is a BNE is decided via a three-dimensional condition space, as the proﬁt has to be better than the proﬁt for any other tuple ( ˆρ1, ˆρ2, ˆσ). This makes it very hard to evaluate whether a given tuple is a BNE. The following theorem instead characterizes equilibria by a one-dimensional condition space, greatly reducing the complexity of checking candidate equilibria.

Theorem 5. A tuple (ρ1, ρ2, [0, ˆt] i) is a BNE if and only if ρ1 = ρ2 and

F(ˆt)ci(0, ˆt) F(a)ci(0, a) (55)

(F(ˆt) F(a)(pf i + µ(a, t)pℓ i) (56)

(1 F(a))c i(a, tmax) (1 F(ˆt))c i(ˆt, tmax) (57)

for all 0 a tmax. If the providers are not symmetric, it also has to hold for all 0 a tmax that

F(a)(pf i + µ(0, a)pℓ i c i(0, a)) (58)

(1 F(ˆt))(pf i + µ(ˆt, tmax)pℓ i c i(ˆt, tmax)) (59)

(1 F(a))(pf i + µ(a, tmax)pℓ i ci(a, tmax)) (60)

F(ˆt)(pf i + µ(0, ˆt)pℓ i ci(0, ˆt)). (61)

The proof is provided in Appendix A. While Theorem 5 fully characterizes all BNEs, it is a very technical characterization. It can be used to check whether a given tuple (ρ1, ρ2, σ) is a BNE, but it does not enable an easy search procedure for ﬁnding candidate BNEs. This is particularly important because a (ρ1, ρ2, [0, ˆt] i) that satisﬁes the conditions of Theorem 5 does not always exist. Thus, even if both providers are innovative, there are cases where no BNE exists. The following corollary addresses this issue, identifying a small subset of user strategy proﬁles that can be part of a BNE and reducing the search for corresponding provider strategies to a one-dimensional search. Corollary 2. If a tuple (ρ1, ρ2, σ) with 0 < ˆt < tmax is a BNE and the cost functions are differentiable, then it holds

d dt|ˆt F(t)c2(0, t) (62)

=f(ˆt)(pf + ˆtpℓ). (63)

dt|ˆt (1 F(t))c1(t, tmax) (64)

Proof. Note that for t = ˆt it trivially holds

F(ˆt)c2(0, ˆt) F(t)c2(0, t) (65)

=(F(ˆt)) F(t)(pf 1 + µ(t, t)pℓ 1) (66)

=(1 F(t))c1(t, tmax) (1 F(ˆt))c1(ˆt, tmax). (67)

Theorem 5 further gives us that the three expressions have the same ordering for all t, especially for all t in any small neighborhood around ˆt. Therefore, all three expressions need to have the same derivative in t at point t = ˆt.

Given a cutoff point ˆt, all potential BNE price functions lie on a line deﬁned by Equation (63). To ﬁnd a BNE, all that remains to be done is to check whether ˆt with any of the (pf, pℓ) on that line satisfy the conditions of Theorem 5.

5 Welfare Analysis In this section, we analyze the impact of variance-based pricing on social welfare. In our model, the social welfare is simply the negative sum of the expected costs of both providers, i.e., w(ρ1, ρ2, [0, t] i) = F(ˆt)ci(0, ˆt) (1 F(ˆt))c i(ˆt, tmax). The social welfare in any constant BNE then follows directly from Proposition 1. Corollary 3. Let both providers be conservative and w.l.o.g. assume c1(0, tmax) c2(0, tmax). Then the social welfare in any BNE is w(ρ1, ρ2, σ) = c1(0, tmax).

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Proof. Follows directly from Proposition 1.

If only one provider is innovative, the social welfare often goes down, as the innovative provider can employ his additional market power to force the conservative provider to give up part of the market, even if it increases overall costs. But if both are innovative, he loses this power and in BNE, the social welfare cannot decrease compared to any constant BNE.

Proposition 5. W.l.o.g. assume c1(0, tmax) c2(0, tmax). When both providers are innovative, then the social welfare in any BNE (ρ1, ρ2, σ) is higher than the social welfare in any constant BNE, i.e., w(ρ1, ρ2, σ) c1(0, tmax).

Proof. Recall that the social welfare is w(ρ1, ρ2.[0, t] i) = ( 1) F(ˆt)ci(0, ˆt) + (1 F(ˆt))c i(ˆt, tmax) . Thus, whenever all users choose provider 1, the social welfare is the same as in any constant BNE, i.e., w(ρ1, ρ2, [0, tmax] 1) = c1(0, tmax). We now show the claim of the proposition by contradiction. Assume (ρ1, ρ2, [0, ˆt] i) for i 1, 2 is an innovative BNE where the social welfare is strictly lower than the social welfare in any constant BNE. Then the social welfare under (ρ1, ρ2, [0, ˆt] i) is also strictly lower than under (ρ1, ρ2, [0, tmax] 1), i.e., the sum of the expected costs is strictly higher; formally: F(ˆt)ci(0, ˆt) + (1 F(ˆt))c i(ˆt, tmax) > c1(0, tmax). Additionally, by Corollary 1, we can assume that ρ1 = ρ2. This means that the payment of any user is independent of which provider he chooses, and therefore the sum of the revenues of both providers does not change between (ρ1, ρ2, [0, ˆt] i) and (ρ1, ρ2, [0, ˆt] 1). Taken together, when going from the ﬁrst proﬁle to the second proﬁle, the sum of the revenues stay the same but the costs strictly decrease, which implies that π1(ρ1, ρ2, [0, tmax] 1) > π1(ρ1, ρ2, [0, ˆt] i) + π2(ρ1, ρ2, [0, ˆt] i). Therefore, (ρ1, ρ2, [0, ˆt] i) can not be a BNE, a contradiction.

6 Numerical Example

In this section, we illustrate our results via a simple numerical example. We assume that user types are uniformly distributed on [0, 1]. Further, we assume provider 1 has cost function c1(a, b) = 0.0125+µ(a, b)2 and provider 2 has cost function c2(a, b) = 0.2 + µ(a,b)2

4 , where µ(a, b) denotes the average type of all users in [a, b] (as previously deﬁned in Section 2.1). Thus, provider 1 has a lower cost for low types but a higher cost for high types than provider 2, and both providers have the same cost for the whole user population. From Proposition 1, we know that when both providers are conservative, there are only zero-proﬁt BNEs. They occur at pf 1 = pf 2 = 0.2625 with a welfare of 0.2625. We now consider each provider unilaterally switching to linear prices (as described in Theorem 2). Figure 1 shows the proﬁt increase that provider 1 could obtain when unilaterally innovating by playing (pf 1 = 0.215, pℓ 1 = 0.5309) while provider 2 remains conservative. Figure 2 shows the analogous result for when provider 2 becomes innovative. We see that provider 1 innovating leads to the overall better result

0.3 0.4 0.5 0.6 0.7

best response

Figure 1: Proﬁt of both providers for all conservative responses of provider 2 to provider 1 playing (pf 1 = 0.215, pℓ 1 = 0.5309).

0.3 0.4 0.5 0.6 0.7 0.8

best response

Figure 2: Proﬁt of both providers for all conservative responses of provider 1 to provider 2 playing (pf 2 = 0.2506, pℓ 2 = 0.6188).

for both providers. This is not surprising, considering that the innovative provider obtains the lower type portion of the market in which provider 1 has lower costs. At the best response of provider 2, the social welfare therefore increases to 0.2077. Nonetheless, if provider 2 innovates instead, he can still obtain a proﬁt of 0.0442 at provider 1 s best constant response of pf 1 = 0.3941. Since here, provider 2 uses the power of his larger strategy space as an innovative provider to force provider 1 to obtain a high type population interval (for which provider 1 has higher costs) social welfare unsurprisingly decreases to 0.3846. For the case where both providers are willing to employ linear pricing, Corollary 2 provides us with conditions on candidate equilibrium user strategy proﬁles. For our example, we can use those conditions to ﬁnd four cutoff points: σ = [0, 0.595] 1, σ = [0.5431, 1] 1, σ = [0, 1] 1 and σ = [0, 0] 1. All of these except for σ = [0, 0.595] 1 do not satisfy Theorem 5 and are eliminated. For σ = [0, 0.595] 1 any pf 1 = pf 2 [0, 0.0409], pℓ 1 = pℓ 2 = 0.2784 pf 1 0.595 satisfy Theorem 5 and form equilibrium pricing strategies. To visualize an example BNE, Figure 3 shows the proﬁt of both providers for pf 1 = pf 2 = 0 and pℓ 1 = pℓ 2 = 0.4676 for different utility-maximizing σ = [0, t] 1. We see that neither provider wants to deviate to enforce a different user strategy proﬁle σ = [0, t] 1 than σ = [0, 0.595] 1. Social welfare at this BNE is 0.2055, which is even slightly better than when only provider 1 was innovative. However, the increased competition leads to a signiﬁcantly lower proﬁt for both providers than when only provider 1 was innovative. This suggests that a conservative provider who is forward-looking and properly anticipates the possible BNEs may prefer to stay conservative if the other provider is already innovative.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

provider 1 provider 2

0.2 0.4 0.6 0.8 1.0

Figure 3: Proﬁt of both providers for different σ = [0, t] 1

7 Conclusion

In this paper, we have studied the competitive effects of providers utilizing linear variance-based (or type-based) pricing rules in settings where a provider s costs depend on the average type of all his users. We have shown that, while a single provider innovating often leads to non-existence of BNEs, the innovative provider can exert the additional market power he has due to his larger strategy space to unilaterally set prices that increase his proﬁt for all individually rational responses of a conservative provider. We have further characterized all equilibria where both providers employ linear pricing. While much of the additional market power of an innovative provider is lost once the other provider also adopts linear pricing, the increased strategy space allows providers to split the market more closely along differences in their cost functions. This often increases both providers proﬁts and social welfare. While our general insights translate to settings with more than two providers, the strategic considerations and the BNEs quickly become too complex to provide useful insights. In future work, it would be interesting to study secondary effects like incentivizing users to actively lower their variance. Furthermore, to deploy variance-based pricing in practice, it would be important to develop good machine learning algorithms to effectively learn the users types over time.

A Proof of Theorem 5

Proof. A tuple (ρ1, ρ2, [0, ˆt] i) is a BNE if [0, ˆt] i is utility maximizing and no provider has a proﬁtable deviation. From Proposition 2 we know that any deviation with different prices is worse than keeping the same prices and choosing the deviating provider s most-preferred utility-maximizing user strategy proﬁle. Thus, the tuple is a BNE if and only if moving to any different user strategy proﬁle (weakly) decreases both providers proﬁts. W.l.o.g. assume i = 2, and thus, in the candidate BNE we consider, provider 2 obtains the lowvariance users. We ﬁrst consider how proﬁts change under different user strategy proﬁles for which provider 2 still obtains the low-variance users. Changing to any [0, a] 2 with 0 a < ˆt yields a proﬁt change for Provider 1 of

(1 F(ˆt))(c1(ˆt, tmax) c1(a, tmax) (68)

a f(t)(pf 1 + tpℓ 1 c1(a, tmax))dt (69)

=(1 F(ˆt))c1(ˆt, tmax) (1 F(a))c1(a, tmax) (70)

+ (F(ˆt) F(a))(pf 1 + µ(a, t)pℓ 1) (71)

while with ˆt < a < tmax it yields a change of

(1 F(a))(c1(ˆt, tmax) c1(a, tmax) (72)

ˆt f(t)(pf 1 + tpℓ 1 c1(ˆt, tmax))dt (73)

=(1 F(ˆt))c1(ˆt, tmax) (74) (1 F(a))c1(a, tmax) (75)

+ (F(ˆt) F(a))(pf 1 + µ(a, t)pℓ 1). (76)

Similarly, the proﬁt change for provider 2 for a < ˆt is

F(a)(c2(0, ˆt) c2(0, a)) (77)

a f(t)(pf 1 + tpℓ 1 c2(0, ˆt))dt (78)

=F(ˆt)c2(0, ˆt) F(a)c2(0, a) (79)

(F(ˆt) F(a))(pf 1 + µ(a, t)pℓ 1) (80)

and for a > ˆt the proﬁt change is given by

F(ˆt)(c2(0, ˆt) c2(0, a)) (81)

ˆt f(t)(pf 1 + tpℓ 1c2(0, a))dt (82)

=F(ˆt)c2(0, ˆt) F(a)c2(0, a) (83)

(F(ˆt) F(a))(pf 1 + µ(a, t)pℓ 1). (84)

Bounding all of these expressions above by zero yields the ﬁrst half of the theorem. Equivalently, we now consider how the proﬁt changes when provider 1 obtains the low variance users (i.e. [0, a] 1): Z a

0 f(t)(pf 1 + tpℓ 1 c1(0, a))dt (85)

ˆt f(t)(pf 1 + tpℓ 1 c1(ˆt, tmax))dt (86)

=F(a)(pf 1 + µ(0, a)pℓ 1 c1(0, a)) (87)

(1 F(ˆt))(pf 1 + µ(ˆt, tmax)pℓ 1 c1(ˆt, tmax)) (88) 0 (89)

a f(t)(pf 1 + tpℓ 1 c2(a, tmax))dt (90)

0 f(t)(pf 1 + tpℓ 1 c2(0, ˆt))dt (91)

=(1 F(a))(pf 1 + µ(a, tmax)pℓ 1 c2(a, tmax)) (92)

F(ˆt)(pf 1 + µ(0, ˆt)pℓ 1 c2(0, ˆt)) (93) 0 (94)

If the providers are symmetric, both providers would get the same proﬁt if they served the same segment of the market, and therefore the conditions (79) (81) and (84) (86) do not have to be checked.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

[Baye and Kovenock, 2017] Michael R. Baye and Dan Kovenock. Bertrand Competition, pages 1 7. Palgrave Macmillan UK, London, 2017.

[Blattberg and Wisniewski, 1989] Robert C Blattberg and Kenneth J Wisniewski. Price-induced patterns of competition. Marketing Science, 8(4):291 309, 1989.

[Celebi and Fuller, 2012] Emre Celebi and J David Fuller. Time-of-use pricing in electricity markets under different market structures. IEEE Transactions on Power Systems, 27(3):1170 1181, 2012.

[Cramton, 2017] Peter Cramton. Electricity market design. Oxford Review of Economic Policy, 33(4):589 612, 2017.

[Dierks and Seuken, 2019] Ludwig Dierks and Sven Seuken. Cloud pricing: The spot market strikes back. In Proceedings of the 2019 ACM Conference on Economics and Computation. ACM, 2019.

[Dierks et al., 2019] Ludwig Dierks, Ian A. Kash, and Sven Seuken. On the cluster admission problem for cloud computing. In Proceedings of the 14th Workshop on the Economics of Networks, Systems and Computation, June 2019.

[Ericsson, 2017] Ericsson. Shifting mobile data plans, 2017.

[Feng et al., 2013] Yuan Feng, Baochun Li, and Bo Li. Price competition in an oligopoly market with multiple iaas cloud providers. IEEE Transactions on Computers, 63(1):59 73, 2013.

[Gallego et al., 2006] Guillermo Gallego, Woonghee Tim Huh, Wanmo Kang, and Robert Phillips. Price competition with the attraction demand model: Existence of unique equilibrium and its stability. Manufacturing & Service Operations Management, 8(4):359 375, 2006.

[Joskow and Wolfram, 2012] Paul L Joskow and Catherine D Wolfram. Dynamic pricing of electricity. American Economic Review, 102(3):381 85, 2012.

[L opez-P erez et al., 2009] David L opez-P erez, Alvaro Valcarce, Guillaume De La Roche, and Jie Zhang. Ofdma femtocells: A roadmap on interference avoidance. IEEE Communications Magazine, 47(9):41 48, 2009.

[Moorthy, 1984] K Sridhar Moorthy. Market segmentation, self-selection, and product line design. Marketing Science, 3(4):288 307, 1984.

[Muratori and Rizzoni, 2015] Matteo Muratori and Giorgio Rizzoni. Residential demand response: Dynamic energy management and time-varying electricity pricing. IEEE Transactions on Power systems, 31(2):1108 1117, 2015.

[Mussa and Rosen, 1978] Michael Mussa and Sherwin Rosen. Monopoly and product quality. Journal of Economic Theory, 18(2):301 317, 1978.

[Rong et al., 2018] Jiang Rong, Tao Qin, and Bo An. Dynamic pricing for reusable resources in competitive market with stochastic demand. In Thirty-Second AAAI Conference on Artiﬁcial Intelligence, 2018.

[Truong-Huu and Tham, 2014] Tram Truong-Huu and Chen-Khong Tham. A novel model for competition and cooperation among cloud providers. IEEE Transactions on Cloud Computing, 2(3):251 265, 2014. [Urieli and Stone, 2016] Daniel Urieli and Peter Stone. Autonomous electricity trading using time-of-use tariffs in a competitive market. In Thirtieth AAAI Conference on Artiﬁcial Intelligence, 2016. [Varian, 1989] Hal R Varian. Price discrimination. Handbook of Industrial Organization, 1:597 654, 1989.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)