Flavien Balbo
email: balbo@lamsade.dauphine.fr

Fabien Badeig
email: badeig@lamsade.dauphine.fr

Julien Saunier
email: saunier@inrets.fr

EVALUATING THE COST OF SUPPORTING INTERACTION AND SIMULATION THROUGH THE ENVIRONMENT

Keywords: Environment, Evaluation, Communication, Activation

The environment has emerged as a powerful first-order abstraction in Multi-Agent Systems (MAS), as well as a critical building block. One benefit is to reduce the complexity of the agents by delegating to the environment a part of the tasks of the system. This delegating process provides a flexible way to exchange information and to coordinate the agents thanks to the environment. The counterpart is a centralization of a part of the MAS processes inside the environment. In this paper, we present the modeling of an environment for multi-agent communication and simulation. Our proposition enables the addition of advanced features to the MAS like multi-party communications (communication) and contextual activation (simulation). We evaluate the cost of this environment process and compare it to the execution of the same tasks in the agents for communication and simulation.

Introduction

In [START_REF] Weyns | Environment as a first-class abstraction in multiagent systems[END_REF], the authors give the following definition of a multi-agent system (MAS) environment: "The environment is a first-class abstraction that provides the surrounding conditions for agents to exist and that mediates both the interaction among agents and the access to resources". The environment is a critical building block in the multiagent systems that encapsulates its own responsibilities. The agents interact in their environment and the effects of their actions are observed and evaluated through this environment. Thus, the environment provides observability and accessibility services.

The relation between the environment and the agents is traditionally based on a perception -decision -action cycle [START_REF] Weiss | Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence[END_REF] which is repeated by the agents during their life time. The three phases of the cycle are executed in each agent. The perception being the agent ability to observe its environment, its result is the computation of what can be called contexts. A context is defined as a set of information that can be used to characterize a situation. This set of information includes percepts and messages that are obtained by the agent and its own state. Thanks to the context computation, the agent decides to execute the suitable action. The relation between the environment and the agents based on this perception -decision -action cycle does not exploit the potential of the environment that remains a static entity. This relation can be enhanced by delegating the perception process to the environment [START_REF] Weyns | Towards active perception in situated multi-agent systems[END_REF][START_REF] Badeig | Contextual activation for agent-based simulation[END_REF][START_REF] Saunier | Regulated multi-party communications and context awareness through the environment[END_REF][START_REF] Kesaniemi | An observation framework for multi-agent systems. Autonomic and Autonomous Systems[END_REF]. The objective is to support advanced features that are difficult to obtain without the environment.

We have proposed an environment modelling and the adequate platform that are based on the delegation of the perception process to the environment. Our proposition supports two advanced features: 1) Multi-Party Communications (MPC) [START_REF] Branigan | Perspectives on multi-party dialogue[END_REF] takes into account dyadic interaction (one to one), group interaction (one to many) and overhearing (many to one/many) within the same interaction process; 2) Contextual activation [START_REF] Laberge | learning and cognitive processes[END_REF] applied to the simulation process consists in activating the agents directly according to their context.

In our proposition, despite the delegation process to the environment, the agents keep their autonomy because the decision process and the action process remain in the agents. The perception phase of the cycle is modified to take into account the relation with the environment. That means that the environment computes the contexts for the agents, and that the agents can modify this computation process of the environment to suit their needs: the agents decides which contexts are important for them and act by modifying in consequence the computation process that is executed by the environment.

In our proposition, in the MPC case, the environment mediates the communication: the context is the information about the agent receiver, the message and any other environment information which is relevant to this communication. if the context is validated, the environment addresses the messages to the related agents. In the simulation case, the environment is the scheduler that manages the agent activation: the context is the subset of information accessible to the agents. The environment activates an agent in a specific context and according to this context, the agent performs the suitable action.

To adapt the perception process to each agent, the environment needs 'tools' to compute their contexts. In our proposition, these tools are filters that reify the relation between an agent (described in the environment) and its contexts. A filter contains the constraints on the context related to an action of an agent. This action is the reception of a message for communication filters and a specific agent action to perform after validation for activation filters. The agents modify their relation to the environment thanks to the addition and removal of their filters in the environment. This process is dynamic and the environment activates only its current filters. These choices (addition/removal) belong to the decision process that is managed by each agent.

The externalization of the computation of the perception process improves qualitatively the design of a MAS. The dynamic filter management by the agents gives more flexibility to the MAS design. More details on qualitative improvement are given in [START_REF] Saunier | Regulated multi-party communications and context awareness through the environment[END_REF] for communication and in [START_REF] Badeig | Contextual activation for agent-based simulation[END_REF] for simulation. The counterpart is a centralization of a part of the MAS processes inside the environment. In this paper, we evaluate the cost of this centralization for computing agent contexts, in comparison to the execution of equivalent solutions for communication and simulation.

Section 2 motivates the delegating process of tasks to the environment for communication and simulation and introduces an illustrative example with different examples issued of a crisis management application. Section 3 presents the environment model. Section 4 provides a theoretical evaluation. In section 5, we provide an empirical evaluation, and we conclude in section 6.

Motivations

Communication

Recent research on multi-party communications [START_REF] Branigan | Perspectives on multi-party dialogue[END_REF][START_REF] Saunier | Regulated multi-party communications and context awareness through the environment[END_REF] shows how multi-agent communications can take advantage of the complexity of the human communication process. The main issue in supporting MPC is to take into account dyadic interaction (one to one), group interaction (one to many) and overhearing (many to one/many) within the same interaction process. The sender does not know all the agents that might be interested in its messages. For example, an agent can listen to messages without the agreement/knowledge of the sender through overhearing. For a recipient, the usefulness of a message may depend on the context of the sender, the context of the message, and the context of the recipient itself.

These challenges are related to the way the recipients are chosen. MPC requires knowledge of the needs of both the sender and the recipients. From the sender viewpoint (direct interaction), it is a connection problem: which agents are related to my message? The problem is to map the senders needs (information, capabilities, resources, ...) to the address of related agents. From the recipient viewpoint (indirect interaction), it is a data extraction problem: which messages are related to me? The problem is to map the recipients needs to the content of the messages. For each message, these problems have to be simultaneously solved by the communication infrastructure. The environment is able to solve these problems by mediating the communication in order to find all the receivers of each message. Nevertheless, in the cognitive agents community, few works explicitly present the environment as an interaction support. For direct interaction, the environment is often associated to an infrastructure that supports point to point communication. For indirect interaction, cognitive agents use specific services that are based on the management of a shared collection of data (e.g. [START_REF] Picco | Exploiting transiently shared tuple spaces for location transparent code mobility[END_REF]) that may be understood as a part of the environment. There is therefore a separation between the solutions to realize direct and indirect interaction although the environment provides a suitable framework to unify them [START_REF] Platon | Overhearing and direct interactions: Point of view of an active environment[END_REF].

If the computation of the context does not take into account ambient conditions, it can classically be done inside the agents. This solution implies that the agents receive all messages and filter them. An evaluation of the environment support consists in the cost comparison of the context filtering either in each agent after the reception or in the environment during the transmission process.

Agent-based simulation

In a simulation, the scheduling policy defines the activation order of the agents. Once activated, the agents behave according to their context. How the agents are activated and what information is available to compute the agent context depend on the agent-based simulation (ABS) framework.

In most ABS frameworks, a scheduler activates the agents one after the other and each activated agent computes its context to choose one action to execute at each simulation step. The classical ABS frameworks are designed to support this activation process. For example, in the platforms CORMAS [START_REF] Bousquet | Cormas: Common-pool resources and multi-agent systems[END_REF] and MASON (Luke et al., 2005), the scheduler activates a standard method for each agent. This method is specialized by the designer to adapt the agent behavior. In the Logo-based multi-agent platforms such as TurtleKit [START_REF] Gutknecht | The madkit agent platform architecture[END_REF] or the STARLOGO system1 , an agent has an automaton that determines the next action to perform.

The choice of these platforms to be agentoriented, with a light environment support, implies that the computation of the context is repetitive because it is computed in each agent at each time cycle during the simulation execution. This computation is done in each agent even if the agent context does not change between two time cycles and/or if several agents share the same context during a time cycle. Here, the evaluation consists in the cost comparison of the context filtering either in each agent after the activation or in the environment during the scheduling process.

