Avner Seror
email: avner.seror@univ-amu.fr

Daniel Chen

Garance Génicot

Jun Hyung Kim

Mathieu Lefebvre

Olivier L'haridon

Thierry Verdier

The Priced Survey Methodology: Theory *

Keywords: JEL C9, D91, C44 Decision Theory, Revealed Preference, Social Preferences, Behavioral Economics, Survey

In this paper, I introduce a novel methodology to conduct surveys. The priced survey methodology (PSM). Like standard surveys, priced surveys are easy to implement, and measure social preferences on numerical scales. The PSM's design draws inspiration from consumption choice experiments, as respondents fill out the same survey several times under different choice sets. I extend Afriat's theorem and show that the Generalized Axiom of Revealed Preferences is necessary and sufficient for the existence of a concave, continuous, and single-peaked utility function rationalizing answers to the PSM. I apply the PSM to a sample of online participants and show that most respondents are rational when answering the PSM. I estimate respondents' single-peaked utility functions and draw several implications on their social preferences.

Introduction

One of the most fundamental contributions of economics to the history of thought is its ability to explain choices by a set of preferences. These preferences encompass consumption goods, attitudes towards risk, time, and social aspects. Specifically, social preferences include aspects such as altruism, identity, environmental concerns, political inclinations, and perceptions of fairness and justice. Although a substantial theoretical literature in economics has focused on the recoverability of preferences over consumption goods [START_REF] Andreoni | Giving According to GARP: An Experimental Test of the Consistency of Preferences for Altruism[END_REF]), risk [START_REF] Choi | Consistency and Heterogeneity of Individual Behavior under Uncertainty[END_REF][START_REF] Choi | Who Is (More) Rational?[END_REF] ;[START_REF] Halevy | Parametric Recoverability of Preferences[END_REF]), and time [START_REF] Dziewulski | Revealed time preference[END_REF]), far less is known about social preferences. As a result, the existing measures of social preferences either implicitly assume the existence of a utility representation that internalizes social aspects of decision-making, or rely on surveys [START_REF] Falk | Global Evidence on Economic Preferences[END_REF]). While these measures are valuable in different contexts, they leave several important points unanswered. To start, little is known about the rationality axioms sustaining the existence of a utility representation for social preferences. Hence, there is no scientific rationale explaining the use and selection of specific utility functions to describe social preferences. As for surveys, they give a snapshot of societal preferences, so the decision mechanisms behind survey answers are unknown. For example, it is not possible to distinguish authentic responses from the ones influenced by the way questions are framed. Moreover, surveys fall short of offering a reliable ground for comparing data, as recently shown by [START_REF] Bond | The Sad Truth about Happiness Scales[END_REF].

In this paper, I introduce a novel methodology to measure social preferences, the Priced Survey Methodology (PSM). While it maintains the simplicity of traditional surveys, the PSM's design draws inspiration from economic concepts of revealed preferences and consumer demand. The fundamental novelty of the PSM is its capacity to allow social scientists to recover the preference ordering embedded in survey responses.

The design of the PSM is close to experiments built to recover preferences from choices on linear budget sets [START_REF] Andreoni | Giving According to GARP: An Experimental Test of the Consistency of Preferences for Altruism[END_REF], [START_REF] Choi | Consistency and Heterogeneity of Individual Behavior under Uncertainty[END_REF], [START_REF] Choi | Who Is (More) Rational?[END_REF], [START_REF] Fisman | The distributional preferences of an elite[END_REF] [START_REF] Halevy | Parametric Recoverability of Preferences[END_REF]) as respondents fill the same survey multiple times under different choice sets. [START_REF] Choi | Consistency and Heterogeneity of Individual Behavior under Uncertainty[END_REF], [START_REF] Choi | Who Is (More) Rational?[END_REF] and [START_REF] Halevy | Parametric Recoverability of Preferences[END_REF] study risk preferences using portfolio choices of Arrow securities. In every round of the PSM, each given participant is not greeted with a blank slate but rather a predetermined default answer. She can however adjust this default to better match her preferences. Participants have a finite pool of credits in each round, and adjusting their answer from the default depletes this pool. The credit cost for changes isn't constant but varies between rounds. With this design, it is as if subjects were "buying" goods when they move from the default.

Example.Deontology vs Utilitarianism. On a scale from 0 to +10, where 0 indicates that you strongly disagree and +10 that you strongly agree, to what extent do you agree with these statements:

1. Human rights should never be compromised, even if it leads to larger societal harm.

2. The needs of the many should sometimes take precedence over the rights of the few.

In the PSM, respondents answer this survey several times, under different choice sets. In each round, the default belongs to one of the four corners of the choice set, and moving from the corners is costly.

The first key contribution of this paper is theoretical. I extend Afriat's theorem, and show that the Generalized Axiom of Revealed Preferences (GARP) is necessary and sufficient for the existence of a concave, continuous, and single-peaked utility function rationalizing survey answers. There are several important implications. First, rather than interpreting the cardinal answers subjects provide to a traditional survey, the PSM enables to estimate -and interpret utility parameters, which are related to the ordinal relations between all possible answers to the survey. This is more than a simple interpretation difference. It is a key improvement, as taking numerical values at face value can be misleading [START_REF] Bond | The Sad Truth about Happiness Scales[END_REF]. In contrast, utility parameters offer a ground for comparing social preferences. Moreover, by estimating the peak of the utility function behind survey answers, experimenters have access to a new measure of a respondent's ideal answer to a survey. This measure is estimated using ordinal relations between survey answers, thereby not subject to issues inherent to cardinal interpretations of scales. Finally, with the PSM, it is possible to measure valuable aspects of social preferences that cannot be captured with traditional surveys such as how people navigate moral dilemmas.

The second key contribution of this paper is to apply the PSM to a sample of 100 online respondents. All participants had to answer a PSM consisting of nine rounds and two questions measuring altruistic and self-interested preferences. I measure the decisionmaking quality by evaluating the consistency of individual choices with the Generalized Axiom of Revealed Preference (GARP), using the CCEI Index (Critical Cost Efficiency Index). I find that respondents reach an average CCEI score of 92%. This is even higher than CCEI scores measured in the consumption choice environment. Second, I used the individual-level data to estimate the following single-peaked utility function:

u i (q) = - S s=1 1 2 a i s q s -b i s 2 .
Vector b i s∈S measures respondent i's ideal answer. It offers a robust alternative to the "ideal point" measured directly through the (cardinal) answer that respondents give to traditional surveys. The key difference with traditional surveys is that the ideal point b i is measured using all rounds of the PSM. Moreover, as b i 's estimation is based on the revealed preference information of the PSM, it is robust to the issues inherent to cardinal interpretations of survey answers [START_REF] Bond | The Sad Truth about Happiness Scales[END_REF]). Vector a i measures the relative importance of different social preferences for respondent i, as measured through survey questions. Concretely, a respondent might answer that she is very altruistic but gives a low weight to altruism, as compared to selfishness.

Although the low number of participants make it difficult to interpret the results, it seems that respondents ideal point, as estimated through the PSM, does not correspond to the answers respondents provide to the traditional survey. Moreover, several aspects of social preferences that cannot be captured by traditional surveys seem to arise. Older respondents seem to be particularly more concerned about their selfish and altruistic values than younger respondents.

Related Literature

