Francois Baccelli
email: francois.baccelli@austin.utexas.edu

Chandramani Singh
email: chandramani.singh@inria.fr

Adaptive Spatial Aloha, Fairness and Stochastic Geometry

This work aims at combining adaptive protocol design, utility maximization and stochastic geometry. We focus on a spatial adaptation of Aloha within the framework of ad hoc networks. We consider quasi-static networks in which mobiles learn the local topology and incorporate this information to adapt their medium access probability (MAP) selection to their local environment. We consider the cases where nodes cooperate in a distributed way to maximize the global throughput or to achieve either proportional fair or max-min fair medium access. In the proportional fair case, we show that nodes can compute their optimal MAPs as solutions to certain fixed point equations. In the maximum throughput case, the optimal MAPs are obtained through a Gibbs Sampling based algorithm. In the max min case, these are obtained as the solution of a convex optimization problem. The main performance analysis result of the paper is that this type of distributed adaptation can be analyzed using stochastic geometry in the proportional fair case. In this case, we show that, when the nodes form a homogeneous Poisson point process in the Euclidean plane, the distribution of the optimal MAP can be obtained from that of a certain shot noise process w.r.t. the node Poisson point process and that the mean utility can also be derived from this distribution. We discuss the difficulties to be faced for analyzing the performance of the other cases (maximal throughput and max-min fairness). Numerical results illustrate our findings and quantify the gains brought by spatial adaptation in such networks.

I. INTRODUCTION

Stochastic geometry has recently been used for the analysis and performance evaluation of wireless (ad hoc as well as cellular) networks; in this approach, one models node locations as a spatial point process, e.g., homogeneous Poisson point processes, and one computes various network statistics, e.g., interference, successful transmission probability, coverage (or, outage) probability etc. as spatial averages. This often leads to tractable performance metrics that are amenable to parametric optimization with respect to network parameters (node density, protocol parameters, etc.). More precisely, this approach yields spatial averages of the performance metrics for given network parameters; then the parameters can be chosen to optimize performance. This approach takes a macroscopic view of the network with the underlying assumption that all nodes in the network have identical statistical characteristics.

In practice, due to randomness and heterogeneity in networks, nodes need to adapt to local spatial and temporal condi-tions (e.g., channel conditions and topology) to reach optimum network wide performance. For example, nodes in wireless LANs adjust their window sizes based on acknowledgment feedback; in cellular networks nodes are scheduled based on channel conditions and adapt their transmit powers based on the measured SINRs, which in turn depend on the transmit powers set by other nodes. In all such scenarios, distributed adaptive algorithms are used to reach a desired network wide operating point e.g. that maximizing some utility. While the behavior of such distributed optimization protocols is often well understood on a given topology, there are usually no analytical characterizations of the statistical properties of the optimal state in large random and heterogeneous networks.

The main aim of this work is to use stochastic geometry to study spatial adaptations of medium access control in Aloha that aim at optimizing certain utilities. While we identify a utility for which stochastic geometry can be used to compute the spatial distribution of MAP and the expected utility, we are far from being able to do so for all types of utilities within the α-fair class and we discuss the difficulties to be faced.

Let us start with a review of the state of the art on Aloha. Wireless spectrum is well known to be a precious and scarce shared resource. Medium Access Control (MAC) algorithms are employed to coordinate access to the shared wireless medium. An efficient MAC protocol should ensure high system throughput, and should also distribute the available bandwidth fairly among the competing nodes. The simplest of the MAC protocols, Aloha and slotted Aloha, with a "random access" spirit, were introduced by Abramson [START_REF] Abramson | THE ALOHA SYSTEM: another alternative for computer communications[END_REF] and Roberts [START_REF] Roberts | ALOHA packet system with and without slots and capture[END_REF] respectively. In these protocols, only one node could successfully transmit at a time. Reference [START_REF] Baccelli | An Aloha protocol for multihop mobile wireless networks[END_REF] modeled node locations as spatial point processes, and also modeled channel fadings, interferences and SINR based reception. This allowed for spatial reuse and multiple simultaneous successful transmissions depending on SINR levels at the corresponding receivers. All the above protocols prescribe identical attempt probabilities for all the nodes. Reference [START_REF] Baccelli | Stochastic analysis of spatial and opportunistic Aloha[END_REF] further proposed opportunistic Aloha in which nodes' transmission attempts are modulated by their channel conditions.

Among the initial attempts of MAP adaptation in Aloha, reference [START_REF] Hajek | Stochastic approximation methods for decentralized control of multiaccess communications[END_REF] analyzed protocol model and proposed stochas-tic approximation based strategies that were based on receiver feedback and were aimed at stabilizing the network. References [START_REF] Baccelli | An Aloha protocol for multihop mobile wireless networks[END_REF], [START_REF] Baccelli | Stochastic analysis of spatial and opportunistic Aloha[END_REF] also optimized nodes' attempt probabilities (or thresholds) in order to maximize the spatial density of successful transmissions. Reference [START_REF] Hsu | Channel-aware ALOHA with SINR capture: When is the knowledge of channel not helpful[END_REF] analyzed both plain and opportunistic Aloha in a network where all the nodes communicate to one access point. They assumed statistically identical Rayleigh faded channels with no dependence on geometry (i.e., no path loss components). They demonstrated a paradoxical behavior where plain Aloha yields better aggregate throughput than the opportunistic one. Reference [START_REF] Mohsenian-Rad | Optimal sinr-based random access[END_REF] also studied optimal random access with SINR based reception. However, they considered constant channel gains. They developed a centralized algorithm that maximizes the network throughput, and also an algorithm that leads to max-min fair operation. Reference [START_REF] Wang | Distributed algorithms for max-min fair rate allocation in aloha networks[END_REF] modeled network as an undirected graph and studied Aloha under the protocol model. They designed distributed algorithms that are either proportional fair or max-min fair. Reference [START_REF] Hanawal | Stochastic geometry based medium access games[END_REF] built upon the model of [START_REF] Baccelli | An Aloha protocol for multihop mobile wireless networks[END_REF], and formulated the channel access problem as a noncooperative game among users. They considered throughput and delay as performance metrics and proposed pricing schemes that induce socially optimum behavior at equilibrium. However, they set time average quantities (e.g., throughput, delay) as utilities (or costs), and concentrated on symmetric Nash equilibria. Consequently, in their analysis, dependence on local conditions vanishes.

In none of the above Aloha models, nodes account for both wireless channel randomness and local topology for making their random access decisions, as we do in the present paper. 1 There is a vast literature on the modeling of CSMA by stochastic geometry which will not be reviewed in detail here. The very nature of this MAC protocol is adaptive as each node senses the network and acts in order to ensure that certain exclusion rules are satisfied, namely that neighboring nodes do not access the channel simultaneously. However, CSMA as such is designed to guarantee a reasonable scheduling, not to optimize any utility of the throughput. The closest reference to our work is probably [START_REF] Baccelli | On optimizing CSMA for wide area ad hoc networks[END_REF] where the authors study an adaptation of the exclusion range and of the transmit power of a CSMA node to the location of the closest interferer. This adaptation aims at maximizing the mean number of nodes transmitting per unit time and space (while respecting the above exclusion rules). This mean number is however only a surrogate of the rate. In addition, the adaptation is only w.r.t. to the location of the nearest interferer.

We study spatial adaptation of Aloha in ad hoc networks. The network setting is described in Section II. We consider quasi-static networks in which mobiles learn the topology, and incorporate this information in their medium access probability (MAP) selection. We consider the cases where nodes are benevolent and cooperate in a distributed way to maximize the global network throughput or to reach either a proportional fair 1 In view of this distinction, we refer to the spatial Aloha protocol of [START_REF] Baccelli | An Aloha protocol for multihop mobile wireless networks[END_REF] as plain Aloha.

or max-min fair sharing of the network resources. We analyze the case where nodes account only for their closest interferers, for all nodes in a given ball around them, or even all nodes in the network.

Section III is focused on the distributed algorithms that maximize the aggregate throughput or lead to max-min fairness in such networks. In the proportional fair case, we show that nodes can compute the optimal MAPs as solutions to certain fixed point equations. In the maximum throughput case, the optimal MAPs are obtained through a Gibbs Sampling based algorithm. In the max min case, the optimal MAPs are obtained as the solution of a convex optimization problem.

Section IV contains the stochastic geometry results. The model features nodes forming a realization of a homogeneous Poisson point process in the Euclidean plane. We compute the MAP distribution in such a network in the proportional fair case using shot noise field theory. To the best of our knowledge, this distribution is the first example of successful combination of stochastic geometry and adaptive protocol design aimed at optimizing ceratin utility function within this Aloha setting. We also show that the mean value of the logarithm of the throughput obtained by a typical node can be derived from this distribution. Finally, we discuss the difficulties to be faced in order to extend the result to other types of utilities.

The numerical results are gathered in Section V. The aim of this section is two-fold: 1) check the analytical results against simulation and 2) quantify the gains brought by adaption within this setting. We model the ad-hoc wireless network as a set of transmitters and their corresponding receivers, all located in the Euclidean plane. This is often referred to as "bipole model" [3, Chapter 16]. There are N transmitter-receiver pairs communicating over a shared channel. The transmitters follow the slotted version of the Aloha medium access control (MAC) protocol (see Figure 1). A transmitter, in each transmission attempt, sends one packet which occupies one slot. Each transmitter uses unit transmission power. We assume that each node has an infinite backlog of packets to transmit to its receiver. The Euclidean distance between transmitter j and receiver i is r ji , and the path-loss exponent is α (α > 2). We also assume Rayleigh faded channels with h ji being the random fading between transmitter j and receiver i. Moreover, we assume that the random variables h ij , 1 ≤ i ≤ N, 1 ≤ j ≤ N are independent and identically distributed with mean 1/µ. 2 Thus all h ji s have cumulative distribution function (cdf) F (x) = 1e -µx with x ≥ 0. All the receivers are also subjected to white Gaussian thermal noise with variance w, which is also constant across slots. We assume that a receiver successfully receives the packet of the corresponding transmitter if the received SINR exceeds a threshold T .

