Bernard Caillaud
email: caillaud@pse.ens.fr.

Romain De Nijs
email: romaindenijs@gmail.com.

Jel Codes

: L11

Strategic loyalty reward in dynamic price Discrimination

Keywords: Price discrimination, Dynamic pricing, Loyalty reward Price discrimination, Dynamic pricing, Loyalty reward. JEL: L11, L40, M31

This paper proposes a dynamic model of duopolistic competition under behaviorbased price discrimination with the following property: in equilibrium, a firm may reward its previous customers although long term contracts are not enforceable. A firm can offer a lower price to its previous customers than to its new customers as a strategic means to hamper its rival to gather precise information on the young generation of customers for subsequent profitable behavior-based pricing. The result holds both with myopic and forward-looking, impatient enough consumers.

Introduction

Behavior-based price discrimination (BBPD) is a very simple form of price discrimination that consists in offering different prices to different customers according to their past purchase history. In practice, firms charge their own previous customers a different price than their new ones. This pricing strategy is already widely established in many important industries (e.g. banks, phones, softwares, hotels, airlines and e-retailers) and is likely to become even more prevalent with the development of new information technologies (See OFT (2010)).

When BBPD is possible, one of the basic questions is: should firms charge higher prices to their previous customers when they renew their purchase or to their new customers at their first purchase ? The academic literature on BBPD often predicts that firms should charge a lower price to their new customers. The reason is that previous customers of a firm have revealed their relative higher preference for the good it provides, thus inducing the firm to charge them a higher price in subsequent periods. The empirical evidence, however, is rather mixed: Shaffer and Zhang (2000) for example provides many instances in which firms charge a lower price on their previous customers. Shin and Sudhir (2010) also notes that practitioners' intuition leads them to think that previous customers should be offered in general better deals than new ones.

There are many examples of introductory offers to new customers. Newspapers usually offer discount to their new subscribers. For instance a new subscriber for 3 months to the French newspaper "Le Monde", pays 50 euros whereas a previous customer is charged 131.30 euros. Another example is the online retailer AuchanDirect who offers a free delivery to its new customers. A third example is the newly opened online betting industry in France wherein operators offer free bets to their new customers. For instance BetClic and the PMU offer respectively 80 euros and 50 euros to their new customers. A last case is the antivirus software developer McAfee that tried in 2010 to make its previous customers renew their subscriptions for 79.99 dollars, whereas it offered the same software to its new customers at 69.9 dollars. Examples of better deals to previous consumers also exist. It is often observed in the sport industry. For instance, the Parisian rugby club the "Stade Francais" offers a discount to its customers that renew their season ticket. In 2008, for the basic season ticket a new customer paid 400 euros while a previous one only 360 euros. The same is sometimes true in fitness clubs. The Club Vitam for instance offers 15% discount on the yearly subscription for those who renew their membership.

The Parisian Club Med Gym is also currently launching a discount campaign towards its old consumers. A last example is Bitdefender that offers 25% to 35% price reduction to its customers that renew their subscription to its antivirus software. This last example in combination with the McAfee case shows that better deals to new or previous customers may arise within the same industry.

In this paper, we present a new theoretical explanation for why a firm may reward its previous customers with better deals even though long term contracts are not enforceable.

We show that a firm can offer a lower price to its previous customers than to its new customers as a strategic means to hamper its rival to gather precise information on the young generation of customers that it could use for subsequent profitable behavior-based pricing.

More precisely, we consider and analyze an infinite competition two-firm model with overlapping generations of consumers who live two periods; each generation of consumers is made of constant and symmetric proportions of price insensitive (hereafter loyal to one firm) consumers and price sensitive consumers (hereafter shoppers), as in Varian (1980).

Firms are able to recognize their own previous customers, but cannot distinguish between the consumers of the young generation and the previous customers of its competitor.

Firms can then price discriminate between their previous customers and their new customers. We characterize a symmetric Markov perfect equilibrium of this model, which is under mixed strategies with continuous support, as in the elementary model of Varian (1980). This equilibrium implies higher profits for firms at the expense of consumers than under uniform competition. More importantly, it exhibits the property that the firm that has recognized its old loyal customers offers a (stochastically) lower price to its new customers (i.e uses a "pay to switch" or a "poaching" strategy) than to its new customers, while its rival, that cannot tell its old loyal and the old shoppers apart, charges a (stochastically) lower price to its previous customers (i.e uses a "pay to stay" or a "loyalty reward" strategy) than to its new customers.

The basic intuition runs as follows. The firm that has recognized its old loyal customers, say firm 1, can extract the whole surplus from this category of consumers. It is more aggressive on its segment of new customers that consists in the young shoppers, the old shoppers as well as its young loyal consumers and therefore exhibits a smaller proportion of loyal consumers. The other firm, say firm 2, has served both its old loyal consumers and the old shoppers in the previous period; as a consequence its two segments of new and previous customers have the same proportion of loyal consumers and shoppers.

The segment of new customers, however, contains firm 2's young loyal customers who are much more "valuable" than its old loyal consumers, since being able to perfectly recognize them enables firm 2 to extract their surplus in the subsequent period. Recognition of these young loyal customers requires a price high enough so that they are the only ones from this generation who buy from the firm. As a consequence, firm 2 has an incentive to charge a higher price on its segment of new customers than on its segment of previous customers, so as to increase its chance to recognize its young loyal consumers.

Our main analysis is carried out with myopic consumers who only care about the current price they pay. They do not foresee the strategic use of their purchase behavior by firms for subsequent price discrimination and hence do not attempt to manipulate the revelation of their preference. This assumption is likely to be relevant for new markets, where consumers have not yet learned the firms' pricing strategies (Armstrong (2006)). This makes the myopic assumption fair enough for instance in the context of e-retailing which is still a nascent sector. Turow et.al (2005) in a study about online markets reports that two-thirds of adult Internet users surveyed believed incorrectly that it was illegal for online retailers to charge different people different prices. Consequently, consumers are unlikely to act strategically to avoid being recognized. In established industries, the myopic assumption can also be seen as a form of bounded rationality. However our main result on previous customers reward is robust to the consideration of fully rational consumers as long as their discount factor for the present is low enough.

In the terminology of Fudenberg and Villas Boas (2007) our model is one of pureinformation price discrimination as past purchases only convey information on consumers' tastes but are not payoff relevant. This branch of the literature has been pioneered by Villas-Boas (1999) and Fudenberg and Tirole (2000) [START_REF] Acquisti | Conditioning Prices on Purchase History[END_REF] (Gehrig and Stenbacka (2004) and Zhang (2011)). [START_REF] Armstrong | Recent Developments in the Economics of Price Discrimination[END_REF] Depending on the underlying consumers' preferences and degree of patience, BBPD has been found to be either profitable or unprofitable. Moreover, a common prediction of these models is that firms should offer lower prices to their rivals' customers to entice them to switch and higher prices to their own previous to capture their captive surplus. In our model, the incentives to recognize one's own captive customers interact with these forces, thereby generating a high price on new customers and rewards for previous customers on the part of the firm that has not recognized its old loyal consumers. A setting with infinite competition and overlapping generation is a natural and somehow necessary [START_REF] Caminal | Endogenous Switching Costs in a Duopoly Model[END_REF] modeling assumption to have this interaction. Also in a infinite competition model with overlapping generations of consumers, Villas-Boas (1999) finds opposite conclusions namely, BBPD decreases firms profits and always generates poaching strategies. His model has different underlying preferences and a specific timing in price setting decisions for previous and new customers that lead to the difference in predictions with ours. [START_REF] Acquisti | Conditioning Prices on Purchase History[END_REF] Another branch of the literature pioneered by Chen (1997) and Taylor (2003) considers environments with ex ante homogenous goods and switching costs that cause ex post differentiation and makes history payoff relevant.

2 See Fudenberg and Villas-Boas (2007), Esteves (2009) and Zhang (2010) for more complete literature reviews. [START_REF] Caminal | Endogenous Switching Costs in a Duopoly Model[END_REF] See the discussion about the two-period with a second-period new generation (See Section 3.

2)

The only paper on BBPD with short term contracts that generates previous customers reward we are aware of is Shin and Sudhir (2010). In a model à la Fudenberg and Tirole (2000), they allow consumers' preferences to vary across periods and they introduce some heterogeneity among customers with respect to the number of units they wish to buy each period. In this context, past purchase history conveys information on both consumers tastes and the quantity they wish to buy. They find that in markets with sufficient heterogeneity in quantities demanded and large enough changes of consumers preferences, it is optimal to reward one's own previous, high-demand customers, since the marginal gain in profit from cutting prices to retain them is greater than the marginal benefit of poaching a mix of low and high demand competitors' customers. Only one category of previous customers is rewarded and both firms use pay-to-stay strategies. Our model does not rely on consumers' mobility neither do we need an additional dimension of heterogeneity to generate previous consumers reward. Besides we predict that only one of the two firms offers a lower price to its previous customers.

Another closely related article is Chen and Zhang (2009). They use the same underlying consumers' preferences as ours in a two-period model where one single generation leaves through the two periods. Their main finding is that firms can be better off with BBPD than without it, even when consumers behave strategically. The intuition is that, in order to pursue customer recognition, [START_REF] Chen | Paying Customers to Switch[END_REF] competing firms need to price high to screen out price-sensitive consumers and hence price competition is moderated. The pursuit of loyal consumers recognition plays a similar role in our analysis as it contributes to the profitability of BBPD, but our repeated setting implies in addition that pricing for new customers aims at increasing the chances to win the race for customers recognition, which results in the strategic loyalty reward phenomenon. Note also that our result holds for myopic or strategic and relatively impatient consumers.

Introducing long term contracts is another possibility to derive loyalty rewards in the literature on BBPD. This strand of the literature has been pioneered by Caminal and Matutes (1990) and has been the object of recent advances (See Chen -Pearcy (2010)).

The rationale for previous customers reward is then the creation of endogenous switching cost through the design of the loyalty program as a way to create an opportunity cost from switching brands.

Last, our article is also related to the literature on static models of preference-based pricing and especially to Shaffer and Zhang (2000). Shaffer and Zhang (2000) considers a setting with asymmetric inherited market shares and asymmetric levels of brand loyalty.

They show that when the average loyalty of the two groups of consumers is sufficiently dissimilar, the firm whose previous customers are the less loyal finds this segment to be the more elastic one and hence offers it a lower price. In this case the other firm charges a lower price to its new customers. So, their result comes from differences in price elasticities while ours is a consequence of dynamic consideration of customer recognition.

The rest of this article is organized as follows. Section 2 describes the model. Section 3 investigates two benchmark situations that help better grasp the rationale behind loyalty rewards: no price discrimination and price discrimination in a static environment. Section 4 provides the main analysis with myopic consumers. Section 5 extends the analysis to forward-looking consumers. Section 6 concludes.