The PSM is close to experiments built to recover preferences from choices on linear budget sets [START_REF] Andreoni | Giving According to GARP: An Experimental Test of the Consistency of Preferences for Altruism[END_REF], [START_REF] Choi | Consistency and Heterogeneity of Individual Behavior under Uncertainty[END_REF], [START_REF] Choi | Who Is (More) Rational?[END_REF], Fisman et al. (2015) Halevy, Persitz and[START_REF] Halevy | Parametric Recoverability of Preferences[END_REF]) as respondents fill the same survey multiple times under different choice sets. [START_REF] Choi | Consistency and Heterogeneity of Individual Behavior under Uncertainty[END_REF], [START_REF] Choi | Who Is (More) Rational?[END_REF] and [START_REF] Halevy | Parametric Recoverability of Preferences[END_REF] study risk preferences using portfolio choices of Arrow securities. [START_REF] Andreoni | Giving According to GARP: An Experimental Test of the Consistency of Preferences for Altruism[END_REF] and [START_REF] Fisman | The distributional preferences of an elite[END_REF] are closer to the PSM in spirit as they seek to recover altruistic preferences using modified versions of the dictator game. In all previous experiments, the designs are meant to capture monotonic preferences. Since respondents have ideal points when answering surveys [START_REF] Coombs | A Theory of Data[END_REF]; Jebb, Ng and Tay (2021); [START_REF] Thurstone | Attitudes Can Be Measured[END_REF]), preferences behind survey answers cannot be monotonic, so the previous designs cannot be applied to recover preferences behind survey answers. A key contribution of this paper is to build on the previous designs so that the PSM can enable social scientists to recover single-peaked preferences over survey answers. The PSM can therefore capture a broader set of social preferences than existing studies.

The economic literature on the recoverability of preferences from repeated choices started with Afriat's theorem [START_REF] Afriat | The Construction of Utility Functions from Expenditure Data[END_REF], who established that cyclical consistency was necessary and sufficient to recover preferences that rationalize consumption choice. Various proofs of this theorem exist in the literature (e.g., [START_REF] Varian | The Nonparametric Approach to Demand Analysis[END_REF], [START_REF] Polisson | Afriat's Theorem and Samuelson's 'Eternal Darkness[END_REF], [START_REF] Chambers | Revealed Preference Theory[END_REF]). The theorem has been extended to risk preferences [START_REF] Polisson | Revealed Preferences over Risk and Uncertainty[END_REF]), or to more general choice environments [START_REF] Forges | Afriat's theorem for general budget sets[END_REF], [START_REF] Nishimura | A Comprehensive Approach to Revealed Preference Theory[END_REF]). One key aspect of Afriat's theorem is that the utility function rationalizing choices is monotonic. This property comes from the assumption that ≥ constitutes an exogenous pre-order of the consumption sets. That is, absent constraints on choice, any individual's consumption will tend to infinity. While this assumption can be justified in the analysis of consumption choices, it cannot reasonably hold for social preferences embedded in survey responses. My key contribution to the literature here is be to extend Afriat's theorem to study single-peaked preference domains.

Design and Theory

Notations. Let's consider a PSM with S questions, and K = {1, . . . , K} denotes a set of rounds. I denote X(s) the set of possible answers to question s, and X = Π s∈S X(s) the set of possible answers to the survey S, with X ⊂ R S . Let X o = {q k } k∈K ⊂ X denotes the set of observations, and A the set of subsets of X. I assume that the answer of respondent i to question s belongs to the integer scale X(s) = {0, . . . , N (s)}, although all the results extend to close, countable, and compact sets. The default answer in the kth round is o k ∈ C(X), where C(X) is the set of corners of X. For example, if X = {0, . . . , 10} × {0, . . . , 10}, there are four corners, C(X) = {(0, 0), (10, 0), (10, 10), (0, 10)}.

Design. The PSM has three key design features. First, each respondent answers the same survey K times under different choice sets. Second, in any round k, respondents are presented with a default answer that belongs to one of the corners. Respondents have a budget in tokens R. Deviating from the default answer is costly. It is as if subjects were "buying" goods with their budget when they move from the default. Third, in any round k, the default answer is randomly selected and belongs to one of the corners.

Figure 1 below represents a PSM with three rounds and two questions, both on the set {0, . . . , 10}. A respondent's answer to the PSM in round k can be represented as a vector q k of two integers between 0 and 10. In round 1, represented by Panel (a), the default answer is the point (10, 0). If the respondent submits this as her final answer, she would express a strong agreement with question 1, and a strong disagreement with question 2. The choice set in this round includes all possible answers in the square. Round 1 is then similar to a standard survey of Likert scale questions starting at the default (10, 0). In round 2, represented by Panel (b), the default answer is the origin (0, 0). If the respondent submits this as her final answer, she will express strong disagreement with both statements 1 and 2. She might want to move from this default to a point closer to her ideal point but only has limited options. She chooses to answer q 2 in round 2, where she expresses slightly more agreement with question 1 than with question 2. In round 3, represented by panel (c) of Figure 1, the default answer is the corner (0, 10). If the respondent submits the default answer, she would express strong disagreement with question 1, and strong agreement with question 2. She might want to move to an answer closer to her ideal point, but again has limited options. She chooses q 3 in round 3.

Choice sets. The choice sets are designed as follows. In round 1, respondents are asked to answer the survey when all answers are included in the choice set, as represented in Figure 1 panel (a). In the following rounds, the choice sets are such that the answer to round 1, q 1 , is never attainable. The basic idea is that if a subject is rational when answering the PSM, she would seek to give an answer in any round that is as close as possible to her answer to the first round q 1 . In round 2 for example, she would increase her answers to both question 1 and question 2 in order to express a more neutral answer, similar to what she did in round 1. Having this key feature of the design in mind, I need to introduce some minimum formalization before discussing the link between PSM and the standard consumption choice environment. I denote o the lowest corner of C(X). In the previous example, the lowest corner is o = (0, 0). To alleviate the notation, when I denote q without a subscript, I mean the coordinate of q in the coordinate system whose origin is the lowest corner of C(X). Moving from the corners is costly. p s,k denotes the price in tokens of marginally changing the answer from the default of observation k, question s. In the coordinate system with origin o k , the choice set of observation k can be defined as follows:

B k = {q o k ∈ X such that q o k .p k ≤ R}, (1)
with q o k the coordinates of q in the coordinate system with origin o k , and q o k .p k the scalar product between q o k and p k . A dataset at the individual level will be denoted

D = {q k , B k } k∈K in the rest of this document.
The similarity with the standard consumption choice environment is straightforward from equation (1). In the PSM, it is as if subjects were "buying" goods when they move from the default. Since the ideal answer q 1 is not part of the budget set in round k, subjects should "saturate" their budget set in any given observation k > 1, behaving like (rational) consumers in the different coordinate systems. This is a key intuition behind the recoverability of preferences in the PSM, as it implies that the standard toolkit of consumer choice analysis can be applied in the different coordinate systems.

Axiomatization of survey answers.

I seek to understand when a respondent's behavior is compatible with rational choice. Formally, a preference relation ≽ weakly rationalizes the dataset D if for all observation k and y ∈ X, p k .q k o k ≥ p k .y o k implies q k ≽ y. If no restriction is placed on ≽, then any dataset is weakly rationalizable (we can let ≽ indicate indifference among all the elements of X).

Definition 1 A preference relation ≽ is c-monotonic with respect to the order pair (≥, >) if for any round k ∈ K and any pair (x, y)

