Geir B Asheim
email: g.b.asheim@econ.uio.no.

Stéphane Zuber
email: stephane.zuber@univ-paris1.fr.

Rank-discounting as a resolution to a dilemma in population ethics *

Keywords: Social evaluation, population ethics, rank-dependent welfare. JEL Classification numbers: D63, D71

When evaluating well-being distributions in an anonymous (and replication invariant) manner, one faces a dilemma between (i) assigning dictatorship to a single worst-off person, thus succumbing to a tyranny of non-aggregation and (ii) assigning dictatorship to (unboundedly) many better-off persons, thus succumbing to a tyranny of aggregation. We show how this corresponds to a population-ethical dilemma in the variable population setting between, on the one hand, a reversed repugnant conclusion (preferring a very small population with high well-being) and, on the other hand, a repugnant conclusion (preferring a sufficiently large population with lives barely worth living to a population with good lives) or very sadistic conclusion (not preferring a large population with lives worth living to a population with terrible lives). The dilemma can be resolved by relaxing replication invariance and thus allowing that evaluation in the fixed population setting might change with population size even though the relative distributions of well-being remain unchanged. Rank-dependent criteria are evaluation criteria that resolve this dilemma but fails replication invariance. We provide conditions under which rank-dependent criteria are the only way out of the dilemma. Furthermore, we discuss the following consequence of relaxing replication invariance: It becomes essential to take into account the existence and utility of non-affected people when evaluating population policies with limited scope.

Introduction

One prominent population ethics view is that there exists a critical level of lifetime well-being which, if experienced by an added individual without changing the well-being levels of the existing population, leads to an alternative which is as good as the original. Combined with a prioritarian criterion where, for fixed population size, the undiscounted sum of the individuals' transformed utilities is maximized, this leads to critical-level prioritarianism (also known in the economics literature as critical-level generalized utilitarianism; [START_REF] Blackorby | Social criteria for evaluating population change[END_REF][START_REF] Broome | Weighing Lives[END_REF][START_REF] Blackorby | Population Issues in Social Choice Theory, Welfare Economics, and Ethics[END_REF].

The standard objection to critical-level generalized utilitarianism is that

• if we set the critical level at or below the individually neutral well-being level (above which life is worth living, and below which it is not), then we get the repugnant conclusion [START_REF] Parfit | On doing the best for our children[END_REF][START_REF] Parfit | Future generations, further problems[END_REF][START_REF] Parfit | Reasons and Persons[END_REF] where, for any population with excellent lives, there is a population with lives barely worth living that is better, provided that the latter includes sufficiently many people,

• if we set the critical level strictly above the individually neutral well-being level, then we get the very sadistic conclusion (Arrhenius, 2000a, forthcoming) where, for any population with terrible lives not worth living, there is a population with lives worth living that is worse, provided that the latter includes sufficiently many people.

There are other criteria that avoid the repugnant and very sadistic conclusions, but they all have their own serious shortcomings. According to average utilitarianism, adding a life not worth living to a population may be socially desirable. According to critical-level leximin, as defined by [START_REF] Blackorby | Leximin population ethics[END_REF], any population with n persons living excellent lives is worse than a population with n + 1 persons whose well-being is barely above a critical level. According to leximin, as suggested by Arrhenius (forthcoming,Sect. 6.8), any population is worse than a population consisting of one individual, provided that the worst-off individual of the former has lower well-being than the single individual of the latter.

Even in a fixed population framework, where there is no difference between the various prioritarian criteria discussed above, and also no difference between the two kinds of leximin criteria, both the prioritarian and the egalitarian (viz. leximin) approaches have shortcomings if there are many present and future people. If one considers a completely egalitarian well-being stream in an intergenerational setting with many future generations, and seeks to evaluate whether the present generation should make a sacrifice leading to a uniform benefit to future generations, then prioritarian and leximin approaches reach opposite and extreme Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée) conclusions: According to prioritarianism, the sacrifice should always be made provided that there are sufficiently many future generations, while according to leximin, it should never be made. This has been labelled by [START_REF] Fleurbaey | The tyranny of non-aggregation versus the tyranny of aggregation in social choices: a real dilemma[END_REF] respectively as the "tyranny of aggregation" and the "tyranny of non-aggregation".

In their paper, [START_REF] Fleurbaey | The tyranny of non-aggregation versus the tyranny of aggregation in social choices: a real dilemma[END_REF] suggest a class of rankdependent welfare orderings that do not suffer from the tyranny of aggregation and the tyranny of non-aggregation. Rank-dependent criteria generalize prioritarian ones by adding a weight on transformed utilities that depend on the rank of the individual in the distribution of well-being. In the context of population ethics, [START_REF] Asheim | Escaping the repugnant conclusion: Rankdiscounted utilitarianism with variable population[END_REF] have proposed and axiomatized a family of such rank-dependent criteria, namely the rank-discounted critical-level generalized utilitarianism criteria. They showed that they can avoid shortcomings such as the repugnant and very sadistic conclusions. This chapter studies to what extent other rank-dependent criteria solve dilemmas in population ethics.

In Sections 2 and 3 we introduce the framework, present some general desirable properties of social welfare orderings in the variable population framework and discuss three families of criteria: prioritarian ones, egalitarian ones, and proper rank-dependent criteria.

In Sections 4 and 5, we discuss the tyranny of aggregation and the tyranny of non-aggregation. We show that rank-dependent criteria may escape both tyrannies, at the cost of not satisfying a replication-invariance property. We argue that this property may not be so appealing in the variable population context.

In Section 6 we consider a related dilemma in population ethics between repugnant and sadistic conclusions, adding new results to those already established by, e.g., [START_REF] Blackorby | Critical-level population priniciples and the repugnant conclusion[END_REF] and Asheim and Zuber (2014, Section 4). We show that rank-dependent criteria may simultaneously avoid the repugnant conclusion, the very sadistic conclusion and the reversed repugnant conclusions. A key condition is that the cumulative effect of adding individuals at a given level of lifetime well-being is bounded. In Section 7 we show how negative results extend to a larger class of prioritarian and egalitarian criteria.

Finally, in Section 8 we conclude, while all proofs are contained in an appendix.

Framework and basic properties

Let N denote the set of positive integers (natural numbers), let R denote the real numbers, and let respectively R + /R ++ /R -/R --denote the non-negative/positive/nonpositive/negative real numbers. We consider distributions of (lifetime) well-being within finite populations of variable sizes. We favor the interpretation where the population consists of people that either are alive now or will exist in the future. The set of such distributions is X = ∪ k∈N R k , with typical element x = (x 1 , . . . , x i , . . . , x k ), and where x i is the well-being of individual i in this population. Thus a distribution x of three people with well-being 5, 10 and 20 respectively will be represented by x = (5, 10, 20), while distribution y of five people with well-being 1, 17, -4, 15 and 33 respectively will be represented by y = (1, 17, -4, 15, 33).

Well-being is assumed to be at least level comparable.1 For every k ∈ N, and each distribution x ∈ R k , the finite population size in x is n(x) = k. Following the usual convention in population ethics, a well-being level equal to 0 represents neutrality. Hence, well-being is normalized so that above neutrality, a life, as a whole, is worth living; below neutrality, it is not.

For every k ∈ N and all x, y ∈ R k , we write x y whenever x i > y i for all i ∈ {1, . . . , n(x)}. Similarly, x ≥ y means that x i ≥ y i for all i ∈ {1, . . . , n(x)}, and x = y means that x i = y i for all i ∈ {1, . . . , n(x)}. We write x > y whenever x ≥ y and x = y.

We assume that distributions of well-being can be normatively ranked by a social welfare ordering (swo) . Such a social welfare ordering is a binary relation, which is complete and transitive. For all x, y ∈ X, x y means that the distribution x is deemed socially at least as good as y. The fact that is complete means that, for all x, y ∈ X, either x y or y x (or both). The fact that is transitive means that, for all x, y, z ∈ X, if x y and y z then x z. We let ∼ and denote the symmetric and asymmetric parts of . We say that a social welfare function (swf) W : X → R represents a swo on X if, for all x, y ∈ X, x y if and only if W (x) ≥ W (y).

For each x ∈ X, we let

x [ ] = (x [1] , . . . , x [r] , . . . , x [n(x)]
) denote the nondecreasing distribution that is obtained by reordering x; i.e., for each rank r ∈ {1, . . . , n(x) -1}, x [r] ≤ x [r+1] . For any real number z ∈ R and any positive integer k ∈ N, we let (z) k ∈ R k denote the egalitarian distribution where all k individual have a well-being level equal to z. For any x ∈ X and z ∈ R, (x, (z) k ) denotes the distribution x with k added individuals, all with lifetime well-being equal to z ∈ R.

We now introduce through axioms some basic requirements that seem appealing for a swo. The first axiom is a principle of impartiality that states all individuals are treated in the same way, so that permuting well-being levels (or permuting the order of people in the list of well-being) leaves the distribution equally good.

Anonymity. A swo on X satisfies anonymity if, for all k ∈ N and all x ∈ R k ,

x ∼ y if y is obtained by reordering the elements of x.

The second principle represent two ideas. First, if we make small mistakes in measuring the well-being of people, this should not radically modify the social assessment so that small changes in distributions does not yield big changes in the social value of the distributions. Second, we want to be able to represent the swo by a swf that is defined across different population sizes. This can be done by endorsing the following principle [START_REF] Blackorby | Population Issues in Social Choice Theory, Welfare Economics, and Ethics[END_REF] Extended Continuity. A swo on X satisfies extended continuity if, for all k, ∈ N and all x ∈ R k , the sets {y ∈ R | y x} and {y ∈ R | x y} are closed in R .

The two next principles can be viewed as version of the Pareto principle, namely that a distribution x should be preferred to a same-population distribution y whenever all individuals prefer x to y. Monotonicity combines a Pareto indifference with a weak version of the Pareto principle. Restricted Dominance requires minimal sensitivity to individual well-being: starting with an egalitarian distribution, if a single individual is made worse off, then the distribution becomes worse.

Monotonicity. A swo on X satisfies monotonicity if, for all k ∈ N and all x, y ∈ R k , x ≥ y implies x y.

Restricted Dominance. A swo on X satisfies restricted dominance if, for all k ∈ N and all z, z ∈ R with z > z , (z) k (z , (z) k-1 ).

The Pigou-Dalton transfer principle requires that we prefer more equal distributions. If well-being is transferred from a better-off person to a worse-off person without reversing their relative ranks, so that the resulting distribution is more equal, then the new distribution is at least as good.

Pigou-Dalton. A swo on X satisfies Pigou-Dalton if, for all k ∈ N, all x, y ∈ R k , all δ > 0 and all i, j ∈ {1, . . . , k}, if (i) x h = y h for all h ∈ {1, . . . , k}, h = i, j, and (ii) y i -δ = x i ≥ x j = y j + δ, then x y.

In this chapter, we will consider both absolute and relative rank-dependent criteria, where absolute criteria require absolute, rather than relative, population size to be significant. To rule out any role for absolute population size, we can use a Replication Invariance property (see [START_REF] Blackorby | Population Issues in Social Choice Theory, Welfare Economics, and Ethics[END_REF]. This is also a consistency property across population sizes: if distribution (1, 1) is preferred to distribution (0, 2) then (1, 1, 1, 1) is also preferred to distribution (0, 0, 2, 2) because if we only add a 'twin' to each person in the initial Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée) Rank-discounting and population ethics distributions.

To formally state this property, we need to introduce the notion of replicas. For all ∈ N and all x ∈ R k , let * x denote the -replica of x, i.e. a distribution giving x to disjoint population of size k.

