Audrey Richard-Ferroudji

Olivier Barreteau
email: olivier.barreteau@cemagref.fr

Concert'Eau: a setting to experiment difficulties of pluralisms

Keywords: experimental sociology, water management, engagement, participation

In the environmental field, water management provides examples of the move towards participative democracy. Indeed, French water policy promotes participative river basin management devices. Such devices allow confrontation of several relationship with water and raise the issue of composing these diversity within decision making process. How to compose diverse cultural viewpoints, water uses objectives and people attachment to environment? We have designed a setting of experimental sociology to allow a group of people to experience this difficulty in composing with a variety of viewpoints. It takes the form of simulation game, Concert'eau, in which players have to embody principles of justification and face events in shared virtual river basin. First experiments have shown that the same patterns due to this pluralism emerge from the gaming session as from real situations of dialogue.

Introduction

Situations of spatial planning or natural resources management have to mix a diversity of viewpoints and objectives on a territory. With the current trend of participatory policy making, developing the necessity for an increasing involvement of citizens, and "stakeholders", this diversity is more and more dealt with in interactive setting, instead of oldfashioned top-down integration. Participatory settings are then flourishing: concerned people are called upon in policy processes, with a lot of investments in time, cognition and money to organize them or to participate. This leads to several deceptive situations: feeling of manipulation, weak outcomes, etc. We assume that this is among other causes due to the fact that organizers and participants to these processes do not consider seriously enough the difficulty of coping with a diversity of people, all of them coming with their full relation to the system at stake, including their experience, their networks, their values and their feelings.

In this paper we propose a simulation game, Concert'eau, aiming at raising the awareness on this difficulty through experimenting it 1 . In a first section, we go deeper in the reason for this difficulty to cope with diversity. This is explained through the example of a river basin in the South of France, which is at the origin of this work and has been used to design the game. In a second section we present the game Concert'eau, and its specificities within the family of simulation games used for Natural Resources Management issues. The third section is then dedicated to discussion of game outcomes in relation with real situations of participatory water management.

A river basin management dialogue process: a place of multiple diversities

2.1 Towards a dialogue process in the Lentilla and Llech basins

The Lentilla and the Llech are two Mediterranean rivers in the south of France, 30 km west of the city of Perpignan. In this place, the predominance of agricultural water uses is questioned by environmental issues and the development of recreational water uses. Sharing water is at stake. The existing political modalities of management are of community type and lean on interpersonal arrangements. Based on strong social links, they have proved efficient. But today they reach some limits as they are required to integrate new people affected with certain water issues. As a consequence, some of these people ("neo-rurals" and the French water agency) ask for public debates and the development of formal devices (management plans, rules and regulations, contracts, standards…) in order to guarantee the integration of their "good" (including stakes and moral principles) [START_REF] Riaux | Mises à l'épreuve et adaptations de la gestion collective de l'eau de la Lentilla[END_REF]. This raises several practical questions when one wants to put it in practice cautiously:

-Limits of the public concerned, -Setting of the agenda, -Insuring understanding in exchanges as well as symmetry in possibility of intervention.

We focus in this paper in raising the awareness on the last question, even though the two others are far from being solved.

In the Lentilla and Llech, people who feel concerned can be described as farmers, professional of tourist sector, pensioner from Northern Europe seeking the sun, ecologists, fishermen, "pendular" urban workers, etc. Of course these categories are not completely exclusive and there is diversity within each category. However these can also be described as children of the place or newcomers; or also according to their attitude in conflict arising as seeking compromise, or asking for a vote, or champion of the public good or of a certain idea of their territory. For some of them, their family did lost land when a dam was built down the Lentilla valley, while others benefit from this facility today.

If you go there and discuss with them about the basin, you'll have as diverse answers as:

-"We need water to irrigate our orchards" -"There should be kept enough water in the river with the suitable quality for trout to live" -"Water is first an economic good which use has to be optimised" -"The river is our heritage" -"You can't know what it means to get one's house flooded" -"I've grown up here, and got my first flirt while bathing there" When all these people come into a participatory setting, unless a huge work is done to lead them to share knowledge and representations, it is likely they won't understand the same when speaking about the river or the landscape. Moreover implicit hierarchies are given according to the use of water or the duration of presence in the area. When involved in a given discussion group, these hierarchies will influence the legitimacy granted to one participant in the discussion.

"Régimes d'engagement" a model of this diversity

River basin management devices propose different spaces for collective debates such as advisory committees or river basin committees. Those spaces can be described as "Hybrid fora". "Hybrid fora" are major deliberating mechanisms to manage controversies over scientific and technological innovations (Michel Callon, Lascoumes, & Barthes, 2001). According to these authors, a hybrid forum must be a space where those taking part can explore options and learn together, a process in which the identity of participants may change or be built up over time. Popular knowledge would not be discredited and considered illegitimate but, on the contrary, respected and taken into consideration. It aims to free up and open the debate between all parties affected (including scientists, industrial corporations, institutions, associations, and the public), such that all opinions can be heard and respected. This diversity in the relationship of human beings to a common system is thoroughly analysed and described in Thévenot's framework of "regime of engagement" (L. [START_REF] Thévenot | L'action au pluriel[END_REF]. This author analyses people's shifts between different "pragmatic regimes of engagement" and moral treatments of their attachments to the material world. He pays attention to the familiar engagement with surroundings which is wrecked through processes of making things public. This framework of analysis links cognition and action. It aims "at accounting not only for the movements of an actor but also for the way his or her environment responds to him or her and the ways that he or she reacts to these responses". Three regimes are identified: "familiarity", "regular planned action" and "justification".

In regime of "justification" [START_REF] Boltanski | The sociology of critical capacity[END_REF], people confront many ways of "describing" people while relying on various forms of conventional information. Boltanski and Thévenot identify "orders of worth" which constitute "common forms of public evaluation and which are grounded on the same grammar of the common good". For example, [START_REF] Thévenot | Which road to follow ? The moral complexity of an "equipped humanity[END_REF] studies a road and tunnel project controversy and describes the plurality of "worthy roads". The road can be described as "a highway of market worth" which is opening landlocked areas to market competition. The project can also be justified because it is efficient infrastructure. The road can also be seen as a customary way of integrating locals or a route of worthy renown. But opponents can argue that it is an environmental scar. In other places, actors would justify their claim for market reasons. This regime of engagement relies on participants' moral capacities. This regime of justification leads to a fist definition of composition of plurality as defining which arguments are considered to be more legitimate.

In a pragmatic regime of "regular planned action", people enter discussions to defend their stakes. In discussion situations, participants are considered as "stake-holders" which implement intentions and consider objects as functional. People defend their interests and use arguments to do that. For example, Salles and his colleagues analyse farmers' strategies within water management devices. They study the integration of environmental norms in farming practices. They underline farmers' "strategic appropriation" of "agri-environmental" devices without real changes in practice [START_REF] Salles | Les stratégies des agriculteurs face aux dispositifs de gestion de l'eau: CERTOP-CNRS GIS ECOBAG[END_REF]. In this regime, strategic capacities of actors are central. Plurality composition comes through connecting actor vision of "community" to actors' interests [START_REF] Moody | Comparing models of stratégy, interests, and the public good in French and American environmental disputes[END_REF]. This regime of "regular planned action" leads to a second definition of composition: negotiating.

Regime of familiarity deals with emotion. It aims at accounting for actors' personal relation to a place, a custom, an object or other people. It deals with a familiar relation built along a lifetime or even longer when inscribed within a family. This kind of relation with surroundings or people needs to use another qualification of acting, other than justifying or doing something with an aim. Thevenot proposes a third "pragmatic regime" of familiarity which depends on idiosyncratic linkages with a customised environment. It has to do with "perceptual and kinaesthetic clues about familiar and customised paths through local environments which involve modifying the surroundings, as well as the habits of the human body (...). The proper language to offer accounts of what happens is far from the formal statements offering justifications. It is highly indexical and gestural" (Laurent [START_REF] Thévenot | Which road to follow ? The moral complexity of an "equipped humanity[END_REF]. How do people cope with such information in discussion situations? They have to cope with their attachments with the environment while participating and make people and things equivalent and general. Doidy studies the tension of such engagement with environment on collective decision. He underlines the difficulties encountered when trying to value this "proximity knowledge" in public arenas. Actors can not leave all their familiar equipment at the door of the device, and they will thus use it in the collective decision making process anyway [START_REF] Doidy | Faire entendre la voix des usagers dans les concertations environnementales. sociologie pratique, 7[END_REF]. It has to be taken in account in the implementation of any kind of hybrid forum. This regime leads to a third way of composing plurality: arrangement.