∈ B k , x o k ≥ y o k iff x ≽ y and x o k > y o k iff x ≻ y, with ≻ the strict part of ≽.
c-monotonicity generalizes the standard concept of monotonicity to account for monotonicity with respect to all coordinate systems. Consider panel (b) of Figure 2. When the respondent answers q 3 in round 3, she could have chosen q 2 by spending strictly less than she did in round 2. We therefore cannot conclude that the respondent regards the two choices as exactly equivalent. These two observations provide a refutation of the hypothesis that the respondent is rational and her preferences c-monotonic. As usual in the revealed preference literature, a preference relation can be characterized through a utility function. A utility function u : X → R weakly rationalizes the data if for all k and y ∈ X,

p k .q k o k ≥ p k .y o k implies that u(q k ) ≥ u(y).
One key aspect of the PSM is that ≥ does not constitute an exogenous pre-order of the set of possible survey answers. Indeed, respondents have ideal points when answering surveys [START_REF] Coombs | A Theory of Data[END_REF]; Jebb, Ng and Tay (2021); [START_REF] Thurstone | Attitudes Can Be Measured[END_REF], so the axiomatization of choice used in the consumer choice environment cannot be applied. My working assumption is that given that the ideal point q1 never belongs to the choice sets after round 1, in each coordinate system that originates with a corner answer, respondents should saturate their budget constraint and behave rationally. 1

Definition 2 The subjective pre-order of set X(s) denoted ⊵ s is such that in round k,

⊵ s =    ≥ if ∀q ∈ B(p k , R), q s ≤ q 1 s ≤ if ∀q ∈ B(p k , R), q s ≥ q 1 s
Any round k falls in one of the two cases highlighted in Definition 2, by design of the choice sets. Definition 2 says that the natural pre-order of X(s) increases with q s ∈ X(s) when increasing q s is costly, and decreases with q s when decreasing q s is costly. Concretely, take an integer scale {0, . . . , 10} for question s. In any round, the default for question s is either 0 or 10. If the default is 0 in round k, increasing the answer is costly. The respondent would perceive that 0 is lower than 1, which is lower than 2, . . . , lower than n, lower the highest answer she can possibly give to question s, and which is lower than q 1 s by construction. Reciprocally, if the default is 10 in round k, decreasing the answer from 10 is costly. The respondent would perceive that 10 is ranked below 9, ranked below 8, and so forth, until the lowest possible answer she can give to question s, which is ranked lower than q 1 s . The following corollary is direct from Definition 2.

Corollary 1 In the coordinate system with origin o

k ∈ C(X), in round k, the subjective pre-order of set X(s) is ⊵ s =≥.
This corollary says that in the coordinate system that takes as origin the default answer of round k, Definition 2 in fact means that ≥ is the natural pre-order of the set of alternatives B(p k , R). As a result of this Corollary -which is direct from Definition 2 -it is possible to apply the rationality axioms used in the standard consumption choice environment and follow the exact same formalization to recover preferences. Here are the rationality axioms in the different coordinate systems: Definition 3 For subject i ∈ I, an observed bundle q k ∈ X is 1. directly revealed preferred to a bundle q, denoted q

k R 0 q, if p k q k o k ≥ p i,k q o k or q o k = q k o k .
2. directly revealed strictly preferred to a bundle q, denoted q

k P 0 q, if p k q k o k > p i,k q o k or q o k = q k o k .
3. revealed preferred to a bundle q, denoted q k Rq, if there exists a sequence of observed bundles (q j , . . . , q m ) such that q k R 0 q j , . . . q m R 0 q.

4. revealed preferred to a bundle q, denoted q k P q, if there exists a sequence of observed bundles (q j , . . . , q m ) such that q k R 0 q j , . . . q m R 0 q. and at least one of them is strict.

Note that if the default was o in any round, Definition 6 would reduce to the standard rationality axioms assumed in the consumer choice environment. The following definition generalizes the standard cyclical consistency condition established by [START_REF] Varian | The Nonparametric Approach to Demand Analysis[END_REF], so that it holds in all coordinate systems:

Definition 4 A dataset D = {q k , B k } k∈K
satisfies the general axiom of revealed preference (GARP) if for every pair of observed bundles, q k Rq implies not qP 0 q k . Again, in the coordinate system where o k = o, Definition 4 reduces to the standard definition of GARP from [START_REF] Varian | The Nonparametric Approach to Demand Analysis[END_REF]. Figure 2 illustrates the (direct) revealed preference relations inherent to the PSM. Panel (a) represents the two last rounds of Figure 1. Here, when the respondent chooses q 3 , q 2 is also in her budget set, as p 3 .q 2 o(2) < p 3 q 3 o(3) . q 3 is directly revealed preferred to q 2 . In panel (b), in round 2, the respondent chooses q 2 although q 3 is available, thereby revealing that she prefers q 2 to q 3 . In round 3, she chooses q 3 although q 2 is available, thereby revealing that she prefers q 3 to q 2 . Since q 3 ̸ = q 2 , these two answers violate GARP (and WARP as well).

One important feature of this design of the PSM is that irrationality can be assessed using standard indices of the revealed preference literature such as the Critical Cost Efficiency Index [START_REF] Afriat | Efficiency Estimation of Production Function[END_REF]), Varian's index [START_REF] Varian | Goodness-of-fit in optimizing models[END_REF]), or the Money Pump Index [START_REF] Echenique | The Money Pump as a Measure of Revealed Preference Violations[END_REF]). As I will show next, utility functions rationalizing the data might be singled-peaked. I define a single-peaked function below:

Definition 5 A function f : X → R is said single-peaked if
• There exists a point y * ∈ X such that f (y) ≤ f (y * ) for any y ∈ X.

• For any x, y ∈ X such that x c ≤ y c ≤ y * c for c ∈ C(X), f (x c ) ≤ f (y c ).
The second condition means that if it is possible to rank x, y, y * as x c ≤ y c ≤ y * c in a given coordinate system c, then f (x) ≤ f (y) as x is further away than y in the coordinate system c. The following theorem extends Afriat's theorem [START_REF] Afriat | The Construction of Utility Functions from Expenditure Data[END_REF]:

Theorem 1 The following conditions are equivalent:

1. D has a c-mononotonic weak rationalization.

The data satisfy GARP.

3. There are strictly positive real numbers U k and λ k , for each k such that

U k ≤ U l + λ l p l (q k o(l) -q l o(l) ) (2)
for each pair of observations (q k , B k ), (q l , B l ) in D.

4. D has a single-peaked, continuous, concave utility function that rationalizes the data.

If all observations start from the origin o, Theorem 1 reduces to the standard version of Afriat's theorem. What is remarkable here is that accounting for different origins, Afriat's theorem can be generalized and D admits a rationalizing utility function that is singlepeaked.

Before detailing the proof, it is useful to observe that given a solution to the system of inequalities 3 in Theorem 1, one can write down a rationalizing utility function as follows:

u(x) = min{U k + λ k p k .(x o k -q k o k ) : k = 1, . . . , K}. (3)
This utility function is illustrated in Figure 3. On the left, in Figure 3, is a dataset satisfying GARP (WARP in that case). On the right are indifference curves corresponding to the utility function defined, as above, from solutions to the Afriat inequalities for that dataset. These indifference curves clearly represent single-peaked preferences. As the indifference curve becomes closer to the peak, the corresponding utility level becomes higher.

