Daniel Sanders
email: daniel.g.sanders@boeing.com

Paul Edwards

Glenn Grant

Mamidala Ramulu

Anthony Reynolds

SUPERPLASTICALLY FORMED FRICTION STIR WELDED TAILORED ALUMINUM AND TITANIUM BLANKS FOR AEROSPACE APPLICATIONS

Keywords: Superplastic Forming, SPF, Friction Stir Welding, FSW, titanium, 6Al-4V, aluminium, 5083, tailored blank, nacelle, aerospace, laminar flow, weight reduction, fuel savings, monolithic assembly

The purpose of this study was to develop a specialized Friction Stir Welding process for superplastic grade aluminum alloy 5083-SP and titanium alloy 6Al-4V, in thickness of 1.5 to 4 mm, such that the butt welded nugget would have equal superplastic forming (SPF) characteristics as the parent sheet material The concept of using tailored blanks for the SPF process is proposed which will allow the joining of multiple pieces to fabricate much larger monolithic components than has been possible in the past. Another benefit of using tailored blanks for SPF applications was found to be a more closely matched blank shape relative to the plan size of the SPF forming die. However, shape of the tailored blanks is critical in SPF of a component. An example of this might be the case where a polygon shaped blank might work in order to reduce the amount of material used, but a rectangular blank is currently used because a tailor made blank with superplastic joints was not found to be technologically feasible. Upon development of a suitable FSW process for each material, the technology was applied to fabricate full scale test components representing a generic jet engine nacelle Lipskin.

INTRODUCTION

The increasing cost of Jet A-1 fuel (Fig. 1) in recent years has compelled Boeing to make changes in the materials and design used for new airplanes, such as the 787 Dreamliner. Carbon Fibber Reinforced Composites (CFRC) are quickly becoming the materials of choice for large passenger jetliner airplane structures such as the fuselage, empennage and wings. While the weight, strength, fatigue and passenger comfort advantages with these materials have allowed for improvements in component design and aircraft performance, the largest pitfall with CFRC has been found to be that it is much less compatible with traditional aerospace aluminium alloys for galvanic corrosion, thermal expansion and electro-magnetic effects (EME) issues. Titanium alloys have properties far more advantages in terms of their compatibility with CFRC and this has led to titanium becoming the material of choice for many applications. SPF-and hot forming of titanium have emerged as two of the most significant processes for the fabrication of large monolithic sheet metal parts that have historically been fabricated using aluminium built up assemblies [START_REF] Sanders | Superplastic Forming of Friction Stir Welds in Titanium Alloy 6Al-4V: Preliminary Results[END_REF][START_REF] Sanders | Characterization of Superplastically Formed Friction Stir Weld in Titanium 6Al-4V: Preliminary Results[END_REF]. Aside from being compatible with CFRC materials, the advantages with using titanium SPF parts include:

• The ability to form complex curvatures and compound contours.

•

No spring back from forming and little or no residual stresses.

•

The need for only a single machined die surface vs. matching halves.

•

Fewer tools required with little or no assembly.

•

Fewer holes to drill and reduces the use of fasteners.

•

Outside mould lines can be very smooth to reduce aerodynamic drag (achieve laminar flow).

•

Integral stiffening beads can be used to avoid separate fastened stiffeners.

•

With tailored blanks, considerable scrap can be avoided, decreasing the buy-tofly ratio.

There are considerations that must be taken into account when using SPF:

• Thinning of the sheet during forming must be carefully understood.

•

Close coordination is required between the engineering and tool designers.

•

Not all metal alloys exhibit superplasticity.

The 737-300 was the first Boeing airplane to convert a riveted aluminium built-up structure used as an Access Door for the Auxiliary Power Unit (APU) into a much simpler assembly that utilizes a single SPF 7475 aluminium formed frame (Fig. 2) [START_REF] Sanders | The Current State-of-the-Art and the Future in Airframe Manufacturing Using Superplastic Forming Technologies[END_REF]. The SPF design uses integral formed "hat" sections in a circuitous pattern to replace hydropress formed detail parts that are subsequently drilled and riveted together. The SPF version eliminated 25 detail parts and 137 holes/rivets. A weight savings of 9% and a cost savings of 75% were achieved.

Because the SPF details are built to higher precision tolerances, the quality problems experienced in building the built-up assembly were completely eliminated. In addition to the more efficient design, the fabrication was simplified through the use of laser trimming and automated fastening equipment. Over 2,000 of these doors are currently in service today and the same design has been used on subsequent variants of the 737 airplane family. Two Service Doors on the 777 are also in production. While implementation of the 737 APU Access Door was a tremendous achievement, it quickly became clear that far greater efficiencies and cost savings could be realized by focusing on larger assemblies. Over the past 20 years, the use of SPF at Boeing has gradually transitioned to ever increasing sizes, with many of the parts that are currently in production being formed using the largest (widest and/or longest) sheets of titanium that are available from the mills.

By the year 2000, the limitation on the size of sheet titanium had become a critical barrier to overcome in order to enable the fabrication of much larger monolithic parts, such as a single piece jet engine Inlet for a Nacelle. Therefore, studies were begun by conducting University-Industry collaborative research to find advanced methods of fabricating tailored blanks for SPF using many different joining methods. After substantial testing of many fusion welding techniques failed to produce a joint that could withstand the amount of stretching encountered in typical SPF parts without tearing, a study was begun to develop the titanium Friction Stir Welding (FSW) process and to find a way to make an FSW weld bead with highly superplastic properties [START_REF] Sanders | Superplastic Forming of Friction Stir Welded Ti 6-4 Sheet[END_REF]. At this time, FSW had been invented and developed by The Welding Institute (TWI) for aluminium alloys only a few years earlier [START_REF] Thomas | Great Britain Patent[END_REF] and no papers had been published on combining FSW with SPF for titanium.

The development of the FSW process for titanium 6Al-4V in standard and fine grain material types yielded an excellent manufacturing process that could produce tailored blanks with joints of equal superplasticity to the parent sheet, which broke the size barrier for producing very large parts. However, the cost of developing the forming and post-forming machines, processes, tooling, material handling equipment and various other technologies using titanium as the experimental material became prohibitively expensive. In order to reduce the cost of development, a process for FSW and SPF of the much less expensive 5083-SP was required to substitute test pieces made from aluminium for the expensive titanium.

DEVELOPMENT OF FSW-SPF FOR 5083-SP

The earlier development work that was reported [START_REF] Sanders | Superplastic Forming of Friction Stir Welded Ti 6-4 Sheet[END_REF], had identified some of the key parameters affecting the superplasticity of titanium FSW joints were the spindle speed (rpm), the feed rate (mm/sec) and the pin tool geometry. . For the 5083-SP testing a commercially available pin tool was chosen that had been designed for general use in FSW of aluminium sheet metal. The pin tool had a shoulder diameter of approximately 20 mm. For the initial FSW trials, the process parameters were chosen as a "best guess" from FSW data developed for similar aluminium alloys of similar thickness.

SPF experimental parameters provided by Pacific Northwest National Laboratories were used during all tests. These parameters had been developed for fabricating fusion welded tailored SPF blanks for the automotive industry during an earlier investigation [START_REF] Davies | Mechanical Properties of Aluminium Tailor Welded Blanks at Superplastic Temperatures[END_REF]. The forming temperature used for the superplasticity tests was 530 °C +/-25 °C and the target strain rate was 4 x 10 -4 s -1 . The range of SPF elongation measured independently in the parent metal and the FSW joint was found to be in a range of 20-80 % when the tests were stopped, with a target of 50 to 70% elongation over the entire length of the specimens.

In order to characterize the superplastic behaviour of FSW joints in 5083-SP aluminium, there are two values that were quantified after FSW-SPF Specimens tensile testing [START_REF] Sanders | Superplastic Forming of Friction Stir Welded Ti 6-4 Sheet[END_REF][START_REF] Davies | Mechanical Properties of Aluminium Tailor Welded Blanks at Superplastic Temperatures[END_REF]. These values were the elongation in the weld (e W ), and the elongation in the parent material (e P ). For the forming evaluation, the elongation ratio (P/W Ratio) is calculated for each test coupon and this is used to gage the relative superplastic strain to make a comparison between the parent metal sheet and the FSW joint. Equation (1) defines the P/W ratio, where eP is the superplastic elongation of the parent material and eW is the superplastic elongation of FSW. A P/W Ratio of 1.00 would indicate equivalent superplastic strain and this was the target for this investigation.

P/W Ratio = (e P )/(e W )

Testing of the titanium material had shown that welds made with "hotter" FSW parameters (welds made with faster spindle speeds and feed rates) showed less superplastic behaviour than welds made with comparatively "colder" FSW parameters (slower spindle rpm and feed rate). When adjusting the FSW process to develop ideal superplastic properties, it is helpful to calculate the Pseudo Heat Ratio as an indication of the relative "hot" or "cool" temperatures developed during the FSW process across the weld joint. The Pseudo Heat Ratio (PHR) is defined in equation ( 2), where N is the spindle speed (rpm) and fr is the feed rate (mm/sec). The units for the PHR value are meaningless, as it is meant to be simply a tool or rough gage for understanding the amount of heat developed due to the relative amount of friction developed as the pin tool interacts with the material and it is not an exact calculation. The calculated values are often manipulated proportionately to a scale that fits nicely on a data plot. Note that small changes in the spindle speed were found to have a more profound influence on the thermal energy developed during FSW than was changing the feed rate.

Pseudo Heat Ratio = (N) 2 /( fr)

(2)

One of the values of the PHR is that, once an appropriate value for N has been determined at a specific fr, it is a simple task to calculate a series of alternative spindle speeds and feeds that would result in approximately the same superplastic performance. However, it has been found through empirical testing that the alternative values chosen must be within about 200 rpm as the original N and about 100 mm/s for the fr to achieve similar SPF results across the FSW for 5083 aluminium.

Butt welded FSW test panels were fabricated using a variety of mixed parameters ranging from 275 to 350 rpm for the spindle speed and 100-150 mm/sec for the feed rate. Test coupons (Fig. 3) were cut from the FSW test panels and tension tested using a tensile testing machine equipped with a furnace and strain control to determine the SPF performance. The P/W ratio and Pseudo Heat Ratio were calculated after forming by measuring the amount of actual strain in the parent metal and weld lengths of the stretched coupons. The data was charted in order to observe performance and determine the optimum forming parameters.

Figure 3. Butt welded FSW panels were cut into SPF tensile coupons and tested for superplastic performance at the Pacific Northwest National Laboratories.

RESULTS

The superplasticity P/W Ratios from several hot tension tests of FSW coupons with varying spindle speeds and a constant feed rate of 150 mm/s are plotted in Figure 4. Three separate test coupons were taken from different locations along the length of the FSW, starting from the point at which each of the butt welds were begun, to observe the effects in thermal changes across the weld joint as the pin tool heated up during its traverse.

From this data, it is seen that the desired value of the P/W Ratio = 1 would likely be achieved with a feed rate of 150 mm/s at approximately 420 rpm spindle speed. It can also be observed that increasing the spindle speed causes the FSW to be less superplastic than does decreasing it, confirming that the performance of the 5083-SP FSW process behaves in a similar fashion to that of the 6Al-4V titanium FSW process. There is also a trend for the hotter welds, e.g.

the FSW made with N = 600 and fr = 150 m/s, to get much hotter as the pin progresses from its start to the end of the butt weld, which is likely due to the increasing temperature of the pin tool, which in turn generates more heat within the body of the FSW weld.