In situation, each individual may behave according to one of the three regimes among others, even though some are more at ease with one regime or another. These regimes give model for three levels of pluralism: attachment, objectives and common goods which must be expressed and composed in participatory processes. To make this composition possible, a device should then let diversity be defined by the participants themselves; otherwise this would happen outside of the debate situation. Making this diversity works in a participative democracy and be explicit has to be equipped. A meeting room and a self designed facilitator might not be sufficient. We designed the game explained below to encourage collective reflexivity on coping with pluralism, for people about to engage in such participatory processes or potential future pilot of these processes.

Concert'eau: a simulation game to experience pluralism

Gaming and NRM

Simulation and Gaming is already used in the field of NRM, proposing tools to support the involvement of stakeholders in the design of NRM policies [START_REF] Barreteau | Contribution of simulation and gaming to natural resource management issues: an introduction[END_REF][START_REF] Duke | Policy games for strategic management[END_REF]Mayer & Veeneman, 2002). These games use models, or metaphors, usually focussing on the representation of the system at stake. This is a way to broaden the field of information available to participants: to give them more insights into the processes at stake [START_REF] Benbasat | Information technology support for debiasing group judgments: an empirical evaluation[END_REF].

The game presented below simulates the dialogue process itself. This is justified by the fact that it is the existence of an outcome of the process which is at stake rather than the nature of this outcome. It comes behind models of clustering which do provide support in finding the suitable allies in a negotiation process [START_REF] Burkardt | Desire to bargain and negotiation success: Lessons about the need to negotiate from six hydropower disputes[END_REF] or of models, whatever the format, aiming at forecasting outcomes of negotiations [START_REF] Green | Forecasting decisions in conflict situations: a comparison of game theory, role-playing and unaided judgment[END_REF].

Concert'eau

This game is a descendant of Eco-logiques [START_REF] Germe | Le traitement local des conflits en matière d'environnement Jeu éco-Logiques Rapport Final[END_REF]. Concert'eau's first step is similar to Eco-logiques' but the objectives are different here. Eco-logiques' aimed at analysing which arguments are more greatly considered to be legitimate in collective discussion. Concert'eau aims at observing shifts between pragmatic regimes from familiar engagement to public formats and between water management logics. It is supposed to be a generic representation of a collective decision process, with contextual elements borrowed from the case studies and rough categories of argumentation which can be observed in the Llech and Lentilla basins. This is our way to represent a collective decision support device.

The game, which is extensively includes 8 players constituting 4 teams (Do, Ré, Mi and Fa). Each team is an inhabitant of the "four seasons' valley". There is a collective discussion table at the centre of the room. There are also inhabitants' "houses": a two person table for each team at the 4 corners of the room.

Grasping participants differences through various criteria of common evaluation

The four logics or good water management described above (part 2) form 4 "departure cards" given to each two player team. This card presents the logic they will have to defend when facing events and when having to elaborate compromises with others teams. In this way, we lead players into a position where they have to follow a logic of water management and to categorise issues through this very logic: green logic (Fa team), patrimony or domestic logic (Do team), market and industrial logic (Ré team) and civic and fame logic (Mi team). Departure cards which define players' roles are an incentive to shift to the justification pragmatic regime. It aims to make people grasp participants' differences through various criteria of common evaluation. Concert'eau aims to make people shift from an a priori strategic engagement in collective discussion to a justification regime.

First step: Making players acquainted with their role and with others

Players' roles are only defined as inhabitants whose viewpoints correspond to the departure cards. In the first step we give each team 34 cards including photos, interviews extracts (such as those chosen to illustrate river basin goods above) or extracts from documents generated from interviews on the case. Teams go to their "house" and choose 6 cards among the 34, corresponding to their departure card. They have 20 minutes for this. In the next step they present these chosen cards to the other teams, and discuss the cards chosen collectively. The facilitator identifies the cards chosen by two or more teams, pointing out the possibility for agreement but also trying to make the reasons explicit for this common choice.

Second step: Drawing compromises

The context is a collective and informal meeting where players discuss how to react to events concerning some aspects of water management that they are jointly facing. They are asked to agree on a compromise. Players are incited to reach a compromise through the insurance that their proposals are likely to be taken into account provided it comes from a consensus: in case of an agreement, they inform a public authority about it. The game's facilitator chooses event results, and chooses the events' progression according to previous event discussion in order to raise trials for the players and make players experiment with the difficulties of composition. For each "event", each team has to give its own opinion. It can build its opinion during a team 5 minute discussion in their "house". They then come back to the collective table and have 10 minutes to discuss and reach a compromise with other teams. The game facilitator helps teams to write down the compromise. The teams can then sign it if they still agree.

A writing of events which aim to provide various information formats

Events are short texts (around 150 words) written on a sheet. One event is for example a retired farmer who plans to sell his land to an external investor who wants to build a large tourist resort. Events are written to give elements from diverse knowledge formats. They give information linked to the 4 teams' logics through inhabitants reactions: "Mr. Dupatelin is happy because his son could find a job. Mr Dusouci worries about water provision and environmental balance…". We then tried to provide elements to induce shifts to a proximity regime. Each team receives the same event card, but one of them gets a slightly modified one: this team receives a card, which for the same event, introduces a mention of some personal ties. In one event for example, the nephew of the green team pollutes the river whereas for the 3 others teams it is an anonymous cattle farmer who pollutes. In another event the Ré team's own property is flooded, while for the others it is the property of an anonymous inhabitant that is flooded. Since the game is designed with four events, each team receives a personalised event at one stage during the game session.

A few contextual descriptions

During the game session, we describe the context of the collective discussion very roughly: we give information neither on the public authority and status of the collective meeting, nor on any social or professional status of the players. Player roles are described very roughly. Players are inhabitants with a departure card but without profession or stake to defend. They are all considered equal except for their justification principle. They are inhabitants and not just disembodied principles so that shifts to other regimes can occur: familiarity and strategic ones. But they are only defined as inhabitants in order to limit elements which could favour strategic behaviours. Even though this strategic behaviour is one of the regimes of the theoretical framework presented in first section, a strong orientation towards this behaviour was observed in first test of the game: players tried to embody themselves in a socioprofessional category to which they considered was the clearest archetype. When they had taken on their representation of this archetype, they attempted to defend its stakes.

Finally, the limitation of the information given to the players allows observation of the complementary information that they need to act and bring to the debate. Which guarantees do they need and bring in the game?

Third step: debriefing After 3 or 4 events, players are asked to come back into their "own shoes" and to quit their Do, Ré, Mi or Fa shoes. The game facilitator's job is over; the game observer shifts to be the debriefing facilitator. The debriefing discussion deals with the participants' feelings during the game and provides a return to reality. It is organised according to the following questions:

-How did you feel during the game? Did you feel at ease? -What difficulties did you meet during the game? -During the events who do you think you were? Where do you think you were? -If you played the game again, would you play the same way? -Do you think what happened in the game could happen in the reality? Later after the game, an individual debriefing is also planned with some players according to the observations in the game. This game doesn't aim at making people value change or analyse such changes like in [START_REF] Kergreis | Régulations cognitives et sociales dans les concertations agrienvironnementales : effets des contextes sociaux et des supports de discussion sur l'évolution des connaissances descriptives et évaluatives des bordures de champs agricoles[END_REF]. Neither it is to analyse strategies in negotiation situation but at making discuss which arguments are more considered to be legitimate facing events and experiencing the difficulties of composing with different values equally legitimate and other elements rising during the game. It aims at making players endure tensions in composing plurality. It is meant to be used either in academic situations with students, or with people about to engage in a dialogue process.

A setting of experimental sociology