q 2 q 3 q 4 q 5 q 1
Question 1 Question 2 0 5 5

q 2 q 3 q 4 q 5 q 1
Question 1

Question The utility that I have depicted is not smooth. Introducing smoothness is not crucial, as for the standard consumption choice environment, but might be important in the applications, as smooth utility functions might be estimated, using predicted answers. I give several elements of proof of Theorem 1 at the end of the proposal. In particular, I show that 2 implies 1 and that D admits a single-peaked, continuous, concave utility function that rationalizes the data. The rest of the proof is provided in the Appendix, and remains close to the proof of Afriat's Theorem.

Proof. Below, I demonstrate that 3 ⇒ 4. The rest of the proof of the theorem can be found in the Appendix.

Define a utility function as (3). It can be demonstrated that u is a weak rationalization. First, u(q k ) = U k for all round k as (5) implies that

U k = U k + λ k p k (q k o(k) -q k o(k) ) ≤ U l + λ l p l (q k o(l) -q l o(l)
). Second, for any round k, let y be such that p k .q k o k ≥ p k .y o k . We have that u(q k ) ≥ u(y), because

u(q k ) = U k ≥ U k + λ k p k .(y o k -q k o k ) ≥ u(y).
The preference represented by u is a weak rationalization of the data.

Proof that the utility function ( 3) is single-peaked. The function given in (3) is the minimum of continuous, concave functions, and hence is itself continuous, and concave. To prove that it is single-peaked, first, I prove that u(q 1 ) ≥ u(q l ) for any round l ∈ K. Indeed, since u(q

1 ) = min{U k + λ k p k .(q 1 o k -q k o k ) : k = 1, . . . , K}, there exists a round k such that u(q 1 ) = U k + λ k p k .(q 1 o k -q k o k ). As p k q 1 o k > p k q l o k for any round l, u(q 1 ) ≥ U k + λ k p k .(q l o k -q k o k ) ≥ U l = u(q l ),
where the second inequality follows from (5). I am now going to prove the second element of Definition 5. Take x, y ∈ X such that there exists c ∈ C(X) and either x c ≤ y c ≤ q 1 c , or y c ≤ x c ≤ q 1 c . Assume without loss of generality that y c ≤ x c ≤ q 1 c . I will demonstrate that u(x) ≥ u(y). u(x) = U k + λ k p k .(x o k -q k o k ) for some k. Two cases need to be distinguished. Case 1: o k = c. Hence,

u(y) = U z + λ z p z .(y o z -q z o z ) ≤ U k + λ k p k .(y o k -q k o k ) ≤ u(x) as p k y o k = p k y c ≤ p k x c = p k x o k . In the second case, o k ̸ = c. Hence, u(x) = U k + λ k p k .(x o k -q k o k ) u(x) ≥ U z + λ z p z (x c -q z o z ) as p k x o k ≥ p k x c when c ̸ = o k . 2 The last inequality implies u(x) ≥ U z + λ z p z .(y c -q z o z ) = u(y), (4)
as p z x c ≥ p z y c . This concludes the proof that the utility function ( 3) is singled-peaked.

■ 4 Application

Data Description

I conducted a Priced Survey Methodology with 100 online participants recruited through Amazon Mechanical Turk. All participants had to answer a PSM consisting of the two following survey questions measuring altruism and self-interest:

On a scale from 0 to +10, where 0 indicates that you strongly disagree and +10 that you strongly agree, to what extent do you agree with these statements:

1. Individuals should primarily look after their own well-being before concerning themselves with the well-being of others.

2. Helping others, even when there's no direct benefit to oneself, is a fundamental value that people should live by.

Participants filled out this survey for 9 consecutive rounds. They were paid $1 for completing the nine rounds and a short sociodemographic survey of seven questions. Table 1 provides summary statistics of individual characteristics.

Budget sets. In the first round, subjects can choose any answer to both questions on the {0, . . . , 10} scale. In the 8 following rounds, subjects are randomly presented with 8 different choice sets. The choice set of respondent i in round k ≥ 1, B k i , depends on i's initial answer:

B k i = {q o k ∈ X such that q o k .p k ≤ q 0 i,o k .p k -2},
with q 0 i denoting i's answer to round 0. That way, in any round k ≥ 1, q 0 i is not attainable but close, as it would have been with 2 more tokens. The price vectors are chosen so that budget sets intersect many times. As seen next, these aspects of the design imply that it is possible for respondents to violate rationality. This is important, as if subjects behave rationality, it is not an artifact of the design, but a feature of their decisions. Finally, the rounds are designed such that two out of eight rounds start from each of the four corners. The low, medium, and high education levels correspond to primary, secondary, and university education, respectively. House annual income are in $.

Table 1: Sociodemographic Variables. Figure 4 gives two designs. In the left panel, the respondent initially provides a neutral answer to round 0. Her budget sets in the following eight rounds are computed such that (5, 5) is never attainable but close, and two out of eight rounds start from each of the four corners. The black, blue, green, and red budget lines correspond to the rounds where the default answer is (0, 0), (0, 10), (10, 10), and (10, 0) respectively. In the right panel, the respondent initially provides a more asymmetrical answer, agreeing with question 1 and disagreeing with question 2.

Checking rationality

I begin by looking at respondents' rationality when they fill out the PSM. For that, I introduce a slightly extended version of the Critical Cost Efficiency Index (CCEI) introduced by [START_REF] Afriat | Efficiency Estimation of Production Function[END_REF].

Definition 6 For subject i ∈ I, and e ∈ [0, 1], an observed bundle q k ∈ X is 1. e-directly revealed preferred to a bundle q, denoted q

k R 0 e q, if ep k q k o k ≥ p i,k q o k or q o k = q k o k .
2. e-directly revealed strictly preferred to a bundle q, denoted q

k P 0 e q, if ep k q k o k > p i,k q o k or q o k = q k o k .
3. e-revealed preferred to a bundle q, denoted q k R e q, if there exists a sequence of observed bundles (q j , . . . , q m ) such that q k R 0 e q j , . . . q m R 0 e q.

4. e-revealed preferred to a bundle q, denoted q k P e q, if there exists a sequence of observed bundles (q j , . . . , q m ) such that q k R 0 e q j , . . . q m R 0 e q. and at least one of them is strict. and Definition 7 Let e ∈ [0, 1]. A dataset D = {q k , B k } k∈K satisfies the general axiom of revealed preference (GARP e ) if for every pair of observed bundles, q k R e q implies not qP 0 e q k .

Afriat's inconsistency index is

e * = max{e ∈ [0, 1] : {q k , B k } k∈K satisfies GARP e }. (5)
Afriat's inconsistency index is the most prevalent in the literature, and measures the extent of utility-maximizing behavior in the data. The main idea behind this index is that if expenditures at each observation are sufficiently "deflated", then violations of GARP will disappear. The closer is the index to 1, the smaller it is necessary to shrink any budget to avoid GARP violation. The violations of revealed preferences are summarized in Table 2. The average value of the CCEI index is 92%. As a comparison, [START_REF] Choi | Who Is (More) Rational?[END_REF] finds an average CCEI of 88% in a standard consumption choice environment. [START_REF] Varian | Goodness-of-fit in optimizing models[END_REF] suggests a significance threshold of 95% for the CCEI index. Hence, even in uncontrolled and online experimental settings, subjects appear to behave rationally in the PSM. The average number of GARP violations in the sample is 2.3, with about 60% of the respondents with 0 GARP violations.