Replication Invariance. A swo on X satisfies replication invariance if, for all k ∈ N, all ∈ N, all x, y ∈ R k , x ∼ y implies * x ∼ * y Our last basic axiom is an independence or consistency axiom that holds on ordered ("comonotonic") distributions. A natural independence condition would be that the social ranking of two same-population distributions x and y does not depend on the well-being level of individuals who have the same level in the two distributions, provided that we do not change individual ranks. This principle of Independence with respect to Ordered Vectors was introduced by Ebert (1988). 2Wakker (1989) and [START_REF] Köbberling | Preference Foundations for Nonexpected Utility: A Generalized and Simplified Technique[END_REF] have shown that, under mild additional conditions satisfied by all swos discussed in this paper, Independence with respect to Ordered Vectors is implied by a broader condition representing the idea that we have a consistent way to measure transformed well-being. This condition, named Trade-Off Consistency for Ordered Vectors, states that the cardinal measurement of how changes in well-being affect social evaluation should be consistent: it does not depend on the rank of the individuals (provided we compare people at the same rank). The condition also adds that social evaluation of two same-population distributions is independent of the well-being of individuals who have the same rank and well-being in the two distributions (which is exactly Independence with respect to Ordered Vectors).

To introduce Trade-Off Consistency for Ordered Vectors, we need further notation. Let x be any distribution, and r be an integer in {1, . . . , n(x)} and z ∈ R a real number. The distribution x [-r] z, if it exists, is the distribution x such that n(x) = n(x), xi = x [i] for all i = r and xr = z. Hence x [-r] z is an ordered vector that is a permutation of x except that the well-being of individual with rank r is now

z instead of x [r] . Such a vector is well-defined only if x [r-1] ≤ z ≤ x [r+1] (or r = 1 and z ≤ x [2] , or r = n(x) and z ≥ x [n(x)-1] ).
Formally, Trade-off consistency for ordered vectors is written as follows:

Trade-Off Consistency for Ordered Vectors. A swo on X satisfies tradeoff consistency for ordered vectors if, for all k ∈ N, all x, y, x, ỹ ∈ R k , all r r ∈ {1, . . . , k} and all z 1 , z 2 , z 3 , z 4 ∈ R and z

3 > z 3 , if x [-r] z 1 , y [-r] z 2 , x [-r] z 3 , y [-r] z 4 , x[-r ] z 1 , ỹ[-r ] z 2 , x[-r ] z 3 and ỹ[-r ] z 4 are all well-defined and x [-r] z 1 ∼ y [-r] z 2 , x [-r] z 3 ∼ y [-r] z 4 , x[-r ] z 1 ∼ ỹ[-r ] z 2 , then x[-r ] z 3 ỹ[-r ] z 4 . 3
In the axiom, x [-r] z 1 ∼ y [-r] z 2 and x [-r] z 3 ∼ y [-r] z 4 means that the difference in well-being brought by z 1 and z 2 has the same impact on social evaluation as the difference in well-being brought by z 3 and z 4 . The axiom says that this difference should not depend on the rank of the individual.

Basic representation results

With the basic properties introduced in Section 2, we are able to present three representation results. The proofs of these and other propositions are contained in an appendix.

Proposition 1 Assume that a swo on X satisfies Anonymity, Extended Continuity, Montonicity and Restricted Dominance. Then there exist,

• for each k ∈ N, a continuous, symmetric and non-decreasing function e k :

R k → R satisfying e k ((z) k ) = z for all z ∈ R, and

• a continuous function V : N × R → R, which is strictly increasing in its second variable, such that W (x) = V (n(x), e n(x) (x)) represents .
The swos obtained in Proposition 1 decompose the evaluation of well-being distributions in two steps. Functions e k are the equally-distributed equivalent function: for all x ∈ R k , the well-being level z ∈ R determined by e k (x) = z has the property that an egalitarian distribution where k individuals have well-being z is socially as good as x. 4 For each k, the function e k : R k → R is a swf that represents the swo on R k -the restricted domain of populations of size k -such that for all x, y ∈ R k , x y if and only if e k (x) ≥ e k (y). Hence, the functions e k embody the principles of justice within populations of the same size. On the other hand, the function V embody the trade-off between population size and equally-distributed equivalent well-being in the population.

The following are three examples of swos that are consistent with this decomposition:

Rank-discounting and population ethics

• Critical-level generalized utilitarianism (clu) has V (k, e) = k (φ(e) -φ(c))
for some critical level c ≥ 0 and

e k (x) = φ -1 1 k k r=1 φ(x [r] ) (1)
for some increasing and continuous function φ : R → R that transforms wellbeing into transformed well-being, so that the clu swo is represented by

W (x) = k r=1 φ(x [r] ) -φ(c) .
For consistency with our discussion below we let the index sum according to rank r, but this is clearly immaterial for the clu swo. The clu swo has a prominent place in the literature on population ethics [START_REF] Blackorby | Social criteria for evaluating population change[END_REF][START_REF] Broome | Weighing Lives[END_REF][START_REF] Blackorby | Population Issues in Social Choice Theory, Welfare Economics, and Ethics[END_REF].

• Average generalized utilitarianism (au) has V (k, e) = φ(e) with e k (x) given by ( 1), so that the au swo is represented by

W (x) = 1 k k r=1 φ(x [r]
) .

• Maximin has V (k, e) = φ(e) and e k (x) = x [1] , so that the maximin swo is represented by

W (x) = φ(x [1] ) . (2)
In the presentation of maximin we have chosen (2) instead of the equivalent representation W (x) = x [1] in order to be consistent with our discussion below.

By imposing that the swo on X satisfies trade-off consistency for ordered vectors and Pigou-Dalton, we obtain a smaller class of swos, which contains the set of clu, au and maximin swos as special cases. To introduce the general class, we need the following index of non-concavity of a continuous and increasing function φ (see [START_REF] Chateauneuf | More pessimism than greediness: a characterization of monotone risk aversion in the rank-dependent expected utility model[END_REF]:

G φ = sup z 1 <z 2 ≤z 3 <z 4 φ(z 4 )-φ(z 3 ) z 4 -z 3 φ(z 2 )-φ(z 1 ) z 2 -z 1 .
Proposition 2 Assume that a swo on X, in addition to the axioms of Proposition 1, satisfies Trade-Off Consistency for Ordered Vectors and Pigou-Dalton. Then, for each k ∈ N , the equally distributed equivalent of x ∈ R k is Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

given by

e k (x) = φ -1 k k r=1 w k r φ k (x [r] ) , (3)
where the weights w k r , for r ∈ {1, . . . , k}, are non-negative, non-increasing and sum up to 1, and the function φ k is continuous, increasing and such that

G φ k ≤ min r∈{1,...,k-1} w k r w k r+1 .
A swo satisfying the axioms of Propositions 1 and 2 is called a rank-dependent generalized utilitarian swo. We can consider different subclasses of rank-dependent generalized utilitarian swos depending on the principles of justice applied for populations with the same size. We will pay particular attention to two subclasses, specified in Definitions 1 and 2.

Definition 1 A swo on X is a prioritarian (or generalized utilitarian) swo if it satisfies the axioms of Propositions 1 and 2 with the weights in (3) given by w k r = 1 k for all k ∈ N and r ∈ {1, . . . , k} and a function φ k = φ for all k ∈ N.

The prioritarian class includes the clu and au swos. However, this class is much richer than these few examples, and can encompass many different ways of trading-off population size and average transformed well-being.

For the prioritarian class, Proposition 2 implies that G φ ≤ 1 so that φ is weakly concave. If φ is affine, then we obtain (non-generalized) utilitarianism. The utilitarian class is the one that has been most studied in population ethics. A famous example is the total utilitarian swo, which is the member of the utilitarian class such that

V (k, z) = kz for all k ∈ N and e k (x) = 1 k k r=1 x [r]
. This is a clu swo with φ(z) = z and c = 0; thus, it is also prioritarian.

The term "prioritarian" suggests that φ is a strictly concave transformation of well-being, thereby giving preference to redistribution of well-being from a betteroff to a worse-off person. An extreme case of such preference for redistribution is given by equalitarian swos.

Definition 2 A swo on X is an egalitarian swo if it satisfies the axioms of Propositions 1 and 2 with the weights in (3) given by w k 1 = 1 for all k ∈ N.

To the best of our knowledge, only a few papers have considered this version of egalitarianism in the population ethics literature. 5 There have been discussions of other versions of egalitarianism that use a leximin rather than a maximin criterion to define e k .6 For instance, [START_REF] Blackorby | Leximin population ethics[END_REF] have argued in favor of Critical-Level Leximin, while Arrhenius (forthcoming, Sect. 6.8) discusses a version of leximin related to the Positional-Extension Leximin of [START_REF] Blackorby | Leximin population ethics[END_REF]. One issue though is that leximin is not continuous so that we cannot apply Proposition 1 to define a family of leximin criteria. Given that leximin gives priority to the worst-off, like maximin, the conclusions that we would obtain would not be very different from the ones for maximin in the context of the present chapter.

Proposition 3 Assume that a swo on X, in addition to the axioms of Propositions 1 and 2, satisfies Replication Invariance. Then φ k = φ for all k ∈ N and there exists a non-decreasing and concave weighting function F : [0, 1] → [0, 1], which is continuous on (0, 1] and satisfies F (0) = 0 and F (1) = 1, such that the weights in (3) are given by w

k r = F r k -F r-1 k
for each k ∈ N and r ∈ {1, . . . , k}.

A swo satisfying the axioms of Propositions 1, 2 and 3 is called a relative rank-dependent generalized utilitarian swo. Both prioritarian and egalitarian swos are in this class. In the case of prioritarianism, we have that the weighting function F is given by F (ρ) = ρ for all ρ ∈ [0, 1]. In the case of egalitarianism, we have that the weighting function F is given by F (0) = 0 and F (ρ) = 1 for all ρ ∈ (0, 1].

Tyranny of aggregation, tyranny of non-aggregation and replication invariance

Fleurbaey and Tungodden (2010) have highlighted a dilemma in social ethics between what they call the "tyranny of aggregation" and the "tyranny of nonaggregation". The tyranny of aggregation means that a tiny gain to sufficiently many well-off people might justify imposing a much larger sacrifice on the worstoff. On the other hand, the tyranny of non-aggregation means that a small gain by the worst-off might be sufficient to justify a sacrifice by a great number of people.

To avoid these two tyrannies, [START_REF] Fleurbaey | The tyranny of non-aggregation versus the tyranny of aggregation in social choices: a real dilemma[END_REF] have proposed the principles of minimal aggregation and minimal non-aggregation.

Minimal Aggregation. A swo

satisfies minimal aggregation if for some k ∈ N and for all x ∈ R k , there exist δ > ε > 0 such that for all y ∈ R k , if (i) for some i ∈ {1, . . . , k}, 0 ≤ x i -y i ≤ ε and (ii) for all j = i, y j -x j ≥ δ, then y x.

Minimal Aggregation means that for some population, if all individuals except individual i gain sufficiently, then it is tolerable to impose a loss on individual i if the loss is sufficiently small. Note that the loss may be arbitrary low, so that the principle does not seem very demanding.

To introduce minimal non-aggregation, let us introduce for any distribution x ∈ X the set of worst-off and best-off individuals in this distribution:

I W (x) = i ∈ {1, . . . , n(x)} | x i = min j∈{1,...,n(x)}
x j and

I B (x) = i ∈ {1, . . . , n(x)} | x i = max j∈{1,...,n(x)} x j .
Minimal Non-Aggregation. A swo satisfies minimal non-aggregation if there exist 0 < z < z and δ > ε > 0 such that for all k ∈ N, all x, y ∈ R k , if (i) for some i ∈ {1, . . . , k}, i ∈ I W (y), y i ≤ z and x i -y i ≥ δ and (ii) for all j = i with x j = y j , it holds that j ∈ I B (x) ∩ I B (y), y j ≥ z and y j -x j ≤ ε, then x y.

Minimal Non-Aggregation means that if a worst-off individual is sufficiently badly-off and gains enough, there is a small loss that is tolerable for all the bestoff, no matter how numerous they are, provided they are sufficiently well-off. Again the principle does not seem very demanding given that the loss by the best-off may be arbitrary small.

The key remark by [START_REF] Fleurbaey | The tyranny of non-aggregation versus the tyranny of aggregation in social choices: a real dilemma[END_REF] is that prioritarian swos do not satisfy Minimal Non-Aggregation, while egalitarian swos do not satisfy Minimal Aggregation. Furthermore, in their Proposition 2(i) they establish conditions under which Minimal Aggregation and Minimal Non-Aggregation cannot be combined with Replication Invariance. Our next proposition illustrate this result under conditions that are stronger than those imposed by Fleurbaey and Tungodden (2010, Proposition 2(i)).

Proposition 4 Assume that a swo on X satisfies the axioms of Propositions 1, 2 and 3. Then fails either Minimal Aggregation or Minimal Non-Aggregation.

The proof of Proposition 4 shows that the failure of minimal aggregation or minimal non-aggregation depends on the properties of the weighting function F which determines the weights in (3). The upshot of this result is that if we want to satisfy minimal aggregation and minimal non-aggregation, and we want to keep the axioms of Propositions 1 and 2, thus keeping the rank-dependent generalized utilitarian form, then replication invariance must go.

This discussion can be related to Arrhenius' (forthcoming) general non-extreme priority condition, capturing the idea that there is some number of people such that a very large loss for them cannot be compensated for by a slight gain for just one person. A swo satisfying the axioms of Propositions 1, 2 and 3 fails this condition if lim ρ→0 + F (ρ) > 0, since then a large loss for many better-off people can be compensated by a slight gain for a single worst-off person if sufficient many people are inserted at intermediate ranks. Hence, by observation (a) above, Minimal Aggregation is weaker than Arrhenius' condition in a setting where these axioms are satisfied.

Escaping tyrannies through absolute rank-dependence

A particular class of swo satisfying the axioms of Propositions 1 and 2, but not necessarily satisfying replication invariance, is obtained by letting weights depend on absolute rather than relative ranks.

Definition 3 A swo on X satisfying the axioms of Propositions 1 and 2 is an absolute rank-dependent generalized utilitarian swo if there exist (i) non-negative and non-increasing absolute weights (a r ) r∈N with a 1 = 1 such that, for all k ∈ N, the weights in (3) are obtained by letting

w k r = a r k r =1 a r
for all r ∈ {1, . . . , k}, and (ii) a function φ such that φ k = φ for all k ∈ N.

Prioritarian and egalitarian swos are also absolute rank-dependent. In the case of prioritarianism, this is obtained by choosing a r = 1 for all r ∈ N as absolute weights. This includes clu and au. In the case of egalitarianism, this is obtained by choosing a r = 0 for all r > 1. This includes maximin. Hence, Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée) prioritarian and egalitarian swos are both relative and absolute rank-dependent generalized utilitarian swos.

