domain: info.info-ro qfin math

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

On the Efficiency of Local Electricity Markets Under Decentralized and Centralized Designs: A Multi-leader Stackelberg Game Analysis *

Keywords: Bilevel Mathematical Programming, Complementarity Theory, Electricity Market, Bidding, Price of Anarchy

In this paper, we analytically compare centralized and decentralized market designs involving a national and local market operators, strategic generators having market power and bidding sequentially in local markets, to determine which design is more efficient for the procurement of energy. In the centralized design, used as benchmark, the national market operator optimizes the exchanges between local markets and the generators' block bids. In the decentralized design, generators act as Stackelberg leaders, anticipating the local market prices and the flows on the transmission lines. Clearing of the local markets can be either simultaneous or sequential. The resulting two-stage game with competitive leaders that are not price takers is formulated as a bilevel mathematical programming problem which is reformulated as a Nash-Cournot game, and conditions for existence and uniqueness of market equilibrium are studied. Imperfect information is also considered, resulting from the lack of incentives from the generators to share their RES-based generations. Through a case study, we determine that the decentralized design is as efficient as the centralized one with high share of renewables, using as performance measure the Price of Anarchy, and that imperfect information has a limited impact on the efficiency of the decentralized market design. Furthermore, we check numerically that there exists an upper-limit on the block bid length maximizing the social welfare under both centralized and decentralized designs.

Introduction

The development of Distributed Energy Resources (DERs) may offer new sources of flexibility, which may allow system operators to cost-effectively mitigate the im-pact of variable and unpredictable generation from Renewable Energy Sources (RES). However, contracting DER-based generation in a centralized market structure may complicate market clearing procedures due to the amount and complexity of the bids and the associated coordination requirements between market parties [START_REF] Cadre | On the Efficiency of Electricity Markets[END_REF]. The goal of this article is to compare the efficiency of two market designs for energy procurement with rebalancing: a centralized market, coordinated by a single national Market Operator (MO), and a decentralized market, governed by a number of strategic generators located in local markets, that interact with the national MO.

In a centralized energy market, a coordinating MO contracts at the national level DER directly from DER owners connected to the distribution grid, possibly by the intermediate of an aggregator. Such a centralized market can be formulated as a standard optimization problem under transmission network constraints. On the contrary, in a local market structure, a MO at the local (e.g., distribution) level matches DERbased generation and local demand. In these local markets, generators have market power, i.e., they adjust their quantities, recognizing that they can affect market clearing prices [START_REF] Cardell | Market power and strategic interactions in electricity networks[END_REF][START_REF] Yao | Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network[END_REF]. In this two-settlement model, generators anticipate the national market clearing and behave as local leaders. Interactions between local markets may be managed by a national MO. As a consequence, resources connected to the distribution grid can only be offered to a global (national) market via local markets, taking into account the transmission network constraints. Local generators will be considered as multiple leaders who anticipate the reaction of the national MO who behaves as a follower. Such hierarchical market structures, in which agents have conflicting interest while sharing network constraints belong to the stream of literature called networked Stackelberg competition [START_REF] Bose | The Role of a Market Maker in Networked Cournot Competition[END_REF][START_REF] Borenstein | The competitive effects of transmission capacity in a deregulated electricity industry[END_REF][START_REF] Xu | On the Efficiency of Networked Stackelberg Competition[END_REF]. Failures observed in electricity market competition literature that increase the need for introducing a centralized authority (either a national Market Operator or a regulator) to coordinate the involved agents, do not seem to be specific to the energy sector. Similar observations were made for example in communication networks, and more specifically, in the Internet, where service providers and content providers interact through a jointly shared network infrastructure. In the Internet economy, to avoid failures resulting from service providers' discriminatory behavior, the Network Neutrality principle was introduced to guarantee the equal treatment of all the data streams by service providers [START_REF] Economides | Net Neutrality on the Internet: A Two-sided Market Analysis[END_REF].

In this article, we consider a stylized energy market with rebalancing (i.e., exchanges between the local markets) where the bids take the form of either simple quantity offers or block quantity offers that are subject to inter-temporal constraints [START_REF] Poli | Clearing procedures for day-ahead Italian electricity market: are complex bids really required?[END_REF]. We assume that these inter-temporal constraints are set up so as to define a convex feasible region for the bids, to keep the problem analytically tractable. In actual markets, start up costs, block bids with minimum income requirements, load gradient, exclusive orders, etc. [START_REF] Poli | Clearing procedures for day-ahead Italian electricity market: are complex bids really required?[END_REF][START_REF][END_REF], render the generators' optimization problems highly non-convex and are thus not amenable to an analytical solution.

We also take into account the transmission network through a simplified linear DC power flow model, which represents an approximation of Kirchhoff's laws. This assumption is classical and well-accepted in the electrical engineering literature [START_REF] Chao | A market mechanism for electric power transmission[END_REF][START_REF] Neuhoff | Network-constrained Cournot models of liberalized electricity markets: the devil is in the details[END_REF][START_REF] Purchala | Usefulness of DC power flow for active power flow analysis[END_REF][START_REF] Stoft | Power System Economics: Designing Market for Power[END_REF]. In practice, flows on lines can be calculated using power transfer distribution factor which specifies the proportion of flow on line resulting from an injection of one unit electricity at the corresponding source node and a corresponding one unit withdrawal at some fixed reference node [START_REF] Yao | Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network[END_REF]. Distribution level constraints are ignored in the provision of DER-based generation.

Stackelberg games are hierarchical games involving a leader and a follower. The leader takes the followers' optimal reaction into account when optimizing his strategy.

Such games are traditionally formulated as bilevel optimization problems [START_REF] Colson | An overview of bilevel optimization[END_REF][START_REF] Dempe | Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints[END_REF][START_REF] Dempe | Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks[END_REF][START_REF] Kulkarni | A Shared-Constraint Approach to Multi-Leader Multi-Follower Games, Set-Valued and Variational Analysis[END_REF]. Dedicated reformulations are required to solve these multi-leader follower games [START_REF] Dempe | Is Bilevel Programming a Special Case of a Mathematical Program with Complementarity Constraints?[END_REF]. In a first stream of the literature, such problems are reformulated using the Karush-Kuhn-Tucker conditions for the lower level problems resulting in a Mathematical Program with Complementarity Constraints (MPCC) [START_REF] Dempe | Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints[END_REF][START_REF] Dempe | Is Bilevel Programming a Special Case of a Mathematical Program with Complementarity Constraints?[END_REF][START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF]. However, as pointed out by Dempe and Dutta in [START_REF] Dempe | Is Bilevel Programming a Special Case of a Mathematical Program with Complementarity Constraints?[END_REF], such reformulation may not coincide with solutions of the original Stackelberg game. In the non-convex cases, the Karush-Kuhn-Tucker conditions are not sufficient and MPCC reformulation will result in a much larger feasible set. If the lower-level is a parametric convex optimization problem, well developedapproaches are used to compute local optima that in general do not coincide with equilibrium of the Stackelberg game, unless the Slater's constraint qualification is checked at the lower level [START_REF] Dempe | Is Bilevel Programming a Special Case of a Mathematical Program with Complementarity Constraints?[END_REF]. Another stream of the literature on bilevel programming, reformulates the lower-level problem as a variational inequality [START_REF] Colson | An overview of bilevel optimization[END_REF]. Variational inequalities are mathematical programs that allow the modelling of many equilibrium phenomena encountered for example, in complementarity games in energy [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF]. Mathematical Programs with Equilibrium Constraints (MPECs) may be viewed as bilevel programs where the lower-level problem consists in a variational inequality. Both streams have generated an abundant literature in the community of mathematical bilevel optimization [START_REF] Colson | An overview of bilevel optimization[END_REF][START_REF] Dempe | Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints[END_REF][START_REF] Dempe | Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks[END_REF], and game theory for energy problems [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF].

Equilibrium Problems with Equilibirum Constraints (EPECs) are generalizations of MPECs in which multiple Stackelberg leaders participate in a simultaneous game, the follower taking the strategies of the leaders as given and leaders making decisions subject to the equilibrium conditions arising from the follower lower-level optimization problem [START_REF] Kulkarni | A Shared-Constraint Approach to Multi-Leader Multi-Follower Games, Set-Valued and Variational Analysis[END_REF]. EPEC solving is still considered as a challenging problem in the optimization and game theory communities [START_REF] Kulkarni | A Shared-Constraint Approach to Multi-Leader Multi-Follower Games, Set-Valued and Variational Analysis[END_REF]. However, several applications of multi-leader follower games can be found in the energy literature [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF][START_REF] Neuhoff | Network-constrained Cournot models of liberalized electricity markets: the devil is in the details[END_REF]. In [START_REF] Cadre | Wind Farm Portfolio Optimization[END_REF], we provided a game theoretic based representation of suppliers that interact in geographic demand markets, organized as two-tiered systems. Assuming rational expectation of the agents with respect to the outcome of the real-time market, existence and uniqueness of subgame perfect Nash equilibrium are investigated. Strategic behaviors of the agents have also been considered in [START_REF] Vaya | Optimal Bidding Strategy of a Plug-in Electric Vehicle Aggregator in Day-ahead Electricity Markets[END_REF][START_REF] Ruiz | Pool Strategy of a Producer With Endogenous Formation of Locational Marginal Prices[END_REF]. In these papers, the authors considered respectively a strategic power producer and an aggregator that bid into the day-ahead electricity market with the objective to maximize their profit and minimize charging costs respectively, while anticipating the market clearing, behavior and data of rival producers and consumers. In [START_REF] Neuhoff | Network-constrained Cournot models of liberalized electricity markets: the devil is in the details[END_REF], Neuhoff et al. provide a very complete review of numerical models of transmission-constrained electricity markets. In Cambridge II and Madrid models, an integrated transmission and energy market is introduced [START_REF] Barquin | Cournot equilibrium computation on electricity networks, 2-nd International workshop on liberalization and modernization of power systems, congestion management problems[END_REF][START_REF] Cardell | Market power and strategic interactions in electricity networks[END_REF][START_REF] Ehrenmann | A comparison of electricity market designs in networks[END_REF] where leaders are not price takers: each Stackelberg leader (strategic generator) anticipates what happens to locational marginal prices, as well as flows on the transmission lines. This is strongly related to the formulation that we present in this paper, except that we do not consider fringe generation and that we introduce sequential bidding which complexifies the computation of market equilibrium. Furthermore, we propose an analytical approach to derive conditions for existence and uniqueness of market equilibria, that can be seen as complementarity to the numerical models introduced in [START_REF] Neuhoff | Network-constrained Cournot models of liberalized electricity markets: the devil is in the details[END_REF].