The relatively high rationality of the respondents raises the question of how easy it is to violate rationality in this PSM design. [START_REF] Bronars | The Power of Nonparametric Tests of Preference Maximization[END_REF] designed a test that answers this question. The test measures the probability that a respondent with a random behavior would violate GARP in the consumption choice environment. Bronars' test is widely applied in the literature on consumer choice and revealed preferences (Cox (1997), Mattei (2000), [START_REF] Andreoni | Giving According to GARP: An Experimental Test of the Consistency of Preferences for Altruism[END_REF]). For example, Cox (1997) reports a Bronars power of 0.49 in a study of three consumption goods and seven budget rounds. With 11 budgets and two goods, [START_REF] Andreoni | Giving According to GARP: An Experimental Test of the Consistency of Preferences for Altruism[END_REF] report a Bronars power of 78%. Since each individual faces different choice sets in the PSM, it is possible to perform Bronars's test for each respondent. Column 3 of Table 2 reports the summary statistics of Bronars power test in the PSM. On average, the Bronars power is 54%, meaning that if answers to the PSM were made randomly, out of 1000 simulated choices, 54% would violate rationality. Hence, the Bronars' power of this PSM design is relatively low. Hence, they inherently intersect less than when they all originate from the same corner, as in the consumption choice environment. Future research might look at different designs that achieve higher Bronars scores. Increasing the Bronars's scores might however require more complicated designs where inattentive respondents might violate rationality more often. Indeed, as reported in column 4, one interesting aspect of this design is that the average response time is less than five minutes, so respondents might not be too inattentive.

Estimating Preferences

Given that subjects' answers are close to rational, it is worth recovering preferences behind survey answers. For subjects that do not consistently give corner answers, I will estimate the following single-peaked functional form:

u i (q) = - S s=1 1 2 a i s q s -b i s 2 . ( 6
)
Vector b i s∈S measures respondent i's ideal answer. It offers a robust alternative to the "ideal point" measured directly through the (cardinal) answer that respondents give to traditional surveys. The key difference with traditional surveys is that the ideal point b i is measured using all rounds of the PSM. Moreover, as b i 's estimation is based on the revealed preference information of the PSM, it is robust to the issues inherent to cardinal interpretations of survey answers [START_REF] Bond | The Sad Truth about Happiness Scales[END_REF]). Vector a i measures the relative importance of different social preferences for respondent i, as measured through survey questions. Concretely, a respondent might answer that she is very altruistic but gives a low weight to altruism, as compared to selfishness. The responses of such respondents might typically be hard to interpret in standard surveys. [complete] With this specification, indifference curves are smooth and have an elliptic shape. Although more general specifications can be found, this one has the advantage of giving simple functional forms for the optimal answer to question s in round k.

q 1,o k = αb 1 + (1 -α) R -p 2 b 2 p 1 , (7)
with α =

a 1 /p 2 1 a 1 /p 2 1 +a 2 /p 2 2 , and q 2,o k = (R -p 1 q 1,o k )/p 2 .
It is as if a respondent was weighting providing an answer to question 1 close to b 1 versus providing an answer to question 2 close to b 2 . If α is high, the respondent prefers to give an answer close to b 1 in observation k and diverges from b 2 when she answers question 2. Note that since R > b 1 p 1 + b 2 p 2 by design, q s,o k < b s for any s ∈ {1, 2}. Here, a respondent will never entirely "sacrifice" one question. She would rather try to answer to both questions as close as she can to her ideal answer (b 1 , b 2 ). This property is akin to the taste for variety property of the CES specification commonly used in consumer theory. In fact, equation ( 6) can be seen as a special case of a single-peaked CES specification.

Table 3 reports the summary statistics of the utility parameters, estimated using the non-linear least square method. It seems that respondents 50 and older seem to give higher weight to answering both the altruistic question and the self-interest question, as both a 1 and a 2 are significantly higher. As there are only five of these respondents, however, this correlation might be spurious. Moreover, it seems that higher education is associated with less agreement with both the selfish and the altruistic statements. Interestingly, interpreting the results of columns 5 and 6, a social scientist could have argued that more education is associated with less selfish attitudes. Interpreting columns 3 and 4, higher education seems to be associated with both less selfish attitudes, and less altruistic attitudes.

Finally, since b i s is the utility parameter that corresponds to a respondent i's ideal answer to question s, it is interesting to compare its value with respondent i's answers to the survey 7 participants were excluded, as their decisions in the PSM were significantly less rational than the decisions of the other respondents. a i and b i are the parameters of the utility model ( 6) estimated using PSM data and a NLLS method. q 0 s is the answer of subject i to statement s in round 0, where i faces no constraint on her choice set. * (p < 0.05), * * (p < 0.01), * * * (p < 0.001). when her choice set is not constrained. Figure 5 represents the correlations between b s,i and q 0 s,i , respondent i's answer to the survey when her choice set is not constrained. As can be seen from Figure 5, there is no correlation between b s,i and q 0 s,i . This intriguing result might be due to the uncontrolled experimental conditions. However, taken at face value, this result would suggest that the answers provided to traditional surveys might in fact be poor predictors of the ideal points that subjects have on scales, as estimated through the PSM.

a 1 a 2 b 1 b 2 q 0 1 q 0 2 Constant 2.

Discussion

In this paper, I introduced a novel methodology to measure social preferences -the priced survey methodology. It consists of giving subjects various opportunities to fill out the same survey under different choice sets.

The first key contribution of this paper is theoretical. I extend Afriat's theorem, and show that the Generalized Axiom of Revealed Preferences (GARP) is necessary and sufficient for the existence of a concave, continuous, and single-peaked utility function rationalizing survey answers. There are several important implications. First, rather than interpreting the cardinal answers subjects provide to a traditional survey, the PSM enables to estimate -and interpret utility parameters, which are related to the ordinal relations between all possible answers to the survey. This is more than a simple interpretation difference. It is a key improvement, as taking numerical values at face value can be misleading [START_REF] Bond | The Sad Truth about Happiness Scales[END_REF]. In contrast, utility parameters offer a ground for comparing social preferences. Moreover, by estimating the peak of the utility function behind survey answers, experimenters have access to a new measure of a respondent's ideal answer to a survey. This measure is estimated using ordinal relations between survey answers, thereby not subject to issues inherent to cardinal interpretations of scales. Finally, with the PSM, it is possible to measure valuable aspects of social preferences that cannot be captured with traditional surveys such as how people navigate moral dilemmas.

The second key contribution of this paper is to apply the PSM to a sample of 100 online respondents. All participants had to answer a PSM consisting of nine rounds and two questions measuring altruistic and self-interested preferences. I measure the decisionmaking quality by evaluating the consistency of individual choices with the Generalized Axiom of Revealed Preference (GARP), using the CCEI Index (Critical Cost Efficiency Index). I find that respondents reach an average CCEI score of 92%. Moreover, I used the individual-level data to estimate a smooth, concave, and single-peaked utility function. Although the low number of participants make it difficult to interpret the results, it seems that respondents ideal point, as estimated through the PSM, does not correspond to the answers respondents provide to the traditional survey.