Any absolute rank-dependent generalized utilitarian swo satisfies the axioms of Propositions 1 and 2, but is not characterized by these axioms. To obtain absolute rank-dependent swos, we could add an additional independence property (which corresponds to the High Income Group Aggregation Property as defined by Bossert, 1990b, and to Top Independence as defined by [START_REF] Pivato | Rank-additive population axiology[END_REF] Same population independence of the existence of the best-off. A swo satisfies same population independence of the existence of the best-off if, for any k ∈ N, and for all x, y ∈ R k and z > max{x

[k] , y [k] }, x y if and only if x, (z) 1 y, (z) 1 .
Definition 4 An absolute rank-dependent generalized utilitarian swo on X is a proper rank-dependent generalized utilitarian swo if the absolute weights (a r ) r∈N satisfy a 2 > 0 and r∈N a r < ∞.

The restriction that a 2 be strictly positive means that no egalitarian swos is proper rank-dependent, and the restriction that the absolute weights be summable means that no prioritarian swo is proper rank-dependent. If there exists a real number β ∈ (0, 1) such that the absolute weights are a r = β r-1 for all r ∈ N, then the swo is proper rank-dependent and called a rank-discounted generalized utilitarian (rdu) swo. We will return to this particular subclass in the next section.

One drawback of proper rank-dependent generalized utilitarian swos is that they allow a large loss for many better-off people to be compensated by a slight gain for a single worst-off person. The reason is that the loss of transformed well-being of the many better-off people is discounted below any positive level by inserting sufficiently many people at intermediate ranks. Hence, swos in this class fail Arrhenius' (forthcoming) general non-extreme priority condition (discussed at the end of Section 4).

Definition 5 An absolute rank-dependent generalized utilitarian swo on X is a regular rank-dependent generalized utilitarian swo if there exists a positive number κ ∈ R ++ such that, for all k ∈ N,

a k ≥ κ • +∞ r=k+1 a r .
The restriction imposed by regularity implies in particular that the absolute weights are summable (i.e. r∈N a r < ∞), but it is stronger than that. Hence no prioritarian swo is regular rank-dependent. On the other hand, the restriction allows weights to be equal to zero from a certain rank r on. Hence egalitarian swos are regular rank-dependent. Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

Rank-discounting and population ethics

As shown by the following result, the absolute rank-dependent generalized utilitarian swo being proper and regular is the key to solving the dilemma posed by the requirements of minimal aggregation and minimal non-aggregation.

Proposition 5 Assume that a swo on X is an absolute rank-dependent generalized utilitarian swo. Then satisfies both Minimal Aggregation and Minimal Non-Aggregation if and only if is proper and regular rank-dependent.

The proof of Proposition 5 shows that:

(a) If the swo is egalitarian, then fails minimal aggregation.

(b) If the swo is not regular rank-dependent, then fails minimal non-aggregation.

The proposition implies that, within the class of absolute rank-dependent generalized utilitarian swos, there must be positive weights on more than the worst-off person, and the sum of the weights must be converging sufficiently fast. This gives a route out of the dilemma posed by Fleurbaey and Tungodden ( 2010), but at the cost of failing the requirement of replication invariance. Indeed, Fleurbaey and Tungodden (2010, p. 404) show existence of a swo satisfying both minimal aggregation and minimal non-aggregation by providing an example of an rdu swo in a form that is actually in the subclass considered in the subsequent section.

Simple rank-dependence and population ethics

Up to now, the general classes of swos that we have considered in our propositions and definitions have not specified the trade-off between population size and equally-distributed equivalent well-being in the population, as embodied by the function V of Proposition 1. We turn now to one particularly natural manner to make this trade-off.

Definition 6 An absolute rank-dependent generalized utilitarian swo on X with absolute weights (a r ) r∈N is a simple rank-dependent generalized utilitarian swo if there exists a critical level c ∈ R + such that the function V of Proposition 1 is given by:

V (k, e) = k r=1 a r (φ(e) -φ(c)) .
The term 'simple' is appropriate since, any rank-dependent generalized utilitarian swo is represented by a swf W : X → R of the form:

W (x) = k r=1 a r φ(x [r] ) -φ(c) .
(4) The class of simple prioritarian swo contains only clu. In particular, the au swo is prioritarian, but not simple. The class of simple egalitarian swo contains only maximin. To the best of our knowledge, only few papers have considered swfs similar to the one defined by (4) and that are neither simple prioritarian nor simple egalitarian. [START_REF] Sider | Might theory X be a theory of diminishing marginal value?[END_REF] has proposed principle GV, with similar ideas already discussed by [START_REF] Hurka | Value and population size[END_REF]. Principle GV is related to but incompatible with the form specified by Equation (4). It first divides a population into two ordered sets: one set with the distribution of the people with positive well-being, in order of descending well-being; and another set with the distribution of the people with negative well-being, in order of ascending well-being. For people with negative well-being, principle GV is similar to (4) with decreasing weights a r , an affine function φ and c = 0. For people with positive well-being, principle GV applies something like (4) with decreasing weights a r an affine function φ and c = 0, but it applies it to the distribution of people ordered in decreasing (and not increasing) order of well-being. Principle GV has been discussed by several papers (Arrhenius, 2000a,b, forthcoming;[START_REF] Pivato | Rank-additive population axiology[END_REF], the latter paper contains also an axiomatization of a generalized version of the principle). These papers point out that Principle GV implies that, if everyone has positive well-being, it is always socially better to make a (non-leaky) well-being transfer from a poor to a rich. Hence, principle GV does not satisfy Pigou-Dalton.

Asheim and Zuber (2014) have proposed and axiomatized the class of rankdiscounted critical-level generalized utilitarian (rdclu) swos. They are a special case of the form specified by (4), where there exists a real number β ∈ (0, 1) such that the weights are a r = β r-1 , for all r ∈ N. The fact that the absolute weights a r are strictly decreasing implies that a rdclu swo may satisfy Pigou-Dalton even if φ is not concave: A rdclu swo satisfies Pigou-Dalton if and only if G φ ≤ ar a r+1 = β -1 . Generalizations of rank-discounted critical-level generalized utilitarian swos have been discussed by [START_REF] Zuber | Éthique de la population: l'apport des critères de bien-être dépendant du rang[END_REF] and axiomatized by [START_REF] Pivato | Rank-additive population axiology[END_REF].

Any simple rank-dependent generalized utilitarian swo satisfies the axioms of Propositions 1 and 2, but is not characterized by these axioms. To obtain simple rank-dependent swos from absolute rank-dependent swos, we could add yet another independence property (which is implied by the Low Income Group Aggregation Property as defined by Bossert, 1990b):

Independence of the Well-being of the Worst-off. A swo satisfies the independence of the well-being of the worst-off if for all x, y ∈ X and any z , z ∈ R such that max{z , z } < min{x [1] , y [1] }, x, (z ) 1 y, (z ) 1 if and only if x, (z ) 1 y, (z ) 1 .

Rank-discounting and population ethics

According to [START_REF] Parfit | Reasons and Persons[END_REF], a social welfare ordering leads to the repugnant conclusion if: "For any possible population of at least ten billion people, all with a very high quality of life, there must be some much larger imaginable population whose existence, if other things are equal, would be better even though its members have lives that are barely worth living."

The repugnant conclusion has caught much attention in the literature on population ethics as most of the literature have discussed ways to avoid such a conclusion. Formally, one can formulate the avoidance of the repugnant conclusion as follows:7

Avoidance of the Repugnant Conclusion. A swo on X avoids the repugnant conclusion if there exist k ∈ N, y ∈ R ++ and z ∈ (0, y) such that, for all m ≥ ≥ k, (y) (z) m .

Although the clu swo does not avoid the repugnant conclusion if the critical level c equals 0, other generalized utilitarian swo, e.g. clu with positive c and au do so. However, they are subject to other difficulties.

On the one hand, clu with positive c imply the sadistic conclusion is that, for any distribution with negative well-being, there is an egalitarian distribution with low, but positive well-being that is worse. This is what Arrhenius (2000a, forthcoming) refers to as the very sadistic conclusion. Formally, one can formulate the avoidance of the very sadistic conclusion as follows:

Avoidance of the Very Sadistic Conclusion. A swo on X avoids the very sadistic conclusion if there exists x ∈ X such that (z) k

x for all k ∈ N and z ∈ R ++ .

One the other hand, au and also maximin leads to the problematic conclusion that for any egalitarian distribution with very high positive well-being, there is a better one-individual distribution with slightly higher well-being. This might be referred to as the reversed repugnant conclusion (Arrhenius, forthcoming). Hence, one can formulate the avoidance of the reversed repugnant conclusion as follows:

Avoidance of the Reversed Repugnant Conclusion. A swo on X avoids the reversed repugnant conclusion if there exist k ∈ N, y ∈ R ++ and z ∈ (0, y) such that (z) k (y) 1 .

The next result shows that in the class of simple rank-dependent generalized utilitarian swos, being proper is the key to avoiding all these three problematic conclusion.

Proposition 6 Assume that a swo on X is a simple rank-dependent generalized utilitarian swo. Then satisfies Avoidance of the Repugnant Conclusion, Avoidance of the Very Sadistic Conclusion and Avoidance of the Reversed Repugnant Conclusion if and only if is proper rank-dependent.

The proof of Proposition 6 shows that:

(a) If the swo is egalitarian, then entails the reversed repugnant conclusion.

(b) If the swo has non-summable absolute weights, then entails either the repugnant conclusion (when c = 0) or the very sadistic conclusion (when c > 0). Proposition 6 implies that, within the class of simple rank-dependent generalized utilitarian swos, there must be positive weights on more than the worst-off person, and the sum of the weights must be converging, in order to avoid all of the repugnant, very sadistic and reversed repugnant conclusions.

It follows from Proposition 6 and our remark just prior to Definition 5 that any simple rank-dependent generalized utilitarian swo avoiding the repugnant conclusion, the very sadistic conclusion and the reversed repugnant conclusion must fail Arrhenius' (forthcoming) general non-extreme priority condition.

Remark that, given that proper rank-dependent generalized utilitarian swos satisfy the Pigou-Dalton principle and avoid the repugnant conclusion, they cannot satisfy the famous mere addition principle introduced by [START_REF] Parfit | Reasons and Persons[END_REF], namely that addition of people with positive well-being is always (at least weakly) socially desirable.

Mere Addition Principle. A swo on X satisfies the mere addition principle if for all z ∈ R ++ and all x ∈ X (z, x) x. Indeed, [START_REF] Carlson | Mere addition and two trilemmas of population ethics[END_REF] proved that the mere addition principle and a non-antiegalitarianism principle (which follows from the Pigou-Dalton principle) imply a violation of our formulation of the avoidance of the repugnant conclusion.

Additional population ethics results

Proposition 6 singles out proper rank-dependent swos in the class of simple rankdependent generalized utilitarian swos. We can more generally compare proper and regular rank-dependent swos to a large class of prioritarian and egalitarian Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

Concluding remarks

In this chapter we have argued that the escape from the tyrannies of aggregation and non-aggregation and the resolution of an important population-ethical dilemma require that we relax the requirement of replication invariance. Thus the normative evaluation of populations and their well-beings may change as populations and their well-beings are replicated. The rdclu swo [START_REF] Asheim | Escaping the repugnant conclusion: Rankdiscounted utilitarianism with variable population[END_REF] is one example of a population-ethical criterion that offers a solution by relaxing replication invariance. However, as we have shown, a larger class of simple rank-dependent generalized utilitarian swos satisfy all the requirements that we have imposed, save replication invariance. In particular, the simple rank-dependent generalized utilitarian swos with absolute weights given by a r = R+1-r R for 1 ≤ r ≤ R and a r = 0 for r > R, where R ≥ 2, are in this larger class.

It is a standard approach in population ethics to associate with the notion of total population not only the people that are alive at any one time, but also people that will ever live and those that have ever lived; in particular, this is the position taken by [START_REF] Blackorby | Population Issues in Social Choice Theory, Welfare Economics, and Ethics[END_REF]. However, Broome (2004, chap. 13) and Blackorby, Bossert and Donaldson (2005, pp. 131-133) argue that it is reasonable to assume existence independence, requiring that the ranking of any two alternatives be independent of the existence of individuals who ever live and have the same well-being levels in both. Existence independence implies that populations principles can be applied to the affected people only.

The relaxation of replication invariance that we promote here is inconsistent with existence independence, and thus it becomes essential to take into account the existence and utility of non-affected people when evaluating population policies with limited scope. In particular, we must consider today the population policies that should be and will be implemented in the far future, and also take into the utilities of people that are dead if we require that the population-ethical criterion be time consistent. We must also depart from the generation-relative population ethics that Dasgupta (2005, pp. 430-431) supports, because the reproductive choices made by future generations will affect the number and well-being of future people, therefore modifying the goodness of changing the population today. This departure from existence independence might have important implications for the conclusions that follow from population ethics.

Rank-discounting and population ethics

Appendix: Proofs

Proof of Proposition 1.

If the swo on X satisfies Montonicity and Restricted Dominance, then it satisfies Minimal Increasingness in Blackorby, Bossert and Donaldson (2005, chap. 5). To see this, consider the distributions (z) k and (z ) k with z, z ∈ R satisfying z > z . Construct x ∈ R k by letting x i = z for some i ∈ {1, . . . , k} and x j = z for all j ∈ {1, . . . , k}\{i}. Then (z) k

x by Restricted Dominance and x (z ) k by Montonicity, so (z) k (z ) k by transitivity. Thus, the result follows from Blackorby, Bossert and Donaldson (2005, Theorem 5.2).

Proof of Proposition 2. From Köbberling and Wakker (2003, Theorem 8), for each population size k ∈ N, there must exist non-negative weights w k r , for r ∈ {1, . . . , k} and a continuous increasing function φ k such that, for all x, y ∈ X with n

(x) = n(y) = k, x y ⇐⇒ k r=1 w k r φ k (x [r] ) ≥ k r=1 w k r φ k (y [r] ).
Using the definition of equally distributed equivalent, we can take the weights w k r summing to one. By the uniqueness result in Köbberling and Wakker (2003, Theorem 8), both the weights and the function φ k are unique after normalization, provided that w k r > 0 for at least two ranks r. By Chateauneuf, Cohen and Meilijson (2005, Theorem 1) (or a similar result in [START_REF] Asheim | Escaping the repugnant conclusion: Rankdiscounted utilitarianism with variable population[END_REF], for each k ∈ N such social orderings satisfy Pigou-Dalton if and only if

G φ k ≤ min r∈{1,...,k-1} w k r w k r+1 .
Note that, by Chateauneuf, Cohen and Meilijson (2005, Proposition 3), G φ k ≥ 1, so that this implies w k r ≥ w k r+1 for all r ∈ {1, . . . , k -1}: the weights are nonincreasing.

Proof of Proposition 3. By Replication Invariance, and by the uniqueness result of functions φ k in Proposition 2, it is easy to show that there must exist a continuous and increasing function φ such that φ k = φ for all k ∈ N, provided that there exist at least two ranks r such that w k r > 0, for k ≥ 2 (otherwise, we have w k 1 = 1 for all k ∈ N, and function φ k does not matter: we can take it identical without loss of generality).

Then we can mimic Donaldson and Weymark (1980, Theorem 4) to show that there exists a non-decreasing and concave weighting function F satisfying all the required properties. Proof of Proposition 4. Case 1: lim ρ→0 + F (ρ) = 1. In this case, the weighting function F is given by F (0) = 0 and F (ρ) = 1 for all ρ ∈ (0, 1], so that the swo on X is egalitarian. Any egalitarian swo clearly contradicts minimal aggregation since no weight is given any person but the worst-off.

Case 2: lim ρ→0 + F (ρ) < 1. To show failure of minimal non-aggregation, we must show that, for all 0 < z < z and δ > ε > 0 there exist k ∈ N and x, y ∈ R k with x ≺ y, even though y i ≤ z and x i -y i ≥ δ for some i ∈ I W (y), and it holds that j ∈ I B (x) ∩ I B (y), y j ≥ z and y j -x j ≤ ε for all j ∈ {1, . . . , k} with j = i and x j = y j .

Choose any 0 < z < z and δ > ε > 0. Since lim ρ→0 + F (ρ) < 1 and F (ρ) is continuous for ρ ∈ (0, 1], we can choose m ∈ N sufficiently large so that F 1 m+1 < 1, and write ∆ := 1 -F 1 m+1 . Construct, for each ∈ N with ≥ 2, x and y such that n(x ) = n(y ) = (m + 1),

x 1 = y 1 = y 2 = z, x 2 = z + δ, x h = y h = z + δ for h = 3, • • • , and x h = z -ε, y h = z for h = + 1, • • • , (m + 1). For each ≥ 2, let Γ( ) := F 2 (m+1) -F 1 (m+1)
, where it follows from our assumptions that Γ( ) > 0 for all ≥ 2 and lim →∞ Γ( ) = 0. Hence, we can choose ≥ 2 such that Γ( ) φ(z + δ) -φ(z) < ∆ φ(z) -φ(z -ε) .

By definition of the swos obtained in Propositions 1, 2 and 3, y

x , which contradicts minimal non-aggregation.

Hence, either minimal aggregation or minimal non-aggregation fails.

Proof of Proposition 5. Case 1: The swo on X is egalitarian. Clearly minimal aggregation is contradicted since no weight is given any person but the worst-off.

Case 2: The swo on X is not regular rank-dependent. Assume that there exist real numbers 0 < z < z and δ > > 0 as required in the statement of Minimal Non-Aggregation. Consider any k ∈ R, m ∈ R, with k < m. Let x, y ∈ R l be such that x i = y i = z for all i < k, y k = z, x k = z + δ, x j = z and y j = z + for all j > k, where z > max{z + δ, z}. By definition of an absolute rank-dependent swo, we have:

x y ⇐⇒ a k φ(z + δ) + m r=k+1 a r φ(z) ≥ a k φ(z) +

Rank-discounting and population ethics

This can be written:

x y ⇐⇒ a k ≥ φ(z + ε) -φ(z) φ(z + δ) -φ(z) m r=k+1 a r .
But denoting

κ = φ(z + ε) -φ(z) φ(z + δ) -φ(z) ,
and given that is not regular rank-dependent, there must exist k ∈ N such that a k < κ • +∞ r=k +1 a r . This means that there must also exist m > k such that a k < κ • m r=k +1 a r . So, Minimal Non-Aggregation must sometimes be violated.

Case 3: The swo on X is proper and regular rank-dependent. Let λ ∈ (0, 1) be such that κ > λ • a 1 a 2 . By Chateauneuf, Cohen and Meilijson (2005, Lemma 1), for any x, y ∈ R, with x ≥ y:

λ • G φ ≥ φ(x + λ) -φ(x) φ(y) -φ(y -1) .
Because the swo satisfies Pigou-Dalton, we have

G φ ≤ inf k∈N ar a r+1 ≤ a 1 a 2 .
Therefore, for any x, y ∈ R, with x ≥ y:

κ > λ • a 1 a 2 ≥ φ(x + λ) φ(x) φ(y) -φ(y -1) .
If the swo is proper and regular rank-dependent, than it clearly satisfies Minimal Aggregation. Let us show that it also satisfies Minimal Non-Aggregation, where in the statement of this property we take z = 0, z > 1, δ = 1 and = λ. Consider any k ∈ N, and any x, y ∈ R k and i ∈ {1, . . . , k}, such that (i) i ∈ I W (y), y i ≤ 0 and x i -y i ≥ 1; and (ii) for all j ∈ {1, . . . , k} with j = i and x j = y j , it holds that j ∈ I B (x) ∩ I B (y), y j ≥ z and y j -x j ≤ λ. We need to show that x y. Let R = |{ ∈ {1, . . . , k} : x ≤ x i }| the number of individuals with well-being lower than x i in distribution x; R = |{ ∈ {1, . . . , k} : y ≤ y i }| the number of individuals with well-being lower than y i in distribution y; K = |{j ∈ {1, . . . , k}: j = i, x j = y j }| the number of individuals other than i with Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée) different well-being in x and y. By definition of a proper rank-dependent swo:

8 x y ⇐⇒ R -1 r=1 a r φ(x [r] ) + R r=R a r φ(x [r] ) + k-K r=R+1 a r φ(x [r] ) + k r=k-K+1 a r φ(x [r] ) ≥ R -1 r=1 a r φ(y [r] ) + R r=R a r φ(y [r] ) + k-K r=R+1 a r φ(y [r] ) + k r=k-K+1 a r φ(y [r] )
By definition of x and y, this can be written:

x y ⇐⇒ R r=R a r φ(x [r] ) + k r=k-K+1 a r φ(x [r] ) ≥ R r=R a r φ(y [r] ) + k r=k-K+1 a r φ(y [r] )
Given that y j -x j ≤ λ for all j ∈ {1, . . . , k} with j = i and x j = y j (and

x j = x [k]
for all such j), a sufficient condition to have x y is:

R r=R a r φ(x [r] ) -φ(y [r] ) ≥ k r=k-K+1 a r φ(x [k] + λ) -φ(x [k] ) But R r=R a r φ(x [r] ) -φ(y [r] ) ≥ a R φ(x i ) -φ(y i ) ≥ a R φ(x i ) -φ(x i -1) , and a R k r=k-K+1 a r ≥ a R +∞ r=R a r ≥ κ > φ(x [k] + λ) -φ(x [k] ) φ(x i ) -φ(x i -1) .
It is then the case that x y.

Proof of Proposition 6. Case 1: The swo on X is egalitarian. Clearly the reversed repugnant conclusion is not avoided.

Case 2: The swo on X has non-summable absolute weights and c = 0. Consider any k ∈ N, y ∈ R ++ and z ∈ (0, y). By definition of a simple rankdependent generalized utilitarian swo: so that (z) m (y) k . This contradicts Avoidance of the Repugnant Conclusion.

Case 3: The swo on X has non-summable absolute weights and c > 0. Assume that there exists x ∈ X such that (z) k x for all k ∈ N and z ∈ R ++ . Let = n(x). By definition of a simple rank-dependent generalized utilitarian swo, x (x [1] ) n . Take any z ∈ R ++ such that z < c. By definition of a simple rank-dependent generalized utilitarian swo:

(x [1] ) n (z ) k ⇐⇒ n r=1 a r φ(x [1] ) -φ(c) > k r=1 a r φ(z ) -φ(c) . If x [1] > z then (x [1] ) n (z ) n , so that by transitivity x (z ) n , which is a contradiction. If x [1] ≤ z < c then φ(x [1] ) -φ(c) ≤ φ(z) -φ(c) < 0 and (x [1] ) n (z ) k ⇐⇒ k r=1 a r n r=1 a r > φ(c) -φ(x [1] ) φ(c) -φ(z) .
But given that the absolute weights are non-summable, there must exist k such that

k r=1 a r n r=1 a r > φ(c) -φ(x [1] ) φ(c) -φ(z) so that (x [1]
) n (z) k and therefore x (z k ) n . This contradicts Avoidance of the Very Sadistic Conclusion.

Case 4: The swo on X is proper rank-dependent. Let us check that satisfies all the required properties.

Because is proper rank-dependent a 2 > 0 and (a 1 + a 2 )/a 1 > 1. By continuity of φ, for any y ∈ R ++ such that y > c there exists z ∈ R ++ such that

1 < φ(y) -φ(c) φ(z) -φ(c) < a 1 + a 2 a 1 so that (a 1 + a 2 ) φ(z) -φ(c) > a 1 φ(y) -φ(c)
. By definition of a simple rankdependent generalized utilitarian swo, this implies that (z) 2 (y) 1 . Avoidance of the Reversed Repugnant Conclusion is satisfied.

Because is proper rank-dependent so that +∞ r=1 a r < +∞, it is also the case that for any ε ∈ R ++ there exists ∈ N such that +∞ r=1 a r / r=1 a r < 1 + ε.

Thus consider ∈ N, y ∈ R --such that +∞ r=1 a r r=1 a r < φ(c) -φ(y) φ(c) -φ(0) = 1 + φ(0) -φ(y) φ(c) -φ(0) .
Let us show that (0) k (y) for any k ∈ N. For this to be the case, we need that

k r=1 a r φ(0)-φ(c) ≥ r=1 a r φ(y)-φ(c) for all k ∈ N. Given that 0 ≤ c, a sufficient condition is then that +∞ r=1 a r φ(c) -φ(0) ≤ r=1 a r φ(c) - φ(y) ,
∈ N such that +∞ r=1 a r k r=1 a r < φ(y) -φ(0) φ(z) -φ(0) = 1 + φ(y) -φ(z) φ(z) -φ(0) .
Hence, for all m ≥ ≥ k: Let z < 0 be the well-being level in the statement of Weak Non-Sadism Condition, and k the integer in this statement. For ≥ k, let θ = [( +k)φ(ŷ)kφ(z)]/ . When is large enough, θ can become arbitrary close to φ(ŷ), so that φ -1 (θ ) is well-defined (φ is continuous and increasing and thus invertible). Let ¯ be an integer such that φ -1 (θ¯ ) is well-defined and denote ζ = φ -1 (θ¯ ). In conclusion, for any k ∈ N, ŷ ∈ R ++ and ẑ ∈ [0, ŷ], there exists m > ¯ such that (ẑ)¯ + m (ẑ)¯ +k . This is a violation of Avoidance of the Repugnant Conclusion.

Proof of Proposition 8.

By Weak Non-Sadism Condition, there exist z < 0 and k ∈ N such that, for any z < z and y ∈ R ++ : (z ) 1 , (y) k+1 (z ) 1 , (z) k . By definition of an egalitarian swo and transitivity, this implies that (z ) k+2 (z ) k+1 . This is a violation of Negative Mere Addition Principle.

Proof of Proposition 9.

Let us (without loss of generality) normalize function φ so that φ(0) = 0.

The simple rank-dependent swo satisfies Weak Non-Sadism Condition. Assume that function φ is concave and bounded above and that there exists κ ∈ R ++ such that, for all k ∈ N, a k ≥ κ • +∞ r=k+1 a r . Let ū := sup{φ(z) : z ∈ R}. Choose ẑ ∈ R --such that9 -φ(ẑ) > ū κ .

(5)

Then, for any initial distribution x ∈ X, let r 1 be the highest rank of an individual with well-being strictly lower than ẑ and r 2 the highest rank of an individual with well-being strictly lower than 0. By definition of a simple rank-dependent , for any and ∈ N, we have x, (0)

x, (ẑ) 1 if and only if: a r (φ(0) -φ(c)) .

Given that φ(0) = 0, this sufficient condition can be written This sufficient condition is thus satisfied.

Therefore we have shown that there exist ẑ ∈ R --such that x, (0) x, (ẑ) 1 for any ∈ N. The Suppes-Sen principle implies that, for any y ∈ R ++ x, (y)

x, (0) , and by transitivity x, (y)

x, (ẑ) 1 .

The simple rank-dependent swo satisfies Negative Mere Addition Principle. Consider any x ∈ X and any z ∈ R --. Let r 1 be the highest rank of an individual with well-being strictly lower than z and r 2 the highest rank of an individual with well-being strictly lower than c. By definition of a simple rank-dependent swo x

x, (z) 1 if and only if: By definition of r 1 and r 2 the left-hand side of the above inequality is strictly negative, while the right-hand side is non-negative. Hence inequality (7) holds, and therefore x x, (z) 1 .

  Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée) Rank-discounting and population ethics (a) The swo fails minimal aggregation if and only if lim ρ→0 + F (ρ) = 1 (so that is egalitarian).(b) The swo fails minimal non-aggregation if and only if lim ρ→0 + F (ρ) < 1 (this includes any prioritarian swo).

  Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