In this paper, we propose an analysis of a multi-leader Stackelberg game under generator market power and convex cost functions. We bring contributions to the existing literature according to three aspects that we detail below:

(i) a first contribution relies on the formal proofs of the efficiency of decentralized energy markets compared to the classical centralized energy market which maximizes social welfare, and on the effect of sequential bidding, when generators have market power and are not price takers.

(ii) a second contribution is related to the inclusion of imperfect information in the two-settlement market model.

(iii) a third contribution is an analytical comparison of sequential versus simultaneous local market clearing.

The article is organized as follows. We start by introducing the model in Section 2, i.e., the network model in Subsection 2.1, the agents and the utility functions in Subsections 2.2 and 2.3 respectively, and the solution concepts that will be used throughout the article in Subsection 2.4. Then we provide a mathematical model for centralized and decentralized market designs in Subsections 3.1 and 3.2. We characterize analytically the existence and uniqueness of solutions in each of these market designs in Subsection 3.3, and quantify the efficiency of decentralized markets (cleared either simultaneously or sequentially) with high shares of renewables, with respect to the centralized market design using the Price of Anarchy as performance measure (Subsection 4.1). Finally, a case study is provided in Section 4 to quantify the impact of the share of renewables on the Price of Anarchy and on the existence of subgame perfect Nash equilibrium for the decentralized market design, taking into account intertemporal constraints. A last numerical illustration opens the discussion towards the necessity to find a trade-off between increasing bid complexity and guaranteeing the efficiency of the market operation.

Notation

To uniformize the notations, vectors and matrices will be denoted by bold characters.

Agents

Network model

We consider a power network with n nodes (also called buses in electrical engineering) labeled {1, ..., n} and l edges (lines). Each node will be associated with a local market.

The line flows are related to the nodal power injections through Kirchhoff's laws. The national Market Operator (MO) controls the exchanges between local market nodes r(t) and the corresponding locational marginal prices are either fixed by the national MO in case where a centralized market is implemented, or by local MOs in case where a decentralized market holds. The exchanges between local market nodes r(t) must satisfy the network feasibility constraints, that is, the resulting power flows should not exceed the transmission line capacity f in both directions. We model the transmission network through a simplified linear DC power flow model, which represents an approximation of Kirchhoff's laws. This assumption is classical and well-accepted in the electrical engineering literature [START_REF] Chao | A market mechanism for electric power transmission[END_REF][START_REF] Neuhoff | Network-constrained Cournot models of liberalized electricity markets: the devil is in the details[END_REF][START_REF] Purchala | Usefulness of DC power flow for active power flow analysis[END_REF][START_REF] Stoft | Power System Economics: Designing Market for Power[END_REF]. In practice, flows on transmission lines can be calculated using power transfer distribution factor which specifies the proportion of flow on one line resulting from an injection of unit electricity at the corresponding source node and a corresponding one unit withdrawal at some fixed reference node [START_REF] Yao | Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network[END_REF]. In our network model, distribution level constraints are ignored in the provision of DER-based generation. On top of that, because we do not consider storage in this paper, the demand and generation must be balanced at every time period, implying that all exchanges between local market nodes must sum up to zero.

Formally, all these constraints are captured through the injection region X that we define below:

X := x ∈ R n | -f ≤ Hx ≤ f , 1 T x = 0 , (1)
where the matrix H is known as the shift-factor matrix that depends on the admittances of the transmission lines of the power network [START_REF] California | Shift Factors: Methodology and Example, CAISO Market Operations[END_REF]. The transmission capacities of the lines are given by f ∈ R l + [START_REF] Yao | Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network[END_REF].

Agents

We consider a local networked market that is cleared at each time period t ∈ {0, ..., tH -1} over a finite time horizon tH ∈ N * , the local MO taking into account local network constraints, and on which conventional generators, consumers and renewable producers interact. The local MO reports the cleared quantities to the national MO who is responsible for the operation of the global (national) market. We consider quantity offers that are bidded on the energy market and take the form of (linked) block bids, i.e., length tH vectors subject to inter-temporal constraints that are accepted in full. In the EU Power Exchange context, generators have the possibility to submit a certain interval of consecutive hours where they are willing to produce [START_REF]Regulation of the Power Sector[END_REF]. In our paper, these inter-temporal constraints are set up so as to define a convex feasible region for the bids, the goal being to keep the problem analytically tractable to obtain closed form expressions for market equilibrium. In Section 4 we will quantify the impact of parametrizations of the feasible set on the existence of market equilibrium. These aspects have already been pointed out in [START_REF] Borenstein | The competitive effects of transmission capacity in a deregulated electricity industry[END_REF][START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF], as well as the fact that mixed strategy equilibria exist where pure strategy ones might not. In actual markets, start up costs, block bids with minimum income requirements, load gradient, exclusive orders, etc. [START_REF] Poli | Clearing procedures for day-ahead Italian electricity market: are complex bids really required?[END_REF][START_REF][END_REF], render the generators' optimization problems highly non-convex and are thus generally not amenable to an analytical solution. An alternative is to use simple bids, which does not require to introduce inter-temporal constraints. But, taking an operational perspective, this means that, for instance, the offers of one thermal generating unit could be accepted in the 3-rd, 5-th, and 7th periods, leading to a unit schedule which could be highly uneconomical or simply infeasible from the technical perspective. The simple idea behind the introduction of inter-temporal constraints is to introduce as few complex constraints as possible in the bid, so as not to complicate the matching process in excess while at the same time removing the huge risk at which agents are exposed with simple bids. So inter-temporal constraints in the bids may capture a mixed effect of actual operational constraints (start up costs, ramping constraints) and cost components.

We introduce the definition of a bijective application, which will be used to define admissible inter-temporal constraints on the block bids: Definition 1. The application Φ : R t H + → R m is bijective if, and only if, ∀y ∈ R m , there exists a unique q ∈ R t H + such that Φ(q) = y.

We now describe in more details the various categories of agents that interact in the market place:

• Local Market Operator (MO): in each local market node k ∈ {1, ..., n} and at each time period t ∈ {0, ..., tH -1}, there is a local MO that clears the local market which is composed of one aggregated conventional (nuclear, gas, coal, etc.) generator G k , one aggregated renewable producer and consumers.

• Conventional generators: G k submits a quantity offer qk ∈ R t H + and incurs a production cost

t H -1 t=0 c k q k (t)
for qk, where the cost function c k : R+ → R+ is assumed to be continuously differentiable, strictly increasing, and convex with c k (0) = 0. The block bids of the generators are subject to inter-temporal constraints Φ(qk) ≤ 0 where Φ : R t H + → R m is continuous, bijective following Definition 1 and increasing in qk and m ∈ N * is the number of inter-temporal constraints that are considered.

• Renewable producers: local MOs may also have RES-based generation in their portfolio, and take it into account when clearing the local markets. We assume a zero marginal cost for the RES-based generation and let ŵk (t), be the estimated RES-based generation in market k ∈ {1, ..., n} node, at time period t ∈ {0, ..., tH -1}.

• Consumers: we assume that the aggregated consumption in each local market node k is represented with an inverse demand function p k : R+ → R+ that specifies how much the aggregate consumer is willing to pay to consume one more unit of electrical energy. d k (t) is the aggregated demand in market node k ∈ {1, ..., n}, at time period t. The consumer inverse demand function p k (.) is assumed to be twice continuously differentiable, strictly decreasing, and concave, i.e., p k (.) < 0 and p k (.) ≤ 0. We assume a linear relation between price and aggregated demand leading to:

p k d k (t) = a k -b k d k (t), (2)
for some a k > 0 and b k ≥ 0.

Regarding the use of local renewable production, two cases are possible:

(i) d k (t) < ŵk (t) + q k (t)
there is a surplus of power which is bought by the local MO on the local market and submitted to the national MO on the global market,

(ii) d k (t) ≥ ŵk (t) + q k (t)
there is a lack of power that needs to be bought by the local MO.

Conventional and renewable generators will be aggregated in a single portfolio, in each local market.

• National Market Operator (MO): the global (national) MO determines the exchanges between different market nodes r(t) ∈ X n . Note that for all k ∈ {1, ..., n}, -r k (t) denotes the net injection into market node k, at time period t. These exchanges are determined according to a market mechanism that maximizes the social welfare while guaranteeing supply and demand balance in each market node. Exchanges, r(t), are constrained by the available transmission capacity between the market nodes.

Timing of the game and utility functions of the agents

Demand and supply balance at each node k ∈ {1, ..., n} and each time period t ∈ {0, ..., tH -1} implies that:

d k (t) = q k (t) + ŵk (t) + r k (t), (3)
which implies in turn that

p k d k (t) = p k q k (t) + ŵk (t) + r k (t)
. We model a nodal pricing mechanism which properly rewards DERs. Exchanges between local markets are only coming from consumers. The national MO plays on it by changing the price so that consumers change how much they buy/consume. This is similar as the approach introduced in [START_REF] Yao | Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network[END_REF] where the demand side is price taking with elastic demand functions subject to quantity shifts in each local market 1 . Depending on the market design, the strategic interactions between the agents is either modeled as a standard constrained optimization problem (centralized market) or as a Stackelberg game (decentralized market). The Stackelberg game takes place as follows:

1) each conventional generator G k , k ∈ {1, ..., n} chooses independently and simultaneously his block bid qk to maximize his profit, anticipating the sequence of local market clearing prices and exchanges between local market nodes.

2) at each time period t ∈ {0, ..., tH -1}, each local MO clears the local market and announces the price p k q k (t) + ŵk (t) + r k (t) to the conventional generator G k and the consumers. Subsequently, the central MO chooses the exchanges between markets, r(t), that maximize the global social welfare.

With decentralized market design, the prices at different locations can differ. This setting follows the locational marginal pricing approach [START_REF] Papavasiliou | Analysis of Distribution Locational Marginal Prices[END_REF], used commonly in the US system 2 , and strongly related to Yao et al. formulation in [START_REF] Yao | Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network[END_REF].

With the centralized market design, we assume that there is no anticipation at the generators' side on the exchanges between local markets and that the national MO optimizes simultaneously the production quantities (qk) k=1,...,n and the exchanges between local markets r(t)

t H -1 t=0
in order to maximize the social welfare.

We now detail the utility functions of the agents involved in the Stackelberg game. At time period t ∈ {0, ..., tH -1}, the conventional generator G k is paid according to the locational marginal price p k q k (t) + ŵk (t) + r k (t) . We define the profit of G k at t 1 Other approaches exist: in lots of markets, exchanges between local markets come from generators within a real-time market (US), or is separately contracted (EU).

