Hélène Le Cadre
email: helene.lecadre@energyville.be

Bernardo Pagnoncelli
email: bernardo.pagnoncelli@uai.cl

Tito Homem-De-Mello

Olivier Beaude
email: olivier.beaude@edf.fr

Designing Coalition-Based Fair and Stable Pricing Mechanisms Under Private Information on Consumers' Reservation Prices *

Keywords: OR in Energy, Coalition Formation, Game Theory, Load Scheduling, Forecast Algorithm

We model the relation between an aggregator and consumers joining a coalition to reduce the risk resulting from the unpredictability of their base load demand, as a Stackelberg game formulated as a mathematical bilevel program with private information on the consumers' reservation prices. At the upper-level of the Stackelberg game, the aggregator optimizes his daily price profile so as to reach a net targeted profit which is the maximum value guaranteeing that no consumer will leave the coalition -to contract with a conventional retailer considered here as a fixed alternative -while meeting fairness criterion imposed by the cost-sharing mechanism. At the lower-level, the consumers are asked to provide in day ahead an estimate of their base load hourly demand profile and to schedule their shiftable loads depending on the price signal sent by the aggregator. We provide algorithms that determine the unique price profile and consumer shiftable load schedules as functions of the reservation price estimates. The Stackelberg game between the aggregator and the consumers being repeated for a period of time, the aggregator has the possibility to update his estimates of the reservation prices relying on a feedback function which depends on the percentage of activated loads. A randomized algorithm for consumers' reservation price learning based on regret minimization is provided. For four cost-sharing mechanisms such as uniform allocation, stand-alone cost, Shapley value, separable and non-separable costs, we determine the closed form of the aggregator's optimal net targeted profit guaranteeing the stability of the coalition. We also determine conditions guaranteeing the core non-emptiness and prove that for a profit-maximizing aggregator, the stand-alone cost is always preferable to the Shapley value, which coincides with the uniform allocation. Furthermore, the optimal size of the coalition -in terms of the aggregator's profit -can be determined analytically when the Shapley value is implemented as cost-sharing mechanism. The results are illustrated on a case study where we show that there exists an optimal net targeted profit below which the consumers energy bill is lower when joining the aggregator than with the conventional retailer. Coalition dynamics is also analyzed numerically depending on the consumer inertia in their energy supplier choice process, for each cost-sharing mechanism.

Introduction

Up to now, conventional consumers have a contractual relation with a retail electricity provider that supplies them electricity at a per unit price defined by a contract. Various pricing mechanisms are currently proposed such as flat rate, Time-Of-Use, etc. In all these mechanisms, the price pattern is defined a priori, contrary to progressive and dynamic pricing in which price evolves online according to the consumers' demand. Most of the tariff schemes proposed in the literature do not discriminate on the basis of consumer predictability, therefore poorly capturing the structure of the costs that energy suppliers face by interacting with the wholesale electricity market [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF]. Recently, Prediction-Of-Use tariffs in which consumers are asked to provide in advance a prediction of their consumption during a Table 1: Comparison of the kWh price for different energy suppliers for same subscribed power (6 kVA) for flat rate and peak / off-peak time period tariffs in France in 2018 https://www.kelwatt.fr/fournisseurs. 'Green origin' of the supply is also compared. Symbol * means that the corresponding option is not available or not described. specific period of time and are then penalized based on the deviation between the estimated and the realized demand profiles have been discussed in [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF][START_REF] Vasirani | Smart Consumer Load Balancing: State of the Art an an Empirical Evaluation in the Spanish Electricity Market[END_REF].

In France since 2007, the historical electricity provider EDF has been facing the entry of multiple energy suppliers on the retail market. This trend has been accelerating following the Nome Law1 voted in December 2010, since consumers can now freely terminate their contract with one energy provider to subscribe to another. In Table 1, we have listed the price per kWh for different energy suppliers for same subscribed power (6 kVA) for flat rate and peak / off-peak time period tariffs in 2018. While EDF follows the regulated tariff for pricing its annual subscription and kWh, competitors offer significant reductions in the annual subscription (20 % for Planète Oui, 5 % for Proxelia) or in the kWh price (5 % in average). Furthermore, many energy suppliers now propose in their contract 'green certificates' on the origin of their production or even direct supply from small renewable energy producers like Enercoop, which advocates a militant and ecological approach based on a cooperative model connecting local renewable energy producers to local consumers. 'Green certificates' have been encouraged by governments with the aim to support and promote power generation based on renewable energy sources 2 . Energy suppliers may use it as a commercial differentiating argument to attract consumers based on their brand image and increase their market share.

Aggregators, like Enercoop, primarily group and manage flexibility of a cluster of consumers with the purpose to offer demand response services to the different power system participants through various markets. Potential for aggregators to manipulate the electricity market price via strategic curtailment may exist in practical settings [START_REF] Ruhi | Opportunities for price manipulation by aggregators in electricity markets[END_REF]. Such curtailments are performed through demand response services. There are two basic categories for demand response: price-based demand response and incentive-based demand response [START_REF] Li | Load Management for Price-based Demand Response Scheduling: a Block Scheduling Model[END_REF]. Price-based demand response includes real-time, criticalpeak, Time-Of-Use and Prediction-Of-Use electricity tariffs. Consumers respond to price signals sent by the aggregator by adapting their consumption pattern, reducing their electricity bills if they adjust the timing of their consumption pattern to take advantage of lower-priced periods and avoid consuming when prices are higher [START_REF] Li | Load Management for Price-based Demand Response Scheduling: a Block Scheduling Model[END_REF][START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF][START_REF] Vasirani | Smart Consumer Load Balancing: State of the Art an an Empirical Evaluation in the Spanish Electricity Market[END_REF]. Incentive-based demand response provide refunds to the consumers to schedule their loads at times of lower consumption [START_REF] Chao | Priority Service: Market Structure and Competition[END_REF]. There exists a vast literature dealing with the problem of minimal cost load scheduling under individual preferences [START_REF] Beaude | Reducing the impact of ev charging operations on the distribution network[END_REF][START_REF] Jacquot | Demand Response in the Smart Grid: the Impact of Consumers Temporal Preferences[END_REF]. A model of block load scheduling for price-based demand response is implemented under two different real-time pricing schemes in [START_REF] Li | Load Management for Price-based Demand Response Scheduling: a Block Scheduling Model[END_REF]: linear pricing and threshold pricing. For linear pricing, the demand response strategy is optimized using a water-filling algorithm adapted for each segment of consumers. For threshold pricing, a detailed characterization of different optimal load profiles under a discrete load model is provided. The impact of the predictability of the consumer base load is evaluated through Prediction-Of-Use electricity tariff in [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF]. In [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF], consumers provide baseline load estimation in day ahead and are penalized in real time depending on the deviation between their forecasted and realized demand profiles. Group formation under heterogeneous tariff structures is also formally studied in [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF]. Contrary to [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF], in this paper we consider stability and fairness issues for one group of consumers managed by the aggregator. Our consumer model is more detailed because, while consumption is modeled as a unique real number in [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF], we assume here that each consumer has a stochastic base load and several shiftable loads which are themselves divided into interruptible and block loads. Consumer willingness-to-pay is evaluated through reservation prices which are private information to the consumer. Heterogeneity between the consumer bills inside the aggregator's coalition may be observed but the price signal sent by the aggregator is the same for all the consumers. Note also that there exist only a few gametheoretic references where the price paid by consumers is a function of the total consumption profile in the aggregator pool; this makes shiftable load scheduling coupling between the different consumers through an endogenous tariff mechanism [START_REF] Mohsenian-Rad | Autonomous demand-side management based on game-theoretic energy consumption scheduling for the future smart grid[END_REF][START_REF] Jacquot | Demand Response in the Smart Grid: the Impact of Consumers Temporal Preferences[END_REF]. Close to our model is also the work of Zugno et al. [START_REF] Zugno | A bilevel model for electricity retailers' participation in a demand response market environment[END_REF] who model the interactions between consumers and the aggregator as a Stackelberg game. However, their model does not allow the possibility for consumers to switch energy supplier and they do not consider private information.

We define a coalition of consumers as a set of end users who agree on a joint demand profile to be contracted in the wholesale electricity market through the mediation of an aggregator. Assuming that consumer predictability is captured through the electricity tariff, consumers having incentives to minimize their risk join the coalition [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF]. A similar effect was observed in the work of Zhang et al. [START_REF] Zhang | Competition and Coalition Formation of Renewable Power Producers[END_REF][START_REF] Zhang | Competition and Efficiency of Coalitions in Cournot Games with Uncertainty, working paper[END_REF], where the game becomes efficient (in the sense of the worst-case ratio of the sum of the consumers costs at equilibrium to the sum of the consumers costs at social welfare optimum, named "Price of Anarchy" in game theory literature) when, in the presence of uncertainty, firms are allowed to take advantage of diversity to form groups of certain sizes. Tradeoff between uncertainty reduction and market power determines the optimal group size to reach equilibria that are socially optimal. The aggregator buys electricity in day-ahead and balancing (wholesale) electricity markets. From the market operator point of view, the aggregator is a single buyer of electricity who takes forward positions in the day-ahead electricity market. A coalition is a group of players who decide to act together, as one unit, relative to the rest of the players. It may be useful to think of a representative agent taking their place; in our model it will be the aggregator. However, as pointed out by Hart and Kurz [START_REF] Hart | Endogenous Formation of Coalitions[END_REF], this arrangement will continue only as long as each agent finds it desirable to act this way and bargaining occurs among the members of the coalition on how to allocate the aggregator's cost [START_REF] Chalkiadakis | Computational Aspects of Cooperative Game Theory, Synthesis Lectures on Artificial Intelligence and Machine Learning[END_REF].

Regarding the aggregator as a -or related to a -transmission system operator, the goal of demand response should be to balance demand and supply on the grid at any time period. Many demand response programs provide incentives to major consumers of electricity, usually in the form of monetary rewards, to reduce their electricity consumption in peak demand periods [START_REF] Gkatzikis | The Role of Aggregators in Smart Grid Demand Response Markets[END_REF]. Chao et al. propose more sophisticated menu based product differentiation mechanisms where the electric power supply service is unbundled into discrete levels of reliability with corresponding rates for each level [START_REF] Chao | Priority Service: Market Structure and Competition[END_REF]. In their model, consumers divide their loads into increments to which they associate a service level which defines the interruption loss and the service priority charge. In case of shortage, the utility can ration the available power efficiently to load increments with the highest interruption losses. Stochasticity arising due to local photovoltaic solar panels, the menu based approach of Chao et al. [START_REF] Chao | Priority Service: Market Structure and Competition[END_REF] is extended in a probabilistic shadow price envelope problem in [START_REF] Campagne | Firming renewable power with demand response: an end-to-end aggregator business model[END_REF][START_REF] Margellos | A fuse control paradigm for demand side management: formulation and stochastic pricing analysis[END_REF].