The model

We consider a market for an homogenous good with overlapping generations of consumers living two periods and two symmetric infinitely-lived firms.

Each period, a unit mass of infinitesimal consumers enters the market and stays until the end of the next period. Consumers have a unit demand per period, with constant per-period valuation equal to v. Within each generation, a proportion l ∈ (0, 1/2) is only interested in buying from firm 1 and the same proportion l for firm 2; these are "loyal" consumers. The remaining proportion s = 1 -2l may buy from either firm and are price sensitive; they are called "shoppers" [START_REF] Chen | Dynamic Price Discrimination with Asymmetric Firms[END_REF] . All consumers discount the future at the same rate β ∈ [0, 1) and choose whether to buy and from which firm at each period of their life.

The size of consumer segments is common knowledge to all agents. [START_REF] Chen | Dynamic Pricing: when to entice brand switching and when to reward consumer loyaly[END_REF] Firms are infinitely lived and their production costs are normalized to 0. They maximize their respective intertemporal profit streams, with common discount factor δ ∈ [0, 1).

At each date, firms choose prices simultaneously.

The information structure is critical. First, firms observe all prices once they have been set. Second, we assume that firms are unable to distinguish loyal consumers from shoppers within the young generation. Third, firms may be able to collect information about the customers they have served at the previous period and therefore they may be able to identify their own "previous" customers when charging prices. However they cannot distinguish between the consumers of the young generation and the previous customers of its competitor: these are just "new" customers for them.

When firms cannot price discriminate between their previous and their new customers, they simultaneously choose at each period one price each, p t i for i = 1, 2, and then consumers make their purchase decisions: it may be that the firms are unable to collect information about their previous customers, or to keep track of them, or that they are forbidden to charge different prices for customers they have served and consumers they haven't.

When firms can price discriminate between their own previous and their new customers, they simultaneously choose a pair of prices at each period,

P t i ≡ (p t o,i , p t n,i ) for firm i = 1, 2, p t
o,i for i's own previous customers and p t n,i for i's new customers. That is, we only allow for short term contracts. Young consumers are necessarily new customers for firms; old consumers may be previous or new customers for a firm at period t, depending on whether they bought from this firm or not previously. This framework is a dynamic game played by both firms and by the consumers. It involves asymmetric information because at a given period a firm privately knows the identity of the customers who bought from it previously. Yet, this private information only serves to implement price discrimination between previous customers and new customers, and it is irrelevant to compute the size of each segment served by each firm; the firms' profits therefore do not depend on private information.

We will focus on symmetric equilibria. Moreover, to get rid of the usual source of multiplicity due to bootstrap strategies that depend on payoff-irrelevant history, we will focus on Markov-perfect equilibria. We analyze the case of myopic consumers, where β = 0, in Section 4. We extend our analysis to forward-looking consumers with β > 0 in Section 5.

Benchmark situations 3.1 Equilibrium with no price discrimination

When price discrimination is not possible, firms choose prices (p t 1 , p t 2 ) at each period t. At each period, both firms face the same population of consumers and consumers face the purchase opportunities defined by current prices, irrespective of what happened before.

In other words, at a pricing stage, the payoff-relevant history is empty and, at a purchase decision stage, the payoff-relevant history only consists in current prices. The game is therefore a stationary repeated game and symmetric Markov-perfect equilibria coincide with the play of static Nash equilibria for every period.

In equilibrium, consumers behavior is immediate. Loyal consumers buy provided the price does not exceed v; shoppers buy from the lowest price firm, provided its price does not exceed v. Firms will not charge prices above v. Moreover, when firm j chooses current price p j , firm i's profit when choosing p i consists in its profit on loyal consumers, equal to 2lp i , and its profit on shoppers, equal to 2sp i when its price p i is smaller than p j , and equal to sp i when p i = p j . [START_REF] Chen | Dynamic Targeted Pricing with Strategic Consumers[END_REF] The model reduces to the infinite repetition of a one-shot game à la Varian (1980). The analysis is omitted and the equilibrium can be shown to be unique within the class of Markov-perfect equilibria, as in Varian (1980); it is in mixed strategies and characterized in the following proposition.

Proposition 1 (Varian, 1980): There exists a unique symmetric Markov-perfect equilibrium when discrimination is not possible; it is in mixed (stationary) behavioral strategies such that, at each period, each firm chooses its price by mixing according to a price de-

cumulative distribution function (d.d.f. 8 ) F (p) = l(v-p)
sp , defined on [p * , v] with p * = vl l+s . The equilibrium intertemporal valuation for a firm is given by V = 2lv 1-δ .

Static equilibrium with price discrimination

Let us now focus on a static game that corresponds to one period of the dynamic game with price discrimination with an asymmetric history. This game is a useful benchmark as it enables us to capture the strategic interaction due to the imperfect overlap of the populations of potential customers for the firms, absent any intertemporal considerations.

It corresponds to the game with price discrimination when β = δ = 0.

Both firms can identify two segments of customers each and can price discriminate between them. One firm, called the H-firm, faces one segment (price p o,H ) consisting in l loyal customers, the H-firm's own previous customers, and another segment (price p n,H ) consisting in l other loyal consumers and all the 2s shoppers. [START_REF] Esteves | A Survey on the Economics of Behaviour-Based Price Discrimination[END_REF] The other firm, called the equal sharing rule of market demand; it can also be viewed as the expected outcome of a stochastic rule such that, with probability 1/2, all shoppers patronize one firm, and with probability 1/2 they patronize the other one. The second tie breaking rule turns out to be more convenient in the main model, as explained later on. [START_REF] Esteves | Customer Poaching and Advertising[END_REF] A decumulative distribution function for a real-valued random variable X is defined as

F (x) = Pr{ X > x} = 1 -Pr{ X ≤ x}; hence, it is càdlàg, i.e.
it is continuous on a right neighborhood of any point x and it admits a limit at x going from the left. [START_REF] Esteves | A Survey on the Economics of Behaviour-Based Price Discrimination[END_REF] The "H" (resp. "L") comes from the fact that, in the dynamic version, this firm must have been the one that charged the highest (resp. lowest) price at the previous period, which enabled it to identify the segment of its "own previous" loyal customers, in contrast with the segment of its "new" customers (hence the "o" and the "n" indices).

(p) + L S n (p) = (1-s)( 1+3s 1+s v-p) 2sp
within [a S , v) and there exists a mass point of L S o (.)+L S n (.) at v equal to 1-s 1+s ; finally, in any mixed strategy equilibria, the intertemporal profits are

V S L = (1-s)v and V S H = (1-s)v(1 + s 1+s ).
In this asymmetric game, the firm that perfectly identifies some of its loyal customers (the H-firm) has a clear strategic advantage: it enjoys full monopoly on these customers and can afford being aggressive on its other segment since the proportion of loyal in it is rather small. By contrast, the L-firm is in an inferior position and cannot be too aggressive on both its segments as, in each segment, the proportion of loyal consumers is rather high and the firm does not want to forego the profit it can extract from these loyal consumers.

Indeed, V S L < V S H . The structure of prices for the L-firm is indeterminate. Indeed, several possible configurations are possible since no other restriction is imposed by the equilibrium condition, such as:

• symmetric independent pricing by the L-firm: p o,L and p n,L are independently distributed according to the d.d.f. L S (p) = [START_REF] Acquisti | Conditioning Prices on Purchase History[END_REF] 2 (

(1-s)( 1+3s 1+s v-p) 2sp
);

• de facto no price discrimination by the L-firm: p o,L = p n,L distributed according to L S (.) and the L-firm handles both segments on equal terms;

• surplus extraction on segment j and aggressive pricing on segment i by the L-firm:

p i,L and p j,L have disjoint and adjacent supports,

p i,L ∈ [a S , (1-s)(1+3s) (1+s) 2 v], p j,L ∈ [ (1-s)(1+3s) (1+s) 2
v, v] (with a mass point at v), so that the L-firm charges (stochastically) a high price on segment j and a low prices on segment i.

In a mixed strategy equilibrium, the H-firm's payoffs must be constant over the range of randomization. So, mixing by the L-firm has to satisfy:

Pr{p o,L > p} + Pr{p n,L > p} = 2L S (p). A symmetric policy implies: Pr{p o,L > p} = Pr{p n,L > p} = L S (p).
More aggressive pricing on some segment i, i.e. shifting some probability weight on lower values of the price p i,L , must go along with less aggressive pricing on the other segment, i.e. shifting probability weight on higher values of p j,L . The L-firm cannot fight more fiercely on both fronts, compared to the symmetric pricing policy. In this knife-edge situation, the two segments of consumers faced by the L-firm are perfectly symmetric and the equilibrium implies playing aggressive on one half of the consumers and extracting more surplus on the other half.

When j = o and i = n, the L-firm extracts more surplus from its own previous customers, which is a common characteristics of behavior-based price discrimination; indeed, so does the H-firm with p o,H = v. When j = n and i = o, the L-firm strategy exhibits previous customers reward (loyalty reward), a more unusual prediction. But the multiplicity of equilibrium strategies in this static framework does not allow to conclude convincingly.

Price discrimination with myopic consumers

We now turn to the dynamic situation in which firms can price discriminate between their own previous and new customers and consumers are myopic, that is: β = 0. This assumption rules out intertemporal strategic considerations; solving for consumers' short run best response is immediate and the game basically reduces to a game between the firms. The analysis in this section can also be viewed as characterizing a situation of limited rationality from consumers who are unable to figure out future prices.

Payoff-relevant history from the consumers' viewpoint consists in current prices and which firm, if any, they patronized previously. At any period t, loyal consumers buy if and only if the price of their matching firm is not larger than v. Shoppers, at any period t, buy from the firm offering the lowest price available to them (as a previous customer or a new customer for the firms), provided this price does not exceed v. In case of a tie, we assume that with probability 1/2 all shoppers patronize one of the firm and with probability 1/2 they patronize the other one. Compared to the more standard tie breaking rule, in which 1/2 consumers split equally among the firms, our rule makes no difference in terms of current expected profits; however, next period, it implies that all shoppers are previous customers of the same firm and the other firm's previous customers are all loyals of that firm. This enables us to simplify the description of the payoff-relevant history at any period and it drastically simplifies the characterization of equilibrium strategies. [START_REF] Fershtman | Finite State Dynamic Games with Asymmetric Information: A Framework for Applied Work[END_REF] Let us restrict attention to prices within [0, v]. [START_REF] Fudenberg | Customer Poaching and Brand Switching[END_REF] Suppose that (P t-1 1 , P t-1 2 ) ∈ [0, v] 4 prevailed at period t-1. At period t, firm i has private information about each consumer, identifying whether he is a previous or a new customer of firm i. When firms choose prices [START_REF] Chen | Paying Customers to Switch[END_REF] , they use their private information to implement price discrimination that is to allow a previous (resp. new) customer to be offered a price p t o,i (resp. p t n,i ).