II. NETWORK MODEL

Let e i be the indicator variable indicating whether transmitter i transmits in a slot, and p i be i's medium access probability. Thus P(e i = 1) = p i . When node i transmits, the received SINR at the corresponding receiver is

γ i = h ii r -α ii j =i e j h ji r -α ji + w .
Then the probability of successful reception q i can be calculated as follows.

P γ i ≥ T |{(h ji , e j ) : j = i} = P   h ii ≥ j =i e j h ji r ji r ii -α T + wT r -α ii {(h ji , e j ) : j = i}   = exp   -µT   j =i e j h ji r ji r ii -α + w r -α ii     .
Thus

q i = E {(hji,ej ):j =i} exp   -µT   j =i e j h ji r ji r ii -α + w r -α ii     = e -µwT r -α ii j =i E (hji,ej ) exp -µe j h ji r ji r ii -α T = e -µwT r -α ii j =i E hji (1 -p j ) + p j exp -µh ji r ji r ii -α T = e -µwT r α ii j =i (1 -p j ) + p j 1 + 1/b ji , where b ji = 1 T rji rii α .
Further simplifying,

q i = e -µwT r α ii j =i 1 - p j 1 + b ji .
(1) 2 The independence assumption is justified if the distance between two receivers is larger than the coherence distance of the wireless channel [START_REF] Baccelli | Stochastic Geometry and Wireless Networks Volume II: Applications[END_REF]. We assume this to be the case.

Then, the rate or throughput of transmitter i is given by p i q i .

The thermal noise appears merely as a constant multiplicative factor in the expression for the successful transmission probability (see [START_REF] Abramson | THE ALOHA SYSTEM: another alternative for computer communications[END_REF]). Moreover, in interference limited networks, the impact of thermal noise is negligible as compared to interference. We focus on such networks, and thus we ignore the thermal noise factor throughout.

III. ADAPTIVE SPATIAL ALOHA AND FAIRNESS

In this section, we analyze adaptations of spatial Aloha that maximize aggregate throughput or achieve proportional fairness or max-min fairness.

A. Maximum Throughput Medium Access

The throughput maximizing medium access probabilities solve the following optimization problem.

maximize Θ := i p i j =i 1 - p j 1 + b ji , subject to 0 ≤ p i ≤ 1, i ∈ N .
We first argue that the optimum in the above optimization problem is attained at one of the vertices of the hypercube formed by the constraint set. To see this, suppose p * ∈ [0, 1] N is an optimal solution, and p * i ∈ (0, 1) for some i ∈ N . Clearly,

∂Θ ∂p i p=p * = j =i 1 - p * j 1 + b ji - j =i p * j 1 + b ij k =i,j 1 - p * k 1 + b kj = 0.
Since the partial derivative is independent of p i , p i can be set to either 0 or 1 without reducing the value of the objective function. This proves our claim. In the following we focus only on such extreme solutions. Then the above problem is equivalent to finding an M ⊂ N such that p i = 1 if and only if i ∈ M is an optimal solution. Thus we are interested in

maximize M⊂N i∈M j∈M\{i} 1 - 1 1 + b ji .
An iterative solution: We can pose this problem as a strategic form game with the users as players [START_REF] Osborne | A Course in Game Theory[END_REF]. For each player its action a i lies in {0, 1}, and the utility function u i : a → R is given by

u i (0, a -i ) = 0, u i (1, a -i ) = 1 - j∈M\{i} 1 - 1 1 + b ji - j∈M\{i} 1 1 + b ij k∈M\{i,j} 1 - 1 1 + b kj .
This is a potential game with the above objective function as the potential function [START_REF] Monderer | Potential games[END_REF]. Thus the best response dynamics converges to a Nash equilibrium. This algorithm can be implemented in a distributed fashion if each node i knows b ij , b ji for all j, and also M and k∈M\{j} (1

-(1 + b kj ) -1
) for all j ∈ M after each iteration. However, a Nash equilibrium can be a suboptimal solution to the above optimization problem.

To alleviate this problem, we propose a Gibbs sampler based distributed algorithm, wherein each node i chooses action 1 with probability

p i = e ui(1,a-i)/τ 1 + e ui(1,a-i)/τ .
The parameter τ is called the temperature. The Gibbs sampler dynamics converges to a steady state which is the Gibbs distribution associated with the aggregate throughput and the temperature τ [START_REF] Bremaud | Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues[END_REF]. In other words, we are led to the following distribution on the action profiles:

πτ (a) = ue i∈N ui(a) ,
where u is a normalizing constant. When τ goes to 0 in an appropriate way (i.e., as 1/ log(1 + t), where t is the time), the distribution πτ (•) converges to a dirac mass at the action profile a * with maximum aggregate utility if it is unique. Notice that the aggregate utility i∈N u i (a) equals the aggregate throughput. Thus the action profile a * is a solution to the original throughput optimization problem.

Remark 3.1: The first two terms in the utility function u i (1, a -i ) can be seen as "selfish" part of user i, whereas the last summation term is "altruistic" part. The user makes a decision based on whether the "selfish" part dominates or viceversa.

Remark 3.2: In a quasi-static network where topology continuously changes, although at a slower time scale, different sets of nodes are likely to be scheduled to transmit under different topologies. Thus, in terms of long term performance, maximum throughput medium access is not grossly unfair.

B. Proportional Fair Medium Access

The proportional fair medium access problem can be formulated as follows.

maximize i log (p i q i ), subject to 0 ≤ p i ≤ 1, i ∈ N .

The objective function can be rewritten as

i   log p i + j =i log 1 - p j 1 + b ji   .
We thus have a convex separable optimization problem. The partial derivative of the objective function with respect to p i is

1 p i - j =i 1 1 + b ij -p i , (2)
which is continuous and decreasing in p i over [0, 1]. We conclude that at optimality, for each 1 ≤ i ≤ N ,

p i =    f i (p i ) := j =i 1 1+bij -pi -1 if f i (1) < 1, 1 otherwise.
Observe that user i's optimal attempt probability is independent of the attempt probabilities of other users. In particular,

if f i (1) < 1, user i can perform iterations p k+1 i = f i (p k i )
autonomously. Furthermore,

f ′ i (p i ) = - j =i 1 (1 + b ij -p i ) 2   j =i 1 1 + b ij -p i   -2 . Clearly, |f ′ i (p i )| < 1, i.e., f i (•)
is a contraction. Thus the fixed point iterations converge to the optimal p i starting from any

p i ∈ [0, 1].
Remark 3.3: The characterization of the optimal attempt probabilities reflects the altruistic behavior of users. More precisely, user i's attempt probability is a function of {b ij , j = i} which are measures of i's interference to all other users. In particular, if j =i 1 bij < 1, i.e., if i's transmission does not cause significant interference to the other users, then i transmits in all the slots. Unlike the throughput maximization problem, there is no "selfish" component in the decision making rule.

Remark 3.4: As the target SINR T → ∞, b ij → 0 for all i, j, and the proportional fair attempt probabilities satisfy

1 p i = j =i 1 1 -p i = N -1 1 -p i
for all i ∈ N . This yields p i = 1 N for all i ∈ N . This is expected, because in the limiting case a transmission can succeed if and only if there is no other concurrent transmission. This is hence Aloha without spatial reuse, and it is well known that in this case, the optimal access probability is 1/N asymptotically [START_REF] Bertsekas | Data Networks[END_REF].

C. Max-min Fair Medium Access

Our analysis in this section follows [START_REF] Wang | Distributed algorithms for max-min fair rate allocation in aloha networks[END_REF], [START_REF] Wang | Lexicographic max-min fair rate allocation in random access wireless networks[END_REF]. The max-min fair medium access problem can be formulated as maximize θ,

subject to θ ≤ p i j =i 1 - p j 1 + b ji , i ∈ N ,
where constraint functions are defined for all p ∈ [0, 1] N . The following is an equivalent convex optimization problem (see [START_REF] Wang | Distributed algorithms for max-min fair rate allocation in aloha networks[END_REF] for details):

minimize 1 2 θ 2 , subject to θ ≤ log p i + j =i log 1 - p j 1 + b ji , i ∈ N .
The Lagrange function of this problem is given by [8]

1 2 θ 2 + i∈N λ i   θ -log p i - j =i log 1 - p j 1 + b ji   ,
with λ i ≥ 0, i ∈ N being the Lagrange multipliers.

Minimization of the Lagrange function (which is concave in p and θ) gives

p i =    λ i j =i λj 1+bij -pi -1 if 1 λi j =i λj bij > 1, 1 otherwise. (3) θ = - i∈N λ i . (4)
Wang and Kar [START_REF] Wang | Distributed algorithms for max-min fair rate allocation in aloha networks[END_REF] suggest that the Lagrange multipliers be updated using the gradient projection method. More precisely, for all i ∈ N ,

λ i (n + 1) = λ i (n) + β(n) (5)   θ -log p i - j =i log 1 - p j 1 + b ji     + , (6)
where β(n) is the step size at the nth iteration. Further more, [START_REF] Wang | Distributed algorithms for max-min fair rate allocation in aloha networks[END_REF]Theorem 2] implies that a solution arbitrary close to an optimal solution can be reached via appropriate choice of step sizes. However, all the users need to exchange variables in order to perform updates.

Finally, the directed link graph corresponding to our network is a directed graph in which each vertex stands for a user (i.e., a transmitter-receiver pair) in the network. There is an edge from vertex i to vertex j in the directed link graph if transmission of user i affects the success of transmission of user j. Two vertices i and j are said to be connected if either of the following two conditions hold:

1) there is an edge from i to j or viceversa, 2) there are vertices v 0 = i, v 1 , . . . , v n-1 , vn = j such that vm and v m+1 are connected for m = 0, 1, . . . , n -1. Clearly, the directed link graph for our network model is a complete graph; for any pair of vertices i and j there is an edge from i to j and also from j to i. In particular, the directed link graph is a single strongly connected component [START_REF] Wang | Lexicographic max-min fair rate allocation in random access wireless networks[END_REF]. Thus [19, Corollary 1] implies that the above optimization also obtains the lexicographic max-min fair medium access probabilities that yield identical rates for all the users.

D. Closest Interferer Case

Note that a user needs to know the entire topology, and in a few cases, also needs to communicate with all the nodes to implement the adaptation rules developed in Sections III-A-III-C. In this section, we carry out analysis under the simplifying assumption that the aggregate interference at a receiver is dominated by the transmission from the closest interferer. This is a reasonable approximation in a moderately dense network, specifically when the path loss attenuations are high. Throughout this section, we use the notation

c(i) := argmin j =i r ji , C(i) := {j : c(j) = i},
for all 1 ≤ i ≤ N . In words, c(i) is the strongest interferer of node i, and C(i) is the set of nodes to which node i is the strongest interferer. We assume that there is always a unique c(i) for each i. Then, accounting only for the nearest interferer, the approximate probability of successful transmission for node i is

qi = 1 - p c(i) 1 + b c(i)i .
The analysis of Sections III can be adapted to this simplified scenario.

1) Maximum Throughput Medium Access:

The throughput maximization problem can now be posed as follows.

maximize Θ := i p i qi , subject to 0 ≤ p i ≤ N, i ∈ N .
As in Section III-A, we can argue that some p * ∈ {0, 1} N attains the optimal throughput. Again, an equivalent optimization problem is

maximize M⊂N i∈M 1 - 1{c(i) ∈ M} 1 + b c(i)i ,
or alternatively,

maximize M⊂N i∈M   1 - j∈C(i) 1{j ∈ M} 1 + b ij   .
We now formulate a strategic form game among users, with action sets {0, 1} and utility functions given by

u i (0, a -i ) =0, u i (1, a -i ) =1 - a c(i) 1 + b c(i)i - j∈C(i) a j 1 + b ij .
Again a Gibbs sampler based algorithm yields the optimal set of the transmitting users. Also, user i only needs to know the distances of user c(i) and all the receivers in C(i) and their actions to make its decision.

Remark 3.5: Notice that user i must choose

a i = 1 if 1 - 1 1 + b c(i)i - j∈C(i) 1 1 + b ij > 0.
Such users can set their actions to 1, and need not undergo Gibbs sampler updates.

Discussion: Consider a scenario where a node's closest interferer does not transmit, i.e., has zero attempt probability. Nonetheless, this node always has an active closest interferer (unless there are no other nodes in the network). A better approximation of the success probabilities, and hence of the throughput, is obtained by always accounting for the closest active interferer. Towards this, let us define

c(i, M) := argmin j∈M,j =i r ji , C(i, M) := {j ∈ M : c(j, M) = i},
for all i ∈ M. We are now faced with the following optimization problem.

maximize M⊂N i∈M   1 - j∈C(i,M) 1 1 + b ij   .
We can now define users' utility functions as follows.

u i (0, a -i ) =0, u i (1, a -i ) =1 - 1 1 + b c(i,M)i - j∈C(i,M∪{i}) 1 1 + b ij - 1 1 + b c(j,M)j ,
where M = {j ∈ N : j = i, a j = 1}. The analogous distributed algorithm (Gibbs sampler based) can again be shown to lead to the optimal solution.

2) Proportional Fair Medium Access: We now aim to solve the following optimization problem.

maximize i log (p i qi ), subject to 0 ≤ p i ≤ 1, i ∈ N .
Following the discussion in Section III-B, we obtain

p i =    j∈C(i) 1 1+bij -pi -1 if j∈C(i) 1 bij > 1, 1 otherwise. Again, if j∈C(i) 1 bij > 1, iterations p k+1 i = f i (p k i ) converge
to the optimal p i starting from any p i ∈ [0, 1].

Remark 3.6:

If j∈C(i) 1 bij < 1, i.e.
, if i's transmission does not cause significant interference to the users for whom i is closest interferer, then i transmits in all the slots. The same user may not transmit (in any slot) under the maximum throughput objective if 1 -1 1+b c(i)i ≈ 0 and c(i) and users in C(i) transmit.

We can have explicit formulae for the attempt probabilities in a few special cases.

1) Suppose

C(i) is singleton for each i. If C(i) = {j}, then p i = 1+bij 2 if b ij < 1, 1 otherwise .
2) Linear Network Topology: We now consider a scenario where nodes are placed along a line, say R, and are indexed sequentially. We also assume that for any node i the potential interferers are the two immediate neighbors i -1 and i + 1. This also amounts to assuming C(i) = {i -1, i + 1} for all i. Then, assuming

1 bi,i-1 + 1 bi,i+1 > 1,
the proportional fair attempt probability of node i satisfies

1 p i = 1 1 + b i,i-1 -p i + 1 1 + b i,i+1 -p i .
This is quadratic equation in p i , which on solving gives 3

p i = 2 + b i,i-1 + b i,i+1 - (bi,i-1-bi,i+1) 2 +(1+bi,i-1)(1+bi,i+1)

3

.

3) Max-min Fair Medium Access: Similar to Section III-C, the max-min fair medium access problem is maximize θ,

subject to θ ≤ p i 1 - p c(i) 1 + b c(i)i , i ∈ N .
Again, the constraint functions are defined for all p ∈ [0, 1] N .

Let us recall the definition of the directed link graph associated with the network. In this section, we only account for the interference due the closest interferer. Thus there is an edge from vertex i to vertex j if and only if j ∈ C(i). We assume that the directed link graph is connected (i.e., all the vertices in the graph are connected with each other). If it is not connected, the max-min fair medium access problem on the entire graph decomposes into separate max-min fair medium access problems on each of the connected subgraphs, which can be solved independently.

We now pursue the following convex optimization problem which is equivalent to the above max-min fair medium access optimization problem.

minimize 1 2 i∈N θ 2 i , subject to θ i ≤ log p i + log 1 - p c(i) 1 + b c(i)i , i ∈ N , θ i ≤ θ j , j ∈ C(i), j = c(i).
The last set of constraints along with the connected assumption (of the directed link graph) forces θ i to be equal for all i ∈ N . This confirms equivalence to the initial optimization problem. Now the Lagrange function is

1 2 i∈N θ 2 i + i∈N λ i θ i -log p i -log 1 - p c(i) 1 + b c(i)i + i∈N j∈C(i)∪{c(i)} µ ij (θ i -θ j ),
where

λ i ≥ 0, µ ij ≥ 0, j ∈ C(i) ∪ {c(i)}, i ∈ N
, are the Lagrange multipliers. An approach similar to Section III-C prescribes the following update rules. For all i ∈ N , j ∈

C(i) ∪ {c(i)}, p i =    λ i j∈C(i) λj 1+bij -pi -1 if 1 λi j∈C(i) λj bij > 1, 1
otherwise, [START_REF] Bertsekas | Data Networks[END_REF] [START_REF] Franceschetti | Random Networks for Communication[END_REF] where β(n) is the step size at the nth iteration as before. Observe that any user i can perform updates ( 7)-( 10) via local information exchange. More precisely, it needs to communicate only with user c(i) and the users in C(i).

θ i =        -λ i - j∈C(i)∪{c(i)} (µ ij -µ ji ) if λ i + j∈C(i)∪{c(i)} (µ ij -µ ji ) > 0, 0 otherwise, (8)
λ i (n + 1) = λ i (n) + β(n) θ i -log p i -log 1 - pc(i) 1 + b c(i)i + , (9)
µ ij (n + 1) =[µ ij (n) + β(n)(θ i -θ j )] + ,

E. A Note on Distributed Implementation

The aim of the present paper is primarily of theoretical nature and it is beyond our scope to discuss implementation issues. Let us however stress that the discussed adaptations of the MAP are implementable. We will focus on the proportional fair case in view the main focus of the paper.

Assume each receiver has a distinctive pilot signal with fixed power. Since we assumed a quasi-static network in which the nodes move at a slower time scale, each node can then learn the distance that separates it from a given receiver by listening to its pilot signal and by performing a time average over (so as to smooth out fading). Once this data is available for all receivers, a given transmitter can then solve the key fixed point equation that characterizes its optimal MAP. Distinctive pilot signals can be obtained by a collection of orthogonal codes chosen at random by the receivers. In practice, it is enough for a transmitter to detect the "dominant" receivers (i.e., those within a certain distance to it), so that the scheme will work in an infinite network with a finite (properly tuned) number of such codes.

IV. STOCHASTIC GEOMETRY ANALYSIS

A. Network and Communication Model

We now assume that the transmitting nodes are scattered on the Euclidian plane according to a homogeneous Poisson point process of intensity λ. For each transmitter, its corresponding receiver is at distance r 0 in a random direction. The traffic and channel models are the same as in Section II. As before the transmitters use slotted Aloha to access the channel, and a receiver successfully receives the packet from its transmitter if the received SINR exceeds a threshold T . Finally, transmitters adapt their attempt probabilities as described in Section III.

Each transmitter is associated with a multi dimensional mark that carries information about the adaptive transmission probability and the transmission status. Let Φ = {Xn, Zn} denote a marked Poisson point, where

• Φ = {Xn} denotes the Poisson point process of intensity λ, representing the location of transmitters in the Euclidean plane. • {Zn = (φn, pn, en)} denote the marks of the Poisson point process Φ , which consist of three components:

-{φn} denote the angles from transmitters to receivers. These angles are i.i.d. and uniform on [0, 2π] and independent of Φ. We will call them the primary marks. -{pn} denote the MAPs of the nodes; pn is a secondary mark (i.e. a functionals of Φ and its primary marks, see below). -{en} are indicator functions that take value one if a given node decides to transmit in a given time slot, and zero otherwise. Clearly, P(en = 1) = pn = 1 -P(en = 0). In particular, given pn, en is independent of everything else including {em} m =n . The locations of the receivers will be denoted by Φ r = {Yn = Xn + (r 0 , φn)} with (r 0 , φ) := (r 0 cos φ, r 0 sin φ). It follows from the displacement theorem [START_REF] Baccelli | Stochastic Geometry and Wireless Networks Volume I: Theory[END_REF] that Φ r is also a homogeneous Poisson point process of intensity λ.

The above assumptions will be referred to as the Poisson model. We will also consider below a more general case where the above marked point process is just stationary.

B. Proportional Fair Spatial Aloha 1) MAP distribution: Let us consider response functions

L : R 2 × R 2 → R + defined for each 0 ≤ p ≤ 1 as follows Lρ(x, y) = ρ x-y α T r α 0 + 1 -ρ .
For all 0 ≤ ρ ≤ 1, x ∈ R 2 , the shot noise field J Φ r (ρ, x) associated with the above response function and the marked point process Φ is

J Φ r (ρ, x) = R 2 Lρ(x, y)Φ r (dy) = Yn∈Φ r
Lρ(x, Yn).

Notice that this shot noise is not that representing the interference at x. It rather measures the effect of the presence of a transmitter at x on the whole set of receivers. Consider a typical node at the origin, X 0 = 0, with marks p 0 , φ 0 . Let P 0 denote the Palm distribution of the stationary marked point process Φ [2, Chapter 1]. The fixed point equation determining the MAP of node X 0 = 0 reads (see ( 2))

1 p 0 = n =0 1 Yn α T r α 0 + 1 -p 0 .
We have a similar equation for each node and the sequence {pn} is readily seen to be a sequence of marks of Φ and its primary marks. It follows directly from monotonicity arguments that

1 p 0 < 1 ρ iff    n =0 ρ Yn α T r α 0 + 1 -ρ < 1    .
Notice that we have not used the specific assumptions on the point process so far. Hence we have the following general connection between the optimal MAP distribution and the shot noise J Φ r : Theorem 4.1: For all stationary marked point processes Φ (not necessarily Poisson), for all 0 < ρ < 1, P 0 (p 0 > ρ) = P 0 J Φ r \{Y0} (ρ, 0) < 1 , and P 0 (p 0 = 1) = P 0 J Φ r \{Y0} (1, 0) < 1 , with P 0 the Palm distribution of Φ. We now use the fact that Φ is an independently marked Poisson point process [2, Definition 2.1]. From Slivnyak's theorem [2, Theorem 1.13],

P 0 J Φ r \{Y0} (ρ, 0) < 1 = P (J Φ r (ρ, 0) < 1)
for all 0 ≤ ρ ≤ 1. Consequently, P 0 (p 0 > ρ) = P (J Φ r (ρ, 0) < 1) , and

P 0 (p 0 = 1) = P (J Φ r (1, 0) < 1) .
It follows from [2, Proposition 2.6] and from the fact that Φ r is a homogeneous Poisson point process that one can write the Laplace transform L J(ρ,0) (s) of the shot noise J Φ r (ρ, 0) as

L J(ρ,0) (s) = exp -2πλ ∞ 0 1 -e - sρr 0 r α +(1-ρ)r 0
rdr , [START_REF] Hajek | Stochastic approximation methods for decentralized control of multiaccess communications[END_REF] where r0 := T r α 0 . Theorem 4.2: Under the above Poisson assumptions, the attempt probability of the typical node has the distribution

P 0 (p 0 > ρ) = 1 2π ∞ -∞ L J(ρ,0) (iw) e iw -1 iw dw, (12)
with L J(ρ,0) (•) given by [START_REF] Hajek | Stochastic approximation methods for decentralized control of multiaccess communications[END_REF].

Proof: Let gρ(•) denote the density of the shot noise field J Φ (ρ, 0). Then

P 0 (p 0 > ρ) = 1 0 gρ(t)dt = ∞ -∞ gρ(t)u(t)dt,
where u(t) = 1 if 0 ≤ t ≤ 1 and 0 otherwise. Now using Parseval's theorem

P 0 (p 0 > ρ) = 1 2π ∞ -∞ F J(ρ,0) (w)F * u (w)dw,
with F A (w) = E exp(-iwA) the Fourier transform of the real valued random variable A and B * the complex conjugate of B. The claim follows after substituting Fu(w) = 1-e -iw iw and

F J(ρ,0) (w) = L J(ρ,0) (iw).
Remark 4.1: For α = 4, the Laplace transform L J(p,0) (s) can be simplified as

L J(p,0) (s) = exp -2πλ (1 -p)T r 2 0 1 0 1 -e -spv 2 /(1-p) v 2 √ 1 -v 2 dv .
2) Mean Utility: This subsection is devoted to the analysis of the mean value of the logarithm of the throughput of the typical node:

θ = E 0 log((p 0 )) + E 0 log((q 0 )),
with q 0 defined in [START_REF] Abramson | THE ALOHA SYSTEM: another alternative for computer communications[END_REF]. Since we know the cdf f of p 0 , the first term poses no problem. The second term can be rewritten as (see ( 1))

E 0 log((q 0 )) = E 0   n =0 log   1 - pn Xn-Y0 α T r α 0 + 1     .
Under the law P 0 , the points {Xn} n =0 of Φ form a homogeneous Poisson point process of intensity λ. However, the marks {pn} n =0 do not have the law identified in the last section. In fact, the mark pn of a point Xn (n = 0) satisfies the following modified fixed point equation:

1 pn = 1 Xn-Y0 α T r α 0 + 1 -pn + m =0,n 1
Xn-Ym α T r α 0 + 1 -pn ,
with the convention that pn = 1 if there is no solution in [0, 1]. We can use the same argument as above to conclude that

1 pn < 1 ρ iff ρ Xn-Y0 α T r α 0 + 1 -ρ + m =0,n ρ Xn-Ym α T r α 0 + 1 -ρ < 1.
Conditioned on there being two nodes at 0 and x, the other points form a homogeneous Poisson point process of intensity λ. This allows one to prove the following. Theorem 4.3: Under the above Poisson assumptions, given that there is a node at 0 and a node at x ∈ R 2 , the attempt probability of the node at x has the distribution

P 0,x (px > ρ) = 1 2π ∞ -∞ L Jx(ρ,0) (iw) e iw -1 iw dw, with L Jx(ρ,0) (s) = 1 2π 2π 0 exp - sρr 0 ||x -(r 0 , φ)|| α + (1 -ρ)r 0 dφ exp -2πλ ∞ 0 1 -e - sρr 0 r α +(1-ρ)r 0 rdr ,
and (r 0 , φ) := (r 0 cos φ, r 0 sin φ).

Due to the circular symmetry, the first integral in the expression of L Jx(ρ,0) (s) depends on x only through x . Thus the density of px also depends on x only, and it will be denoted by fr when x = r. The density of p 0 identified in the last subsection will be denoted by f . The main result of this section is: Theorem 4.4: Under the above Poisson assumptions, in the proportional fair case, the mean utility of a typical node is

θ = 1 0 log(u)f (du) + 1 2π φ∈(0,2π) x∈R 2 v log 1 - vr 0 ||x -(r 0 , φ)|| α + r 0 dφf ||x-(r0,φ)|| (dv)dx. ( 13
)
Proof: See Appendix A.

C. Discussion of the Other Cases

A preliminary concern when trying to use Euclidean stochastic geometry of the infinite plane in the maximum throughput and max-min fairness cases is that it is not clear whether the associated infinite dimensional optimization problems make sense in the first place. In the proportional fair case, each node computes its optimizing MAP in one step as the solution of a fixed point equation that is almost surely well defined (in terms of a shot noise) even in the infinite Poisson population case. Unfortunately, this does not extend to the other two cases.

This does not mean that there is no hope at all. Consider for instance the maximum throughput case accounting only for the closest interferer, and further simplify it by measuring interference at the transmitter rather than at the receiver. In other words, consider the same optimization problem as in Section III-D1 but with c(i) being the closest transmitter to transmitter i (rather than to receiver i). Then, in the Poisson case, the infinite dimensional optimization problem can be shown to reduce to a countable collection of finite optimization problems. This follows from the fact that there are no infinite "descending chains" in a homogeneous Poisson point process [10, Chapter 2] (a descending chain is a sequence of nodes i 1 , i 2 , . . . such that c(in) = i n+1 for all n). As a result, the Poisson point process can be decomposed into a countable collection of finite "descending trees", where each path from the leaves to the root is a descending chain. The associated optimization is hence well defined and the problem can be reduced to evaluating the solution of the optimization problem of Section III-D1 on the typical descending tree. Hence, there is hope to progress on this and on related cases. This will however not be pursued here and is left for future research.

V. NUMERICAL RESULTS

In this section, we study the proposed adaptive spatial Aloha schemes quantitatively. We compute various metrics formulated through the stochastic geometry based analysis, and we also perform simulation. The simulation not only validates the analytical model, but also illustrates the performance of schemes for which we do not have an analytical characterization.

A. Computation of the Integrals

We used Maple and Matlab to evaluate the integrals of Section IV. The infinite integral that shows up in the expression of the Laplace transform [START_REF] Hajek | Stochastic approximation methods for decentralized control of multiaccess communications[END_REF] is handled without truncation by Maple and Matlab. The singularity at w = 0 in the contour integrals (12) leveraging Parseval's theorem is a false singularity and it is also handled without further work by either Maple or Matlab. The Matlab code is particularly efficient and is used throughout the analytical evaluations described below.

B. Simulation Setting