Example

In this paper, we consider a crisis management application where several emergency services must be coordinated in order to reduce the crisis effects. A crisis situation is a dynamic phenomenon defined by the initial situation, which depends on place and time, and by the impact on population and infrastructure. We focus our example on a specific point which is the victim evacuation. This task consists in coordinating two agents playing the role medical porter. The goal of the medical porters is to shift a victim to an emergency vehicle. This action requires one medical porter with the skill medical monitoring and one medical porter with the skill victim handling. The first skill allows the medical porter to monitor the victim and to inform the hospital of the evolution of the victim health. The second skill is necessary to handle correctly the victim.

Each simulation component (agents, messages and objects) is situated on a grid, i.e. a twodimensional space. In this example, we consider that the victims belong to the set of the objects because they are not autonomous. The agents (medical porter) act in this environment and cooperate in order to evacuate victims. A medical porter can move randomly or towards a given direction, and it possesses only one skill. It can either monitor or handle a victim, but the two skills are required to evacuate the victim. The agents can communicate in order to find a partner with the complementary skill. Each agent has a field of perception that limits its perception of the environment. A medical porter is able to perform one of the following actions in a time cycle of simulation: 1) the action move randomly, 2) the action move towards a location, 3) the action wait, and 4) the action evacuate a victim.

We use this application along the paper to illustrate our study of the cost of the environment supporting interaction and simulation.

Environment Modeling

To support multi-party communications and contextual activation, we propose to use the environment as a privileged intermediary to control interaction (EASI, Environment as Active Support for Interaction) and activation (EASS, Environment as Active Support for Simulation). The EASS model [START_REF] Badeig | Contextual activation for agent-based simulation[END_REF] embeds the EASI model [START_REF] Saunier | Regulated multi-party communications and context awareness through the environment[END_REF]. The environment manages metainformations on the MAS (agents, messages, context) and uses them to compute the agent context(s). In this section, we give the background elements to understand the assessment of the cost of the environment. More details about the models can be found in [?] 3 .

The environment model EASI is thus defined by Ω, D,P,F with:

• Ω = {A ∪ M SG ∪ O} = {ω 1 , .
.., ω m } the set of entities (with A the set of agents, M SG the set of messages and O the set of objects, i.e. all entities that are not agents or messages),

• D = {d 1 , ..., d m } the set of domain descriptions of the properties,

• P = {p 1 , ..., p n } the set of properties, • F = { f 1 , ..., f k } the set of filters.
Entity: An entity ω i ∈ Ω is defined by e r , e d where e r is a reference to an element of the MAS and e d is the description of that element. An element of the MAS can be an agent, a message or an object. A reference is its physical address on the platform or other objects (such as URL, mailbox, etc.).

The description e d is a set of couples p i , v j where p i ∈ P and v j is the value of the property for the entity. Any agent of the MAS has its own processing and knowledge settings. It is connected to the environment thanks to its description that the environment stores and updates. This description e d is used for the routing of the informations to the agent with the reference e r (EASI) or its activation (EASS). The agents can modify their description dynamically. Property: A property p i ∈ P : Ω → d j ∪ {unknown, null} is a function whose description domain d j ∈ D can be quantitative, qualitative or a finite set of data. The unknown value is used when the value of the property cannot be set, and null is used to state that the property is undefined in the given description. In order to simplify the notation, only the value of the description domain d j is given to specify a property.

Filter: A filter identifies the entities according to their description (e d ) and realizes the interaction between the concrete objects (e r ). A filter

f j ∈ F is a tuple f j = f a , [ f m ], [ f C ], n f with n f the filter name.
The assertion f a : A → {true, f alse} identifies the related agents, the assertion f m : M SG → {true, f alse} identifies the related messages, and f C : P (Ω) → {true, f alse} is an optional set of assertions identifying other entities of the context. A filter is considered valid for any tuple agent,

[message], [context] such as f a (agent)[∧ f m (message)][∧ f C (context)] is true.
The choice of the action specializes the filter. Every agent a whose description validates f a is activated if there exists a set of entities in the context such that f C is true. After its activation, the agent validates the action related to this context and executes it (or not). It is a communication filter if the action is to add the message m that satisfies f m in the message box of the agent a. The agents can add and remove dynamically the filters. Thus, they adapt their relation with the environment according to their needs.

In a crisis simulation, the agents have observable properties: their identifier, which is unique, their location, their availability (true/false values) which specifies if an agent rescues a victim, their skill (position/monitoring), their field of vision, and their internal time. The messages have the following properties: their identifier that is unique, their sender identifier, the message type ('request'/'accept'), their location which is the location of the sender when the message is put in the environment, and the skill required by the sender in the case of communication. The victims have three properties: their identifier, their location and their status (stretcher/vehicle). The victims to be evacuated must be diagnosed; this is expressed by the property diagnosed (true/false values). The following In the simulation example, let f e be a communication filter related to the following context: an agent is interested by a message if it is available ( f a ), if the request message is close to the agent a and a has the requested skill ( f m ) and if the victim has been diagnosed ( f c ). In this example, f c contains one entity which is a victim identified by the property id v of the message. The request messages have information about the victim location and the skill of the medical porter.

The processing of the context is traditionally done by the agents, but in EASI and its extension EASS it is done by the environment. In this way, the computation can be done with information that is shared by the agents (the entities descriptions) and with a degree of mutualization. However, it implies the centralization of the computation and the management of the information update. Now, we propose to evaluate the cost of this centralization.

Theoretical assessment

The theoretical assessment is the comparison between the processing by the environment of a communication filter for n a agents and the processing by n a agents of all the messages. In order to take into account the context dynamics, this theoretical assessment also studies the update process of the MAS. The theoretical assessment is based on two criteria. The first, noted Cost T , is the number of tests performed during the filtering process and the second, noted Cost M , is the number of resulting messages. The objective is to identify in which cases it is better to medi-ate the communication through the environment than to manage it in the agents.

Following the definition given in section 3, a filter f has tests related to one agent description ( f a ), one message description ( f m ) and a subset of entities ( f c ). To simplify the explanation, we assume there is only one entity to match f c and this entity cannot be an agent. This last assumption implies that there is no additional cost for the update process if the message processing is executed by the agents. The following generic filter illustrates our assessment, it is shown in a classical "if" structure: The elements ?a, ?m and ?c are variables that respectively match an agent, a message and an entity. Let T x i be a test on a x entity and T

Tests N i f ∧ i=1..n T m i (?m) (
x,y i a test between two entities. For the filter example f e : an agent (?a) is interested by a request message (?m) (1) if it is available (2), if this request message is close to the agent and the agent ?a has the skill specified in the message (3) and if the victim to evacuate (?c) (5) is diagnosed (4). T a 1 (?a) is the result of the first test on an agent related to its availability and ∧ i=1..n T a i (?a) are all the tests on the agent receiver. T a,m 1 (?a, ?m) is the result of the first test on an agent and a message related to the requested skill and ∧ i=1..n T a i (?a, ?m) are all the tests on the receiver and the message.

Evaluation of the number of tests. A filter is composed of two types of tests. The first type is a comparison between the value of a property and a constant: the tests (1)(2)(4). The second type of test implies a matching process: the tests (3)(5)(6). For each of these types the cost in number of tests is related to the number of entities that have to be tested and on the result of the previous tests on the same set of entities. For example, the number of agents that is tested by T a 2 (?a) is related to the number of agents that have validated the test T a 1 (?a). Let t i be the percentage of entities that validates the test i.

Let |C i | be the number of tests and C i be the number of evaluated tests of (i), the value of C i is :

C i =        1 + |C i | ∑ j=1 j ∏ k=1 t k if |C i | > 1 1 if |C i | = 1 0 if |C i | = 0
The cost of a filter is the sum of the costs of its tests (sequentially validated). The following table gives the cost of the generic filter if one message has to be processed by the environment (column E) or by the n a agents (column A) . There are two differences between these two processing: 1) the factorization of the tests if the processing is executed by E; 2) the implicit elimination of the agents if the processing is executed by the agents. If the processing is executed by E the tests are factorized, for example (1) is executed only once and is repeated for n a agents. Each test (i) that is false implies an elimination of the agent that executes the the processing. For example in (5) only the subset of agents where the test (4) is validated continue the processing.