(P t 1 , P t 2 ) ∈ [0, v]
When such price-discriminating policy is implemented, firm i's total demand and profit simply depend on (P t 1 , P t 2 ) and on whether it served the shoppers born at t -1 or not, since that determines the composition of their respective segments of potential customers.

Profits therefore depend solely on public information, private information is not relevant at the price setting stage. In other words, there exists a public sufficient statistics for the whole payoff-relevant history that corresponds to the identity of the firm who served the shoppers born at t -1: either firm 1 served all shoppers born at t -1, i.e. (P t-1

1 , P t-1 2 ) is such that p t-1 n,1 < p t-1 n,2 (or p t-1 n,1 = p t-1
n,2 and all shoppers patronized firm 1), or firm 2 served them all, i.e. when p t-1 n,2 < p t-1 n,1 or (p t-1 n,1 = p t-1 n,2 and all shoppers patronized firm 2). To ease notation, we will thereafter change the labeling of firms: we let P L = (p o,L , p n,L ) denote the prices of the L-firm, that is the firm that served all the shoppers born at the previous period, P H = (p o,H , p n,H ) the pricing rule for the H-firm, that is the firm that had the highest price and served no shoppers. Similarly, we let V L and V H denote the intertemporal valuations starting from the current period for the L-firm and the H-firm.

We focus on symmetric Markov-perfect equilibria in which firms choose their prices based solely on whether they are the (current) H-firm or L-firm, and consumers make their purchase decisions based solely on the current prices available to them, given which firm, if any, they patronize previously.

Our first result is not surprising given the underlying preferences of consumers: there exists no symmetric pure-strategy Markov-perfect equilibrium. The result is however not immediate to prove in our setting as short term gains from price undercutting have to be compared with long-term losses, due to the change in the state variable characterizing whether the firm is the L-firm or the H-firm, and long-term losses are endogenous. [START_REF] Fudenberg | Behavior-Based Price Discrimination and Customer Recognition[END_REF] Proposition 3 : There exists no pure strategy symmetric Markov-perfect equilibrium of the game of price discrimination with myopic consumers.

Therefore, we now focus on symmetric Markov-perfect equilibria that involve mixing. Note, though, that in equilibrium, we necessarily have: p o,H = v. So, an equilibrium is characterized by a d.d.f. H(.) for p n,H , and a (joint) distribution for (p o,L , p n,L ) characterized by its marginal d.d.f. L o (.) and L n (.) with respect to p o,L and p n,L .

Let us provide some intuition about the construction of our equilibrium. We must first emphasize that the standard approach, e.g. Narasimhan (1988), is not useful in our model for the very same reason that the standard proof of non-existence of pure strategy equilibrium fails. Small changes in prices for new customers have a short-term impact in terms of current market shares among shoppers and current profit margins, as well as a long term impact through a change in the probability distribution of the state variable.

If mass points could be ruled out a priori, the approach à la Narasimhan (1988) would still allow us to determine the interval support of H(.) and of the union of the supports of L o (.) and L n (.). But mass points cannot be ruled out a priori and when prices are changed around a mass point in the mixed strategies, the comparison between the short term and the long term impacts requires the full construction of the continuation payoffs as a function of the state variable.

Following the discussion of Proposition 2, we look for an equilibrium with strategies that reward previous customers, i.e. with the following features:

• for any realization of prices in R + , the state variable characterizes which firm had the lowest price for new consumers at the previous period (or which firm served all the shoppers in case of equal prices for new consumers at the previous period);

• the support of H(.) is [p, v], the support of L o (.) is [p, p], the support of L n (.) is [p, v];
• H(.), and L o (.) are absolutely continuous, while L n (.) has a mass point at v.

An equilibrium of this type should satisfy the following equilibrium conditions:

V L = max po≤v p o [l + sH(p o )] (1)
+ max pn≤v {p n [l + sH(p n )] + δV L H(p n ) + δV H (1 -H(p n ))} = p(l + s) + vl + δV H (2)
= p(l + sH(p))

+ vl + δV H (3) = p(l + s) + p(l + sH(p)) + δV L H(p) + δV H (1 -H(p)), (4)
V H = vl + (5)
max q<v {q[l + sL o (q) + sL n (q)] + δV L L n (q) + δV H (1 -L n (q))} = vl + p(l + 2s) + δV L = vl + p(l + s) + δV L (6)
≥ vl + v(l + s 2 L n (v)) + δV H (1 -L n (v)) + δ V L + V H 2 L n (v). (7)
The main lines ((1) and ( 5)) rule out profitable deviations below v, the subsequent lines make explicit the indifference or dominance relations when pricing occurs at one of the threshold p, p or v. It is a simple, although tedious, matter to solve for the variables (p, p, H(p), V H , V L ) that completely determine the candidate equilibrium and subsequently, to check that indeed no deviation is profitable for any payoff-relevant history. We obtain the following characterization result of a symmetric Markov-perfect equilibrium.

Proposition 4 : In the model of price discrimination with myopic consumers, there exists a unique equilibrium with previous customers reward of the posited form:

p and p are characterized by:

v p = 1 + s 1 -s - 4s 2 (1 -s)(1 + 3s) δ 1 + δ v p = (1 + s) 2 (1 -s)(1 + 3s) - 4s 2 (1 + s) (1 -s)(1 + 3s) 2 δ 1 + δ ;
the L-firm charges random prices (p o,L , p n,L ) given by the marginal d.d.f. with disjoint adjacent supports:

L o (p) = (1 + s)(p -p) 2sp on [p, p] L n (p) = (1 + s)p -δ 1+δ 2sp -(1 -s)p 2sp -δ 1+δ 2sp on [p, v)
and L n (.) has a mass λ = 1-s 1+s at v; the H-firm charges p o,H = v on its old customers and p n,H according to the d.d.f.

H(p) = (1 + s)p -(1 -s)p 2sp on [p, p] = (1 -s)(v -p) 2sp -δ 1+δ 2sp on [p, v];
The intertemporal value functions are given by:

V L = (1 + s)p 1 -δ [1 + s 1 + 3s δ 1 + δ ] V H = p 1 -δ [1 + 2s - δs 1 + δ (1 + 2s 1 + 3s )] = V L + sp 1 + δ .
The equilibrium characterized in the previous proposition exhibits a remarkable feature: the L-firm charges uniformly lower prices for its own previous customers than for its new customers, i.e. its previous customers are rewarded in equilibrium. This feature is in striking contrast with the usually described pricing strategies in behavior-based price discrimination models in which, firms usually extract more surplus from their previous customers than from the consumers they have never served.

In our model, the firm that has perfectly identified its previous loyal customers actually extracts all their surplus (p o,H = v). To understand the L-firm's behavior, we can start from the intuition given in the static framework after Proposition 2. If the firm that has not identified its customers (the L-firm) adopts an asymmetric pricing strategy, choosing a stochastically low price p o,L for its own previous customers, it is more aggressive with respect to the rival and to ensure the rival is willing to mix, it has to adopt a stochastically high price p n,L for its new customers. The dynamic setting introduces a new effect: charging a high price p n,L on new customers enables the L-firm to become with high probability the future H-firm, that is the firm that identifies its loyal customers and is able to extract their surplus later on. The profitability of the H-firm position at t + 1 therefore creates an additional incentive at t for shifting probability weight on high values of p n,L , and consequently for shifting probability weight on low values of p o,L , i.e. for increasing loyalty reward. Note that it similarly creates an incentive for the H-firm to charge higher prices towards its new customers, i.e. to shift probability weight on higher values of p n,H compared to the situation with δ = 0.

Our model therefore enables us to characterize a behavior that consists in rewarding previous customers, which does not hinges on the use of long-term contracts. The argument relies on the profitability of identifying one's young loyal consumers and on the impossibility of discriminating among old and young shoppers when the firm has never served any of them.

Unsurprisingly, when δ goes to 0, the equilibrium above converges to the repetition of the static equilibrium in Proposition 2. The dynamic race to the H-firm position then vanishes. As δ increases, it is easy to prove that p and p increase and that the price distributions shift in the sense of first order stochastic dominance so that higher prices become more likely: price competition becomes less intense as δ increases, i.e. as the incentives to enter a race for the H-firm position become more pregnant. Also, when δ increases, the per-period profit of the L-firm improves while the per-period profit of the Hfirm position diminishes: (1δ)V L increases and (1δ)V H decreases. The L-firm engages in a race to ensure the next H-firm position and therefore enjoys the benefits associated to the H-position eventually; similarly, the H-firm does not secure the H-position for ever.

Corollary 5 Behavior-based price discrimination, when it results in the equilibrium with previous consumers reward, increases the profits of both firms at the expense of consumers.

It is immediate to check that V J > V for J = H, L, which means that behavior-based price discrimination boosts the industry profits in comparison with uniform price competition. This result is driven by the surplus appropriation effect of price discrimination against recognized old captive customers and the related pursuit of young loyal customers recognition. It is in line with Chen and Zhang (2009). But, here a novelty arises in the sense that even the firm that did not recognize its old loyal customers derives a higher profit on its segment of previous customers. This effect is a direct consequence of the loyalty reward: it is due to the infinite nature of competition and to the structure of information available to firms that make the L-firm benefit, on its segment of previous customers, from the price softening effect induced by the race for young consumers recognition. In our model, welfare does not depend on the type of competition and is fixed to 2v by period. Consequently the profit boosting effect from price discrimination comes at the expense of the consumer surplus.

The advantage of becoming the H-firm constitutes an incentive for both firms to charge higher prices for their new customers; by the same token, it also implies that the other equilibrium configurations that appeared in the static framework do not constitute equilibrium configurations anymore in a dynamic context, as they relied on a knife-edge strategic indifference between both price components of the L-firm. Given the difficulty of constructing the whole continuation valuations for any possible equilibrium configurations, we have not been able to prove that any symmetric Markov-perfect equilibrium is necessarily such that it rewards old customers. However following a similar construction as in our main existence result, we can exhibit a set of impossibility results for several natural configurations: [START_REF] Gehrig | Differentiated-Induced Switching Costs and Poaching[END_REF] • there exists no symmetric Markov perfect equilibrium such that all prices except p o,H are drawn from absolutely continuous mixed strategies H(.), L o (.), and L n (.);

• there exists no symmetric Markov perfect equilibrium such that the L-firm de facto does not price discriminate between its previous and its new customers, i.e. such that p o,L = p n,L ;

• there exists no symmetric Markov perfect equilibrium (with absolutely continuous d.d.f. except perhaps at v) such that the L-firm extracts surplus from its previous customers and charges low prices on its new customers, i.e. such that Pr{p n,L < p o,L } = 1.