Other potentially useful applications are not discussed in this paper. First, the dynamics of revealed preferences over social preferences could be assessed, following works in demand analysis by [START_REF] Crawford | Habits Revealed[END_REF], or [START_REF] Demuynck | I'll Never Forget My First Cigarette: A Revealed Preference Analysis of The "Habits As Durables" Model[END_REF]. The intergenerational transmission of social preferences could also be assessed, by implementing priced surveys in the appropriate samples. There are several important studies on revealed preferences for multi-person demand behavior (e.g., [START_REF] Chiappori | Rational Household Labor Supply[END_REF], [START_REF] Brown | Testable Restrictions on the Equilibrium Manifold[END_REF], [START_REF] Cherchye | The Collective Model of Household Consumption: A Nonparametric Characterization[END_REF][START_REF] Crawford | Habits Revealed[END_REF], 2011)). Accounting for multi-person demand for social preferences could be a starting point to an empirical analysis of social interactions and social preferences in a general equilibrium framework.

A Proof of Theorem 1

The proof that 4 ⇒ 1 is direct, and 3 ⇒ 4 has been proven in the main text. It remains to be proven that 2 ⇒ 3, and 1 ⇔ 2.

Proof that 2 ⇒ 3. The following is a constructive proof that follows the standard proof of Afriat's Theorem, as detailed by (Chambers and Echenique, 2016, p.45).

Consider the revealed preference pair (≽ R , ≻ R ) restricted to X 0 . GARP implies that there is a preference relation ≽ on X 0 such that x ≽ y when x ≽ R y, and x ≻ y when x ≻ R y. Partition X 0 according to the equivalence classes of ≽. That is, let I 1 , . . . , Y J be a partition of X 0 such that x ∼ y for x, y ∈ I j and x ≻ y if x ∈ I j , y ∈ I h and j > h.

Define (U k , λ k ) k∈K recursively. Let U k = λ k = 1 if x k ∈ I J . Suppose that we have defined (U k , λ k ) for all x k ∈ J h=j+1 I h . We can choose V j such that, for all x l ∈ I j and x k ∈ J h=j+1 I h ,

V j < U k and V j < U k + λ k p k .(x l o k -x k o k ). (A.1)
Set U l = V j for all l with x l ∈ I j . Given this choice of U l , if x k ∈ J h=j+1 I h , then U l < U k . Moreover, since p l .(x k o l -x l o l ) > 0, it is possible to characterize λ l as:

λ l = max k U k -U l p l .(x k o l -x l o l ) ≥ 0 (A.2)
where the max is taken over the values of k such that x k ∈ J h=j+1 I h . The chosen (U k , λ k ) k∈K satisfy the system of inequalities (5). Indeed, let k and l be such that x k ∈ I j , and x l ∈ I h with j > h. Then (A.1) ensures that

U l ≤ U k + λ k p k .(x l o k -x k o k ).
and equation (A.2) ensures that

U k ≤ U l + λ k p l .(x k o l -x l o l ).
If k and l are such that x k , x l ∈ I j , then U k = U l , so U k ≤ U l + λ k p l .(x k o l -x l o l ) because p l .(x k o l -x l o l ) ≥ 0, and

U l ≤ U k + λ k p k .(x l o k -x k o k ) because p k .(x l o k -x k o k ) ≥ 0 Proof that 1 ⇔ 2.
The proof below closely follows the steps of the proof of Theorem 3.1 in (Chambers and Echenique, 2016, p. 37).

Theorem 2 In any observation k, (≥, >) is an acyclic order pair, and for any (x, y) ∈ B k , it satisfies x o k > y o k ≥ z ⇒ x o k > z o k . There exists a preference relation which is cmonotonic with respect to the order pair (≥, >) and which weakly rationalizes the data iff (≽ R , ≻ R ) satisfies GARP.

Assume that ≽ is c-monotonic and weakly rationalizes the data D. Assume moreover that (≽ R , ≻ R ) does not satisfy GARP. Hence, there exists a sequence of observations in D x 1 , . . . , x L such that

x 1 ≽ R • • • ≽ R x L and x L ≻ R x 1
As x L ≻ R x 1 and B L is comprehensive in the coordinate system with origin o L , there exists z ∈ B L such that x L ≽ R z and z o L > x 1 o L . Since ≽ weakly rationalizes D, x 1 ≽ • • • ≽ x L ≽ z. By c-monotonicity, since z o L > x 1 o L , z ≻ x 1 , a contradiction that ≽ is a preference relation.

Conversely, assume that (≽ R , ≻ R ) is an acyclic order pair. Let's show that (≽ R ∪ ≥, >) is also an acyclic order pair. To do that, we make first three key observations. For any observation k, and pair (x, y) ∈ B k 1. x ≽ R y and y o k ≥ z o k ⇒ x ≽ R z.

x ≽ R y and y

o k > z o k ⇒ x ≻ R z. 3. x ≻ R y and y o k ≥ z o k ⇒ x ≻ R y.
Assume that (≽ R ∪ ≥, >) is not acyclic and let Q =≽ R ∪ ≥. There exists a sequence of observations in D such that x 1 Q . . . Qx L and x L o L > x 1 o 1 . Without loss of generality, the cycle can be rewritten as

x 1 o 1 ≥ x 2 o 1 , x 2 o 2 ≥ x 3 o 2 , x 3 o 3 ≥ x 4 o 3 , . . . x p-1 o p-1 ≥ x p o p-1 , x p ≽ R • • • ≽ R x L , and x L o L > x 1 o L .
If p ̸ = L, x L-1 ≽ R x L and x L o L > x 1 o L implies, from observation 2, that x L-1 ≻ R x 1 . Repeating the same reasoning using the inequality x 1 o 1 ≥ x 2 o 1 , we obtain x L-1 ≻ R x 2 .

Repeating again in an iterative way, we obtain x L-1 ≻ R x p . Hence,

x p ≽ R • • • ≽ R x L-1 ≻ R
x p , contradicting that (≽ R , ≻ R ) is acyclic. This implies that (≽ R ∪ ≥, >) is an acyclic order pair. As (≽ R ∪ ≥, >) is an acyclic order pair, there is a preference relation ≽ such that ≽ R ⊆≽, ≥⊆≽, and >⊆≻ (Theorem 1.5 in (Chambers and Echenique, 2016, p. 7)). As a consequence, ≽ is c-monotonic with respect to (≥, >) and weakly rationalizes D.

  Figure 1: (a) Round 1 (b) Round 2 (c) Round 3

Figure 2 :

 2 Figure 2: Revealed Preferences in the PSM

Figure 3 :

 3 Figure 3: Dataset satisfying GARP (left panel) Indifference curves for single-peaked utility (3) (right panel).

Figure 4 :

 4 Figure 4: Examples of budget sets

Figure 5 :

 5 Figure 5: Correlation between (a) b 1 and q 0 1 (b) b 2 and q 0 2 .

  One reason why it is hard

		CCEI GARP Bronars Time
	Mean 0.92	2.31	0.54	285
	Std	0.14	3.92	0.12	143
	p5	0.6	0.00	0.31	91
	p25	0.86	0.00	0.46	159
	p50	1.00	0.00	0.56	294
	p75	1.00	3.00	0.64	406
	p95	1.00	11.40	0.66	492
	Column 1 gives the summary statistics of
	Afriat's Critical Cost Efficiency Index (CCEI).
	Column 2 gives the summary statistics for the
	number of GARP violations. Column 3 gives
	the summary statistics for the Bronars' index,
	and Column 4 gives the summary statistics for
	the time to complete the experiment in sec-
	onds.