N E A tested entities (1) C 1 n a * C 1 n m = 1 (2) n a * C 2 n a *
Following the hypothesis that the filtering and the shared information are the same, the matching done by the agents is more costly than by the environment for the tests (1)(4)(5) and are the same for (2)(3)(6). We conclude that the mediation by environment is always better than the broadcast when at least one agent is interested in the message. Nevertheless the implicit agent elimination implies that if the agents do not share all information some part of the filter evaluation can be less costly for the agents than for the environment. This parameter will be empirically tested in section 5.

Moreover, the environment and the agents need the same information to process the filters and the result has to be balanced by the cost of the access to this information.

Evaluation of the number of messages. If the exchange of information is done via messages, there are two types of messages to take into account: 1) the messages related to the interactions in the MAS such as the request messages in our example f e ; 2) the messages related to the update process.

Firstly we evaluate the number of messages that are the result of the interaction in the MAS. Let n m be the number of messages sent by the agents, let p r be the average percentage of agents that have to receive the messages. If the matching process is executed by the environment then each message is sent to the environment, and the environment transmits it to the p r * n a receivers. The total number of messages is therefore n m (1 + p r * n a ). If the matching process is executed by the agents, then each message is sent to all the agents which locally execute the matching process. The total number of messages is therefore n m * n a . Except if p r is close to 1 which means that the message is related to all the agents, the environment mediation is less costly. The more the selection is important, the more the mediation by the environment is beneficial.

Secondly we evaluate the number of messages that are the result of the update process of the MAS. To simplify, we consider only the update process of the descriptions of the agents and not of the context, although the principle is the same. In our example, it implies that the state of the victims is not updated (or that its cost is the same if it is computed by the environment or by the agents). When an agent is updated all its properties are updated in the environment. Remember that the filter example does not contain tests on the state of the agents to compute the context ( f c ). Hence, the computation by the agents does not imply additional costs because we suppose the agents do not need to access updated information about the other agents, which is an underestimation of the cost of the "agent" solution.

When the communication is mediated by the environment, the agents update their descriptions by putting in the environment new descriptions that replace the old ones. This action is associated to the sending of a message. One agent can make between 0 and n updates during a time period. Let f req a be the average frequency of the description update during a time period. There is therefore f req a * n a update messages if the interaction is mediated by the environment during the reference time period.

To have the total cost according to the number of messages criteria we have to sum these costs. Let Cost E M = n m (1 + p r n a ) + f req a n a be the total environment cost and Cost A M = n m n a be the total agents cost. To compare these two costs, we study the sign of the subtraction of the two costs

Cost M = Cost E M - Cost A
M in order to find when the environment medi- ation is more costly than the local computation in function of the number of messages and of the frequency of the update process. The resulting formula is Cost M = n m (1 + n a (p r -1)) + f req a n a . Figure 1 gives the plan corresponding to this function in the three dimensional space (message, agent update, cost) if the number of agents (n a ) and the average proportion of receiver (p r ) are respectively fixed to 100 and 0.6. These assessment parameters are unfavourable to the mediation by the environment: 1) the cost of the update process is not taken into account when the context is computed by the agents; 2) the agents are interested by more than half the messages. Nevertheless we can see that there are few cases in which the use of the environment is more costly than the local matching according to the number of messages criteria.

The function Cost M (n m , f req a ) = 0 enables to find the number of messages dedicated to the interaction in the MAS (m) that have to be mediated by the environment to compensate the cost of the update process ( f req a ). The relation between these two parameters is n m = -(n a /(1 + n a (1p r ))) * f req a , the value of n m is therefore inversely proportional to the proportion of the agents interested in the messages. Figure 2 illustrates this proposition. The environment area represents the cases where it is better to use the environment than to mediate the messages in function of the number of messages. For instance, with f req a = 2, if there is more than 5 messages related to the interaction in the MAS, then it is better to use the environment to mediate the communication even if that means that there are f req a n a = 200 messages related to the update process.

This study has been done in the worst case for the environment because the agents are not taken into account to evaluate the interaction context ( f c ). If it were the case, there would be no modification of the update cost of the environment. However, when the matching is executed by agents, the number of messages in the update process would be increased by f req a (n a -1) (the cost of broadcasting the description updates), thus improving the comparative environment performance.

In this section the assessment has been done with the hypothesis that the agents have the same information to evaluate a filter. In the next section, we depict how these results relate to real experimentation where this hypothesis is not valid.

Empirical assessment

In section 4, we have shown that using the environment to compute the contexts is less costly than computing them locally in the agents when the agents update frequency is not too high. In other words, the entities dynamics is the parameter that determines which solution is the best for a multi-agent system. This section consists in evaluating the cost of the context computing on a real example that is a simulation of the victim evacuation in the crisis situation. The simulation run-time results aggregate the previous calculations.

A prototype of our ABS framework has been implemented as a plugin for the multi-agent platform Madkit [START_REF] Gutknecht | The madkit agent platform architecture[END_REF]. This plugin is composed of an environment component with an API that enables the agents to add/retract/modify their descriptions and filters. We have chosen to implement the matching process within a Rules-Based System (RBS). The instantiation of the model into a RBS is straightforward: the descriptions are the facts of the rule engine, and the filters are its rules. Rule firing is based on the efficient RETE algorithm [START_REF] Forgy | Rete : A fast algorithm for the many pattern/many object pattern match problem[END_REF]. It is a network-based algorithm designed to speed the matching of patterns with data. RETE uses a static discrimination network, generated by the language compiler, that represents data dependencies between rule conditions. We compare our model which encompasses contextual activation by the environment with a model which encompasses a classical activation process to evaluate the cost of supporting the simulation process through the environment. We have tested two simulation scenarios, without and with communication, using ten filters: seven filters for contextual activation ( f 1 to f 7 ), two filters for communication ( f recept and f accept ) and one filter for classical activation f classicalactivation . Except for the filter f classicalactivation , each activation filter allows to activate an agent medical porter in a specific context to perform an action. The filter f classicalactivation is used in the scenarios S 1 and S 3 in order to simulate a classical activation process. This filter activates each agent once by simulation cycle. It does not take into account the context.

The scenarios are defined below. S 1 and S 2 are scenarios without inter-agent communication, and S 3 and S 4 are scenarios with inter-agent communication:

• -S 1 -{ f classical activation } + Local Agent Context Analysis (LACA), • -S 2 -{ f 1 , f 2 , f 3 , f 4 , f 5 }, • -S 3 -{ f classical activation } + LACA + Broadcast, • -S 4 -{ f 1 , f 2 , f 3 , f 4 , f 5 , f 6 , f 7 } + { f recept , f accept }
S 1 illustrates a classical scenario with an activation phase and a local agent context analysis; S 2 is a scenario with a contextual activation inside the environment. We describe the filters of S 2 . The filter f 1 allows to activate the action move randomly that is triggered when a medical porter has no victim next to it (context victim seeking). The filters f 2 and f 3 correspond to the association of the action move towards a location with the contexts closest victim discovery ( f 2 ) and handled victim discovery ( f 3 ). The context closest victim discovery happens when an agent perceives the closest victim to evacuate in its perception field. The context closest victim discovery depicts the situation where an agent medical porter perceives a victim that is handled by another medical porter. The filter f 4 activates the action wait and triggers when a medical porter is alone close to a victim to evacuate (context victim proximity). The filter f 5 corresponds to the association between the action evacuate victim and the context rescue victim. This context appears when two medical porters with the complementary skill are close to a victim ready to be evacuated. This context is related to the following information: the availability of the porters, the location of the porter and the victim. The comparison between S 1 and S 2 enables to study the cost of the activation process.