The first impossibility result shows that any mixed strategy equilibrium involves mass points in the price distribution, which, as explained before, requires a full analysis of the global long term consequences of local changes in prices. Proposition 4 falls short of proposing a uniqueness result precisely because of the difficulty in dealing with the possibility of mass points. The second result shows that the L-firm has a strict incentive in discriminating among its customers, contrary to the static result in Proposition 2;

as suggested earlier, this is due to the desirability of acquiring the H-firm position in a dynamic context. The last result rules out more aggressive prices on new customers than on previous customers, a configuration that was also possible in the static model.

Price discrimination with forward-looking consumers

We now turn to the case of non-myopic consumers: β > 0. Consumers' behavior can exhibit two types of patterns that were absent in the previous section: a young loyal consumer may decide not to buy so as to avoid being identified and being charged an excessive price by his favorite firm when old; and a young shopper may decide either not to buy or even to buy from the highest-price firm so as to benefit from a more advantageous array of prices when old.

The equilibrium with loyalty reward exhibited in Proposition 4 is disrupted by such strategic manipulation. Suppose v > p t n,1 > p t n,2 , which is possible since H(.) and L n (.) overlap in a right neighborhood of v, so that at t + 1 firm 1 will become the H-firm. If he buys from firm 1, a young consumer loyal to firm 1 is identified as a loyal customer and is charged p t+1 o,H = v, which leaves him with no surplus when old. If instead the consumer does not buy when young, he will face a price distribution H(.) when old, the expectation of which is bounded away from v: in expectation, he will therefore enjoy a positive surplus, which makes this deviation profitable even for small β when p t n,1 is close enough to v. This suggests that firms cannot charge prices too close to v in equilibrium.

As in the previous section, we cannot pursue the ambition of characterizing all equilibria. The definition of an equilibrium itself requires some clarification with strategic consumers. Consumers' demand cannot be mechanically determined as previously, since young consumers' choices depend on their expectations about the future prices. Moreover, the state variable that describes the payoff-relevant history should record the proportions of loyal consumers and of shoppers served by each firm. Properly defining general Markovperfect equilibria in our setting would therefore be quite cumbersome. [START_REF] Gehrig | History-based price discrimination and entry in markets with switching costs: a welfare analysis[END_REF] In the following, we adopt a more modest approach. We present a mild modification of the Markovian strategies of our previous equilibrium with loyalty reward and show that, for a range of small discount factors β, they support a (Markov-perfect) equilibrium in the following sense: no firm and no (individual) consumer has any profitable deviation after any history of prices either on the equilibrium path or off the equilibrium path, in any subgame subsequent to a price deviation by one firm. [START_REF] Kim | Customer Information Sharing: Strategic incentives and new implications[END_REF] More precisely, let the L-firm at period t be the firm who had the lowest price for its segment of new customers at period t -1; the other firm is the H-firm. Strategies on the equilibrium path are as follows: the H-firm charges p o,H = v and chooses p n,H according to a d.d.f. H * (.) with support [a, ā], form some ā ≤ v; the L-firm chooses (p o,L , p n,L )

according to a joint distribution with marginal d.d.f. L * o (.) and L * n (.) respectively, L * o (.) has support [a, â] and L * n (.) has support [â, ā] with a mass at ā; young consumers purchase at the lowest acceptable price to them if and only if this price is not larger than ā, and they refrain from consuming when the lowest acceptable price is larger than ā; old consumers follow their static dominant strategy, as previously. These behaviors are similar to the ones generated by the equilibrium with reward of previous customers when consumers are myopic, except for the maximal price ā that firms can charge in equilibrium.

The description of the strategies off the equilibrium path is presented in the Appendix.

In subgames following any price deviation below â or a, the same behavior as on the equilibrium path is prescribed. After a deviation on a price above ā at t-1, the prescribed behavior at t relies on similar price distributions, with the same maximal price ā and other thresholds âθ and a θ determined by the proportion θ of loyal consumers served by the deviating firm at t -1, followed by a reversion to the on-the-equilibrium-path behavior from period t + 1 on, or repeated in case again of a deviation at t. The maximal price ā is determined so that no individual consumer has an incentive to deviate from the straightforward behavior he would follow if he were myopic, provided firms price below ā, but not all young loyals consumers of a firm purchase from this firm when it charges a price above ā.

As suggested above, the possibility that consumers strategically refrain from buying when young so as to ensure better conditions when old implies that the maximal price ā will be strictly smaller than v. The next proposition shows in what sense Proposition 4 is robust to forward-looking consumers: the above described behaviors are part of equilibrium strategies in the general case of non-myopic, but impatient enough consumers. Proposition 6 : For small enough values of the consumers' discount factor β, there exists an equilibrium with reward of previous customers by the L-firm, characterized by a maximal price ā strictly smaller than v.

Proposition 6 shows that strategic loyalty rewards can survive to the intertemporal considerations of forward-looking consumers. When consumers become very patient, the equilibrium is likely to be qualitatively different with consumers who forgo their purchase when young to have a better price when old. The characterization of such equilibria is beyond the scope of this paper.

A last remark is worth mentioning regarding the interpretation of market segmentation. In the marketing and the economics literature, the model of Varian (1980) is indifferently used to model heterogeneity in consumers' preferences (loyal consumers vs price-sensitive consumers) or in consumers' information (uniformed consumers who know only one price vs informed consumers who know all prices). These two interpretations usually make no difference for the resolution of the model. But, in our analysis, the interpretation matters. Under the preference interpretation that we have adopted, consumers know the prices charged by all firms and consequently perfectly anticipate which firm will become the H-firm or the L-firm and can react accordingly. Under the informational interpretation, captive consumers do not observe the prices offered by their non-preferred firm and consequently do not know which firm will become the H-firm or the L-firm. They must form expectations, based on the price they are offered and their knowledge of the equilibrium price distributions. This would require an even higher computational capability for consumers than in the preference interpretation. We do not formally address this issue.

Conclusion

In this article, we have analyzed an infinite competition model with overlapping generations and firms that are able to recognize their own previous customers when charging prices. A symmetric Markov-perfect equilibrium of this game exhibits interesting properties regarding which segments of customers (i.e previous or new customers) a firm should offer a better price. We found that the firm that has recognized its old loyal customers charges a lower price to its new customers than to its own previous customers. But we showed that the firm that did not recognize its old captive consumers charges its previous customers a lower price, in contrast with much of the literature on behavior-based price discrimination. This loyalty reward is a strategic means to hamper its rival to recognize its young loyal consumers. These results hold for myopic consumers and forward-looking consumers as long as their discount factor is not too high.

B Proof of Proposition 4

Under the assumption about the form of the equilibrium, one can obtain the following necessary conditions by writing down the optimality of q = p, q = p, p o = p, p n = v, p o = p, and p n = p:

V H = vl + p(l + 2s) + δV L p(l + 2s) = p(l + s) V L = p(l + s) + vl + δV H p(l + s) = p(l + sH(p)) vl = p(l + sH(p)) -δ(V H -V L )H(p).
It is a simple, although tedious, matter of computation to solve this system of 5 equations within the 5 variables (p, p, H(p), V H , V L ) and to obtain the expressions in the proposition. Note, for further reference, that a side result is:

(1 + δ)(V H -V L ) = (l + s)(p -p) = sp > 0.
It follows:

V L = vl + (s + l)p 1 -δ + δsp 1 -δ 2 V H = vl + (s + l)p 1 -δ + sp 1 -δ 2 .
The expressions for p and p show trivially that 0 < p < p < v. Simple computations

also show that L o (p) = 1, L o (p) = 0, L n (p) = 1, H(p) = 1, H(.
) is continuous at p and

H(v) = 0. Moreover, L o (.), L n (.
) and H(.) are strictly decreasing. Using the expression of v p , it is a simple matter of tedious computation to prove that: λ = 1-s 1+s , hence λ > 0. We now investigate possible deviations, assuming that firms' continuation strategies are of the same nature, depending on which firm offered the highest / lowest price previously to new consumers, even if this price is below p. Indeed, deviations below p have no future impact and only limits the margin earned by a firm: they cannot be profitable. [START_REF] Maskin | Markov Perfect Equilibrium: Observable Actions[END_REF] What about deviation within [p, v]? Given H(.), let us consider the L-firm's possible

deviations to p o ∈ (p, v]: then, p o [l + sH(p o )] = vl + δ 1+δ sp (v-po) sp o -δ
1+δ sp , which is decreasing in p o , hence smaller than its value for p. There is no profitable deviation for the L-firm with respect to p o . Let us consider L-firm's deviations to p n ∈ [p, p): then,

p n [l+sH(p n )]-δH(p n )(V H -V L )+δV H = (s+l)p+ δl s (V H -V L )- δ(V H -V L )(s + l)p sp n +δV H ,
which is increasing in p n , and therefore smaller than its value for p. Therefore, there is no deviation for the L-firm with respect to p n either.

Given L o (.) and L n (.), the only possibly profitable deviation for the H-firm could be to charge q = v. When the H-firm charges q and q ↑ v, its profit on new customers is:

v(l + sλ) + δλV L + δ(1 -λ)V H
while by charging exactly q = v, the H-firm gets:

v(l + s λ 2 ) + δλ V H + V L 2 + δ(1 -λ)V H
on new customers. The deviation on q = v is unprofitable if and only if:

vs ≥ δ(V H - V L ) ⇐⇒ v ≥ p δ 1+δ
, which is trivially true. This completes the proof.

C Proof of Proposition 6

Preliminary step: a mixed strategy equilibrium in an auxiliary game.

Fix parameters θ ∈ [0, 1], x ∈ [0, v] and ∆ > 0, such that: δ∆ < xs. [START_REF] Maskin | Markov Perfect Equilibrium: Observable Actions[END_REF] We have a priori restricted prices to be not larger than v. It is possible to relax this restriction and prove that firms will not charge above v. This requires to specify the strategies in continuation subgames after a deviation above v: this can be done as a special case of the proof of Proposition 6. The construction, however, is rather involved and in the current proof, we have chosen the a priori restriction in order to facilitate the reading.

Consider a one-period game between a so-called H θ -firm and a so-called L θ -firm, facing a global population of 2l loyal consumers for each firm and 2s shoppers. All consumers are myopic. The H θ -firm has identified a group of θl loyal customers to whom it can propose a price q 0 , and a group of (2θ)l + 2s consumers, among whom (2θ)l are loyal consumers and 2s are shoppers, and to whom it can propose a price q. The L θ -firm can propose a price p o to a group consisting of l loyal consumers and s shoppers and a price p n to a group consisting of the other l loyal consumers and s shoppers. On top of revenue from sales, if q > p n the H θ -firm gets a bonus equal to δ∆, if p n > q the L θ -firm gets this same bonus; in case of equal prices, the bonus is granted with equal probability to one firm or the other. Finally, suppose prices (q, p o , p n ) are constrained to belong to [0, x].