2 By comparison, the EU system relies on zonal pricing, i.e., there is a unique market price per zone [START_REF] Smeers | Generalized Nash Equilibrium and Market Coupling in the European Power System[END_REF]. The delimitation of the zones, which may contain multiple nodes, is a difficult problem.

as the difference between the revenue generated by the selling of q k (t) units at market price p k (t) and the cost of these units production:

πG k q k (t), q-k(t), r(t), ŵ(t) = q k (t)p k q k (t) + ŵk (t) + r k (t) -c k q k (t) . (4)
Assuming a zero marginal cost for the production of renewable energy, the profit of the renewable producer in local market k at time period t is defined as the revenue generated from the selling of ŵk (t) at market price p k (t):

πk q k (t), q-k(t), r(t), ŵ(t) = ŵk (t)p k q k (t) + ŵk (t) + r k (t) . (5)
The national MO profit function is the following:

πMO q(t), r(t), ŵ(t) = k=1,...,n r k (t)p k q k (t) + ŵk (t) + r k (t) . (6)
The national MO's objective coincides with social welfare maximization, which is defined as the maximization of the sum of the surplus of consumers and generators (here, conventional and renewable generators) and the national MO's profit:

SW q(t), r(t), ŵ(t) = n k=1 q k (t)+ ŵk (t)+r k (t) 0 p k (u)du -p k q k (t) + ŵk (t) + r k (t) du local market k consumer surplus + ŵk (t)p k q k (t) + ŵk (t) + r k (t) + q k (t)p k q k (t) + ŵk (t) + r k (t) -c k q k (t) + k=1,...,n r k (t)p k q k (t) + ŵk (t) + r k (t) , = n k=1 q k (t)+ ŵk (t)+r k (t) 0 p k (u)du -c k q k (t) . (7)

Solution concepts

The goal of this section is to formally introduce game theoretical solution concepts that will be used throughout the article. We start by introducing the notion of strategy and strategy profile.

Definition 2. [25]

The strategy set of generators G k , k ∈ {1, ..., n}, is the set of actions (block bids) qk ∈ R t H that check the constraints defining the generator's feasible set. Similarly, the strategy set of the national MO is the set of exchanges r(t)

t H -1 t=0 ∈
X t H that check the demand and generation balance equation.

The first solution concept that we define ignores the sequential structure of the game; it treats the strategies as choices that are made once and for all before play begins. We assume that the exchanges between the local markets, r, is fixed.

Definition 3. [25]

A Nash equilibrium (for the Nash-Cournot game occurring between the generators) is a strategy profile q (t)

t H -1 t=0 such that for every generator G k , k ∈ {1, ..., n} t H -1 t=0 πG k q k (t), q -k (t), r(t), ŵ(t) ≥ t H -1 t=0 πG k q k (t), q -k (t), r(t), ŵ(t) ,
for all qk in generator G k 's strategy set.

Stackelberg games are two-stage games involving multiple leaders (generators) and a follower (the national MO). In the literature, they are often assimilated with EPEC [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF]. Two-stage games can be modeled as extensive form games3 . A subgame is part of this extensive form game that constitutes a valid extensive form game on its own. In a perfect information extensive form game, every action of the agents (generators or national MO) initializes a subgame [START_REF] Osborne | A Course in Game Theory[END_REF]. This enables us to introduce the definition of a subgame perfect Nash equilibrium.

Definition 4. [25]

A subgame perfect Nash equilibrium is a strategy profile q , r for which for any history h (i.e., generators' actions, or sequence of actions of generators and national MO) the strategy profile q , r | h is a Nash equilibrium of the subgame induced by h.

Since the whole game is a subgame, every subgame perfect Nash equilibrium is a Nash equilibrium. Subgame perfect Nash equilibrium can be found using simple algorithm known as backward induction [START_REF] Schwalbe | Zermelo and the Early History of Game Theory[END_REF].

Mathematical programming formulation

The two market designs described in Section 1, can be modeled as mathematical programs that we detail in Subsection 3.1 (centralized market design) and 3.2 (decentralized market design). Proofs for the existence and uniqueness of market equilibrium for the decentralized market design are provided in Subsection 3.3. Finally, an analytical comparison of sequential versus simultaneous market clearing is provided in Subsection 3.4.

A standard optimization problem for the centralized market

With the centralized market design, we assume that the national MO simultaneously balances supply and demand by optimizing exchanges, r k (t), between local markets k ∈ {1, ..., n} such that demand at node k receives a quantity d k (t) = q k (t) + ŵk (t) + r k (t), and optimizes the quantities produced by the conventional generators under nonnegativity and inter-temporal constraints. The centralized market is here modeled as a one-level standard optimization problem under constraints on the quantity bids (nonnegativity, inter-temporality) and r(t) belongs to the injection region X defined in Equation ( 1) at any time period t ∈ {0, ..., tH -1}:

max (q(t)) t H -1 t=0 ,(r(t)) t H -1 t=0 t H -1 t=0
SW q(t), r(t), ŵ(t) , s.t. q k (t) ≥ 0, ∀t = 0, ..., tH -1, ∀k = 1, ..., n,

Φ(qk) ≤ 0, ∀k = 1, ..., n,
where Φ : R t H → R m is continuous, bijective following Definition 1 and m ∈ N * is the number of inter-temporal constraints that we consider for the block bids.

A bilevel mathematical program for local markets

With the decentralized market design, the national MO optimizes only the exchanges between the local markets to guarantee that the aggregated supply and demand balance in each local market. Conventional generators declare simultaneously and independently quantity offers (block bids) in the local market 4 . The local market is modeled as a Stackelberg game where generators (G k ) k=1,...,n act as leaders with the national MO as a follower. It is therefore formulated as a bilevel mathematical programming problem, where generators bid in their local market to maximize their profits, subject to inter-temporal constraints on the block quantity offers, while anticipating the outcome of the national market clearing. Bilevel problems are challenging to solve because they are generally non-convex [START_REF] Dempe | Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints[END_REF].

The variables are divided into two classes, namely the lower-level variables r(t) ∈ X , ∀t ∈ {0, ..., tH -1}, which determine the exchanges between the local markets at time period t, and the upper-level variables qk ∈ R t H , ∀k = 1, ..., n, which capture the sequences of simple bids made by the generators. Mathematical programs (8), ( 9), [START_REF] Economides | Net Neutrality on the Internet: A Two-sided Market Analysis[END_REF] and [START_REF] Ehrenmann | A comparison of electricity market designs in networks[END_REF], [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF] are connected through the use of common variables, namely the sequence of exchanges between the local markets over time horizon tH , r(t)

t H -1 t=0
. Also, the profits of the generators in Equation ( 8) cannot be computed until the sequences of exchanges, r(t)

t H -1 t=0
, between the local markets are known. These exchanges are not in the direct control of the generators, but the solution of a mathematical program parametrized in the generators' bids q(t)

t H -1 t=0 .
Formally, for all k = 1, ..., n, the bilevel optimization problem writes down as follows:

for all k = 1, ..., n, max

q k ∈R t H ,(r(t)) t H -1 t=0 ∈X t H t H -1 t=0 πG k q k (t), q-k(t), r(t), ŵ(t) , (8)
s.t. q k (t) ≥ 0, ∀t ∈ {0, ..., tH -1}, (9)
Φ(qk) ≤ 0.

for all t = 0, ..., tH -1,

r(t) = arg max r (t)∈X SW q(t), r (t), ŵ(t) , (11)
s.t. n k=1 r k (t) = 0. ( 12
)
As classical in bilevel optimization [START_REF] Colson | An overview of bilevel optimization[END_REF][START_REF] Dempe | Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints[END_REF], the lower-level problem in Equations ( 11) and ( 12) is nested within the upper-level problem described by Equations ( 8)- [START_REF] Economides | Net Neutrality on the Internet: A Two-sided Market Analysis[END_REF]. The lower-level problem describes a setting where the national MO optimizes consumption only, and is strongly related to Yao et al. [START_REF] Yao | Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network[END_REF] formulation of the Cournot problem, but differs from it because their Cournot players cannot affect the price difference between buses.

At the upper-level, Equation ( 9) imposes non-negativity of the bid quantity submitted by G k in local market node k and Equation ( 10) captures the inter-temporality constraints associated with bid qk. At the lower-level, Equation ( 12) captures the fact that the sum of the exchanges between local markets, r(t) ∈ X , vanishes at each time period t ∈ {0, ..., tH -1}, by definition of the set X introduced in Equation (1). Equation ( 12) can easily be reformulated as an equation which represents demand and supply equilibrium, i.e., n k=1 q k (t) + n k=1 ŵk (t) = n k=1 d k (t), ∀t ∈ {0, ..., tH -1}. Furthermore, note that there is a temporal scale difference between the upper and the lower level: while G k defines block bids over time period {0, ..., tH -1}, the national MO re-optimizes the exchanges between local markets at each time period t ∈ {0, ..., tH -1}.

Solving the bilevel mathematical program

The inverse demand function p k : R+ → R is linear (a fortiori concave) and strictly decreasing in q k . Hence p -1 k :] -∞; a k ] → R+ is well-defined and shares the same properties as p k . We introduce the function D :] -∞, max k=1,...,n a k ] → R+ such that:

D(x) := n k=1 p -1 k (x). ( 13
)
For D to be well-defined and striclty decreasing and concave (as the sum of such functions), we make the assumption that the price intercepts are identical i.e., a k = a, ∀k = 1, ..., n. Under this assumption, we can properly introduce the inverse demand function D -1 : R+ →] -∞; a] which is strictly decreasing and concave.

Proposition 1. For simple bids, the equilibrium q ( ŵ), r ( ŵ) solution of the Stackelberg game described by Equations ( 8), ( 9), ( 10), ( 11), ( 12) coincides with the social welfare optimum of a Cournot game between the n conventional generators.

Proof of Proposition 1. For the sake of simplicity in this proof we omit the t index since for simple bids we consider solely one time period. We start by computing the reaction function ρ(.) solution of the lower-level optimization problem that checks demand and supply balance, i.e.:

d(q, ŵ) = q + ŵ + ρ(q) r . ( 14
)
Making change of variable in the lower-level problem, i.e., replacing the decision variable r by d, Equations ( 11) and ( 12) can be re-written:

max d∈R n + n k=1 d k 0 p k (u)du -c k (q k ) , (15)
s.t. n k=1 d k = n k=1 q k + n k=1 ŵk . (16)
Note that