a

  r φ(z + ). Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

  But given that the absolute weights are non-summable, there must exist m such Rank-discounting and population ethics that

  which is true by definition of and y. For any z ∈ R ++ and any k ∈ N, (z) k (0) k and therefore (z) k (y) . Hence Avoidance of the Very Sadistic Conclusion is satisfied.If c > 0, for any y > c > z > 0 and for any m ≥ , by definition of a simple rank-dependent generalized utilitarian swo, (y) (z) m so that Avoidance of the Repugnant Conclusion is satisfied. If c = 0 then for any y > z > 0, because is proper rank-dependent, there exists k

  φ(z) -φ(0) . By definition of a simple rank-dependent generalized utilitarian swo, (y) (z) m . Hence Avoidance of the Repugnant Conclusion is satisfied. Proof of Proposition 7. Consider any k ∈ N, ŷ ∈ R ++ , ẑ ∈ [0, y] and ŵ ∈ (0, z).

  By definition of a prioritarian swo, (ζ)¯ , (z) k ∼ (ŷ)¯ +k . But, by Weak Non-Sadism Condition, for any m ∈ N, (ζ)¯ , ( ŵ) m (ζ)¯ , (z) k . However, for m large enough we have: ¯ φ(ζ) + mφ( ŵ) < ( ¯ + m)φ(ẑ), because ŵ < ẑ. Thus, by definition of a prioritarian swo, there exists m large Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée) Rank-discounting and population ethics enough (and in particular such that m > k) such that (ẑ)¯ + m (ζ)¯ , (z) m . By transitivity of social welfare orderings, (ẑ)¯ + m (ŷ)¯ +k .