We look for a mixed strategy equilibrium of this auxiliary game of the following form:

• the H θ -firm charges q 0 = v and draws q according to the d.d.f. H θ (.) with support [a, x);

• the L θ -firm draws p o and p n according to L θ o (.) on [a, â] and L θ n (.) on [â, x] with a mass point at x. Consider the following system with unknown variables (a, â, Ĥ):

a(l + s) = â(l + s Ĥ) = lx + δ∆ Ĥ a((2 -θ)l + 2s) = â((2 -θ)l + s).
The solution is given by:

Ĥθ = (1 -θ)l + s (2 -θ)l + 2s âθ (x, ∆) = xl + δ∆ Ĥθ l + s Ĥθ a θ (x, ∆) = xl + δ∆ Ĥθ l + s .
This solution is such that for all θ ∈ [0, 1), x ∈ [0, v] and ∆ > 0, Ĥθ ∈ (0, 1) and âθ (x, ∆) > a θ (x, ∆) > 0. Moreover, âθ (x, ∆) < x ⇔ δ∆ < xs.

The overall price distributions are given by: p(l + sH θ (p)) = a(l + s) for p ∈ (a, â)

p(l + sH θ (p)) + δ∆(1 -H θ (p)) = xl + δ∆ for p ∈ (â, x) p((2 -θ)l + s + sL θ o (p)) = a((2 -θ)l + 2s) for p ∈ (a, â) p((2 -θ)l + sL θ n (p)) + δ∆(1 -L θ n (p)) = â((2 -θ)l + s) for p ∈ (â, x).
It is immediate to check that these equalities define d.d.f, that lim p→x H θ (p) = 0,

lim p→â L θ o (p) = 0 and lim p→x L θ n (p) = [(2-θ)l+s]θl [(2-θ)l+2s]l+s[(1-θ)l+s]
[sx-δ∆] > 0, which corresponds to the mass at x. Finally, note that Ĥθ decreases in θ. So, a θ (x, ∆) decreases in θ while âθ (x, ∆) increases in θ. Moreover, it is immediate to show that the cumulative distribution function 1-H θ (.) increases in θ: so, when θ increases, the distribution of prices q changes to smaller prices in the sense of first-order stochastic dominance. E H θ [q] is a continuously differentiable decreasing function of θ, with bounded derivative for θ ∈ [0, 1].

Step 1: necessary condition based on the analysis of firms' behavior on the equilibrium path.

Consider first the firms' behaviors. Fix ā. Let us characterize the variables (a, â, H * (â), V * L , V * H ) that can possibly form equilibrium strategies for given ā, assuming consumers behave as posited. The analysis is similar to the analysis of the case with myopic consumers, with ā instead of v as the maximal possible price. The following must then hold:

V * H = vl + a(l + 2s) + δV * L (10) a(l + 2s) = â(l + s) (11)
V

* L = a(l + s) + āl + δV * H (12) a(l + s) = â(l + sH * (â)) (13)
āl = â(l + sH * (â)) -δ(V * H -V * L )H * (â). ( 1 4 )
From ( 10) and ( 12), one gets:

V * H -V * L = (v -ā)l + as 1 + δ .
Then, using the preliminary step with θ = 1, x = ā and ∆

= V * H -V * L = (v-ā)l+as 1+δ
, and using the notation φ = δ 1+δ , it comes:

H * (â) = s l + 2s = 2s 1 + 3s [(l + s)(l + 2s) -s 2 φ]a = slφv + l(l + 2s -φs)ā (l + s) 2 â = slφv + āl(l + 2s -φs) + asφ.
Given that φ ∈ [0, 1/2], these equations imply that a is an increasing affine function of ā, and so is â. Now, for ā = v, these equalities lead to the solution with myopic consumers namely, p and p, for which we know that p < v. Therefore, there exists A 1 < v such that for all ā ∈ (A 1 , v), δ(V * H -V * L ) < ās, i.e. there exists an admissible solution (a, â, H * (â), V * L , V * H ) to the system ( 10)-( 14) (with â < ā): this solution enables us to construct the candidate equilibrium by writing down that payoffs are constant within the supports of price distributions:

p o (l + sH * (p o )) = a(l + s) for p o ∈ (a, â) (15) p n (l + sH * (p n )) -δH * (p n )(V * H -V * L ) = āl for p n ∈ (â, ā) (16)
q(l + s * L o (q) + sL * n (q)) + δ(1 -L * n (q))(V * H -V * L ) = a(l + 2s) for q ∈ (a, ā), (17)
with L * o (.) having support (a, â) and L * n (.) having support (â, ā] and a mass at ā.

Step 2: condition for no deviation by consumers when they anticipate future prices on the equilibrium path.

Consider first the condition for a young loyal consumer of the L-firm to buy at some period, given the continuation equilibrium path: for all (p n , q) such that

p n < q, v -p n + β[v -E L * o [p o ]] ≥ β[v -E L * n [p n ]]
and for all (p n , q) such that

p n > q, v -p n ≥ β[v -E H * [q]].
The first condition always holds while the second requires that it be satisfied for the highest possible value of p n , i.e.:

v -ā ≥ β(v -E H * [q]).
The case of a young loyal consumer of the H-firm leads to the same condition.

Finally, consider the case of young shoppers. They buy from the lowest price firm instead of buying from the highest price firm provided for all (p n , q),

v -inf{p n , q} + β[v -E L * o ,H * [ inf{p o , q}]] ≥ v -sup{p n , q} + β[v -E L * n [p n ]],
and instead of refraining from buying provided for all (p n , q),

v -inf{p n , q} + β[v -E L * o ,H * [ inf{p o , q}]] ≥ β[v -E L * n ,H * [ inf{p n , q}]]. Since E L * o ,H * [ inf{p o , q}] ≤ â < E L * n [p n ] and E L * o ,H * [ inf{p o , q}] ≤ E L * n ,H * [ inf{p n , q}], both inequalities are always fulfilled. To summarize, if v -ā ≥ β(v -E H * [q]
) and consumers anticipate prices on the equilibrium path, all loyal consumers buy from their corresponding firm and all shoppers buy from the lowest-price firm.

We will concentrate on ā that solves this condition as an equality: v-ā β = v -E H * [q] (remember that H * (.) depends ā). The LHS of this equality is decreasing in ā, from v β > v for ā = 0, to 0 when ā = v. Since H * (.) depends continuously on ā and has a support strictly included in (0, v) for all ā, the RHS is bounded away from 0 for ā ≤ v. It follows that for any A * < v, there exists β 1 (A * ) > 0 such that for all β ∈ (0, β 1 (A * )), there exists

ā ∈ (A * , v) that solves v-ā β = v -E H * [q].
Step 3: considering the continuation strategies after a deviation by one firm.

Up to now, we have only described the strategies on the equilibrium path, that is for all prices within the support of their respective distributions. To complete the characterization of the equilibrium, we need to give the nature of the strategies in subgames following a deviation by one firm. [START_REF] Narasimhan | Competitive Promotional Strategies[END_REF] Many deviations can be handled with very quickly and we will see that only deviations above ā require some care.

charges v on its θl past consumers and plays according to H θ (.) at period t + 1, while the non-deviating firm plays according to (L θ o (.), L θ n (.)). If both firms play this way at t+1 (or deviate still charging below ā), firms resume the strategies H * (.) and (L * o (.), L * n (.)) that are played repeatedly on the candidate equilibrium path afterwards. If another deviation above ā occurs at τ ≥ t + 1, inducing θ 0 l loyal consumers to buy from the deviating firm, firms revert to H θ 0 (.) and (L θ 0 o (.), L θ 0 n (.)) at τ + 1 and resume the strategies H * (.) and (L * o (.), L * n (.)) afterwards. First, we focus on the consumers. On the equilibrium path, all prices are smaller than ā and therefore loyal consumers buy from their firm and shoppers buy from the lowest-price firm. In a subgame following a deviation at t characterized by θ, young loyal consumers still face at t + 1the prospect of an expected price equal to E H * [q] or E L * n [p n ] at t + 2 if they decide to abstain from consuming at t + 1: therefore, with all prices below ā they should also buy from their firm when young (see step 2). Finally, in case of a deviation at t, the young loyal consumers of the deviating firm at t have to compare consuming, i.e. enjoying an intertemporal utility of vρ, or abstaining and enjoying an intertemporal utility of β[v -E H θ [q]]. Equilibrium requires that if θ ∈ (0, 1), then ρ and θ are related by:

v -ρ = β[v -E H θ [q]],
while if θ = 0, then necessarily: vρ ≤ β[v -E H 0 [q]]. This enables us to define the mapping R(.) that characterizes the highest price deviation above ā that induces exactly θl young loyal consumers to buy still from the firm at t. R(1) = ā, R(0) = v, and for θ ∈ (0, 1), R(θ) ∈ ((1β)v, v), R(.) is continuously differentiable decreasing over (0, 1)

and 1 β | dR dθ |=| d[E H θ [q]] dθ | is bounded.
We finally need to prove that for all θ, a deviation leading to θ, hence characterized by ρ = R(θ), is not profitable for the deviating firm, given the hypothesized continuation.

Consider that at t, the L-firm deviates at R(θ) > ā. It must be that: Given that 1 β | dR dθ | is bounded, there exists β 2 such that for all β ∈ [0, β 2 ), the RHS is strictly decreasing in θ; as it is null for θ = 1, it follows that the RHS is positive for all θ < 1. Tedious but straightforward computations show that the LHS is equal to

(1 -θ)lδ[ δ(V * H -V * L )+āl s+l -v]. For ā > A 1 , δ(V *
H -V * L ) < ās and therefore the LHS is smaller than (1θ)lδ(āv), that is the LHS is negative. The condition of no-deviation by the L-firm is therefore satisfied.

Consider now a deviation at t by the H-firm to R(θ). It is not profitable if:

V * H ≥ vl + R(θ)θl + δ[θlv + a θ ((2 -θ)l + 2s) + δV * L ]
.

Using V * H = V * L + (V * H -V * L )
, the same decomposition of V * L and the same rearranging of terms, the condition can be written as:

δ[(a θ -a)(l + 2s) -(1 -θ)l(v -a θ )] ≤ (ā -θR(θ))l + (V * H -V * L ) + a(l + s) -vl.
A new term appears compared to the condition of no-deviation by the L-firm, which is:

a(l + s) -vl = (V * H -V * L )(1 + δH * (â)) -(v -ā)l.
Given the analysis at step 1, there exists A 3 < v, such that for all ā > A 3 , this term is positive and therefore this no-deviation condition holds when the condition for the L-firm holds.

To terminate, we have to look for the no-deviation condition of the H θ 0 -firm and the L θ 0 -firm in the period immediately following a deviation (by the now H θ 0 -firm) that lead to θ 0 . The non profitability for the L θ 0 -firm of a deviation leading to θ writes down (omitting the profit on its previous consumers):