Concert'eau is a setting of "experimental sociology": it entails participants to get experience through simulation of interaction behavioural patterns. Such experimental posture in sociology provides a pragmatic value through a double validation: according to its internal coherence and to the trial of facts generated by the setting [START_REF] Berthelot | Les règles de la méthode sociologique où l'instauration du raisonnement expérimental[END_REF]. Trial, which is a core concept of pragmatic sociology, fits this experimental posture. Experience is by itself a trial of theory to facts. Modelling of social facts which is required to design an experience is assessed with pragmatic view. With Concert'eau, these settings fall in the category of platform among the three categories proposed by (M. [START_REF] Callon | Economic Experiments and the Construction of Markets[END_REF] to describe experimental settings in social sciences. Platform is an intermediate category, open to compromise and to inputs from participants, but still enforcing distance between the simulated world and the "real" world. Simulation games, such as policy exercises fall usually in this category. They are designed to facilitate hybridizing and confrontation of stakes and values. They provide situations with new interactions to be experienced by players. This facilitates an "exploration regime" [START_REF] Auray | Une autre façon de penser le lien entre technique et politique : les technologies de l'Internet et le réagencement de l'activité autour de l'exploration[END_REF]: players can experience new behavioural patterns with low risk and high reversibility.

Discussion

Outcomes of game sessions

Game sessions have been made either with graduate students (environmental engineering, agricultural engineering, development studies, sociology) or with people already involved or prepared to be involved in dialogue processes for river basin management (two times in the Lentilla basin, once in the nearby Orb basin). These sessions came after three test sessions with colleagues from our institute. All the sessions have included a collective "hot" debriefing, while only those with people involved or about to be involved in dialogue processes have been followed by "cold" individual debriefing (ca. 2 months later). In these sessions several characteristics of the difficulties for dealing with diversity have emerged. First, convergence of discussions went rather to weak compromises such as asking for complementary studies or for external party to provide new goods in the system. Second, without succeeding in elaborating strong compromises some players asked for external arbitration such as state arbitration. In the attitudes in the game, difficulties to deal with disincarnated justification principles have been very strong. During the game players fleshed out their character by bringing in social categories. Implicit hierarchy in values led some players to invent for themselves new characteristics to increase their legitimacy in the debate. When domestic value comes to the top, a player with another principle declared having 5 children to grow on this value. Information about proximity was dealt with differently: from totally unconsidered to a low profile in the discussion if value and some personal ties were rather in conflict. In the debriefing, players recognized their difficulties in dealing with this gap.

Comparison with real settings

These outcomes fit to what is reported in the literature or to what we have observed in real situation of dialogue for water management issues in the South of France. Compromises are usually weak, which is currently disqualifying these processes claimed to be non efficient. Agreement reached through an openness of the system is the most common issue. A group finally finds a collective solution through handling resources coming from outside of their territory. Historically the downstream area of Durance basin in South of France came to an agreement on water sharing through an increase of water availability in summer thanks to a dam in the upper part of the basin… however people from this upper part were not part of the agreement. State is required to come back by people unsatisfied with participative process results. Hierarchy of values, generally implicit, is always present: legitimacy of ecology face to market principles is often disqualified, unless the population playing is rather composed of green or development militants.

Conclusion

We have developed a simulation game, Concert'eau, which aims at making people experience the difficulties in composing with their diversity from their principles to their personal ties with the system at stake. This game is built upon a model of collective setting, the model of "régimes d'engagement", the system at stake being a river basin. This leads to raising awareness of participants in these difficulties. The game as such should now be used in training sessions organized by the farming sector for farmers about to take part in dialogue processes. This should allow us to grasp information on innovations which emerge within the artefacts produced by the game sessions.

This communication is based on a part of PhD work of Audrey Richard-Ferroudji, which is in finalisation stage. The tool Concert'eau has been designed specifically for this PhD work.


Pieter Bots
email: pieter.bots@cemagref.fr

Olivier Barreteau
email: olivier.barreteau@cemagref.fr

Géraldine Abrami
email: geraldine.abrami@cemagref.fr

Simulation of solidarity in a resource sharing situation

Keywords: agent-based model, social simulation, solidarity, typology, values

In this paper we present a first attempt to represent social behavior of actors in a resource sharing context in such a way that different forms of solidarity can be detected and measured. We expect that constructing agentbased models of water-related interactions at the interface of urban and rural areas, and running social simulations to study the occurrence and consequences of solidary behavior will produce insights that may eventually contribute to water and land resource management practice. We propose a typology for solidary behavior, present the agent-based architecture that we are using, show some illustrative results, and formulate some questions that will guide our future work.

Introduction

Is it conceivable that a farmer voluntarily gives up irrigation to improve the surface water quality in the city downstream? Or agrees to let his fields be inundated to reduce flood damage in urban areas? And will upstream city dwellers of their own accord invest in a separate system of rain water retention to avoid sewer overflows? Intrigued by these and other questions concerning water-dependent individuals who live at the interfaces between urban and rural areas, we have started to explore the issue of solidarity around water sharing and maintenance of water resources during an interdisciplinary workshop in January 2007 in Montpellier1 . The participating researchers brought a variety of case studies in very different geographical and political contexts to the table, and a variety of definitions of solidarity as well.

To sort out this diversity of situations of water-related interactions in which some form of solidarity becomes apparent or is called for, we decided to develop a decontextualised simulation model of solidarity with agents seeking to uphold various values, living in either an urban area or a rural area, and sharing a resource. The purpose of these models is to allow analysis how different types of solidarity (can) play a role in the dynamics of a system that comprises an urban area and a rural area linked by a shared resource. This analysis is expected to provide useful feedback to the initial interdisciplinary group, allowing the researchers to focus on common questions regarding solidarity about water, questions that need to be answered not only to improve water resource management, but also to strengthen the social cohesion of territories.

This paper presents the first stage of this work: a sketch of an urban perspective and a rural perspective on the role and use of land and water resources, a categorization of different types of solidarity, the So-Si-So modeling platform that we are developing to represent and analyze behavioral patterns of solidarity, and an embryonic version of Solid'Eau, a simulation model that eventually should allow us to study the social behavior of agents located in a system around a shared water resource. The first results obtained with this model show that the So-Si-So model architecture indeed allows identifying and measuring different types of solidarity, and lead to several questions that will guide our future work in this area.

Solidarity at the Interface between Urban and Rural Areas

The social phenomena that we are interested in spring from the tension between two opposing perspectives on water issues: an urban perspective and a rural perspective. At a first glance, this tension leads to attempts from one group to impose constraints on, or get compensations from, the other group. Looking more closely, a variety of more specific and refined stakeholder perceptions can be distinguished within each perspective. Moreover, at the level of individuals, the boundary between an urban community and a rural community is not so clear as it is sometimes claimed: there is always a peri-urban area where individuals are difficult to categorize as urban or rural, individuals migrate at various speeds from urban areas to rural areas and vice versa, and they are linked to both types of areas in intricate ways. To emphasize interdependency and the potential for conflict, however, the two perspectives are characterized as follows:

Urban perspective:

• Cities are the centers of modern human society. Their complex social structure is essential for technological, economic and cultural development.

• Water is a necessity of life. Citizens are entitled to adequate drinking water supply and sanitation. • Rural areas are indispensable for food production, but large scale agriculture reduces the ecological and recreational value of the landscape. • Rivers are a drinking water supply as well as a discharge channel for rainwater and

wastewater, but also a potential threat that needs to be contained by adequate flood prevention measures.

• The natural water system has a high capacity for regeneration, but balances are threatened by the extraction of irrigation water and heavy use of fertilizers and pesticides in agricultural production.

Rural perspective:

• Not only historically, but also today, the modern, human society has its roots in small agricultural communities. Without agriculture no food, and without food no cities.

• Water supports natural vegetation and wildlife as well as agriculture and human life. The traditional rural life style is in harmony with nature and uses water resources in a sustainable way. • The growth in population, which is strongest in urban areas, puts greater demands on agricultural production as well as on facilities for recreation. • Urbanization creates a new hydrological environment (buildings and roads replace vegetation and soil, sewers replace stream channels), reducing infiltration and groundwater recharge while increasing runoff and the probability of flooding. • Urban areas produce high volumes of faeces and other organic waste, heavy metals, and mineral oil products. Although sewage systems and wastewater treatment plants mitigate emission to surface water, high peak discharges generate sewer overflows. Also, industrial and household consumption of electricity causes thermal pollution that threatens aquatic wildlife.

These outlines of the urban and rural perspectives clearly show a number of interdependencies and tensions that underlie many water resource management issues. However, these interdependencies and tensions may not be obvious at the stakeholder level. Any attempt to cope with undesirable impacts from one perspective is likely to generate unexpected feedbacks on other aspects of the other perspective. For example, if an urban group succeeds in imposing constraints on rural water use for agriculture, this will impact on landscapes which are valuable for residents of urban areas.