d k 0 p k (u)du = d k 0 (a -b k u)du = (a -b k 2 d k )d k .
Hence the objective function in Equation ( 15) is strictly concave. This implies that the lower-level equivalent problem described by Equations ( 15) and ( 16) admits a unique solution d (q, ŵ). In turn, this implies that there exists a unique reaction function ρ (.) solution of Equation [START_REF] Karamardian | The Complementarity Problem[END_REF].

We now introduce the Lagrangian function associated with Equations ( 15) and ( 16):

L(d, λ) = n k=1 d k 0 p k (u)du -c k (q k ) + λ n k=1 d k - n k=1 q k - n k=1 ŵk ,
where λ ∈ R is the Lagrange multiplier associated with lower-level constraint [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF].

Differentiating L(d, λ) with respect to d k , we obtain:

∂L(d, λ) ∂d k = 0 ⇔ λ = p k (d k ), ⇔ p -1 k (λ) = d k . ( 17
)
By summation over k = 1, ..., n and definition of the market demand introduced in Equation ( 13), we obtain: D(λ) = n k=1 d k . Using Equation ( 16), it can be rewritten: D(λ) = n k=1 q k + n k=1 ŵk . From which we infer:

λ = D -1 ( n k=1 q k + n k=1 ŵk ). ( 18
)
By substitution of Equation [START_REF] Cadre | On the Efficiency of Electricity Markets[END_REF] in Equation ( 17), we obtain:

d k (q, ŵ) = p -1 k D -1 (1 T q + 1 T ŵ) . (19)
From which we infer the reaction function closed form expression: ρ (q, ŵ) = d (q, ŵ) -qŵ.

The space of definition of r in the lower-level problem ( 11)-( 12) imposes that:

ρ (q, ŵ) ∈ X ⇔ n k=1 ρ (q k , ŵ) = 0, -f ≤ Hρ (q, ŵ) ≤ f .
This means that for a solution q, ρ (q, ŵ) to be feasible in the upper-level problem, the generators need to select q that check (9), [START_REF] Economides | Net Neutrality on the Internet: A Two-sided Market Analysis[END_REF] and -f ≤ Hρ (q, ŵ) ≤ f , the constraint n k=1 ρ (q k , ŵ) = 0 being automatically checked through Equation ( 16). In practice, we will assume that a generator will always presumes that the transmission network constraints remain non-binding (e.g., they are not saturated) when calculating the subgame perfect Nash equilibrium output 5 . If the anticipated constraints coincide with the realized constraints then the belief of the generators is consistent, and the algorithm converges to an equilibrium; otherwise oscillations might appear [START_REF] Neuhoff | Network-constrained Cournot models of liberalized electricity markets: the devil is in the details[END_REF].

We now substitute the reaction function ρ (.) in the upper-level optimization problem objective function:

πG k q k , q-k, ρ (q, ŵ), ŵ = p k d k (q, ŵ) q k -c k (q k ), = D -1 1 T q-k + q k + 1 T ŵ q k -c k (q k ), ( 20
)
using Equation [START_REF] Cadre | Wind Farm Portfolio Optimization[END_REF]. We observe that Equation (20) becomes independent of the lower-level reaction function ρ (q, ŵ). As a result, an equilibrium of the Stackelberg game (a subgame perfect Nash equilibrium following Definition 4) is also an equilibrium of a corresponding Cournot game involving the n conventional generators and D -1 1 T q-k + q k + 1 T ŵ as inverse demand function.

An important by-product of this result is that there is no difference between local market prices. Also, note that in case where the cost function of the generators is quadratic (i.e., c k (q k ) = c k q 2 k , c k > 0, ∀k ∈ {1, ..., n}), each conventional generator which is producing more energy makes the profit of all the other conventional generators lower since the market price is decreasing as a function of the total production.

We now introduce an intermediate result on the generators' profit functions.

Lemma 1. The generator G k 's profit function πG k q k , q-k, ρ (q, ŵ), ŵ is twice continuously differentiable and strictly concave with respect to own output q k .

Proof of Lemma 1. For the sake of simplicity we set Q := 1 T q-k + q k + 1 T ŵ. We mentioned above that the inverse market demand function D -1 (.) is concave and strictly decreasing with respect to q k which implies that

∂ 2 D -1 (Q) ∂q 2 k < 0 and ∂D -1 (Q)
∂q k < 0 respectively. Differentiating twice πG k with respect to q k , we obtain:

∂ 2 π G k q k ,q -k ,ρ (q), ŵ ∂q 2 k = q k ∂ 2 D -1 (Q) ∂q 2 k <0 +2 ∂D -1 (Q) ∂q k <0 - ∂ 2 c k (q k ) ∂q 2 k >0
< 0, which implies that πG k (.) is striclty concave with respect to q k . Proposition 2. For simple bids, we prove that the Stackelberg game described by Equations ( 8), ( 9), ( 10), ( 11), ( 12) is equivalent to a non linear Complementarity Problem.

Proof of Proposition 2. Considering simple bids means that there is no intertemporal constraints, i.e., Φ(.) ≡ 0. It is well-known that the set of Cournot-Nash equilibria is the same as the set of simultaneous solutions of the first-order optimality conditions of the n individual generators' problems [START_REF] Szidarovsky | A new proof of the existence and uniqueness of the Cournot equilibrium[END_REF]:

Ψ k (q, ŵ) : = ∂πG k q k , q-k, ρ (q, ŵ), ŵ ∂q k = ∂D -1 (Q) ∂q k q k + D -1 (Q) -c k (q k ) ≥ 0, q k ∂πG k q k , q-k, ρ (q, ŵ), ŵ ∂q k = 0, q k ≥ 0.
This system of equations can be reformulated as a non linear Complementarity Problem CP (R n + , Ψ):

Ψ q, ŵ ≥ 0,

q T Ψ q, ŵ = 0, q ≥ 0,
where we set Ψ q, ŵ := Ψ1 q, ŵ , ..., Ψn q, ŵ . The generators' objective functions πG k q k , q-k, ρ (q, ŵ), ŵ being twice continuously differentiable and striclty concave with respect to q k for all k ∈ {1, ..., n} according to Lemma 1, Kolstad and Mathiesen proved in [START_REF] Kolstad | Computing Cournot-Nash Equilibria[END_REF] that finding a Nash-Cournot equilibrium q is equivalent to find q ∈ CP (R n + , Ψ).

We now try to generalize this result in case where inter-temporal constraints hold, i.e., Φ(.) ≡ 0. Let introduce the set

K := q ∈ R n + |Φ(q k ) ≤ 0, ∀k ∈ {1, ..., n} . (21)
K is a subset of R n . First, we check that K = Φ -1 ] -∞; 0] m is closed as reciprocal image of a closed subset of R m through a continuous application. By definition, K is a bounded subset of R n . Since compacts in R n are in general the closed and bounded subsets, we have proved that K is compact in R n + . We now prove some properties of the Ψ vector.

Lemma 2. ∇Ψ is an Hadamard matrix if, and only if

c k (q k ) > (n -3) 1 n l=1 1 b l , ∀k ∈ {1, ..., n}. (22)
Proof of Lemma 2. By definition

p k (Q) = a k -b k Q ⇔ Q = a k b k -1 b k p k (Q), ∀k ∈ {1, ..., n}. Substituting p -1 k (Q) in Q we obtain p -1 k (Q) = a k b k -1 b k Q. Then using the definition of the demand function D(Q) = n k=1 p -1 k (Q), we infer that D(Q) = ( n k=1 a k b k ) -( n k=1 1 b k )Q.
Using the same principle, we infer that:

D -1 (Q) = n k=1 a k b k n k=1 1 b k A - 1 n k=1 1 b k B Q.
Differentiating D -1 (Q) with respect to q k , we obtain ∂D -1 (Q)

∂q k = -B, ∂ 2 D -1 (Q) ∂q 2 k = 0, ∀k ∈ {1, ..., n}.
For ∇Ψ to be an Hadamard matrix we need to check the row strictly diagonally dominance condition, i.e.,

| ∂ 2 ∂q 2 k D -1 (Q)q k + 2 ∂ ∂q k D -1 (Q) -c k (q k )| > n l=1,l =k | ∂ 2 ∂q l ∂q k D -1 (Q)q k + ∂ ∂q l D -1 (Q)| ⇔ 2B + c k (q k ) > (n -1)B, ⇔ c k (q k ) > (n -3)B.
We now come to the more general result below Proposition 3. The Stackelberg game described by Equations ( 8), ( 9), ( 10), ( 11), ( 12) admits a unique equilibrium provided Equation ( 22) holds.

Proof of Proposition 3. We checked in Lemma 1 that each generator G k profit function is twice differentiable and striclty concave with respect to q k , and in Lemma 2 that ∇Ψ is an Hadamard matrix if, and only if, Equation ( 22) is checked. Then following Moré and Rheinbold in [START_REF] Moré | On P-and S-functions and Related Classes of n-dimensional Nonlinear Mappings[END_REF], there exists at most one solution to CP (R n + , Ψ). This would prove the uniqueness of q . We now deal with existence.

Let q ∈ R n + \ K, then there exist at least one k ∈ {1, ..., n} such that Φ(q k ) > 0 ⇔ q k > Φ -1 (0) if Φ -1 is monotonically increasing. We build a vector y ∈ R n + such that y k < Φ -1 (0) for all k ∈ {1, ..., n} such that q k > Φ -1 (0) and for the remaining k, choose

y k = q k . Then (q -y) T Ψ(q, ŵ) = k∈{1,...,n}|q k >Φ -1 (0) (q k -y k ) ∂π G k (q, ŵ) ∂q k > 0 by
definition of q and construction of y. The same construction can be transposed to the case where Φ is monotonically decreasing. In that case, for all the k ∈ {1, ..., n} such that Φ(q k ) > 0, we choose y k = q k , and for the remaining ones, we choose y k < Φ -1 (0).

Following [START_REF] Karamardian | The Complementarity Problem[END_REF] this proves that if Equation ( 22) is checked, there exists a unique Cournot-Nash equilibrium for the non-cooperative game between the generators, that we call q ( ŵ).

The precedent steps lead us to the conclusion that there exists a unique equilibrium q ( ŵ), ρ (q , ŵ) solution of the Stackelberg game described by Equations ( 8), ( 9), [START_REF] Economides | Net Neutrality on the Internet: A Two-sided Market Analysis[END_REF], [START_REF] Ehrenmann | A comparison of electricity market designs in networks[END_REF], [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF]. Proposition 4. For block bids, there exists a unique equilibrium (q ( ŵ(t), t)

) t H -1 t=0 , (r ( ŵ(t), t)) t H -1 t=0
solution of the Stackelberg game, provided Equation ( 22) is checked at each time period t ∈ {0, ..., tH -1}.