S 3 and S 4 are the extensions of respectively the scenarios S 1 and S 2 with the communication filters f recept and f accept , and the associated activation filters f 6 and f 7 . The filters f recept and f accept provide the support for the communication process: f recept enables the reception of the request messages and f accept enables the reception of their answer(s). When the agents communicate, the simulation has to manage two new agent actions that are activated by the filters f 6 and f 7 . The filter f 6 is related to the action contact: an agent puts a request message in the environment and waits for an answer. The filter is activated when the agent is close to a victim to evacuate but does not have another agent nearby to evacuate this victim. The filter f 7 is related to the action coordination: an agent answers to the contact agent and moves towards the victim location. The context of this filter is the reception of a request message containing the location of the victim. The comparison between S 3 and S 4 enables to study the cost of the activation when the medical porters use communication protocol to contact another medical porter with the skill required.

Activation. We have run three series of simulations characterized by two parameters: number of agents medical porters and field of vision. For each series of simulations, we evaluate our model using the average run-time over 50 simulations with similar parameters. In the first group, we have experimented with 5 medical porters with the skill "health monitoring", 5 medical porters with the skill "victim handling" and 5 victims, in the second group with 15 of each, and in the third group with 20 of each.

Figure 3 shows the result for the third experiment. As we can see, the scenario S 2 is faster than the classical scenario S 1 , except for the lowest field of vision. For a field of vision from 8 to 30, S 2 run-time curves (dotted curves) are below S 1 run-time curves (solid curves). The increase of the field of vision improves the knowledge of the agents on the environment and should improve their efficiency: the probability for an agent to perceive victims and other agents increases. This is true with the use of the environment in the scenario S 2 , a larger field improves the efficiency of the agents: as the field of vision increases from 5 to 30, run-time decreases from around 4000s to 800s. But with the classical activation process in the scenario S 1 , the improvement of victim perception barely offsets the cost of local context analysis. We can observe that in most cases, the cost of the context computing in each agent is more expensive in terms of simulation run-time than the cost of computing the context inside the environment. The results are similar for the Communication. In the following experimentation, we compare the use of broadcast and the use of the environment for the communication. In these tests, only the communication filters f recept and f accept of the scenario S 4 are evaluated and compared to the broadcast of the scenario S 3 . The message exchange to find partners has been instantiated: • The agents send "request" messages. The agents interested in these messages are those which are close to the sender and have a different skill, if the victim can be moved. In scenario S 3 , the message is broadcasted to all the agents, while in S 4 , they are managed by f recept .

• Those agents answer with either an accept or a reject message through an addressed message. In scenario S 3 , the message is sent to the agent via point-to-point communication, while in S 4 , they are managed by f accept .

Each data is an average on 50 simulations. Each simulation is composed of 2000 steps. We have run two series of simulations characterized by two parameters: number of agents and number of updates during the simulation.

Firstly, we have tried to use the RETE algorithm to implement the communication filter, and compared it to the broadcast and addressed messaging capabilities of MadKit. The following table sums up the simulation run-time in function of the messaging implementation: EASI with a RETE tree, MadKit Messaging support, ad hoc Environment and Broadcast. These results show that the cost of a RETE tree offsets the gains in the message treatment. This discrepancy with the previous results for activation can be explained by the cost of the addition and removal of the messages. In the activation part, the entities are the same all along the simulation, and only rule firing and description modifications take place. This has lead us to use an ad hoc implementation of the environment for communication, which treats the calculations in the same way as described in section 4. However, the comparative results show that the MadKit implementation of the broadcast and addressed messaging is not efficient because of its genericity. Therefore, we also re-implemented the broadcast and point-to-point communications using the same data structures as the environment, in order to have a fair comparison between the environment and the broadcast solutions.

In the following, we compare the two last solutions. Firstly, we study the impact of a variation in the number of agents. The results shown in Fig. 5 feature 10 to 100 agents. The curve shows a clear advantage of the environment over the broadcast, and that the more agents there are, the more EASI is comparatively interesting (from 27.8% for 10 agents to 53.9% for 100 agents). In the second phase (Fig. 5),we study the impact of a variation in the number of updates, for 50 agents. During each update, all the agents move and in the case of the Environment implementation, they modify their description accordingly. The run-time gain of EASI over broadcast gets from 50.7% for 20 updates to 48.8% for 1000 updates. Therefore, the cost of the update mechanism is not significant in comparison with the difference in efficiency.

These experimentations show a clear advantage to the environment over the broadcast, and this result is

Discussion and conclusion

In the EASI/EASS models, the environment offers a technical support for communication and activation. Its processing is the result of the filters triggering according to the MAS descriptions. In that way, the agents add or remove dynamically filters and update their description. Thanks to the filter triggering, an agent receives a message or is activated in a specific context. The processing of the messages and the action execution remain to the agents responsibility.

This paper is focused on the cost of the centralization, which is closely related to the cost of the update process. Organizations, such as the agent-group-role model [START_REF] Ferber | Organization models and behavioural requirements specification for multi-agent systems[END_REF] enable to decrease the cost but do not take into account ambient criteria like the location of the agents (e.g. in the simulation). Let us note that our modeling enables to reproduce a selection of percepts according to the organisation. Institutions (see e.g. [START_REF] Esteva | Ameli: An agent-based middleware for electronic institutions[END_REF])) generally do not share the same objective. The focus is on control and not on the filtering / matchmaking. However, the technical solutions may be close to ours.

The use of a shared knowledge has already been done within agents (for example Sycaras work, e.g. [START_REF] Sycara | A taxonomy of middleagents for the internet[END_REF]) but in that case the update of the properties is not considered. In this paper, we focus on the cost of the update process that could limit the interest to centralize specific information. Furthermore, middle-agents are generally used only as a first step to find contacts, and not to manage all the communications. In our view, the environment is a facility, which can be used to facilitate the interaction, apply norms, or verify some rules related to the application design. These roles do not belong to the same design level as the agents.

Theoretically, we have shown that if the communication takes the context into account, there is no strictly dominant solution. It depends on the dynamicity of the multi-agent system, the number of agents and the average percentage of agents interested in each message. According to the number of tests criteria, we have shown that the environment is always better than the local context computation. According to the number of messages criteria, the result has to take into account the number of messages related to the MAS activity and the number of messages related to the update process. We have shown that the environment solution is generally better to mediate the communication of the MAS activity and that few messages to mediate are needed to compensate the cost of the update process.

To propose an empirical assessment of the cost of the environment, we have studied the run-time criterion in the crisis simulation example. We compare the cost of the local context analysis for each agent to a central and global control ensured by the environment, and the cost of communication. The main conclusion is that the environment cost is significantly lower than the local agent calculation of the context perception, except when there are very few agents.

In the future, we intend to investigate different ways to improve the environment performance. An ongoing effort concerns the theoretical evaluation of a RETE-based instantiation of the model. We also study how to take advantage of the filter and entity structures to speed up the matching process.

Figure 1 :

 1 Figure 1: Comparison of the cost with p r = 0.6 and n a = 100

Figure 2 :

 2 Figure 2: Comparison of the number of messages in function of the agent update frequency with p r = 0.6 and n a = 100

Figure 3 :

 3 Figure 3: Simulation run-time with the strategies S 1 and S 2 for the third group

Figure 4 :

 4 Figure 4: Comparative results of Broadcast and EASI in function of the number of agents

Figure 5 :

 5 Figure 5: Comparative results of Broadcast and EASI in function of the number of description updates

table sums

 sums

	up the properties of the MAS components
	descriptions:
	property	Medical porter Message Victim
	id	x	x	x
	location	x	x	x
	availability	x
	vision	x
	time	x	x
	skill	x	x
	id sender		x
	type		x
	id v		x
	status			x
	diagnosed			x

http://education.mit.edu/starlogo/


Denis Cornaz

Lucie Galand

Olivier Spanjaard

Bounded single-peaked width and proportional representation 1

. We define clustered single-peakedness as a form of singlepeakedness with respect to clusters of candidates, i.e. subsets of candidates that are consecutive (in arbitrary order) in the preferences of all voters. We show that the PR problem becomes polynomial when the size of the largest cluster of candidates (width) is bounded. Furthermore, we establish the polynomiality of determining the single-peaked width of a preference profile (minimum width for a partition of candidates into clusters compatible with clustered singlepeakedness) when the preferences are narcissistic (i.e., every candidate is the most preferred one for some voter).

Introduction