We consider a two dimensional square plane with side length L, and N nodes placed independently over the plane according to the uniform distribution; this corresponds to λ = N/L 2 in the stochastic geometry model. 4 Each node has its receiver randomly located on the unit circle around it, again as per the uniform distribution. Thus r ii = 1 for all i. We set α = 4 and T = 10. To nullify the edge effect, we take into account only the nodes falling in the L/2 × L/2 square around the center while computing various metrics. While all other parameters remain, we vary L and N for different simulations. For each parameter set we calculate the average of the performance metric of interest over 1000 independent network realizations.

C. Joint Validation of the Analysis and the Simulation

We validate the analytical expression against the simulation for the case of proportional fair medium access. For illustration, we plot the cumulative distribution function (c.d.f.) of the MAP in Figure 2. Here we set L = 40 and consider two values of N , N = 400 and N = 800, which correspond to λ = 0.5 and λ = 0.25 respectively. The plots show that the stochastic geometry based formula (see Theorem 4.2) quite accurately predicts the nodes' behavior in simulation. We also study the distributions P 0,x (px > ρ) (also referred to as fr for x = r) defined in Theorem 4.3. Figure 3 shows their plots for λ = 0.25 and two values of x , x = 1 and x = 10. Again the plots based on the analytical expression and those based on simulation closely match. Clearly, under P 0 , nodes closer to the origin are more likely to be inactive.

D. Performance of the Adaptive Protocols

In this section we illustrate the performance of various adaptive schemes and their benefit over plain Aloha. We compute the performance metrics via simulation and also through analytical expressions whenever the latter are available. In such cases the analytical results and the simulation validate each other.

First we set L = 20 and N = 50. We consider the maximum throughput medium access, however, only accounting for the closest interferers. In figure 4, we show steady state behavior of our Gibbs sampling based algorithms; we have set the temperature τ (t) = 1/ log(1 + t). As expected, the improved maximum throughput medium access (see the discussion at the end of Section III-D1) insures a better exclusion behavior. Under this scheme, a lesser number of nodes transmit, and neighboring nodes are unlikely to transmit simultaneously. So, this is expected to deliver better aggregate throughput. Now we keep L fixed at 20, but vary N from 10 to 100; this corresponds to varying λ from 0.025 to 0.25 in the analytical expressions. We evaluate the aggregate throughputs of various Aloha schemes including plain Aloha. The average throughputs are plotted in Figure 5. Although in some of the schemes we derive the attempt probabilities only considering the closest interferers, we always take into account the aggregate interference while calculating the throughput. When the number of nodes is small, both the throughput maximizing medium access and plain aloha have identical performance; both prescribe attempt probabilities close to one for all the nodes. When the number of nodes increases beyond 45, the throughput maximizing medium access significantly underestimates the interference, and thus its performance deteriorates. On the other hand, the aggregate interference based proportional fair scheme significantly outperforms plain Aloha in terms of aggregate throughput also. This benefit is sustained even as the number of nodes increases. We also notice that the improved version of maximum throughput medium access (see the discussion at the end of Section III-D1) yields best performance among all the schemes, and its performance does not deteriorate until a much higher number of nodes. In Figure 6, we plot the logarithms of the aggregate throughputs corresponding to the two proportional fair medium access schemes. The figure illustrates that as the number of nodes increases, the performance of the closest interferer based medium access worsens in comparison to the performance of the aggregate interference based scheme -this is not visible merely looking at the corresponding aggregate throughputs (see Figure 5)).

In Figure 7, we plot the c.d.f. of the MAP for the proportional fair case. Our objective is to compare the case when nodes account for the aggregate interference with when they account for the closest interferer only. We set L = 40 and plot MAP distributions corresponding to two values of N , 400 and 800 (corresponding to λ = 0.25 and λ = 0.5 respectively). As expected, the nodes attempt more aggressively when they account for the closest interferer only. While there is a favored probability interval in the aggregate interference case, there are more than one such intervals in the closest interferer case. Also, in the latter case, about 34% of nodes attempt in almost all slots, irrespective of N , the total number of nodes. This can be understood by noticing that the probability that a node is not the closest interferer to any other node is not sensitive to N .

VI. CONCLUSION

We have shown the feasibility of the performance analysis of distributed adaptive protocols that aim at maximizing some global utility in a large random network using stochastic geometry.

More precisely, the most natural distributed adaptation of the medium access probability of Aloha that aims at proportional fairness optimization was shown to have a tractable optimal MAP distribution. This distribution is obtained from the law of a certain shot noise field that describes the interference created by a typical node to all receivers but his. In the Poisson case, the distribution of the optimal MAP is obtained as a non-singular contour integral which is amenable to an efficient evaluation using classical numerical tools. The network performance at optimum can in turn be deduced from the latter using Campbell's formula.

This approach is shown to provide an analytic way of quantifying the gains brought by this proportionally fair adaptive version of Aloha compared to plain Aloha.

This line of thoughts opens several research directions. The first one is the extension to other types of fairness, still in the framework of Aloha. We indicate that this is possible at least under certain simplifications of the interference model. The second and broader question is whether this approach can be extended to MAC protocols other than Aloha. An example would be an adaptation of the exclusion radius of CSMA/CA to the full environment of a node aiming at maximizing some utility of the throughput. A third general question concerns the evaluation of the "price of decentralization". When the discussed protocols are suboptimal because of their greedy/distributed nature, is it possible to use stochastic geometry to evaluate the typical discrepancy between the performance of the distributed scheme and the optimal centralized one? where the last relation follows from Slivnyak's theorem.

Fig. 1 .

 1 Fig. 1. A snapshot of bipolar MANET with Aloha as the medium access protocol. The diamonds represent transmitters, and the connected circles the corresponding receivers. The solid diamonds represent the nodes that are transmitting in a slot.

Fig. 2 .

 2 Fig. 2. Cumulative distribution function of the MAP for the proportional fair case.

Fig. 3 .

 3 Fig. 3. Demonstration of fr, the MAP distribution of a node at distance r from origin, under P 0 .

Fig. 4 .

 4 Fig.[START_REF] Baccelli | An Aloha protocol for multihop mobile wireless networks[END_REF]. Throughput maximizing medium access: There are 100 transmitter receiver pairs. The diamonds represent candidate transmitters, and the connected circles the corresponding receivers. The solid diamonds represent the nodes that transmit in all the slots; others never transmit. The left plot corresponds to the maximum throughput medium access and the right one to its improved version.

Fig. 5 .

 5 Fig. 5. Throughputs of various medium access schemes as a function of the number of nodes. MT, PF, CI and AI stand for maximum throughput, proportional fair, closest interferer and aggregate interference respectively.

Fig. 6 .

 6 Fig. 6. Performance of the two proportional fair medium access schemes as a function of the number of nodes.

Fig. 7 .

 7 Fig. 7. Cumulative distribution function of the MAP for the proportional fair case.

  convention if there is no solution in [0, 1]. It follows from Slivnyak's theorem that h(||Xn-Y 0 ||, Φ r \ {Y 0 , Yn} • θ Xn ) -(r 0 , φ)||, Φ r \ {Yn} • θ Xn ) -(r 0 , φ)||, Φ r \ {Yn} • θ Xn ) r 0 , φ)|| α + r 0 λdx P 0 (h(||x -(r 0 , φ)||, Φ r \ {Y 0 }) = dv) = R 2 v log 1 -vr 0 ||x -(r 0 , φ)|| α + r 0 )λdx P(h(||x -(r 0 , φ)||, Φ r ) = dv),

A finite snapshot of a Poisson random proces would contain a Poisson distributed number of nodes. However, for large λL 2 , the Poisson random variable with mean λL 2 is highly concentrated around its mean. Thus we can use λL 2 nodes for all the realizations in our simulation.

VII. ACKNOWLEDGMENTS This work was carried out at Laboratory of Information, Networking and Communication Sciences (LINCS) Paris, and was supported by INRIA-Alcatel Lucent Bell Labs Joint Research Center.

APPENDIX Let Ψ = {Y ′

m } be a point process with marks and ψ • θz be the point process ψ shifted by -z. Given that Y 0 = (r 0 , φ),

where the mapping h(u, Ψ) associates with Ψ and the real number u the solution of


Adrien Vogt-Schilb

Stéphane Hallegatte
email: shallegatte@worldbank.org

When Starting with the Most Expensive Option Makes Sense On Marginal Abatement Cost Curves and Optimal Abatement Pathways

Keywords: optimal timing, inertia, sectoral policies, dynamic eciency

This paper investigates the optimal implementation schedule of the measures listed in a Marginal Abatement Cost Curves (MACC). Costs and abating potentials of each measure, provided by a MACC, are completed with a maximum implementation speed. We nd that, when coping with a carbon budget, it makes sense to implement some expensive options before exhausting the abating potential of the cheapest options. With abatement targets expressed in terms of emissions at one point in time, e.g. reducing emissions by 20% in 2020 and by 75% in 2050 it can be preferable to start with the most expensive options if their potential is higher and their inertia is great. The best strategy to reach a short-term target depends on whether this target is the ultimate objective or there is a longer-term target. Using just the cheapest options to reach the 2020 target may create a carbon-intensive lock-in and make the 2050 target unreachable. Results suggest that a unique carbon price in all sectors may not be the most ecient approach. Additional sectoral policies, such as the 20% renewable energy target in Europe, may be part of an ecient mitigation policy.

Highlights

MACCs are not abatement supply curves: listed activities may take decades to implement.

Extending MAC curves with inertia changes the optimal order of abatement options.

Reaching short-term targets with cheap options may cause carbon-intensive lock-in.

Using expensive but high-inertia options in the short term may be optimal.

A carbon price could usefully be combined with complementary sector-or technology-specic policies.

Introduction