āl + δV * H ≥ R(θ)θl + δ[θlv + a θ ((2 -θ)l + 2s) + δV * L ].
Writing the LHS as: āl + δ[vl + a(l + 2s) + δV * L ] leads to the same condition as the nodeviation condition by the L-firm. The non profitability for the H θ 0 -firm of a deviation leading to θ writes down (omitting the profit on its previous consumers):

((2θ 0 )l + 2s)a θ 0 + δV * L ≥ R(θ)θl + δ[θlv + a θ ((2θ)l + 2s) + δV * L ].

We know that the RHS is smaller than V * Hvl (no-deviation of the H-firm), hence than a(l + 2s) + δV * L . Moreover, a θ 0 ≥ a (preliminary step) and so:

((2θ 0 )l + 2s)a θ 0 ≥ a(l + 2s).

Hence, the no-deviation condition of the H θ 0 -firm.

To conclude, let A * = sup{A 1 , A 2 , A 3 } < v and let β * = inf{β 1 (A * ), β 2 }, such that for any β ∈ [0, β * ), the strategies characterized in the proof with ā solving v-ā β = v -E H * [q], constitute an sequential equilibrium of the all game. This completes the proof.

  . It has then been extended in several directions: asymmetry among firms (Chen (2008) and Gehrig et.al (2011)), changes in consumers' preferences (Chen and Pearcy (2010) and Shin and Sudhir (2010)), link with firms' advertising strategies (Esteves (2009)), discrete distribution of consumers' preferences (Chen and Zhang (2009) and Esteves (2010)), enhanced services (Aquisiti and Varian (2005) and Pazgal and Soberman (2008)), complement goods (Kim and Choi (2010)) and endogenous product design

  V * L ≥ a(l + s) + R(θ)θl + δ[θlv + a θ ((2θ)l + 2s) + δV * L ].Using the decomposition: V * L = a(l + s) + āl + δ[vl + a(l + 2s) + δV * L ], the no-deviation condition by the L-firm is equivalent to:δ[(a θa)(l + 2s) -(1θ)l(va θ )] ≤ (ā -θR(θ))l.

  L-firm, faces two identical segments, consisting of l loyal consumers and s shoppers each; one of them (price p o,L ) can be viewed as consisting in the firm's previous customers, the other one (price p n,L ) consisting in new-born consumers. The H-firm will obviously charge p o,H = v on the segment of identified previous loyal customers. Figuring out the static equilibrium in prices in this situation involves solving a problem à la Varian with two price instruments and overlapping segments of consumers. We merely state the result and omit the proof that follows the same technical steps asNarasimhan (1988). and p n,L are jointly distributed on [a S , v] 2 so that, letting L S o (.) and L S n (.) denote the marginal d.d.f. w.r.t. p o,L and p n,L of the joint d.d.f., L S o

[START_REF] Esteves | Pricing with Customer Recognition[END_REF]

Proposition 2 : In the static price setting game with price discrimination, there exists no pure strategy equilibrium; in any mixed strategy equilibrium, p n,H is distributed according to the absolutely continuous d.d.f. H S (p) = (1-s)(v-p) 2sp on [a S , v], with a S = 1-s 1+s v, p o,L

See alsoEsteves (2009) about the competition softening effect of the pursuit of customers recognition

Basically this is a duopoly version of[START_REF] Varian | A Model of Sales[END_REF].

In practice, it would be expected that firms are more or less certain about the size of the segments. Thus, our results should be interpreted as the solution to an important limit case.

In this simple model, the form of profits in case of a tie can be viewed as the outcome of a standard

The precise derivation of the price distribution and of the critical thresholds can be obtained as a special case of the preliminary step in the proof of Proposition 6 in the Appendix.

More precisely, the conventional tie breaking rule delivers the same characterization of equilibrium strategies on the equilibrium path as in our model, but it requires to specify strategies also after an event of equal split of shoppers facing equal prices, an event that occurs with zero probability on the equilibrium path: since the specification of the strategies in these events does not convey additional economic intuition, we have chosen a tie-breaking rule that makes such events impossible even after deviations.

As is intuitive, prices cannot be larger than v in equilibrium. Allowing prices to fall above v and describing equilibrium strategies after some deviation above v is however extremely heavy. We choose not to present these complications in this section. The proof of proposition 6, however, explains, in the general case of strategic consumers, how to deal with such price deviations and what are continuation strategies.

The non-existence of pure strategy equilibrium is robust to the choice of the tie breaking rule; it is however much more tedious to prove with the equal split rule than with our stochastic tie-breaking rule.

The proofs of these claims mimic the proof in Proposition 4 until they lead to a contradiction.Reaching the final contradiction, however, requires to compute all equilibrium variables, a tedious and insightless approach that we have chosen to skip.

On the general theory of Markov-perfect equilibria, see Maskin -Tirole (2001). In our setting in which only prices are observed, tools developed by Fershtman and Pakes (2009) should be used.

Note first that since strategies are mixed, so the issue is about deviating on prices above the maximal observable price (low prices can be easily handled). We omit the description of strategies in subgames following price deviations by both firms above the maximal observable price. This enables us to reduce the possible values of the state variables to the H-firm / L-firm statistics and the proportion of loyal consumers served when a price exceeds the maximal observable price. A full description of strategies, and of the associated Markov-perfect equilibrium, is possible but it would require an extremely heavy presentation and Appendix, without any economic insights.

To describe strategies in all possible subgames, one would have to consider subgames with any

A Proof of Proposition 3

Suppose there exists a pure strategy equilibrium, characterized by equilibrium prices p o,L , p n,L , p o,H , p n,H .

The price p o,L targets old loyal customers of the L-firm and competes with p n,H for old shoppers that bought from the L-firm. Therefore, in equilibrium, it cannot be that p o,L < p n,H , as p o,L could be increased profitably; it cannot be that p n,H < p o,L < v either, since p o,L could be increased up to v profitably, and it cannot be that p o,L = p n,H , since p o,L could be slightly decreased with a jump in demand. This implies that p o,L = v. p o,H only targets old loyal customers of the H-firm and should therefore be set at v.

In equilibrium, it cannot be that p n,L < p n,H , since then p n,L could be increase profitably. Similarly for the strict reverse inequality. Therefore, one must have p n,L = p n,H = p. So, it comes:

From these, it immediately follows that: V H -V L = ps > 0.

The L-firm prefers charging p o,L = v instead of p o,L = pε, for ε small, which would enable it to serve the old shoppers: that is, it is necessary that:

The L-firm also prefers charging p n,L = p instead of charging p n,L = v -ε, which would enable it to enjoy a high mark-up on its young loyal customers and to become the next H-firm for sure: that is, it is necessary that:

Since

; also vl ≥ p(l + s) implies that vl > p(l + s 2 ). Therefore (9) cannot be satisfied.

Consequently, there does not exist a symmetric Markov perfect pure strategy equilibrium.

Suppose that all behaviors are as specified in step 1 after a deviation in p o,i ; this is natural since only old consumers are concerned and they will not be around in the future.

Given how a has been determined at step 1, it is immediate that there exists A 2 < v such that for any ā ∈ (A 2 , v) and associated a, the above inequality is satisfied.

Consider now deviations in p n,i . Deviations below a can be immediately disregarded, if they are treated in the continuation strategies as if no deviation had taken place: this is so because the deviating firm then simply foregoes some profit it could have obtained by charging precisely a. Deviations within (a, â) for the L-firm are dealt with similarly, since on this interval, p(l + sH * (p)) is constant and therefore, p(l + sH * (p))δ(V * H -V * L )H * (p) is increasing, hence everywhere smaller than its value for â.

The more complicated type of deviations occurs for p n,i > ā. Suppose that the deviating firm at period t sets the price p t n,i = ρ ∈ (ā, v]. This firm charges the highest price at period t, so it gets no shoppers at period t. Whether it sells at t to its young loyal depends on these consumers' expectations about future prices in the continuation subgame. Suppose that θl young loyal consumers buy from this deviating firm at period t, θ ∈ [0, 1], then the situation at period t + 1 resembles the auxiliary game analyzed at the preliminary step. Then, let us specify strategies using this auxiliary game equilibrium strategies obtained for x = ā and ∆ = V * H -V * L . After the deviation, the deviating firm allocation of consumers among the various segments of each firm, solve for a mixed behavior as in the preliminary step, using ∆ = V * H -V * L and x = ā. For β small enough, these behaviors would induce consumers to behave as if myopic.


T T Pham
email: pham@cmi.univ-mrs.fr

R Jeansoulin
email: robert.jeansoulin@cmi.univ-mrs.fr

V Phan Luong

A J Comber

DETECTION OF LAND COVER CHANGE BY INTEGRATING INFORMATION UNDER LATTICE BASING ON THE COMPLETENESS AND CONSISTENCY

Keywords: Land cover change, semantic heterogeneity, completeness, consistency, information lattice, data integration

This paper examines issues in detection of land cover changes. Several causes are identified and treated separately before any relevant "change" decision: (a) errors in signal processing, (b) ontological disagreement on candidate classes, (c) real world updates.

Basing on these issues, we propose an information quality measure of information before detecting the land cover change. The approach to determine the change is composed the steps: (i) measurement of data quality, (ii) identification of semantic discordances to determine a possible common ontology of land cover classes, which is considered as an information lattice, (iii) integration of information integrating under a lattice based on quality.

Introduction

Land cover change detection has become a more common area of research in recent years. It takes as input very large data sources, which can be over entire countries and continents, and compares them, in order to record changes. It has been made possible by the introduction of spatial techniques and of large database facilities. However, direct comparison is problematic because of the large variety of onthe-ground situations containing in a limited number of identified thematic classes, and the user may ignore how the abstraction process was undertaken from raw data to derived thematic products. It is necessary, before integrating these data for time comparison, to identify possible semantic heterogeneity.

This paper proposes a solution to conclude about land cover change by integrating of land cover information under lattice basing on quality information. We consider the Land Cover Map of Great Britain of 1990 (LCMGB) and the UK Land Cover Map 2000 (LCM2k) as case study.

Section 2 describes the land cover change issues as ontological heterogeneity, data quality, and comparison of dominant land cover classes. Section 3 recalls the information lattice (Phan et al, 2003) which presents the basis for our solution. The notions of complementary and conflicting data are formalized, and the methods for integrating information to identify the consensus and aggregation are given. We propose a methodology to conclude about change, and the results for the case study with LCMGB and LCM2k in the Midlands.

Finally, some concluding remarks and future work are presented in Section 4.

Issues of land cover change

Given two thematic maps of an area, with different dates, there are the problem to resolve before conclude about landscape change: semantic heterogeneity, ontology change, quality of information,…

Ontology heterogeneity