Social choice theory deals with making collective choices on the basis of the individual preference relations of a set of agents (or voters) over a set of alternatives (or candidates). In this field, an active stream of research deals with "multi-winner" elections, where one aims at electing a subset of candidates rather than a single candidate. This occurs for instance when electing an assembly. In such situation, a combinatorial difficulty arises: while there are only m possible outputs of a singlewinner election with m candidates, there are m κ possible assemblies of κ representatives. This difficulty is often overcome by organizing κ single-winner elections over κ subelectorates. With this way of partitioning the election, it may nevertheless happen that the elected assembly fails to represent minorities [START_REF] Betzler | On the computation of fully proportional representation[END_REF]: assume that the representatives of a party are in second position for the κ single-winner elections, then the party will have no representative in the assembly. Proportional representation aims at tackling this issue by performing a single multi-winner election ensuring that collectively the voters are satisfied enough by at least one elected candidate. This can be achieved for instance by using Chamberlin and Courant's scheme [START_REF] Chamberlin | Representative deliberations and representative decisions: Proportional representation and the Borda rule[END_REF], where one elects a subset of κ candidates minimizing a misrepresentation score. The effective computation of such winning subsets of candidates has been studied by several authors. Procaccia et al. have shown that the problem is NP-hard in the general case, but polynomial for a fixed κ [START_REF] Procaccia | On the complexity of achieving proportional representation[END_REF]. Lu and Boutilier provided a polynomial approximation algorithm with performance guarantee (for maximizing a representation score), and show, on different experimental datasets, that it almost always returns an optimal solution [START_REF] Lu | Budgeted social choice: From consensus to personalized decision making[END_REF]. Their setting is nevertheless different from proportional representation in political science: they aim at designing a system able to recommend a set of options to a group, based on the individual preferences of its members. Such a system could be used for instance by a conference organizer wishing to select a subset of sushis for the gala dinner, based on the individual preferences of the participants over the varieties of sushis. Clearly, this context authorizes suboptimality. Coming back to voting procedures, it is nevertheless important to note that the scores only provide an ordinal information: if an assembly A has a misrepresentation score 1 while an assembly B has a misrepresentation score 1 + ε, one can only conclude that A is better than B, and not that B is close to be as good as A. Furthermore, in a political setting, it is simply not possible to elect an assembly without guaranteeing that it is the true winner. To our knowledge, the only general exact approaches proposed for proportional representation in Chamberlin and Courant's scheme are based on integer programming as the ones by Potthoff and Brams [START_REF] Potthoff | Proportional representation: broadening the options[END_REF] and by Balinski [START_REF] Balinski | On finding integer solutions to linear programs[END_REF] (in this latter reference, the formulation was actually proposed for the κ-median location problem, which is equivalent to the proportional representation problem [START_REF] Procaccia | On the complexity of achieving proportional representation[END_REF]). The solution of these IP formulations might of course take exponential time in the worst case.

Very recently, Betzler et al. proposed an extensive investigation of parameterized complexity results for the problem [START_REF] Betzler | On the computation of fully proportional representation[END_REF]. Besides, they established that the problem becomes polynomial when the preferences are single-peaked [START_REF] Black | The Theory of Committees and Elections[END_REF]. Single-peakedness is the most popular domain restriction in social choice theory. In single-winner elections, it makes it possible to overcome Arrow's impossibility theorem (that states that no voting rule can simultaneously fulfill a set of basic axioms). In particular, there always exists a Condorcet winner (i.e., a candidate who is preferred to any other candidate by a majority of voters) if preferences are single-peaked. Such preferences are typically encountered in political science. Intuitively, preferences are single-peaked when 1) all voters agree on a left-right axis on the candidates reflecting their political convictions, and 2) the preferences of all voters decrease along the axis when moving away from their preferred candidate to the right or left. Nevertheless, this condition on preferences can be a bit restrictive when several candidates share similar opinions (e.g. they belong to the same party) since it is unlikely that the preferences of all voters are single-peaked on this subset of candidates.

We therefore study a new domain restriction, clustered single-peakedness, where singlepeakedness holds on subsets of candidates (parties or more generally clusters), and not within clusters. The candidates belonging to the same cluster are ranked consecutively in the preferences of all voters, though not necessarily in the same order. Given a partition of the candidates into clusters such that the preferences are clustered single-peaked, the width of the partition is the size of the largest cluster minus one. Note that, for a given set of individual preference relations, several partitions into clusters can be compatible with clustered single-peakedness: we call single-peaked width the minimum width among all possible partitions of candidates into clusters. We show that the single-peaked width is computable in polynomial time if preferences are narcissistic, and that a bounded single-peaked width makes it possible to design a polynomial time solution algorithm for the proportional representation problem. Note that the same structures have been studied by Elkind et al. [START_REF] Elkind | Clone structures in voters' preferences[END_REF], under another terminology (in particular, clusters are called clone sets). Their main concern is not to study how clustered single-peakedness can be used to determine the winner of an election, but they show interesting connections with PQ-trees, and use them to design an algorithm to compute a partition of the candidates into (as many as possible) clusters. The links between their work and ours will be detailed in Section 4.

The paper is organized as follows. We first formally introduce the proportional representation problem and clustered single-peakedness (Sect. 2). Then we present a dynamic programming procedure for solving the proportional representation problem when the preferences are clustered single-peaked (Sect. 3). A key parameter for the efficiency of the procedure is the width of the partition into clusters. We therefore study the complexity of determining the single-peaked width of a set of individual preference relations (Sect. 4), and show the polynomiality of the problem for narcissistic preferences.

Preliminaries

Proportional representation

Let V be a set of n voters and C a set of m candidates. Let P be an m × n preference profile matrix over C, that is, each candidate appears exactly once in each column. So the set of columns of P is the set V and each column v is the preference relation of voter v. We denote by r(v, c) the rank of candidate c in the preferences of voter v, and by x ≺ v y the preference for y over x. A non-decreasing misrepresentation function µ : {1, . . . , m} → N is defined such that µ(r(v, c)) is the misrepresentation value of c for v. The proportional representation problem aims at determining a subset S ⊆ C of κ candidates such that the total misrepresentation score is minimized. In Chamberlin and Courant's scheme, the scoring function s : 2 C → N is defined as follows:

s(S) = v∈V min c∈S µ(r(v, c))
The proportional representation problem can then be simply written: min |S|=κ s(S). The following example illustrates the value of using Chamberlin and Courant's scheme. The optimal solution is subset ac with score 1. With such a solution, only one voter is not represented by her preferred candidate (but by her second choice). Assume now this multi-winner election is divided into two single-winner elections, namely an election L between b and c for voters 1, 2, 3, and an election R between a and d for voters 4, 5, 6. The winner of election L (resp. R) is b (resp. d). Consequently, the winning solution is bd, which is the worst one according to the misrepresentation scores!

Clustered single-peakedness

Definition 1. Let C = (C 1 , . . . , C q ) be an ordered partition of C into q non-empty subsets (called clusters). Preference profile matrix P is clustered single-peaked with respect to C if for all v ∈ V there exists an index p in {1, . . . , q} such that:

i < j < p ⇒ x ≺ v y ≺ v z p < j < i ⇒ x ≺ v y ≺ v z for all x ∈ C i , y ∈ C j and z ∈ C p .
For a voter v, we call C p the peak of v, which means that any candidate in C p is preferred to any candidate in C \ C p . This definition coincides with usual single-peakedness when |C i | = 1 for all i. The only candidate in C p is then the most preferred one.

Example 2. Coming back to Example 1, it can be easily seen that the preferences are not singlepeaked w.r.t. axis (a, b, c, d), by considering Figure 1 where each curve represents a preference ranking of a voter, namely voters 1, 2, 6. For each curve and each candidate on the X-axis, the value on the Y-axis is the rank in the corresponding preference ranking (the better the rank the higher the point). Preferences are single-peaked w.r.t. an X-axis iff all curves have a single peak. This is not the case in the left graph since the curve of voter 6 (in bold) spikes down for b and then spikes up for a. More generally, it can be shown that the preferences in Example 1 are not single-peaked, whatever permutation of candidates on the X-axis is considered. However, the preferences are clustered single-peaked with respect to ({a, b}, {c}, {d}), denoted by (ab, c, d) for simplicity. Note that a and b are adjacent in all preference rankings, which is a necessary condition to be clustered (but not sufficient for clustered single-peakedness!). A preference profile is clustered single-peaked with respect to an ordered partition (C 1 , . . . , C q ) iff it is single-peaked when considering each subset C i as a single candidate. In the example, introducing cluster {a, b} amounts to considering a and b as a "single candidate" ab. The preference profile matrix becomes then the one indicated on the right-hand side of Figure 1. In the graph on the right, one can observe that the preferences become then single-peaked, i.e. they are clustered single-peaked with respect to (ab, c, d).

    § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ a c a c