aa

  r φ(x [r] ) -φ(c) + a r 1 +1 (φ(ẑ) -φ(c)) + n(x)+1 r=r 1 +2 a r φ(x [r-1] ) -φ(c) φ(0) > φ(x [r] ) ≥ φ(ẑ) for all r 2 ≥ r > r 1 , we have a r 1 +1 (φ(ẑ) -φ(c)) + r 1 +r 2 +1 r=r 1 +2 a r φ(x [r-k] ) -c ≤ r 1 +r 2 r=r 1 +1 a r φ(x [r] ) -c + a r 1 +r 2 +1 (φ(ẑ) -φ(c)) ,and,n(x)+1 r=r 1 +r 2 +2 a r φ(x [r-k] ) -φ(c) ≤ n(x)+1 r=r 1 +r 2 +2 a r (ū -φ(c)) < +∞ r=r 1 +r 2 +2 a r (ū -φ(c)) . r φ(x [r] ) -φ(c) + a r 1 +1 (φ(ẑ) -φ(c)) + n(x)+1 r=r 1 +2 a r φ(x [r-1] ) -φ(c) < r 1 +r 2 r=r 1 +1 a r φ(x [r] ) -c + a r 1 +r 2 +1 (φ(ẑ) -φ(c)) + +∞ r=r 1 +r 2 +2 a r (ū -φ(c)) .Also, given that φ(x [r] ) ≥ φ(0) for all r ≥ r 2 +1 and 0 ≤ c (so that φ(0)-φ(c) ≤ 0):r 1 +r 2 + r=r 1 +r 2 +1 a r (φ(0) -φ(c)) + +n(x) r=r 1 + +r 2 +1 a r φ(x [r-] ) -φ(c) r=r 1 + +r 2 +1 a r φ(x [r-] ) -φ(c)Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)Rank-discounting and population ethicsA sufficient condition for inequality (6) to hold is therefore: a r 1 +r 2 +1 (φ(ẑ) -φ(c))+ +∞ r=r 1 +r 2 +2 a r (ū -φ(c)) ≤ +∞ r=r 1 +r 2 +1

a r 1

 1 +r 2 +1 φ(ẑ) + +∞ r=r 1 +r 2 +2 a r ū ≤ 0.But we know that:1 κ ≥ +∞ r=k+1 a r a kfor all k ∈ N, and -φ(z) > ū κ .

a

  (x [r] ) -φ(c) + a r 1 +1 (φ(z) -φ(c)) + r φ(x [r] ) -φ(c) + r 2 r=r 1 +1 a r φ(x [r] ) -φ(c) + n(x) r=r 2 +1 a r φ(x [r] ) -φ(c) (7)Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée) Inequality (7) can be written:a r 1 +1 φ(z) -φ(x [r 1 +1] ) + r 2 r=r 1 +2 a r φ(x [r-1] ) -φ(x [r] ) + a r 2 +1 φ(x [r 2 ] ) -φ-a r+1 ) φ(x [r] ) -φ(c)

Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

We actually need stronger measurement conditions except for maximin, a population-size independent version of the egalitarian criterion introduced in Definition

Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