In our model, each consumer has exactly one base load, that cannot be shifted, and several shiftable loads [START_REF] Vasirani | Smart Consumer Load Balancing: State of the Art an an Empirical Evaluation in the Spanish Electricity Market[END_REF]. Only the base load may differ from the estimated one since all the shiftable loads are assumed to be scheduled through the intermediate of an intelligent device deployed in the consumers' houses. This device is responsible for the scheduling of the consumers' shiftable loads: its output is the result of an integer optimization problem that depends on the price signal sent by the aggregator. The aggregator task is made of two parts that occur simultaneously: taking forward positions in the day-ahead electricity market to compensate the uncertainty associated with the base load estimation (similar problem was considered in [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF][START_REF] Vasirani | Smart Consumer Load Balancing: State of the Art an an Empirical Evaluation in the Spanish Electricity Market[END_REF][START_REF] Zugno | A bilevel model for electricity retailers' participation in a demand response market environment[END_REF]); and, pricing his supply service so as to reach a net targeted profit for a fixed and finite number of periods, which is the maximum value guaranteeing the stability of the coalition under some cost-sharing mechanism. In the second part of the aggregator's task, the created value for the aggregator comes from the stochastic nature of the base load demand. Indeed, each consumer pays the aggregator for his short or long position (estimated in day ahead), therefore somehow reporting his risk to the aggregator. But this does not automatically imply that the aggregator will need to cover the position in the balancing market. For example, a short position of a consumer may be cancelled out by a long position of another consumer (exactly the effect observed in [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF]). Although both consumers pay the aggregator for their mismatches, the aggregator is not required to buy or sell power in the balancing. As a result, the aggregator may keep the revenue resulting from the imbalance penalties of two consumers. The second task of the aggregator captures the contribution of our model to the literature.

The questions that we want to address in this paper are the following:

• how should an aggregator price his services so as to reach a net targeted profit?

• how should this net targeted profit be defined so as to guarantee that the consumer coalition remains stable, i.e., prevent consumers from switching to the conventional retailer (and possibly also attract clients of the conventional retailer)?

The stability -of consumers in the coalition -is here addressed by considering a conventional retailer with a fixed tariff offer. This fixed tariff offer corresponds to an exogenous threshold: if consumers get more with aggregator (e.g., a lower energy bill), they remain in the aggregator coalition, otherwise they switch to the conventional retailer offer.

We now detail the organization of the article. In Section 2, we describe the Stackelberg game that occurs between the aggregator and the consumers. In Section 3, the aggregator's problem is formalized as a Stackelberg game and algorithms are introduced to solve the resulting bilevel mathematical optimization problem. In Section 4, we provide an algorithm for learning the consumer reservation prices. Coalition stability and fairness issues are discussed in Section 5. Finally, a numerical case study is provided in Section 6.

Nomenclature

We use the following convention for notation: vectors and matrices are represented in bold characters whereas standard characters are used for scalars (constants, parameters and variables).

A Stackelberg game between the aggregator and the consumers

The coalition containing the set of clients of the aggregator will be denoted G. Its composition and size may vary as functions of the parameters of the problem. The aggregator will share the cost among the members of the coalition, and we assume that a cost-sharing mechanism is chosen in advance [START_REF] Frisk | Cost allocation in collaborative forest transportation[END_REF]. This leads to a Stackelberg game that takes place between the aggregator, acting as the leader, and captive consumers, acting as followers. The game takes place over n ∈ N * days, each day being discretized into T ∈ N * time periods.

The consumer model

We detail now the model of each client i of the aggregator. Each client has two types of loads: a base load that cannot be shifted but needs to be estimated by the consumer in day ahead, and a set of shiftable loads that are scheduled in day ahead depending on their intrinsic characteristics, priority level and aggregator's daily price profile. In this section, we focus exclusively on shiftable loads, the base load mathematical model will be introduced later, in Subsection 3.1.

For each i, we define a set L i containing all his shiftable loads. The set L i is divided into two subsets defining the class of the loads: L i = B i ∪ I i where:

• B i is the set of block loads that cannot be interrupted; they must be scheduled as one block if they are scheduled,

• I i is the set of interruptible loads that can be interrupted but must be fully completed if they are scheduled.

Figure 1 gives a schematic illustration of both these types of loads. Vasirani et al. give examples in [START_REF] Vasirani | Smart Consumer Load Balancing: State of the Art an an Empirical Evaluation in the Spanish Electricity Market[END_REF] of shiftable block loads: dishwashers, washing machines, dryers and of shiftable interruptible loads: electric vehicles, air conditioning, heating. Base load, i.e., loads that cannot be shifted, include fridge, light, oven, micro-wave, toaster, etc. In Figure 1, we provide an illustration of these two types of loads. Each consumer i ∈ G specifies, for each load l ∈ L i , its intrinsic characteristics and a priority level that he shares with the aggregator3 . The set of intrinsic characteristics of load l ∈ L i are the following:

• the earliest time period for the load to start, t i,l ∈ 0; nT -1 ,

• the latest time period for the load to finish4 , t i,l ∈ 0; nT -1 with t i,l ≤ t i,l ,

• the duration of the load µ i,l ∈ 0; nT , with 0 ≤ µ i,l ≤ t i,l -t i,l + 1 which ensures that the number of available time periods between the earliest time periods and the latest time period is enough for the shiftable load to run for its entire duration.

In addition, each load l ∈ L i is run at a power rate (kW) w i,l ∈ R + * , supposed to be constant over each time slot over which the load is activated (see Figure 1). In extension of our work, we can envisage that the consumer has also the possibility to modulate the power rate of his equipments, which would consists in considering continuous load powers but with additional constraints to take into account the fact that block loads must be scheduled over consecutive time-slots. Consumers are asked to associate a priority level k ∈ {1, ..., K} with each of their loads5 ; this information is transmitted to the aggregator [START_REF] Papalexopoulos | Precise Mass-Market Energy Demand Management Through Stochastic Distributed Computing[END_REF]. Consumers should also give a reservation price capturing their willingness-to-pay, for each priority level k, but this information remains private to the consumer and is not transmitted to the aggregator. By definition, the reservation price is the maximum price the consumer is willing to pay per unit of load for each priority level (i.e., each family of loads having the same priority). The reservation price is chosen privately by consumer i for each priority level, and remains constant during all the considered time periods nT . For load l with priority level k i,l , we denote r i (k i,l ) ∈ R + the associated unitary (i.e. per-unit of energy) reservation price. The priority rule defined by consumer i for two loads l i , l i ∈ L i , l i = l i can be formalized as follows: load l i has more priority than load l i (written l i l i ) if r i (k i,li ) ≥ r i (k i,l i ), and the reverse holds if and only if r i (k i,l ) < r i (k i,l ).

Convention is that the highest priority class (class 1 in our case) is associated with an 'almost infinite' reservation price (by comparison with the aggregator and retailer price scales), meaning that the loads having the highest priority level will be scheduled with certainty. A load is scheduled if the generating daily average cost is lower than the daily average cost that the consumer would have been charged if the aggregator had applied the reservation price from the load priority class. This inequality is checked automatically every day by an intelligent device operating in the consumer house without having to reveal the consumer reservation prices to the aggregator. If this inequality is not checked the load is not scheduled, meaning that it is abandoned or canceled out. In that case, at another repetition of the game (for instance, the next day), the consumer has the possibility to adapt his priority levels and the load, which was cancelled out in the previous nT time periods, can be rescheduled provided the associated reservation price is higher than the offered price. To use the classical example of a washing machine, the consumer might indeed decide to cancel out that load on a certain day if the electricity price is too high; the next day, that consumers reservation price for the washing machine may go up since the use of the washing machine becomes more important. Note that we have assumed that each consumer has two categories of loads: the baseline load which cannot be shifted in time and loads that can be shifted in time and are therefore associated with priority levels. So, independently of the consumer's reservation prices, his base load will be scheduled.

For each consumer i, we denote by x i,l (t) the power consumed by load l ∈ L i at time period t, by x i (t) := l∈Li x i,l (t) the aggregated shiftable load at time period t and by

x i := x i (t) nT -1 t=0 the associated load profile. The (shiftable) load profiles x i,l = x i,l (t) nT -1 t=0 , ∀l ∈ L i , ∀i ∈ G constitute
the decision variables of the consumers in the coalition. With these notations, the condition for i to schedule load l is p T x i,l ≤ ri (k i,l )µ i,l w i,l .

The interaction between consumers and the aggregator

The Stackelberg game between the aggregator and the consumers takes place as follows. Aggregator plays the leader role anticipating the consumer rational reaction function, while consumers in the coalition behave as followers [START_REF] Colson | An overview of bilevel optimization[END_REF][START_REF] Dempe | Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks[END_REF][START_REF] Cadre | On the Efficiency of Local Electricity Markets Under Centralized and Decentralized Designs: A Multi-leader Stackelberg Game Analysis[END_REF][START_REF] Cadre | Wind farm portfolio optimization under network capacity constraints[END_REF]. We define Π agg as the net targeted profit of the aggregator, which will be considered as an input for the Stackelberg game together with the coalition G. The timing of the aggregator-consumers game can be described as follows:

(1) the aggregator -leader, at the upper-level (see Figure 2) -determines his price profile over n days to come p = p (t)

nT -1 t=0 so as to reach his net targeted profit Π agg , (2) after observing the aggregator's price profile p , each consumer i ∈ G -follower, at the lowerlevel -chooses his load profile x i,l = x i,l p , r i (k i,l ) , ∀l ∈ L i , so as to schedule the maximum number of loads while minimizing the cost and taking into account constraints imposed by his load intrinsic characteristics and reservation prices.

The Stackelberg game can be repeated for multiple nT time periods. At the end of each nT time periods, each consumer has to decide whether he joins coalition G, or prefers the conventional retailer's offer, by comparing the bill he would have paid with the conventional retailer and the one based on aggregator's price profile p over the past nT time periods. Consumers that were not included in the coalition G in the former nT time periods can be part of it. In Figure 2, a global scheme captures the proposed approach. The constituting elements in the consumers and aggregator blocks (Algorithms 1 and 2) will be detailed later on in the article.

To determine his optimal price profile, the aggregator needs to estimate the consumer reservation prices. This implies that his optimal price profile will depend on his estimates of the consumer reservation prices. Furthermore, depending on the bias introduced by these estimates, the rational reaction function of the consumers as anticipated by the aggregator might not coincide with the load schedule implemented by the consumers knowing the true reservation prices. These discrepancies between the anticipated consumer reaction functions and their realized load schedules might affect the aggregator's coalition dynamics.

At level (2) of the aggregator-consumers game, each consumer i ∈ G solves a simple integer program that in practice can be done by Algorithm 1 below. The algorithm schedules the consumer shiftable loads based on the order of the prices set by the aggregator. Example 1 illustrates the procedure.

Algorithm 1 Load Scheduling Algorithm (Problem (Li)) For each block load l ∈ B i • Choose t * such that t * = arg min τ ∈{t i,l ,t i,l -µ i,l +1} t=τ +µ i,l -1 t=τ p (t). • If t=t * +µ i,l -1 t=t * p (t) ≤ r i (k i,l )µ i,l , then schedule the load on time slots t * , t * + 1, ..., t * + µ i,l -1.
• Otherwise, do not schedule the load.

For each interruptible load l ∈ I i • Order the prices occurring between t i,l and t i,l from the smallest to the highest, and let t 0 , t 1 , ..., t l be the corresponding time slots such that p (t 0 ) ≤ p (t 1 ) ≤ ... ≤ p (t l ).

• If

τ =µ i,l -1 τ =0 p (t τ ) ≤ r i (k i,l )µ i,l
, then schedule the load on time slots t 0 , t 1 , ..., t µ i,l -1 .

• Otherwise, do not schedule the load.

Example 1. We consider two instances with n = 1, T = 144, which represents a day with 10 min time slots [ts], and three priority levels K = 3. Following the priority rule introduced above, load having priority 1 has greater priority than load having priority 2, which itself has greater priority than load having priority 3. Consumer has access to both 'heater' and 'air conditioning', reason for it is that we target in this example large scale consumers, i.e., commercial consumers who have more flexibility than residential consumers. Typical example are large and medium size firms. We can imagine that in parts of their infrastructure they use air conditioning (such as in server rooms, storage warehouses, experimental test rooms, etc.) whereas in the other parts of their infrastructure where employees are present they need to turn on the heater (at least from time to time, the priority level being lower). Consumer i loads are decomposed as follows:

• block loads

-l='dishwasher': k i,l = 1, µ i,l = 12 [ts], t i,l = 36 [ts], t i,l = 126 [ts], w i,l = 0.35kW, -l='washing machine': k i,l = 2, µ i,l = 6 [ts], t i,l = 108 [ts], t i,l = 132 [ts], w i,l = 0.26kW, -l='dryer': k i,l = 3, µ i,l = 3 [ts], t i,l = 132 [ts], t i,l = 144 [ts], w i,l = 0.4kW, • interruptible loads -l='electric vehicle', k i,l = 1, µ i,l = 42 [ts], t i,l = 42 [ts], t i,l = 108 [ts], w i,l = 4kW, -l='air conditioning', k i,l = 3, µ i,l = 36 [ts], t i,l = 0 [ts], t i,l = 144 [ts], w i,l = 1.3kW, -l='heater', k i,l = 2, µ i,l = 48 [ts], t i,l = 0 [ts], t i,l = 144 [ts], w i,l = 3.2kW.
The aggregator's price profile is given in Figure 3(a) in Instance 1 and 3(c) in Instance 2. In this example, the aggregator's price profile is not optimized. It is fixed exogenously, the goal being to test the impact of its shape on the consumer load schedule. In the first instance, consumer i reservation prices for the three priority levels are high compared to the aggregator's price profile p , we set: r i (1) = 100, r i (2) = 20, r i (3) = 15 (e/MWh) in Figure 3(a). We represent consumer i six-load scheduling in Figure 3(b). In the second instance (Figure 3(c)), we lower consumer i second and third priority level reservation prices and set: r i (1) = 100, r i (2) = 10, r i (3) = 5 (e/MWh). The resulting load scheduling is plotted in Figure 3(d). We observe that lower reservation prices imply that some loads such as 'air conditioning' and 'washing machine' are not scheduled.

The aggregator's problem

The aggregator's problem of choosing the price profile p has three components. The first one is the amount of payments received corresponding to the consumers' scheduled and base loads. The second one corresponds to the deviations from the forecast consumption of base loads, as described in Subsection 3.1 below. The third one results from choosing a desired net profit, adding the coalition cost and applying a cost-sharing mechanism to the resulting quantity which is the total income. The aggregator has also to decide for the cost-sharing mechanism (several of which will be described in detail later in Section 5), which determines the target amount paid by each consumer. Roughly speaking, the goal is to choose a non-negative price profile p ≥ 0 so that the following equation holds:

Target amount = Contributions from scheduled loads + Expected deviations from base load. [START_REF] Beaude | Reducing the impact of ev charging operations on the distribution network[END_REF] In what follows we explain the base-load estimation process and how energy excesses and surpluses are accounted for by the aggregator.

Expected deviations from the forecast consumption of base loads

Stochasticity is introduced through the consumer base load, i.e., the demand that cannot be shifted. For consumer i ∈ G, we denote by d i (t) the base load demand observed in real time t ∈ 0; nT -1 and di (t) the estimated demand in day ahead. The consumer base load is modeled as:

d i (t) = di (t) -i (t), ∀i ∈ G, ∀t ∈ 0; nT -1 ,
where the random variable i (t) ∼ f i (0; σ i ) is distributed according to a normal probability density function f i 0; σ i centered in zero and with standard deviation σ i > 0. Furthermore, we assume that the consumer error variables are correlated, which requires to introduce the correlation function: corr i (t), j (t) = ρ i,j , ∀i, j, i = j. Based on historical data of the consumer base load demand, the intelligent device deployed in the consumer's house produces predictions of 24 hour daily demand based on a forecasting algorithm encapsulated within the device. These predictions are reported to the aggregator in day ahead and the consumer will be penalized in real time depending on the deviation between his forecasted and realized demand profiles. Similar assumption was made in [START_REF] Robu | Efficient Buyer Groups with Prediction-Of-Use Electricity Tariffs[END_REF][START_REF] Vasirani | Smart Consumer Load Balancing: State of the Art an an Empirical Evaluation in the Spanish Electricity Market[END_REF][START_REF] Zugno | A bilevel model for electricity retailers' participation in a demand response market environment[END_REF] where each consumer is asked to provide in advance a prediction for his consumption during a specific period and is then charged a Prediction-Of-Use tariff depending on the gap between base load prediction and real consumption. The electrical load forecasting has become more and more important in recent years due to the electricity market deregulation and integration of renewable resources. A number of forecasting methods have been developed in the literature based on neural networks [START_REF] Mandal | A neural network based several-hour-ahead electric load forecasting using similar days approach[END_REF], ensemble methods combining together multiple learning algorithms [START_REF] Lahouar | Day-ahead load forecast using random forest and expert input selection[END_REF], etc.

Using the estimated demands di (t), i ∈ G, the aggregator procures energy in the day-ahead market. We let p f (t) be the day-ahead wholesale market price.

In the balancing, we introduce p + (t), the unit price when excess power must be sold by the aggregator on the balancing at time instant t and p -(t), the unit price when more power must be purchased by the aggregator on the balancing at time period t. According to [START_REF] Saguan | L'architecture de marchés électriques : l'indispensable marché du temps réel[END_REF], the market is designed so that for all time periods t, we have the relation p + (t) < p f (t) < p -(t) which ensures that selling in the balancing a certain amount of power that has been purchased in day ahead cannot generate a profit.

In the balancing, the utility companies are price-takers, i.e., the energy prices p + (t), p -(t) are known ahead of time and exogenous whereas the day-ahead energy price p f (t) and the aggregator's prices p (t) are functions of the aggregator's clients' baseload (as estimated in day ahead).

Consumer i ∈ G is penalized on the basis of the difference between his estimated demand (in the day ahead) and the realization of his demand (in real time) depending on whether he has over estimated or under estimated his demand:

• Demand over estimation: Consumer i forecast is higher than the realization of his demand, i.e., di (t) ≥ d i (t);

• Demand under estimation: Consumer i forecast is smaller than the realization of his demand, i.e., di (t) ≤ d i (t).

Depending on the "aggregated" misestimation of all the consumers, the aggregator must:

• either sell the total excess power bought in the day-ahead market i.e., i∈G ( di (t)d i (t)) + , in the balancing market, at price p + (t);

• or buy the total missing power, i.e., i∈G ( di (t) -d i (t)) -, on the balancing, at price p -(t).

To compensate the loss due to over-buying (because p + (t) < p f (t)), or missing power (because p -(t) > p f (t)), penalties are paid by consumers to the aggregator according to the two cases distinguished previously:

• Demand over estimation: Consumer i is penalized with (p f (t) -p + (t)) >0 di (t) -d i (t) + ; • Demand under estimation: Consumer i is penalized with p -(t) di (t) -d i (t)
-. Note that the aggregator simply transfers the cost of buying the missing power to the consumer in case of demand under estimation.

During the day of delivery, consumer i is required to pay the aggregator an imbalance penalty at every time period t ∈ 0; nT -1 , which is given by:

B i (t) := p -(t) di (t) -d i (t) - + p f (t) -p + (t) di (t) -d i (t) + , = p -(t) i (t) -+ p f (t) -p + (t) i (t) + .
(

) 2
Note that before the actual demand d i (t) is observed, B i (t) is a random variable. Therefore, Equation (1) deals with expected imbalances.

Aggregator's expected profit

The cost of the aggregator at time period t ∈ 0; nT -1 is defined as the sum of the costs resulting from the buying of his positions in day ahead and from the buying of missing power on the balancing minus the revenue resulting from the selling of excess power on the balancing:

c G, t = p f (t) i∈G l∈Li x i,l (t) + di (t) + p -(t) i∈G ( di (t) -d i (t)) - -p + (t) i∈G ( di (t) -d i (t)) + . (3)
Using the demand forecast definition, Equation (3) can be rewritten:

c G, t = p f (t) i∈G l∈Li x i,l (t) + di (t) + p -(t) i∈G i (t) - -p + (t) i∈G i (t) + . (4)
The profit achieved by the aggregator at horizon nT is the sum of his revenue minus his cost. Formally, the aggregator's expected profit Π(p * ) at horizon nT is defined as6 :

Π(p ) := nT -1 t=0 p (t) i∈G l∈Li x i,l (t) + di (t) + i∈G E B i (t) total bill paid by coalition G -E c G, t , (5)
where B i (t) is consumer i imbalance penalty as defined in Equation ( 2) and c(G, t) is the aggregator's cost as defined in Equation (3). We would like the sum of the bills y i paid to the aggregator by each consumer i in the coalition G to be equal to the target income resulting from a desired profit Π agg , i.e., we want to find p such that Π agg = Π(p ). Note that assuming that the coalition cost-sharing mechanism is chosen in advance, the bill paid by consumer i to the aggregator can be expressed as a closed form expression in the aggregator targeted profit Π agg and in the coalition estimated consumption. We will capture these relations as the following system of card(G) equations:

y i - nT -1 t=0 E[B i (t)] = nT -1 t=0 p (t) l∈Li x i,l (t) + di (t) , ∀i ∈ G. (6)
The set of Equations ( 6) can be formulated as a rectangular system in p :

Ap = b, (7)
where:

b i = y i - nT -1 t=0 E[B i (t)], ∀i ∈ G and A i,t = l∈Li x i,l (t) + di (t), ∀i ∈ G, ∀t ∈ 0; nT -1 .
Since the price profile sent as a signal by the aggregator to the consumers has a direct influence on consumer load schedule, it is quite natural to assume that the aggregator forms some 'rational expectation' [START_REF] Cadre | On the Efficiency of Local Electricity Markets Under Centralized and Decentralized Designs: A Multi-leader Stackelberg Game Analysis[END_REF][START_REF] Cadre | Wind farm portfolio optimization under network capacity constraints[END_REF] on the consumers' reaction to his price signal, thus justifying the Stackelberg game modeling of the consumers-aggregator interaction problem. This means that for each consumer i the optimum schedule x i obtained as output of the lower-level problems can be expressed as a function of the aggregator price profile p . To solve these lower-level problems, the aggregator needs to estimate the consumers' reservation prices, therefore forming estimates contained in a vector ri and evaluated in each priority level. The aggregator's price profile will depend on the reservation price estimates. The reaction function that the consumer should implement in response to the aggregator price profile x * i ri , p ( rj ) j∈G might not coincide with x * i r i , p ( rj ) j∈G in the presence of bias in the estimates of the consumer reservation prices. This point will be discussed in more details in Subsection 3.4 dealing with existence and uniqness of the equilibrium solution of the Stackelberg game (U)- (Li).

Since prices must be non negative, at the upper level the aggregator solves the following optimization problem anticipating the rational reaction function of the followers (consumers):

(U) min p A x i i∈G , di (t) nT -1 t=0,i∈G p -b y (x i ) i∈G , ( di (t)) nT -1 t=0,i∈G , s.t. p (t) ≥ 0, ∀t ∈ 0; nT -1 ,
where the dependency between y and x i comes from (6).

Solving the bilevel optimization program

Generally, when one wants to find the equilibrium of a bilevel program, one solves it by backward induction [START_REF] Brotcorne | One-level reformulation of the bilevel Knapsack problem using dynamic programming[END_REF][START_REF] Colson | An overview of bilevel optimization[END_REF][START_REF] Dempe | Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks[END_REF][START_REF] Cadre | On the Efficiency of Local Electricity Markets Under Centralized and Decentralized Designs: A Multi-leader Stackelberg Game Analysis[END_REF][START_REF] Cadre | Wind farm portfolio optimization under network capacity constraints[END_REF]. We start by finding each consumer's rational reaction or response function, i.e., the optimal x i,l l∈Li,i∈G (p ) considering that the aggregator prices are fixed and, then we replace x i,l l∈Li,i∈G by these optimal values in Program (U) and finally we solve this program to find the optimal aggregator prices. The reaction function connects the upper-level (U) with the lower-level (Li) decision variables [START_REF] Sun | A bi-level programming model and solution algorithm for the location of logistics distribution centers[END_REF]. However, in our case, we cannot find a simple closed form expression for the optimal values of x i,l because the lower-level problem (Li) is an integer optimization program.

To solve the aggregator-consumers game, we start by determining the consumer optimal schedule as function of p . The original idea we use to solve the bilevel program in this article is to fix the prices conditions that will lead to a certain x i,l l∈Li,i∈G and then to restrict the search for optimal prices under these conditions so that we are sure that the optimal prices we obtain in the second step of the resolution does not correspond to a different x i,l l∈Li,i∈G .

Since we have a combinatorial finite set of possible values for x i,l l∈Li,i∈G , we can span the whole set of possible prices conditions leading to the corresponding load schedules.

We denote by L s i ⊆ L i the set of loads that are scheduled by consumer i over time horizon nT . Loads in L s i meet the constraint imposed by the reservation prices, i.e.:

p T x i,l ≤ ri (k i,l )µ i,l w i,l , (8)
In Program (Li), the loads in L i that do not meet the constraint imposed by the reservation prices as defined in Equation ( 8) are deleted and therefore, do not belong to L s i . Without loss of generality, we also order the prices 7 . More precisely, we let t 0 , t 1 , ..., t nT -1 be the time periods such that p (t 0 ) ≤ p (t 1 ) ≤ ... ≤ p (t nT -1 ).

Then the prices conditions that lead to a given x i,l l∈Li,i∈G are fully defined by the order of prices and the scheduled loads L s i for each consumer i. This is straightforward when we look at Algorithm 1 which is used to schedule optimally each load l.

To determine the aggregator optimal price profile p , we need to solve optimization problem (U). For a given value of consumer shiftable load schedule (x i ) i∈G , problem (U) is a quadratic program that could be solved with standard-off-the-shelf solvers. However, with such an approach it would be very difficult to gain insights regarding existence and uniqueness of equilibrium for the aggregator-consumers Stackelberg game. For this reason, we introduce a reformulation of optimization problem (U) based on Moore-Penrose pseudo-inverse [START_REF] Rao | Generalized Inverse of Matrices and its Applications[END_REF], as detailed in Appendix A.1.

Existence and uniqueness of solutions of the Stackelberg game

In case of full information on the consumer reservation prices and assuming a strict aggregator price order p (t 0 ) < p (t 1 ) < • • • < p (t nT -1 ), the Stackelberg game (U)-(Li) admits a unique equilibrium, provided it exists. Having no closed form expression for the Stackelberg game equilibrium, the proof is based on Algorithm 1 interpretation:

• if the aggregator price order is strict, Algorithm 1 gives rise to a unique schedule of the consumer loads;

• then, since we reformulate (U) in (U') and then (U") as detailed in Appendix A.1, the optimal aggregator price profile is the one minimizing its norm (U') and such that the sum of the square of the coefficients of deviation from p is minimized as output of optimization problem (U") (to be totally precise, this is done under the invertibility assumption given in Proposition 5).

If the price order is not strict, multiple load schedules might be solutions and we need to consider pessimistic or optimistic approaches [START_REF] Dempe | Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks[END_REF] to select one of them and obtain a unique solution of the Stackelberg game 8 .

More generally, we conclude that:

• an equilibrium might not exist if the aggregator price vector obtained as output of Algorithm 2 does not check the price order imposed at the beginning of Algorithm 1;

• if Algorithm 2 gives rise to different solutions for different price orders, the Stackelberg game may have multiple equilibria.

In case of imperfect information, the values of private information might impact the Stackelberg game equilibrium. As mentioned earlier, the consumer rational reaction function computed by the aggregator under private information on the consumer reservation prices might not coincide with the reaction function that the consumers will implement in practice based on the price signal sent by the aggregator and on their true reservation prices. The bias introduced by the estimates of the consumer reservation prices might give rise to new equilibria for the Stackelberg game.

Learning consumer reservation prices

To solve bilevel optimization problem (U)- (Li), the aggregator needs to estimate the reservation prices associated with each priority level for each consumer. As detailed in the consumer model in Subsection 2.1, each consumer associates a priority level with each of his loads, where the priority level is chosen in a set of K priority levels ordered by decreasing level of priority such that r i (k) > r i (k + 1), ∀k ∈ {1, ..., K -1}. The aggregator estimates give rise to a vector of estimated reservation prices ri for each consumer i.

Example 2. In the two instances considered in Example 1, consumers are asked to associate a priority level with each of their loads. The priority level can be chosen from the highest priority level 1 (red), to the intermediate 2 (orange), to the lowest priority level 3 (green). The priority level associated with each device is communicated to the aggregator thanks to an intelligent device deployed in the consumer's house. Each consumer also defines a reservation price for each priority class, that we have represented in Figure 4 for the two instances of Example 1 with different color shades (darkest shade being for Instance 1 while the lightest one is for Instance 2). Reservation prices remain private information of the consumer and are not shared with the aggregator. Learning consumer private information is a recurrent topic which has generated intense research activities in revenue management and management science literature [START_REF] Den Boer | Dynamic pricing and learning: historical origins, current research and new directions[END_REF]. Besbes and Zeevi [START_REF] Besbes | On the (surprising) sufficiency of linear models for dynamic pricing with demand learning[END_REF] consider the problem of learning a consumer unknown demand curve by pricing dynamically on multiple periods a single product while assuming a linear parametric model for the demand . They prove that the misspecification of the underlying parametric demand model has a limited impact on the revenue loss incurred by the seller. However, it is not straightforward to generalize their result to our paper because we have no explicit closed form expression linking the load schedule and the aggregator price. Other papers [START_REF] Levina | Dynamic pricing with online learning and strategic consumers: an application of the aggregating algorithm[END_REF][START_REF] Shiller | Approximating reservation prices from broad consumer tracking[END_REF] consider that the seller updates dynamically his price to achieve a profit almost as large as if he knew the maximal price each consumer is willing to pay for the product. These problems belong to the more general class of limited-feedback (or partial monitoring) prediction problems [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]. In this section, we want to apply a randomized algorithm from [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] to learn consumer reservation prices evaluated through the minimization of the aggregator's regret.

To that purpose (independently of the priority class), we suppose that consumer i reservation price is associated with a random variable r i which is absolutely continuous, i.e., it admits a probability density function f ri (.) and a cumulative distribution function F ri (.). The elements of the vector of consumer i reservation prices cannot be considered as independent and identically distributed because they are linked by a specific order such that r i (k) > r i (k + 1), ∀k ∈ {1, ..., K -1}. This implies that the ordered vector of reservation prices for consumer i r i admits a density function of the form:

f ri (u 1 , ..., u K ) = K! K j=1 f ri (u j ) if u 1 ≥ ... ≥ u K , 0 otherwise.
We infer the marginal density function associated with consumer i kth priority level:

h ri(k) (u) = K! (k -1)!(K -k)! f ri (u)F ri (u) k-1 1 -F ri (u) K-k , ∀k ∈ {1, ..., K}. (9)
The goal of the aggregator is to achieve a profit almost as large as if he knew the maximal price each consumer is willing to pay for each priority level. Furthermore, assuming that the aggregator price profile p is fixed, the consumer load scheduling problems (Li) are independent of one another.

Thus, if the price offered to consumer i is p ( ri ) and the highest price consumer i is willing to pay is r i , we define the aggregator loss for consumer i as the difference between the profit he earned and the profit he would have earned having full information on consumer i reservation prices [START_REF] Besbes | On the (surprising) sufficiency of linear models for dynamic pricing with demand learning[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Den Boer | Dynamic pricing and learning: historical origins, current research and new directions[END_REF]:

∆( ri , r i ) = Π p (r i , r -i ), x * (r i , p (r i , r -i )) -Π p ( ri , r-i ), x * (r i , p ( ri , r-i )) , (10)
where r -i = (r j ) j∈G,j =i and r-i = ( rj ) j∈G,j =i are the vectors of true and estimated reservation prices of all the consumers in the coalition except i.

The Stackelberg game between the aggregator and the consumers is repeated for a fixed number m of time periods of nT days. While consumers reservation prices are supposed constant, the aggregator has the possibility to update his forecast of the consumers reservation prices at each mnT , m ∈ {1, ..., m} period. We let R ⊂ R + be the finite discrete set containing all the possible values of the reservation price 9 . The goal for the aggregator is to find an algorithm to forecast the consumers reservation prices. A randomized method is here chosen so that the aggregator's regret is minimized regardless of the consumers reservation prices true values, where regret is defined in Equation [START_REF] Dempe | Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks[END_REF] and ri,m is the vector of consumer i estimated reservation prices at round m (corresponding to an horizon of nT time periods):

1 m m m=1 ∆ m (r i,m , r i ) -min r i ∈R K ∆(r i , r i ). ( 11
)
The prediction is with limited feedback because the aggregator does observe neither the consumers true reservation prices nor the losses as described in Equation ( 10) resulting from his estimation or for any other values he might have chosen, because he ignores what the true value of r i is. Instead, the aggregator observes a feedback function which captures whether the daily average cost evaluated in the estimated reservation price is lower than the maximum daily average cost the consumer agrees to pay (i.e., the number of loads that are activated over the total number of loads):

Θ ri , r i = 1 card(L i ) l∈Li 1 p T ( ri)xi,l ri,p ( ri) ≤ri(k i,l )µ i,l w i,l . (12)
Note that the feedack given in ( 12) only depends of consumers individual variables through their number of shiftable appliances card(L i ) and their proportion of effectively schedule appliances (term corresponding to the summation), which is of interest regarding privacy concerns.

Based on [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF], we construct a randomized algorithm which minimizes the aggregator's regret (11) independently of the consumer reservation prices true values. This algorithm requires the computation, for each consumer i in G, of the matrices ∆ i and Θ i that contain the loss function [START_REF] Colson | An overview of bilevel optimization[END_REF] and feedback function [START_REF] Den Boer | Dynamic pricing and learning: historical origins, current research and new directions[END_REF] evaluated in all the possible combinations of values of ri , r i , so card(R) K × card(R) K combinations. These ad-hoc computations are possible because they do not require to know the true reservation price of consumer i. Furthermore, we need to assume that for each consumer i in G, there exists a matrix G such that ∆ i = G i Θ i . Calibration and convergence bounds mathematical derivation are out of the scope of the current paper, more details can be found in [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]. A detailed description of the algorithm can be found in Appendix A.3.

Coalition stability and fairness issues

The aggregator shares his expected cost (evaluated in day ahead) defined in Equation ( 4), among his coalition members to guarantee stability of coalition G with respect to the conventional retailer, and (a certain idea of) fairness.

Regarding the stability aspect, we observe a fundamental difference between the cost with retailer compared to the one in the coalition: while the latter depends on the (endogenous) decisions of consumers -by sharing gains/losses inside the coalition, the former is independent of consumers' decisions (exogenously fixed as a parameter). A path for future research would be to integrate a competitive behaviour of the conventional retailer, whose offer would depend on the pool of consumers choosing it (but in a different manner than a coalition).

At time period t ∈ 0; nT -1 , the conventional retailer price is fixed to p retailer (t) > 0. The cost that consumer i has to pay to the conventional retailer at time period t is defined as follows:

c retailer (i, t) = p retailer (t) d i (t) + l∈Li x i,l (t) . ( 13
)
To optimize his targeted expected profit, the aggregator solves Program (UU) at the top of the bilevel program described in Section 3. The first constraint defines how the cost-allocation captures fairness criteria. The second and third constraints characterize the stability of the cost allocation:

(UU) max Π agg , s.t. y i = ψ i Π agg , j∈G nT -1 t=0
x j (t) + dj (t) , ∀i ∈ G, fairness

1 T y = Π agg + nT -1 t=0 E[c(G, t)], y i ≤ nT -1 t=0 E[c retailer (i, t)], ∀i ∈ G.    stability

Stability issues

There exist several coalitional game models that describe the behavior of agents outside the coalition G. In the definition below, we introduce the notion of γ-game [START_REF] Coló | Quantification du Profit Long-Terme d'un Agrégateur sous Comportement Incertain des Agents[END_REF][START_REF] Hart | Endogenous Formation of Coalitions[END_REF][START_REF] Mochaourab | Coalitional Games in MISO Interference Channels: Epsilon-Core and Coalition Structure Stable Set[END_REF].

Definition 1. A γ-game is a characteristic function game defined for a specific coalition structure considering coalition G and all agents outside G forming single-agent based coalitions. As a result the characteristic function v(.) maps G to a real number v(G) and any agent i ∈ N \ G to a real number v(i).

In our paper, the game follows a γ-model as introduced in Definition 1: the aggregator's clients form a coalition G; all consumers outside the coalition G subscribe to the conventional retailer's offer and build single-player coalitions without direct participation to the market.

The game is with characteristic function v(.) defined as follows:

• v G = Π agg + nT -1 t=0 E c G, t if card(G) ≥ 2
where the aggregator's cost is defined in Equation (4),

• v(i) = nT -1 t=0 E c retailer (i, t) , ∀i ∈ N, where the cost charged by the conventional retailer for consumer i is defined in Equation ( 13).

The game is with Transferable Utility (TU) because the coalitional value Π agg + nT -1 t=0 E c G, t can be divided between the aggregator's clients in any way that the aggregator's clients choose [START_REF] Chalkiadakis | Computational Aspects of Cooperative Game Theory, Synthesis Lectures on Artificial Intelligence and Machine Learning[END_REF].

We introduce the notion of core which characterizes the aggregator's coalition stability [START_REF] Saad | Coalitional Game Theory for Communication Networks[END_REF]. For TU game, the core is defined as the set of allocations y = y i i∈G such that no consumer has an incentive to switch from the aggregator to the conventional retailer [START_REF] Saad | Coalitional Game Theory for Communication Networks[END_REF] at horizon nT .

A cost allocation method that splits the total cost paid by G, i.e., Π agg +

nT -1 t=0 E c G, t , among the participants i ∈ G is said to be efficient or Group Rational (GR), if i∈G y i = Π agg + nT -1 t=0 E c G, t
, where y i is the cost allocated to participant i at horizon nT . A cost allocation is said to be Individual Rational (IR) if no participant pays more than his 'stand alone cost', which is the participant's own cost, when no coalitions are formed [START_REF] Frisk | Cost allocation in collaborative forest transportation[END_REF]. Formally, this property is expressed as:

y i ≤ nT -1 t=0 E c retailer (i, t) , ∀i ∈ G.
The core of the TU game is defined as those cost allocations, y i i∈G , which are solutions of the following linear system of equations:

i∈G y i = Π agg + nT -1 t=0 E c G, t , Group Rational (GR) ( 14
)
y i ≤ nT -1 t=0 E c retailer (i, t) , ∀i ∈ G. Individual Rational (IR) (15)
Equation ( 14) describes Group Rationality (GR) and Equation ( 15) Individual Rationality (IR).

Example 3. In case of uniform allocation between the aggregator's clients, y i is the same for any participant i ∈ G. Using Equation ( 14) of the core definition, we infer that the allocation vector y should check:

y i = Πagg+ nT -1 t=0 E c G,t card G
, ∀i ∈ G. So, for the uniform allocation vector to be in the core, we need to check that:

Π agg ≤ card G nT -1 t=0 E c retailer (i, t) - nT -1
t=0 E c G, t , ∀i ∈ G which can be reformulated as:

Π agg ≤ card G min i∈G nT -1 t=0 E c retailer (i, t) - nT -1 t=0 E c G, t . (16)

Fairness issues

In this section, we introduce a number of economic mechanisms for sharing the expectation of the aggregator's revenue Π agg +

nT -1 t=0 E c G, t among its clients, that all rely on a certain idea of fairness. Other sharing mechanisms, that are out of the scope of our paper, exist such as nucleolus, shadow prices and equal profit methods [START_REF] Frisk | Cost allocation in collaborative forest transportation[END_REF].

The stand-alone cost-sharing

Under the stand-alone cost allocation, the expected cost of the aggregator's coalition is distributed among the participants according to a cost-weighted measure. The energy bill allocated to consumer i takes the following form:

y i = κ i Π agg + nT -1 t=0 E c G, t (17)
where

κ i = nT -1 t=0 E c retailer (i,t) j∈G nT -1 t=0 E c retailer (j,t)
is equal to agent i's share of the total cost charged by the conventional retailer if all the participants in coalition G were clients of the conventional retailer. The weight κ i captures the relative influence of consumer i with respect to the other consumers if they all switch from the aggregator to the conventional retailer at time period nT -1.

Proposition 1. If the aggregator chooses the stand-alone cost as cost-sharing mechanism, the net targeted profit Π * agg solution of Program (UU) is:

Π * agg = j∈G nT -1 t=0 E[c retailer (j, t)] - nT -1 t=0 E[c(G, t)]. (18)
Proof of Proposition 1. GR condition ( 14) is always checked by definition of κ i , i ∈ G because i∈G κ i = 1. For IR condition [START_REF] Fudenberg | The Theory of Learning in Games[END_REF], we need to check:

y i ≤ nT -1 t=0 E[c retailer (i, t)], ∀i ∈ G, ⇔ Π agg ≤ j∈G nT -1 t=0 E[c retailer (j, t)] - nT -1 t=0 E[c(G, t)]. (19)
In Program (UU) the aggregator chooses the largest Π agg that guarantees that the stand-alone allocation remains in the core. Therefore, at the optimum, Inequality (19) should be saturated.

By substituting expressions ( 4) and ( 13) for c(G, t) and c retailer (j, t), respectively, and using the fact that the expected value of the positive part of a Normal(0, σ) distribution is σ/ √ 2π, it follows from [START_REF] Jacquot | Demand Response in the Smart Grid: the Impact of Consumers Temporal Preferences[END_REF] that the aggregator's net targeted profit under stand-alone cost-sharing can be expressed analytically as a function of coalition G content, game parameters and Programs (U) and (Li) decision variables:

Π * agg = i∈G nT -1 t=0 p retailer (t) di (t) + l∈Li x i,l (t) - i∈G nT -1 t=0 p f (t) l∈Li x i,l (t) (20) + di (t) - nT -1 t=0 p -(t) -p + (t) 1 √ 2π i∈G σ 2 i + 2 1≤j<k≤card(G) σ j σ k ρ j,k 1/2
.

Note that for Π * agg to be positive, the retailer's revenue should be larger than coalition G expected cost.

The Shapley value

The Shapley value, also known as Shapley-Shubik power index [START_REF] Chalkiadakis | Computational Aspects of Cooperative Game Theory, Synthesis Lectures on Artificial Intelligence and Machine Learning[END_REF], attributes to each consumer in coalition G an allocation of the coalition cost which is a function of his marginal contribution to the coalition that takes into account the order in which the consumers join the coalition. It is computed under the assumption that the coalition is formed by entering the participants one at a time, taking the average over all the interactions that each consumer can have with other consumers in the coalition.

Formally, the Shapley value associated with consumer i belonging to coalition G is:

y i = g⊂G,i∈g card G -card(g) ! card(g) -1 ! card G ! v(g) -v(g \ {i}) (21)
Let's explain how to compute the Shapley value [START_REF] Saad | Coalitional Game Theory for Communication Networks[END_REF]: the marginal contribution of every consumer

i in a coalition g ⊂ G is v(g) -v(g \ {i}). The weight that is used in front of v(g) -v(g \ {i})
is the probability that consumer i faces the coalition g \ {i} when entering in a random order, i.e., the consumers in front of i are the ones already in g \ {i}. In this context, there are card(g) -1 ! ways of positioning the consumers of g \ {i} at the start of an ordering, and card(G) -card(g) ! ways of positioning the remaining consumers at the end of an ordering. The probability that such an ordering occurs (when all orderings are equally probable) is therefore

card(G)-card(g) ! card(g)-1 ! card G ! .
Consequently the resulting payoff y i in Equation ( 21) is the expected marginal contribution, under random-order joining of the consumers for forming coalition G.

Lemma 1. The Shapley value associated with our TU γ-model game coincides with the uniform allocation described in Example 3, i.e.:

y i = Π agg + nT -1 t=0 E[c(G, t)] card(G) , ∀i ∈ G. (22)
Proof of Lemma 1. Due to the γ-model assumption, consumer i Shapley value introduced in Equation ( 21) can be simplified to give:

y i = 1 card G v(i) -v(∅) =0 + j∈G\{i} 1 (card(G) -1)card(G) v(j ∪ i) =0 -v(i) + 1 card G v G -v G \ {i} = v(G) card(G) = Π agg + nT -1 t=0 E[c(G, t)] card(G) .
Proposition 2. If the aggregator chooses the Shapley value as sharing mechanism, the net targeted profit solution of Program (UU) is:

Π * agg = card(G) min i∈G nT -1 t=0 E[c retailer (i, t)] - nT -1 t=0 E[c(G, t)]. (23)
Proof of Proposition 2. By construction, the Shapley value checks the GR condition ( 14) [START_REF] Chalkiadakis | Computational Aspects of Cooperative Game Theory, Synthesis Lectures on Artificial Intelligence and Machine Learning[END_REF]. For the IR condition [START_REF] Fudenberg | The Theory of Learning in Games[END_REF] to be checked, we need to have:

Π agg ≤ card(G) nT -1 t=0 E[c retailer (i, t)] - nT -1 t=0 E[c(G, t)], ∀i ∈ G, ⇔ Π agg ≤ card(G) min i∈G nT -1 t=0 E[c retailer (i, t)] - nT -1 t=0 E[c(G, t)].
In Program (UU) the aggregator chooses the largest Π agg so that the Shapley value remains in the core which leads to the proposition statement.

A by-product of Lemma 1 and Proposition 2 is that if the aggregator chooses as net targeted profit

Π agg = Π * agg , the corresponding Shapley value y * i = Π * agg + nT -1 t=0 E[c(G,t)] card(G)
, ∀i ∈ G belongs to the core of the game.

Note that for Π * agg to be positive, the retailer's revenue computed assuming that all the consumers consume as much as the lowest consuming consumer10 should be larger than the aggregator's revenue.

If the aggregator chooses the Shapley value as cost-sharing mechanism, card(G) can be expressed as a function of the game parameters and decision variables of Programs (U) and (Li):

card(G) = Π * agg + nT -1 t=0 p f (t) j∈G dj (t) + l∈Lj x j,l (t) + nT -1 t=0 (p -(t) -p + (t)) 1 √ 2π j∈G σ 2 j + 2 1≤j<k≤card(G) σ j σ k ρ j,k 1/2 min i∈G nT -1 t=0 p retailer (t) di (t) + l∈Li x i,l (t) -1 . (24)
Corollary 1. Π * agg solution of Program (UU) is larger under the stand-alone cost than under the Shapley value cost-sharing mechanism.

Proof of Corollary 1. Since card(G) min i∈G {v(i)} ≤ i∈G v(i), we infer from Equations ( 18) and ( 23) that Π * agg is smaller under the Shapley value than under the stand-alone cost-sharing mechanism.

As a result, the stand-alone cost-sharing mechanism is more advantageous for the aggregator than the Shapley value, because it gives rise to a larger net targeted profit for the aggregator. Observe that this is obtained here through calculation; a more intuitive explanation of this result seems complex at first glance (and seems not to be provided in coalition game literature).

The separable and non-separable costs

For any agent i belonging to the coalition G, we introduce the separable cost

m i = nT -1 t=0 E c G, t - E c G {i}, t
. It coincides with the marginal cost of participant i with respect to the coalition G. Methods based on separable and non-separable costs allocate the costs according to:

y i = m i + κ i j∈G κ j ξ G , ∀i ∈ G (25)
The non-separable cost that remains to be distributed is:

ξ G = Π agg + nT -1 t=0 E c(G, t) - j∈G m j (26)
We detail two ways to share the non-separable cost among G participants [START_REF] Frisk | Cost allocation in collaborative forest transportation[END_REF]:

• Equal Charge Method (ECM): κ i = 1 card G , ∀i ∈ G,
• Alternative Cost Avoided Method (ACAM):

κ i = nT -1 t=0 E c retailer (i, t) -m i , ∀i ∈ G
expresses savings that are made for each participant by joining G instead of operating alone. This sharing mechanism only applies when ∀i, κ i = 0. Proposition 3. If the aggregator chooses the separable and non-separable cost-sharing mechanisms, the net targeted profit solution of Program (UU) takes the following form:

Π * agg = min i∈G j∈G κ j κ i nT -1 t=0 E[c retailer (i, t)] - j∈G\{i} nT -1 t=0 E[c(G \ {j}, t)] -1 -card(G) + j∈G κ j κ i nT -1 t=0 E[c(G, t)] . (27)
Proof of Proposition 3. By definition of ξ(G) the separable and non-separable cost checks the GR constraint [START_REF] Frisk | Cost allocation in collaborative forest transportation[END_REF]. For the IR constraint [START_REF] Fudenberg | The Theory of Learning in Games[END_REF] to be checked, we need to have:

m i + κ i j∈G κ j ξ G ≤ nT -1 t=0 E[c retailer (i, t)], ∀i ∈ G, ⇔ nT -1 t=0 E[c(G, t)] - nT -1 t=0 E[c(G \ {i}, t)] + κ i j∈G κ j ξ(G) ≤ nT -1 t=0 E[c retailer (i, t)], ∀i ∈ G, ⇔ nT -1 t=0 E[c(G, t)] 1 + κ i j∈G κ j 1 -card(G) + i∈G\{i} nT -1 t=0 E[c(G \ {j}, t)] - nT -1 t=0 E[c retailer (i, t)] ≤ - κ i j∈G κ j Π agg , ∀i ∈ G. (28)
Multiplying the left and right parts of the last inequality by -j∈G κj κi , we obtain the proposition statement.

Comparison of the cost-sharing mechanisms

We summarize in Table 2 the comparison between the aggregator's net targeted profits Π * agg solutions of Program (UU), for each cost-sharing mechanism.

For a profit-maximizing aggregator, we have proved that:

• if the core is not empty, and the aggregator chooses as net targeted profit Π(p ) = Π * agg distinguished above for the different cost-sharing mechanisms, then all the different allocations belong to the core of the game;

• the Shapley value cost-sharing mechanism coincides with the uniform cost-sharing mechanism which allocates the same part of the coalition cost to each consumer in the coalition;

• the stand-alone cost-sharing mechanism is always preferable to the Shapley value cost-sharing mechanism because the stand-alone cost gives rise to a higher net targeted profit for the aggregator than the Shapley value;

• it is not possible to rank the separable and non-separable cost-sharing mechanism in relation to the Shapley value and the stand-alone cost relying only on the analytical expression of the optimal net targeted profit;

E[c(G \ {j}, t)] -1 -card(G) + j∈G κj κi nT -1 t=0 E[c(G, t)]
Table 2: Comparison of the aggregator's net targeted profit Π * agg for three cost-sharing mechanisms (the standalone cost, the Shapley value, separable and non-separable costs). Π * agg is chosen so that the cost allocation vector y belongs to the core, i.e., checks (GR) and (IR) constraints.

• for the Shapley value, when the aggregator chooses as net targeted profit Π(p ) = Π * agg , the optimal size of his coalition can be determined analytically;

• naturally, if the core of the game is empty, there does not exist any cost-sharing mechanism that guarantees the stability of the aggregator's coalition.

Other comparison elements between the different cost-sharing mechanisms seem difficult to be established; they have been analyzed through numerical simulations.

Impact of the game parameters on the coalition overall benefit

An inadequate allocation of the coalition cost may jeopardize the stability of the coalition, captured through the IR constraint in (UU). Despite positive gains of cooperation in coalition, the cost-sharing mechanisms may not satisfy all the consumers in the coalition, and some consumers may leave the coalition simply because the coalition cost is not adequately shared. This is the drawback of costsharing mechanisms: some might win, whereas some others might lose. This effect will be illustrated in Figures 10,[START_REF] Dempe | Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks[END_REF][START_REF] Den Boer | Dynamic pricing and learning: historical origins, current research and new directions[END_REF] for three cost-sharing mechanisms (the Shapley value, the separable and nonseparable costs, and the stand-alone cost-sharing), where we capture the dynamics of the aggregators coalition on a monthly basis, depending on the net targeted profit fixed by the aggregator.

More generally, it is possible to characterize the benefit brought by the coalition to the consumers as a whole, depending on the net targeted profit fixed by the aggregator and the long-run differences between the balancing prices, for each of the cost-sharing mechanisms introduced in Subsections 5.2.1-5.2.3. To keep the economic interpretations as simple as possible, we assume that all the consumers in the coalition have the same standard deviation, i.e., σ i = σ, ∀i ∈ G and that there is no correlation between the error variables of two consumers in the coalition, i.e., ρ i,j = 0, ∀i, j ∈ G, i = j. In general, any consumer i will stay at time period nT in the aggregator's coalition if, and only if,

y i ≤ nT -1 t=0 E[c retailer (i, t)].
Assuming that consumer i bill is of the generic form

y i = κ i Π agg + nT -1 t=1 E[c(G, t)] ,
and by expanding the expressions for c(G, t) and c retailer (i, t) as done in the derivation of Equation ( 20), we infer that consumer i stays in the aggregator's coalition at time period nT if, and only if:

j∈G nT -1 t=0 p f (t) l∈Lj x j,l (t) + dj (t) + Π agg nT -1 t=0 p retailer (t) di (t) + l∈Li x i,l (t) + σ card(G) 2π nT -1 t=0 p -(t) -p + (t) nT -1 t=0 p retailer (t) di (t) + l∈Li x i,l (t) ≤ 1 κ i . ( 29
)
From Equation [START_REF] Papalexopoulos | Precise Mass-Market Energy Demand Management Through Stochastic Distributed Computing[END_REF], assuming that the equality holds, it is possible to express 1 κi as a linear function of σ. From this definition, if (σ, 1 κi ) belongs to the area located above the line of equation then, consumer i stays with the aggregator at time period nT ; otherwise he leaves and joins the conventional retailer. The corresponding area is depicted in Figure 5 in blue cyan, for a linear function with 3 as director coefficient and a y-intercept value of 50.

Figure 5: Impact of σ and κi on the choice for consumer i to stay with the aggregator. The blue cyan area defined the set of values of (σ, 1 κ i ) for which consumer i stays in the aggregator's coalition at time period nT . We set 3 as director coefficient of the blue cyan area delimitating line and

1 κ i = 50.
Under stand-alone and the Shapley value cost-sharing mechanisms, κ i captures respectively consumer i's share of the total cost charged by the conventional retailer if all the participants in the coalition were clients of the conventional retailer, defined in Equation ( 17), and is equal to 1 card(G) for the Shapley value defined in Equation [START_REF] Levina | Dynamic pricing with online learning and strategic consumers: an application of the aggregating algorithm[END_REF]. Based on Figure 5, the smallest value 1 κi necessary for consumer i to stay with the aggregator at nT is 1

κ i = j∈G nT -1 t=0 p f (t) l∈L j
x j,l (t)+ dj (t) +Πagg nT -1 t=0

p retailer (t) di(t)+ l∈L i x i,l (t)

. If the κ i associated with the stand-alone cost-sharing mechanism is such that κ i > κ i then, consumer i leaves the coalition at time period nT ; otherwise he stays with the aggregator, provided that the difference 1 κi -1 κ i is larger than the second term on the right hand side of Equation [START_REF] Papalexopoulos | Precise Mass-Market Energy Demand Management Through Stochastic Distributed Computing[END_REF]. Interesting interpretations on the impact of Π agg , σ and nT -1 t=0

p -(t) -p + (t) can also be derived:

• if the aggregator is greedy, selecting high values for Π agg , the minimum value of 1 κi necessary for consumer i to stay in the aggregator's coalition ( 1 κ i ) increases;

• the size of the area located above the separating line in blue cyan in Figure 5 is determined by the value of the long-run imbalance price differences nT -1 t=0

p -(t) -p + (t) : the higher, the smaller (the area) and the chances that consumer i stays with the aggregator at time period nT , depending on his σ value; the smaller, the larger (the area) and the chances that consumer i stays with the aggregator at time period nT , depending on his σ value.

• More precise demand forecasts (i.e. smaller σ), with everything else unchanged, will cause more consumers to join the coalition.

Proceeding similarly for the Shapley value (where κ i = 1 card(G) ), we see that consumer i stays in the coalition if the left-hand side of ( 29) is smaller or equal to card(G). A fortiori, this also means that if the Shapley value is implemented as cost-sharing mechanism, the aggregator's coalition needs to not be too large to guarantee that it can be stabilized in the next repetitions of the game.

For the separable and non-separable costs, Equation [START_REF] Papalexopoulos | Precise Mass-Market Energy Demand Management Through Stochastic Distributed Computing[END_REF] needs to be slightly adapted to become:

j∈G nT -1 t=0 p f (t) l∈Lj x j,l (t) + dj (t) + Π agg -j∈G m j nT -1 t=0 p retailer (t) di (t) + l∈Li x i,l (t) + σ card(G) 2π nT -1 t=0 p -(t) -p + (t) nT -1 t=0 p retailer (t) di (t) + l∈Li x i,l (t) ≤ j∈G κ j κ i . (30)
Similarly to the stand-alone and Shapley value cost-sharing mechanisms, when equality holds, it is possible to express j∈G κj κi as a linear function of σ. The area defining the set of values (σ, j∈G κj κi ) for which consumer i stays with the aggregator is located above the line defined by the equality in Equation [START_REF] Rao | Generalized Inverse of Matrices and its Applications[END_REF].

To summarize, the economic benefit of joining the aggregator's coalition is characterized by the aggregator's net targeted profit and long-run differences between the imbalance prices. Whether a coalition participant i loses or wins by joining the aggregator's coalition is characterized by the definition of his standard deviation σ i when estimating his demand and cost-sharing mechanism parameter κ i defined by the aggregator.

Note, furthermore, that non-economic motivation for coalition to emerge might also play a role, such as willingness to go green and become energetically independent, etc. All these effects tend to further stabilize the community.

Non emptiness of the core

Given a set g ⊆ N, let 1 g : N → {0; 1} be the indicator function of the set g, i.e., let 1 g (i) = 1 if i ∈ g and 1 g (i) = 0 if i ∈ N \ g. We introduce the notion of balanced cooperative game in the definition below. Definition 2. A collection of sets G ⊆ 2 N \ {∅} is said to be balanced if there exists a vector (λ g ) g∈G of positive numbers such that: g∈G λ g 1 g (.) = 1 N (.).

The vector (λ g ) g∈G is called the balancing weight system for G.

To check that the core of our TU γ-game is non empty, we rely on the Bondareva-Shapley Theorem, i.e., we need to prove that the TU game is balanced [START_REF] Saad | Coalitional Game Theory for Communication Networks[END_REF] relying on Definition 2 of a balanced cooperative game.

We introduce the (column) vectors λ = λ i i∈G , δ = δ i i∈G) and 1 = 1, ..., 1 is the unitary vector of length card(G).

Proposition 4. The core of the TU game defined by Equations ( 14) and ( 15) is non empty if, and only if for any balancing weight system

λ i ∈ [0; 1], ∀i ∈ G, λ G ∈ [0; 1], it holds that: i∈G λ i δ i ≥ 0, i∈G λ i = 1 -λ G . ( 31
)
where the ith component of the vector δ can be expressed analytically as follows:

δ i = nT -1 t=0 p retailer (t) di (t) + x i (t) - 1 card(G) nT -1 t=0 p f (t) i∈G x i (t) + di (t) + p -(t) -p + (t) 1 √ 2π j∈G σ 2 j + 2 1≤j<k≤card(G) σ j σ k ρ j,k 1/2 - 1 card(G) Π agg , ∀i ∈ G,
where x i is taken identical with the conventional retailer and with the aggregator, as if consumer i would compare what he would have paid under the same consumption profile.

Proof of Proposition 4. We recall that the TU game is balanced [START_REF] Saad | Coalitional Game Theory for Communication Networks[END_REF] if, and only if:

i∈G λ i nT -1 t=0 E c retailer (i, t) + λ G nT -1 t=0 E c G, t + Π agg ≥ nT -1 t=0 E c G, t + Π agg , (32)
for all the collections of weights

λ i i∈G , λ G such that λ i ∈ [0; 1], ∀i ∈ G, λ G ∈ [0; 1] and λ i + λ G = 1, ∀i ∈ G. This last equality is equivalent to: λ G = 1 -λ i , ∀i ∈ G.
By summation over all i ∈ G, we obtain that:

λ G = 1 - 1 card(G)
i∈G λ i . By substitution of this new definition of λ G in Equation ( 32), we infer that the TU game is balanced if, and only if:

i∈G λ i nT -1 t=0 E c retailer (i, t) - 1 card(G) nT -1 t=0 E c G, t + Π agg ≥ 0, ∀i ∈ G, (33)
for all

λ i ∈ [0; 1], ∀i ∈ G such that i∈G λ i = 1 -λ G .
The expectation of the cost paid by consumer i to the conventional retailer defined in Equation ( 13) can be computed analytically:

E c retailer (i, t) = p retailer (t) di (t) + x i (t) . (34)
Similarly, the expectation of the aggregator cost defined in Equation ( 4) can be expressed as a function of the positive part of the sum of the errors of the aggregator's clients. Indeed, by definition any real z ∈ R can be expressed as the linear combination of its positive and negative parts:

z = z + -z -.
For the sum of the errors of the aggregator's client this implies that:

i∈G i (t) - = i∈G i (t) + - i∈G i (t) .
Taking the expectation of this expression, we obtain:

E i∈G i (t) - = E i∈G i (t)
+ since by definition E i∈G i (t) = i∈G E i (t) = 0 (the expectation operator being linear). Using this trick, the expectation of the aggregator cost defined in Equation (4), becomes:

E c G, t = p f (t) i∈G x i (t) + di (t) + p -(t) -p + (t) E i∈G i (t) + . (35)
By substitution of ( 34) and [START_REF] Shiller | Approximating reservation prices from broad consumer tracking[END_REF] in Equation [START_REF] Saad | Coalitional Game Theory for Communication Networks[END_REF], we obtain the expression of the ith component δ i of the left part of Equation [START_REF] Saad | Coalitional Game Theory for Communication Networks[END_REF]:

δ i = nT -1 t=0 p retailer (t) di (t) + x i (t) - 1 card(G) nT -1 t=0 p f (t) i∈G x i (t) + di (t) + p -(t) -p + (t) E j∈G j (t) + - 1 card(G) Π agg , ∀i ∈ G. (36)
According to the Central Limit Theorem, for large enough coalition (i.e., card G → +∞), the Gaussian density function is a good approximation of the distribution of the sum of the error variables [START_REF] Cadre | Wind farm portfolio optimization under network capacity constraints[END_REF]. Furthermore, as assumed in Subsection 3.1, the error variables in G are correlated, which implies that i∈G i (t) ∼ N 0; i∈G σ 2 i + 2 1≤i<j≤card(G) σ i σ j ρ i,j where the correlation can be expressed as a function of the covariance, i.e., ρ i,j = cov i(t), j (t) σiσj

. The expectation of the positive part of the sum of the errors in G can be computed analytically:

E j∈G j (t) + = 1 √ 2π j∈G σ 2 j + 2 1≤j<k≤card(G) σ j σ k ρ j,k 1/2 . ( 37
)
6.2 Impact of the aggregator's net targeted profit on the consumers' bills and aggregator's price profile

In the case study, we assume that the conventional retailer applies a time-of-day tariff such as the Blue / White / Red tariff proposed by EDF [START_REF]Time-of-day tariff comparison[END_REF]. In that case, one unit of kWh costs 0.1595 eduring peak hours and 0.1252 eduring off-peak hours. In Figures 7 (a) and (b), we represent the consumer's bill (y i ) under four cost-sharing mechanisms: the Shapley value, the stand-alone cost-sharing mechanism, separable and non-separable costs (SNS 1 stands for ECM based and SNS 2 stands for ACAP based). The allocation resulting from each costsharing mechanism is compared with the bill that the consumer would have paid if he had chosen the conventional retailer as provider ( nT -1 t=0 E[c retailer (i, t)]). The aggregator's net targeted profit (Π agg ) takes values 10 k for k ∈ 0; 4 in (a) and k ∈ 0; 7 in (c). We observe that the allocations from the cost-sharing mechanisms are rather close and that the consumer's bill is smaller when joining the aggregator than with the conventional retailer for k ≤ 3, and larger for k ≥ 4. So, for Π agg ≤ 10 3 the consumer who wants to minimize his bill, would rather join the aggregator's coalition than the conventional retailer. If the aggregator is too greedy (choosing Π agg ≥ 10 4 ), the consumer has no incentive to join the aggregator's coalition (the energy bill being too high) and contracts with the conventional retailer. We also observe in (b) and (d) that, as expected, the aggregator's price increases as a function of Π agg . The aggregator being profit-maximizer, he will choose Π * agg = 10 3 for any cost-sharing mechanism. However, the optimal size of his coalition cannot be computed analytically relying on analytical results in Table 2, except for the Shapley value. We proved in Lemma 1 that the Shapley value associated with our TU γ-model coincides with the For the stand-alone cost-sharing mechanism, we observe in Figure 12 (a) and (b) that for any Π agg below Π * agg = 599, all the consumers stay with the aggregator, whereas they ultimately leave him at the end of 10 months for any Π agg above this threshold value (whatever value of β is chosen).

Private information impact on the existence and uniqueness of equilibrium for the Stackelberg game

We consider three consumers with three priority levels, reservation prices are similar to the ones introduced in Instance 2 of Example 1 and identical within the consumers, so that r i (1) = 1.00, r i (2) = 0.10, and r i (3) = 0.05 (e/10kWh). Consumers are differentiated on the basis of their standard deviations so that σ 1 = 0.35, σ 2 = 0.30, σ 3 = 0.25. The aggregator optimizes his price profile on a daily basis with hourly time slots with net targeted profit Π * agg = 30 ke. We run Algorithms 1, 2, 3, 4 on a number of rounds m = 10 3 . In Figure 13 (a), we have superposed the consumption daily profiles of the three consumers at the final round mnT . In Figure 13 daily price profile with hourly time slots for two rounds of Algorithm 4 (m = 100 in grey and m = m in purple), i.e., for different evaluations of the reservation prices. We observe that depending on the reservation price estimates:

• Algorithm 2 may fail to converge meaning that no equilibrium is reached.

• if it exists, the solution of Algorithm 2 (x, p ) is unique.

• different price profiles p for the aggregator might be reached at equilibrium depending on the reservation prices estimates.

Conclusion

In this article, we model the relation between an aggregator and consumers joining a coalition to reduce the risk resulting from the unpredictability of their base load demand, as a Stackelberg game formulated as a mathematical bilevel program with private information on the consumers' reservation prices. At the upper-level of the Stackelberg game, the aggregator optimizes his daily price profile so as to reach a net targeted profit which is the maximum value guaranteeing that no consumer will leave the coalition while meeting fairness criterion imposed by the cost-sharing mechanism. At the lowerlevel, the consumers are asked to provide in day ahead an estimate of their base load hourly demand profile and to schedule their shiftable loads depending on the price signal sent by the aggregator. The presence of integer variables at the lower-level of the Stackelberg game prevents us from using mixedcomplementarity constraint reformulations which are classical in the bilevel optimization literature. We provide algorithms that determine the unique price profile and consumer shiftable load schedules as functions of the reservation price estimates. The Stackelberg game between the aggregator and the consumers being repeated for a period of time, the aggregator has the possibility to update his estimates of the reservation prices at several time periods, relying on a feedback function which depends on the shiftable load schedules. A randomized algorithm for consumers' reservation price learning based on regret minimization is provided. The Stackelberg game being repeated for a period of time, the consumers can switch from one energy provider to another. In a case study, we check that there exists a threshold for the aggregator's net targeted profit above which consumers leave his coalition due to the large prices that he applies. Depending on the game parameters, we determine numerically the aggregator's optimal net targeted profit for three cost-sharing mechanisms: the stand-alone cost, separable and non-separable costs (SNS 1 and 2) and the Shapley value. We observe that the consumer inertia in his energy supplier choice process has an impact only on the Shapley value and that the aggregator's coalition size stabilizes in less than 10 months. Furthermore, small differences between the consumers' energy bills are observed between separable and non-separable costs SNS 2 (as well as the stand-alone) cost-sharing mechanism and the Shapley value (as well as the separable and nonseparable costs SNS 1). We prove that in the framework of our model, the Shapley value guarantees a uniform allocation of the coalition cost among the consumers in the coalition.

Figure 1 :

 1 Figure 1: Schematic representation of the two different flexible load profiles considered here: interruptible on the top, versus block on the bottom. Both types of profiles have a fixed power (height w .,l of both profiles) and a fixed duration µ .,l that can be decomposed or not.

Figure 2 :

 2 Figure 2: Global scheme of the proposed approach.

  (a) Aggregator's price profile and reservation prices (1st instance) (b) Scheduled loads, 1st instance (c) Aggregator's price profile and reservation prices (2nd instance) (d) Scheduled loads, 2nd instance

Figure 3 :

 3 Figure 3: Daily load scheduling for two instances: in 3(a) ri(1) = 100, ri(2) = 20, ri(3) = 15 (e/MWh); in 3(c) ri(1) = 100, ri(2) = 10, ri(3) = 5 (e/MWh). The resulting load schedules are represented in Figures 3(b) and 3(d).

Figure 4 :

 4 Figure 4: Consumer's reservation price associated with each priority level. Darkest color shade is for Instance 1 and the lightest for Instance 2 from Example 1.

Figure 7 :

 7 Figure 7: Consumer's energy bill and aggregator's daily price profile p as functions of the aggregator's net targeted profit which takes values 10 k for k ∈ 0; 4 in (a) and (b), and for k ∈ 0; 7 in (c) and (d).

Figure 9 :

 9 Figure 9: Numerical computation of the aggregator's net targeted profit Π * agg for three cost-sharing mechanisms: the stand-alone, the Shapley value and separable and non-separable costs. Each bar chart is associated with a specific value of β, i.e., either β = 0 or β = 0.2.

Figure 10 :

 10 Figure 10: We consider initially 120 consumers and plot the dynamics of coalition G over 10 months for β = 0 and β = 0.2 in (a) under the Shapley value cost-sharing mechanism. We consider four values of Πagg, from the left to the right and top to bottom: 10 3 , 300, 200 and 75. In (b), we plot the coalition size at the end of the 10 months as a function of Πagg.

  10 months. In Figure11(a), we note that for Π agg = 415, all the consumers stay with the aggregator. Increasing the value of Π agg until Π agg = Π * agg = 449, the coalition stabilizes around 113 consumers for β = 0.2 and 110 consumer for β = 0.

Figure 11 :

 11 Figure 11: We consider initially 120 consumers and plot the dynamics of coalition G over 10 months for β = 0 and β = 0.2 in (a) under separable and non-separable costs sharing. We consider four values of Πagg, from the left to the right and top to bottom: 415, 430, 449 and 450. In (b), we plot the coalition size at the end of the 10 months as a function of Πagg.

Figure 12 :

 12 Figure 12: Dynamics of coalition G over 3 months for β = 0 and β = 0.2 in (a) under stand-alone as costsharing mechanism. We consider two values of Πagg: 599 and 600. In (b), we plot the coalition size at the end of the 10 months as a function of Πagg.

Figure 13 :

 13 Figure 13: Final consumer load profile schedule in (a) and aggregator's price profile obtained in (b) evaluated in different estimated values of the reservation prices at round m = 100 and m = m = 10 3 in Algorithm 4.

Nome Law, Online December

2010: http://www.cre.fr/glossaire/loi-nome 2 Support system: green certificates for Flanders, Online January 2018 http://www.vreg.be/en/ support-system-green-certificates

The reporting of the load characteristics and priority levels can be done through an intelligent device like Google Nest https://nest.com/be/fr/ or Sowee https://www.sowee.fr/ deployed by the aggregator in the consumer house.

Note that the convention used here is that if a load has to finish at time t, it can be on at time t for the associated task to be completed "at the end" of this time-slot.

From a user perspective, we believe that it is easier to associate a priority level taken from a limited number of possibilities to a device than a numeric value, which can be quite erroneous depending on the intrinsic preferences and subjective evaluations of the user.

Note that we do not introduce discount factor because the time scale being the month there is no significant variation in the inflation rate.

This is done without loss of generality because there is no "inertia effect" making this order fundamental.

This consists in knowing how consumers will choose between different scheduling solutions of identical cost in(Li), which is not necessary when the scheduling solution of this problem is unique.

Note that we assume in a first approach, that the consumers' reservation prices can take a quantified finite number of values.

This assumption can be interpreted as a lower-bound on the retailer's revenue.

The authors acknowledge the support of the Gaspard Monge Program for Optimization and Operations Research (PGMO).

Case Study

In this section, we test Algorithms 1, 2, 3 and 4 on a large data base containing the historical energy consumption of residential consumers in France. We aim at solving numerically Program (UU) which solution Π * agg relies on the equilibrium of the bilevel optimization program (U)- (Li). Since the aggregator's net targeted profit Π * agg cannot be computed analytically, we resort to numerical illustrations to approximate it. In this section, illustrations are provided to quantify the impact of the aggregator's net targeted profit Π agg on the consumers' energy bills and on the aggregator's price profile in Subsection 6.2. Coalition dynamics is studied in Subsection 6.3. Finally, the impact of private information values on the Stackelberg game equilibrium is analyzed in Subsection 6.4.

Data

We run our algorithm on Eco2Mix database which contains the power consumption of French residential consumers [START_REF]RTE eco2mix database[END_REF]. In Figure 6(a), we represent the aggregated power consumption (in MW) in France for the first two weeks of December 2017 (from December 4 to December 17 2017). As expected, we observe recurrent patterns in the consumers weekly consumption profile. In Figure 6(a), the following color convention is used: the realized consumption appears in brown, the day-ahead forecasted consumption is in blue and the forecast updated in real time appears in black. To disaggregate the global consumption at the individual consumer scale, we use the INSEE database [START_REF] Coló | Quantification du Profit Long-Terme d'un Agrégateur sous Comportement Incertain des Agents[END_REF]45] which details the number of inhabitants in France and how they are distributed per household (depending on the region to which they belong). Consumer i error variable standard deviation σ i and correlation with other consumer error variables (ρ i,j ) j =i are then fitted on Eco2Mix data assuming the difference between the forecasted and the (true) realized demands follows a Gaussian density function. To that purpose, we build the histogram associated with the empirical distribution of the difference between the day-ahead forecasted consumption in blue and the realized consumption in brown evaluated over three consecutive weeks. Using the method of moments, the Gaussian density function parameters are then fitted on the empirical distribution of the error variable captured through the histogram by computing its mean and standard deviation. The market price profile in day ahead and on the balancing are simulated based on RTE market data [START_REF]RTE market data[END_REF]. In Figure 6(b), we represent daily market price profiles in day ahead (blue) and on the balancing (green and red). uniform cost-sharing allocation. Furthermore, taking the point-of-view of the aggregator, the standalone cost-sharing mechanism is always preferable to the Shapley value because it gives rise to a higher net targeted profit for the aggregator. Relying on analytical results in Subsection 5.2.4, we checked that it is impossible to rank the separable and non-separable cost-sharing mechanism in relation to the other cost-sharing mechanisms. So we take an alternative apporach, considering the point of view of the consumers. To that purpose, we compare the consumer's bill under the stand-alone and the separable and non-separable cost-sharing mechanisms (SNS 1 and SNS 2) with the consumer's bill under the Shapley value and plot in Figure 8 the resulting differences as functions of the aggregator's coalition size for a net target profit Π * agg = 10 3 . We observe that the four cost-sharing mechanisms (stand-alone cost, SNS 1, SNS 2, Shapley value) produce rather close consumer's bills. But SNS 2 and stand-alone cost-sharing mechanisms make the largest divergence from the Shapley value, therefore making the largest consumer differentiation.

Numerical computation of Π * agg and dynamics of coalition G

In this subsection, the aggregator-consumers game is repeated for a number m of nT time periods. We represent the consumer choice process as follows: at regular time periods (m -1)nT ; mnT -1 , m ∈ N * , each consumer has to choose his electricity provider between an aggregator and a conventional retailer, while for nT time periods the consumers remain captive of their provider. We introduce a parameter β ∈ [0; 1] capturing the inertia of the consumer [START_REF] Coló | Quantification du Profit Long-Terme d'un Agrégateur sous Comportement Incertain des Agents[END_REF][START_REF] Nasiry | Advance selling when consumers regret[END_REF][START_REF] Zhao | Dynamic pricing in the presence of consumer inertia[END_REF]. Formally, β is the probability that the consumer does not enter the choice process at time period mnT, m ∈ N * .

In Figure 9, we represent the values of Π * agg solution of Program (UU) for three cost-sharing mechanisms: the stand-alone, the Shapley value and separable and non-separable costs. In our numerical experiments, the Stackelberg game between the providers and the consumers is iterated for a period of 10 months. The aggregator's net targeted profit Π * agg that we represent coincides with the numerical value obtained at the end of the 10 months. We also consider two cases for the probability that the consumers enter the choice process: β = 0 meaning that we are in a situation of competition à la Bertrand, i.e., all the consumers enter the choice process, and β = 0.2 meaning that 80% of the consumers enter the choice process. We observe that β has no influence on the stand-alone and separable and non-separable costs-sharing mechanisms, whereas it has a strong impact under the Shapley value.

In Figure 10, we plot the evolution of the coalition size as a function of Π agg , under Shapley value cost-sharing for β = 0 and β = 0.2. We observe that above the threshold values Π * agg = 75 for β = 0 and Π * agg = 200 for β = 0.2, the coalition becomes empty. In addition, for Π agg ≤ Π * agg , we note in Figure 10 (a), that the coalition size stabilizes in around 10 months to 40 consumers for both values of β.

For separable and non-separable cost-sharing mechanisms (SNS 1), we observe in Figure 11 (b) that for both values of β and above Π * agg = 449, the aggregator looses all his clients at the end of the

A Appendix

A.1 Determining the aggregator optimal price profile p

We denote A + the Moore-Penrose pseudo-inverse of matrix A from Equation ( 7), and by p = A + b the Moore-Penrose approximate solution of Equation [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]. We assume that n is so large that card(G) < nT . This implies that the Moore-Penrose solution minimizes the l 2 -norm of p , i.e., it is a solution of the following optimization problem:

There are generally an infinite number of solutions, and the Moore-Penrose is the particular solution whose l 2 -norm p is minimal. The Moore-Penrose solution is one of the solutions of Program (U) in which the non-negativity constraints would have been relaxed. In order to find a solution of Program (U), we need to introduce a method enabling to deviate from this solution while keeping the same value for Ap . We define the Kernel space of matrix A, denoted Ker(A) as follows:

If r is the rank of matrix A, then the Kernel space is a linear vector space with dimension:

Every element in Ker(A) is orthogonal to any element in Im(A), which is a linear span of matrix A columns. Hence, Ker(A) and Im(A) are orthogonal to each other. Thus, any vector p ∈ R nT can be uniquely split into its Image and Kernel space components: p = p Im + p Ker . By definition of A Kernel, we have:

The difference between two possible solutions lies in the amount of Kernel space contribution to the solution. Since Im(A) and Ker(A) are orthogonal to each other, by Pythagora's Theorem:

By definition the Moore-Penrose solution p is the minimum norm solution, i.e., the particular solution that has no Kernel space component.

But p may contain some negative components. As a result, to allow the solution p to deviate from A + b, we need to add a linear combination of elements from the Kernel of A.

For the sake of simplicity, we use the notation D(A) := 1; dim Ker(A) to denote the interval of integers from 1 to dim Ker(A) .

where p Ker,k the k-th Kernel space component of A. The mathematical program defined by Equations [START_REF] Zhang | Competition and Coalition Formation of Renewable Power Producers[END_REF] and ( 39) has a unique solution if, and only if, the square matrix having as coefficient (t, t ) ∈ 0; nT -1 2 , k∈D(A) p Ker,k (t)p Ker,k (t ), is invertible.

Proof of Proposition 5. Let µ ∈ R nT . The Lagrangian associated with the system of Equations ( 38) and ( 39) is:

under the constraint that:

Derivating L(µ) with respect to α k , we obtain:

If there exists t ∈ 0; nT -1 such that µ t > 0, using Constraint (41) we infer that:

p Ker,k (t)p Ker,k = 2p (t), ∀t ∈ 0; nT -1 .

Equation ( 43) can be reformulated as a matricial equation with unknown variables contained in µ.

It admits a unique solution if, and only if, the square matrix k∈D(A) p Ker,k (t)p Ker,k (t )

is invertible. If µ t = 0, ∀t ∈ 0; nT -1 , then using Equation (49) we infer that α k = 0, ∀k ∈ D(A).

To satisfy the non-negativity constraints using the kernel, the program we have to solve to find the aggregator's optimal price profile considering a specific order of prices and set of scheduled loads is the following:

To summarize the steps developed in Subsections 3.3, we compute the aggregator's optimal price profile using the following algorithm:

Algorithm 2 Main Algorithm For each set of scheduled loads and each price order (1) Run the load scheduling Algorithm 1 to find x i for each consumer i ∈ G.

(2) Calculate A x i and y x i .

(3) Calculate the Moore-Penrose pseudo-inverse of A and the associated solution p .

(4) Calculate the Kernel vectors p Ker,k , ∀k ∈ D A .

(5) Solve program (U") to find p x i using the Algorithm 3 described in Appendix A.2.

A.2 Algorithm 3 description

Let µ ∈ R nT be the Lagrangian multipliers associated to constraints (45) and ( 46) and μ ∈ R i∈G card(L s i )

be the Lagragian multipliers associated to constraints (47). Then the Lagrangian associated with Program (U") is:

Derivating L(µ, μ) with respect to α k and stating that this derivative is zero at the optimum, we obtain:

j<nT -1

Then by replacing α k by Equation (49) in the constraints of Program (U"), we obtain the matrix M and the vector d such that the saturated constraints of Program (U") can be written as M µ μ = d.

We detail the analytical expressions of M and d below. In the following expressions, we denote by (j, l) the quantity k<j card(L s k ) + l to simplify the notation of matrix M elements. For all i < nT -1, we have:

• and

p Ker,k (t i ) -p Ker,k (t i+1 ) p Ker,k T x j,l ,

• and d(i) = 2 p (t i ) -p (t i+1 ) .

For i = nT -1, we have:

p Ker,k (t 0 ) p Ker,k (t j ) -p Ker,k (t j+1 ) ,

• and

p Ker,k (t 0 )p Ker,k T x j,l ,

• and d(nT -1) = 2p (t 0 ).

For all i ∈ G and l ∈ L s i , we have:

p Ker,k (t j ) -p Ker,k (t j+1 ) p Ker,k T x i,l ,

• and

p Ker,k (t 0 )p Ker,k T x i,l ,

• ∀j ∈ G, ∀l ∈ L s j , M nT + (i, l), nT + (j, l ) = k∈D(A)

p Ker,k T x i,l p Ker,k T x j,l ,

• and d nT + (i, l) = 2 p T x i,l -r i (k i,l )µ i,l w i,l .

Then solving Program (U") can be done thanks to Algorithm 3 which is based on an efficient checking of Karush-Kuhn-Tucker (KKT) conditions.

Algorithm 3 Solving Program (U")

For each set of indexes Z of Lagrange multipliers equal to zero (starting with the minimum number of zeros and in increasing order)

• Set to zero the corresponding lines and columns of M and d leading to M and d .

• Check if there is a solution to the linear system M µ μ = d .

• If there is no solution, choose another set Z of Lagrange multipliers equal to zero.

• If there is a solution, calculate α k and the resulting prices p with this solution for the Lagrange multipliers and check if these prices verify the constraints of program (U").

If it is the case, these prices are solution of program (U").

A.3 A general forecaster for consumers' reservation price learning

For each consumer i, we introduce matrix of losses ∆ i and feedbacks Θ i which contain card(R) K × card(R) K entries corresponding to the evaluations of loss function [START_REF] Colson | An overview of bilevel optimization[END_REF] and feedback function [START_REF] Den Boer | Dynamic pricing and learning: historical origins, current research and new directions[END_REF] in all possible values of ri , r i ∈ R K . We assume that there exists a matrix G i such that ∆ i = G i Θ i . Matrix ∆ i , G i , Θ i can be computed in an ad-hoc manner because their computations do not require to know the true reservation price of the consumers. We describe in Algorithm 4, the algorithm used by the aggregator to learn the consumers' reservation prices.

Algorithm 4 A General Forecaster For Consumer Reservation Price Learning For each consumer i, define matrix G i so that

Initialization of the learning weights: w 0 = (1, ..., 1) ∈ card(R) K .

For each round m = 1, ..., m

• Draw an estimated reservation price r i ∈ R K based on the pdf:

, ∀r i ∈ R K .

• Compute w r i ,m = w r i ,m-1 exp -γ i ∆i m (r i , r i ) , ∀r i ∈ R K and W i,m = r i ∈R K w r i ,m .

Regret bounds are derived in [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] for γi = ln(card(R) K )

, g * i = max 1, max k,l |G i (k, l)| . We make a similar parameter choice in our simulations. Depending on the learning strategy of the aggregator, other weight updating rules can be envisaged. Fictitious play [START_REF] Fudenberg | The Theory of Learning in Games[END_REF] can be considered as a possible alternative, in that case (50) will be replaced with fr i ,m = 1 m-1 m-1 l=1 fr i ,l and fr i ,1 = (1 -γi ) w r i ,0 Wi,0 + γi card(R) K , ∀r i ∈ R K . Another well-known learning strategy is tit-for-tat [START_REF] Fudenberg | The Theory of Learning in Games[END_REF]. To implement it would require that the consumers react to the aggregator's estimate by updating their reservation price density function and reveal their realized reservation prices at each round m. The forecaster should then 'cooperate' on first round by choosing the reservation price estimate that minimizes his loss for each consumer. Then he should copy the opponents' (consumers) previous move after. Under such a setting, loss and feedback matrix would coincide. However, for the sake of simplicity, we consider throughout the paper that consumers' reservation prices are unchanged and remain private information to the consumers.