To design the best policies to cope with climate change, decision-makers need information about the options for reducing greenhouse gas (GHG) emissions. Such information has been provided to the public in many ways, including through Marginal Abatement Cost (MAC) curves. We call measure-explicit MACCs the curves that represent information on abatement costs and potentials for a set of mitigation measures (here, we simply refer to them as MAC curves or MACCs). 1 These MACCs are usually constructed for a specic country or region, and for a specic time horizon. They report abatement potentials that can be achieved as a function of the abatement cost, ranking potential mitigation options from the least to the most expensive (Fig. 1). .N characterized by their maximum potential amax and their abatement cost c, ranked from the least to the most expensive. This curves stands for a given date in the future T. We nd, maybe counter-intuitively, that the optimal mitigation strategy to reach a short-term target X is not to implement exclusively the measures cheaper than Y.

Marginal cost $/tCO

In this paper, we investigate which options from a MACC should be used to achieve a given abatement target, and in which order these options should be implemented. To do this, we complete the information on costs and potential from a MACC with information on the implementation speed of each measure. This maximum implementation speed makes it possible to distinguish available abatement measures not only using their costs and potentials, but also the time it takes to implement them. For instance, it accounts for the fact that urban planning may be cheaper and may have a higher potential to reduce emissions than technological change in the car industry, but is also much slower and requires much more anticipation to be eective [START_REF] Gusdorf | Time and space matter: How urban transitions create inequality[END_REF]. We then use an inter-temporal optimization model to investigate the optimal timing for abatement of GHG emissions (choice across time) along with the optimal dispatch of the reduction burden (choice across abatement measures).

The rest of the paper is organized as follows. Section 2 proposes a review of the literature on the MACCs methodology and limits. In Section 3, we present our model. Then, we use it in Section 4 with an objective in terms of cumulative emissions over a long period, a so-called carbon budget, which is reportedly a good proxy for climate change. We nd that it makes sense to implement the more expensive options before exhausting the whole potential of the cheapest options. Also, it may be optimal to use expensive options even when cheap ones are sucient to reach the abatement target, in order to delay action and save present value. We then turn to objectives expressed in terms of aggregate abatement at one point in time, closer to the actual practices. In that case, we nd that it can be preferable to start by implementing the most expensive options, if their potential is large and their inertia is great (Section 5.1). An other counterintuitive result is that MACCs should not be used as supply curves when choosing the optimal strategy to achieve short-term emission targets, as the optimal short-term strategy actually depends on the long-term emission objective (Section 5.2). We conclude in section 6.

Literature on measure-explicit MAC curves

Since the rsts proposals by [START_REF] Jackson | Least-cost greenhouse planning supply curves for global warming abatement[END_REF], [START_REF] Rubin | Realistic mitigation options for global warming[END_REF] and [START_REF] Stoft | The economics of Conserved-Energy "Supply" curves[END_REF], measure-explicit MACCs have been used to characterize available options to mitigate GHG emissions (or to save energy) in terms of their abatement potential (respectively energy saving potential) and abatement cost. More recently, McKinsey and Company have published measure-explicit MACCs assessing potentials in 2030 at the global scale [START_REF] Mckinsey | Pathways to a low-carbon economy: Version 2 og the global greenhouse gas abatement cost curve[END_REF]. The World Bank has assessed reduction potentials of many countries in the form of MACCs (e.g., [START_REF] Johnson | Low-Carbon development for mexico[END_REF]). Also, [START_REF] Sweeney | Analysis of measures to meet the requirements of california's assembly bill 32[END_REF] have proposed a MACC for California in 2020.

2 Recent research has identied and proposed solutions for methodological issues when building measure-explicit MAC curves; this has allowed to enhance the reporting of abatement costs and potentials.

A rst issue relates to uncertainty when assessing future costs. It is commonly addressed by presenting ranges of costs and potentials instead of just two gures (IPCC, 2007, SPM6 p.11). A second issue comes from the interaction between dierent measures (e.g, promoting electric vehicles and green electricity together would allow to save more GHG than the sum of the two isolated abatement measures). This can be tackled by using integrated models to build the MACCs [START_REF] Kesicki | Marginal abatement cost curves: Combining energy system modelling and decomposition analysis[END_REF]. Also, future abatement costs at a given date (e.g. 2030) will depend on previous eorts to reduce GHG emissions, and on expectations about the future price of carbon. Kesicki (2012a) studies this question by testing dierent abatement pathways, along with dierences in social and private discount rates. Other issues are more dicult to address, like the fact that MACCs neglect non-climate benets such as air pollution reduction or increase in energy security , or that they assess project or technological costs only, excluding institutional barriers, transaction costs and non-monetary costs [START_REF] Kesicki | Marginal abatement cost curves: a call for caution[END_REF].

Our contribution is an investigation of how the information presented in a MACC could be used to decide which options to use and in which order to achieve a given abatement target. To do so, we characterize each option by their inertia, in addition to their cost and abating potential.

Model description

A social planner controls GHG abatements from an emission baseline, by spending money on a set of options described by their cost and abatement potential. We do not incorporate more realistic but complex dynamics, such as sectoral interactions, crowding-out eect on investment, or learning-by-doing [START_REF] Del Rio Gonzalez | Policy implications of potential conicts between short-term and long-term eciency in CO2 emissions abatement[END_REF][START_REF] Kalkuhl | Learning or lock-in: Optimal technology policies to support mitigation[END_REF]. Instead, we only extend the MACC with information on how long it takes to implement each of the measures.

GHG emissions

There are N abatement options, indexed by i. The model is run on a period that goes from 2000 to 2050 with a time step, ∆t, of 0.25 years. At each time step t, emissions are computed from the baseline emissions E base (t) and the abatement a(i, t) achieved with each measure i at time t.

E(t) = E base (t) - N i=1 a(i, t) (1)
We assume constant baseline emissions, that is E base (t) = 5 GtCO 2 /yr. The cumulative emissions M (t) are then computed as the sum of emissions:

M (0) = 0 (2) M (t) = E(t) • ∆t + M (t -∆t) (3)
2 For a more comprehensive review of existing MACCs, see Kesicki (2012a)

Potentials, costs and inertia

Abatements eorts in each sector are subject to two restrictions. First, each measure i has a maximum abating potential a max (i), expressed in avoided annual emissions, in MtCO 2 /yr. For instance, switching to more ecient thermal engines for passenger vehicles may save a fraction of GHG emissions associated with private mobility, but not more. In MACCs, this potential is commonly represented by the width of the rectangles (see Fig. 1).

a(i, t) ≤ a max (i) (4)
In the MACC, each measure i is qualied with a constant abatement cost c(i) the heights in Fig. 1.

Here, we also assume that abatement costs are independent of cumulative abatements and time. Abatement a(i, t) achieved thanks to measure i at time t has a cost I(i, t) which reads:

I(i, t) = a(i, t) • c(i) (5)
So far, the model could be calibrated with data from a MACC. We add an explicit representation of economic inertia, in the form of a measure-specic constraint on implementation pace. A given amount of abatement requires a non-negative amount of time for its implementation. This is modeled as a maximum speed α(i), (in MtCO 2 /yr per year), assumed to be independent of the nancial cost of the option 4 : achievable abatements at time t directly depend on already achieved abatements at time t -∆t.

a(i, t) ≤ a(i, t -∆t) + α(i) • ∆t (6)
For simplicity, we assume that α(i) is constant and does not depend on the previously achieved abatements nor current time step t. This modeling diers from the time-to-build à la [START_REF] Kydland | Time to build and aggregate uctuations[END_REF]. Time-to-build would reect the idea that there is an incompressible lag between investment decisions and actual abatements.

With time-to-build, an arbitrary large amount of abatement would require as much time to be implemented as a small abatement (if achieved through the same measure). In our framework, in contrast, the required time lag is proportional to the amount of abatement.

These costs in time may come from any bottleneck, such as (i) availability of skilled workers, (ii) availability of productive capacities, (iii) incompressible institutional requirements, or other factors such as (iv) emissions embedded in long-lived capital. Issues (i) and (ii) could be overcome by training workers or redirecting unemployed workers and unused capital; but training and redirecting are measures per se and cannot be done overnight either. The issue of institutional or organizational delays is well documented (World Bank, 2010). Reducing them is also a measure per se, and takes time. The last point is related to capital vintages and turnover: if one sees emissions as embedded in capital [START_REF] Davis | Future CO2 emissions and climate change from existing energy infrastructure[END_REF], decarbonization cannot be faster than capital turnover, except by wasting valuable productive capital through premature replacement [START_REF] Lecocq | Decision making under uncertainty and inertia constraints: sectoral implications of the when exibility[END_REF].

The value of α for a given measure can be assessed from available data. For instance, if cars are typically scrapped 12 years after they are manufactured, switching from conventional cars to plug-in hybrids would 4 Note that abatement is expressed in MtCO 2 /yr. 4 take at least 12 years. Taking into account slow technological diusion [START_REF] Guivarch | Existing infrastructure and the 2C target[END_REF] sales are not likely to switch overnight from 100% conventional cars to 100% plug-in hybrid cars , it can take as long as 30 years (IEA, 2009a). This full implementation time T f is linked to the abatement potentials a max and the maximum speed α:

T f (i) = a max (i) α(i) (7)

Social planner objectives

The objective is to achieve a climate-related target while minimizing abatement costs. The social planner minimizes C, the total present cost of abatements, discounted at rate ρ over the period:

C = T t=0 N i=1 I(i, t) (1 + ρ) t•∆t (8)
Theoretically, the social planner could control GHG emissions in order to equalize the marginal costs of mitigation and adaptation in a cost-benet approach. Because of uncertainty surrounding both climate response to a change in GHG emissions and adaptation costs, and because decisions are made at national instead of global scale, it is common to adopt a cost-eectiveness approach [START_REF] Ambrosi | Optimal control models and elicitation of attitudes towards climate damages[END_REF].

In our model, this can be done by constraining cumulative emissions M to remain below a given carbon budget M obj .

M (t) ≤ M obj (9)
Cumulative emissions over a long period can be used as proxies for climate change [START_REF] Matthews | The proportionality of global warming to cumulative carbon emissions[END_REF]. In practice, however, governments and other public agencies frequently provide objectives for given points in time. For instance, the EU has the objective of cutting its emissions by 20 % of 1990 levels by 2020.