In comparison to the superplastic performance of titanium 6Al-4V to 5083-SP, we can see that the aluminium material is much less responsive to changes in the N and fr in the "colder" weld region (350 to 450 rpm at 150 mm/s) than is the titanium FSW process. Relatively large adjustments to the FSW process seemed to have little effect on the P/W ratio for the 5083 aluminium. Whereas changes on the order of N ~ +/-10 rpm or fr ~ +/-15 mm/s to the stable FSW-SPF parameters around the region where P/W = 1.0 will result in significant improvement or degradation in the superplasticity of the FSW titanium. The next step for developing a suitable range of FSW process parameters with induced superplasticity in 5083-SP was to calculate the PHR for each of the superplastic formed tensile test coupons and graph it versus the P/W. This data is presented in Figure 5. A best fit curve is then calculated and plotted from the data that represents the trend of the data. From this curve, the PHR can be found at the point at which the P/W ratio is equal to unity, which are presumably the FSW parameters for perfect superplastic performance (the parent sheet stretches at the same strain rate and flow stress as does the FSW nugget). Once the PHR is found, it becomes a simple mathematical exercise to determine values for N and fr that are different than those tested, but would likely result in similar superplastic characteristics. Using the data generated during this study, four tailor cut segments of 5083-SP sheet metal were welded together to form a 12 m diameter shape, which resembled a very large donut. The blank was then superplastic formed into an aerodynamic shape emulating the leading edge of a very large jet engine Nacelle Inlet (Figure 6). Several test parts were fabricated in this fashion to be used in developing the manufacturing and post processing requirements for a similar part that was also built using titanium alloy 6Al-4V. A considerable cost savings was realized by using the relatively inexpensive aluminium material in place of titanium. Observations of the 5083-SP FSW joints after the part was formed showed that the thickness of the weld nugget was very close to being the same as the parent sheet.

Figure 1 .

 1 Figure 1. The price of crude oil and Jet A-1 fuel (U.S. dollars) vs. time. Source: U.S. Dept. of Commerce, July, 2008.

Figure 2 .

 2 Figure 2. The built-up aluminium APU Access Door is shown on the left and the SPF monolithic design is shown on the right.

Figure 4 .

 4 Figure 4. The P/W Ratio from superplastic formed tensile tests are plotted with FSW parameters are made from varying feed rates and rpms.

Figure 6 .

 6 Figure 6. A fully SPF formed 5083-SP jet engine leading edge Nacelle Inlet made by FSW butt welding of four separate segmented blanks prior to forming.

  Figure5. The P/W Ratio from superplastic formed tensile tests are plotted vs. the Pseudo Heat Ratio. From this plot, it is possible to predict SPF performance of FSWs made using slightly different FSW process variables.

				RPM^2 / IPM vs. P/W ratio -Prediction
				AL 5083SP 1.5 mm Thickness
		7.00
		6.00
		5.00
	P/W Ratio	3.00 4.00		y = 0.0032x 2 -0.123x + 1.8535 R 2 = 0.958
		2.00	Looking for: RPM^2/(Feed Rate) = 30		This is approx.: 438 RPM / 150 mm/s 473 RPM / 175 mm/s
						506 RPM / 200 mm/s
		1.00				566 RPM / 250 mm/s
		0.00
		10	20	30	40	50	60	70
				Pseudo Heat Index (N )^2/(f r) -No Scale, Comparison Use Only

SUMMARY AND CONCLUSIONS

During this study, the FSW process parameters were developed to allow the fabrication of very large monolithic structures, such as what would be required for a single piece 5083-SP aluminium Lipskin for a high bypass ratio (large diameter) jet engine. The results of the test program have shown that friction stir welding is a viable option for the fabrication of tailored blanks for use in the manufacture of SPF commercial hardware.


Gianluca Crippa
email: gianluca.crippa@unipr.it

É Chlo

AND Aldo Jimenez
email: chloe.jimenez@univ-brest.fr

Pratelli
email: aldo.pratelli@unipv.it

OPTIMUM AND EQUILIBRIUM IN A TRANSPORT PROBLEM WITH QUEUE PENALIZATION EFFECT

Consider a distribution of citizens in an urban area in which some services (supermarkets, post offices. . . ) are present. Each citizen, in order to use a service, spends an amount of time which is due both to the travel time to the service and to the queue time waiting in the service. The choice of the service to be used is made by every citizen in order to be served more quickly. Two types of problems can be considered: a global optimization of the total time spent by the citizens of the whole city (we define a global optimum and we study it with techniques from optimal mass transportation) and an individual optimization, in which each citizen chooses the service trying to minimize just his own time expense (we define the concept of equilibrium and we study it with techniques from game theory). In this framework we are also able to exhibit two time-dependent strategies (based on the notions of prudence and memory respectively) which converge to the equilibrium.

Introduction

In this paper we study an optimization problem coming from the modeling of the behaviour of citizens who every day need to use some services (supermarkets, post offices. . . ) present in a city. We consider a bounded set Ω ⊂ R d which is the geographic reference for the city and a nonnegative function f with unit integral representing the population density. We fix k points x 1 , x 2 , . . . , x k at which the services are located. If every service was able to answer immediately to the demand of each customer, obviously every person would choose the one closest to his home. Namely, being p ≥ 1 a fixed number so that the time spent to cover a distance ℓ is given by ℓ p , then a citizen living at x would choose the service located at x i if and only if

|x -x i | p = min j=1,...,k |x -x j | p .
However, in real world, if a service is crowded because a certain amount of citizens have chosen it, the satisfaction of the demand of the customer is not immediate, and some time has to be spent waiting for it. This time spent in the queue surely depends on the amount of people waiting at the service, but also on the characteristics of the service (for instance, its dimension or the ability of the employees). This can be modeled using k functions h 1 , h 2 , . . . , h k which express the time to be waited in dependence of the amount of people in the queue. If the amount of citizens choosing the service x j is c j , for j = 1, . . . , k, then a citizen living at x and going to the service x i needs to use a total amount of time expressed by the quantity |xx i | p + h i (c i ) in order to reach the service x i and to have his request fulfilled. In particular, the better service for the customer is not necessarily the closest one. It could be convenient for him to go a bit further away in order to be served in a bigger service, in which the queue is faster.

It is surely apparent from the above discussion that, in this modeling, the decision of each citizen depends on the choices of all the other citizens. Each customer chooses the best service according to the corresponding queue, but the queue itself depends on the choices of all the other customers. A possible attempt to tackle this question is to look for a global minimum. Let us denote by A j the subset of Ω consisting of the areas in which the citizens using the service x j live. The total cost, in term of time spent to be served, needed by the citizens of the whole city is expressed by

k i=1 A i |x -x i | p + h i A i f (x) dx f (x) dx .
If we agree that the choice of each citizen is done in order to minimize this total cost (for instance, if the major of the city has the right to force the choices of the customers, in order to make the global cost as small as possible), we are led to consider the following minimization problem: inf

(A i ) i=1,...,k partition of Ω k i=1 A i |x -x i | p + h i A i f (x) dx f (x) dx .
(1.1)

This type of minimization problem fits very well in the theory of optimal mass transportation. This theory goes back to Monge [START_REF] Monge | Memoire sur la Theorie des Déblais et des Remblais[END_REF], who considered the problem of moving a pile of sand into a hole of the same volume, minimizing the transportation cost. We briefly refer on the Monge problem, its relaxation due to Kantorovich ([21] and [START_REF] Kantorovich | On a problem of Monge[END_REF]) and the recent progresses on it in Section 2.2. The study of the minimization problem (1.1) is done in Section 3. We define the concept of optimum, which is a partition (A i ) i=1,...,k solving (1.1), we prove results of existence and uniqueness of the optimum (under suitable assumptions on the functions h i ) and we give some characterizations of it. However, this kind of solution of the problem is not very natural, from an economic point of view. Indeed, as pointed out in Example 4.7, it could happen that for some citizens the choice of the service forced by the need of producing an optimum for (1.1) is too expensive. It is more realistic to consider as a good solution of the problem a partition of Ω in which each citizen is "satisfied" with his own choice. By this we mean the following: the citizen looks at the behaviour of all the other citizens, and regarding it as fixed he decides whether his decision has been clever or not. In particular, a citizen living at x is satisfied with his choice of going to the service located at x i if and only if

|x -x i | p + h i (c i ) = min j=1,...,k {|x -x j | p + h j (c j )} , (1.2)
where the numbers c j , as before, represent the amount of customers choosing the service x j , for j = 1, . . . , k, but now these quantities are seen as fixed by the citizen who evaluates the correctness of his decision. This is radically different from the previous minimization problem, as we explicitly remark in Section 4.4. The condition expressed in (1.2) paves the way for a connection with game theory (for which good references are [START_REF] Friedman | Differential games[END_REF] and [START_REF] Aubin | Optima and equilibria. An introduction to nonlinear analysis[END_REF]): in Section 4 we define an equilibrium for our problem as a partition in which every customer is satisfied with his choice, in the sense specified above. In classical game theory this corresponds to the socalled Nash equilibrium. We are able to prove, under suitable assumptions on the functions h i , existence and uniqueness of an equilibrium, and we also comment on the main differences between equilibrium and optimum.

In Section 5 we finally consider a dynamical evolution of the problem, looking for convergence to the equilibrium. The general question is the following. Assume that the citizens have some strategy to decide, day by day, the most convenient service, using data which come from the previous days. At each day, they decide where to go, considering the lengths of the queues that have been observed in the previous days. Does this iterative scheme converge to the equilibrium? In Example 5.3 we show that this is not the case, if the strategy of the customers is too na ïve. If they just choose every day to minimize the right hand side of (1.2), in which the time spent on the queues in the various services is simply the one observed the day before, then we could obtain some oscillatory phenomena, with no convergence. However, we propose two different strategies, quite natural at a social level, which lead to convergence to the equilibrium.

The first one (see Section 5.2) is based on the concept of prudence (which, in some sense, could also be viewed as laziness or resistance to a change of habits). The decision that every citizen makes is again based on the information on the queues of the previous day, but it is now seen as a stochastic variable (in the language of optimal mass transportation this corresponds to the notion of transport plan, see again Section 2.2). It is "too risky" for the customer to change immediately the preferred service, thus we assume that he is only going to change his opinion, in the sense that he will be more tempted by the most convenient service, but he will not immediately "fully choose" it. The choice between two services of each customer is modeled by a function with values between 0 and 1: value 0 means that the choice is completely in favour of the first service, while value 1 means that the choice is completely in favour of the second service. Values between 0 and 1 mean that the customer chooses a mixed strategy (this is also common in game theory). This can also be interpreted in statistical terms: if at each point of the city there is a condominium instead of a single citizen, then each person will choose the service in such a way that the statistical distribution of the choices follows the stochastic variable defined above. Assuming that the citizens have "enough prudence", we are able to show that the iteration of the stochastic choices converges to a deterministic decision, which is an equilibrium for our problem.

The second strategy (see Section 5.3) relies on the notion of memory. We go back to a deterministic strategy, but we assume that each customer bases his decision not only on the informations coming from the previous day, but also remembering the queues that have been seen in a certain amount of days in the past. Then the choice for the new day is based on an average of all these informations. If the citizens have "enough memory", in the sense that they consider in their choice a sufficiently big amount of days, we are able to show that also this iteration converges to an equilibrium for the problem.

We close this introduction by relating our problem to some other optimization problems studied in the previous literature. The idea for our model came from some results relative to the so-called location problem, see [START_REF] Bouchitté | Asymptotique d'un problème de positionnement optimal[END_REF], [START_REF] Jimenez | Optimisation de problèmes de transport[END_REF] and [START_REF] Brancolini | Long-term planning versus short-term planning in the asymptotical location problem[END_REF]. In this problem, we are given a distribution of citizens f in a city Ω, but the location of the services is no more fixed. The question is to optimize the location of the services, in such a way that the transportation cost of the citizens onto the services is minimized. We observe that no queues are considered in this model. Two different approaches to this problem are possible. In the long term planning all the services are built at the same time, minimizing the average distance the people have to cover to reach the nearest service. In the short term planning, it is assumed that services are built one by one, minimizing the average distance step by step, taking into account at each stage the location of all the services opened at previous steps. Other related works, regarding the modeling of urban areas and the structure of cities, are [START_REF] Buttazzo | Optimal urban networks via mass transportation[END_REF], [START_REF] Buttazzo | A model for the optimal planning of an urban area[END_REF], [START_REF] Carlier | The structure of cities[END_REF], [START_REF] Carlier | Equilibrium structure of a bidimensional asymmetric city[END_REF], [START_REF] Carlier | A variational model for urban planning with traffic congestion[END_REF] and [START_REF] Lucas | On the internal structure of cities[END_REF]. this work. Moreover, they also thank the Scuola Normale Superiore di Pisa and the Mathematics Department of the University of Pavia for the hospitality during the preparation of this paper.