Proof of Proposition 4. We proceed by extension of Proposition 1 proof. The continuity and strict concavity of t H -1 t=0 πG k q k (t), q-k(t), r(t), ŵ(t) is straightforward as the sum of functions having this property. In Proposition 1 proof, the case where there is no inter-temporal constraint is straightforward to extend to block bids since the upper-level problem in Equations ( 8), ( 9) can be decomposed in independent problems over the temporal space 0, ..., tH -1. In case where inter-temporal constraints are introduced, Lemma 2 can be extended to prove that ∇Ψ q(t), ŵ(t) is an Hadamard matrix at any time period t ∈ {0, ..., tH -1}. The end of the proof is straightforward to transpose to block bids by observing that K n := (qk) n k=1 ∈ R nt H + |Φ(qk) ≤ 0, ∀k ∈ {1, ..., n} = k=1,...,n Φ -1 ] -∞; 0] m is closed as the product of closed sets, and that (q -y) T Ψ q, ŵ = t H -1 t=0 q(t) -y(t)

T Ψ q(t), ŵ(t) . Then, following the same procedure as above, it is possible to construct vectors y(t) ∈ R n + such that q(t) -y(t) T Ψ q(t), ŵ(t) > 0, ∀t ∈ {0, ..., tH -1}.

We have proved that the Stackelberg game between n generators located in local markets and a national MO admits a unique equilibrium under mild assumptions.

Sequential local market clearing

In the previous section, the conventional generators optimize their quantity bids simultaneously and independently, and the local markets are cleared simultaneously by the national MO. Another market design can be envisaged in which the local markets are cleared sequentially by the national MO. Without loss of generalities, we assume that local market k has lower priority than local market k + 1 for any k = 1, ..., n -1, in the sequential clearing, and that the cost functions are quadratic in the quantity produced, leading to c k (q k ) = c k q 2 k , ∀k = 1, ..., n. To solve the local market optimization sequentially, we have to decompose the upper-level problem in n sequential optimization problems that will be solved proceeding by backward induction, i.e., starting with the lowest priority local market. The lower-level problem remains the same and the reaction function ρ (q) coincides with the one obtained in case of simultaneous local market clearing. We checked in Lemma 2 proof that it is possible to write the inverse demand function as , assuming that there exists at least one k ∈ {1, ..., n} such that b k > 0. Differentiating the conventional generator G1 (lowest priority local market) profit function with respect to q1 we obtain:

D -1 (Q) = A -BQ
∂πG 1 q1, q-1, ρ (q), ŵ ∂q1 = A -B(q1 + Q) -2c1q1 = 0, ⇔ A -BQ = (B + 2c1)q1. (23)
For any k = 2, ..., n, by substitution of Equation ( 23) in any G k profit function, we obtain:

πG k q k , q-k, ρ (q), ŵ = (A -BQ)q k -c k q 2 k , = (B + 2c1)q1q k -c k q 2 k .
Then differentiating πG k with respect to q k we obtain:

∂πG k q k , q-k, ρ (q), ŵ ∂q k = (B + 2c1)q1 -2c k q k = 0, ⇔ (B + 2c1)q1 2c k = q k , ∀k = 2, ..., n. (24)
Proposition 5. Assuming that all the local markets are cleared sequentially, the optimal quantity bidded by the generator in the lowest priority local market is smaller than the optimal bid obtained when all the local markets are cleared simultaneously.

Proof of Proposition 5. Using Equation [START_REF] Nisan | Algorithmic Game Theory[END_REF] we infer that Q = q1+ n k=2 B+2c 1 2c k q1+ n k=1 ŵk . By substitution in Equation ( 23), we infer that (B + 2c1)q1 = A -B q1

+ n k=2 B+2c 1 2c k q1 + n k=1 ŵk which is equivalent with: 2B + 2c1 + B(B + 2c1) n k=2 1 2c k q1 = A -B n k=1 ŵk . (25)
If local markets are cleared simultaneously we have

q k = B+2c 1 B+2c k q1, ∀k = 2, ..., n. Hence Q = (B +2c1) n k=2 1 B+2c k q1 +q1 + n k=1 ŵk .
Using the relation (B +2c1)q1 = A-BQ we infer that:

2B + 2c1 + B(B + 2c1) n k=2 1 B + 2c k q1 = A -B n k=1 ŵk . (26)
Using the definition of B, we conclude that the left part of Equation ( 26) is smaller than the left part of Equation ( 25).

There is no straightforward generalization of Proposition 5 to local markets with higher priority than 1, and related results could only be derived numerically.

Note that Proposition 5 does not imply a last-mover advantage [START_REF] Lieberman | First-Mover Advantages[END_REF] in general because πG 1 (q 1 , q -1 , ŵ) = (1 -BQ)(q 1 ) 2 -c1(q 1 ) 2 = (B + c1) >0 (q 1 ) 2 using the fact that A -BQ = (B + 2c1)q 1 , which holds both under simultaneous and sequential local market clearing. Proposition 5 implying that the lowest priority generator G1's optimal bid is lower under sequential market clearing than under simultaneous, G1's profit function, πG 1 (q 1 , q -1 , ŵ) recalled just above, is smaller under sequential market clearing than under simultaneous market clearing. However, in Subsection 4.3.2 case study, we check numerically that sequential market clearing gives rise to a higher social welfare (as defined in Equation ( 11)) than simultaneous market clearing. Based on social welfare definition in Equation [START_REF] Dempe | Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints[END_REF], this implies that sequential local market clearing may be more profitable to other agents (generators and MOs in local markets with higher priority than 1, renewable producers, consumers) than simultaneous local market clearing.

Case study

We consider two market nodes interconnected by a single transmission line. Each generator has a quadratic cost function, i.e., c k (q k ) = c k q 2 k , ∀k = 1, 2. Furthermore c2 > c1 > 0 and r1 = -r2 = r.

Quantifying efficiency

The Price of Anarchy (PoA) is defined as the ratio between the optimal social welfare and that of the worst value of an equilibrium [START_REF] Koutsoupias | Worst-case equilibria[END_REF][START_REF] Cadre | On the Efficiency of Electricity Markets[END_REF][START_REF] Nisan | Algorithmic Game Theory[END_REF]:

P oA( ŵ) := max q∈R nt H + ,r∈X nt H SW(q, r, ŵ) SW q , ρ(q ), ŵ . ( 27
)
The PoA is a measure of the efficiency loss when introducing anticipatory behavior from the generators located in local markets, compared with the centralized market design (where no anticipatory behavior holds). By definition, the PoA is always larger than 1 and the efficiency loss is minimal when the PoA approaches 1 [START_REF] Cadre | On the Efficiency of Electricity Markets[END_REF].

Computing solutions for centralized and decentralized market designs

In the proposed case study, the social welfare can be expressed analytically as:

SW(q, r, ŵ) = k=1,2 a k (q k + r k + ŵk ) - b k 2 (q k + r k + ŵk ) 2 -c k q 2 k . (28)
Using Equation ( 28), we derive closed form expressions of solutions for the centralized market optimization problem given in Subsection 3.1 and Stackelberg game decribed in Equations ( 8)-( 12).

Centralized market

In the centralized market organization, the national MO determines simultaneously the quantities produced by the generators (q c k ) k=1,2 and the exchanges between nodes r c . Differentiating the social welfare function in Equation ( 28) with respect to each of these variables, we obtain a linear system of equations in q c 1 , q c 2 , r c which admits a unique solution:

∂SW(q, r, ŵ) ∂q k | q k =q c k = 0 ⇔ q c k = a k -b k r c -b k ŵk b k + 2c k , ∀k = 1, 2,
∂SW(q, r, ŵ)

∂r |r=rc = 0 ⇔ r c = a1 + a2 -b1q c 1 -b1 ŵ1 -b2q c 2 -b2 ŵ2 b1 + b2 .
This is a linear system of equations that can be rewritten matricially as follows:

  b1 + 2c1 0 b1 0 b2 + 2c2 b2 b1 b2 b1 + b2     q c 1 q c 2 r c   =   a1 -b1 ŵ1 a2 -b2 ŵ2 (a1 + a2) -b1 ŵ1 -b2 ŵ2   .
Since the discriminant of the system matrix is positive (2b1b2c1+2b1b2c2+4b1c1c2+ 4b2c1c2 > 0) because of the assumptions made on the parameters, the system admits a unique solution that can be expressed analytically:

q c 1 ( ŵ) = a1b2c2 -a2b1c2 -b1b2c2 ŵ1 + b1b2c2 ŵ2 b1b2c1 + b1b2c2 + 2b1c1c2 + 2b2c1c2 , q c 2 ( ŵ) = -a1b2c1 + a2b1c1 + b1b2c1 ŵ1 -b1b2c1 ŵ2 b1b2c1 + b1b2c2 + 2b1c1c2 + 2b2c1c2 , r c ( ŵ) = a1b2c1 + 2a1c1c2 + a2b1c2 + 2a2c1c2 -b1b2c1 ŵ1 -b1b2c2 ŵ2 -2b1c1c2 ŵ1 -2b2c1c2 ŵ2 b1b2c1 + b1b2c2 + 2b1c1c2 + 2b2c1c2 -1
.

Finally, we discuss the impact of inter-temporal constraints on the existence of an equilibrium and prove numerically that there exists an optimal upper-limit on the generators' bid length in Subsection 4.3.4.

Impact of RES-based generation, transmission and local market capacity constraints

In this subsection, we quantify numerically the impact of RES-based generation on the efficiency of decentralized market design, using the PoA as performance measure.

Then, we focus on the analysis of the impact of transmission line and local market capacity limits, on the existence of an equilibrium for the decentralized market design.

Impact of RES-based generation on the efficiency of the decentralized market design: We want to quantify the impact of RES-based generation, ŵ1 and ŵ2, on the PoA, assuming that the local markets are cleared simultaneously. The parameters are set as follows a1 = a2 = 8, b1 = 0.3, b2 = 0.7, c1 = 10, c2 = 20. In Figure 1, we have represented the PoA as a function of local RES-based generations. We observe that the PoA always remains in the range of values [1; 1.025] and is exactly 1 in case where RES-based generation is the highest. This means that efficiency loss caused by the introduction of anticipatory behavior is the smallest for high shares of renewables. In other words, the decentralized market design output coincides with the centralized market design output when the total RES-based generation is high. A possible interpretation is that the increase of RES-based generation implies a decrease of the market price and, a fortiori, a decrease in the conventional generators' bids (that are linear in D -1 (Q) under simultaneous market clearing). Such a situation implies less ability for conventional generators to affect pricing outcomes. These results may be in favor of fully-decentralized market designs, i.e., peer-to-peer energy trading, were no national MO is involved and local MOs/generators trade bilaterally energy with one another [START_REF] Matamoros | Microgrids Energy Trading in Islanding Mode[END_REF], for high penetration of renewables.