5

In our model, these objectives can be implemented by dening a set of milestones indexed by m, and by constraining emissions at each milestone:

E(t m ) ≤ E obj m (10)

Numerical values

For illustrative purpose, we assume a MAC containing only two contrasted measures (N = 2), labeled cheap and deep. Cheap has a lower abatement cost than deep, but also a lower abatement potential (see Tab. 1 and Fig. 2). Cheap could represent for instance the measure of switching energy sources in buildings, and deep could represent the retrotting of these buildings. In the auto industry, cheap could represent the energy eciency gains in the internal combustion engines and deep switching to other energy sources, such as electricity or biofuels.

In the absence of reliable data, we assume that it takes 70 years to implement the whole potential of deep, while cheap only requires 25 years. Applying Eq. 7 gives values for α of respectively 50 MtCO 2 /yr 2 and 60 MtCO 2 /yr 2 . We also use a discount rate ρ = 5%/yr. These values are not meant to represent accurately concrete sectors of the economy, even though they do not dier much from the two sectors modeled by [START_REF] Lecocq | Decision making under uncertainty and inertia constraints: sectoral implications of the when exibility[END_REF]. We use them to carry out illustrative experiments, which help draw more general conclusions.

We solve this simple model using a linear programing algorithm provided by GAMS [START_REF] Brook | GAMS, a user's guide[END_REF]. The source code also uses Scilab (Scilab Consortium, 2011). Code and data are available on the corresponding author's web page. Figure 2: The MACC used in our experiments. We nd that the long-term target of 3.75 GtCO2/yr should not be achieved by implementing rst cheap and then deep. We also nd that a short-term abatement target of 750 MtCO2/yr should not be achieved implementing just cheap.

Figure 3: Left: Optimal abatement strategy to limit cumulative emissions below 175 GtCO2 between 2000 and 2050.

Because of inertia and discounting, deep has to enter before the potential of cheap has been exhausted. Right: curves represent emissions in the baseline and in the constrained simulation; in-between areas represent the cumulative abatement and the carbon budget in the constrained simulation.

Optimal implementation schedule to cope with a carbon budget

In this section, we investigate the optimal abatement pathway when using a carbon budget, i.e. with full exibility on when to reduce emissions. This is implemented in our model by excluding Eq. 10, and including Eq. 9. We then test a range of carbon budgets (M obj ), and assess the consequence on the optimal reduction pathway.

Using expensive options before exhausting the potential of cheap ones

Figure 3 shows the optimal strategy for maintaining cumulative emission below 175 GtCO 2 over the 2000-2050 period.

Figure 4: Entry date and ceiling date of each abatement as a function of the carbon budget. "Start of deep/cheap" is the date when the respective measure begins to be implemented; the ceiling date is the date when the abating potential is exhausted.