The formal statement of the principle is as follows: Independence wrt. Ordered Vectors. A swo on X satisfies independence wrt. ordered vectors if, for all k ∈ N, all M ⊆ {1, . . . , k} and all x, y ∈ R k , x ∼ y implies x ∼ y whenever x [r] = y [r] and x [r] = y [r] for all r ∈ M and x [r] = x [r] and y [r] = y [r] for all r ∈ {1, . . . , k}\M . Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

With x[-r ] z 3 ỹ[-r ] z

for any essential rank r such that there exists an ordered vector for which increasing the well-being of the individual with r th level of well-being yields a strict social welfare improvement.4 The axioms of Extended Continuity, Montonicity and Restricted Dominance imply that such a level exists and is unique Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

Only Bossert (1990a),Blackorby, Bossert and Donaldson (2005, Chap. 5) and Arrhenius (forthcoming) mention versions of egalitarianism. Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

The leximin ordering k lex over R k is defined as follows. For all x, y ∈ R k : x ∼ k lex y if and only if x [ ] = y [ ] ; x k lex y if and only if there exists r ∈ {1, . . . , k} such x [r] > y [r] and x [ ] = y [ ] for all ∈ {1, . . . , r -1}. Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

Other formalization have been proposed, for instance by[START_REF] Blackorby | Population Issues in Social Choice Theory, Welfare Economics, and Ethics[END_REF]. The formulation is slightly stronger than the one they have, but we think it is in the spirit of Parfit's initial formulation. Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

We use the convention that k-1 r=k u r = 0. Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

There must exists such a ẑ ∈ R --: given that φ(0) = 0 and φ is concave, so that it is not bounded below on R. Documents de travail du Centre d'Economie de la Sorbonne 2017.41R (Version révisée)

* We thank Gustaf Arrhenius, Walter Bossert, Orri Stefánsson and Dean Spears for helpful comments. This chapter is part of the research activities at the Centre for the Study of Equality, Social Organization, and Performance (ESOP) at the Department of Economics at the University of Oslo. ESOP has been supported by the Research Council of Norway through its Centres of Excellence funding scheme (project number 179552). Asheim's research has also been supported by l'IMéRA (Institut d'études avancées d'Aix Marseille Université) and CIREQ (Centre interuniversitaire de recherche en économie quantitative -Montréal). Zuber's research has been supported by Agence nationale de la recherche through the Fair-ClimPop project (ANR-16-CE03-0001-01) and the Investissements d'Avenir program (ANR-10-LABX-93).

Rank-discounting and population ethics criteria, including those that are not simple. For this purpose we first state a principle generalizing Avoidance of the Very Sadistic Conclusion (see Arrhenius, forthcoming, for a discussion of the principle):

Weak Non-Sadism Condition. A swo on X satisfies the weak non-sadism condition if there exist k ∈ N and z ∈ R --such that for all x ∈ X, y ∈ R ++ and ∈ N x, (y)

x, (z) k .

Any prioritarian social welfare ordering will be subject to one of the two problems: either it implies the repugnant conclusion or it cannot satisfy the weak non-sadism condition.

Proposition 7 A prioritarian swo on X cannot satisfy both Avoidance of the Repugnant Conclusion and Weak Non-Sadism Condition.

Proposition 7 seems to reject prioritarian criteria for population ethics. One could therefore consider egalitarian criteria. However, they are also subject to a population ethics dilemma. They cannot satisfy the weak non-sadism condition if we want to insist on the intuitive principle that we should not create lives with a negative level of well-being.

Negative Mere Addition Principle. A swo on X satisfies the negative mere addition principle if for all x ∈ X and all z ∈ R --, x

x, (z) 1 .

Proposition 8 An egalitarian swo on X cannot satisfy both Weak Non-Sadism Condition and Negative Mere Addition Principle.

In contrast with these negative results, proper and regular simple rank-dependent swos may escape all the population dilemma we have discussed up to now provided function φ is concave and bounded above.

Proposition 9 Assume that a swo on X is a simple rank-dependent generalized utilitarian swo. Then satisfies Weak Non-Sadism Condition and Negative Mere Addition Principle if is proper and regular rank-dependent and the function φ is concave and bounded above.

Note that, by Proposition 6, we already know that the simple rank-dependent generalized utilitarian swo described in Proposition 9 satisfies Avoidance of the Repugnant Conclusion, Avoidance of the Very Sadistic Conclusion and Avoidance of the Reversed Repugnant Conclusion. So we obtain a family of swos that comply with many population ethics requirements. This family deserves receiving further attention.


Da-Jung Cho
email: da-jung.cho@lsv.fr

Yo-Sub Han

Hwee Kim
email: hweekim@mail.usf.edu

Kai Salomaa
email: ksalomaa@cs.queensu.ca

Kai Salomaa Site-Directed

Site-Directed Deletion

Keywords: Bio-inspired operations, Site-directed deletion, Closure properties, Decidability, Automata theory

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A deletion operation is one of the well-established operations [START_REF] Dassow | Operations and language generating devices suggested by the genome evolution[END_REF][START_REF] Domaratzki | Deletion along trajectories[END_REF][START_REF] Han | State complexity of deletion and bipolar deletion[END_REF][START_REF] Ito | Insertion and deletion closure of languages[END_REF][START_REF] Kari | Deletion operations: closure properties[END_REF]. We focus on a variant of deletion, site-directed deletion mutagenesis, which can be performed in vitro, whose goal is to create a deletion on a given gene sequence under enzymatic activities [START_REF] Reikofski | Polymerase chain reaction (PCR) techniques for sitedirected mutagenesis[END_REF]. The activity under DNA polymerase requires a single-stranded DNA segment (called a template) and primers designated to form a partially double-stranded region with the template. In particular, primers complementarily bind to a given template excluding a region to be deleted and extend to the end of the template forming a double-stranded DNA segment.

From the formal language viewpoint, Head et al. [START_REF] Head | Splicing systems: Regularity and below[END_REF] and Kari and Kopecki [15] considered a splicing system inspired by DNA recombination under enzymatic activities. Kari and Thierrin [START_REF] Kari | Contextual insertions/deletions and computability[END_REF] modeled a contextual deletion that occurs in a context sensitive manner: It deletes a string v from a string u only if certain contexts are presented in a given set C. Furthermore, Daley and McQuillan [START_REF] Daley | Template-guided DNA recombination[END_REF], and Enaganti et al. [START_REF] Enaganti | Further remarks on DNA overlap assembly[END_REF][START_REF] Enaganti | A formal language model of DNA polymerase enzymatic activity[END_REF] studied operations inspired by the action of DNA polymerase enzyme that plays a major role in DNA recombination. Recently, Cho et al. [START_REF] Cho | Outfix-guided insertion[END_REF] studied the site-directed insertion operation 6 that inserts a string y at a specific position of x according to the matching outfix of x.

We define a new operation called site-directed deletion that partially deletes a substring from a given string x based on a guide string y that specifies which part of a substring can be deleted. In other words from a biological viewpoint, x is a template and y is a guide primer with information of the region to be deleted. We say that a site-directed deletion occurs on x if a site-directed deletion of x and y partially deletes a substring from x guided by y. This is analogous to the contextual deletion operation studied by Kari and Thierrin [START_REF] Kari | Contextual insertions/deletions and computability[END_REF]. A contextual deletion of a string y from x occurs only if certain contexts exist in a given set C of contexts. Roughly speaking, contextual deletion specifies y-a string to be deleted-according to a set C whereas site-directed deletion deletes a substring from x according to y. Fig. 1 illustrates the difference among ordinary, contextual and site-directed deletions.

A site-directed deletion successfully generates a desired DNA sequence in vitro if a primer is designed to complementarily interact with a template which can result in the desired DNA sequence. From the formal language viewpoint, we consider a question of deciding whether or not the template and primer interact each other as desired. We show linear time algorithms to determine whether or not the site-directed deletion (SDD) of two strings x and y is not empty and whether or not the site-directed deletion of x and y results in a given string z. We show that regular languages are closed under site-directed deletion, whereas context-free languages are not, and we give a context-free language L which is not closed under iterated site-directed deletion. Finally, we consider decidability for sdd-closedness and sdd-freeness on a language L.

Preliminaries

Let Σ be a finite alphabet of characters and Σ * be the set of all strings over Σ. The symbol ∅ denotes the empty language and the symbol λ denotes the empty string. Given a string x, |x| denotes the length of x and x R denotes the reversal of

x. A string x = x[1]x[2] • • • x[n] ∈ Σ n is a finite sequence of n symbols. For 1 ≤ i ≤ j ≤ n, we denote x[i : j] = x[i]x[i + 1] • • • x[j]. Given a string x = uv,
where u, v ∈ Σ * , we say that u is a prefix of x and v is a suffix of x. Given a string y = uwv, where u, w, v ∈ Σ * , we say that (u, v) is an outfix of y. If u = λ and v = λ, then we say that (u, v) is a non-trivial outfix of y. Sometimes (in particular, when talking about the site-directed deletion operation) we call an outfix (u, v) simply a string uv (when it is known from the context what the components u and v are). Given a language L, we use L to denote the complement of L; L = Σ * \ L.