Impact of transmission line finite capacity and local market capacity constraints:

We now assume that there is a single transmission line that interconnects the local market nodes, with a finite capacity. We want to check to what extent line capacity constraint might prevent the emergence of an equilibrium [START_REF] Borenstein | The competitive effects of transmission capacity in a deregulated electricity industry[END_REF][START_REF] Xu | On the Efficiency of Networked Stackelberg Competition[END_REF]. Such effects have already been studied using a game theoretical approach in [START_REF] Borenstein | The competitive effects of transmission capacity in a deregulated electricity industry[END_REF]. Borenstein et al. proved that there is an impact of capacity of transmission lines on the degree to which generators in different locations compete with one another. They demonstrated that there is a threshold level of capacity, above which two otherwise isolated markets are effectively merged. In case where the line capacity is below this threshold, they proved analytically that line capacity has a clear effect on the output of both generators: increases in the line capacity cause a monotonic decline in the expected market price and monotonic increase in expected quantities produced up to the point that the unconstrained market equilibrium is reached. Assuming that transmission capacity holds, the set X includes a constraint of the form -f ≤ h1r1 + h2r2 ≤ f . The shift-factor vector H depends on the admittances of the transmission line. We set the reactance to the line to 2.10 -3 and the bus admittance matrix is 1000 -1000 -1000 1000 .

Following [START_REF] California | Shift Factors: Methodology and Example, CAISO Market Operations[END_REF], this implies that the associated shift-factor vector is H = 1 0 assuming power flow is in the direction from bus 1 to 2 and bus 2 is the reference. In Figure 2, we have represented Hr c in (a) and Hr in (b), i.e., the local market exchanges evaluated in the optimum (centralized design) and in the equilibrium (decentralized design), as functions of RES-based generation on the local markets, ŵ1 and ŵ2. If we choose the line transmission capacity so that f = 5, the set of ( ŵ1, ŵ2) ∈ R 2 + for which there exists an equilibrium is the subspace of R 2 + located between the two dot magenta lines. We observe that the existence of solutions for the centralized optimization problem and bilevel mathematical programming problem depends on parametrizations (here, the RES-based generations).

In addition, we assume that capacity constraints hold in each local market node, i.e., q k ≤ qk , ∀k = 1, 2 where qk > 0 is the maximum production capacity available at node k. In Figure 3 (a), we have plotted q 1 ( ŵ1, ŵ2), q 2 ( ŵ1, ŵ2) as functions of ŵ1 and ŵ2. In Figure 3 (b) we have represented q as a function of ŵ1 and ŵ2 taking into account the finite capacity link constraint (0 ≤ r ≤ 5) already represented in Figure 2 and local market capacity constraints with q1 = q2 = 0.19. The magenta area delineates the set of ŵ1 and ŵ2 for which equilibrium exists.

Based on these numerical illustrations, we observe that equilibrium satisfying finite transmission line capacity and local market capacity constraints might exist only for high RES shares. Otherwise, unstable behaviors will be observed which would be in favor of a more centralized design.

Simultaneous versus sequential market clearing

In this subsection, we assume the the local market 1 has lower priority than the local market 2, which implies that M O2 announces his clearing price p2(.) before M O1, who will announce p1(.) later. We observe in Figure 4 that the optimal simple bid of the generator in local market 1 is inferior under sequential market clearing than under simultaneous market clearing, for any value of RES-based generation, ŵ1, ŵ2. This observation coincides with the result obtained in Proposition 5. In local market 2, the reverse relation holds, i.e., the optimal bid under simultaneous market clearing is lower than the optimal bid under sequential market clearing for ŵ1 ≤ 9.5, ∀ ŵ2 ≤ 10 and for ŵ1 ≥ 9.5, ŵ2 ≤ 5. But for ŵ1 ≥ 9.5 and ŵ2 ≥ 5, the optimal bid for the generator in local market 2 is larger under simultaneous market clearing than under sequential market clearing. This numerical result illustrates that incentives for the generator in the highest priority market to bid higher quantities under simultaneous market clearing than under sequential is highly dependent on the RES-based generation.

Impact of imperfect information

To compute the closed form expressions of the optimal bids of each generator as introduced in Subsection 4.2, generators should share their (estimated) RES-based generation with all the market operators (both local and national) and the other generators, something for which they might have no a priori incentives. To check whether (RES-based generation) information sharing might be profitable for the generators, we assume that each local MO k , k = 1, 2, makes the estimate that ξ k ŵl , l = 1, 2, l = k, renewable power is produced on the other local market, with ξ k ≥ 0 a distortion factor. Note that ξ k = 1 means that full information is disclosed, which implies that MO k correctly guesses the RES-based generation on local market l = 1, 2, l = k. We have represented in Figure 5, the PoA as a function of the distortion factors for both simultaneous and sequential market clearings, assuming that the estimated RES-based generation on each local market are set so that ŵ1 = 8 and ŵ2 = 10. Furthermore, we assume that under centralized market design, perfect information holds, i.e., local market RES-based generations are common knowledge. We observe in Figure 5 that for distortion factors smaller than 3, imperfect information has a limited impact on the PoA which stays exactly at 1 (meaning that the decentralized market design with imperfect information is as efficient as the centralized market design with perfect information). Identically, in [START_REF] Vaya | Optimal Bidding Strategy of a Plug-in Electric Vehicle Aggregator in Day-ahead Electricity Markets[END_REF], even with simple mechanisms to guess the bids of other market participants, results close to a perfect information benchmark can be achieved.

On the complexity of block bids

The liberalized electricity market design has been extended to facilitate the trade of energy flexibility by introducing new categories of complex bids such as linked block orders, exclusive block orders and flexible orders [START_REF] Poli | Clearing procedures for day-ahead Italian electricity market: are complex bids really required?[END_REF][START_REF][END_REF]. The introduction of such new categories of bids is justified by the need to take into account techno-economical aspects of generation units, currently not captured by simple quantity bids. They also generate lots of debates regarding possible trade-offs between an increase of complexity in the bid definition and the guarantee of the efficiency of market operation.

Inter-temporal constraints: In this paper, we consider quantity offers that are bidded on the energy market and take the form of (linked) block bids, i.e., length tH vectors subject to inter-temporal constraints that are accepted in full. Inter-temporal constraints might capture dynamic constraints such as ramping or start-up costs constraints. In the framework of this numerical illustration and for the sake of simplicity, the RES-based generation on market 2 on the time period [t; t + 1] is fixed, i.e., ŵ2(t + 1) = ŵ2(t) = 8 and we focus on high wind share penetration. In Figure 6 left, we have represented

q 1 (t+1) q 1 (t)
as a function of the local market RES-based generation at time periods t and t + 1, i.e., ŵ1(t), ŵ1(t + 1). We observe that in case of a significant decrease in the RES-based generation, i.e., if ŵ1(t) >> ŵ1(t + 1) then, q 1 (t + 1) >> q 1 (t) meaning that the optimal quantity bidded by the generator in the local market is larger at t + 1 than at t. Otherwise, i.e., in case of significant increase in the RES-based generation ( ŵ1(t) << ŵ1(t + 1)) then, q 1 (t + 1) << q 1 (t) meaning that the optimal quantity bidded by the generator in local market 1 is smaller at t + 1 than at t. If we take into account additional transmission line capacity constraint and local market capacity constraints, we observe in Figure 6 right, that equilibrium exists only for ŵ1(t + 1) ≥ 7 i.e., only under high share of renewables in the local market. Optimal bid size: We want to optimize numerically the length of the block quantity offers submitted by the generators in the local markets. RES-based generations are based on the values provided on the ELIA website http://www.elia.be/en/ grid-data/data-download. We make the assumption that local market 1 RES-based generation is provided by an offshore wind producer only, whereas on local market 2 the RES-based generation relies mainly on onshore wind farms.

In Figure 7, we have represented the social welfare as a function of the length of the bid, evaluated in number of quarter hours (15 minutes), under centralized and decentralized market designs. The decentralized market design may involve either simultaneous or sequential market clearings of the local markets. We observe that a first threshold is reached around 190 quarters (i.e., after two consecutive days) and a third threshold is reached after 270 quarters (i.e, before three consecutive days).

These results are therefore in favor of the existence of a maximum bid length, i.e., an upper-limit on tH . We observe in addition in Figure 7 that the social welfare (in Equation ( 11)) is higher under simultaneous local market clearing than under sequential market clearing.

Conclusion

In this paper, we have modeled interactions between local and national Market Operators for two market designs: a centralized one, formulated as a standard constrained optimization problem, and a decentralized one, formulated as a Stackelberg game where strategic generators, who have market power, act as leaders anticipating the exchanges between the local markets, i.e., the locational marginal prices and transmission flows in line. Both cases where local markets are cleared simultaneously or sequentially are considered. We have quantified the loss of efficiency caused by the generators' anticipation through the Price of Anarchy (PoA). We have proved that the Stackelberg game, formulated as a bilevel mathematical programming problem, can be reformulated as a non linear Complementarity Problem and admits a unique Nash equilibrium in case of simple bids. The result is generalized to block bids, i.e., length tH quantity vectors that are linked by inter-temporal constraints, using Complementarity Theory. A case study highlights the impact of transmission line and local market generation capacities, as well as RES-based generation impacts, on the existence of a market equilibrium. The impact of distortion caused by imperfect information on local RES-based generation on the PoA is also quantitatively assessed. Numerical illustrations highlight that (i) decentralized market design is as efficient as the centralized market design under high share of renewables, that (ii) transmission and local market generation capacities have an impact on the existence of a market equilibrium, that (iii) imperfect information has only a limited impact on the decentralized market design efficiency compared with the centralized one, and that (iv) for each market design, there exists an optimal size for the block bids that maximizes the social welfare. Finally simultaneous market clearing gives rises to larger social welfare than sequential market clearing.

Figure 1 :

 1 Figure 1: We evaluate numerically the impact of RES-based generation on the Price of Anarchy (PoA) for decentralized market design and simultaneous clearings of the local markets.

Figure 2 :

 2 Figure 2: We represent parametric feasible sets for the local market exchanges r(t) as functions of RES-based generations for centralized (a) and decentralized market designs (b).