Land cover information, as one of the major sources of geographic information, is highly heterogeneous in formats and semantics. The heterogeneities arise because land cover data are produced basing on different definitions, standards. For example, LCMGB [START_REF] Fuller | The Land Cover Map of Great Britain: an automated classification of Landsat Thematic Mapper data[END_REF] and LCM2k [START_REF] Fuller | Land Cover Map 2000, a guide to the classification system[END_REF][START_REF] Fuller | The characterization and measurement of land cover change through remote sensing: problem in operational application?. in int[END_REF] are produced by the same institution and from composite winter and summer satellite images. LCMGB is raster dataset, recording 25 Target land cover classes; LCM2k is vector dataset, data is provided as polygons of land parcel, and each parcel has a list of attributes attached to it. LCM2K contains different levels of class detail. The standard level of detail provides 26 Broad Habitat land cover classes. LCM2k is not directly comparable with LCMGB because of these heterogeneities.

Solving the problem of ontology heterogeneity, is difficult, is an important task as a preparatory step to the information integration to conclude the landscape change. The aim of ontology integration is building a common ontology or to finding the relation between the concepts of two different ontologies. Several approaches to the integration of heterogeneous ontologies are proposed in [START_REF] Worboys | Integration of Imperfect Spatial Information[END_REF][START_REF] Worboys | Integrating spatio-thematic information[END_REF], Foncseca et al (2002) and [START_REF] Stumme | FCA-Merge: Bottom-Up Merging of Ontologies[END_REF]. Comber et al (2003b) propose a semantic statistical approach for identifying change from ontologically divers land cover data. We aim to build a common ontology of LCMGB and LCM2k. In [START_REF] Pham | Correspondence between the attributes of ontologies[END_REF] we have proposed a method to determine the associations between the classes of two ontologies basing on the information in datasets. Further, there are many possible associations between two classes from two different hierarchies (classification systems), some are likely similarities, and some are likely dissimilarities. It is rather difficult to formalize what we mean by similarity and dissimilarity, but when asking an expert, he is in general able to take a decision and to fill up a table such as:

… l n c 1 1 -1 -1 c 2 0 1 -1 … c p -1 -1 1
This matrix, called a "Look-Up Table " (short: LUT), and precisely an "Expert LUT" can be used to determine a probable transition status between parcels:

For a parcel A, suppose that c i is unique classes of A at first date and l j is unique classes of A at second date,

if LUT(i,j) = 1, then A is unchanged, if LUT(i,j) = 0 then status of A is unknown, if LUT(i,j) = -1, then A is changed
We combine the result of our approach in [START_REF] Pham | Correspondence between the attributes of ontologies[END_REF] and the "Expert LUT" to determine a common ontology of LCMGB and LCM2k on each study zone.

For example, information lattice in Figure 1 represents the result of integration of ontologies. The node containing the classes of different datasets, for instance node in Figure 1, where 13.1 is a class of LCM2k and C1, C2 are classes of LCMGB, represents that there is the 13.1, C1, C2 correspondence between these classes. When we integrate the information of land cover classes (node) in a parcel A, if the consensus or aggregation is result in one of these nodes then A is unchanged, if the consensus of land cover classes in two dates is its super-class then we can conclude there are mismatches, or internal confusion, or reduced reliability. It depends on the distance between them and their consensus, if the consensus land cover classes in two dates is bottom then A is changed. We will clearly present this solution of change detection in Section 3.2.

Uncertainty and quality of information in land cover datasets

It may be impossible to represent a true landscape if definitions of soil classes are inherently uncertain or vague. For example, the classes of grass (improved grassland, acid grass, neutral grass,…) is internally heterogeneous. Besides, the lack of information is related to the quantity of information needed for recovering the truth. The lack of information causes the incomplete of dominant subclasses in each parcel. Land cover information consists of basic information describing the land cover classes that occupy the territory, and its assessments via the cartographic representations. When the lack of information of land cover classes exists then the determination of majority class or Broad Habitat (BH) class in each parcel is not exact. For this reason, there exist parcels where the attributed BHs are not the generalization of the dominant subclasses in the complement data (metadata).