Table 2 :

 2 Summary Statistics: Rationality to achieve high indices in the PSM is that budget sets originate from different corners.

Table 3 :

 3 Utility parameters explained by Sociodemographic Variables

This is what would happen if the choice correspondence was single-peaked[START_REF] Bossert | Single-Peaked Choice[END_REF]).

This follows from the observation that x is either lower or higher than the peak. Since it is lower than the peak in the coordinate system originating in c, p k x c is lower or equal to the scalar product of p k with x q for any q ∈ C(X).

For each pair of rounds starting from a given corner, there are two symmetric price vectors: p k = (1, 2), and p l = (2, 1) for k, l ∈ {1, . . . , 8}.

Mistakes are my own. I acknowledge funding from the french government under the "France 2030" investment plan managed by the French National Research Agency (reference :ANR-17-EURE-0020) and from Excellence Initiative of Aix-Marseille University -A*MIDEX.


Rawan Ghnemat
email: rawan.ghnemat@litislab.eu

Gérard H E Duchamp

Cyrille Bertelle
email: cyrille.bertelle@litislab.eu

ON THE USE OF GENERALIZED DERANGEMENTS FOR SCHELLING'S MODEL OF SEGREGATION

Keywords: self-organization, urban modelling, generalized derangement, Schelling's model

This paper proposes a definition of Schelling's model of segregation using generalized derangements. Many of urban or territorial modellings are based on decentralized approaches where rule-based systems have to be integrated inside a whole interaction system to describe complex phenomena. The goal of these decentralized modellings is to deal with emergent computing able to detect dynamically emergent organizations in an unsupervized way, thanks to complex systems theory. The convergence of these modern computings is generally hard to study because of the use of asynchronised processes dealing with a number of autonomous entities which are acting and interacting, in non linear way, during the whole simulation. Our approach is to define a non sequential-dependant algorithm, thanks to generalized derangements, and so to use this efficient tool to study some properties on the evolutive process.

INTRODUCTION

Urban or territorial systems are nowadays the topics of decentralized simulations which find roots on two majors advances in the development of scientific researches (Pumain 2006). The first one concerns the development of powerful distributed computer networks which allow to simulate in accurate way, detailed phenomena. The second one which finds major support from the first, is the development of decentralized approaches of modelling. This modern vision of modelling has been mainly enlighted by the complex systems theory [START_REF] Lemoigne | La modélisation des systèmes complexes[END_REF] which allows to deal with the dynamic detection of emergent organizations using swarm optimization processes [START_REF] Ghnemat | Community Swarm Optimization[END_REF], for example. Practical applications deal today with the development of Geographical Information Systems (GIS) which give accurate spatial data and allow with specific platforms [START_REF] Strout | What is Agent Analyst[END_REF] to link these spatial data with agent-based simulation and emergent computing. We can observe that humans are more or less sorted into groups of similar people, according sometimes with racial and ethnic features but also in many others ways according to various characteristics. Thomas Schelling proposed in the 1970's a very simple rule-based model able to describe segregation phenomena [START_REF] Schelling | Dynamic Models of Segregation[END_REF]. His description concerns two-dimensional lattice support and it generates from random population, a spatial self-organization which is observed as patterns of clusters of similar persons. The cluster formation does not follow linear dependance from any parameter dealing with the evolution of the rule-based systems. More generally, Schelling model can be used as generic spatial self-organization concept for various kinds of systems: A. Singh and M. Haahr, for example, use a variant of this model to study the topology adaptation in P2P networks [START_REF] Singh | Creating an adaptive network of hubs using Schelling's model[END_REF].

AN EXACT DEFINITION OF SCHELLING'S MODEL USING GENERALIZED DERANGE-MENT

The original Schelling's model can be extended in concurrent version in order to obtain an exact definition of the implementation for each time step, not depending of way the grid is scanned.

Even if the qualitative behavior of Schelling's model is independant of the order of execution od the agents, as long as each agents has the same expected probability to move, the quantitative outcome can be different. Our purpose is to give a non sequential dependant algorithm which mainly allows us to exhibit exact computationn scheme for the whole iterative process.

In the following, we will make use of the (somewhat extended) notion of derangement. For the classical notion see [START_REF] Stanley | Enumerative combinatorics[END_REF] http://en.wikipedia.org/wiki/Derangement Here it will be called generalized derangement. Definition 0.1 Let X, Y be two sets X ⊂ Y . A generalized derangement from X to Y is an into (i. e. injective) mapping 1 α : X → Y such that

(∀x ∈ X)(α(x) = x) (1)
To describe Thomas Schelling's concurrent model, we start with a two-dimensional lattice board which is a rectangle of n × m (n lines and m columns) points (each point will be located by its coordinates (x, y)

with 1 ≤ x ≤ m ; 1 ≤ y ≤ n).
A state of the board will be simply a mapping s : [1..m] × [1.

.n] → {0, A, B} 2 indicating whether a point at (x, y) has a value corresponding to

   • nothing s(x, y) = 0 • an element of type A, s(x, y) = A • an element of type B, s(x, y) = B (2)
the dynamics of the system will be described by a sequence of states s 0 , s 1 , • • • , s n , • • • generated by the following rules.

1. one fixes a threshold (in percent) 0 ≤ t ≤ 1;

2. the original state is s 0 (i.e. a distribution of A, B and empty cells along the board);

3. at each step, for each (filled) cell of type X at (x, y), one counts the ratio ρ(x, y) of neighbours of type X over the number of neighbours;

4. if ρ ≥ t the cell is marked r (remain), if not it is marked m (move);

5. let M be the set of cells marked "move" and E the set of empty cells;

6. choose randomly (uniform distribution) α among the generalized derangements M → M ∪ E; 7. then s n+1 (x, y) = s n (x, y) if the cell was marked r and s n+1 (x, y) = α(s n (x, y)) otherwise.

This algorithm is typically controlled by grid diffusion processus using elementary rule-based systems. The rules leading to each move is based on local computation of neighbourhood, however the moves are global, holistic self-organizational. The following section proposes more sophisticated behavior modelled by agent systems.

1 see http:en.wikipedia.orgwikiInjective function 2 We can extend the model using greater alphabet cardinal

RANDOM GENERATION FOR THE STUDY OF THE PROPERTIES OF THE DYNAMIC PROCESS

In order to make experiences for the description of emerging phenomena varying the threshold. We have to be able to draw "at random" a generalized derangement M → M ∪ E (step 6). This can be done very efficiently using a step by step random generation of the images. But one must be aware that, given a fixed element of M , say m 0 the set of generalized derangements α such that α(m 0 ) ∈ E has not the same cardinality that the set of generalized derangements α such that α(m 0 ) ∈ M . More precisely, if one denotes gd(M, E) the set of generalized derangements M → M ∪ E and gd(m, e) its cardinality (m = |M | and e = |E|), one has

• gd(0, e) = 1

• gd(m, 0) = d m , the number of classical derangements, given by the formula

∞ n=0 d n z n n! = exp( ∞ n=2 z n n! ) (3)
• gd(m, e + 1) = gd(m, e) + m gd(m -1, e + 1)