Given these more or less straightforward physical interdependencies, we want to question whether any social link between both parties exists or can be created or reinforced that could manage these physical interdependencies. Institutions in the sense of [START_REF] Ostrom | Governing the Commons: The Evolution of Institutions for Collective Action[END_REF] may exist that already provide or could establish this social link. But what we are presently even more interested in are loose forms of interaction such as solidarity.

Our work is based in the assumption that raising awareness of physical interdependencies and social links is a way towards a management of the resource better for the whole system. In this perspective, we think that models are effective tools to reveal and make explicit those situations where the heterogeneity within each group, and the existing relations at the individual level between persons associated with one group or the other is providing opportunities (1) to find institutions to manage the interdependencies, and (2) to find synergies among various perspectives. Meanwhile, we see our modeling work also as a means to achieve a better formalization of solidarity situations and of the solidarity concept itself. This paper reports our progress in this formalization to date.

The capacity to resolve the tensions as water resources become scarce is largely determined by the willingness of stakeholders to share. It is at this point that the concept of solidarity becomes interesting. Solidarity is a loose form of social binding characterized by latent reciprocity: the interdependencies need not be explicitly known or understood by those involved. Solidarity is a feeling, rather than a calculated attitude.

On the individual level, solidarity can be defined as "a sense of community between persons who, despite their differences, believe to have the same objective(s) that one has achieved more than the other, from which rises the voluntary obligation to support the other, coupled with the entitlement to support from the other should the situation be reversed" (Hondrich & Koch-Arzberger 1992, p. 14-15). [START_REF] Segall | Political Participation as an Engine of Social Solidarity: A Sceptical View[END_REF] sees solidarity as a relation between the individual and the collective: "[Social solidarity] comprises the following phenomena:

• Integration -Identification on the part of the individual with the goals and features of the collective (Miller, 1999, p. 26); • Commitment to the common good -Willingness to forgo self-interest for the sake of the common good [START_REF] Mason | Solidarity', The Routledge Encyclopaedia of Philosophy[END_REF]); • Empathy -concern for the wellbeing of other members who are less well off than oneself (Cohen and Arato, 1992, p. 472;[START_REF] Mason | Solidarity', The Routledge Encyclopaedia of Philosophy[END_REF]; • Trust -the willingness to suspend suspicion of others, at least until receipt of evidence to the contrary (Misztal, 1996, p. 209;Seligman, 1997, p. 94;Warren, 1999, p. 330)." (Segall 2005, p. 362, the references are his).

Thus, solidarity may be a relation between two individuals or a relation between an individual and the collective that the individual is part of. When considering the (potential) solidarity between urban and rural areas, both relations need to be examined.

In this paper, we focus on solidarity at the individual level, where solidarity involves a voluntary action of person A in support of another person B where A by performing this action knowingly incurs a cost to himself. The definition by Hondrich and Koch-Arzberger is quite precise with regard to the mechanism that leads to solidary action: The sense of community that leads A to support B stems from A's belief that A and B share certain values and objectives. When A furthermore believes to have achieved these objectives more than B, A experiences a voluntary obligation to support B, coupled with the implicit entitlement to support from B should the situation be reversed. This precision allows us to distinguish the following categories of solidary behavior: • The action of A is an act of altruism, rather than one of solidarity, when it is motivated solely by the belief that this action will contribute to the realization of B's objectives (absence of the shared objectives aspect). Example: A is wealthy and donates, for no particular reason other than to do good, to a charity organization that funds B to recover from flood damage. • The action of A is an act of 'heartfelt solidarity' when it is motivated by the sense of community due to A's belief that B shares some of his own objectives. Example:

Village A does not lie in a flood-prone area and its inhabitants nonetheless contribute to a flood damage compensation fund for village B because they believe that those who live in village B aim, just like they do, to preserve their characteristic houses as part of their cultural heritage. • The action of A is and act of 'opportune solidarity' when A and B have the same objective and A values this objective even more than B (dominance of selfinterest). Example: Some inhabitants of A contribute to the flood damage compensation fund for village B because they value its cultural heritage even more than the inhabitants of B. • An action of A is an act of 'calculated solidarity' when A takes this action motivated by his expectation of possible future benefits should he find himself in a situation similar to B (absence of the latent reciprocity aspect). Example: Village A and B are both situated in a flood-prone area and their inhabitants choose to contribute to the flood damage compensation fund because that will cover their own flood risk. • The action of A is an act of 'self-interested solidarity' when A's actual motivation to support B does not stem from B's objectives, but from A's own, different objectives. Example: Village A does not lie in a flood-prone area and yet some of its inhabitants contribute to the flood damage compensation fund for village B, but they do so merely to increase the fidelity of their customers living in the floodprone village B. • An action of A is an act of 'imposed solidarity' when A takes this action as a result of some contract or social rule (absence of the voluntary aspect of the action).

Example: The people in villages A an B all pay a national income-based tax, the revenues of which are used to compensate people who incur flood damage.

These definitions of solidarity provide categories for individual behavioral patterns. In the present stage of our research, we focus on these patterns to study the conditions that lead to different forms of solidarity, and the effect on a group level. In a later stage, we will also consider group solidarity, that is, the degree to which individuals in a group comply with corporate rules in the absence of compensation (Hechter, 1987, p. 39).

So-Si-So: A modelling Platform to Analyse Solidarity in Behavioural Patterns

In this section we describe the modelling platform called So-Si-So (Social Simulation of Solidarity) that we have developed to study the simulated behaviour of cognitive agents, situated in physical spaces, and interacting in social spaces.

To be able to distinguish between the different types of solidarity defined in the previous section, the observer must have access to the mental state (beliefs, motivations) of both A and B. Our agent-based models should therefore allow inspection of the motives for agents to take action. The design of So-Si-So agents should otherwise be as simple as possible. This led us to the following choices:

• Agents derive their ultimate motivation for action from values, which they seek to uphold. Some values are intrinsically individualistic (e.g., one's own survival), other values are intrinsically collective (e.g., peace). • Agents have concerns that define relations between their values and indicators that give them insights on aspects of the physical spaces and/or the social spaces that they have access to. • Agents acquire factual beliefs about these indicators through their sensors. Being actor-bound, sensors are subjective: different agents may construct different factual beliefs about the same situation. • Agents become privately concerned when, according to their factual beliefs, one or more of these aspects appear to be in bad shape. • Agents may also become socially concerned, that is, consider the concerns of other agents situated in their social space(s). Agents will become socially concerned only if they have some inclination towards altruism. • To address concerns (their own and/or those of other agents), agents evaluate their causal beliefs, looking for actions that they expect to ameliorate the aspects of their environment about which they are concerned. • For each of their 'active' concerns, agents choose the action (insofar available) that seems best to them.

This agent design permits the modeller to trace for each action taken the values that motivated the agent to perform this action, and therefore also to detect solidary actions (actions that address the concerns of others) and distinguish between different types of solidarity. To demonstrate this, we must define more precisely the way in which So-Si-So agents come to act: • An agent is represented as an 12-tuple a = (Val, Con, Sen, Bfact, m, α, Cp, Cs, Cw, Bcaus, budget, Soc) where Val is a set of values, Con a set of potential concerns, Sen a set of sensors, Bfact the set of factual beliefs, m the agent's memory depth (represented as a non-negative integer value), α the agent's inclination towards altruism (represented on the interval [0, 1]), Cp, Cs and Cw sets of, respectively, private, social, and weighted concerns, Bcaus a set causal beliefs, budget the agent's financial resources (represented as a non-negative real value), and Soc the set of social spaces that a is part of. • A value is represented as a 3-tuple (idea, type, importance), where idea expresses something that the agent holds dear, for example: 'survival', 'wealth' or 'environment'. The value type is either IND (for individualistic) or COL (for collective). When an agent has multiple values, their relative importance can be represented on the interval of (0, 1]. • A potential concern is represented as a 3-tuple (indicator, value, intensity) that expresses the subjective relation that the agent sees between some aspect of the world and what the agent holds dear. When an agent considers multiple indicators to be related to the same value (for example, both quality and quantity of the water resource relate to the value 'ecology'), the relative intensity of their relations with this value can be represented on the (0, 1] interval. • A factual belief is represented as a 3-tuple (tick, indicator, judgement) that expresses how the agent perceives some aspect of its environment at a particular tick (time step as counted by the model's clock) in the simulation. An agent's factual belief list cannot contain beliefs older than the agent's memory depth. New factual beliefs are added to the agent's factual belief list by the agent's sensors, where a sensor typically compares one or several variables in the agent's environment with pre-defined threshold values, and produces a judgement on some scale. In our experiments, we used this scale: AWFUL=-1, BAD=-0.5, NEUTRAL=0, GOOD=+0.5, GREAT=+1, but other scales can be defined, as long as they map onto the same interval of [-1, 1]. • The three lists of actual concerns (private, social, and weighted, respectively) contain 2-tuples (concern, state) that express for the current time step the degree (represented by the numeric field state) to which the agent is actually concerned about certain aspects. For example, when in time step 25 an agent has a factual belief (25, 'water quantity', BAD), and the potential concern c = ('water quantity', 'ecology', 1), its private concern will be pc = (c, -0.5). Private concerns are created from the agent's own potential concerns, social concerns are created from other agents' potential concerns. The set of weighted concerns contains the weighted average of an agent's private and social concerns. It is this set of actual concerns that the agent used for taking decisions.