For example, the important information (to change detection) is the list of percentage of cover classes (of LCMGB) and the BHs and it metadata (of LCM2k). We note that the information is incomplete (sum of the not null values of percentage is not 100%) then gives rise to the possibility of the inconsistency between BH and it metadata (see an example of data in Table 3). In LCMGB, the observation of land cover classes is imperfect because there exist the parcels which do not contain information of land cover. In LCM2k, the basic information is described by a list (Parcel#, PerPixList, BH,...) where PerPixList is a list of area percentages of the top five spectral subclasses recorded by satellite images within Parcel#. The descriptions of BHs (see Figure 1) were developed by the Joint Nature Conservation Committee. LCM2k aimed to contribute to the assessment of habitats by mapping, as far as possible, the widespread examples of terrestrial, freshwater and coastal Broad Habitats [START_REF] Fuller | Land Cover Map 2000, a guide to the classification system[END_REF]. We remark that there exist parcels, where the attributed BHs are not the generalization of the dominant subclasses in the parcel. Moreover, the attributed BHs may correspond to non-dominant subclasses.

A data quality measure

There are many aspects of data quality [START_REF] Veregin | Data quality parameters[END_REF] as correctness, accuracy, precision, completeness, consistency, relevance and timeliness, etc. In this work, we propose a measure of completeness and consistency of data in LCMGB and LCM2k datasets. We consider:

Completeness of information:

The sum of all percentages of non-null values of dominant classes is incomplete. The smaller sum of percentages of dominant classes corresponds to the lower quality.

Consistency: For each PerPixList, we regroup the subclasses following the lattice structure. For example, in the first line of Basing on the above ideas, we propose a method for measure the completeness and consistency of parcel:

Completeness = Â(percentage of dominant classes) Consistency = Rang of BH in TopList
For example, Table 3 represents information after regrouping of information in Table 2 and completeness and consistency in each parcel of its information are presented in Table 4 and Table 5.

Data quality based integration under lattice to detect the land cover change

Information lattice

An information lattice is a lattice (L, £), which contains top (inconsistent) and bottom (unknown). £ is partial order between the elements of L, top is maximal element and bottom is minimal element of L. Let x, y in L, if x £ y then y is called more complete or more specific than x. In the case L is a lattice of land cover classes if x £ y then y is subclasses of x. Let X Õ L such that X ≠ ∅, the set of all minimal (resp. maximal) elements of X is denoted by min(X) (resp. max(X)). The least upper bound of X, if exists, is denoted by ⁄X, and called the join of X. The greatest lower bound of X, if exists, is denoted by ŸX, and called the meet of X. In particular, if X = {x, y} then ⁄X and ŸX, respectively denoted by (x ⁄ y) and (x Ÿ y), always exist. We have (x Ÿ y) £x, y £ (x ⁄ y), and the following equivalence: x £ y if and only if x = (x Ÿ y), y = (x ⁄ y).

If (x ⁄ y) ≠ top, then x and y are called complementary to one another. If (x ⁄ y) = top, then x and y are called in conflict with each other. The conflict between x and y is called total if x Ÿ y = bottom, as x and y do not share any common information. Otherwise, the conflict is called partial, and x Ÿ y is called a consensus of x and y.

Let I and J be subsets of L. We define I J if I = ∅, or for each x OE I, there exists y in J such that x£y. J contains the information of I. I is called an information containment of J.

Let I and J be subsets of L, I is called a information equivalence of J if and only if I is an information containment of J, and J is an information containment of I.

Let (L, £) be an information lattice. Let I and J be subsets of L. If I and J are non-empty, then define the consensus and the aggregation of I and J to be respectively 1 represents an information lattice of land cover classes, 4.1 £ Ab or barley is subclass of arable cereal: 4.1 £ Am or maize is subclass of arable cereal. The consensus of 1.1 (broad-leaved wood) and C16 (conifer) is woodland. 13.1 (water) is total conflict with 17.1 (suburban). 8.1 (acid grass) is partial conflict with C8 (rough / marsh Grass). 5.1 (improved grassland) is a complement of 6.1 (neutral). There exists internal confusion between 5.1 (improved grassland) and 6.1 (neutral). It is called internal heterogeneity.

ƒ : I ƒ J = max{ x Ÿ y | xOEI, yOEJ } ⊕ : If I J (or J I) then I ⊕ J = max(J) (resp. max(I)), else I ⊕ J = max{ x ⁄ y | xOEI, yOEJ } Example: Figure

Data preparation

The necessary information to our methodology is:

-the information lattice which represents the common ontology of land cover classes, -the quality information is available in each datasets, -the "toplist" (list of regrouping the subclasses into level of Broad Habitat, remark that this list is sorted in descending order of percentages).

It means that each parcel A is described by triplet (A | toplist | completeness, consistency) in LCMGB and LCM2k, where A is the code of parcel, toplist is information of land cover classes. The lattice information will be used for integration process.

Integration for determination of consensus

Suppose parcel A is covered by only one class C i of LCMGB and class L j of LCM2k. In section 1, the consensus of C i and L j is C i ƒ L j = C i Ÿ L j = x. When x is in a same node of C i and L j , A is unchanged.

If C i and L j is subclasses of x then we can conclude there are the mismatch in A. In this case, the level of change-nochange depends on the "distance" between x and C i , L j . If the x is bottom then we can say that A is changed. The level of change is as following:

C i L j : ÿp (no change) C i L j : ÿ p' (no change with warning) C i L j : p' (indecision) … C i L j : p (change) When the parcel A is covered by many classes {C i } of LCMGB at first date, and many classes {L j } of LCM2k at second date. The change measure is calculated basing on the consensus of pair-wise of classes from two sources. This measure is represented in next section.

Query with the user's constraints on quality

The users can specify a quality level when querying the integration of land cover information to detecting the change. When the constraints on quality of user's queries are introduced, the integration process will choose the information, which satisfies the needs of user, for fusion. The constraint on quality is intended to limit the computation to parcels which present enough information for making a decision of change.

With the constraint on quality is completeness ≥ c 1 and consistency = {I}. For each parcel A, If com 1 (A) ≥ c 1 and com 2 (A) ≥ c 1 and con 1 (A) OE {I}and con 2 (A) OE {I} then the change/nochange conclusion is realized by integration process for detecting of change. Else the parcel is colored by white (lack information for change conclusion).

The integration process for detecting of change in the parcel: 1 st step: fusion toplist of LCMGB and toplist of LCM2K. It integrates a pair-wise of toplist to calculate the consensus of land cover classes. In each toplist, the classes in descending order play the different part to detecting the "change".

Toplist of LCMGB

Toplist of LCM2k

The major class plays the important part of "change". In order to present this, the classes of toplist are coded by binary code which is "degree of importance", each toplist = (1 st class, 2 nd class, …, n th class) is coded by (2 n-1 , 2 n-2 , … ,2 0 ), with n is maximal number of element in toplist of all parcels. We note that if a toplist have k elements, k < n, then element k+1, k+2, …n is null classes. It means that and coef(

1 st class) = 2 n-1 , … coef(2 nd class) = 2 n-2 …
The coefficient is assigned to each element (i,j) of this matrix:

coef(i,j) = coef(i) * coef(j)
For example, with the toplist = (1 st class, 2 nd class, 3 rd class), the result of two toplist integration from two sources is:

f 11 f 12 f 13 f 21 f 22 f 23 f 31 f 32 f 33
The "degree of importance" of the integration result of two toplist:

coef(1,1) = 16 coef(1,2) = 8 coef(1,3) = 4 coef(2,1) = 8 coef(2,2) = 4 coef(2,3) = 2 coef(3,1) = 4 coef(3,2) = 2 coef(3,3) = 1
We call d(f ij ) is short way from f ij to bottom or the "near" of f ij and "change". By definition, if

f ij = bottom then d(f ij ) = 0, elseif "distance" from f ij to bottom is k then d(f ij )=2 k .
The "quantitive nochange" is defined by

 ij (coef(i,j) * d(f ij ))
When the "quantitive nochange" is greater then the possible change is smaller.

3 rd step: change decision basing on the preference order.

As an example to conclude the change: with the toplist = (1 st class, 2 nd class,

3 rd class), d(f ij ) OE{0, 2, 4, 8} (d(f ij ) = 0 if f ij = bottom, d(f ij ) = 2 if f ij is a successor of bottom, …). If the "nochange" is f 11 = (1 st of LCMGB ƒ 1 st of LCM2k) f 12 = (1 st of LCMGB ƒ 2 nd of LCM2k) f 13 = (1 st of LCMGB ƒ 3 rd of LCM2k) f 21 = (2 nd of LCMGB ƒ 1 st of LCM2k) f 22 = (2 nd of LCMGB ƒ 2 nd of LCM2k) f 23 = (2 nd of LCMGB ƒ 3 rd of LCM2k) f 24 = (2 nd of LCMGB ƒ 4 th of LCM2k) …
concluded if the major classes of two toplist are a same node in information lattice, then the thresholds for change decision are:

Nochange if  ij (coef(i,j) * d(f ij )) >= 512 Indecision if  ij (coef(i,j) * d(f ij )) >= 256 Change if  ij (coef(i,j) * d(f ij )) < 256

Results

Figure 3 and Figure 4 display the same midland zone: Figure 3 shows the map of majority class taken from LCMGB; Figure 4 is the map of Broad Habitat of LCM2k, colored according to the LCM2k display class description. The parcels color white lack information of land cover classes.

Figure 5 displays the change when the integration takes as input the major class of LCMGB and Broad Habitat of LCM2k. The constraint on quality for query of integration is (completeness >=50%) and (consistence = first). This constraint is "strong", for this reason there many parcels detected change. There are 40.22% nochange, 2.09% indecision, 38.23% change, 19.46% white.

[legend: no change= green, change= red, indecision= yellow, white= insufficient information for decision]

Figure 6 displays the result of integration query, which takes as input the "toplist" of LCMGB and "toplist" of LCM2k. The constraint on quality for query of integration is (completeness ≥ 50%) and (consistence = {first, second, third}). There are 40.22% nochange, 22.52% nochange with warning, 16.08 indecision, 1.72% change, 19.46% white.

[legend: no change= green, indecision= yellow, indecision "near change" = orange, change = red, white= insufficient information for decision]

Conclusion and future works

We have presented a solution to conclude about of land cover change. This solution takes into account constraints on quality information related to the completeness and consistency degree of classification of each parcel and to internal conceptual consistency. Then it integrates the two land cover class hierarchies under a common information lattice and proposes a way to identify the consensus of land cover classes at two dates. This consensus is relevant for determining the mismatch of land cover classes, and is used to conclude about the level of land cover classes, and is used to conclude about the level of change. The constraint on quality is intended to limit the computation to parcels which present enough information for making a decision of change. Experimental results have been performed on real-scale data and show some interesting properties, reducing the overestimation of change which is frequently computed with classical statistical methods.

We have proposed a common ontology for LCMGB and LCM2k on a zone study. This ontology is determined combining the expert opinion and the real information in the datasets. Consequently the common ontology of a zone is not suitable another zone or the all case. So it is necessary to thoroughly examine the ontology heterogeneity.

Fig. 1 .

 1 Fig. 1. Information lattice of common ontology of LCMGB and LCM2k

  step: build the preference order to conclude about change

Fig 4 .Fig 3 .Fig. 6 .Fig. 5 .

 4365 Fig 4. Broad Habitat display of LCM2k

Table 1 .

 1 Example of an expert look-up table

	Classes #2 Classes #1	l 1	l 2

Table 2 .

 2 the means of abbreviation in Figure1

	W : water	Ds : scrub	Gc : calcareous(managed)
	Ab : barley	C : conifers	Grc: calcareous(rough)
	Am : maize	Cf : felled	Ga : acid
	Ao : oats	Cn : new plantation	Gra : acid (rough)
	Aw : wheat	H : dense	Gaj : acid with Juncus
	Acs : cereals	Hg : gorge	Gam : acid Nardus
	Aba : arable bare ground	Hga : open	Gbr : bracken
	Ac : carrots	Gi : intensive	Id : despoiled
	Af : field beans	Gih : grass	Ib : semi-natural
	Ah : horticulture	Gim : grazing marsh	Us : suburban/ rural dev.
	D : deciduous	Gis : grass setaside	U : urban residential
	Dm : mixed	Grn : rough grass	Ui : urban industrial
	Db : open birch	Gn : grass (neutral)
	13.1 : water	10.1 : dense dwarf shrub	8.1 : acid grass
	4.1 : arable cereal	10.2 : open dwarf shrub	9.1 : Bracken
	4.2 : arable horticultural	5.1 : improved grassland	16.1 : inland rock
	1.1 : broad-leaved wood	6.1 : Neutral	17.1 : suburban
	2.1 : Coniferous wood	7.1 : Calcareous	17.2 : continuous urban
	5 : pasture/grassland	C7 : pasture/meadow/	C17 : upland bog
	6 : semi-natural	amenity grass	C18 : tilled land
	7 : neutral and calcareous	C8 : rough / marsh Grass	C20 : suburban/rural dev.
	8 : acid grass/bracken	C12 : bracken	C21 : urban development
	C1 : water	C14 : scrub / orchard	C23 : inland bare ground
	C2 : sea/estuary	C15 : deciduous woodland	C24 : lowland bog
	C6 : mown / grazed turf	C16 : conifer	C25 : open shrub heath

Table 3 .

 3 an example of land cover information in LCMGB dataset and LCM2k dataset

			LCMGB (1990)
	P# PerList
	1	26% suburban	22% pasture/meadow/ amenity grass	11% tilled land	11% inland bare ground
	2	64% inland bare ground	22% tilled land	11% pasture/meadow/ amenity grass	3% suburban
	3	37% tilled land	30% neutral and calcareous	4% suburban	2% deciduous woodland
	4	…	…	…
			LCM2k (2000)
	P# PerPixList (level 1 in information lattice)			BH
	1	30%maize, 25%suburban, 11%barley (type a), 11%arable bare ground, 4%barley (type b)	17.1
	2	55%carrots, 22%suburban, 7%intensive, 3%field beans		4.2
	3	48%grass (neutral), 30%deciduous (type a) , 19%deciduous (type b), 3%mixed		2.1
	4		…

Table 2

 2 , subclasses maize, barley (type a), barley (type b) are regrouped into class 4.1(arable cereal) with percentage 45, suburban is regrouped into class 17.1 with percentage 25, and arable bare ground is regrouped into class 4.2 (arable horticultural) with percentage 11 (see Figure1). The result list is sorted in descending order of percentages, called "TopList": 2.1, 45: 17.1, 25: 4.2, 11. We say that an estimated broad habitat value is consistent if it is the first value of the TopList. Hence, for the first line of Table2, BH is not consistent with PerPixList.

Table 4 .

 4 Completeness and consistency of LCMGB information in Table3

	P#		TopList			Completeness Consistency
	1	26%C20 22%C7 11%C18 11%C23	0.7	1 st
	2	64%C23 22%C18 11%C7	3%C20	1	1 st
	3	37%C18 30%C7	4%C20	2%C15	0.73	1 st
	4	…	…	…

Table 5 .

 5 Completeness and consistency of LCM2k information in Table3The problem of detecting change between thematic (land cover) maps is described by[START_REF] Fuller | The characterization and measurement of land cover change through remote sensing: problem in operational application?. in int[END_REF] with reference to the accuracy of LCMGB and LCM2k. With the assumptions of random error distribution, ignoring different types of thematic errors and change, they show the underlying problems of change detection that exist with respect to map accuracies stating that to detect a change of 17% (the likely rate of change cited by[START_REF] Fuller | The characterization and measurement of land cover change through remote sensing: problem in operational application?. in int[END_REF] with a 75% reliability both maps would have to be 97% accurate. In reality LCMGB and LCM2k are between 70% and 80% accurate.Most improvements proposed for theses approaches concern the way the "surfaces" are computed, paying attention to the "internal data quality", not to the external quality. At the European scale, a lot of studies have been done for the CORINE Land-Cover program (see (IES)), whose LCMGB is the British subset. The overall results are used as very broad indicators only, and in general they are reputed "overestimated".[START_REF] Fuller | The characterization and measurement of land cover change through remote sensing: problem in operational application?. in int[END_REF] indicate that a possible way forward for detecting land cover change between, is to utilize the vector structure of LCM2k to interrogate the LCMGB raster data. This provides local descriptions of LCMGB distributions, and allows change to be identified on a per-parcel basis. A complementary description of LCM2k parcel heterogeneity is provided by one of the LCM2k metadata attribute PerPixList.Comber et al (2003a; 2003b;[START_REF] Comber | Identifying land cover change using a semantic statistical approach: first results[END_REF] have developed and applied a methodology that compares two parcel characterizations based on PerPixList attribution and the distribution of LCMGB classes, in order to identify locales of change.

	P#		TopList		BH	Completeness Consistency
	1	45%2.1	25%17.1 11%4.2	17.1	0.81	2 nd
	2	58%4.2	22%17.1	7%5.1	4.2	0.87	1 st
	3	52%1.1	48%2.1		2.1	1	2 nd
	4	…	…	…
	4 Land cover change
	4.1 Existing methods

http://www.ceh.ac.uk/

Acknowledgements

This work is supported by the European Community under contract IST-1999-14189: « REVIGIS » project of the « Future and Emerging Technologies » program of IST, in the 5 th Framework Program. Data are provided by courtesy of CEH 1 , through an agreement with Department of Geography, University of Leicester.