Moreover, the graphs of generalized derangements are of "exponential class" [START_REF] Duchamp | One-parameter groups and combinatorial physics[END_REF][START_REF] Stanley | Enumerative combinatorics[END_REF][START_REF] Wilf | Generating Functionology[END_REF]) and therefore, the multivariate stastistics of them can be treated by the exponential formula (a formula invented by the Physicist G. E. Uhlenbeck, see [START_REF] Goulden | Combinatorial Enumeration[END_REF]). One can then harness elegantly the random generation by computing explicitely the branching quantities. The combinatorial study of these probabilities does not meet the purpose of this contribution and will be the subject of a forthcoming paper.

CONCLUSION AND PERSPECTIVES

This paper presents a definition of Schelling's model using generalized derangements. Thanks to the non sequential dependant algorithm formalism proposed here, we gives an efficient tool to study the properties of the system dynamic. Combinatorial studies and implementation of this segregation model description are in progress. Convergence properties could be then studied and are expected to be obtained.

  ): http://mathworld.wolfram.com/Derangement.html hal-00431234, version 1 -11 Nov 2009 Author manuscript, published in "ESM'2007, St Julian : Malta (2007)"


Kifaya Qaddoum

Fadi Thabtah

Cyrille Bertelle
email: cyrille.bertelle@litislab.eu

ON THE USE OF ANT COLONY IN ASSOCIATIVE CLASSIFICATION

Keywords: Ant Colony, associative classification, data mining, classification rules

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

INTRODUCTION

Building effective classification systems is one of the main tasks of data mining and machine learning. Past researches have produced many techniques (e.g. Decision Tree [START_REF]Programs for machine learning[END_REF], NaiveBayes [START_REF] Pimont | A Generic Ant Algorithm for Solving Constraint Satisfaction Problems[END_REF], Support Vector Machines [START_REF] Cristianini | An Introduction to Support Vector Machines[END_REF], Neural Networks [START_REF] Lippmann | An introduction to computing with neural nets[END_REF], and Statistical approaches [26], [START_REF] Dorigo | The Ant System: Optimization by a colony of cooperating agents[END_REF]. In recent years a new classification approach that integrates classification with association rule mining called associative classification arises, which is considered a promising technique that produces highly accurate classifiers, AC in many experiments proved to give more accurate rules, and less error rate relating to the produced rules, comparing with other leading techniques in Data Mining Classification .

AN EXACT DEFINITION OF ASSOCIATIVE CLASSIFICATION

Classification rule mining and association rule mining are two important data mining techniques [START_REF] Liu | Integrating classification and association rule mining[END_REF]. The target of mining is not predetermined for association rule mining, while for classification rule mining there is one and only one predetermined target, i.e., the class.

Associative classification [START_REF] Baralis | A lazy approach to pruning classification rules[END_REF] proposed the integration of association rule mining and classification. Association rule is unsupervised learning that describes the cooccurrence among data items in a large amount of collected data [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF]. Whereas, associative classification is a supervised task that predicts the class label of test cases. This section introduces the associative classification technique. A training dataset R is characterized by a schema (A1. . . Ak, c), where (A1, . . . , Ak) are k distinct attributes and c is a class attribute. Each tuple in R is a data object, which is associated to a unique identifier called tid. The attributes may have either a categorical or a continuous domain. For categorical attributes, all values in the domain are mapped to consecutive positive integers. For continuous attributes, the value range is discretized into intervals, which are mapped into consecutive positive integers.1 In this way, all attributes are treated uniformly.

Each data object in R can be described as a collection of pairs (attribute, integer value), plus a class label (a value belonging to the domain of the class attribute c). Each pair (attribute, integer value) is called item in the remaining part of the paper.

In associative classification, classification rules are used to model the most relevant properties characterizing classes of data, and to predict the class label for unknown (unlabeled) data. A classifier is a function from 2 I to C that allows the assignment of a class label to a data object. A classifier, able to predict the class label for data objects with high accuracy, is generated from a collection of transactions (i.e., data objects with a label, also called training dataset). In associative classification, the classifier is generated by selecting the most appropriate set of association rules. A rule r :   c classifies or matches a data object d when  ⊆ d. In this case, rule r assigns class label c to data object d.

Several measures have been proposed to quantify the "interestingness" or the quality of an association (and a classification) rule. Frequently used quality indices are support and confidence [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF]. In our setting, these measures correspond to the support and confidence of the litemset © EUROSIS-ETI encoding the classification rule. For an arbitrary classification rule c, the support sup(c) is the fraction of transactions in D which contain  and are labeled by class label c. For the rule antecedent  , the support sup( ) is the fraction of transactions in D which contain  .

ANT COLONY ALGORITHM FOR CLASSIFICATION RULES DISCOVERING

Ant colony techniques have been successfully applied to many problems including the Travelling Salesman Problem [START_REF] Dorigo | The Ant System: Optimization by a colony of cooperating agents[END_REF], Quadratic Assignment Problem [START_REF] Dorigo | The Ant System: Optimization by a colony of cooperating agents[END_REF], JobShop Scheduling Problems [START_REF] Dorigo | Distributed optimization by ant colonies Proceedings of the first European Conference on Artificial Life Paris[END_REF], generic constraint satisfaction problems [START_REF] Pimont | A Generic Ant Algorithm for Solving Constraint Satisfaction Problems[END_REF], University Course Timetabling Problems [START_REF] Socha | A MAXMIN Ant System for the University Course Timetabling Problem[END_REF], cutting and packing [START_REF] Burke | Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem[END_REF] graph colouring problems [START_REF] Dorigo | Distributed optimization by ant colonies Proceedings of the first European Conference on Artificial Life Paris[END_REF] and load balancing in simulation distribution [START_REF] Bertelle | Organization detection for dynamic load balancing in individual based simulation[END_REF]. The standard technique is a constructive one: a colony of ants moves in a solutions space and evolve in collaborative way to find the best solution. Each ant contributes to this collaborative construction by making decisions stochastically, using existing problem constraints and heuristics combined with experience (which is analogous to a substance called pheromone). The colony then reinforces decisions in the construction process according to their successes by adding pheromone, which also decays to mitigate against poorer decisions. Our purpose in this paper is to investigate the ant algorithm technique as a means of constructing effective class labels associated with an attribute value in the training data set rather than just the single most obvious class.

For our purpose, we define a weighted graph G = (V,E) such that V is the set of vertices corresponding to the class labels and E is the set of edge (u,v) represent the transactions between two nodes u and v. The edge weight value corresponds to w(u,v) is sup(u), the fraction of transactions which contain u. At each step, a ant will choose to move, crossing an edge (u,v), according to a probabilistic value p(u,v):

p(u,v) = (w(u,v))  (c(u,v))  /( w∈u (w(u,w))  (c(u,w))  ) (1)
Where  u is all the state reachable from u,  and  are arbitrary parameters and c(u,v) is the pheromone rate deposite by the ant colony on the edge (u,v). When a ant crosses an edge, it deposite a pheromone value on it. After a complete iteration, the whole pheromone rate on each edge (u,v) is computed by c t+1 (u,v) =  k∈A c t+1 (u,v,k) +  c t (u,v) [START_REF] Burke | Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem[END_REF] where c t+1 (u,v,k) is the pheromone value deposite by the ant k from the set A, at the iteration t+1,  is an evaporation factor which allow to decrease the previous pheromone rate. This negative feedback allow to forget some initial and non optimal solution to make emerge new ones in dynamic way. This distributed computation contribute to find appropriate transations path for emergent association classification.