Notation and preliminary results on optimal mass transportation

In this section we introduce the general setup of the paper and the main notation, we review some basic facts about optimal mass transportation (for which the reader can consult [START_REF] Ambrosio | Lecture Notes on Optimal Transport Problems. Mathematical aspects of evolving interfaces[END_REF] or [START_REF] Villani | Topics in Optimal transportation[END_REF]) and we establish some preliminary results which will be useful in the sequel.

2.1. Main notation of the paper. We fix a bounded Borel set Ω ⊂ R d and we denote by L d the d-dimensional Lebesgue measure in R d . We consider k points x 1 , x 2 , . . . , x k belonging to Ω, where k is a strictly positive integer; these points represent the location of the services in the city. The density of the citizens is given by an absolutely continuous probability measure µ = f L d Ω, where f : Ω → R is a nonnegative function with unit integral. The measure µ defined in this way will be typically the reference measure in Ω, and we shall also write f -a.e. and f -negligible as a shortening of the more precise notation µ-a.e. and µ-negligible. For i = 1, . . . , k we consider the functions h i : [0, 1] → [0, +∞[ which encode the amount of time to be waited in dependence of the amount of people using the service. With this we mean that, if the service located at x i is chosen by an amount c i of citizens, then the time that will be spent in the queue by each customer is h i (c i ). Notice that in this modeling we can also include some penalizations for the particular features of the various services, choosing the queue functions in such a way that h i (0) > 0: for instance, higher prices or lower quality of the products. We do not specify a priori any condition on the functions h i , but we will rather clarify the assumptions needed in each particular result. For every Borel set A ⊂ Ω we consider the indicatrix function 1 A defined by

1 A (x) = 1 if x ∈ A 0 if x ∈ A.
The set of probability measures on Ω and Ω × Ω are denoted by P(Ω) and P(Ω × Ω) respectively. When γ ∈ P(Ω) is given, we denote by L 1 γ (Ω) the vector space consisting of the Borel functions which are γ-integrable. A partition of Ω is a finite or countable family (A i ) i∈N of pairwise disjoint (up to f -negligible sets) Borel sets A i ⊂ Ω such that ∪ i∈N A i has full measure in Ω.

2.2.

Optimal mass transportation. In 1781 Monge [START_REF] Monge | Memoire sur la Theorie des Déblais et des Remblais[END_REF] raised the problem of transporting a given distribution of mass (a pile of sand, for instance) into another one (a hole, for instance), in such a way that the total work done is minimal. In modern terms the problem can be stated as follows. Given two measures µ, ν ∈ P(Ω) and p ≥ 1 we consider the minimization problem

M p (µ, ν) = inf Ω |x -T (x)| p dµ(x) 1/p : T : Ω → Ω Borel and such that T # µ = ν .
Here we denote by T # µ ∈ P(Ω) the push-forward of the measure µ, defined by

(T # µ) (A) = µ T -1 (A)
for every Borel set A ⊂ Ω.

Any map T which is admissible in the above problem is called a transport map from µ to ν. It is extremely difficult to attack the Monge problem, mainly due to the fact that it is highly nonlinear. This is why the following relaxed formulation, due to Kantorovich ([21] and [START_REF] Kantorovich | On a problem of Monge[END_REF]), is of great importance. We denote by Π(µ, ν) ⊂ P(Ω × Ω) the set of the probability measures γ in Ω × Ω with marginals µ and ν, i.e. such that (π 1 ) # γ = µ and (π 2 ) # γ = ν, where we denote by π 1 the projection on the first component and by π 2 the projection on the second component.

Every element of Π(µ, ν) is called a transport plan from µ to ν. We notice that Π(µ, ν) is always nonempty, since for instance µ ⊗ ν ∈ Π(µ, ν). The relaxed formulation of the Monge problem can be stated as follows:

W p (µ, ν) = inf Ω×Ω |x -y| p dγ(x, y) 1/p : γ ∈ Π(µ, ν) .
By considering γ = (id × T ) # µ for any given transport map T we see that the Kantorovich problem is indeed a relaxation of the Monge problem. It turns out that W p is a distance on P(Ω), which metrizes the weak convergence of measures (recall that we are assuming that Ω is bounded). This distance is called the Wasserstein distance of order p.

Existence and uniqueness results for the optimal mass transportation problem has been proved only very recently. We refer to [START_REF] Brenier | Polar factorization and monotone rearrangement of vector-valued functions[END_REF] and [START_REF] Knott | On the optimal mapping of distributions[END_REF] for the case p = 2, to [START_REF] Rüschendorf | Optimal solutions of multivariate coupling problems[END_REF] and [START_REF] Gangbo | The geometry of optimal transportation[END_REF] for the case p > 1 and to [START_REF] Caffarelli | Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs[END_REF], [START_REF] Evans | Differential equations methods for the Monge-Kantorovich mass transfer problem[END_REF] and [START_REF] Ambrosio | Existence and stability results in the L 1 theory of optimal transportation[END_REF] for the case p = 1. We summarize these results in the following theorem.

Theorem 2.1 (Existence and uniqueness of an optimal transport map). Let µ and ν be probability measures in Ω and fix p ≥ 1. We assume that µ is absolutely continuous with respect to the Lebesgue measure L d . Then M p (µ, ν) = W p (µ, ν) and there exists an optimal transport map from µ to ν, which is also unique f -a.e. if p > 1.

Remark 2.2. In the particular case when µ ≪ L d and ν = i∈N b i δ y i any transport map T is associated to a partition (B i ) i∈N of Ω in such a way that

T (x) = i∈N y i 1 B i (x) and µ(B i ) = b i .
Conversely, any partition (B i ) i∈N of Ω satisfying µ(B i ) = b i corresponds to a transport map of the form above.

In the situation of the above remark any transport plan can be written as

γ = i∈N (ψ i µ) ⊗ δ y i (2.1)
where the functions ψ i : Ω → R + are such that i∈N ψ i (x) = 1 for each x ∈ Ω and Ω ψ i dµ = b i . With this language γ corresponds to a transport map if and only if the functions ψ i have only the values 0 and 1. Another useful feature of Kantorovich's relaxation is the fact that this new problem admits a dual formulation.

Theorem 2.3 (Dual formulation). For µ, ν ∈ P(Ω) the following equality holds:

W p p (µ, ν) = sup Ω u dµ + Ω v dν : u ∈ L 1 µ (Ω) , v ∈ L 1 ν (Ω) and u(x) + v(y) ≤ |x -y| p for µ-a.e.
x and ν-a.e. y .

Moreover, there exists an optimal pair (u, v) for this dual formulation.

In the particular case when ν = i∈N b i δ y i is an atomic measure the dual formulation reads as:

W p p µ, i∈N b i δ y i = sup    Ω u dµ + i∈N b i v(y i ) : u ∈ L 1 µ (Ω) , v ∈ L 1 ν (Ω) and u(x) + v(y i ) ≤ |x -y i | p for µ-a.e. x and every i ∈ N    . (2.2)
2.3. A preliminary result on the shape of partitions. We present in this subsection a result of standard flavour relative to the shape of the sets in the partition determined by the optimal transport of a diffuse measure to an atomic measure.

Proposition 2.4. Let f : Ω → R be a nonnegative function such that µ = f L d Ω is a proba- bility measure, and let (y i ) i∈N be a sequence of points belonging to Ω.

(i) Let ν = i∈N b i δ y i and (B i ) i∈N be a partition of Ω such that the map T (x) = i∈N y i 1 B i (x) is an optimal transport map from µ to ν. Let moreover the pair (u, v) be any solution of the dual formulation (2.2). Then we have

u(x) = inf i∈N {|x -y i | p -v(y i )} = i∈N (|x -y i | p -v(y i )) 1 B i (x)
for f -a.e. x ∈ Ω.

(2.3)

(ii) Let (B i ) i∈N be a partition of Ω and set b i = B i f (x) dx, ν = i∈N b i δ y i and T (x) = i∈N y i 1 B i (x). Let moreover u ∈ L 1 µ (Ω) and v ∈ L 1 ν (Ω)
be two functions (if any) satisfying condition (2.3). Then we have that T is optimal for M p (µ, ν) and that the pair (u, v) is optimal for the dual formulation (2.2).

Remark 2.5. We easily see that condition (2.3) implies that for every i ∈ N the following equality, intended up to f -negligible sets, holds:

B i = {x ∈ Ω : |x -y i | p -v(y i ) < |x -y j | p -v(y j ) ∀j = i} .
(2.4)

This equality precisely describes the shape of the sets in the partition. For instance, in the case p = 1 the boundaries of the sets B i are hyperboloids and in the case p = 2 the cells B i are polytopes.

From the above discussion we easily deduce the following corollary, regarding the uniqueness of the optimal transport map from an absolutely continuous measure to an atomic measure, which will be useful in the sequel.

Corollary 2.6. Assume that µ ≪ L d and ν = i∈N b i δ y i are probability measures in Ω. Then the optimal transport map from µ to ν is unique f -a.e. even in the case p = 1.

Proof. The existence of an optimal transport map is ensured by Theorem 2.1. The point is to show that in this case we also have uniqueness. We fix an optimal couple (u, v) for the dual formulation of the Kantorovich problem (2.2) and we consider an optimal transport map T . Recalling that, from Remark 2.2, every transport map is associated to a partition of Ω, we find a partition (B i ) i∈N of Ω in such a way that T (x) = i∈N y i 1 B i (x). But recalling (2.4) we deduce that the sets (B i ) i∈N are uniquely determined (up to f -negligible sets) by v, thus we conclude that the optimal transport map T is unique.

We close this section proving Proposition 2.4.

Proof of Proposition 2.4. (i) Using Theorem 2.3 an the fact that the transport T and the pair (u, v) are optimal we deduce that (see Remark 2.2)

Ω i∈N 1 B i (x)|x -y i | p f (x) dx = W p p (f L d Ω, ν) = Ω u(x)f (x) dx + i∈N b i v(y i ) .
Since T is a transport map from µ to ν we obtain

Ω i∈N 1 B i (x)|x -y i | p f (x) dx = Ω i∈N 1 B i (x)(u(x) + v(y i ))f (x) dx .
Then, recalling that in the dual formulation (2.2) the pair (u, v) is subject the the constraint u(x) + v(y) ≤ |x -y| p for µ-a.e. x and ν-a.e. y, we get i∈N

1 B i (x)|x -y i | p = i∈N 1 B i (x)(u(x) + v(y i ))
for f -a.e. x ∈ Ω.

This in particular implies

u(x) = i∈N (|x -y i | p -v(y i ))1 B i (x) for f -a.e. x ∈ Ω. (2.5)
Using again the constraint of the dual formulation (2.2) we immediately deduce (2.3) from (2.5).

(ii) First of all we notice that T is a transport map from f L d Ω to ν = i∈N b i δ y i and that the pair (u, v) is admissible for the dual formulation (2.2). Moreover using condition (2.3) we obtain

Ω |x -T (x)| p f (x) dx = i∈N B i |x -y i | p f (x) dx = i∈N B i [v(y i ) + u(x)] f (x) dx = Ω v(x) dν(y) + Ω u(x)f (x) dx .
Recalling Theorem 2.3 we obtain the validity of (ii).

3. Existence, uniqueness and characterization of the optimum 3.1. Formulation of the problem and definition of the optimum. In this section we consider our problem from a global point of view. The unknown is a partition (A i ) i=1,...,k of Ω, where each A i represents the urban area where customers choosing the service located at x i live. The total amount of people living in A i is given by c i = A i f (x) dx. Every citizen living at x and using the service located at x i is going to spend, in order to be served, a time given by |x -

x i | p + h i (c i ) .
In this expression, |xx i | p is the transport time and h i (c i ) is the time spent waiting in the queue. Consequently, the total time spent by the whole population is given by

k i=1 A i |x -x i | p + h i (c i ) f (x) dx . (3.1)
We want to choose the partition (A i ) i=1,...,k of Ω in such a way that the quantity in (3.1) is as small as possible; thus we are led to the following minimization problem: inf

(A i ) i=1,...,k partition of Ω k i=1 A i |x -x i | p + h i A i f (x) dx f (x) dx . (3.2) Definition 3.1 (Optimum).
We say that a partition

(A i ) i=1,...,k of Ω is an optimum if it is a minimizer for (3.2).

Preliminary considerations.

In this subsection we prove two lemmas which will be used in the following. We denote by S the unit simplex in R k defined by

S = c = (c 1 , c 2 , . . . , c k ) ∈ R k : c i ≥ 0 , k i=1 c i = 1 .
Lemma 3.2. The following equality holds:

inf (3.2) = inf c∈S W p p f L d Ω, k i=1 c i δ x i + k i=1 h i (c i )c i .
Proof. By applying Theorem 2.1 we have

inf c∈S W p p f L d Ω, k i=1 c i δ x i + k i=1 h i (c i )c i = inf c∈S M p p f L d Ω, k i=1 c i δ x i + k i=1 h i (c i )c i (3.3) = inf c∈S Ω |x -T (x)| p f (x) dx + k i=1 h i (c i )c i : T transport map from f L d Ω to k i=1 c i δ x i .
But recalling Remark 2.2 we can deduce

inf (3.3) = inf c∈S (A i ) i=1,...,k partition of Ω k i=1 A i |x -x i | p f (x) dx + k i=1 h i (c i )c i : A i f (x) dx = c i = inf (3.2) ,
thus we obtain the thesis.

Lemma 3.3. The function F : S → R defined by

F (c 1 , . . . , c k ) = W p p f L d Ω, k i=1 c i δ x i is continuous and convex.
Proof. The continuity follows directly from the fact that the topology induced by the Wasserstein distance of order p is the weak convergence of measures, as observed in Section 2.2.

Let us now show the convexity. Let (c 1 , . . . , c k ) and (c ′ 1 , . . . , c ′ k ) be two elements of S and let t ∈ [0, 1]. Consider two optimal transport plans

γ ∈ Π f L d Ω, k i=1 c i δ x i and γ ′ ∈ Π f L d Ω, k i=1 c ′ i δ x i .
This implies that

tγ + (1 -t)γ ′ ∈ Π f L d Ω, k i=1 tc i + (1 -t)c ′ i δ x i ,
hence we deduce

F t(c 1 , . . . , c k ) + (1 -t)(c ′ 1 , . . . , c ′ k ) = W p p f L d Ω, k i=1 tc i + (1 -t)c ′ i δ x i ≤ Ω×Ω |x -y| p d tγ + (1 -t)γ ′ (x, y) = t Ω×Ω |x -y| p dγ(x, y) + (1 -t) Ω×Ω |x -y| p dγ ′ (x, y) = tF (c 1 , . . . , c k ) + (1 -t)F (c ′ 1 , . . . , c ′ k )
. This precisely means that the map F is convex.

3.3.

Existence and uniqueness of the optimum. In this subsection we show how to use the reformulation of the minimization problem (3.2) obtained in Lemma 3.2 and the results on optimal mass transportation collected in Section 2.2 to show existence and uniqueness (under suitable assumptions) of an optimum for (3.2). In the following we consider for i = 1, . . . , k the functions η

i : [0, 1] → [0, +∞[ defined by η i (t) = th i (t) .
(3.4) Proposition 3.4. Assume that the functions h i are lower semi-continuous. Then:

(i) there exists an optimum ( A i ) i=1,...,k for (3.2);

(ii) if in addition the maps η i are strictly convex the optimum is unique.

Proof. (i) Recalling the definitions of F and η i and using Lemmas 3.2 and 3.3 we have

inf (3.2) = inf c∈S F (c 1 , . . . , c k ) + k i=1 η i (c i ) .
The expression to be minimized on the right hand side of the above equality is a lower semi-continuous function defined on the non-empty compact set S, hence there exists a minimizer ( c i ) i=1,...,k . By Theorem 2.1 there exists an optimal transport map

T from f L d Ω to k i=1 c i δ x i . Thanks to Remark 2.2 the transport map T is associated to a partition ( A i ) i=1,...,k of Ω which satisfies c i = A i f (x) dx.
Let us check that this partition is an optimum for (3.2). From the above considerations we deduce

inf (3.2) = min c∈S F (c 1 , . . . , c k ) + k i=1 η i (c i ) = F ( c 1 , . . . , c k ) + k i=1 η i ( c i ) = W p p f L d Ω, k i=1 c i δ x i + k i=1 η i ( c i ) = k i=1 A i |x -x i | p f (x) dx + k i=1 η i A i f (x) dx .
This exactly means that ( A i ) i=1,...,k is an optimum for (3.2).

(ii) Assume by contradiction that we have two different optima ( A i ) i=1,...,k and ( A i ) i=1,...,k for (3.2). We define

c i = A i f (x) dx and c i = A i f (x) dx for each i = 1, . . . , k. It is immediate to check that T (x) = k i=1 x i 1 A i (x) is an optimal transport map from f L d Ω to k i=1 c i δ x 1 and that T (x) = k i=1 x i 1 A i (x) is an optimal transport map from f L d Ω to k i=1 c i δ x 1 .
Recalling the fact that the optimal transport map from a diffuse measure to an atomic measure is unique (see Theorem 2.1 for the case p > 1 and Corollary 2.6 for the case p = 1) we deduce that ( c i ) i=1,...,k = ( c i ) i=1,...,k . But using again the result in Lemma 3.2 we deduce that ( c i ) i=1,...,k and ( c i ) i=1,...,k are minimizers of the map S ∋ (c 1 , . . . , c k ) → F (c 1 , . . . , c k ) + k i=1 η i (c i ). However, the strict convexity of the maps η i , together with the convexity of F shown in Lemma 3.3, implies the uniqueness of the minimizer of this map, and from this contradiction we deduce the thesis.

3.4. Characterization of the optimum. We say that a function φ :]0, 1] → [0, +∞[ is differentiable if it is differentiable in the usual sense in the open interval ]0, 1[ and has a left derivative in the point 1. We also use the convention 0h ′ i (0) = 0.

Proposition 3.5 (Necessary optimality condition). Let (A i ) i=1,...,k be an optimum for (3.2).

Assume that h i are differentiable in ]0, 1] and continuous in 0. Then for all i = 1, . . . , k the following holds:

   A i = x ∈ Ω : |x -x i | p + h i (c i ) + c i h ′ i (c i ) < |x -x j | p + h j (c j ) + c j h ′ j (c j ) ∀ j = i c i = A i f (x) dx , (3.5)
where as usual equalities between sets are intended up to f -negligible sets.

Proof. Consider a partition (A r ) r=1,...,k which is an optimum for (3.2) and take an L d -negligible

set N ⊂ Ω such that for every x ∈ N (i) x is a Lebesgue point of f ; (ii) if x ∈ A r , then x is a point of density 1 in A r .
Fix now two indices i and j in {1, . . . , k} and consider a point x 0 ∈ A i \ N . For every ǫ > 0 let the partition ( A r ) r=1,...,k be defined by

       A i = A i \ B ε (x 0 ) A j = A j ∪ A i ∩ B ε (x 0 ) A r = A r for all r ∈ {1, . . . , k} \ {i, j} . Let c ε = A i ∩Bε(x 0 ) f (x) dx.
By the optimality of the partition (A r ) r=1,...,k , comparing its total cost with the total cost of the partition ( A r ) r=1,...,k we deduce

k r=1 Ar |x -x r | p f (x) dx + k r=1 c r h r (c r ) ≤ r=1,...,k r =i,j Ar |x -x r | p f (x) dx + r=1,...,k r =i,j c r h r (c r ) + A i \Bε(x 0 ) |x -x i | p f (x) dx + (c i -c ε )h i (c i -c ε ) + A j ∪(A i ∩Bε(x 0 )) |x -x j | p f (x) dx + (c j + c ε )h j (c j + c ε ) .
This leads to

A i ∩Bε(x 0 ) |x -x i | p f (x) dx + c i h i (c i ) + c j h j (c j ) ≤ (c i -c ε )h i (c i -c ε ) + A i ∩Bε(x 0 ) |x -x j | p f (x) dx + (c j + c ε )h j (c j + c ε ) .
We now divide this expression by ω d ε d , where ω d is the volume of the unit ball in R d . We obtain

1 ω d ε d A i ∩Bε(x 0 ) |x -x i | p f (x) dx + c i ω d ε d h i (c i ) -h i (c i -c ε ) + c ε ω d ε d h i (c i -c ε ) ≤ 1 ω d ε d A i ∩Bε(x 0 ) |x -x j | p f (x) dx + c j ω d ε d h j (c j + c ε ) -h j (c j ) + c ε ω d ε d h j (c j + c ε ) .
Letting ε → 0 and recalling that x 0 satisfies assumptions (i) and (ii) we easily obtain

|x 0 -x i | p f (x 0 ) + f (x 0 )c i h ′ i (c i ) + f (x 0 )h i (c i ) ≤ |x 0 -x j | p f (x 0 ) + f (x 0 )c j h ′ j (c j ) + f (x 0 )h j (c j )
, that is the desired thesis.

The following lemma will imply that condition (3.5) is in fact sufficient, under reasonable assumptions.

Lemma 3.6. Assume that the functions h i are differentiable in ]0, 1] and continuous in 0 and that η i are convex. Then there exists at most one partition (A i ) i=1,...,k for which (3.5) holds.

We notice that the convexity assumption on η i is satisfied for instance if h i (t) = t q with 0 < q < 1, which are natural concave cost functions.

Proof of Lemma 3.6. Assume by contradiction that there exist two partitions (A i ) i=1,...,k and ( A i ) i=1,...,k satisfying (3.5). We set c i = A i f (x) dx and c i = A i f (x) dx and we consider the set I = i ∈ {1, . . . , k} : c i < c i . Assume that I is nonempty. Recalling the definition of the functions η i and comparing with (3.5) we obtain

i∈I A i = x ∈ Ω : min i∈I |x -x i | p + η ′ i (c i ) < min j ∈I |x -x j | p + η ′ j (c j )
and

i∈I A i = x ∈ Ω : min i∈I |x -x i | p + η ′ i ( c i ) < min j ∈I |x -x j | p + η ′ j ( c j ) .
Since we are assuming that the functions η i are convex, we obtain that

η ′ i (c i ) ≤ η ′ i ( c i ) for every i ∈ I and that η ′ j (c j ) ≥ η ′ j ( c j ) for every j ∈ I. This immediately implies that ∪ i∈I A i ⊆ ∪ i∈I A i , thus ∪ i∈I A i f (x) dx ≤ ∪ i∈I A i f (x) dx . (3.6)
But recalling the definition of c i and c i and of the set I we have

∪ i∈I A i f (x) dx = i∈I c i < i∈I c i = ∪ i∈I A i f (x) dx ,
and this is in contradiction with (3.6). We deduce that the set I is empty, which means that c i ≥ c i for every i = 1, . . . , k. By symmetry the opposite inequality is also true, thus we obtain that c i = c i for every i = 1, . . . , k. But going back to (3.5) we immediately deduce that A i = A i for every i = 1, . . . , k.

Proposition 3.7 (Sufficient optimal condition). Let (A i ) i=1,...,k be a partition of Ω which satisfies (3.5). Assume that the functions h i are differentiable in ]0, 1] and continuous in 0 and that η i are convex. Then (A i ) i=1,...,k is the unique optimum for (3.2).