A E G I B F J A C B D I H J x z y D C C D H H to be deleted guided position guided position A E G I B F J x D C H y E G F to be deleted (u, v) ∈ C C D H u v A C B D I H J z A C E G I B D F H J A C B D I H J (
A nondeterministic finite automaton (NFA) is a tuple A = (Σ, Q, δ, q 0 , F ), where Σ is an input alphabet, Q is a finite set of states, δ : Q × Σ → 2 Q is a multivalued transition function, q 0 ∈ Q is the initial state and F ⊆ Q is a set of final states. In the usual way, δ is extended as a function Q × Σ * → 2 Q and the language recognized by A is L(A) = {w ∈ Σ * | δ(q 0 , w) ∩ F = ∅}. The automaton A is a deterministic finite automaton (DFA) if δ is a single valued partial function. A sequence q 0 , q 1 , . . . , q n of states denotes a path. A string w is accepted by A if there is a labeled path from q 0 to q n ∈ F , and we call this path an accepting path.

We now introduce a new operation called a site-directed deletion that formalizes an enzymatic reaction called the site-directed deletion mutagenesis.

Definition 1. The site-directed deletion from a string x by y is

x sdd ← y = {x 1 uvx 2 | x = x 1 uwvx 2 , y = uv, u = λ and v = λ}.
We say that y is a deletion guide of x if x sdd ← y = ∅. ⇒ z to indicate that z is obtained by x sdd ← y. Note that a string x is obtained from itself by selecting the outfix to be x itself, in other words x ⇒ x, when |x| ≥ 2. The site-directed deletion operation can be extended to languages as follows:

We use the notation x

L 1 sdd ← L 2 = wi∈Li,i=1,2 w 1 sdd ← w 2 .
We define the iterated site-directed deletion on a language, which is an iterated version of the site-directed deletion operation. Definition 2. Site-directed deletion SDD of L is inductively defined as

SDD (0) (L) = L, and SDD (i+1) (L) = SDD (i) (L) sdd ← SDD (i) (L), i ≥ 0. The iterated site-directed deletion SDD * of L is SDD * (L) = ∞ i=0 SDD (i) (L).

Decidability of Site-Directed Deletion on Strings

We first consider the question of determining whether or not a string y can be a deletion guide of a string x; in other words, is x sdd ← y = ∅? The sitedirected deletion mutagenesis deliberately creates mutant DNA sequences using designed DNA sequences-a source DNA sequence to be partially deleted, a DNA sequence that contains the target mutant region and designed primers that indicate a starting point of synthesis. Given two strings x and y, a DNA sequence that contains a target mutant region is a deletion-guide y of a source DNA sequence x. Note that site-directed deletion cannot create a mutant DNA sequence if a DNA sequence containing a mutant region does not interact with a source DNA sequence. Thus, it is important to check whether or not designed DNA sequences can interact each other. We present a linear time algorithm that determines whether or not x sdd ← y = ∅. Theorem 1. Given two strings x and y, we can determine whether or not

x sdd ← y = ∅ in O(n) time, where |x| = n, |y| = m and m ≤ n.
Proof. Our goal is to determine whether or not there exist two substrings u, v of x such that y = uv. In other words, we look for a pentuple (g, h, i, j, k) that satisfies the following conditions:

1. y[1 : g] = x[j-g+1 : j] 2. y[m-h+1 : m] = x[k : k+h-1] 3. j -g + i ≤ k + h -m + i 4. i ≤ g 5. m -i ≤ h
Suppose there exists a pentuple (g, h, i, j, k) that satisfies all five conditions. Also suppose that there exists g such that y[1 : g ] = x[j-g +1 : j] and g < g. If i ≤ g , then i ≤ g and (g, h, i, j, k) also satisfies the five conditions. Therefore, for each index in x, we need to find the longest prefix of y that ends at j and the longest suffix of y that starts from k. We check the required conditions using a modified Aho-Corasick algorithm [START_REF] Aho | Efficient string matching: an aid to bibliographic search[END_REF].

Using all prefixes of y and y R as two dictionaries, we construct two Aho-Corasick automata A P and A S where the output function from a state directs to the longest matching pattern. Since we use prefixes of a string as a dictionary, it is straightforward that these modified automata can be built in O(m) time using O(m) space. The result is two lists of pairs (j, g), (k, h) of indices from A P and A S , where the first element indicates the ending (starting, respectively) index and the second elements indicates the length of the longest matched pattern.

In condition 3, the inequality indicates that m ≤ (g -j) + (k + h). From conditions 4 and 5, we know that m ≤ g +h. On the other hand, if two conditions m ≤ (g -j) + (k + h) and m ≤ g + h are satisfied, then we can find i = g that satisfies conditions 3, 4 and 5.

We store j and k using g and h as indices respectively. Moreover, to check the condition m ≤ (g -j) + (k + h), we only need to keep the smallest j and the largest k for same g and h, respectively. Constructing such two arrays j We next consider a problem of determining whether or not z ∈ x sdd ← y for given strings x, y and z. The biological implication of z ∈ x sdd ← y is that a sitedirected deletion mutagenesis by PCR (Polymerase Chain Reaction) successfully generates a desired DNA sequence, which is denoted by z. We show that the problem can be solved in linear time. Proof. Suppose that there exist three strings x[1 : n], y[1 : m] and z[1 : l] such that z ∈ x sdd ← y, where n, m, l ≥ 2. Then there are decompositions of strings x = x 1 uwvx 2 , y = uv and z = x 1 uvx 2 , where x 1 , x 2 , w ∈ Σ * and u, v = λ. We decide whether or not z ∈ x sdd ← y as follows:

1. Scanning x and z for finding common prefix x 1 u and suffix vx 2 :

We scan both ends of x and z until a mismatch occurs-in other words, we find the longest matching prefix and suffix between x when y appears within the search-range using a similar argument. We check the existence of y within the search-range in O(m) time using the KMP algorithm [START_REF] Knuth | Fast pattern matching in strings[END_REF]. Thus, the total runtime is O(n).

4 Closure Properties and Decidability on Languages Proof. Let L 1 be recognized by an NFA A = (Q A , Σ, δ, q 0 , F A ) and L 2 be recognized by an NFA B = (Q B , Σ, γ, p 0 , F B ). Let

Q A = { q | q ∈ Q A } such that Q A is disjoint with Q A . We construct an NFA C = (Q C , Σ, ω, s, F C ) recognizing all strings of L 1 sdd ← L 2 , where Q C = Q A × ({♣, ♥} ∪ Q B ) ∪ Q A × Q B , s = (q 0 , ♣) and F = {(q, ♥) | q ∈ F A } ∪ {( q, p) | q ∈ F A , p ∈ F B }.
Let α be an arbitrary symbol of Σ. We set the following transitions of ω:

(i) for q ∈ Q A , ω((q, ♣), α) = {(q , ♣ | q ∈ δ(q, α)}∪{(q , p ) | q ∈ δ(q, α) and p ∈ γ(p 0 , α)}, (ii) for q ∈ Q A and p ∈ Q B , ω((q, p), α) ∈ {(q , p ) | q ∈ δ(q, α) and p ∈ γ(p, α)} ∪ {( q , p ) | q ∈ δ(q, α), q ∈ δ(q , λ), p ∈ γ(p, α) and q ∈ Q A }, (iii) for q ∈ Q A and p ∈ Q B , ω(( q, p), α) ∈ {( q , p ) | q ∈ δ(q, α) and p ∈ γ(p, α)} ∪ Z q , where

Z q = {(q , ♥) | q ∈ δ(q, α)} if p ∈ F B , ∅ if p ∈ F B ,
(iv) for q ∈ Q A , ω((q, ♥), α) = {(q , ♥) | q ∈ δ(q, α)}.

All transitions not listed above are undefined. We show that L(A) sdd ← L(B) ⊆ L(C). Let x 1 uwvx 2 ∈ L(A) and uv ∈ L(B), where x 1 , x 2 , w ∈ Σ * and u, v ∈ Σ + . The construction is based on the idea that C uses the states (q, ♣) of C to process the prefix x 1 , the states (q, p) to process the following substring u, the states ( q, p) to process the substring v and the states (q, ♥) to process the following substring x 2 . Let P A (x) be an accepting path q 0 , . . . , q x1 , . . . , q u , . . . , q w , . . . , q u , . . . , q x2 of x ∈ L(A) and P B (y) be an accepting path p 0 , . . . , p u , . . . , p v of y ∈ L(B). From the initial state (q 0 , ♣) of C the transition rule (i) allows C to simulate the path q 0 , . . . , q x1 of P A (x 1 uwvx 2 ) reaching a state (q x1 , ♣). When the first symbol α of u appears, the transition rule (ii) allows C to simulate both paths q x1 , . . . , q u of P A and p 0 , . . . , p u of P B . Note that the transition (ii) allows C to nondeterministically enter the state ( q w , p u ) which shows that C simulates the path q u , . . . , q w of P A reading w. Then, the transition (iii) allows C to simulate both paths q w , . . . , q v of P A and p u , . . . , p v of P B , and C enter the state ( q v , p v ). Note that C enter the state (q v , ♥) if p v ∈ F B . The transition (iv) allows C to simulate the remaining path q v , . . . , q x2 of P A , and simulation ends in an accepting state (q x2 , ♥), where q x2 ∈ F A .

We now show that if C recognizes a string x 1 uvx 2 , then A recognizes a string x 1 uwvx 2 and B recognizes a string uv, in other words; L(C) ⊆ L(A) sdd ← L(B). We decompose an accepting path (q 0 , ♣), . . . , (q x2 , ♥) for a string z = x 1 uvx 2 ∈ L(C) into four paths P 1 , P 2 , P 3 and P 4 such that (q 0 , ♣), . . . , (q x1 , ♣) P1 , (q x1 , p s ), . . . , (q u , p u ) P2 , ( q w , p u ), . . . , ( q v , p v )

P3

, and (q v , ♥), . . . , (q x2 , ♥)

P4

.

Path P 1 shows that there is a path q 0 , . . . , q x2 in P A that recognizes a string x 1 . Path P 2 shows that there exist paths q x1 , . . . , q u of P A and p 0 , . . . , p u of P B that recognize a string u, and path P 3 shows that there exist paths q u , . . . , q v of P A and p u , . . . , p v of P B that recognize a string v. Note that based on the transitions (ii), C nondeterministically enters a state ( q, p u ) from (q u , p u ), then, C simulates a path q, . . . , q w of P A reaching ( q w , p u ). Path P 4 shows that C only simulates a path q v , . . . , q x2 of P A , and the simulation ends on the final state (q x2 , ♥). It implies that if C accepts a string x 1 uvx 2 , then there exist accepting paths on A and B that recognize strings x 1 uwvx 2 and uv. Theorem 4. There exist context-free languages L 1 and

L 2 such that L 1 sdd ← L 2 is not context-free. Proof. Consider two context-free languages L 1 = {a n $b n $%c m # | n, m ≥ 1} and L 2 = {$b n $c n # | n ≥ 1}. Then, the language (L 1 sdd ← L 2 ) ∩ (a * $b * $c * #) = {a n $b n $c n # | n ≥ 1} is not context-free.
The proof of Theorem 5 is omitted due to the limitation on the number of pages.

Theorem 5. Given a context-free language L 1 and a regular language L 2 , L 1 sdd ← L 2 and L 2 sdd ← L 1 are context-free. Theorem 6. There exists a context-free language L such that SDD * (L) is not context-free.

Proof. Let Σ = {a, b, c, $, %, #} and define L = L 1 ∪L 2 , where L 1 = {#a n $b n $%c m # | n, m ≥ 1} and L 2 = {$b n $c n # | n ≥ 1}. Denote M 1 = #a + $b + $%c + #, M 1 = #a + $b + $c + # and M 2 = $b + $c + # (and thus L 1 ⊆ M 1 and L 2 ⊆ M 2 ).
We observe the following properties:

(i) It is not possible to use a string y ∈ M 1 ∪ M 1 as a deletion guide for a string x ∈ M 2 (because strings of M 2 contain only one occurrence of #). (ii) Using a string in M 1 ∪ M 1 as a deletion guide for a string in M 1 ∪ M 1 can be done only in a trivial deletion step (that produces the original deletion guide). (iii) Using a string in M 2 as a deletion guide for a string in M 2 can be done only in a trivial deletion step. (iv) Using a string in M 2 as a deletion guide for strings of M 1 ∪ M 1 always produces a string in M 1 .

We explain observation (iv) below. The first three observations follow directly from the definition of site-directed deletion. Consider z ∈ x sdd ← y where x ∈ M 1 ∪ M 1 and y ∈ M 2 . The end-marker # of y must be matched with the last symbol of x and the two occurrences of $ in y must be matched with the two occurrences of $ in the string x. This means that z must be the result of deleting from x ∈ M 1 the symbol % and zero or more symbols c and, if x ∈ M 1 , z must be the result of deleting from x zero or more symbols c. Not all c's can be deleted because the string y ∈ M 2 contains at least one c. Thus, in both cases z ∈ M 1 .

Since trivial deletion steps produce only the original deletion guide, observations (i)-(iv) imply that

L ∪ SDD (1) (L) = L 1 ∪ L 2 ∪ (L 1 sdd ← L 2 ),
and in particular,

L ∪ SDD (1) (L) = L 1 ∪ L 2 ∪ {#a n $b n $c n # | n ≥ 1}. (1)
The last equality is verified as in the proof of Theorem 4. Note that our current construction is a modification of the construction used in the proof of Theorem 4. Now L 1 sdd ← L 2 ⊆ M 1 and none of the deletion steps (i)-(iv) produces new strings of M 2 (the steps (ii) and (iii) must use a trivial deletion step). This means that using induction on k and the observations (i)-(iv), we get that k+1 i=0

SDD (i) (L) = L 1 ∪ L 2 ∪ (SDD (k) (L) sdd ← L 2 ),
and, thus, SDD * (L) consists of L and strings obtained from L by iterated deletions that all use a string in L 2 as a guide.

When using a string y ∈ L 2 as a deletion guide for a string x ∈ {#a n $b n $c n # | n ≥ 1}, the only possibility is to match y with a suffix of x, because the string x has the same number of b's and c's and the string y has the same property. When y is matched with a suffix of x, the result of the deletion is just x. This means that iterating the deletions does not produce anything new and SDD * (L) = L ∪ SDD (1) (L) and from equation [START_REF] Aho | Efficient string matching: an aid to bibliographic search[END_REF]

we get that SDD * (L) ∩ #a + $b + $c + # = {#a n $b n $c n # | n ≥ 1} which is not context-free.
Closure of regular languages under iterated site-directed deletion remains open.

Decidability of sdd-closed and sdd-free Languages

A language L is sdd-closed if L sdd ← L ⊆ L, which implies that L does not generate a string that is not in L under the site-directed deletion operation. A language L is sdd-free if x sdd ← y = ∅, where x, y ∈ L and x = y. Note that a string in L is obtained only from itself by site-directed deletion if L is sdd-free.

We show that it is decidable whether or not a given language L is sdd-closed when L is regular and is undecidable when L is context-free.

Theorem 7. Given a regular language L, it is decidable in polynomial time whether or not L is sdd-closed. Theorem 8. For a given context-free language L, determining whether or not L is sdd-closed is undecidable.

Proof. Let ((u 1 , . . . , u n ), (v 1 , . . . , v n )) be an instance of the Post's Correspondence Problem (PCP) [START_REF] Post | A variant of a recursively unsolvable problem[END_REF], where u i , v i ∈ Σ * and 1 ≤ i ≤ n. A solution for the instance is a sequence of integers (i 1 , . . . , i k ), i j ∈ {1, . . . , n}, j = 1, . . . , k such that

u i1 • • • u i k = v i1 • • • v i k .
It is well known that the PCP is undecidable [START_REF] Post | A variant of a recursively unsolvable problem[END_REF]. Let Σ = Σ ∪ {#, %, ¢}.

We consider a context-free language L = L 1 ∪ L 2 , where

L 1 = {¢$i 1 i 2 • • • i r #u R ir u R ir-1 • • • u R i1 #%#v j1 v j2 • • • v js #j s j s-1 • • • j 1 $¢} and L 2 = {$i 1 i 2 • • • i r #w##w R #i r i r-1 • • • i 1 $}
for w ∈ Σ * , 1 ≤ r, s, and 1 ≤ i r , j s ≤ n. Then, L has two types of string

w 1 = ¢$i 1 i 2 • • • i r #u R ir u R ir-1 • • • u R i1 #%#v i1 v i2 • • • v ir #i r i r-1 • • • i 1 $¢ ∈ L 1 , and
w 2 = $i 1 i 2 • • • i r #u R ir u R ir-1 • • • u R i1 ##u i1 u i2 • • • u ir #i r i r-1 • • • i 1 $ ∈ L 2 . Here, w = u R ir u R ir-1 • • • u R i1 and it follows w R = u i1 u i2 • • • u ir-1 .
We claim that the PCP has a solution if and only if L is not sdd-closed, and we prove both implications of the claim.

• "If the PCP has a solution, then L is not sdd-closed": Suppose that (i 1 , . . . , i r ) is a solution for the PCP, which implies

u i1 u i2 • • • u ir = v i1 v i2 • • • v ir .
We decompose w 1 = x 1 uwvx 2 and w 2 = uv, where x 1 , x 2 = ¢, w = %, and

u = $i 1 i 2 • • • i r #u R ir u R ir-1 • • • u R i1 #, v = #u i1 u i2 • • • u ir-1 #i r i r-1 • • • i 1 $.
Then, the claim holds that L is not sdd-closed since

w 1 sdd ← w 2 = ¢$i 1 i 2 • • • i r #w##w R #i r i r-1 • • • i 1 $¢,
which is not in L-there is no string contains all occurrences of symbols ¢, $ and # without the symbol %.

• "If the PCP has no solution, then L is sdd-closed": We consider two strings

w 1 = ¢$i 1 i 2 • • • i r #u R ir u R ir-1 • • • u R i1 #%#v j1 v j2 • • • v js #j s j s-1 • • • j 1 $¢ ∈ L 1 and w 2 = $i 1 i 2 • • • i r #u R ir u R ir-1 • • • u R i1 ##u i1 u i2 • • • u ir #i r i r-1 • • • i 1 $ ∈ L 2 .
We consider the following four possible cases of L sdd ← L, and show that there is a contradiction of the assumption. (iv) L 1 sdd ← L 2 : Suppose that w 2 ∈ L 2 is a deletion guide of w 1 ∈ L 1 such that w 1 = x 1 uwvx 2 and w 2 = uv, where u, n = λ. Since w 1 begins and ends with ¢, and w 2 does not contain occurrences of ¢, in the decomposition of w 1 , the first symbol ¢ must be in x 1 and the last symbol ¢ must be in x 2 . Similarly, in the decomposition of w 1 , % must be in w since w 2 does not contain %. As an outfix (u, v) of a substring of w 1 should be w 2 = uv when w 2 is a deletion-guide of w 1 , it follows that

(i) L 1 sdd ← L 1 : A string w 1 ∈ L 1 itself is a deletion guide of w 1 ,
u = $i 1 i 2 • • • i r #u R ir u R ir-1 • • • u R i1 # and v = #v j1 v j2 • • • v js #j s j s-1 • • • j 1 $, where r = s, i r = j r and v j1 v j2 • • • v js = u i1 u i2 • • • u ir-1 = (u R ir u R ir-1 • • • u R i1 ) R . Thus, (i 1 , . . . , i r ) is a solution for the PCP-a contradiction.
Therefore, it is undecidable whether or not L is sdd-closed since the PCP is undecidable.

We also show that it is decidable whether or not L is sdd-free in polynomial time when L is regular, and it is undecidable when L is context-free. The insertion of y into x in an arbitrary place in x is defined as the set of strings [START_REF] Han | State complexity of insertion[END_REF][START_REF] Kari | Insertion operations: closure properties[END_REF]. We use the closure property of regular languages under the insertion operation. When L is regular the language on the left-side of the equation of Lemma 1 is regular. Theorem 9 is proved using Lemma 1.

x ins ← y = {x 1 yx 2 | x = x 1 x 2 and x 1 , x 2 ∈ Σ * }
Theorem 9. Given an NFA A, we can decide in polynomial time whether or not L(A) is sdd-free.

Theorem 10. It is undecidable whether or not a context-free language L is sddfree.

We now consider the question of determining whether or not sdd-closed and sdd-free languages preserve their properties. We establish the following results which characterize sdd-closed and sdd-free languages with respect to basic operations such as intersection, union, catenation and complement. Notice that the basic operations are widely used in molecular biology, biochemistry and pharmacology, for instance, a complement under enzymatic activities inhibits an enzymatic activation that causes a disease or inflammation [START_REF] Gasque | Complement components of the innate immune system in health and disease in the CNS[END_REF].

Theorem 11. sdd-closed languages are closed under intersection and complement but not closed under union and catenation.

Theorem 12. sdd-free languages are closed under intersection but not closed under union, compliment and catenation.

Conclusions

From a site-directed deletion mutagenesis under enzymatic activities, we have introduced the site-directed deletion operation. We have designed linear time algorithms for determining whether or not x sdd ← y = ∅ and z ∈ x sdd ← y. We have shown that L 1 sdd ← L 2 is regular when L 1 and L 2 are regular, however, L 1 sdd ← L 2 may not be context-free when L 1 and L 2 are context-free. Given a context-free language L 1 and a regular language L 2 , both L 1 sdd ← L 2 and L 2 sdd ← L 1 are context-free. In addition, we have established that it is decidable whether or not a regular language L is sdd-closed and sdd-free in polynomial time, and it is undecidable whether or not a context-free language is sdd-closed and sdd-free.

Research & Development Program of NRF (2017K1A3A1A12024971). Kim was supported in part by the NIH grant R01 GM109459. Salomaa was supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.

Fig. 1 :

 1 Fig. 1: Examples of ordinary deletion, contextual deletion and site-directed deletion. (a) An ordinary deletion of x results in a string z removing a substring EF G. The resulting string z is one of many possible deletion outputs. (b) A contextual deletion of x and y with a set C ⊆ Σ * × Σ of contexts results in a string z if there exists an infix uyv of x, where (u, v) ∈ C, uv = CDH and y = EF G. (c) A site-directed deletion of two strings x and y-in other words, a template and a primer, respectively-results in a string z if y = CDH is the catenation of an outfix (CD, H) of a substring CDEF GH of x. The string z is the only possible site-directed deletion output when the guide string is CDH.

  [g] and k[h] requires O(n) time and O(m) space. Note that we have k[h] > k[h+1], since an occurrence of y[m-h+2 : m] that starts at index k guarantees an occurrence of y[m-h+1 : m] that starts at index k+1. Then we start from g = 1 and h = m, and check if j[g] ≤ k[h] + 1. If the condition is satisfied, we know that m ≤ g + h and m ≤ g -j[g] + k[h] + h. If the condition is not satisfied, we increase g and decrease h by 1 continuously and check the condition. The runtime to compare arrays is O(m), and the total runtime becomes O(n).

Theorem 2 .

 2 Given three strings x, y, z ∈ Σ * , we can determine whether or not z ∈ x sdd ← y in O(n) time, where n = |x| and |x| ≥ |z| ≥ |y| ≥ 2.

2 .

 2 [1 : n] and z[1 : l]. Let z[1 : i] = x[1 : i] be the longest matching prefix, and z[l-j+1 : m] = x[n-j+1 : n] be the longest matching suffix, where i, j > 1. When i+1 = l-j+1, we show that the catenation of the longest matching prefix and suffix z[1 : i] • z[l-j+1 : l] equals to z = x 1 uvx 2 . Identifying search-range of z with respect to y: For the case i > l-j+1, which implies that a suffix of z[1 : i] is a prefix of z[l-j+1 : l], we check an occurrence of y within z[l-(j+m)+2 : i+m-1]. We call the range from l-(j+m)+2 to i+m-1 a search-range on z. The search-range is calculated from the assumption that the longest prefix z[1 : i] contains u as an infix, and the longest suffix z[l-j+1 : l] contains v as an infix, where the catenation of u and v becomes y for |u|, |v| ≥ 1. We consider a case where y matches with z[l-j-m+2 : i+m-1]. Suppose y = z[l-j-m+2 : l-j+1]. Then, z[l-j+1 : l] = x[n-j+1 : n] denotes vx 2 and there exists a corresponding prefix x[1 : l-j], which denotes x 1 u, and we show that z ∈ x sdd ← y. 3. Finding y from search-range of z: We can prove for all the other cases

4. 1 Theorem 3 . 1 sdd← L 2

 1312 Closure Properties of Site-Directed Deletion on LanguagesWe show that regular languages are closed under the site-directed deletion, whereas context-free languages are not. Context-free languages are closed under site-directed deletion with regular languages. We give a context-free language L such that SDD * (L) is not context-free. If L 1 and L 2 are regular, then L is regular.

which is obtained by w 1 [ 2 sdd← L 2 :

 122 w1] ⇒ w 1 , and the claim holds that L sdd ← L ⊆ L. (ii) L Similarly, a string w 2 ∈ L 2 is obtained by w 2 [w2] ⇒ w 2 , and it implies that L sdd ← L ⊆ L. (iii) L 2 sdd ← L 1 : A string w 1 ∈ L 1 begins and ends with the symbol ¢, which does not occur in w 2 ∈ L 2 , and it also implies that L sdd ← L ⊆ L.

Lemma 1 .

 1 Consider L ⊆ Σ * . Then L is sdd-free if and only ifL ∩ [Σ + (L ins ← Σ * )Σ * ∪ Σ * (L ins ← Σ + )Σ * ∪ Σ * (L ins ← Σ * )Σ + ] = ∅.

Site-directed insertion has earlier been considered under the name outfix-guided insertion[START_REF] Cho | Outfix-guided insertion[END_REF].

Acknowledgments

We wish to thank the referees for their careful reading of our manuscript and their insightful comments and suggestions that improve the quality of the paper. Cho was supported by Labex DigiCosme (ANR-11-LABEX-0045-DIGICOSME) operated by ANR as part of the program "Investissement d'Avenir" Idex Paris-Saclay (ANR-11-IDEX-0003-02). Han was supported by the Basic Science Research Program through NRF (2015R1D1A1A01060097) and the International