The abatement paths (gure 3, left panel) have triangular or trapezoidal shapes; this shows that one of the inertia (Eq. 6) or maximum potential (Eq. constraint is binding. The cumulative corresponds the area between baseline emissions and emissions in the constrained run (gure 3, right panel). In this case, the intuitive ranking of abatement measures is respected: the social planner starts by implementing cheap before deep. However, she does not use the whole potential of cheap before starting using deep. Deep enters in 2023 while cheap does not reach its full potential before 2027. A more stringent objective would force deep to start even earlier (see below).

The optimal implementation strategy does not follow a merit order in which the whole potential of the cheapest solutions is used before more expensive solutions are introduced.

A more systematic analysis using a range of carbon budgets (Fig. 4) conrms that for any objective it is never preferable to implement the expensive deep before cheap. It also shows that if the objective is stringent enough (about 195 GtCO 2 ), deep has to begin before the whole potential of cheap has been exploited the implementation is not sequential. And if the carbon budget is even more stringent (about 130 GtCO 2 ), deep is forced to start in 2000, at the same time as cheap.

Expensive options may be useful even when cheaper ones appear sucient

Let us analyze a case in which the carbon budget is not very stringent, e.g. 210 GtCO 2 . This translates into cumulative abatements of 45 GtCO 2 over the period.

7 Cheap has a cumulative abatement potential of more than 55 GtCO 2 .

8 It is then possible to achieve the abatement objective by implementing only cheap. An intuitive strategy could be to focus on cheap and to not implement deep. Our simulation show that this is not the optimal strategy, because there is a trade-o between (i) implementing only the cheapest solutions, but starting early to give them enough time to reach the objective; (ii) delaying abatements in order to save present value (thanks to the discounting), but undertaking both cheap and deep to be more aggressive later and reach the objective in spite of the delayed action.

In our simulations (Fig. 4), the optimal strategy to meet a (lax) 210 GtCO 2 carbon budget is to implement deep from year 2040, which makes it possible not to implement cheap before 2011 (for a strategy starting in 2000). The additional cost of using deep is more than compensated by the delay on implementing cheap. In other words, the optimal strategy uses an expensive measure even when a cheaper measure appears sucient to fulll the objective.

Policymakers and the public should be informed of abatement potentials and costs, and MAC curves provide this information. But they also need to be informed on the duration of the implementation process of these measures. MACC providers could enhance their reporting with this information.

Optimal abatement pathways with emission targets

Commitments in terms of carbon budget are dicult to enforce: there is an incentive for decision-makers to delay investments and eorts beyond their mandate. Alternative policies include the denition of emission targets at one or several points in time. Short-term targets can be enforced with tradable emissions permits, such as the EU ETS system. In the next two sections, we assume that commitments are made in terms of abatement levels at dierent points in time.

Cumulative-emissions constraint (Eq. 9) is thus excluded from the model, we include the emission constraint with a single milestone (m ∈ {1}, t 1 = 2050) and we test various emission objectives (E obj 1 in 10). In absence of inertia i.e. an innite α in Eq. 6 the optimal response to an emission objective would be to remain on the baseline emissions pathway from 2001 to 2049, and to implement abatement options in 2050 only. 9 We nd that with inertia i.e., with a nite α in Eq. 6 the shape of the optimal mitigation strategy depends on the stringency of the emission target.

Implementing expensive options before cheap ones

Figure 5 shows the optimal abatement pathway for achieving an ambitious reduction of 75% of emissions in 2050. In this case, the optimal strategy is to start by implementing the most expensive option before the cheapest (i.e., deep before cheap).

Indeed, the emission objective translates into abatements by 3.75 GtCO 2 /yr in 2050, which cannot be achieved by implementing cheap alone. The cheapest way to achieve this objective in 2050 is to use cheap to abate as much GHG emissions as possible, i.e. 1.5 GtCO 2 /yr. Because cheap cannot penetrate faster than 60 MtCO 2 /yr 2 , it has to enter in 2026. Then 2.25 GtCO 2 /yr remain to be abated with deep by 2050. To do so, deep has to enter as soon as 2006, 20 years before cheap.

The 75% reduction in emissions leads to cumulative emissions of 175 GtCO 2 , and is thus comparable to the simulation proposed in Section 4.1.

10 Compared to the carbon budget simulation (CB), this simulation with emission targets (ET) leads to start cheap later and deep sooner. Short-term abatements are lower in 2020, they amount to 750 MtCO 2 /yr in ET, against 1.3 GtCO 2 /yr in CB but long-term abatements are higher.

The loss of when-exibility eventually raises the present cost of abatements, from 390 G$ in the CB case to 630 G$ in the ET simulation for the same nal cumulative emissions.

11

This illustrates the fact that, compared to emission objectives, carbon budgets with full when-exibility allow the social planner to reach the same climate target at lower cost.

A more systematic analysis is presented in Fig. 6. It gives the optimal entry dates of both measures (cheap and deep), as a function of the 2050 emission target. It shows that below a threshold emission target, the optimal strategy starts to implement the expensive, inert and high abating potential measure before the cheap one. In our example, this happens when the emission target is lower than 2.25 GtCO 2 /yr i.e.

when the abatement objective is higher than 2.75 GtCO 2 /yr. 9 One could say that this would be done by starting with the cheapest measure and continuing with the more expensive one until the emission objective is achieved. In this context, however, the terms starting and continuing would not have a chronological meaning, as the abatement measures would both be implemented in 2050. Instead, those words would denote the fact that the social planner, while designing the optimal strategy, would rst consider to implement cheap and then to implement deep.

Figure 5: Optimal abatement pathways to achieve ambitious abatements (3.75 GtCO2/yr) in 2050. The expensive option with large abatement potential is implemented before the cheaper option.

Figure 6: Entry date of each measure as a function of emission objective for 2050. For ambitious emission targets (below 2.25 GtCO2/yr), the expensive option with large abatement potential is implemented before the cheaper option.

a. Short-term and Long-term objs.

b. Short-term Only Figure 7: Comparison of optimal abatement strategies to reach the same target for 2020, taking into account or disregarding the longer-term 2050 objective (respectively S&L and SO). With an ambitious long-term target, the short-term strategy is based on the more expensive option with higher abatement potential, not on the cheapest option.

The fact that, with emission targets, expensive options may have to be implemented before cheap ones illustrates that, in presence of inertia, marginal abatement costs should not necessarily be equal across sectors [START_REF] Vogt-Schilb | How inertia and limited potentials aect the timing of sectoral abatements in optimal climate policy[END_REF]. It also poses a practical problem. Considering the diculty in creating a credible long-term signal for the price of carbon and in government ability to commit in general [START_REF] Kydland | Rules rather than discretion: The inconsistency of optimal plans[END_REF][START_REF] Dixit | Interactions of commitment and discretion in monetary and scal policies[END_REF], economic actors cannot rely on long-term prices. If actors consider only the current carbon price, then a carbon price of 60 $/tCO 2 would be necessary to trigger the entry of deep (see Tab.1). Fig. 5 shows that this measure should be implemented as early as 2005 to reach the stringent objective (emissions of 750 MtCO 2 /yr in 2050) at the lowest possible cost. But this high carbon price would also trigger the implementation of cheap (because its abatement cost, 30 $/tCO 2 , is lower than the signal) in 2005, i.e. too soon, leading to a suboptimal abatement pathway.

The inuence of long-term objectives on short-term strategies

Actual policies include shorter-term emission objectives, such as the EU target to abate emissions by 20% or 30% in 2020. Short-term targets are a priori relevant because there is visibility over the short term on technology availability, macroeconomics trends and institutional frameworks. But they are only a milestone toward a more ambitious climate target in the long run, as the -75% by 2050 objective in Europe.

In this section, we nd that it is dangerous to use only information on costs and abating potential to decide which measures to implement in order to achieve the intermediate target, because it can make the long term target impossible to reach.

We compare two simulations. The rst simulation, labeled SO (Short-term Only), has a short-term constraint for 2020, but no long-term constraint:

E obj 1 = E(2020) = 4.25 GtCO 2 /yr (11)
The second simulation, S&L (Short-term and Long-term objectives), has the same short-term target for 2020, and a longer-term constraint: a reduction by 75% of GHG emissions in 2050. In this simulation, there are thus two emission milestones (see Eq. 10):

E obj 2 = E(2050) = 1.25 GtCO 2 /yr (12) E obj 1 = E(2020) = 4.25 GtCO 2 /yr ( 13
)
Our objective is to assess the dierence over the short-term between a strategy aiming at a short-term target and a strategy aiming at both short-term and long-term targets. We nd that long-term objectives impact strongly the short-term strategy. and uses cheaper and lower-potential options, namely cheap and deep instead of deep only. The discounted expenditures in abatement measures amounts to 28 G$ against 112 G$ when the 2050 objective is taken into account: the optimal short-term nancial eort is much higher if the long-term target is taken into account, even though the abatement in MtCO 2 is the same.

If the 2050 target is not taken into account before 2020, it may then appear extremely costly or even impossible to achieve. In this illustrative example, the 75% reduction in emissions becomes indeed impossible to achieve in 2050 in this case.

12 Despite short-term aggregate emissions being abated to the same level in SO as in S&L by 2020, the Short-term Only (SO) strategy produces a lock-in in a carbon intensive pathway that cannot be reversed in the second period. In other words, the optimal strategy to reach the 2020 target is dierent (it uses more expensive options) if the 2050 objective is included in the optimization. With an ambitious long-term objective, the short-term target needs to be achieved implementing the options with the largest potentials and the greatest inertia, not with the cheapest solutions.

Conclusion

This paper investigates the use of measure-explicit MAC curves to design optimal abatement strategies taking inertia into account. Inertia is modeled as a maximum amount of abatement that can be achieved over a given period of time with a given measure from a MACC. This maximum implementation speed complements the cost and abating potential already provided by existing MACCs. It has a large inuence on the optimal schedule of the various abatement measures.

In particular, optimal abatement strategies may (i) implement expensive options before the whole potential of cheaper measures has been exploited; (ii) use expensive options even when cheap ones appear sucient to meet the climate target; or (iii) start to implement expensive options before cheap ones. If the climate objective is stringent and their inertia is large enough, the optimal strategy would be to start implementing at the same time a set of measures covering a wide range of abatement costs.

These results conrm the need to account for specic inertia when designing climate policies. Transforming climate objectives into emissions pathways cannot be done with aggregate models if perfect foresight and long-term policy credibility are not assumed. Without these assumptions, emissions pathway need to be multi-sectoral, distinguishing in particular heterogeneous capital turnovers [START_REF] Lecocq | Decision making under uncertainty and inertia constraints: sectoral implications of the when exibility[END_REF][START_REF] Jaccard | Heterogeneous capital stocks and the optimal timing for CO2 abatement[END_REF][START_REF] Vogt-Schilb | How inertia and limited potentials aect the timing of sectoral abatements in optimal climate policy[END_REF].

This has some implication for current mitigation policies. In the European Union, there is currently a debate on whether aggregate GHG emissions should be abated by 20% or 30% in the short-term (i.e.

2020). This question on when to abate GHG emissions cannot be separated from the question on how these abatements have to be done (i.e., in which sector and with which measures). Economic actors might otherwise focus on cheap and fast-to-implement solutions to reach the short-term target, neglecting highpotential but high-inertia options which may be required to meet an ambitious objective in 2050. For this reason, the optimal approach to achieve a given abatement target at one point in time may not be to set a carbon price and introduce all the abatement options that show an abatement cost below this carbon price.

It may be preferable to use additional policies, targeted at high-potential but long-to-implement options, such as urban planing or deployment of low-carbon technologies.

There is of course a balance to maintain [START_REF] Azar | The elusive quest for technology-neutral policies[END_REF]: sectoral policies should be targeted enough to distinguish dierences in inertia, but broad enough to let economic agents select the best options and technologies to reach them (this is for instance the case of existing fuel economy standards in the auto industry). Because of information asymmetry and the risk of rent-seeking behavior, micro-managing mitigation by dening over-targeted objectives can be counter-productive [START_REF] Laont | Political economy, information, and incentives[END_REF]. Also, objectives need to be updated when new information is available [START_REF] Rodrik | Normalizing industrial policy. Commission for Growth and Development[END_REF]; for instance if one measure turns out to be more expensive, or turns out to save less GHG, than expected. Finally, if these sectoral policies overlap, they may come with additional costs that should be analyzed carefully [START_REF] Braathen | Instrument mixes for environmental policy: How many stones should be used to kill a bird?[END_REF][START_REF] Böhringer | Green promotes the dirtiest: on the interaction between black and green quotas in energy markets[END_REF][START_REF] Fischer | Combining policies for renewable energy: Is the whole less than the sum of its parts?[END_REF] and taken into account.

Our results are still theoretical, based on illustrative examples. We propose that MAC providers enhance their reporting to the decision-makers and the public, supplying also an assessment of the implementation speed of each option. With this information, the simple model proposed in this paper could be used to assess the optimal implementation schedule of the various existing abating options. Short-term sectoral or technological targets (e.g for 2020 or 2030) could then be derived from these pathways. This process would provide gures to debate new or existing sectoral policies, such as the objective of 20% of renewable energies in 2020, the fuel economy standards in the auto industry, or proposed changes in land-use planning, building norms and infrastructure design.

X

  Figure1: A measure-explicit MAC curve exhibits abatements options 1..N characterized by their maximum potential amax and their abatement cost c, ranked from the least to the most expensive. This curves stands for a given date in the future T. We nd, maybe counter-intuitively, that the optimal mitigation strategy to reach a short-term target X is not to implement exclusively the measures cheaper than Y.

  3

Figure 7

 7 Figure7compares the optimal abatement strategies from 2000 to 2020 in the two cases. With both the 2020 and the 2050 objectives (simulation S&L, panel a.), the social planner starts by implementing deep in 2006, and does not implement cheap before 2020 (as in Section 5.1). In contrast, when the 2050 milestone is disregarded (simulation SO, panel b.), the social planner starts abating later(in 2010 vs 2006)

Table 1 :

 1 . Numerical assumptions

		Cost	Abatement potential	Growth constraint	Implementation time
		c	a max	α		a max /α
		$/tCO 2	MtCO 2 /yr	MtCO 2 /yr	2	yr
	Cheap	30	1 500	60		25
	Deep	60	3 500	50		70

Note that time considerations are already included in the building process of the MACCs, and play an important role in assessing both the potential and the cost of each options(Kesicki, 2012a). However, the resulting MACC does not report any information on inertia, making it dicult to build optimal strategies from MACCs only. One conclusion will be that this information on time could be displayed along with information on costs and potentials nearby the MACCs to allow a debate on optimal implementation schedules of the presented mitigation options using these extended MACCs.

It is also common to adopt intensity objectives, as the eciency standards in the auto industry. Our model may be used with existing intensity MACCs(IEA, 2009b, p. 37).

This value is used for illustrative purpose, and will allow us to make some comparisons with subsequent simulations (in Section 5).6 Cumulative emissions in the baseline amount to 5 Gt/yr during 51 years, with a total of 255 Gt. The carbon budget thus amounts to 69% of cumulative emisions.

Cumulative emissions in the baseline amount to 5 Gt/yr during 51 years, with a total of 255 Gt.

Its annual abatement potential is 1.5 Gt/yr and takes 25 years to implement in full (see Tab. 1); adding the cumulated potential during the take-o phase (25 yr × 1.5 Gt/yr)/2 and the potential when annual abatements have reached their maximum value 25 yr×1.5 Gt/yr gives a total of 56.25 Gt.

Since cumulative emissions are good proxies for climate change, both simulations would lead to comparable climate change impacts.

In other words, 390 G$ is the lowest possible cost to reach the carbon budget constraint, while 630G$ is the lowest cost for reaching the same carbon budget through one aggregate emission target in 2050.

Cheap has entered in 2006. It would reach its full potential (1.5 Gt/yr) in 2030. If deep enters in 2021, it would also reach abatements of 1.5 Gt/yr in 2050, 30 years after (30 yr × 50 MtCO 2 /yr). The total would be abatements of 3 Gt/yr in 2050, when the target is 3.75 Gt/yr.

Acknowledgments

The authors wish to thank Nils Axel Braathen, Marianne Fay, Michael Grubb, Jean Charles Hourcade, Fabian Kesicki, Camille Mazas, Guy Meunier, Julie Rozenberg, the audiences at the International Energy Workshop ( 2012), at the European Association of Environmental and Resource Economists Conference (2012), at the International Association of Energy Economics (2012) and at the CIRED seminar who provided useful comments. We also thank Patrice Dumas for technical support. The remaining errors are entirely the authors'.

The views expressed in this paper are the sole responsibility of the authors. They do not necessarily reect the views of the World Bank, its executive directors, or the countries they represent.