Proof. It is a direct consequence of Propositions 3.4 and 3.5 and of Lemma 3.6.

3.5. Summary of the results on the optimum. We close this section presenting a summary of the results relative to the optimum for (3.2). Remember that the functions η i have been defined in (3.4).

• If h i are lower semi-continuous, then there exists an optimum for (3.2).

• If h i are lower semi-continuous and η i are strictly convex, then there exists a unique optimum for (3.2).

• If h i are differentiable in ]0, 1] and continuous in 0 and η i are convex, then there exists a unique optimum for (3.2). • If h i are differentiable and continuous in 0, then (3.5) is a necessary optimality condition.

• If h i are differentiable in ]0, 1] and continuous in 0 and η i are convex, then (3.5) is a necessary and sufficient optimality condition.

We remark in passing what follows: in the general setting of the Monge problem, the "distance" |y -x| p is replaced by any lower semi-continuous function c(x, y), usually called cost function. But in fact we have used only two features of the particular choice c(x, y) = |y -x| p , namely, the existence and uniqueness of an optimal transport map and the fact that for any y ∈ Ω the level sets of c(•, y) are negligible. Hence our results can be extended for general costs c(x, y) for which both properties hold true, such as c(x, y) = |y -x| p with 0 < p < 1 (see [START_REF] Gangbo | The geometry of optimal transportation[END_REF]) or c(x, y) = yx for different kinds of norm (see [START_REF] Caffarelli | Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs[END_REF] and [START_REF] Ambrosio | Existence of optimal transport maps for crystalline norms[END_REF]).