Dynamic Programming

We now present a dynamic programming algorithm that generalizes the one proposed by Betzler et al. for single-peaked preferences [START_REF] Betzler | On the computation of fully proportional representation[END_REF]. Let P (i, C , k) denote the subproblem where all candidates in C ⊆ C are made mandatory and one selects k

-|C | candidates in C 1 ∪ . . . ∪ C i .
For the convenience of the reader, we briefly recall the recursion scheme of the procedure proposed by Betzler et al., with an alternative proof. Assume that the preferences are single-peaked with respect to axis (x 1 , . . . , x m ) (i.e. clustered single-peaked with respect to (C 1 , . . . , C m ), where C i = {x i } ∀i). Let z(i, k) denote the optimal score for problem P (i -1, {x i }, k), where one selects x i and k -1 candidates among {x 1 , . . . , x i-1 } (the i -1 leftmost candidates on the axis). The authors use the following recursion:

z(i, k) = min j∈[k-1••i-1] z(j, k -1) - v∈V max{0, µ(r(v, x j )) -µ(r(v, x i ))}
The optimal score for a subset of κ candidates is then min i∈{κ••m} z(i, κ). The validity of the recursion can be established by showing that selecting a subset of k candidates, including x j and x i (mandatory candidates), in {x 1 , . . . , x j , x i } (problem P (j -1, {x j , x i }, k)) amounts to selecting k -1 candidates, including x j , in {x 1 , . . . , x j } (problem P (j -1, {x j }, k -1)). Indeed, it reduces to computations on the same minor of the preference profile. Definition 2. Any preference profile matrix that depicts the individual preferences of a subset V ⊆ V of voters over a subset C ⊆ C of candidates is called a minor and denoted by P(V , C ).

The voters can be partitioned into two sets: the set V [1,j-1] of voters whose peak x p is in {x 1 , . . . , x j-1 }, and the set V [j,m] of voters whose peak x p is in {x j , . . . , x m }. Both problems P (j -1, {x j , x i }, k) and P (j -1, {x j }, k -1) amount to computations in the same minor:

• Problem P (j -1, {x j , x i }, k): all voters in V [j,m]
can be deleted from the preference profile matrix since their preferred candidate among {x 1 , . . . , x j , x i } is either x i or x j , that are mandatory, and therefore the preferences of these voters play no role in the determination of the optimal solution to P (j -1, {x j , x i }, k). Furthermore, all voters in V [1,j-1] prefer x j to x i since their peak is to the left of x j , and therefore candidate x i plays no role since x j is mandatory. Consequently, the problem reduces to selecting k -1 candidates, including x j , according to minor P(V [1,j-1] , {x 1 , . . . , x j }).

• Problem P (j -1, {x j }, k -1): for all voters in V [j,m] , candidate x j is necessarily the most preferred one in {x 1 , . . . , x j }. Since candidate x j is mandatory, all voters in V [j,m] can be deleted from the preference profile matrix. The problem reduces then to selecting k -1 candidates, including x j , according to minor P(V [1,j-1] , {x 1 , . . . , x j }).

The two problems P (j -1, {x j , x i }, k) and P (j -1, {x j }, k -1) are thus equivalent, which establishes the validity of the recursion. We now show how this recursion scheme can be extended to handle clustered single-peaked preferences. Assume that the preferences are clustered singlepeaked with respect to an ordered partition (C 1 , . . . , C q ). Let z(i, C i , k) denote the optimal score when candidates in C i ⊆ C i are mandatory, candidates in C i \ C i are forbidden, and one selects k

-|C i | candidates in C 1 ∪ . . . ∪ C i-1 .
In our setting, the recursion can be written as follows:

z(i, C i , k) = min j∈[1••i-1] min C j ⊆Cj C j =∅ z(j, C j , k -|C i |) - v∈V max{0, min y∈C j µ(r(v, y)) -min x∈C i µ(r(v, x))} (1)
where

z(i, C i , k) = +∞ if |C i | > k or |C 1 ∪ . . . ∪ C i-1 | < k -|C i |.
The optimal score for a subset of κ candidates is then:

min i∈[1••q] min C i ⊆Ci C i =∅ z(i, C i , κ)
The proof of the recursion is similar to the one in the single-peaked case. It amounts to establishing the equivalence of problems

P (j -1, C j ∪ C i , k) and P (j -1, C j , k -|C i |), by considering a partition of V into the set V [1,j-1] of voters whose peak is in {C 1 , . . . , C j-1 } and the set V [j,q]
whose peak is in {C j , . . . , C q }:

• Problem P (j -1, C j ∪ C i , k): all voters in V [j,q
] can be deleted from the preference profile matrix since their preferred candidate among

C 1 ∪ . . . ∪ C j-1 ∪ C j ∪ C i is either in C i or in C j . All voters V [1,j-1]
prefer a candidate in C j to a candidate in C i since their peak is to the left of C j .

Consequently, the problem reduces to selecting k -|C i | candidates, including candidates in C j , according to minor

P(V [1,j-1] , C 1 ∪ . . . ∪ C j-1 ∪ C j ).
• Problem P (j -1, C j , k -|C i |): for all voters in V [j,q] , the most preferred candidate in C 1 ∪ . . . ∪ C j-1 ∪C j necessarily belongs to C j . The voters can therefore be deleted from the preference profile.

The problem reduces then to selecting k -|C i | candidates, including candidates in C j , according to minor

P(V [1,j-1] , C 1 ∪ . . . ∪ C j-1 ∪ C j ).
Both problems are thus equivalent, which establishes the validity of the recursion. Algorithm 1 describes the ensuing dynamic programming procedure.

Algorithm 1: Dynamic programming

for i = 1, . . . , q do for C i ⊆ C i with |C i | ≤ κ, C i = ∅ do z(i, C i , |C i |) = v∈V min x∈C i µ(r(v, x)) for i = 2, . . . , q do for C i ⊆ C i with |C i | ≤ κ, C i = ∅ do for k = |C i | + 1, . . . , min{κ, |C i | + i-1 j=1 |C j |} do compute z(i, C i , k) by Equation 1 return min i∈[1••q] min C i ⊆Ci, C i =∅ z(i, C i , κ)
Example 3. For simplicity, a set {a, b} is denoted by ab in this example, and {a, b} ∪ {c, d} by abcd. Consider a proportional representation problem with 6 candidates a, b, c, d, e, f having clustered single-peaked preferences with respect to (ab, cd, e, f ). Let us study how many triples of candidates are examined by the procedure when computing z(4, f, 3). Given r subsets S 1 , . . . , S r of candidates, let us denote by opt{S 1 , . . . , S r } a subset in arg min i s(S i ). The following computation is performed by the procedure: z(4, f, 3) = s opt f ab, f opt{ca, cb}, f opt{da, db}, f cd, f opt{ea, eb, ec, ed} Therefore 5 subsets are examined (three of the four "opt" operations have been performed during the previous iterations) while there are 10 subsets of cardinality 3 including f .

For a small single-peaked width, the computational savings become of course more and more significant when the size of the instance increases. Actually, the following complexity analysis shows that the dynamic programming procedure is polynomial for a bounded singe peaked width. Equation 1 requires indeed a computational time within O(nqt2 t ) where t = max i |C i |-1. Furthermore, the number of computed terms z(i, C i , k) is upper bounded by q2 t κ. Therefore the running time of the procedure is within O(nq 2 t2 2t κ), which amounts to O(nm 3 ) for a bounded singlepeaked width t (we recall that q ≤ m and κ ≤ m).