• A causal belief is a 3-tuple (action, effects, cost) that expresses the relation that the agent sees between an action, its effects on one or more indicators, and the costs involved. For example, the causal belief ('SELF:produce', {('water quality', BAD), ('income', GOOD)}, 50) represents that the agent believes that its own action 'produce' affects two indicators and will require 50 of the agent's budget units. The list of causal beliefs may be incomplete (thus representing what an agent conceives as possible) and even incorrect (agents may wrongly estimate effectiveness and/or cost). Agents may also have causal beliefs about actions that can be taken by other agents. • An action represents what agents can do. The actual consequences of actions are calculated by the physical space entities and/or social space entities that the agent has access to.

Physical spaces, social spaces and their autonomous evolution (i.e., state changes that are not the immediate result of actions of agents) are defined by the modeller (see the example in section 5). Once physical spaces, social spaces and agents have been initialised, a So-Si-So model iterates through this cycle: 1. The agents get the opportunity to act. In the experiments reported in this paper, this happens in a fixed sequence: the order in which the agents were created. 2. The social spaces coordinate collective actions. Collective actions are actions that require more than one agent to be effective, so agents can only 'announce' their intention to perform such an action in a social space. When all agents have had the opportunity to act, each social space checks whether the conditions for successful collective action as specified by the modeller (e.g., at least five agents are needed for this action to be effective) are met, and only if that is the case will the consequences of the action be effectuated as changes in the state of certain physical and/or social spaces. In the experiments reported in this paper, this feature has not been used.

3. The physical spaces evolve. Although the immediate consequences of agent actions have all been effectuated, the state of the physical spaces may still change autonomously. 4. The agents evolve. Similar to physical spaces, certain attributes of agents may also change as a function of time, independently of agent actions. 5. The model advances to the next time step: Clock.tick = Clock.tick + 1 A So-Si-So agent a comes to act by in a sequence of steps: The division by n makes that the scale for the state attributes of the agent's private concerns and its social concerns is the same. Note, however, that if some other agent is part of more than one of the agent's social spaces, its concerns will be considered several times. We see this as appropriate, as it reflects that in reality those other agents with multiple relations will also have more influence on the agent. 5. Weigh up private and social concerns. Agent a's parameter α is used when the agent merges its private and social concerns into its set of weighted concerns Cw: starting with an empty set, the agent first adds for each of its private concerns pc a new weighted concern wc with wc.state = pc.state*(1-α); then for each of its social concerns sc, the agent checks to see whether it already has a weighted concern wc with wc.concern = sc.concern; if not, a new weighted concern wc is added with wc.state initialised to sc.state*α; otherwise, the state of the existing weighted concern wc is updated as follows: wc.state = wc.state + sc.state*α 6. Deliberate. For each of its weighted concerns wc (in order of increasing state, so as to deal with the worst problem first) agent a checks its causal beliefs looking for actions that are believed to alleviate this concern. More precisely: the agent selects those causal beliefs b with b.effects containing a 2-tuple e = (indicator, impact) with e.indicator = wc.concern.indicator and e.impact > 0 (i.e., GOOD or GREAT). Agent a then selects the action that is still affordable (b.cost ≤ a.budget) and has the highest utility (taking into account its consequences for its other concerns), adds it to its action list, and computes its remaining budget.

1. Forget. Agent
The utility u of an action is calculated as follows: starting with an initial value u = 0, the agent checks for each of the action's effects e = (indicator, impact) whether it has one or more weighted concerns wc with wc.indicator = e.indicator and wc.state < 0, and for each such concern u = ue.impact*wc.state. This reflects that a only considers the indicators a is concerned about (ignoring all other indicators), and will favour those with a (strong) positive effect on indicators whose state is (very) negative. 7. Act: the agent performs the actions on its action list. Note that the actual consequences of each action for the agent's own attributes (notably a.budget) as defined by the modeller may differ form the anticipated consequences, that is, the effects according to the agent's causal beliefs.

This architecture makes it possible to detect different types of solidarity because it allows scrutinizing an agent's motivation for taking certain actions.

The basic characteristic of an act of solidarity action is that agent a takes this action to support agent b, and that a makes some kind of sacrifice by doing so. In the So-Si-So architecture, agents are aware of the concerns of other agents, but on an aggregate level only. Where a's private concerns a.Cp are its own and therefore individual, a's social concerns a.Cs are a 'weighted union' of the weighted concerns of a set of other agents. Thus, the 'other agent' b in our definitions of solidarity is the aggregate of all agents in a's social spaces, rather than an individual agent.

The terms 'support' and 'sacrifice' both entail a concept of utility: an action of a supports b when it produces positive utility for b, and it constitutes a sacrifice for a if it produces negative utility for a. By the same type of reasoning, a supports b by not taking an action that would produce negative utility for b, even though it would produce positive utility for a. The foregone utility for a then constitutes a's sacrifice.