4. Existence, uniqueness and charaterization of the equilibrium 4.1. Definition of the equilibrium. In this section we start to consider the situation from the point of view of the single citizen. Assume for the moment that the sets A i , and so the quantities c i , are given: the single citizen is probably not interested whether the partition (A i ) i=1,...,k is optimal in the global sense that we discussed up to now. Indeed, it is quite convincing that he does not even know the sets A i , nor the quantities c i , nor the functions h i : what is meaningful, is that he only knows the quantities h i (c i ), i.e. the queue times in the various services. Then, of course, a citizen living at x ∈ Ω and going to x i shall be "satisfied" if and only if

|x -x i | p + h i (c i ) = min j=1,...,k |x -x j | p + h j (c j ) .
In the context of game theory this is precisely a Nash equilibrium (see Section 12.3 of [START_REF] Aubin | Optima and equilibria. An introduction to nonlinear analysis[END_REF]): each player is satisfied in the sense that his strategy (i.e. the choice of the service) is the best possible, once the behaviour of the other players (in this case, the sets A i ) is fixed. We give the following definition. Definition 4.1. We say that a partition (A i ) i=1,...,k of Ω is an equilibrium if for every i = 1, . . . , k the following condition holds:

     A i = x ∈ Ω : |x -x i | p + h i (c i ) < |x -x j | p + h j (c j ) for every j = i c i = A i f (x) dx . (4.1)
We remark that this type of equilibrium is non-cooperative: each citizen chooses the service just by himself, without collaborating with the other citizens in order to choose a "better" global strategy. In Theorem 4.4 and Proposition 4.5 we show that there exists an equilibrium, under fairly general assumptions: we remark that this is not a trivial result, since in general game theory it is typically a difficult task to show existence of a Nash equilibrium.

4.2.

Existence and uniqueness of the equilibrium. In this subsection we show how it is possible to formulate an auxiliary problem in such a way that the optimum for this new problem corresponds to the equilibrium for the original problem. Thus we easily deduce some existence and uniqueness results for the equilibrium, relying on the results presented in the previous section.

Assume that the functions h i are continuous. We introduce for i = 1, . . . , k the functions