Theorem 1. The proportional representation problem over bounded single-peaked width preferences is polynomial.

The complexity analysis shows that max i |C i | is a key parameter for the efficiency of the algorithm. Note that there always exists an ordered partition for which the preferences are clustered single-peaked: in the worst case, it is sufficient to consider the partition (C). It is nevertheless interesting from an algorithmic viewpoint to have an ordered partition where each subset includes few candidates. Two cases can occur: either the partition is known in advance (for instance, when the candidates indicate their affiliation to a political party and the preferences of the voters are consistent with the displayed affiliations) or it is unknown. In both cases, it is desirable to be able to compute an ordered partition compatible with clustered single-peakedness and such that max i |C i | is minimized. In the next section, we show the polynomiality of this problem for narcissistic preferences [START_REF] Bartholdi | Stable matching with preferences derived from a psychological model[END_REF][START_REF] Trick | Recognizing single-peaked preferences on a tree[END_REF].

Single peaked width

We call width of an ordered partition (C 1 , . . . , C q ) the value max i |C i | -1. Given a preference profile matrix, we call single-peaked width the minimum width among all ordered partitions compatible with clustered single-peakedness. This can be seen as a distance measuring near-single-peakedness (the single-peaked width is indeed equal to 0 for single-peaked preferences). Note that this should not be confused with other distance measures that have been proposed in the literature, such as the number of voters to remove to make a profile single-peaked [START_REF] Faliszewski | The complexity of manipulative attacks in nearly single-peaked electorates[END_REF].

Example 4. Consider the preference profile matrix P represented in Figure 2, where the preferences are not single-peaked. It is easy to check that they are nevertheless clustered single-peaked with respect to ordered partition (ac, ef g, bd, h) (see the left part of the figure, where the subsets of the partition are encircled), whose width is |{e, f, g}| -1 = 2. However the preferences are also clustered single-peaked with respect to (ac, f, eg, b, d, h) (right part of the figure). The singlepeaked width of this preference matrix is thus 1. [START_REF] Ballester | A characterization of the single-peaked domain[END_REF] recently showed that single-peakedness can be lost just because of the existence of two voters and four candidates, or three voters and three candidates. Conversely, they showed that if a profile is not single-peaked there must exist a set of two voters (resp. three) whose preferences over four candidates (resp. three) are not single-peaked. More precisely, the authors characterize single-peakedness with the following two conditions: • Worst-restriction: Given a triple V ⊆ V of voters and a triple C ⊆ C of candidates, let L(V , C ) be the set of all candidates ranked last in C by at least one voter in V . The worst-restriction condition holds if |L(V , C )| < 3 for all triples V and C .

Ballester and Haeringer

P =             § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ f b c g d a e h f c g e a e g b f b d a d h c h             P =             § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ § ¦ ¤ ¥ f b c g d a e h f c g e a e g b f b d a d h c h            
• α-restriction: the α-restriction condition holds if there do not exist two voters v and v and four candidates w, x, y, and z such that their preferences over w, x and z are opposite (w v x v z and z v x v w) and the voters agree about the preference for y over x (y v x and y v x).

Interestingly, these conditions amount to forbidding five minors in the profile P (Lemma 1). In this formalism, we propose here a shorter proof of the characterization result of Ballester and Haeringer. Our proof is based on the polynomial algorithm proposed by Escoffier et al. [START_REF] Escoffier | Single-peaked consistency and its complexity[END_REF] to determine if a profile is single-peaked with respect to some axis. This algorithm runs in time O(mn) improving on the O(mn 2 ) algorithm proposed by Bartholdi and Trick [3]. Before stating Lemma 1, let us present the algorithm of Escoffier et al. It works recursively and takes as arguments the left part (x 1 , . . . , x i ) and the right part (x j , . . . , x m ) of the axis under construction. A third argument is the subset C of candidates which remains to be positioned on the axis. This algorithm returns an axis compatible with P or proves that the preferences are not single-peaked (by raising a contradiction between voters). The recursion is made possible by the fact that single-peakedness over P implies single-peakedness over any of its minors. It heavily uses the property that candidates ranked last in the preferences are necessarily at the extremities of the axis. At each step of the algorithm, one candidate x or two candidates x and y are ranked last in P(V, C ) and will be positioned in x i+1 or x j-1 on the axis. There is a contradiction if a candidate has to be placed in two different positions (according to the preferences of two voters). These positions depend on the way x and y are positioned with respect to x i and x j in the preferences of all the voters. The whole procedure is detailed in Algorithm 2. The initial call is Make-axis(C, (), ()).

Before presenting Lemma 1 (on which our algorithm to compute single-peaked width strongly relies), we need to introduce the notion of isomorphic minors. A minor P is isomorphic to P if there exists a bijection φ such that P and P are identical up to column permutation if one renames every candidate x in P as φ(x). For instance, preference profile matrix P below is isomorphic to P (take φ(a) = b, φ(b) = c, φ(c) = a and permute the columns).

P =   a c b a c b   , P =   a b b c c a   Definition 3.
A minor is called forbidden if it is isomorphic to one of the following profiles:

T1 =   a b c b c a c a b   ,T2 =   a c a b b c c a b   , F1 =     a c d d b b c a     , F2 =     a d d c b b c a     , or F3 =     d d a c b b c a     .
Lemma 1. P is single-peaked iff it has no forbidden minor.

Proof (sketch) Necessity: it suffices to check that none of the five forbidden minors is singlepeaked, since the single-peakedness property is closed under taking minors. Sufficiency: run Algorithm 2 and suppose that it returns not single-peaked. If it stops at Line 5, then P has a minor T 1 or T 2 . Otherwise it stops at Line 10 or 13 and P has a minor F 1 , F 2 or F 3 .

The rest of the section is devoted to the problem of determining an ordered partition of minimum width among the ones that are compatible with clustered single-peakedness. Note that Elkind et al. [START_REF] Elkind | Clone structures in voters' preferences[END_REF] studied a closely related problem, namely finding an ordered partition (C 1 , . . . , C q ) maximizing q. Both problems are not equivalent, as shown by the following example.

Example 5. Consider the preference profile matrix P:

P =           d d x a y v c b b c a x v y          
Both partitions (abcv, d, x, y) and (v, a, d, bcxy) maximize q and are compatible with clustered single-peakedness, but (abv, d, cxy) is the only partition that minimizes the single-peaked width.

However, for narcissistic preferences [START_REF] Bartholdi | Stable matching with preferences derived from a psychological model[END_REF][START_REF] Trick | Recognizing single-peaked preferences on a tree[END_REF], one can show that the algorithm proposed by Elkind et al. for their problem returns an ordered partition of minimum width. Nevertheless, our approach proves that there is a unique (up to reversal) ordered partition maximizing q. Preferences are said to be narcissistic when each candidate is most preferred by some voter. In politics, as soon as the candidates are voting, this assumption seems reasonable. In the remainder, we prove the following result: . This definition coincides with the notion of clone set studied by Elkind et al. [START_REF] Elkind | Clone structures in voters' preferences[END_REF]. Notice that the set of intervals I of P is not closed under taking subsets. Nevertheless, it is closed under intersection [START_REF] Elkind | Clone structures in voters' preferences[END_REF]. Given a, b ∈ C, the minimal interval w.r.t. inclusion that contains a and b is thus uniquely defined: we denote it by I(a, b). The following lemma will prove useful in order to design an algorithm able to compute a partition compatible with clustered single-peakedness. For simplicity, if P is isomorphic to P for φ, we write I(x, y) for I(φ(x), φ(y)). Notice that the preference profile matrix P obtained by contracting an interval of P is a minor of P. Note also that if I, J ∈ I are two intervals of P, then the two minors obtained from P either by contracting I then J, or by contracting J then I coincide (even if I and J overlap). Besides, if P is a minor of P and F is a minor of P , then F is also a minor of P. The greedy procedure is detailed in Algorithm 3. The termination follows from the fact that contracting candidates cannot create new forbidden minors.

P =         f b a e d f a h e b e b d f d h a h        
There is no more forbidden minor in the preference profile, and thus the greedy procedure stops. The clusters are {a, c} and {e, g}.