Figure 3 :

 3 Figure 3: In (a) we represent each local market generator optimal block bid as a function of local RES-based generation, ŵ1, ŵ2. Incorporating transmission capacity 0 ≤ r ≤ 5 and local market generation capacity constraints with q1 = q2 = 0.19, we delineate the set of RES-based generation where equilibrium exists in (b).

Figure 4 :

 4 Figure 4: We compare the ratio of optimal bids under sequential and simultaneous local market clearings in local market 1 (left) and local market 2 (right).

Figure 5 :

 5 Figure 5: We quantify the impact of information distortion on the PoA for simultaneous (left) and sequential (right) market clearings.

Figure 6 :

 6 Figure 6: We represent the impact of a change (increase/decrease) in RES-based generation over two consecutive time periods on the ratio between two optimal consecutive simple bids (left) and on the existence of a market equilibrium taking into account transmission link and capacity constraints (right).

Figure 7 :

 7 Figure 7: Impact of the block bid size on the social welfare under centralized and decentralized market designs (with either simultaneous market clearing or sequential market clearing of the local markets).

An extensive form game describes with a tree how a game is played. It depicts the order in which players make moves, and the information each player has at each decision point[START_REF] Osborne | A Course in Game Theory[END_REF].

The national MOs are responsible for the clearing of their local markets. It can happens either simultaneously or sequentially.

The case where generators anticipate transmission link congestion is for example addressed in[START_REF] Cadre | Wind Farm Portfolio Optimization[END_REF].

Local markets with simultaneous market clearing

With the local market organization, a Stackelberg game (EPEC [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF][START_REF] Neuhoff | Network-constrained Cournot models of liberalized electricity markets: the devil is in the details[END_REF][START_REF] Yao | Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network[END_REF]) occurs between the conventional generators who anticipate the outcome of the market clearing process, and the national MO. The Stackelberg game is formalized as a bilevel optimization problem involving an upper-level optimization problem decribed by Equations ( 8), ( 9), [START_REF] Economides | Net Neutrality on the Internet: A Two-sided Market Analysis[END_REF] inter-related with a lower-level optimization problem described in Equations ( 11), [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF].

In this Stackelberg game setting, we are looking for subgame perfect Nash equilibrium. To determine the lower-level reaction function, we proceed by backward induction, i.e., we start by solving the lower-level optimization problem [START_REF] Ehrenmann | A comparison of electricity market designs in networks[END_REF], [START_REF] Gabriel | Complementarity Modeling in Energy Markets[END_REF] assuming that the generators' quantities q1, q2 are fixed. Differentiating the lower-level objective function with respect to r, we obtain the analytical expression of the reaction function:

By substitution of the reaction function in the upper-level equations ( 8), ( 9) and ( 10) and differentiation with respect to q k (k = 1, 2), we obtain:

Local markets with sequential market clearing

In this section, we assume instead that the local markets are cleared sequentially. The reaction function is identical with Equation (29), i.e., in the case where local markets are cleared simultaneously. The optimal bids of the generators located in the two local markets (market 1 having lower priority than market 2) are computed analytically:

.

Numerical illustrations

We aim, in this section, at quantifying numerically the impact of local market RESbased generations, transmission and local market capacity constraints, on the PoA and on the existence of a market equilibrium in Subsection 4.3.1. The impact of simultaneous versus sequential market clearings on the PoA and optimal bidding strategy is analyzed in Subsection 4.3.2. Imperfect information is included in Subsection 4.3.3.


Maria Makolkina
email: makolkina@list.ru

Andrey Koucheryavy

Alexander Paramonov

Investigation of Traffic Pattern for the Augmented Reality Applications

Keywords: Augmented reality, flying ubiquitous sensor networks, unmanned aerial vehicles, interaction model, traffic pattern, quality of experience

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Today there are many applications of augmented reality that can be classified into six large groups: medicine; assembly, maintenance and repair of the complex equipment; addition of the private and common information of private to the existing objects; control of robots, unmanned aerial vehicles, etc.; gaming and entertainment industry; military [START_REF] Soh | Virtual and augmented reality applications in manufacturing[END_REF][START_REF] Billinghurst | A survey of augmented reality[END_REF]. In addition, the use of augmented reality for the management and monitoring of telecommunication networks is a special interest [START_REF] Bergenti | Augmented Reality for Field Maintenance of Large Telecommunication Networks[END_REF][START_REF] Hui | Highway traffic flow nonlinear character analysis and prediction[END_REF]. Also, augmented reality is used to analyze traffic flows in the Vehicular Ad-hoc networks (VANET) [START_REF] Abdi | In-Vehicle Augmented Reality Traffic Information System: A New Type of Communication Between Driver and Vehicle[END_REF][START_REF] Park | Design of a visual perception model with edge-adaptive gabor filter and support vector machine for traffic sign detection[END_REF][START_REF] Vinel | A simple analytical model for the periodic broadcasting in vehicular ad-hoc networks[END_REF] and other transport networks to detect congestions [START_REF] Hong-Bin | Analysis and prediction of complex dynamical characteristics of short-term traffic flow[END_REF][START_REF] Topór-Kamiñski | Delays models of measurement and control data transmission network[END_REF]. There are a few applications that allow user to manage various engines and devices [START_REF] Ng-Thow-Hing | User-Centered Perspectives for Automotive Augmented Reality[END_REF], informing drivers about the rod situation [START_REF] Winter | Preparing drivers for dangerous situations: A critical reflection on continuous shared control[END_REF], and control the UAVs [START_REF] Zollmann | Augmented Reality Supported Micro Aerial Vehicle Navigation[END_REF]. Flying ubiquitous sensor networks (FUSN) based on UAVs is gaining more popularity with arising of the Industrial Internet of Things (IIoT). Among the industries that demonstrate the greatest interest in the introduction of the Industrial Internet, can be called mining, engineering, agriculture, and transport. It is widely believed that data collection from the devices and data analysis are the main ideas of the FUSN. At the same time the important aspect is missed, that the transfer of a rapidly growing raw data in processing centers requires new technological solutions and methods of the network planning [START_REF] Shafig | A First Look at Cellular Machine-to-Machine Traffic: Large Scale Measurement and Characterization[END_REF][START_REF]Analysis of routes in the network based on a swarm of UAVS[END_REF]. For some applications, for example, observing over the territory, cameras may be installed on the UAVs. Such systems apply new restrictions on the application and impose new requirements to the telecommunication networks, because of high sensitivity of the UAVs to the network performance. The accuracy and maneuverability of UAV management depends on the quality of service and quality of experience.

Due to the fact that there are many fundamentally different services, it is necessary to develop models for the interaction of network elements while providing the services of the augmented reality, the traffic model, the user's behavior model, and the density model of both users and objects of augmented reality.

In this paper, we investigated traffic pattern for the augmented reality applications that use video camera for control, observation, monitoring, surveillance etc.

RELATED WORKS

By now, several works on new traffic patterns have been known in the context of the introduction of the concept of the Internet of Things (IoT). Thus, in [START_REF] Pokric | Augmented Reality Based Smart City Services Using Secure IoT Infrastructure[END_REF] authors investigated the solutions for a smart city service based on the technology of augmented reality and Internet of Things infrastructure. They described the implementation of delivering the important information about the bus arrival times, tourist landmarks to the citizens, using bus-mounted IoT devices which transmit the data to the associated cloud servers. In the paper [START_REF] Drajic | Traffic Generation Application for Simulating Online Games and M2M applications via Wireless Networks[END_REF] traffic modeling and simulation of multiplayer realtime games and M2M applications are presented. Authors evaluate the impact of additional simulated traffic on the performance of mobile wireless network. The researches from Japan in [START_REF] Orlovsky | Virtual and augmented reality on the 5G highway[END_REF] review 5G network to perform augmented reality applications. They investigated the influence of the bandwidth and the latency on the development and implementation augmented reality services. In [START_REF] Westphal | Challenges in Networking to Support Augmented Reality and Virtual Reality[END_REF] the features of augmented reality applications researched. They consider network requirements, such as bandwidth, delay and propose to reevaluate the network infrastructure to support such applications. In this paper [START_REF] Vybornova | Traffic Analysis in Target Tracking Ubiquitous Sensor Networks[END_REF] traffic in Ubiquitous sensor networks is analyzed. The new on-off model for the source traffic simulating described. During the investigation authors determine how parameters of such model influence on the traffic at the sink. It is also worth noting that today much attention is paid to models of downloading traffic D2D [START_REF] Andreev | Analyzing Assisted Offloading of Cellular User Sessions onto D2D Links in Unlicensed Bands[END_REF][START_REF] Pyattaev | Networkassisted D2D communications: Implementing a technology prototype for cellular traffic offloading[END_REF]. These works are important and allow us to move forward in analyzing traffic, but for augmented reality there are features associated with the emergence of new parameters such as traverse speed, the angle of sector of the review, density of objects, which are planned to be taken into account in the developed model.

The goal of the investigation is the development a traffic pattern, depending on the UAV's position changes in the augmented reality applications.

INTERACTION MODEL

To develop an interaction model of the network elements, we chose as an example an application for the city area monitoring. In the observed area, the objects are people, their personal devices, buildings, cars, traffic conditions, etc. Installing the camera on the UAV allows the pilot to detect the obstructions, to control the UAV, collect data from land sensors and observe everything in the surveillance area. For example, the pilot can determine the object by the sensor located on it and get all the necessary information with the augmented reality glasses or visually identify the object independently if it does not have sensors. The pilot controls the actions of UAV through the AR device (glasses or helmet) by means of turns and nods, fig. 1. The camera is installed on the UAV, video stream displayed on the AR device that is on the head of the pilot. Based on the video stream, pilot can define the UAV location and control both the UAV itself and the camera to change the viewing angle. So, it is necessary to transmit two streams simultaneously with different requirements to quality of transmission; the first one is a video stream, the second is a control stream. Also, objects found in the field of view may transmit information to the AR device. Depending on the movement of the UAV or the camera number and type of objects in the field of view may change, which affects both the video stream itself and the control flow.

TRAFFIC PATTERN

For the description of the traffic made by service it is necessary to connect volume given by the user and the user of data in case of changes of his surrounding:

─ -service space model; ─ -model of a surrounding of the user; ─ -behavior model.

As a service space we will understand an information model of physical threedimensional space in which there can be a user of service. The information model includes the description of some objects which are in this space of , where n is total number of objects.

The model of a surrounding of the user is a subspace of service space, i.e. a part of space limited by perception opportunities (model of these opportunities). A surrounding is usually bound to position of the user in space of service and includes a set of objects of

, where k is a number of the objects, which are in the area of perception of the user.