g i : [0, 1] → [0, +∞[ defined by g i (t) =        1 t t 0 h i (s) ds if 0 < t ≤ 1 h i (0) if t = 0.
It is immediate that the functions g i are continuous and that t → tg i (t) are differentiable everywhere in [0, 1] with derivative h i (t).

Proposition 4.2. Assume that the functions h i are continuous. Every partition (A i ) i=1,...,k of Ω which is a minimizer of the problem inf

(A i ) i=1,...,k partition of Ω k i=1 A i |x -x i | p + g i A i f (x) dx f (x) dx (4.2)
is an equilibrium for the original problem. If in addition the functions h i are non-decreasing then every equilibrium for the original problem is a minimizer of (4.2).

Proof. Consider a minimizer (A i ) i=1,...,k of (4.2). Since the functions g i are continuous in 0 and the functions tg i (t) are differentiable in [0, 1] we can apply Proposition 3.5 to deduce that (A i ) i=1,...,k satisfies the optimality condition (3.5), but in view of the definition of g i this condition is precisely (4.1): recall that tg i (t) ′ = h i (t). Thus (A i ) i=1,...,k is an equilibrium for the original problem. If h i is non-decreasing for all i = 1, . . . , k, we immediately obtain the convexity of the functions t → tg i (t), thus we can apply Proposition 3.7, obtaining precisely that every equilibrium for the original problem is a minimizer of (4.2).

Remark 4.3. Arguing similarly to the previous proof, we can also show that, under the assumption that the maps η i defined in (3.4) are differentiable in [0, 1], any optimum for (3.2) is an equilibrium for the problem with queue functions

hi (t) = h i (t) + th ′ i (t) i = 1, . . . , k .
Using the correspondence given by the previous proposition, it is now easy to show the following theorem. Theorem 4.4. Assume that the functions h i are continuous. Then there exists an equilibrium. If in addition the functions h i are non-decreasing then the equilibrium is unique.

Proof. Under the assumptions of the theorem we have that the functions t → tg i (t) are lower semi-continuous, thus applying Proposition 3.4 we obtain the existence of a minimizer of (4.2), and using the result of Proposition 4.2 we deduce that this minimizer is an equilibrium for the original problem. If the functions h i are non-decreasing we apply again Proposition 4.2, obtaining that every equilibrium for the original problem is a minimizer of (4.2). But since h i are non-decreasing we also deduce that the maps t → tg i (t) are convex, thus using Proposition 3.7 we deduce that (4.2) has a unique solution, and this concludes the proof.

4.3.

A direct proof in the case k = 2. We now give an alternative and more direct proof of the above result in the particular case k = 2. This has also the advantage of introducing some ideas and notation that will be important in the dynamical analysis of Section 5. In what follows, we will make extensively use of the following definitions:

τ (x) = |x -x 1 | p -|x -x 2 | p , m(t) = {x : τ (x)<t} f (x) dx . (4.3)
The condition in (4.1) defining the equilibrium can be read in this context as follows: a partition (A 1 , A 2 ) of Ω is an equilibrium when there exists t ∈ R such that:

A 1 = x ∈ Ω : τ (x) < t , A 2 = x ∈ Ω : τ (x) > t (4.4) h 2 1 -m( t) -h 1 m( t) = t . (4.5)
Proposition 4.5. Assume that the functions h 1 and h 2 are continuous and non-decreasing.

Then there exists a unique equilibrium (A 1 , A 2 ).

Proof. Let us consider the map

U (t) = t -h 2 1 -m(t) + h 1 m(t) .
It is a continuous and strictly increasing map. Notice that for t ≥ sup Ω τ we have m(t) = 1 and U (t) = th 2 (0) + h 1 (1) so that lim t→+∞ U (t) = +∞. In the same way for t ≤ inf Ω τ we have m(t) = 0 and U (t) = th 2 (1) + h 1 (0), thus lim t→-∞ U (t) = -∞. By consequence, there exists a unique t such that U ( t) = 0, that is, (4.5) holds. Then the partition (A 1 , A 2 ) associated to t as in (4.4) is an equilibrium and this is unique.

4.4.

A comparison between optimum and equilibrium. Recall that the optimality condition for the optimum obtained in Proposition 3.5, read with the notation of the previous subsection, was

h 2 1 -m t + 1 -m t h ′ 2 1 -m t -h 1 m t -m t h ′ 1 m t = t .
Thus a comparison with (4.5) shows how deep is the difference between the two conditions of optimality. In this subsection we give two explicit examples in which we see in a qualitative way some differences between the optimum and the equilibrium.

Example 4.6. On a beach represented by Ω = [0, 1] there are two ice-cream shops at coordinates x 1 = 1/4 and x 2 = 3/4. Suppose there are less employes in the second shop, so that h 1 (t) = t and h 2 (t) = (1 + ε)t. Assume that the costumers are uniformly distributed on the beach, that is f ≡ 1, and take p = 2. In this case the optimum (A 1 , A 2 ) is given by

A 1 = [0, λ opt ε [ , A 2 =]λ opt ε , 1] with λ opt ε = 1 2 + ε 5 + 2ε , whereas the equilibrium (B 1 , B 2 ) is B 1 = [0, λ eq ε [ , B 2 =]λ eq ε , 1] with λ eq ε = 1 2 + ε 6 + 2ε ≤ λ opt ε .
The costs for the customers in the two cases are given by: cost on the optimum cost on the equilibrium position

|x -1/4| 2 + λ opt ε |x -1/4| 2 + λ eq ε 0 ≤ x ≤ λ eq ε |x -1/4| 2 + λ opt ε |x -3/4| 2 + (1 + ε)(1 -λ eq ε ) λ eq ε ≤ x ≤ λ opt ε |x -3/4| 2 + (1 + ε)(1 -λ opt ε ) |x -3/4| 2 + (1 + ε)(1 -λ eq ε ) λ opt ε ≤ x ≤ 1
Note that, in the case ε = 0, the situations of optimum and equilibrium coincides and we have

A 1 = B 1 = [0, 1/2[ and A 2 = B 2 =]1/2, 1].
In the case ε > 0, despite the global cost is minimized by the partition (A 1 , A 2 ), in the equilibrium situation more than one half of the costumers pay less than in the optimum situation.

Example 4.7. Let us now take Ω = [0, 1], f ≡ 1, x 1 = 0, x 2 = 1, p = 1 and h 1 (s) ≡ 100 and h 2 (s) = 0 for 0 ≤ s ≤ 0.999 1 for 0.999 < s ≤ 1.

It is clear that the unique equilibrium is A 1 = ∅ and A 2 = [0, 1], whereas the optimum is obtained with A 1 = [0, 0.001[ and A 2 =]0.001, 1]. Notice that the optimum is very unfair for costumers living in A 1 , who pay 100 + x, whereas the other costumers just pay the distance from 1. Note that the result would have the same features with h 2 equal to 0 on [0, 0.998], equal to 1 on [0.999, 1] and increasing smoothly from 0 to 1 on ]0.998, 0.999[.

A comparison with Pareto optimum.

The examples given in the previous subsection show that in some cases the global optimum can really be not convenient for some citizens; in particular, in Example 4.7 the optimum is better than the equilibrium for 99.9% of the citizens, even though it is much worse for the remaining 0.1%. In some classical games (like the wellknown prisoner's dilemma, see for instance Section 7.8 of [START_REF] Aubin | Optima and equilibria. An introduction to nonlinear analysis[END_REF]) the equilibrium is in fact a bad strategy for all players, in the sense that there is a situation which is better for everybody.

On the contrary, we are going to see that in our model this can not happen. Even more, given an equilibrium, we show that it is not possible to find a situation in which every citizen spend less time. More precisely, and introducing a further notion from game theory, we are going to see that every equilibrium is a Pareto optimum for the problem. This means that, in our situation, starting from the non-cooperative Nash equilibrium it is not possible to lower the costs of all the citizens by a cooperation in the choice of the services.

Let us introduce the individual cost function

C(x, (B i ) i ) = k i=1 |x -x i | p + h i B i f (x) dx 1 B i (x) , (4.6)
defined for x ∈ Ω and (B i ) i=1,...,k partition of Ω. We say that a partition (A i ) i=1,...,k of Ω is a Pareto optimum (see also Section 12.5 of [START_REF] Aubin | Optima and equilibria. An introduction to nonlinear analysis[END_REF]) if there exists no partition (B i ) i=1,...,k of Ω satisfying

C(x, (B i ) i ) ≤ C(x, (A i ) i ) for f -a.e. x ∈ Ω
with strict inequality in a set of strictly positive measure. With this definition of C the following equivalence is immediate:

(A i ) i=1,...,k is an equilibrium ⇐⇒ C(x, (A i ) i ) = min j=1,...,k |x -x j | p + h j A j f (x) dx . (4.7)
We establish now the following result of independent interest, which makes a connection between the equilibrium and the optimal transport map from µ = f L d Ω to the atomic measure concentrated on the points x 1 , . . . , x k .

Proposition 4.8 (Link between equilibrium and optimal transportation). Let (A i ) i=1,...,k be a

partition of Ω, µ = f L d Ω, c i = A i f , ν = k i=1 c i δ x i and T = k i=1 x i 1 A i ; let moreover u(x) = C(x, (A i ) i ) and v(x i ) = -h i (c i ).
Then the couple (u, v) is optimal for the dual problem (2.2) if and only if (A i ) i=1,...,k is an equilibrium. Moreover, in this case T is an optimal transport map between µ and ν.

Proof. First of all, one can notice that the cost of the transport T equals Ω u dµ

+ i c i v(x i ): indeed, one has Ω |x -T (x)| p dµ = k i=1 A i |x -x i | p f (x) dx = k i=1 A i |x -x i | p + h i (c i ) f (x) dx + k i=1 c i v(x i ) = Ω u(x) dµ(x) + Ω v(x) dν(x) .
Thanks to Theorem 2.3 we deduce that, if (u, v) is admissible for the dual problem, then T is an optimal transport map and (u, v) is optimal for the dual problem.

On the other hand, the property (4.7) exactly means that (u, v) is admissible for the dual problem if and only if (A i ) i=1,...,k is an equilibrium. These two considerations give the thesis.

Notice that, in the situation of the proposition above, it may happen that T is an optimal map but (u, v) is not optimal for the dual problem and (A i ) i=1,...,k is not an equilibrium.

We now use Proposition 4.8 to prove that an equilibrium is a Pareto optimum.

Proposition 4.9. Assume that the maps h i are strictly increasing and let (A i ) i=1,...,k be an equilibrium. Let (B i ) i=1,...,k be a partition of Ω such that

C(x, (B i ) i ) ≤ C(x, (A i ) i ) for f -a.e. x ∈ Ω. (4.8)
Then the partitions (A i ) i=1,...,k and (B i ) i=1,...,k coincide.

Proof. We first show that for every i = 1, . . . , k the equality

A i f (x) dx = B i f (x) dx holds.
Indeed, if this were not true, we could find j ∈ {1, . . . , k} such that

A j f (x) dx < B j f (x) dx.
Considering a point x ∈ B j such that (4.8) holds we have |x -

x j | p + h j B j f (x) dx = C(x, (B i ) i ) ≤ C(x, (A i ) i ) = min i=1,...,k |x -x i | p + h i A i f (x) dx ≤ |x -x j | p + h j A j f (x) dx .
But this leads to a contradiction: indeed, h j being strictly increasing, we should have

h j A j f (x) dx < h j B j f (x) dx . This shows as claimed that A i f (x) dx = B i f (x) dx
for every i = 1, . . . , k. Since (A i ) i=1,...,k is an equilibrium, using Proposition 4.8 we obtain that the map T = k i=1 x i 1 A i is an optimal transport map from µ to k i=1 A i f (x) dx δ x i . Using this fact and applying the assumption (4.8) we deduce

k i=1 B i |x -x i | p f (x) dx ≤ k i=1 A i |x -x i | p f (x) dx = W p µ, k i=1 A i f (x) dx δ x i = W p µ, k i=1 B i f (x) dx δ x i .
Hence the map S = k i=1 x i 1 B i is an optimal transport map from µ to k i=1

B i f (x) dx δ x i = k i=1 A i f (x) dx δ x i .
By the uniqueness results of Theorem 2.1 and Corollary 2.6 we conclude.

Corollary 4.10. If the maps h i are strictly increasing, then every equilibrium is a Pareto optimum.

Evolution dynamic and convergence to the equilibrium

In this section we discuss a dynamical formulation of the problem, in which every single day each citizen decides where to go, using the knowledge of what happened in the previous days and trying to make a "smart" choice. We set the problem and discuss under which assumptions the situation converges to the (unique) individual equilibrium, giving also counterexamples to show that this is not always the case. In the first subsection we consider the standard evolution, where every day one thinks only to the previous day. In the second subsection we study the evolution with prudence, where the citizens again remember only the previous day, but are more careful and try to avoid changing idea too often. In the last subsection we describe the case of the evolution with memory, where each day the citizens remember more previous days. In all this section, to keep the discussion as simple as possible, we consider the case k = 2 when there are only two services located at x 1 and x 2 ; however, the general case requires more care with multiple indeces but no really new ideas.

Recall that, thanks to Proposition 4.5, we know the existence of a unique individual equilibrium under the assumption that the functions h 1 and h 2 are continuous and non-decreasing.

Standard evolution.

We face now the question whether or not the situation can naturally evolve toward this equilibrium. By "naturally" we mean that we try to model the evolution in time, in which the citizens do not know the situation in its complete complexity, but they just see how long is the queue and decide day by day how to behave. In other words, we introduce a simple scheme which models the everyday choice of people, and we study the possible convergence under this model. The idea is very easy: at each day, each citizen decides freely whether to go to x 1 or to x 2 . Moreover, at the end of every day he discovers what has happened in that day, that is, he discovers h 1 (c 1 ) and h 2 (c 2 ): this will clearly affect the choice of the following day. More precisely, for each j ∈ N we have the function ψ j : Ω → {0, 1}, where ψ j (x) = 0 (resp. ψ j (x) = 1) means that at the day j the citizen living at x goes to x 1 (resp. to x 2 ); note that, Notice that the function G has a very simple meaning, namely, it is t j+1 = G(t j ); moreover t is uniquely determined by the fact that G( t) = t. We then prove the following result which clarifies what happens for the standard evolution. Proposition 5.1. Assume that h 1 and h 2 are continuous and non-decreasing, as well as that

|G(s) -G(t)| < |s -t| (5.6)
for all s = t ∈ R. Then t j → t for j → +∞, hence also ψ j → ψ uniformly on the compact subsets of Ω \ {τ = t}.

Proof. The evolution of the sequence j → t j is shown in the Figure 1: notice that since h 1 and h 2 are non-decreasing then the function G is non-increasing, hence the equilibrium point t = G( t) is unique. Let us assume by symmetry that, as in the figure, t 1 ≤ t: then, since G is a

-M N t 0 t 2 t 3 t 1 G Figure 1.
The situation in Proposition 5.1 non-increasing function and G( t) = t, we have immediately that t n ≥ t for all even n and t n ≤ t for all odd n. Therefore, t 2n ց t + and t 2n+1 ր t -with t -≤ t ≤ t + . Moreover, by continuity of G it is clear that G(t + ) = t -and G(t -) = t + . By (5.6) we deduce that, if t -< t + , then

t + -t -= G(t -) -G(t + ) < t + -t -,
which gives an absurd: hence, t -= t + , so t j → t as we stated. Consider now any compact subset K of Ω \ {τ = t}: there is then a small interval I ∋ t so that τ (x) / ∈ I for all x ∈ K. There exists j, depending on I thus on K, such that t j ∈ I for all j ≥ j; hence, for any x ∈ K and for any j ≥ j, one has ψ j (x) = ψ(x).

Remark 5.2. As the proof underlines, we have more than the uniform convergence of ψ j to ψ on the compact subsets of Ω \ {τ = t}: indeed, in such compact subsets one has that ψ j ≡ ψ for j ≫ 1.

Example 5.3 (Non-convergence). We show now that the strict 1-Lipschitzianity of G required in Proposition 5.1 is necessary. Indeed, let f and h 1 , h 2 be such that G(t) = 1t for t ∈ (-2, 2): this is of course possible with a smooth choice of f and of h 1 and h 2 . Moreover, let ψ 0 be given by (5.2): in this case it is clear that t j = 0 for all even j and t j = 1 for all odd j, so there is not convergence to t = 1/2. Notice that in this case G is a Lipschitz function with Lipschitz constant equal to 1.

We can easily understand a practical meaning of the possible non-convergence that we have described: if a small town has two supermarkets, there is not a big difference for the people to drive to one or to the other one. However, it may happen that these supermarkets can have very long queues. Therefore, if in a certain day everybody decides to go to the first one, all the people will be unsatisfied with their choice, noticing that the other one has no queue. Consequently, in the next day everybody will go to the second supermarket, leading to a long queue in this one and no queue in the first one. Clearly this procedure will be repeated all the following days, and so there will be no convergence.

Remark 5.4. Let us underline what is the meaning of the request of 1-Lipschitzianity of G; if everything is smooth, we can evaluate

G ′ (t) = -h ′ 2 (1 -m(t)) -h ′ 1 (m(t)) m ′ (t) ;
hence, requiring that |G ′ | is small means that we want h ′ i and/or m ′ small: the first fact means that the queue does not change dramatically for a small change in the quantity of people; and the second one means that f is not too big, so that a small region of the city (the region where the people can have the doubt whether going to one or the other place) does not contain too many citizens. 5.2. Evolution with prudence. As Example 5.3 shows, in the previous setting the convergence to the individual optimum does not always hold; however, this does not seem to be likely. In particular, in the case described in the second part of the example, it seems not so reasonable that people continue to change their idea every day in such a silly way. To model the "smarter" behaviour of the people, we can follow two ways. One way is to allow people to remember more than a single day, giving them a memory, and this is the content of Section 5.3. The other way, which is what we investigate now, is to make people more "prudent".

To introduce the concept of prudence, we start by noticing that the easiness with which people change their habit is excessive: in other words, it is not very reasonable that for a generic x ∈ Ω the function j → ψ j (x) can change from 0 to 1 and vice-versa. The idea of "prudence" is that it can be more convenient to consider the choice of a citizen living at x at time j as a stochastic variable, hence using the approach with transport plans instead of transport maps; recalling (2.1), this means that the value of ψ j (x) can be not only 0 or 1, but any number between 0 and 1. This approach is also common in game theory, and is related to the notion of mixed strategy, for which we refer to Section 7.4 of [START_REF] Aubin | Optima and equilibria. An introduction to nonlinear analysis[END_REF]. So, ψ j (x) is the percentage of the citizens living at x which decide to go to x 2 at the time j, while 1ψ j (x) is the percentage of those going to x 1 . With this approach, one is not assuming that all the citizens living at the same place x are forced to take always exactly the same decisions. The evolution rule will be then a simple modification of (5.3). Recall the definition (5.1) of m j which corresponds to the mass of people going to x 1 at time j. Notice also that the definition (5.4) of t j+1 means that at time j + 1, for a citizen living at x it would seem at first glance more convenient to go to x 1 (resp.

x 2 ) if τ (x) is smaller (resp. greater) than t j+1 . We introduce then a parameter 0 < ρ < 1 which we call prudence parameter, expressing the "resistance" that the average citizen feels against changing his habit. The evolution rule is then given as follows:

ψ j+1 (x) = ρψ j (x) if τ (x) < t j+1 1 -ρ 1 -ψ j (x) otherwise.
(5.7)

Note that the extreme case ρ = 0, that is no prudence, corresponds to the case of the previous section; on the opposite, the extreme case ρ = 1, that is full prudence, means that nobody will ever change his habit, and so ψ j = ψ 0 for each j. We can then prove our result.

Theorem 5.5. Assume that f is bounded and that h 1 and h 2 are non-decreasing and Lipschitz continuous. Then there exists 0 < ρ < 1 so that, if ρ < ρ < 1, ψ j converges to ψ uniformly on the compact subsets of Ω \ {τ = t}.

Proof. First of all, we introduce the quantities

S 2 j = {τ (x)< t} ψ j (x) dµ(x) and S 1 j = {τ (x)> t} 1 -ψ j (x) dµ(x) . (5.8)
Observe that, at time j, S 2 j is the amount of people which are going to x 2 , but which should go to x 1 according to the equilibrium ψ; analogously, S 1 j are the people going to x 1 and which should go to x 2 . Clearly, if we call m = m( t), it is m j = m + S 1 j -S 2 j , where m j is defined in (5.1). Hence, comparing (4.5) and (5.4) and recalling that h 1 and h 2 are Lipschitz, we deduce

t j+1 -t ≤ K S 1 j -S 2 j (5.9)
with a constant K depending only on h 1 and h 2 . Moreover, since h 1 and h 2 are non-decreasing and since G( t) = t by definition of equilibrium, we deduce that m j ≤ m implies t j+1 ≥ t and symmetrically m j ≥ m implies t j+1 ≤ t. This means that if at time j "few" people are going to x 1 , at time j + 1 "many" people will assume to be convenient to do so: however, thanks to the prudence, only a part of those people will indeed change their goal point.

Let us now take j ∈ N and let us assume by symmetry that S 1 j ≥ S 2 j , hence m j ≥ m( t), t j+1 ≤ t and m(t j+1 ) ≤ m( t). Keep in mind that, due to the prudence, it is not true in general that m j = m(t j ). By construction, we know S 1 j+1 = ρS 1 j .

(5.10)

On the other hand, concerning S 2 j+1 , by definition (5.8) one has

S 2 j+1 = {τ < t} ψ j+1 (x) dµ(x) = {τ <t j+1 } ψ j+1 (x) dµ(x) + {t j+1 <τ < t} ψ j+1 (x) dµ(x) = {τ <t j+1 } ρψ j (x) dµ(x) + {t j+1 <τ < t} (1 -ρ + ρψ j (x)) dµ(x) = ρS 2 j + 1 -ρ m( t) -m(t j+1 ) ≤ ρS 2 j + (1 -ρ)D S 1 j -S 2 j .
(5.11)

Here D = KL, where K is given by (5.9) and L is the Lipschitz constant of m: indeed, by immediate geometric arguments one understands that t → L d x ∈ Ω : τ (x) ≤ t is a Lipschitz map, so that m(t), which is the integral over the sets x ∈ Ω : τ (x) ≤ t of the bounded function f , is also Lipschitz. Now, using (5.10) and (5.11) we have

S 1 j+1 -S 2 j+1 ≥ ρ -(1 -ρ)D S 1 j -S 2 j .
We can finally deduce what follows: if the prudence is close enough to 1, namely ρ > 1 -1 D+1 , the sign of S 1 m -S 2 m remains positive for all m ≥ j. In other words, if the population is prudent enough and at a certain moment too many people are going to the service x 1 , then in the sequel the same service will always have more people than in the equilibrium, though the excess becomes smaller and smaller.

We can now observe that S 1 m and S 2 m go to 0 for m → ∞. Indeed, by (5.10) we have that S 1 m = ρ m-j S 1 j , so S 1 m → 0; moreover, being 0 ≤ S 2 m ≤ S 1 m , it is clearly also S 2 m → 0. Using (5.9) we deduce that t m → t, and finally by (5.7) this implies that ψ m converges to ψ uniformly on the compact subsets of Ω \ {τ = t}.

Example 5.6 (Non-convergence). We show that the claim of Theorem 5.5 is sharp, in the sense that a small prudence could be not enough to ensure convergence. As in the second part of Example 5.3, assume to be in a small city with two supermarkets having long queues, and take the prudence ρ = 1/3. Assume also that ψ 0 (x) = 1/4 for f -a.e. x: then, 25% of people are going to the first supermarket and 75% to the second one. Since the city is small, the queue convinces all the citizens that the first supermarket could be better; hence it will be ψ 1 (x) = 3/4 for f -a.e. x, so that at the day 1 one has 75% of people going to the first supermarket and 25% to the second one. Clearly, this procedure will be periodic and there will be no convergence to the equilibrium.

We conclude by noticing that this model with a "fixed prudence" may seem not so convincing, since it appears more likely that the prudence is increasing with the time: this increment can be also thought as a sign of "laziness", or of habit. We describe now how a model with an increasing prudence (that is, ρ = ρ j in the definition (5.7)) gives rise to convergence to the equilibrium.

Theorem 5.7 (Increasing prudence). Assume that f is bounded and that h 1 and h 2 are nondecreasing and Lipschitz continuous. Consider a sequence (ρ j ) j≥1 such that

ρ j → 1 and ∞ j=1 (1 -ρ j ) = +∞ .
Consider an evolution with increasing prudence, i.e. consider (5.7) with ρ = ρ j . Then there is convergence of ψ j to ψ uniformly on the compact subsets of Ω \ {τ = t}.

Proof. Since ρ j → 1, there is j ∈ N so that for all j ≥ j one has ρ j ≥ ρ, being ρ as in Theorem 5.5.

From the proof of that theorem, we know that, assuming by symmetry that S 1 j ≥ S 2 j , for all j ≥ j it is still S 1 j ≥ S 2 j . Notice also that a trivial calculation ensures

∞ j= j ρ j = exp ln ∞ j= j ρ j = exp ∞ j= j ln ρ j ≤ exp ∞ j= j -(1 -ρ j ) = 0 .
(5.12)

Keeping in mind (5.10) and the fact that for all j ≥ j it is S 2 j ≤ S 1 j , we have that S 1 j = S 1 j j-1 l= j ρ l → 0 and so also S 2 j → 0; by (5.9), which does not depend on ρ j , we deduce that t j → t. Finally, the required convergence of ψ j to ψ is shown exactly as in Theorem 5.5 recalling (5.12). We now briefly discuss the assumptions of the above theorem: as already said, the meaning of ρ j → 1 is that the people become more and more prudent, or more and more lazy. The fact that j (1ρ j ) must diverge tells us that if the prudence goes to 1 too fast, we can have convergence to a situation different from the equilibrium: for instance, if ρ j = 1 for all j, as already pointed out we have the full prudence, so that the people do never change their habit, and so ψ j = ψ 0 for all j, whatever ψ 0 is. Finally, we have this last remark.

Remark 5.8. Notice that the constant ρ of Theorem 5.5 depends on the data of the problem. Since it is likely that the people only know how long the queues are everyday, but not the functions f , h 1 and h 2 , a "smart" population does not have enough information to decide a fixed prudence ρ which ensures the convergence to the equilibrium. However, thanks to Theorem 5.7, the population can decide a strategy which surely leads to the convergence, that is an increasing prudence such as, for instance, ρ j = 1 -1/j. 5.3. Evolution with memory. We describe now the second possibility to overcome the unsatisfactory non-convergence behaviour of the simple evolution modeled in Section 5.1. As anticipated, the idea is to allow people to have a memory, so that every day they can decide what to do keeping in mind more than just the queue of the day before. We go back to the deterministic model, in which the position where a citizen lives completely determines his behaviour. Recall that the function G given by (5.5) represents the difference between the queues at x 2 and at x 1 if a quantity m(t) of people is going to x 1 .

In the model of Section 5.1, each citizen assumes that at the day j + 1 the queue would have been the same as in the day j. Here, we give to the people a "memory": in other words, we take κ ∈ N, κ > 1, and in this model each citizen guesses that the queue will be approximatively the average of the queues of the preceding κ days. Therefore, the citizen assumes that the difference between the queues at x 2 and at x 1 at the day j + 1 will be

Q = j m=j-κ+1 G(t m ) κ .
As a consequence, the citizen living at x will decide to go to x 1 at the day j + 1 if τ (x) < Q.

We take ψ 1 , ψ 2 , . . . , ψ κ as data of the problem, which means that for the first κ days we let the people decide freely how to move (as in Section 5.1, the choice of these ψ j 's will not effect any of our results). For each n > κ, one has again

ψ n (x) = 0 if τ (x) < t n 1 otherwise,
but this time the evolution rule is simply

t n+1 = n m=n-κ+1 G(t m ) κ . (5.13)
We give now the first result of this section, which reduces to Proposition 5.1 in the extreme case κ = 1.

Theorem 5.9. Assume that h 1 and h 2 are continuous and non-decreasing. Assume that the function G given by (5.5) is Lipschitz with constant L < κ. Then t n → t for n → +∞, hence also ψ n → ψ uniformly on the compact subsets of Ω \ {τ = t}.

To prove this theorem, we will need the following definition.

Definition 5.10. Given n ∈ N and j ∈ {1, 2, . . . , κ}, we say that the property P j n (α) holds true when, given any set I ⊆ {n, n -1, . . . nκ + 1} with #I = j and n ∈ I, there holds i∈I G(t i ) -G( t) ≤ α .

(5.14)

The fundamental feature of the properties P j n (α) is given by the lemma below.

Lemma 5.11. Assume that G is L-Lipschitz with a constant L ≤ κ. Then take n ∈ N and α > 0, and assume that P j m (α) holds true for any j ∈ {1, 2, . . . , κ} and for any m ∈ {n, n -1, . . . , nκ + 1}. We have then what follows. (A) For any j ∈ {1, 2, . . . , κ} and for any m > n, one has that P j m (α) is true. (B) For any j ∈ {1, 2, . . . , κ} and for any m > n + (j -1)κ one has that P j m (C j α) is true, where

C j = 1 -1 - L κ j .
(5.15)

Before proving the lemma, let us notice how the result of Theorem 5.9 easily follows.

Proof of Theorem 5.9. Let us set n = κ: there exists a positive α such that all the properties P j m (α) are valid for j and m in {1, 2, . . . , κ}, since there are a finite number of inequalities of the type (5.14) to be checked. By part (A) of Lemma 5.11 we know then that all the properties P j m (α) hold true for any m ∈ N and 1 ≤ j ≤ κ. Moreover, since the constants C j are increasing in j because L < κ, by part (B) we also have that the properties P j m (C κ α) are valid for any j and all m > κ + (κ -1)κ, that is

m ≥ κ + κ(κ -1) + 1 .
By an immediate iteration, we obtain the validity of the properties P j m (C h κ α) for all j and all m ≥ κ + h κ(κ -1) + 1 .

Since C κ < 1, the properties with j = 1 are sufficient to deduce that G(t i ) -G( t) → 0 for i → ∞, and since G(t i ) = t i+1 while G( t) = t this ensures that t i → t which is the first part of the thesis. The second part follows from the first one as already done in Proposition 5.1.

Let us then prove the lemma.

Proof of Lemma 5.11. We start by proving (A). Let us then fix m > n and j. We aim to show the validity of the property P j m(α). We can assume as an inductive hypothesis that P j m (α) has already been established

• for all n < m < m and all j;

• for m = m and all j < j.

Let us now fix a set I according with Definition 5.10, and let us assume that t m ≤ t (so that G(t m) ≥ G( t)), which is clearly admissible by symmetry. Keeping in mind that G( t) = t, and then

t m -t = { m-κ≤i< m} [G(t i ) -G( t)] κ , (5.16)
we can first give the simple estimate

i∈I [G(t i ) -G( t)] = G(t m)-G( t)+ i∈I\{ m} [G(t i ) -G( t)] ≥ i∈I\{ m} [G(t i ) -G( t)] ≥ -α . (5.17)
Notice that the last inequality is emptily true for j = 1, even in the stronger form where 0 replaces -α, while for j > 1 it is a consequence of the property P j-1 m (α) with m = max{i ∈ I \ { m}}, which is already known to hold by assumption.

We must now show also the opposite inequality, that is,

i∈I [G(t i ) -G( t)] ≤ α . (5.18)
To this aim notice that, calling J = { m -1, m -2, . . . , m -κ} \ I, one can evaluate

t m -t = i∈I\{ m} [G(t i ) -G( t)] + i∈J [G(t i ) -G( t)] κ ≥ i∈I\{ m} [G(t i ) -G( t)] -α κ , (5.19)
using P j m ′ (α) with m ′ = max J < m and j = #J. Since in the same way one also has i∈I\{ m} [G(t i ) -G( t)] ≤ α, the right term in last inequality is nonpositive: hence, by the L-Lipschitzianity of G and the fact that L ≤ κ we obtain

G(t m) -G( t) ≤ L α -i∈I\{ m} [G(t i ) -G( t)] κ ≤ α - i∈I\{ m} [G(t i ) -G( t)] , (5.20)
which gives (5.18). Hence, we have shown (A) in its full generality.

Let us now attack (B), which will be done performing the same estimates as above, but more carefully. Our proof will be obtained as an induction over j, so we must start with the case j = 1. In fact, this case is trivial: for any m > n, recalling (5.16) we have

t m -t = { m-κ≤i< m} [G(t i ) -G( t)] κ ≤ α κ , (5.21)
and hence by the L-Lipschitzianity of G one has

G(t m) -G( t) ≤ L κ α ;
this means that for any m > n one has the validity of P 1 m(C 1 α) with C 1 = L κ , which coincides with (5.15).

We now take 1 < j ≤ κ, suppose by induction that (B) has been proved for any j < j, and try to obtain the thesis. We take then m > n + ( j -1)κ, a set I as in Definition 5.10 and, as before, to fix the ideas we start assuming without loss of generality that t m ≤ t. Since, as a consequence, we have G(t m) ≥ G( t), it is immediate to give the lower bound. Indeed, exactly as in (5.17), we can estimate

i∈I [G(t i ) -G( t)] = G(t m) -G( t) + i∈I\{ m} [G(t i ) -G( t)] ≥ i∈I\{ m} [G(t i ) -G( t)] ≥ -Cj -1 α ≥ -Cjα . (5.22)
To do so, we have used that Cj -1 ≤ Cj, which is clear by the definition (5.15), and we have also used the validity of P j-1 m ′ (Cj -1 α) where m ′ = max{i ∈ I \ { m}}. And in turn, P j-1 m ′ (Cj -1 α) is true by the inductive assumption and since m ′ > mκ > n + ( j -1)κκ = n + ( j -2)κ .

To conclude the proof, we need then to show the upper bound, that is, i∈I [G(t i ) -G( t)] ≤ Cjα .

(5.23)

We start exactly as we did to show (5.18) in the proof of (A); more precisely, we keep in mind the first inequality in (5.20), which has already been proved above, that is

G(t m) -G( t) ≤ L α -i∈I\{ m} [G(t i ) -G( t)]
κ .

In order to use in a more careful way the L-Lipschitzianity of G, we rewrite the last inequality in the equivalent form

G(t m) -G( t) ≤ L κ α - L κ i∈I\{ m} [G(t i ) -G( t)] ,
from which we obtain, using again some P j-1 m ′ (Cj -1 α) of which we already know the validity by inductive assumption, that

i∈I [G(t i ) -G( t)] ≤ L κ α + 1 - L κ i∈I\{ m} [G(t i ) -G( t)] ≤ L κ α + 1 - L κ i∈I\{ m} G(t i ) -G( t) ≤ L κ α + 1 - L κ Cj -1 α = L κ + 1 - L κ 1 -1 - L κ j-1 α = Cjα , (5.24)
hence (5.23) is established and we have completed the proof.

As in the previous cases, we can give a counterexample to show that a small memory coefficient κ could be not enough to guarantee convergence.

Example 5.12 (Non-convergence). This example is very similar to the ones in Examples 5.3 and 5.6: take a small city with the two supermarkets, and assume that the first supermarket can have a long queue, but the second one can have a much longer one. Take the memory coefficient κ = 2, and assume that in the days 0 and 1 everybody goes to the first supermarket. This gives, for the days j = 0 and j = 1, an average queue which is high for the first supermarket and null for the second one: hence, at the day j = 2 everybody will go to the second supermarket. The average queue for the days j = 1 and j = 2, then, is high for the first shop but very high for the second, thus everybody will go back to the first one at the day j = 3. Again, the average queue for the days j = 2 and j = 3 will be high in the first supermarket and very high for the second one, so also at the day j = 4 everybody will go to the first one. But then, at the day 5 all the people will move to the second one because the average queue for the days j = 3 and j = 4 is all at the first one. This procedure is clearly periodic with a period of 3 days and so the situation does not converge to the equilibrium. It is obvious how to modify the example to show that any memory coefficient κ can be not enough for a suitable choice of Ω, f , h 1 and h 2 .

Let us give also a "precise" counterexample to show the exact role of the assumption L < κ.

Example 5.13. Let us take a situation so that G(t) = -2t for -3 ≤ t ≤ 3. Assume also that κ = 2 and t 0 = t 1 = -1. Then it is immediate to deduce by (5.13) that it will be t j = -1 for all j ≡ 0 (mod 3) or j ≡ 1 (mod 3), while t j = 2 for all j ≡ 2 (mod 3).

In the example above there is no convergence even though the Lipschitz constant L coincides with the memory coefficient κ, and it is immediate to modify the example to find a situation with no convergence with L = κ for any κ. This ensures that the assumption L < κ in Theorem 5.9 is almost sharp. Indeed, we can slightly strengthen the assumption of Theorem 5.9 covering also the situation in which L = κ but the Lipschitzianity is strict. We recall that a function ϕ : X → Y is said strictly Lipschitz with constant L if for any x 1 = x 2 in X one has ϕ(x 1 )ϕ(x 2 ) Y < L x 1x 2 X .

We have the following result.

Theorem 5.14. Assume that h 1 and h 2 are continuous and non-decreasing and that the function G given by (5.5) is strictly Lipschitz with constant κ. Then t n → t for n → +∞, hence also ψ n → ψ uniformly on the compact subsets of Ω \ {τ = t}.

Proof. We start by recalling that the result of Lemma 5.11 has been proved also in the case L = κ; therefore, we can start as in the proof of Theorem 5.9 finding a constant ᾱ and knowing that all the properties P j m (ᾱ) with 1 ≤ j ≤ κ and m ∈ N are valid. However, for L = κ all the constants C j given in (5.15) are all equal to 1, so obtaining P j m (C h j ᾱ) is of no help. We now claim what follows: there exists a continuous and decreasing function ξ : R + → R + such that ξ(α) < α for all α > 0, with the property that if all the P j m (α) with 1 ≤ j ≤ κ and m ≥ n are valid, then all the P j m (ξ(α)) with 1 ≤ j ≤ κ and m > n + κ(κ -1) hold. Notice that this will immediately give the thesis, because for any h ∈ N we will have, for m big enough, all the properties P j m (ξ h (α)), and by the continuity of ξ the sequence h → ξ h (ᾱ) must converge to 0.

To conclude the proof we take α > 0 and we suitably modify the proof of Lemma 5.11 for the case of L = κ but with the strict Lipschitzianity, so to show the existence of the desired constant ξ(α) < α. Our plan is to find constants α j < α for 1 ≤ j ≤ κ in such a way that P j m (α j ) is true for m > m + κ(j -1). The key idea is the following: since G is strictly κ-Lipschitz, for any ε ∈]0, α[ there exists κ ε < κ so that G(t) -G( t) ≤ κ ε |t -t| , for all t ∈ [ tα, tε] ∪ [ t + ε, t + α] : (5.25) this is trivial by compactness, but it will also be very useful for our purpose. We start arguing by induction. The case j = 1 is very easy: indeed, we already noticed in (5.

G(t m) -G( t) ≤ κ ε |t m -t| ≤ κ ε κ α .
Hence we obtain the case j = 1 with α 1 = min{κ ε α/κ, κε} < α. Consider now the case 1 < j ≤ κ, and assume that the claim has been already proved up to j -1. Let us begin as in Lemma 5.11: supposing that t m ≤ t by symmetry, as in (5.22) we have i∈I

G(t i ) -G( t) = G(t m) -G( t) + i∈I\{ m} G(t i ) -G( t) ≥ i∈I\{ m}
G(t i ) -G( t) ≥ -α j-1 (5.26)

  [START_REF] Kantorovich | On the transfer of masses[END_REF]) that for all m > n one has |t m -t| ≤ α/κ. Then we can fix an arbitrary ε < α/κ. If |t m -t| < ε, then by Lipschitzianity of G we haveG(t m) -G( t) ≤ κε ;on the other hand, if |t m -t| ≥ ε, by making use of (5.25) we know that

Acknowledgment. The authors warmly thank Luigi Ambrosio, Guy Bouchitté, Guillaume Carlier, Fabio Priuli and Filippo Santambrogio for many valuable conversations on the subject of

in the language of (2.1), the function ψ j corresponds to ψ 2 at time-step j, while ψ 1 is simply 1ψ 2 . We also set m j ∈ [0, 1] the mass of the people that, at the day j, decide to go to x 1 , i.e. m j := Ω 1ψ j (x) f (x) dx .

(5.1)

The evolution of the problem is the following: we fix any function ψ 0 : Ω → {0, 1}, and consider it as a data of the problem; that is, we leave the citizens free to decide by chance what to do at the day 0. Of course, the most meaningful choice would be

recalling the definitions of τ and m given previously

Indeed, this choice of ψ 0 means that in the first day each one simply goes to the closest of the two service places, which makes sense since he does not have any information about queues. However, our results also hold with any other function ψ 0 . Given now any j ∈ N, and given the function ψ j , the function ψ j+1 is determined as follows:

3)

The meaning of this model is extremely clear: at the day j + 1, each citizen decides where to go assuming that the quantity of people going to x 1 and x 2 will be the same as in the day j.

The first property that we can easily notice is the following: there exists a sequence (t j ) j≥1 such that for any j one has

otherwise; this is immediate by the definition for any j ≥ 1. Being ψ 0 free, we can not say the same for j = 0, of course: however, in the case of the "meaningful" choice (5.2), the above formula holds also for j = 0 with t 0 = 0. Notice that

(5.4) as a consequence, we understand that everything in the choices of the citizen living at x depends only on the value of τ (x). This also implies, for j ≥ 1, that

What we want to know is if the situation converges to the individual optimum; that is, if ψ j converges to the function ψ defined as

where (A 1 , A 2 ) is the equilibrium partition given by Proposition 4.5. Equivalently, we want to understand if t j converges to t where, according to Proposition 4.5, t is the unique real number such that t

.

A first answer to this question is given below. We shall consider the function G : R → R defined by

and the estimate from below is done. Concerning the estimate from above, there are again two cases to consider: fix an arbitrary

On the other hand, if |t m -t| ≥ ε, we can use (5.25) to derive, from (5.19) which says

the estimate

Therefore, we mimic (5.24) to find

(5.28) Recalling (5.26), (5.27) and (5.28), we obtain the inductive step of the claim by setting

We finally set ξ(α) = α κ = max j=1,...,κ α j ; since the continuity of this map ξ is clear by the construction, the proof is obtained.

We conclude the paper with a last result in the same philosophy of Theorem 5.7, in which we considered a prudence increasing in time: we consider what happens with an increasing memory. More precisely, we focus on the case of "global memory", where the citizens remember all the previous days and then the definition (5.13) must be replaced by

We can show that there is always convergence with global memory, and this leads exactly to the same considerations as in Remark 5.8.

Theorem 5.15 (Global memory). Assume that h 1 and h 2 are continuous and non-decreasing. Assume that the function G is Lipschitz, and that the evolution is given by the global memory (5.29). Then t n → t and so ψ n → ψ uniformly on the compact subsets of Ω \ {τ = t}.

Proof. We can rewrite (5.29) in a useful way as

Take then n ∈ N and assume for simplicity that t n ≥ t, so that G(t n ) ≤ G( t): we can estimate

as a consequence, provided n is big enough, regardless of the sign of t n -t we have

Since Π ∞ n=1 1 -1/n = 0, this immediately leads to the thesis. Remark 5.16. One can of course consider a lot of other "schemes of memory". For instance, one could have a global memory with different weights for older days, such as

where the term (1 -2 -n ) is put to let the sum of the coefficients equal 1. It is not hard to notice that our method of proof can be easily adapted to a generality of those "schemes": it is important that t n+1 is given by a mean of terms G(t j ) for some times j ≤ n and that the associated coefficients are decreasing as the days become older; that is,

with 0 ≤ C(n, m) ≤ 1, n m=1 C(n, m) = 1 and C(n, m) ≤ C(n, m ′ ) for m < m ′ . In these cases one has the desired convergence provided G is L-Lipschitz with a suitable constant L as well as general convergence for a Lipschitz G for reasonable global schemes of memory.