This algorithm is polynomial since the forbidden minors can be enumerated in O(m 3 n 3 ) for T 1 , T 2 , and O(m 4 n 2 ) for F 1 , F 2 , F 3 . The clusters identified by the algorithm belong to an ordered partition compatible with clustered single-peakedness. The ordered partition itself can be computed by applying Algorithm 2 on the final preference profile. Coming back to Example 6, Algorithm 2 returns axis (h, d, b, e, f, a) on P , which corresponds to the ordered partition (h, d, b, eg, f, ac) since e (resp. a) is the representative of {e, g} (resp. {a, c}). This is an ordered partition of minimum width for this profile. However, in the general case, the width of the returned ordered partition is not guaranteed to be minimal. We now show how to refine the greedy procedure to get an ordered partition of minimum width when preferences are narcissistic. To this end, we introduce a notion of similarity between candidates that enables us to identify necessary and sufficient contractions for clustered single-peakedness. Definition 4. Two candidates a and b are said to be similar if they belong to the same cluster in all ordered partitions w.r.t. which P is clustered single-peaked.

It results from Lemma 2 that the following properties hold: These properties imply that all contractions but one (F 3 ) in the greedy algorithm cover candidates which belong to the same cluster in any ordered partition of minimum width. The only case of a forbidden minor that cannot be removed from P by contracting similar candidates is thus F 3 when I(a, b) and I(b, c) intersect properly, i.e. I(a, b) ⊆ I(b, c) and I(b, c) ⊆ I(a, b). We call such forbidden minors ambiguous. If one finds an ambiguous minor M, at least two candidates in M must be in the same cluster. Nevertheless the single-peaked width of an ordered partition depends on the choice of the candidates to contract. Furthermore this choice does not only depend on the maximum number of candidates involved in the possible interval contractions. For instance, consider the preference profile matrix P of Example 5 which has the following minor:

• If T 1 (T 2 )
    d d c v b b v c    
The smallest contraction implied by the given minor would be to contract b and c (2 candidates in the interval). But (abv, d, cxy), where b and c are not in the same cluster, is the only minimum width ordered partition compatible with clustered single-peakedness.

For this reason, the greedy algorithm may fail to provide clusters belonging to an ordered partition of minimum width. However when preferences are narcissistic, no ambiguous minor can exist in the preference profile matrix. Assume indeed that there exists a minor M isomorphic to F 3 for φ. Since P is narcissistic, candidate φ(b) is the most preferred one for some voter v, and conse Furthermore, the greedy algorithm uses necessary and sufficient contractions to make the profile clustered single-peaked, and thus partition (C 1 , . . . , C q ) of minimum width is clearly unique under maximizing the number q of clusters.

Conclusion

An interesting open question is whether there exists a general polynomial algorithm to compute the single-peaked width (not necessarily in the narcissistic case). Adapting the P Q-trees based algorithm of Elkind et al. [START_REF] Elkind | Clone structures in voters' preferences[END_REF] to our problem could work. Besides, the concept of minors could be a tool for finding a short validity proof.

Example 1 .

 1 Consider a proportional representation problem with 6 voters 1, 2, 3, 4, 5, 6 (indices of the columns) and 4 candidates a, b, c, d, and the following preference profile matrix: Assume that the misrepresentation function is µ(r) = r -1. If κ = 2, then the possible subsets and scores are (for simplicity ab stands for {a, b}): ab ac ad bc bd cd 6

Figure 1 :

 1 Figure 1: Clustered single-peakedness.

Figure 2 :

 2 Figure 2: Single-peaked width.

Theorem 2 .

 2 Finding the single-peaked width is polynomial if P is narcissistic. For each voter v ∈ V and candidates a, b ∈ C we denote I v (a, b) := {c ∈ C : c = a or c = b or a v c v b or b v c v a} the set of candidates between a and b in the preferences of voter v. By convention, I v (a, a) = {a}. A subset I of C is called an interval of P if for each v ∈ V , one can choose two candidates a, b ∈ I such that I = I v (a, b)

Lemma 2 .

 2 The following properties hold:• If T 1 isa minor of P, then I(a, b) = I(a, c) = I(b, c); • If T 2 is a minor of P, then I(a, b) and I(a, c) include I(b, c); • If F 1 is a minor of P, then I(a, b), I(a, c), I(a, d), I(b, c) and I(c, d) include I(b, d); • If F 2 is a minor of P, then I(a, b), I(a, c), I(a, d), I(b, d) and I(c, d) include I(b, c); • If F 3 is a minor of P, then -I(a, c), I(a, d), I(b, d) and I(c, d) include I(a, b), -I(a, c), I(a, d), I(b, d) and I(c, d) include I(b, c). Proof (sketch) Let v be the voter of the first column of T 1 . Since b ∈ I v (a, c), it follows that b ∈ I(a, c). Thus I(a, b) and I(b, c) ⊆ I(a, c). The second column gives I(b, c) and I(a, c) ⊆ I(a, b), and the third column gives I(a, c) and I(a, b) ⊆ I(b, c). Finally I(a, b) = I(a, c) = I(b, c). The proofs for the four other forbidden minors go along the same lines.We propose a greedy algorithm to compute the clusters of an ordered partition compatible with clustered single-peakedness. This algorithm proceeds by contracting candidates so that no forbidden minor remains in the preference profile matrix. Contracting two candidates a, b ∈ C consists in contracting I(a, b). Contracting an interval I consists in collapsing all candidates in I into a single "cluster" candidate. This amounts to choosing a representative in I and removing from P all the other candidates in I. For instance, contracting b and d in P yields cluster {b, d, e} (since I(b, d) = {b, d, e}) and profile P :

Example 6 . 1 . 2 . 1 . 2 . 3 .

 612123 Consider the preference profile matrix P in Figure 2 and apply Algorithm 3, assume that it detects: Greedy algorithm let P be a minor of P isomorphic for φ to: T Contract φ(a) and φ(b) T Contract φ(b) and φ(c) F Contract φ(b) and φ(d) F Contract φ(b) and φ(c) F Contract φ(a) and φ(b), or φ(b) and φ(c) apply these contractions (non-deterministically) until no forbidden minor remains. The first minor is isomorphic to T 2 for φ(a) = g, φ(b) = a and φ(c) = c. Therefore candidates a and c are contracted. The second minor is isomorphic to F 1 for φ(a) = f , φ(b) = e, φ(c) = h and φ(d) = g. Therefore candidates e and g are contracted. Taking candidate a (resp. e) as the representative of cluster {a, c} (resp. {e, g}), the preference profile becomes:

  is a minor of P, then a and b (b and c) are similar;• If F 1 (F 2 )is a minor of P, then b and d (b and c) are similar; • If F 3 is a minor of P, then if I(b, c) ⊆ I(a, b), then b and c are similar; if I(a, b) ⊆ I(b, c), then a and b are similar.

  quently: φ(b) v φ(a) v φ(c) or φ(b) v φ(c) v φ(a). Therefore we have I(a, b) ⊆ I(b, c) or I(b, c) ⊆ I(a, b). The minor is thus unambiguous. To obtain an optimal greedy algorithm for narcissistic preferences, contraction related to F 3 must then be modified as follows: let v be a voter whose most preferred candidate is φ(b) if φ(b) v φ(a) v φ(c) then contract φ(a) and φ(b) else contract φ(b) and φ(c).

This paper appeared in the proceedings of ECAI

Acknowledgements

We wish to thank the anonymous reviewers of ECAI and COMSOC for their fruitful comments on an earlier version of the paper. This research has been supported by the ANR project ComSoc (ANR-09-BLAN-0305).

Algorithm 2: Make-axis(C ,(x 1 , . . . , x i ),(x j , . . . , x m )) if C = ∅ then return (x 1 , . . . , x i , x j , . . . , x m ) 1 if C = {x} then return (x 1 , . . . , x i , x, x j , . . . , x m ) 2 L ← candidates ranked last in P(C , V ) by at least one voter

else return not single-peaked 13 if L = {x} then 14 if x = x i+1 then Make-axis(C \ {x},(x 1 , . . . , x i , x i+1 ),(x j , . . . , x m )) 15 else Make-axis(C \ {x},(x 1 , . . . , x i ),(x j-1 , x j , . . . , x m )) 16