The behavior model describes changes of position of the user and his surrounding in service space. Changes in a surrounding of the user can be caused by relocation of the user, and relocation of objects in service space. The change caused by appearance in a surrounding of the user of a new object , leads to a request of data on this object.

The algorithm of implementation of service shall provide performance of the following functions: ─ -identification of an event of change of a surrounding and computation of parameters of change; ─ -information request about surrounding change; ─ -receiving data and its display.

The possible diagram of a data interchange is provided on fig. 2.

As a surrounding also as well as space of service is limited (area of perception) physical three-dimensional space, changes in it can be described as a stream of events connected to appearance of objects in it. Objects can enter through its boundaries owing to relocation of these boundaries or objects. In the first case, relocation of boundaries is connected to behavior of the user, and in the second to behavior of objects. In that and other case quality of functioning of system will depend on its ability to timely service events of this flow. Thus, the task of support of quality of service can be considered as a choice of parameters of system (productivity, throughput, distribution of its functionality) from the characteristic of an event stream and load of the system made by this flow.

Properties of an event stream substantially define properties of a data stream between system elements. For example, in system of positioning on the district map such flow is defined by events of change of coordinates of the user and is defined by characteristics of his movement, in system with using AR glasses it will be determined by their orientation in space and, probably, by the events connected to transferring data about objects in field of view or their characteristics.

It is obvious that characteristics of a flow will depend on distribution and characteristics of objects in service space, and also characteristics of movement of the UAV.

Let's make an assumption that objects in space of service are distributed in a random way (form a Poisson field) and are fixed, only the UAV is mobile. Then, change of position of the UAV is equivalent to change of its surrounding. Taking into account properties of space of service and surrounding, this change can be described by the volume or the area.

Properties of the traffic generated by the UAV device, depends on the distribution of objects of the UAV surrounding and the UAV behavior (motion and rotation).

Poisson field is a one of the possible distribution of the objects. This distribution may not very close to real world distribution, bat it is very convenient to get final solutions for the queuing system model. The arguments for the Poisson field are that we do not know for now the exact distribution of the objects in the real world, but we know exactly the solutions for the Poisson field. This model can be used for comparison and quality angling of the service system.

In case information about surrounding of the user represents the image, received by the videocamera, set on the unmanned aerial vehicle, for determination of field of restriction of a surrounding of the user it is necessary to consider features of movement of this device and the transferring video camera. Let's consider 2D option of a surrounding (terrestrial objects) and will describe a surrounding of the user by radius sector r. Such model is closer to a real situation, than model of a circle [START_REF] Koucheryavy | Applications of Augmented Reality Traffic and Quality Requirements Study and Modeling[END_REF] since the video camera has limited viewing angle, and probably rather high line speed of movement restricts opportunities regarding the circle review. We will mean the line speed of relocation of the UAV v a constant. Then, during t change of a surrounding will be defined by number of new objects in the area defining a surrounding of the user.

As an example, when using the UAV, the district map with the conditional text and graphics images or designations of objects can be model of a surrounding. The highspeed link of video transmission is more subject to changes of conditions of reception, than low-speed link of signal transmission of control. In case of decline in quality of transmission channel of video, the image, represented to the user. can be changed for the district map which is available on the local server.

Let's estimate quantity of new objects in a surrounding during t as

( )ρ ) ( ) ( t L S t n = (1)
Where ( )

) ( ~t L S
-is square of change of a surrounding; ρdensity of objects (objects/sq.m). The density is equal to the number of objects to the service area ratio.

The model illustrating relocation of the user and change of its surrounding is given in fig. 3. Offset of the sector representing a surrounding of the user from starting point on distance L is led to formation of area (the shaded area) which defines surrounding change. Objects in the field are identified according to a service provision algorithm, therefore requests for provision of additional information are created. From the given figure, the area of the shaded area can be determined by a formula (2)

( ) ( ) ( ) ( )      > ≤ - = - - = r L r r L L rL L r S r S L S 2 2 2 ~2 2 α α (2)
The number of new objects in the area can be defined as

( )ρ L S t n ) ( = (3)
where ρ -density of objects (objects/sq.m), α -the angle of sector of the review (radians). Dependence of the number of new objects the area on the time, for different angle and velocity, is depicted on the fig. 4. As you can see from this picture, when the viewing angle or speed increases, the number of new objects in the area also rises over a time interval. Stabilization of the number of objects in the case as a speed exceeds over some value occurs when a complete change of all objects in the area takes place during the considered period of time. This is because their number is determined by the area of the sector.

Considering this process in progress, i.e. in case of movement of the user, there is the event stream (data requests).

Intensity of an event stream (data requests) can be defined as number of objects in a small increment of the area of the considered figure

( ) v L dL L S d r ρ λ 0 ~= = (4)
where ρ -density of objects (objects/sq.m), v -traverse speed (m/s). Derivative of formula (2) in a point L=0.

( ) ( )

r L L r L dL L S d α α = = - = = 0 0 ~ (5) Then, consider (4) и (5) v r r ρ α λ = (6)
Considering properties of the Poisson field accepted for model the quantity of objects in some limited area is accidental, distributed under the Poisson law and depends only on the area (or volume) of the considered area. Therefore, for the accepted model the flow of requests will represent the elementary flow for which the probability of arrival of k of requests for an interval of time of t will be defined as

( ) ( ) vt r k t k r k e k vt r e k t p r ρ α λ ρ α λ - - = = ! ! (7)
Probability of k arrival requests during the time interval given in the fig. 5.

Fig. 5. Probability density of k requests during the time interval (moving)

With translational motion the device can make rotational motions. The model of rotational motion is given in fig. 6.

The square of the shaded area can be determined by a formula (8) The number of new objects in the area can be defined as

( ) ( ) ( )        > ≤ = - = α β α α β β β β 2 2 0 ~2 2 r r S S S
( )ρ β β S n ) ( = (9)
where ρ -density of objects (objects/sq.m), β -the turning angle (radians), α -the angle of sector of the review (radians). Dependence of the number of new objects the area on the time, for different angle, is depicted on the fig. 7. Considering this process in progress, i.e. in case of movement of the user the event stream (requests of data) takes place.

Intensity of an event stream (requests about data) can be defined as number of objects in a small increment of the area of the considered figure For example, upon rotation 2 π β = for the one second traffic intensity is equivalent to the traffic intensity of the linear motion with speed of 50 m/s (180 km/h). In this example, the radius is selected to be 50 m. This ratio of produced traffic and UAV motion features should be considered when choosing a method of selection and implementation of data delivery.

The traffic flow made as a result of service provision is defined by a flow of replies to the data requests. Generally, both the single data packet, and a flow of packets (transmission of video or audio data) can be the response. Intensity of this flow can be described as η λ λ r s = [START_REF] Pokric | Augmented Reality Based Smart City Services Using Secure IoT Infrastructure[END_REF] where η -average quantity of the packets necessary for processing of a request.

By transmission of video data can exceed intensity of requests in tens and hundreds times. Taking into account requirements to quality it leads to essential growth of requirements to throughput of communication network.

The physical amount of surrounding of the user is, as a rule, commensurable with a radius of wireless technologies used for the PAN organization, for example group of Wi-Fi standards. Many objects of AR services (elements of city infrastructure, vehicles, household appliances) can be equipped with nodes of access and necessary data which can be presented to users. Therefore, use of D2D technologies can be the possible decision, providing essential lowering of a traffic on a communication network.

Intensity of this flow will be defined as

D D r s 2 η λ λ = (15) Where η γ η ) 1 ( 2 - = D D
, γ -part of the objects of surrounding supporting D2D technology.

Certainly, application of D2D of technologies is possible only when objects of service are the physical entities mentioned above, which can be equipped with the respective communication centers. Rather wide range of services requires interaction with remote data bases and the solution of tasks of provision of quality.

FURTHER RESEARCHES

The model considered above allows analysis of the AR service traffic regardless of a service implementation methods, both on the server and client components. The specific method of implementation can significantly influence the nature of the traffic. Implementation is characterized by distribution of data handling functions between the client and server applications, and also methods of data selection. In particular, it is the organization of a buffer memory (cache) of the client application, determination of its size, speed of updating, formations of data requests with the forecast of movement. Control of these parameters allows to select the most acceptable usage mode of resources depending on requirements and behavior of the client application or device.

CONCLUSION

The article represents the investigation of the Augmented Reality scenario that uses UAV for data and video collection. This application may be widely used for the monitoring of the remote and inaccessible areas, restrained urban conditions with the busy streets and roads. The UAV with a video camera installed is used as an intermediate element. The user of the application through the AR glasses may see not only the picture from the video camera, but also an additional information about objects on the picture, due to the data collectoin from the sensors and online data analysis on the servers.

During the investigation, the service model of the AR application with the UAV was developed. From this service model, it appears that the characteristics of the created traffic depend on the UAV behavior, UAV surroundings, and the way of data transmission.

Fig. 1 .

 1 Fig. 1. Interaction of the main elements in the provision of AR services.

Fig. 2 .

 2 Fig. 2. Diagram of a Data Interchange by provision of AR service.

Fig. 3 .

 3 Fig. 3. Change of Surrounding in case of translational motion.

Fig. 4 .

 4 Fig. 4. Dependence of the number of new objects the area on the time (moving)

Fig. 6 .

 6 Fig. 6. Change of Surrounding in case of turn.

Fig. 7 .

 7 Fig. 7. Dependence of the number of new objects the area on the time (turn)

  ρ -density of objects (objects/sq.m), w -angular speed of turn (rad/s). Derivative of expression (2) in a point β=0 model of a Poisson field, the flow of requests will represent the elementary flow, for which the probability of arrival of k-requests for an interval of time t will be defined as of k arrival requests during the time interval given in the fig.8.

Fig. 8 .Figure 9 2 π

 892 Fig. 8. Probability density of k requests for an interval of time (turn)

Fig. 9 .

 9 Fig. 9.The ratio of angular speed of turn (rad/s) and the line speed of relocation (m/s) for the equal traffic intensity.

Further authors develop the traffic model that considers the UAV-based AR service characteristics, such as a limited lookout angle, speed of the UAV, and a number of objects in the service area.

The proposed model estimates traffic parameters of the new, previously not investigated application. For this reason, authors began the investigation with the Poisson field model for the object distribution, as it has known solutions, and the real objects distribution on the territory is unclear. In the future works authors are going to provide models for the other distributions.

ACKNOWLEDGMENT.

The publication was financially supported by the Ministry of Education and Science of the Russian Federation (the Agreement number 02.a03.21.0008), RFBR according to the research project No. 16-37-00209 mol_a "Development of the principles of integration the Real Sense technology and Internet of Things".