While deliberating, agent a constructs an action list, selecting (insofar as a's budget permits) for each of its weighted concerns a.Cw the action with the highest utility. To see whether a makes a sacrifice, a second action list is constructed according to the same procedure but now based on a's private concerns a.Cp. The former (from now on called the 'weighted action list' of a) represents what a does, the latter (a's 'private action list') represents what a would have done if b had not existed. Likewise, a's 'social action list' is constructed on the basis of a's social concerns a.Cs.

Using these three action lists, we can now define the following types of utility: • Being based on a's weighted concerns, the utility of an action x on a's weighted action list is called the 'weighted utility' of action x. The 'private utility' and the 'social utility' of x are defined likewise.

• Usoc cumulates the social utility of actions in a's weighted action list that are not in a's private action list PLUS for those actions x that are in both lists the 'social utility surplus' defined as the difference (if positive) of social utility of x -private utility of x. • Uneg cumulates the negative private utility of actions in a's weighted action list.

Having a negative private utility, such actions will not be in a's private action list. • Uasoc cumulates the negative social utility for actions in a's weighted action list.

When an action x has a social utility < 0 and yet occurs in the weighted action list, it must be motivated by private concerns only, hence Uasoc, which stands for 'anti-social utility'. • Uopp cumulates for actions in a's weighted action list that are also in a's private action list (but only those driven by the same concern, with the state of a's private concern being worse than the state of a's social concern) the 'private utility surplus' defined as the difference (if positive) of private utility of x -social utility of x. • Uself cumulates the private utility surplus for the remaining (i.e., not used for Uopp) actions in a's weighted action list that are also in a's private action list. • Uforegone cumulates the private utility of actions in a's private action list that are not in a's weighted action list. Motivated by social concerns, a decided not to take these actions, hence the term 'forgone utility'.

As shown in Table 1, these different types of utility allow us to detect and measure four of the six types identified in section 3. Not represented in So-Si-So models, as presently agents are driven only by their own values. This will change once we have extended the architecture with social norms.

In view of the categories of solidarity we want to test, we did not need to make agents foresighted with respect to expected social behavioural patterns. Agents are myopic and act only upon their knowledge of consequences of potential actions they might perform on their own concerns or on concerns of others. They do not take into account any belief or expectation regarding others' actions like in [START_REF] Conte | Reputation in Artificial Societies: Social Beliefs for Social Order[END_REF] or in [START_REF] Dittrich | On the Scalability of Social Order: Modeling the Problem of Double and Multi Contingency Following Luhmann[END_REF]. As noted in Table 1, such sophistication will be needed to detect calculated solidarity.

Agents in So-Si-So compute their perceptions according to their values only, their concerns according to their actual perceptions (and some of their previous perceptions, since agents can keep their factual beliefs for memory depth time steps), and their actions according to their causal beliefs based on actions. Figure 1 below is expanding the Perception-Deliberation-Action cycle from Jacques [START_REF] Ferber | Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence[END_REF] as it is activated in So-Si-So agents. If more cognitive agents are required, the deliberation stage might be more refined, for example through the identification and choice of actions, taking into account more than causal beliefs only.

A simple Test Model

We tested So-Si-So with what we see as an embryonic version of Solid'eau: a simple decontextualised model of a set of individuals, equipped with the previously described cognitive capacities, located in an urban or a rural area, in which they have a productive activity using units of a shared resource. To facilitate analysis, we use no stochastic parameters. The two areas (modelled as physical spaces) are linked by a water resource. This resource is localized, with a flow from an upstream space to a downstream one, depending on resource availability in the upstream space. As it is the most frequent case, we assume that the rural physical space is located upstream. The connection between the two spaces is described by the two following rules:

• a constant ratio of resource level, φ, disappears from upstream space and flows in downstream space, • if the resource availability in the upstream space after resource renewal exceeds its maximum capacity, the surplus flows to the downstream part.

The resource in the upstream physical space renews at a fixed rate ρ relative to its maximum capacity.

Agents are localised in either one of the physical spaces. The population is then described by the total number, N, and the ratio in urban area, θ. Urban agents and a part of rural agents (those who have social ties in the urban area) share a social space.

Agents are described by their localisation, the weight α they attach to social concerns, and their thresholds to determine how they assess the information received from their sensors. All agents are driven by three values: ('survival', IND, 1), ('environment', COL, 0.33) and ('wealth', IND, 0.33), the numbers indicating relative importance, with potential concerns ('subsistence', 'survival', 1), ('budget', 'wealth', 1) and ('resource', 'environment', 1).

Possible actions of agents are production at level 0, 1, 2, or 3, where production at level 0 means: do not produce. Production in a rural area consumes πr*level units of resource and generates Υr*level units of budget, respectively πu*level and Υu*level in urban areas. Agents also incur production costs of γ*level, the base production cost γ being equal for urban and rural areas.

All agents have the same causal beliefs:

• ('produce.0', {('subsistence', AWFUL), ('resource', GOOD)}, 0)

• ('produce.1', {('subsistence', GOOD), ('budget', GOOD)}, γ)

• ('produce.2', {('subsistence',GREAT), ('budget',GOOD), ('resource',BAD)}, 2*γ)

• ('produce.3', {('subsistence',GREAT), ('budget',GREAT), ('resource',AWFUL)}, 3*γ)

At each tick, all agents spend the same fixed amount of budget for their cost of living, λ. The order in which agents can act (and therefore co-determines their actual resource use, given a chosen production level) is fixed for each physical space. All agents have sensors that generate factual beliefs fb = (indicator, judgement) for the indicators 'resource' (to assess the resource availability in the physical area where the agent produces), 'subsistence' (to assess whether the agent's budget is sufficient to cover its cost of living), and 'budget' (to assess whether the agent's budget is on average increasing, with a desired percentage per year. These sensors return judgements based on threshold values. In the model we have used so far, all agents to have the same thresholds for the same concern, but these threshold values may be individualised. Table 2 shows the threshold values used, as well as all other parameter values for the model used in the simulations referred to in the next section.

Simulation Results

Even though this work is still ongoing, we have been able to verify that the So-Si-So model architecture permits identification and measurement of the various categories and subcategories of solidarity, even with a model with but few options in terms of values and the structure of social spaces. The model's outcomes have been verified through code proofreading and comparison of outcomes with expectations.

Figure 2 and 3 show two scenarios, the only difference being that in the second scenario some of the rural agents do not share the urban-rural social space. As the aim of this paper is to propose a categorisation for solidary behaviour and ways to measure it, the model results are illustrations that hold little surprises. In both scenarios, stimulated by their desire for wealth (a budget increase of at least 10% and preferably 20% or more of their initial budget each time step), the agents who can use the resource first produce at high levels, while those who then see the resource dwindle become concerned about it and produce less. Around tick 30, the least fortunate agents start to produce merely to survive (this causes the high peaks of selfinterested utility: production serves both survival and wealth). As more agents become very concerned about the resource, agents who share their social space start foregoing high production (this causes the peaks of foregone utility that first appear around tick 40) and by consequence fall back in wealth. Looking at both the resource level plot and the budget units graph in Fig. 2, it can be seen that gradually more rural agents forego production even when their resource (upstream) would permit it.

As was expected, the first scenario shows more solidary behaviour. In the second scenario, a resource crisis occurs between tick 110 and 125, when more than half of the urban agents run out of budget. In the model used, this makes them become inactive, which represents that the inhabitants leave the region, or-worse-starve. Inactive agents are ignored, so their concerns no longer influence the deliberation of other agents. As a result, the three rural agents who were sensitive to the urban agents' concerns feel less need for solidarity pick up their production. The steady alternation in Fig. 3 between production at level 0 and level 1 shown by the six rural agents without a social space reflects their own concern with the resource only; they are the last to access the rural resource, and their budget drops only when the three rural agents who do share a social space with the other agents pick up their production.

Population

Conclusion and perspectives

With this tentative framework to represent solidarity at an individual level we have succeeded in identifying and distinguishing solidary actions in a simple virtual world, and we have paved the way for an evolution towards a more grounded representation of resources and networks of relations between agents (via social spaces) as well as between agents and these resources (via physical spaces).

To achieve this evolution we need to couple this framework with a more structured description of the virtual world, and to include concepts that will permit representation and analysis of other forms of solidarity. For example, to represent imposed solidarity, we will have to include norms.

We aim at incorporating this work in a policy perspective, through the identification of existing social networks which might serve as driving belt for solidarity actions and joint preservation of resources across physical spaces.

Fig. 1 .

 1 Fig. 1. Extension of Ferber's Perception-Deliberation-Action cycle in So-Si-So

Fig 2 .

 2 Fig 2. Scenario in which all agents are part of one and the same social space

Fig 3 .

 3 Fig 3. Same scenario, except that 6 of 9 rural agents have no social ties with the other agents

  a removes all factual beliefs fb from a.Bfact for which (Clock.tick -fb.tick) > a.m. 2. Perceive. Agent a activates each of its sensors; each sensor in a.Sens may add to a.Bfact a new factual belief about the state of a's environment. 3. Appraise. Agent a checks to see whether its factual beliefs activate one or more of

its potential concerns: for each factual belief fb in a.Bfact the agent checks whether it has a potential concern c in a.Con with c.indicator = fb.indicator; if that is the case, the agent checks to see whether it already has a private concern pc with pc.concern = c; if not, such a private concern pc is created (with pc.state initialised to 0) and added to the agent's set of private concerns; the state of the (new) private concern pc is then updated as follows: pc.state = pc.state + c.intensity*c.value.importance*fb.judgement 4. Survey socially. The agent a considers the concerns of those agents with which it has a social relation: let n be the sum, for each social space ss in a.Soc, of the number of other agents that are also part of ss; then for each social space ss in a.Soc, the agent a checks for each other agent b in ss whether it has one or more weighted concerns wc in b.Cw with wc.state < 0 and wc.concern.value.type = COL. For each such wc, agent a checks to see whether it already has a social concern sc with sc.concern = wc.concern; if not, such a social concern sc is created (with sc.state initialised to 0) and added to a.Soc; the state of agent a's (new) social concern sc is then updated as follows: a.sc.state = a.sc.state + b.wc.state / n

Table 1 .

 1 Operationalisation of different types of solidarity

	Type of solidarity	Detection/measure
	altruism	Usoc + Uneg + Uforegone
	heartfelt solidarity	The distinction between altruism and heartfelt solidarity can be
		made in step 4 (survey socially). Altruistic actions are precluded
		by making agent a consider only those social concerns that are
		related to a value that also occurs in a.Val. As the present
		Solid'eau model includes only one collective value, the
		difference cannot occur.
	opportune solidarity	Uopp
	self-interested solidarity	Uself
	calculated solidarity	Not represented in So-Si-So models, as in the present
		architecture agents cannot anticipate on other agent's actions
		and therefore not foresee reciprocity.
	imposed solidarity

Table 2 .

 2 Parameter setting of the Solid'eau model

	Parameter

This workshop benefited from the participation of Géraldine Abrami, Olivier Barreteau, Bettina Blümling Pieter Bots, Catherine Carré, Flavie Cernesson, Raphaële Ducrot, Katrin Erdlenbruch, Patrice Garin, Patrick Le Goulven, and Cathy Werey. We wish to thank them for numerous contributions to the discussion, some of which provided inspiration for this paper. However, only the authors are responsible for the views and ideas put forward in this paper.


Frederic Ros
email: frederic.ros@gemalto.com

Serge Guillaume
email: serge.guillaume@montpellier.cemagref.fr

Rachid Harba
email: rachid.harba@univ-orleans.fr

A GA BASED APPROACH FOR CLASSIFICATION PURPOSES

Keywords: classification, genetic algorithms, hybrid systems

This paper presents a nearest prototype classifier based on a hybrid genetic algorithm. It has been developed for general pattern recognition tasks and can be applied for identification. The approach deals simultaneously with the twofold objective of selecting relevant features and minimizing the set of instances to discard the noisy and superfluous ones. The interest of the approach is demonstrated with real life data sets.

INTRODUCTION

The purpose of an authentication system [1] is to verify the claim of the identity of an individual. It is a pattern recognition system which may operate either in verification mode ore identification mode: the first consists of a "one-to-one check". The verification is performed locally by comparing individual's features with the templates stored on the credential. The identification mode consists of presenting an individual's credentials (one-to-many check) to verify the individual exists within a known population. Identification confirms the individual is not enrolled with another identity and is not on a predetermined list of persons (e.g. blacklist). Typically this operation needs a secured database and it relies on statistical analysis and machine learning techniques [2]. The decision procedure is called a "classifier". For any biometry systems multiple templates are necessary to account for variations observed in the biometric trait and the templates (also called prototypes or instances) in the database may be updated over time. To be efficient for identification purposes, a classifier has to be tractable, selective and flexible. Compared to other well-known classifiers [3], based for example on radial basis function or back propagation neural networks, neighborhood techniques [4] remain very attractive thanks to their easy use and simple implementation. According to 1-nn rule, an input individual is assigned to the class of its nearest neighbor from a labeled reference set. Updating the database does not require any other computations. The main drawbacks of nearest classifiers in practice have been their computational demands and memories. In addition, they generally require low feature spaces to be efficient.The relevance of a pattern recognition system is highly dependent on measured features representing the pattern. For each database, high efficiency can be obtained only by optimizing the feature selection part. The goal of designing efficient nearest classifiers is then to maximize classification accuracy while minimizing the sizes of both prototype and feature sets. This imposes pre-processing stages to respectively edit the best prototype patterns and select the best feature vectors. Feature selection [5][6],while remaining a challenging issue, has been extensively researched. The selection can be done either considering each feature independently, the filter approach [7], or by managing a subset of the available features as in wrapper approaches [8]. The importance of the feature selection step is a crucial one as the distance function works in the feature space. The neighborhood of a given pattern is highly dependent on this distance function, i.e. the selected features. For prototypes, the objective is related to instance selection problems, editing and condensing techniques [9-10]: the goal is to select the most critical patterns in order to make the classifier faster and relevant. This objective is of prime concern when dealing with large databases as finding a pattern neighborhood requires as many distance computations as there are items in the reference data set. Despite their obvious dependence, these points are generally studied separately. In this paper, we propose to perform in a single step edition and selection via a multi objective approach, the challenge is to obtain the global optimal solution with a minimum number of experiments. Among many search algorithms, GAs [11] (genetic algorithms) are one of the best-known techniques for solving optimization problems. Their use has reported promising results in many areas and their reputation for selection problems is certain. However, the majority of the methods involved in multiobjectives suffer per nature from the excessive consuming time to design the optimal solution. Specifically, standard GA may fail and particularly when applied to real life problems involving many features and patterns. We therefore propose a dedicated GA which is hybridized with more conventional techniques. The hybridization is structured in such a way that the classifier tractability and efficiency are both optimized. We focus here on the development of a generic classifier for small and medium databases. The next section is devoted to the methodology. We then present its performances on real pattern recognition problems to give some conclusions.

MATERIAL AND METHODS

To build an efficient nearest neighbor classifier three objectives have to be reached: achieve a high accuracy rate, minimize the set of prototypes to make the classifier tractable even with large data bases and internally, reduce the set of features used to describe the prototypes. At the opposite of many methods separating the instance and feature selection aspects despite their dependence, we propose to perform in a single step edition and selection via a multi objective approach managed by a dedicated GA. Let Z = z 1 , . . . , z be a set of samples described by a set of features X = x 1 , . . . , x f . Each item, z j ∈ R f , is labeled, L = 1, . . . , l being the set of available labels. Given C 1nn a nearest neighbor classifier, the optimization problem consists in finding the smallest subsets S 1 ⊆ X and S 2 ⊆ Z such that the classification accuracy of C 1nn over Z is maximal.

T HE GENETIC ALGORITHM

GAs can be seen as powerful techniques miming natural reproduction. To solve a classification problem, a single solution via a fitness function must be presented in a single data structure. GAs will create a population of solutions based on the sample data structure proposed. In fact, they work on the basis of a set of candidate solutions. Each candidate or chromosome represents a trial solution of the problem posed and is a member of the population. For a recent review see [12]. There are few studies using evolutionary techniques to define 1-nn classifiers with the twofold objectives of prototype and feature selection. The native ones can be found in [13][14].

Conceptual strategy: Our proposal is hybrid (See Fig. 1). The genetic exploration is driven by an aggregative fitness assignment strategy. It is based on two self-controlled phases with dedicated objectives combining crowding and elitist strategies. The first one, which can be called a preliminary phase, is a pure GA. The goal is to promote diversity within the chromosome population in order to remove the unused features and to prepare the second step, called the convergence phase. This stage starts when there is a large enough number of good and diverse chromosomes in the population. The GA is then hybridized via forward and backward local procedures. The hybridization is structured in such a way that the classifier tractability and efficiency are optimized. Some neighborhood concepts related to the prototype nature are also incorporated in the local procedures. By progressively filtering useless and noisy prototypes, they contribute to select critical prototypes and discard superfluous or noisy ones. During the genetic life, elitism and pressure preservation are reinforced by two mechanisms, say, a breaking process and an evolutionary memory. Instead of trying in vain to maintain an effective search and a good selection pressure in the current population, this mechanism considers the current best chromosome for a secondary population (called the archive population) while re-seeding the current population to explore new directions. The archive population is updated at each generation from the chromosome solutions found out through the different explorations in such a way that both diversification and elitism are promoted. The combination of implemented mechanisms and the particular hybridization approach constitute the main parts of our contribution. It should be noted that the first phase is mandatory for starting the design of a new classifier but not necessary when new individuals are added to the native database. In this case, these individuals are included in preliminary "competent" chromosomes to form the initial population of the second stage.

The chromosome: As the optimization procedure deals with two distinct spaces, the feature space and the pattern space, both are managed by the GA. A chromosome represents the whole solution. It is encoded as a string of bits, whose length is f+p, f being the number of available features and p the number of patterns in the training set. In a chromosome a 1 for the ith feature or pattern stands for its selection, while a 0 means it is not taken into account. As the number of features is likely to be smaller than the number of patterns, in order to speed up the procedure and to improve the exploration power of the algorithm, the two spaces are managed independently at each iteration by the genetic operators such as crossover and mutation. This means the whole chromosome is the union of two distinct subchromosomes, the first one to encode the feature space and the second one the pattern space. In each subchromosome a classical one-point crossover is applied. We superimpose some general restrictions for a chromosome to represent a valid solution. Some others can be included for each particular problem.

F = w c C 1nn (Z) + w f λ f + w p λ p (1)
with w c +w f +w p = 1. The weight values stand for the importance of the corresponding objectives. The parameters λ f and λ p , have to be maximal for a small number of selected features or patterns.

λ f = 1 -|S 1 | f max i f |S 1 | ≤ f max 0 else (2) λ p = 1 -|S 2 | p max i f |S 2 | ≤ p max 0 else (3)
The parameter f max for the feature space and p max for the pattern space are set to limit the range of variation of l.

SPECIAL MECHANISMS

Preserving both elitism and diversity constitutes the main challenge for a GA. Most methods [14-15] such as Determinist Crowding (DC), Restricted Tournament Selection (RTS) and others are continuously looking for a balance between elitism and diversity in the current population. We have implemented two mechanisms:

An evolutionary memory: Two distinct populations with different evolution rules and no direct interaction are used. The first one is called the current population, pop c , its evolution is managed using classical genetic schemes (elitism, DC, RTS, ...). The second one is called the archive population, pop a , it acts as an evolutionary memory. It is a repository of good chromosome solutions found during the evolution. The chromosomes of pop c are included in pop a only if they provide either more elitism or more diversity. The decision to include a given chromosome in popa is based on two criteria, the first one is the fitness score. This is the elitist side of the process. If the candidate score is slightly better than others, the candidate replaces the chromosome with the most comparable structure. This is the diversity side of the process.

Breaking process: The current population needs to be reseeded when there are a lot of similar chromosomes within the population. The similarity between the ith and jth chromosomes is:

s(i, j) = 1 i f d f h (i, j)
< n f and d p h (i, j) < n p 0 else (4) where d f h (i, j) (resp. d p h (i, j)) stands for the hamming distance in the feature (resp. pattern) space, and n f (resp. n p ) is a predefined threshold. The proportion of chromosomes similar to the ith one is given by:

P s (i) = 1 s -1 s ∑ j=1, j =i s(i, j) (5)
where s is the population size. This mechanism produces major changes in the current population by including chromosomes from the archive population or applying a high mutation rate to refresh the chromosome. The breaking mechanism is active when there are a lot of similar chromosomes within the population. The P s (i) are thresholded to compute the diversity index:

DI = 1 s s ∑ i=1 S(i)
where S(i) = 1 i f P s (i) > th min 0 else (6) When the diversity index, DI, is too low, some of the chromosomes which have a lot of similar ones in the population, some of the i ones for which S(i) = 1, are either replaced by ones randomly chosen in the archive population or re-generated with a high mutation probability.

OPTIMIZATION

Convergence phase: in this phase, the GA is intelligently hybridized via ascending and descending local phases. The ascending one aims at aggregating new elements, features or prototypes, in a given chromosome while the goal of the descending phase is, on the contrary, to remove features or prototypes from the chromosome description. Both procedures are random free. They are based on the population yielded by the GA. The hybridization is applied in such a way that the contribution of local optimizations is relevant for optimization without monopolizing too many computing resources, making the method practical for medium size data. The local procedures are carried out periodically in sequences and only a fraction of the chromosomes randomly chosen and only a variable subset of chromosome components are considered. They are applied only with competent chromosomes to avoid vain computational processing. It is a good compromise between the complete use of local search, which is not practicable, and complete removal, which leads to worse solutions.

Local optimization: Let us first consider the ascending step. It can be applied to the feature or the prototype space. Let S ′ be the set of chromosomes whose fitness score is higher than a given threshold, and S ′ 1 ⊆ X (resp. S ′ 2 ⊆ Z) be the set of features (resp. prototypes) included in at least one chromosome (from S ′ ) description. The ascending procedure consists, for each chromosome in S', in aggregating each of the features in S'1 (resp. each of the prototypes in S'2) to the chromosome and selecting the ones that improve the classification results. The process is repeated until no improvement is possible or a maximal number of ascendant iterations is reached. It should be mentioned that the number of features and prototypes to be tested is reasonably small as some features have been discarded by the first phase of the GA, and among the others, only those which are currently part of one of the best chromosomes are used. This remark highlights the complementary roles played by the GA and the local approach. However, depending on the evolution stage, the cardinalities of S'1 and S'2 may be important. In this case, in order to control the ascendant procedure computational cost, the number of features or prototypes tested by the procedure is limited. The selected ones are randomly chosen in S'1 or S'2. The descending phase is only applied to the S' set. For each chromosome each of the selected features (resp. prototypes) is removed if its removal does not affect the classification results while improving the fitness function.

Prototype filtering: The prototype selection is not only based on classification results, it also takes into account the prototype status within the training set in order to avoid selecting either noisy or superfluous prototypes and favor the selection of critical ones. A simple and unambiguous definition has been considered. A prototype is said to be noisy if none of its k nearest neighbors is of its class. That means this prototype is not able to correctly classify any of its neighbors. The value of k, k ≥1, is set according to the class cardinality, the higher k the lower the number of prototypes likely to be removed. On the other hand, a prototype is said to be superfluous if all of its neighbors are of its class. That means its neighbors remain well classified after its removal. The amount of filtering depends only on the number of neighbors, k, no additional heuristic is needed. These concepts, noisy or superfluous prototypes, are highly dependent on the feature space and the distance in use. Thus, their implementation requires a specific management via an evolutive memory: a list of prototypes to be discarded is attached to a given feature space. The more the convergence phase progresses, the more the memory provides information about the prototype nature and speed up the local procedures. The identification of noisy or superfluous prototypes is carried out at the beginning of the descending procedure. The prototypes part of the list are no longer available, neither for the ascending procedure nor GA selection or chromosome generation. Note that GA may select superfluous prototypes as they improve classification results. In this case the solution found can be considered as good but remains a suboptimal one.

RESULTS AND DISCUSSION

The method is not dedicated to a specific application domain. It has been initially developed for pattern recognition applications involving few individuals (classes) with many templates. We therefore have then devoted the evaluation to this context by selecting seven known data sets of variable difficulties. Five have been largely used to test many machine learning algorithms [8] and the two others are from the chemometric area. For some of them, we have sampled the individuals to respect a balance in the sizes. The database characteristics are summarized in Table 1.

From each data set, 10 training and test samples are randomly generated. The training set is made up of about 80% of the data set, the remaining 20% being the test set. For each of the ten samples, the training data are centered and normalized, the computed coefficients are applied to the corresponding test set. For each database, we compare our hybrid GA to two very popular genetic approaches: MHA (Multi Hill Climbing) and EA (Elitism strategy) algorithms [13][14]. Both are not hybrid. These methods were compared to no genetic approaches where selection and edition were applied in different steps. They have proved to be better than all the other combinations of tested approaches. We then focus on comparing our hybrid GA to only genetic approaches. Then for each of the 3 algorithms, a classifier is designed using the training data and its performance is assessed over the test data. The same very common genetic parameters have been chosen whatever the database, and of course the same fitness function. The selected weights and other parameters have been the followings: w c =0.4, w p =w f =0.3, n f =1, n p =0.1*p, th min =0.75*s. The overall results (Table 2)correspond to the best overall score obtained after 20 runs of 300 generations for each algorithm and a population of 100 chromosomes. Each element respectively depicts the number of features, instance patterns, and classification test scores. These results highlight that the HGA gives better results than any of the other algorithms. They vary a lot regarding database difficulty. For very simple sets such as iris or breast, there is no real difference. The native feature space is already competent for classification purposes without any selection. The databases Gaussian 8D, Satimage and Texture present more features and patterns. HGA leads every time to more tractable and efficient classifiers. Chemometric databases are reputed difficult to manage as they contain more overlapping. HGA gives various competent chromosomes and its superiority is globally higher than the ones of MGA and EA. It is clear that only HGA is able to perform the double selection correctly. It should be noted that the classifier performances obtained for Chemo 2 can be improved by increasing a little w c . With w c =0.6 providing more importance to the efficiency, the classification performances are between 0.8 and 0.85 with a cardinality for S 1 and S 2 less than 5. Concerning the other approaches, MGA has more difficulties than the others to manage the three objectives. It can be easily explained: This random recursive search approach does not include intelligent mechanism. EA is a selective algorithm which can come across a classical premature convergence issue due to the difficulty to define the right controlling parameters (which remains a challenge for pure GAs). This consolidates our idea of introducing different helping mechanisms (evolutionary memory, breaking process, hybridization) to compensate some weaknesses of pure GAs.

CONCLUSION

In this paper, we have proposed a nearest classifier based on a hybrid algorithm aiming at maintaining

Fig. 1 .

 1 Fig. 1. Hybrid algorithm: basic diagram

Table 1 .

 1 Data base characteristics

		Iris Breast Gaussian8D Satimage Texture Chemo1 Chemo2
	# items	150	699	1000	1028	989	566	1294
	# features	4	9	8	36	40	166	167
	# classes	3	2	2	6	11	8	8

Table 2 .

 2 Method Evaluation

	Iris	Breast	Gaussian8D Satimage	Texture	Chemo1	Chemo2