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

The present document is the property of COMEX SAS. It has been entrusted to the ORPHY laboratory, which scanned and uploaded it. The ORPHY laboratory focuses on major physiological functions, their regulation, interactions, and their contribution to the development and prevention of certain pathologies. The primary mechanisms studied involve metabolic aspects (oxygen transport and utilization, energetics, etc.) and electrophysiological aspects (contractility and excitability), mainly related to respiratory, vascular, and/or muscular functions. These mechanisms are studied under various physiological and physiopathological conditions, ranging from the cellular and subcellular levels to the entire organism. In Europe, the ORPHY laboratory is one of the leaders in hyperbaric physiology and diving research.

Being a major player in innovation and expertise in the field of pressure, COMEX maintains a scientific archive from its experimental diving campaigns. The value of this archive is both scientific and historical, as it documents a remarkable chapter in the history of marine exploration and contains results obtained during dives that are very unlikely to be replicated in the future.

  COMEX (Compagnie Maritime d'Expertises), established in 1962, has positioned itself in the offshore activities sector, where it held a leading international position, becoming the world's foremost company in engineering, technology, and human or robotic underwater interventions. Comex designed a Hyperbaric Testing Center in 1969 and developed its own research programs on various breathing mixtures used in deep-sea diving (helium and later hydrogen). These research efforts led to spectacular advancements in this field, including several world records, both in real conditions and simulations. Comex still holds the world record at -701 meters, achieved in its chambers during Operation HYDRA 10.


Rémy Guyonneau
email: remy.guyonneau@univ-angers.fr

Franck Mercier
email: franck.mercier@univ-angers.fr

Vincent Boucher
email: vincent.boucher@cerema.fr

Robotic system for indoor illuminance map generation

Keywords:

come

Introduction

Lighting requirements are determined by the satisfaction of three basic human needs: visual comfort, visual performance and safety. The quantifiable parameters subject to the requirements CEN (2021a) CEN (2021b) are the illuminance (amount of light arriving on a surface), its uniformity, the discomfort glare and the color rendering index. When constructing a building, the type and number of lighting elements are sized according to those lighting standards, depending on use of the site if it concerns a hospital, a warehouse, a home, etc. European standards also exist for the lighting of sports facilities [START_REF] Cen | Light and lighting -sports lighting . CEN, 2021a. Light and lighting -lighting of work places -part 1: Indoor work places[END_REF], which ensures good visual conditions for players, athletes, referees, spectators and for color TV broadcasting. The objective is to specify recommendations and requirements to produce good quality lighting for sports facilities ensuring the needs of all users. This is done by optimizing the perception of visual information used during sports events, maintaining the level of visual performance, providing acceptable visual comfort and limiting obtrusive light. Standards provide values for lighting control in terms of illuminance, uniformity, glare control and color properties of light sources. It also provides mesh-grids for measuring these values [START_REF] Cen | Light and lighting -sports lighting . CEN, 2021a. Light and lighting -lighting of work places -part 1: Indoor work places[END_REF].

To meet the standards, it is usually appropriate to carry out a control operation by measuring the illuminance. This operation is done by an operator equipped with an illuminance meter, who must perform spot measurements. The steps are

• Referencing the location of the measurement within a normative mesh-grid;

• Moving away from the illuminance meter to perform the measurement;

• Recording the measurement.

The operation must be done many times in order to achieve a relevant mesh of the area of interest [START_REF] Akashi | A field study of illuminance reduction[END_REF]. This operation is tedious and time-consuming. In practice, this operation is rarely done. Instead, installers tend to over-light to ensure compliance with standards.

The automation of controls is interesting in many ways because it could provide better suitability with the standards: the control will be actually done, the quality of the measurements will be constant and not subject to the human operations uncertainties. A better compliance with the standard could lead to:

• Improve user comfort since the standards are studied in particular with regard to this criterion;

• Save energy thanks to the readjustment of the installation lighting power. This can be easily done, for instance, with dimmed LED lights.

Evaluating lighting quality is of interest to reduce energy consumption Li (2010) Muzet, Colomb, Toinette, Gandon-Leger and Christory (2019a) Muzet, Greffier, Nicolaï, Taron and P.Verny (2019b), to predict building integrated performance [START_REF] Todorovic | Beyond the science and art of the healthy buildings daylighting dynamic control's performance prediction and validation[END_REF], to implement lighting control algorithms [START_REF] Mohammad | A review on lighting control technologies in commercial buildings, their performance and affecting factors[END_REF], [START_REF] Guillemin | An innovative lighting controller integrated in a self-adaptive building control system[END_REF], to evaluate visual comfort [START_REF] Nabil | Useful daylight illuminance: a new paradigm for assessing daylight in buildings[END_REF], [START_REF] Akashi | A field study of illuminance reduction[END_REF] or also to manage road lighting [START_REF] Kumar | Energy efficient smart outdoor lightning system using scada control system[END_REF]; [START_REF] Greffier | A grid in perspective for road lighting calculations[END_REF].

Lighting quality evaluation is then based on illuminance measurements related to spatial locations [START_REF] Carter | Field measurement of illuminance[END_REF]. For outdoor applications, those locations are generally recorded thanks to a Global Navigation Satellite System (GPS for instance) J. and Oliver (2017). But for indoor applications, this technology is no more available and an alternative has to be found. The LiDAR technology has been chosen here for its performance regarding the detection range [START_REF] Warren | Automotive lidar technology[END_REF]. To deal with the standards requirements and to acquire quickly and easily data along a specified mesh-grid, an automated illuminance acquisition system has been developed aiming to construct illuminance maps of a room.

A robot has been designed for an indoor environment. The problem of automated lighting measurement is an active research domain. Attempts are made to perform this task, but encounter localization problems Tang, Inoue, Oshio, Tsujimoto, Taniguchi and Kubota (2020) He, Wang, Zhao, Hao, Hu, Tong, Jiang and Shao (2021) [START_REF] Oshio | 2dslam of illuminance measurement robot using 3d-lidar and imu on slopes[END_REF], or demonstrate the ability to perform localized measurements in extremely controlled environments [START_REF] Drábek | Statistical-based control points selection for indoor illuminance measurement[END_REF]. The contribution of this paper is twofold:

• On the design of the platform which is very accomplished and robust in face of localization issues;

• On the expertise of the illuminance measurements by going to the end of the process with illuminance maps.

The paper is organized as follows: first the mechanical and technical specifications of the system are described, then some experiments and results are presented, and the final section concludes and draws perspectives for this approach.

Requirements, solutions and platform presentation

Objectives, constraints and environment

The objective for developing a robot is to ease the illuminance mapping of indoor environments. To that purpose the robot must:

• Acquire illuminance measurements;

• Locate those measurements in the environment.

However, indoor environments have characteristics that should be considered for robot design. Admittedly, the ground is flat and presents little disturbances (door threshold, concrete threshold bar, electric cables, etc.), but more insidious difficulties may appear (tables, chairs, structural posts, etc.) and lead to both navigation avoidance, and more complex mapping. These constraints must guide the form factor of the robot and its kinematic model for the maneuverability of the system.

The illuminance measurements are governed by standards. In order to comply with EN 12193 CEN (2018) and EN 12464 CEN (2021a[START_REF] Cen | Light and lighting -lighting of work places -part 2: Outdoor work places[END_REF] standards, the illuminance is measured by a calibrated illuminance meter. The spectral characteristics of the photo-diode make it conform to the human eye sensitivity and constitute a key point in measuring illuminance (Figure 1). Here, our illuminance meter is made of a commercial luxmeter OPT3001 associated with a diffuser dome and has been calibrated thanks to an integrating sphere. This sensor has a measurement range from 0.01 lux to 83 k lux. The illuminance meter is carried by the robot and it has been decided to place it at a maximum height of 25 cm above the floor to keep the results comparable to those made on the floor. The illuminance meter owns two integration times of 100 ms or 800 ms depending on the noise sensibility mode. Regarding to the robot velocity, the shorter integration time has been selected. According to a robot speed around 1 m/s, an illuminance measurement is integrated over 10 cm. Moreover, the sensor must not be in the shadow of any other component. The placement height in addition to shadow avoidance forces the integration of the illuminance sensor at the top of robot.

Another constraint is to leave clearance for the localization sensor (360°LiDAR). Both sensors (LiDAR and illuminance sensor) therefore have the same placement requirement: to be at the top of the robot. The proposed solution is to place the illuminance meter on top of the LiDAR at its centre. It allows an agreement at the cost of a loss of vision in a 20°cone behind the LiDAR sensor. This solution has the advantage to avoid a transformation between illuminance sensor and LiDAR localization.

Kinematic study

Kinematic with high maneuverability is useful for indoor mobility. The choice has been oriented on a 4 wheels robot, including 2 wheels with stabilizer bar (or anti-roll bar). This prevents ground irregularities and increases the stability of the robot. Moreover, due to the requirement of high maneuverability, differential kinematic appears to be a good solution. Thus, the chosen kinematic is 2 differential wheels with 2 castor wheels on stabilizer bar. This model allows higher mobility than Ackermann steering, up to rotation only [START_REF] Salem | Dynamic and kinematic models and control for differential drive mobile robots[END_REF]. To avoid additional transformation between the several frames of the system (sensors and robot's chassis), the Li-DAR and illuminance sensors are aligned with the center of rotation (CoR) of the robot.

The sensors placement is illustrated in Figure 2 while Figure 3 shows the different variables related to robot kinematics.

In the world frame, the speed of a differential robot can be represented by:

⎡ ⎢ ⎢ ⎣ ẋ ẏ θ⎤ ⎥ ⎥ ⎦ = ⎡ ⎢ ⎢ ⎣ 𝑉 cos 𝜃 𝑉 sin 𝜃 𝜔 ⎤ ⎥ ⎥ ⎦ , (1)
with (𝑥, 𝑦) 𝑇 the position of the robot, 𝜃 its orientation, 𝑉 the linear speed and 𝜔 the angular speed. In a context of differential architecture, these two speeds can be expressed as a function of wheel speed of the form:

[ 𝑉 𝜔 ] = [ 𝑅∕2 𝑅∕2 𝑅∕𝐿 -𝑅∕𝐿 ] [ 𝑣 𝑟 𝑣 𝑙 ] , (2)
with 𝑅 the radius of the wheels, 𝐿 the distance between the wheels and 𝑣 𝑟 and 𝑣 𝑙 respectively the speed of the right and left wheels in rpm.

Doing so, the Jacobian 𝐉 of the system is:

𝐉 = 𝑅 2𝐿 [ 𝐿 𝐿 2 -2 ] . ( 3
)
Depending on a linear 𝑉 and angular 𝜔 speed set-point, it is possible to compute the corresponding wheel speed using Equations 2 and 3:

[ 𝑉 𝜔 ] = 𝐉 [ 𝑣 𝑟 𝑣 𝑙 ] , ( 4
) [ 𝑣 𝑟 𝑣 𝑙 ] = 𝐉 -1 [ 𝑉 𝜔 ] = 1 2𝑅 [ 2 𝐿 2 -𝐿 ] [ 𝑉 𝜔 ] . ( 5
)
It is the relation of Equation 5that is implemented in the low level functions of the robot.

General Architecture

Figure 4 depicts the general architecture of the robot, named Romulux, the robot which measures lux. The CPU unit centralizes sensors acquisition, interface commands and controls the motors while communicating and recording all Robot Operating System (ROS) topics 1 .

For general requirement, it is wanted an autonomy of operation of one hour, which defines the size of the batteries. Indirectly the DC/DC converters take into account consumption and capability of upstream and downstream systems. Two 24V brushed DC motors are used to motorize the robot. Those have a 28:1 metal gearbox, provided by Maxon. No coder are embedded as it is assumed that the LiDAR will be used for trajectory following and steering. The couple motor/reducer is able to produce 1Nm torque and a rotation speed above 220𝑟𝑝𝑚, corresponding to a linear full speed above 3𝑚∕𝑠. The motors are controlled by Sabertooth card 2 , and communicate through serial communication with the processor, a Nvidia Jetson TX2 3 . The general architecture of the proposed solution is presented in Figure 4. The LiDAR sensor is a Velodyn Puck 4 @15Hz scanning at 360°with vertical slices between -15°and +15°and a 100m range with a typical ±3 cm accuracy. The chassis depicted in Figure 5 has been entirely designed and built to respect the maximum height of 25cm for the illuminance sensor. The maximum speed is therefore set at 3m/s with a working speed of around 1m/s.

Romulux software architecture is based on ROS Quigley, Conley, Gerkey, Faust, Foote, Leibs, Wheeler, Ng et al. (2009). ROS is based on a communication model based on nodes and topics. Nodes are autonomous processes that perform specific tasks, such as controlling a robot's motors or processing data from sensors. These nodes can communicate with each other by publishing or subscribing to topics. Topics are virtual communication channels that allow nodes to share messages asynchronously. A node can publish messages on a specific topic, while other nodes can subscribe to this topic and receive these messages. This flexible and decentralized communication architecture allows different components of a robotic system to operate independently and easily interface with each other. Thanks to the ROS architecture and specifically the twist5 data format, it is quite easy to change the remote device. For the presented experiments, a Dualsense Playstation controller has been considered. The connection between the remote controller and the robot is a Bluetooth link. The working range for this remote has been measured up to 30 m, which allows a fine control in visual range of operator without being too close from the robot and thus corrupting the illuminance data. While the robot is being controlled, all the data (LiDAR, illuminance...) are recorded into rosbag files6 . Those allow to replay the data afterward as if the robot was moving in real time. In this scenario, the illuminance map is built off-line. One of the primary experiment is depicted on the following video7 where the SLAM result has been added afterward.

According to the block diagram presented in Figure 4, each wired input/output of the CPU Unit corresponds to a node which interacts with the main node for control or acquisition. A graphical representation is given in Figure 6. Thanks to this architecture, it is quite easy to add or update sensors. The following section presents experiments and results based on that hardware/software architecture.

Experiments and results

Romulux experiment 1

The first scenario took place in a sports hall (30m long x 20m wide), where illuminance constraints are specific to this type of infrastructure. Figure 7 depicts Romulux in the experimental conditions. Different SLAM algorithms (HDL Cross comparison between algorithms. In each are the differences between the paths of the algorithms: from top to bottom the mean, the standard deviation and the maximum (in meters).

paths. In the first case, an external calibrated and accurate measurement system is required. Here we chose the second method consisting in cross comparison of different algorithms.

Results described in Figure 8 depict a maximal deviation between Lego and loam algorithms of 1.11m (at the end of the travel) with an average value of 0.71m (see Table 1).

Comparing to the width (20 m) of the hall, it represents a relative error of 3.5% which is quite acceptable and gives relative confidence in the illuminance map. This latter is constructed from the positions measured by Lego algorithm in Figure 9(a), then interpolated into a user-defined grid (every 10 cm in Figure 9)(b). For comparison, the recommended grid in the standards is made of points every 2 m. In the computed illuminance map (b), it can be seen the four lighting areas, which are consistent with on-site observations. The lights are adjustable halogens, of which this orientation was observed. The lighting level shall be at least the Class III level, that is the average horizontal illuminance (Emean) shall be over 300 lx for a uniformity (Emin/Emean) of 0.7. We found an average illuminance of 854 lx and a uniformity of 0.66. It should be noted that this uniformity was altered by obtrusive light coming from windows located on one side of the hall. A fifty percent reduction in luminous flux would help to comply with the standard thresholds and save energy.

Romulux scenario 2

This scenario took place in an international standard ice rink (see Figure 10(a)). Due to event broadcasting, it has to comply with lighting standards for television. The robot's motor skills were not affected by the ice, even though this was a concern at the outset. Figure 10(b) presents an example of recorded point-cloud. The lighting is intense and it is interesting to obtain a map of illumination to assess its homogeneity. For this ice hockey rink (namely Ice Park) at the international or national level of competition (class I), the standards recommend an average horizontal illuminance (Emean) of 750 lx and a 0.7 uniformity (Emin/Emean) . The playing area measures 60m long by 30m wide. The recommended mesh-grid defined to achieve all the measurements contain 17 points in length and 9 points in width either 153 measurement points each separated by 3.5m. These measurements are made classically with an illuminance meter placed on the ground and moved successively on the 153 points of the mesh-grid. The advantage of using an automatic measurement system is then obvious. For this experiment, an IMU has been added to the robot to improve the SLAM algorithm robustification. The IMU is a MTi-610, which is the highest standard among Inertial Measurement Units8

The robot pathway (see Figure 11(a)) has been defined to maximize the measurement points into the mesh-grid and it took around 30 minutes to acquire (half a day would have been needed if doing the measurements manually). The Figure 11(b) shows the result of the generated illuminance map. It presents a maximum of illuminance at a corner corresponding to an entry on the ice rink.The average illuminance is found to be 3607 lx (for an objective of 750 lx, demonstrating the huge over-lighting). The minimal illuminance value is 2754 lx leading to an homogeneity of 0.76 (for an objective of 0.7). Again, a 75% reduction in luminous flux would still comply with standards and save energy.

Stregths and limitations

Regarding those results, it appears that the presented robotic system can be a useful tool for illuminance mapping. It shows several advantages compared to classical processes:

• Considerable time savings comparing to manual measurement. It takes about 30 minutes to cover 1000 m² with the robotic system where at least half a day is needed manually; • As the robot performs data acquisition when moving, it provides much more measurement than doing it by hand leading to a better space discretization;

• As the robot is tele-operated (up to 30 m) it removes illuminance measurement disturbance that can raise when an operator directly manipulates the sensor.

On the other hand, some limitations can be noticed at this state of the project:

• As the SLAM is not currently performed online, the robot is not fully autonomous yet;

• As the illuminance sensor has been calibrated, the light measurement uncertainties are precisely known however localization uncertainties are complex to estimate and are not evaluated so far, but will be the subject of a further work;

• The system is not user-friendly yet and must be operated by a specialist or at least after some training courses where manual measurements are more straightforward.

It should be noted that the presented system is still a prototype and has not been industrialized. It is custom-made and the hardware costs about 20 k€ including 7 k€ for the LiDAR and 4 k€ for the frame. Furthermore, maintenance costs that will raise when using the robot daily are not evaluated so far as it has only been considered for academic researches.

Conclusion and perspectives

This paper describes Romulux, a mobile robot equipped with a 3D LiDAR carrying an illuminance meter. A SLAM algorithm is used to estimate the robot location in an indoor environment in order to construct an illuminance map. Illuminance values can then be compared to the standards. As places are often over-lit, the comparison can lead to downward adjustment in lighting power, thus saving energy while maintaining a sufficient level of safety and comfort. The results are significant and can be replicated in different indoor environments. The first evolution will be to consider outdoor environment: in particular because requests have appeared for measurement campaigns on tramway lines and on outdoor sport facilities. The use of Romulux robot for outdoor applications pushes the limits of its design framework. Particular attention will be paid to the behavior of the robot and the results. To that purpose the robot will be equipped with a GNSS sensor. A second axis of study will be to evaluate the precision of the approach in order to guarantee the measurements and thus the illuminance map. It is needed to take into account the uncertainty of location, resulting from LiDAR precision and SLAM algorithm result. The problem is complex and interval analysis tools will be explored for solving it. A third axis of study will be the complete automation of the system, by integrating algorithms of explorations, and by automating the outputs, ideally by generating them in real time. Finally it can be noted that this approach could be extended with several sensor maps such as temperature, air quality.

Figure 1 :

 1 Figure 1: The OPT3001 and Human Eye sensitivity.

  Figure 2 illustrates our implementation of the illuminance sensor above the LiDAR sensor. The location of illuminance measurements will be provided by Synchronous Localization And Mapping (SLAM) algorithms Birk and Pfingsthorn (2016); Bautin, Lucidarme, Guyonneau, Simonin, Lagrange, Delanoue and Charpillet (2013).

Figure 2 :Figure 3 :

 23 Figure 2: Sensor alignment: the illuminance sensor (little white dome) is above the LiDAR sensor (black tower). Both are aligned over the rotation center of the robot.

Figure 4 :

 4 Figure 4: Romulux architecture.

Figure 5 :

 5 Figure 5: Views of Romulux Robot.

  a) Sports hall point-cloud. b) SLAM paths.

Figure 8 :

 8 Figure 8: Cross comparison of SLAM path generated.

Figure 9 :

 9 Figure 9: Generation of illuminance map.

  a) The robot on the ice rink. b) Point cloud of Ice Park.

Figure 10 :

 10 Figure 10: Romulux in Ice Park.

Figure 11 :

 11 Figure 11: Generation of illuminance map.

Table 1

 1

	/velodyne_nodelet_manager
	/pa_slam /scan	/paslam/probmap /visualization_marker /obstacle /cmd_vel /rviz_to_twist /aru /move_base_simple/goal /aru /clear /rviz /clicked_point /cmd_vel /aru /custom_ui /visualization_marker /rviz_maillage /maillage_to_twist /clear /rviz_maillage /rviz_maillage /move_base_simple/goal /clear /aru
			/twist_controller
		/teleop	/cmd_vel	/controlled_cmd_vel	/motor

Figure 6: ROS Architecture with nodes and topics Figure 7: Romulux in the sport hall.

http://wiki.ros.org/geometry_msgs

http://wiki.ros.org/rosbag

https://youtu.be/0PwFAdcqaLE

https://mtidocs.xsens.com/mti-600-series-user-manual

https://hal.science/hal-00939161.

Acknowledgment

The authors thank Alain Thomas for the project management, Anthony Colin for the mechanical study, Yannick Besiau for the electrical study, Bruno Nourrisson, Jocelyn Onillon, Jean-François Besson for the mechanical construction, Florian Greffier for the original idea.

CRediT authorship contribution statement

Rémy Guyonneau: ROS programming and SLAM integration, experiments, redaction of the paper. Franck Mercier: mecatronic design and theoretical formalism, experiments, redaction of the paper. Vincent Boucher: illuminance map generation and standards comparisons, experiments, redaction of the paper.


Gabrielle Demange

Stable outcomes in simple cooperative games

Keywords: simple games, coalitions, median graph, tree, intermediate preferences, Condorcet JEL Classification D720, D710

In a cooperative game, coalitions are the fundamental behavioral units. Stable outcomes (in the core) are those blocked by no coalition. This paper has two objectives. First, building on the notion of intermediate preferences indexed by a median graph, I unify and extend previous results on the existence of stable outcomes in simple games. Second, I review how and when the core approach applies in more general settings and may help to predict the stable splitting of a whole group into disjoint coalitions.

Introduction

The stability of collective decisions is a prominent issue for groups, organizations, political bodies and communities. Often, instability comes from the threats of blocking coalitions. A coalition blocks a proposed decision when it has the power to impose another decision that is preferred by all its members. A stable outcome (in the core) is one that is blocked by no coalition. As illustrated by the celebrated Condorcet 'paradox', no stable outcome may exist under the majority rule. There are three individuals, three alternatives a,b,c. The first agent prefers a to b to c, the second b to c to a and the third c to a to b. 1 and 2 both prefer a to c; since coalition {1, 2} has a majority of the electorate, it blocks c. Similarly, {2, 3} blocks a and {3, 1} blocks b. Such a configuration potentially gives rise to an unlimited sequence of blocking and instability. Instability is due to two ingredients: the distribution of coalition power (each of the three doubletons has the power to block any alternative) and the preferences configuration. This raises the question: under which conditions on coalitions power and preferences does a stable decision exist? A large part of the cooperative theory literature is devoted to answer this question in a variety of settings beyond the majority rule.

The main result of this paper provides an additional contribution that encompasses a number of known results. Consider a simple game, as defined by Von Neumann and [START_REF] Von Neumann | Theory of Games and Economic Behavior[END_REF], in which coalitions are either all-powerful or ineffectual, represented by a set of winning coalitions as, for example, the coalitions with more than half the population in a majority game. I display families of preference that guarantee stability, meaning that a stable outcome exists when the preferences of all individuals involved in the game belong to such a family. Preferences in a family satisfy some interdependence structure captured by betweenness relationships, as described below. While the main result bears on a simple game, representative of voting power, the stability of collective decisions is a pervasive issue. In many political and economic situations, a group of individuals coordinate their actions while facing the threats that potential coalitions may generate by blocking or seceding. In the last section, I briefly review how the core notion sheds some lights on these situations and help to predict on the endogeneous formation of stable subgroups.

The domain of simple games is quite rich in practice. Many political and organizational structures base their decisions on simple games. Unanimity, majority, weighted majority, super-majority are all simple games. More elaborate is double majority, which requires a majority of votes (or supermajority) according to two separate criteria, say the number of voters and their weights. For example, the Council of the European Union requires 55% of voting EU member states representing at least 65% of the population of voting members for a European Commission proposal to be approved (except for decisions requiring unanimity). Although simple to describe, simple games are worth studying for several reasons, methodological, didactic, and practical, as argued by [START_REF] Shapley | Simple games: an outline of the descriptive theory[END_REF]. 1 Most of the issues related to stability in games describing in detail applied situations already arise in simple games. The transparent technical tools for analyzing simple games thus shed some light on more complex situations.

Consider a group that has to choose a collective decision based on members' preferences on the set of possible decisions (alternatives). Each preference ordering is parameterized by a characteristic belonging to a connected graph, where a link between two characteristics means that they are between two others if it lies on a shortest path joining them.

I show that a family of preferences parameterised by characteristics on a graph guarantees stability2 in any simple game if the following two conditions are met: (1) preferences are intermediate and

(2) the graph linking characteristics is median. Preferences are said to be intermediate if the order associated to a characteristic that is between two other characteristics ranks any pair of alternatives as these two others whenever they agree on the ranking of the pair. Intermediate preferences thus imposes some interdependence structure between individual preferences but no restrictions on the shape of each one. The graph is median when any triple of vertices has a unique median, meaning there is a unique vertex that lies on shortest paths between each pair of vertices. Important examples of median graphs are trees, which include lines, and hypercubes, composed with all points with p coordinates equal to 1 or 0.

The result encompasses known results. For instance, it implies that the majority relation is acyclic when the sets of alternatives and characteristics are both ordered and preferences are singlecrossing, as shown by [START_REF] Gans | Majority voting with single-crossing preferences[END_REF] 3 because single-crossing preferences are intermediate on a line. This example is specific in several aspects. First, the majority relation is associated to a particular simple game. Second, a line describes a very specific structure of relations between characteristics. Third, the set of alternatives is ordered. Our stability result bears on any simple game and the alternative space, in particular its dimension or structure, does not matter, provided that preferences are intermediate.

The proof relies on the notion of convexity in a graph, called discrete convexity. A set is said to be convex if it contains all shortest paths between two points.4 Hence intermediate preferences require that for any two alternatives x and y the subset of characteristics for which x is preferred to y is convex. The central property used in the proof is that the convex sets of a median graph satisfy the Helly property: for any family of pairwise intersecting convex sets, the sets in the family have a common intersection. 5 The fact that the space is median is essential for the result. For example, stability is not guaranteed for the majority relation when alternatives are multi-dimensional and preferences are based on the euclidean distance to their peaks [START_REF] Grandmont | Intermediate Preferences and the Majority Rule[END_REF]. Euclidean distances define intermediate preferences but a multi-dimensional space is not median.

The literature on median graphs is extremely vast. Median graphs have been introduced independently in different equivalent ways in several fields, as they are related to lattice theory and important notions used in classification. Links between various definitions appear in Mulder and Schriver (1980) and there are several surveys e.g. [START_REF] Klavzar | Median graphs: characterizations, location theory and related structures[END_REF] and [START_REF] Van De | Theory Of Convex Structures[END_REF].

I only use the Helly property for convex sets.

Intermediate preferences impose restrictions between the preferences in a family. Single-peakedness is another type of restrictions, defined with respect to some ordering on the set of alternatives and the preferences 'peak' (the most preferred alternative). [START_REF] Black | On the rationale of group decision-making[END_REF] introduces single-peaked preferences on a line as those decreasing from the peak and shows the existence of a Condorcet winner (a stable alternative under majority). In [START_REF] Demange | Single-peaked Orders on a Tree[END_REF], I define single-peaked preferences on a tree as those decreasing from the peak on any path of the tree and extend Black's result. More recently, [START_REF] Nehring | The structure of strategy-proof social choice-Part I: General characterization and possibility results on edian spaces[END_REF] define single-peaked preferences on a median space, by requiring that any alternative between the peak and another alternative is preferred to that alternative. By their very definitions, single-peakedness and intermediate preferences differ: single-peakedness assumes some ordering structure on the set of alternatives, and intermediate preferences assume some structure on a characteristic space but not on the set of alternatives. This fact is somewhat blurred because the prominent model in voting assumes both the set of alternatives and characteristics to coincide and to be ordered. However even in that case, the two notions differ (see more discussion in [START_REF] Saporiti | Strategy-proofness and single-crossing[END_REF]. Single-peaked preferences have been mostly used in the works on the majority rule and, more generally, on strategy-proof functions.

More references are given in the text. The plan is as follows. Section 2 presents the framework, introduces the basic definitions of simple games, median graph and intermediate preferences, and illustrates with some examples. Section 3 gives the main result which states that the dominance relation is cycle-free for a family of intermediate preferences on a median graph, applies it to the majority relation and compares intermediate preferences and single-peaked preferences. Section 4 discusses some extensions of the core allowing to study the stability of coalition formation.

The framework

A finite set N = {1, .., i, .., n} of individuals -a 'society'-has to choose an alternative in a feasible set X. Individuals have preferences over these alternatives. A coalition is a nonempty subset of N . We are interested in alternatives that are stable in the sense that no coalition blocks them. A coalition blocks an alternative if it has the power to impose another alternative that all of its members prefer.

Hence blocking is defined jointly by the power of coalitions and individuals' preferences.

I consider simple games, in which the power of coalitions is all or nothing, represented by the set of winning coalitions. The interpretation is that a winning coalition can block any alternative and a non-winning coalition can block none. Let W denote the set of winning coalitions. The following natural assumptions are made:

(monotonicity): any coalition containing a winning coalition is also winning, that is, (S ∈ W and S ⊆ T ) imply T ∈ W (consistency): the complement of any winning coalition is losing, that is,6 S ∈ W implies N -S / ∈ W. Let R = (R 1 , ..., R n ) denote the profile of the n individuals' preference orderings over X.

A winning coalition blocks alternative y if there is an alternative x that all its members prefer to y. Blocking defines a dominance relation between alternatives as follows.

x is said to dominate y if the subset of agents preferring x to y is a winning coalition. Therefore an alternative that is dominated is blocked and conversely. Formally, given R, denoting the dominance relation7 by dom R :

xdom R y if {i ∈ N such that xP i y} ∈ W. ( 1
)
The core is the set of alternatives that are not blocked, equivalently not dominated:

C(R) = {x ∈ X, for no y ∈ X : ydom R x}. (2)
The set X is assumed finite for simplification. When the dominance relation is acyclic, there are alternatives that are not dominated, hence the core is nonempty.8

Many common procedures in committees and assemblies are represented by simple games. For example, qualified majority requires a specified level of support to pass a candidate. It is defined by weights on individuals, i.e. w i ≥ 0 for i in N such that i∈N w i = 1, and a threshold q ≥ 1/2 (simple majority corresponds to equal weights and q equal to 1/2). S is winning if i∈S w i > q. A stable alternative is a candidate for which no other candidate is preferred by more than the proportion q of the weighted voters. Increasing the level q decreases the set of winning coalitions, hence increases the chances for a stable alternative to exist.

A family of preferences O is said to guarantee acyclicity if the dominance relation dom R is acyclic for any profile R = (R 1 , ..., R n ) in O n .9 If O guarantees acyclicity, then it also guarantees the existence of stable outcomes whenever all individuals' preferences belong to the family. I consider a family O where preferences are parameterized by a characteristic θ running in a set Θ: O = {R θ , θ ∈ Θ}. So i's preference ordering is determined by i's characteristic θ i , and a preference profile by the

n-tuple of characteristics θ = (θ 1 , .., θ n ) in Θ N .
The main result in Section 3 displays families of preferences that guarantee acyclicity. The result assumes three ingredients: (1) the set of characteristics is endowed with betweenness relationships defined by a graph (2) the betweenness relations between characteristics carry over to preferences in O in a natural sense as defined by [START_REF] Kemeny | Mathematics without numbers[END_REF] (3) the graph on Θ satisfies a property on triples, making Θ a median space. Here are the formal definitions.

Betweenness relationships

The notion of intermediate preferences assumes there are betweenness relations on the set of characteristics. A graph structure on Θ, meant to describe which characteristics are 'close', define betweenness relations as follows. A path between θ and θ is a sequence of elements θ 1 , ..., θ j , ..., θ p in Θ for which θ = θ 1 , θ = θ p and the pairs (θ j , θ j+1 ) are edges for j ∈ {1, ..., p -1}. The graph is assumed to be connected, meaning there is a path between any two points in Θ. A line is a graph formed with a unique path; a tree is a graph for which there is a unique path between any two points, equivalently the graph has no cycle.

Betweenness relation on characteristics

The shortest paths in graph G define a betweenness relation between characteristics as follows.

A shortest path linking two vertices is one with the minimal number of edges in a path joining the two vertices. This minimal number is defined as the distance between the two points, denoted by d(θ, θ ) for θ and θ . A vertex θ is between θ and θ if it belongs to a shortest path joining θ and θ or, equivalently, if the distance between θ and θ is the sum of the distances between θ and θ and between θ and θ . The interval between θ and θ , denoted by [θ, θ ], is the set of all vertices between θ and θ :

[θ, θ ] = {θ , d(θ, θ ) = d(θ, θ ) + d(θ , θ )}. (3)
A subset of Θ is said to be convex if it includes the interval between any pair of elements, equivalently it includes all shortest paths between any pair. A subset is connected if it includes a path between any of two elements. Hence a convex set is connected. The converse is not necessarily true, except in a tree since there is a unique path between two points.

Intermediate preferences A preference relation is between two others if it ranks two alternatives as these two others whenever they agree on the ranking on the two alternatives [START_REF] Kemeny | Mathematics without numbers[END_REF]). 10

Preferences in O are intermediate when the betweenness relationships between characteristics carry over to preferences:

Definition 1 Let Θ be endowed with a betweenness relationship described by a graph G. The family O = {R θ , θ ∈ Θ} satisfies the intermediateness property if for any θ and θ in Θ and θ between θ and θ , P θ is between P θ and P θ that is: for all x and y in X (xP θ y and xP θ" y) imply xP θ y

The intermediateness property requires that for every pair of elements x and y in X the set {θ ∈ Θ such that xP θ y} is a convex set. Observe that the property imposes relations between the preferences in a family, but does not impose restrictions on the shape of each one.

When X and Θ are uni-dimensional, intermediate preferences appear under various related forms, such as the Spence-Mirrlees condition (monotony of marginal rates of substitution) increasing differences and ordinal single-crossing property (see [START_REF] Gans | Majority voting with single-crossing preferences[END_REF]. [START_REF] Grandmont | Intermediate Preferences and the Majority Rule[END_REF] Call these preferences d-preferences. Here, the graph is the transportation network, the alternatives are the vertices and individuals' characteristics are their locations on the network: It is easy to check that the d-preferences are intermediate when Θ is a line or, more generally, is a tree.

10 One may also require similar conditions for the weak relations R θ . Theorem 1 only uses the conditions on the strict preferences.

Example 2 Increasing differences and Spence-Mirlees condition. Consider the problem of choosing the quality of a public facility. An alternative is the quality q for a public good. A characteristic belongs to Θ = [θ, θ]. The characteristic θ determines the valuation for quality q, represented by u(q, θ) for some function u (u is not necessarily monotone in q if u is an indirect utility function incorporating the financing of the cost to provide quality q). u is said to satisfy the increasing differences property if the incremental benefit of increasing quality is increasing in θ: for q > q , the function θ → u(q, θ) -u(q , θ) increases with θ. For a twice differentiable function u, the Spence-Mirrlees condition, ∂ 2 u ∂θ∂q > 0, implies increasing differences because for q > q the derivative of θ → u(q, θ) -u(q , θ) is positive.

Assume u satisfies increasing differences. Let us prove that the family {u(θ, .), θ ∈ Θ} satisfies the intermediate preferences property. It suffices to consider any two alternatives q and q , q > q , and show that the set I of θ for which q is preferred to q is an interval. We have I = {θ ∈ [θ, θ] such that u(q, θ) -u(q , θ) > 0}. Increasing differences ensure that I is either empty, the whole interval, or there is a cutoff value θ * for which the θ preferring q to q are those larger than θ * , that is I =]θ * , θ]. This proves the intermediateness property.

The result extends to a richer two-dimensional set of alternatives. For example, consider the problem of choosing the quality q of a public facility as well as its access price p. An alternative is thus a pair x = (q, p). Let individual preferences be separable represented by u(q, θ) -p. One easily checks that preferences are intermediate if u satisfies increasing differences. 11

Median graph, Median space

A graph is median if for any triple of vertices a unique vertex belongs to a shortest path between any two points of the vertex. 12 Definition 2 A graph G = (Θ, E) is said to be median if for every triple (α, β, γ) made of elements in Θ, a unique vertex µ is between (α, β), (β, γ) and (α, γ):

{µ} = [α, β] ∩ [β, γ] ∩ [α, γ]. The set Θ endowed with the median graph structure G is called median space.
Familiar examples of median graphs are lines and trees. In a line, the median of the triple is always a member of the triple. In a tree, the median of the triple is not always a member of the triple, as 11 Now the set I of θ for which (q, p) is preferred to (q , p ) is I = {θ ∈ [θ, θ] such that u(q, θ) -u(q , θ) > p -p }. If q > q , the same proof works as if there is no access price. If q = q , I is either empty or the whole interval [θ, .θ].

12 There are different equivalent definitions of median graphs ( see the survey by [START_REF] Klavzar | Median graphs: characterizations, location theory and related structures[END_REF]). One definition is in terms of the distance in the graph. A median is characterized by

d(α, β) = d(α, µ) + d(µ, β), d(β, γ) = d(β, µ) + d(µ, γ) and d(γ, α) = d(γ, µ) + d(µ, α).
Hence the median minimizes the sum of the distance to the three elements in the triple, i.e. is a metric median. An equivalent definition thus requires the uniqueness of a metric median for each triple.

illustrated by (α, β, γ) in the tree of Figure 1 on the left. A graph that contains a cycle of length different from 4 is not median. This is obvious for a cycle of length three. For a cycle of length five, as depicted in Figure 1 on the right, let us show that the triple {α, β, δ} has no median. The interval between α and β is {α, β}, the interval between β and δ is {β, γ, δ} and the interval between α and δ is {α, ε, δ}. Since the three intervals do not intersect, the triple has no median. The argument extends to cycles of length larger than 5. The two graphs depicted in Figure 2 are median and include cycles of length four. In the grid on the right, there are three shortest paths between α and β. More generally, the interval between two points contains all the points with coordinates between the minimum and maximum of the coordinates of the two points.

Hypercubes A p-cube, also called hypercube, describes points with coordinates equal to 0 or 1: the p-cube is Θ = {0, 1} p . Figure 2 on the left represents the 3-cube. One interpretation of an hypercube is in terms of properties. Each of the dimensions of the hypercube is associated to a property, say home ownership, marital status, worker status and so on. Each property can be An edge of the graph links two vertices whose coordinates are all equal but one. It follows that the interval between two vertices θ and θ is composed of all the vertices θ such that, for each k = 1, • • • , p, the k-th coordinate of θ assumes the same value as that of θ and θ when there are identical:

θ k = 1 if θ k θ k = 1 and θ k = 0 if θ k = θ k = 0.
The median of three vertices is the unique point for which each coordinate is equal to the majority value in the triple: the k-th coordinate of the median is equal to 1 if at least two values in the triple assume value 1, and is equal to 0 otherwise. For example, in the 3-cube in Figure 3, the median of the triple α = (0, 0, 1), δ = (1, 1, 1) and A convex set C of an hypercube is characterized by two disjoint (possibly empty) subsets K 0 and K 1 of {1, • • • , p} on which the coordinates are fixed, equal to 0 or 1: C = {θ, such that for k ∈ K 0 : θ k = 0 and for k ∈ K 1 : θ k = 1}. It follows that preferences indexed on an hypercube are intermediate if, for each pair of alternatives x and y, whether xP θ y holds is characterised by two disjoint subsets K 0 and K 1 . Interpreting each of the p dimensions as a property, x is preferred to y by the characteristics θ that satisfy the properties in K 1 and do not satisfy those in K 0 . The set of characteristics for which yP θ x must be also convex, hence characterized by two subsets K 0 and K 1 . Consistency imposes some requirements, for example that simultaneously K 0 is identical to K 0 and K 1 to K 1 . The more indifferences preferences involve, the larger the index subsets are and the less severe these requirements are. Instead, if the orderings are strict between x and y, then {θ ∈ Θ such that xP θ y} and {θ ∈ Θ such that yP θ x} form a partition of the cube into two convex sets. One easily checks that K 0 must be empty and K 1 a singleton or the reverse, i.e. K 0 a singleton and K 1 empty. This means that a single property determines the preferences of x over y.

β = (1, 0, 0) is β = (1,
Let us now consider the d-preferences (introduced in Exemple 1). Contrary to the case where the graph is a tree, d-preferences on hypercubes are not intermediate. For example, in the 3-cube in Figure 2, both α and δ are closer to β than to γ but γ, which is between α and δ, is closer to γ than to β. More generally, let a median graph contain a cycle and Θ has at least 5 elements. The cycle is necessarily of order four, so one can find five elements with the same structure as (α, β, γ, δ, γ ) in the 3-cube. It follows that d-preferences are not intermediate.

The main result

The combination of a median graph structure for the set of characteristics and the property of intermediate preferences allows for a 'positive' result in the sense that the dominance relation of any profile is acyclic, hence the core is nonempty. The crucial point in the proof is that the convex sets in a median graph satisfy the following property called Helly property: Given a median graph, let F be an arbitrary family of pairwise-intersecting convex sets. Then all sets in F have a common intersection.

Applying the condition to a family with three elements, the Helly property excludes the existence of Condorcet triples of convex sets. Define a Condorcet triple as three coalitions that intersect each other and whose overall intersection is empty:

S i , i = 1, 2, 3, with S i ∩ S j = ∅ and S 1 ∩ S 2 ∩ S 3 = ∅. (4)
The following proof first shows that there are no Condorcet triples of convex sets in a median graph and then uses an induction argument to prove the Helly property.14 Let F be made of a Condorcet triple of convex sets. Choose for each pair a point in its intersection, θ 12 in S 1 ∩ S 2 , θ 23 in S 2 ∩ S 3 , θ 31 in S 3 ∩ S 1 . The median of the three points is between θ 12 and θ 23 hence belongs to S 2 by convexity; similarly considering the other pairs, the median belongs to S 3 and S 1 . This proves that the overall intersection of the three sets is nonempty. The proof proceeds by induction on the number of elements in F, using that the intersection of two convex sets is also a convex set.

Theorem 1 Given a set of agents N , consider a simple game on N defined by a collection of winning coalitions. Let O = {R θ , θ ∈ Θ} be a family of preferences on a set of alternatives X.

Assume Θ is a median space and O a family of intermediate preferences. Then for each n-tuple of characteristics θ there is a characteristic θ, not necessarily in the profile, such that the dominance relation is stronger than the order P θ :

xdom θ y implies xP θ y.

(5)

Hence the family O guarantees that the dominance relation is acyclic and the core is nonempty.

The proof is given at the end of this section. I first draw some consequences for the majority relation.

Majority relation and majority rule

To simplify, let us assume n to be odd and preferences strict. Then two distinct alternatives are always comparable since either a majority prefers x to y or a majority prefers y to x. Theorem 1 implies that the majority relation coincides with the order P θ hence it is transitive. Two consequences can be drawn. The majority relation aggregates well preferences and the majority rule is strategy-proof, as stated in [START_REF] Demange | Majority relation and median representative ordering[END_REF] and the following corollary. Furthermore, θ can be qualified as a representative characteristic of the profile θ.

Corollary 1 Let Θ be a median space and let O = {R θ , θ ∈ Θ} be a family of intermediate strict preferences on a set of alternatives X. Let n be odd. The majority rule, which assigns to each (θ 1 , .., θ n ) its Condorcet winner, i.e. the top alternative of P θ , is strategy-proof.

Theorem 1 readily applies to variations of the majority relation obtained by adding 'phantom' voters in a similar way as in [START_REF] Moulin | On strategy-proofness and single-peakedness[END_REF]. Fix (τ 1 , .., τ p ), the profile of p phantom voters. Given a characteristics' profile (θ 1 , .., θ n ), consider the majority relation for the profile (τ 1 , .., τ p , θ 1 , .., θ n ).

Corollary 1 applies hence the aggregation and strategy-proof results hold for these modified majority relations.

In [START_REF] Demange | Majority relation and median representative ordering[END_REF], I prove the result in a different way by relying on the local Condorcet characteristic of the profile θ for the graph distance. By definition, a local Condorcet characteristic θ beats all its neighbors for the d-preferences, meaning that, for each neighbor, a majority of voters is closer to θ than to that neighbor. [START_REF] Bandelt | Medians in median graphs[END_REF] prove the existence and uniqueness of a local Condorcet characteristic when the graph is median.

In a tree, θ is also a global Condorcet characteristic, meaning that, for each other characteristic, a majority of voters is closer to θ than to that characteristic. This follows from Theorem 1: since Comparison between intermediate preferences and single-peaked preferences It is useful to clarify the differences between single-peaked and intermediate preferences and the types of associated results. In that purpose, let the set of alternatives X be endowed with a tree structure. A strict preference ordering on X is single-peaked if the ordering decreases along any path starting at the peak. A Condorcet winner always exists for single-peaked preferences on a tree [START_REF] Demange | Single-peaked Orders on a Tree[END_REF]. The majority relation however may have cycles as illustrated in Figure 1 on the left. Let X = {α, β, γ, µ} and three individuals have preferences µP 1 α P 1 β P 1 γ, µ P 2 β P 2 γ P 2 α and µ P 3 γ P 3 α P 3 β. These preferences are single-peaked and µ is obviously the Condorcet winner.

But the majority relation has a cycle on (α, β, γ). Hence, the set of single-peaked preferences on a tree guarantees a Condorcet winner but does not guarantee the transitivity of the majority relation.

Consider now a family of intermediate preferences for which the characteristic represents the peak. The above example is excluded since a single preference relation has µ as the peak. From

Theorem 1 the majority relation is transitive.

Although this example may suggest that the framework with intermediate preferences is more restrictive than the one with single-peaked preferences, this is not true for at least two reasons.

First, even in uni-dimensional spaces, preferences satisfy the intermediate property but not the single-peaked one in several applications to political economy and models of redistribution (see [START_REF] Saporiti | Strategy-proofness and single-crossing[END_REF] for various examples and references and a thorough discussion on the differences between the two properties). The basic reason is that intermediate preferences do not impose restrictions on the shape of individual preferences. Second, intermediate preferences are not necessarily parameterised by their peaks or by any alternatives. They allow for any set of alternatives different from the set of characteristics. This fact has been somewhat blurred because the prominent model in applications assume a uni-dimenional set of alternatives and characteristics specified by their peaks.

A different viewpoint asks the following question: Given observed preferences, does it exist some set Θ endowed with a betweenness structure such that these preferences are intermediate?

or some ordering of the alternatives such that these preferences are single-peaked? Computational social choice addresses these questions, with a focus on the design and complexity of algorithms for recognizing whether a family of preferences satisfies a particular property. [START_REF] Elkind | Preference restrictions in computational social choice: A survey[END_REF] survey the results on the single-crossing and single-peaked properties.

Proof of Theorem 1 For a pair w, x of alternatives, denote Θ w>x the subset of characteristics for which w is preferred to x: Θ w>x = {θ ∈ Θ s.t. wP θ x}. Let us define the family F of subsets Θ w>x for which wdom θ x. Let us first prove that the assumptions imply that the intersection of all the sets in F is nonempty. Because of intermediate preferences, Θ w>x is a convex set of the median graph G. From Lemma 1, each pair of sets in F has a nonempty intersection. Hence, by the Helly property, their overall intersection is nonempty.

Let θ belong to the overall intersection of subsets in F. By definition, for each pair such that wdom θ x, θ belongs to the set Θ w>x = {θ ∈ Θ s.t. wP θ x}. Hence wdom θ x implies wP θ x, which proves (5). A cycle of dom θ would be a cycle of P θ , which is impossible.

Lemma 1 Consider a simple game. Let two pairs w, x and y, z of elements of X such that wdom θ x and ydom θ z. Then there is i in N for which wP θi x and yP θi z, hence Θ w>x ∩ Θ y>z = ∅.

Proof. wdom θ x if the set {i, wP θi x} is a winning coalition. Hence wdom θ x and ydom θ z imply that both coalitions {i, wP θi x} and {i, yP θi z} are in W. By consistency of the game, the two coalitions intersect, and for i in their intersection, wP θi x and yP θi z. This proves the lemma. .

Extending the approach

In many political and economic situations a group of individuals coordinate their actions while facing the threats that potential coalitions may generate by blocking or seceding. A main issue is whether these threats hamper the group to coordinate efficiently. Stability and the core notion as investigated in the previous section in the voting context extend to these situations. The approach is not limited to games where the whole society must coordinate. Indeed, in some problems, coordination brings benefits but, at the same time, it is efficient for the whole group to split into smaller self-sufficient groups. It is then natural to consider partitions of the society and to investigate which ones are stable to blocking. This insight was pioneered by [START_REF] Aumann | Cooperative Games with Coalition Structures[END_REF], who introduced stable coalition structures. The notion of the core applied to partitions thus produces predictions on the endogeneous formation of subgroups. Before presenting such approach, I make two observations.

First, the notion of stable coalition structures assumes the absence of externalities across coalitions, meaning that the actions that are feasible for a coalition if it forms as well as the payoffs to its members are not affected by the organization of agents outside the coalition. Without externalities, a coalition can predict the payoffs its members can achieve by splitting from the rest of the society. Externalities across groups, negative or positive, have an important impact in some contexts, those concerning environmental agreements for example. Their analysis however raises a number of conceptual and technical difficulties and there are no general results. 15

Second, alternative approaches to blocking have been proposed to address the stability to coalitions deviations. Blocking can be perceived as myopic, as a coalition does not account for further 15 One difficulty is that the blocking behavior depends of which prediction a coalition makes on how the remaining agents organize themselves. See e.g. [START_REF] Chander | The core of an economy with multilateral environmental externalities[END_REF], Carraro and Siniscalco (1997), [START_REF] Bloch | Sequential formation of coalitions in games with externalities and fixed payoff division[END_REF], [START_REF] Yi | Stable coalition structures with externalities[END_REF], [START_REF] Ray | A theory of endogenous coalition structures[END_REF], [START_REF] Currarini | Group stability of hierarchies in games with spillovers[END_REF].

blocking. These critics have led to consider different types of deviations, for example Chwe (1995) introduce farsighted coalitions and Bernheim, Peleg, and Whinston (2014) introduce credible and self-enforcing deviations. Considering coalition moves that differ from blocking leads to different equilibria. The literature is too vast to give a faithful account of these approaches. An argument to justify considering alternatives in the core is similar to the one that justifies considering Nash equilibria: if a stable alternative is outstanding, it is common knowledge that no coalition benefits from an unilateral move.

Modeling a (cooperative) game As in the previous section, the analysis is based on the payoffs that coalitions can achieve on their own. Two ingredients are fundamental to describe these payoffs:

the power of coalitions and individuals' preferences.

The power of a coalition is specified by the decisions that its members can make independently of the organization of outsiders. Let X(S) denote the set of feasible decisions for coalition S. The description of the feasible sets depends on the problem at hand. In a simple game, X(S) is empty for a non-winning coalition and the whole set X for a winning one. In general, a feasible set incorporates the technological, institutional or informational constraints that a coalition faces if it forms and restrict the way decisions it can made. For example, a coalition of citizens can choose personalized taxes when perfectly informed about all citizens' characteristics but must rely on unit taxes or consumption taxes when less information is available.

Individuals' preferences bear on the decisions, represented by a utility function, u i for i. If S forms and chooses a, i member of S obtains utility level u i (a).

Super-additive games Super-additive games represent situations where each coalition is always at least as efficient as any of its partitions. Formally, given two disjoint coalitions, S and T , for any a feasible for S and b feasible for T , there is c feasible for the union S ∪ T under which all members are at least as well off:

   for any a in X(S) and b in X(T ), there is c in X(S ∪ T ) such that for each i ∈ S : u i (c) ≥ u i (a) and for each i ∈ T :

u i (c) ≥ u i (b). (6)
These conditions state that the payoffs S and T can achieve by acting separately can be achieved by their union. A game in which (6) holds for each disjoint pair of coalitions is called super-additive.

A simple game is super-additive since at least one of two disjoint coalitions has no power, hence its alternative set is empty. Under strict inequalities in (6), efficiency requires the whole set N to form and make a decision that applies to each member of the society.

Since a coalition S can achieve on its own the vector of utility levels (u i (a)) i∈S for a in X(S), the blocking and core notions follow: A decision a ∈ X(N ) is blocked by coalition S if there is a decision b feasible for S that makes every member of S better off:

for some b in X(S) u i (b) > u i (a) each i in S.

a is stable (or in the core) if it is not blocked. We already know that the core of a super-additive game can be empty. Working on the set of feasible payoffs for each coalition, 16 Bondareva (1963), [START_REF] Shapley | On Balanced Sets and Cores[END_REF] and [START_REF] Scarf | The core of an N person game[END_REF] provide conditions under which the game has a non-empty core.

Roughly speaking, these conditions require some form of super-additivity for families of coalitions that are not disjoint but form with some probability (called balanced family of coalitions). These conditions apply to a given game, that is to fixed feasible sets and preferences. In the spirit of the previous section, it is interesting to investigate stability for a range of games by varying preferences or the feasible sets. I present results along this line in games that are not necessarily super-additive.

Stable coalition structures In games that are not super-additive, the whole society may benefit from splitting into a partition of smaller self-sufficient groups. A coalition structure describes such an organization.

A coalition structure of N is a family (a , S ) =1,...,L where (S ) =1,...,L is a partition of N and a is feasible for S , = 1, . . . , L.

The interpretation is that each group S forms and adopts decision a , which is feasible for it independently of the remaining agents. Letting (i) denote the unique coalition to which i belongs, i's achieves the utility level equal to u i (a (i) ). The blocking notion follows:

The structure (a , S ) =1,...,L is blocked by coalition S if there is a decision b feasible for S that makes every member of S better off:

for some b in X(S) u i (b) > u i (a (i) ) each i in S.
The structure is stable if it is blocked by no coalition. If the game is strictly super-additive (i.e. the inequalities (6) hold strictly) L is necessarily equal to 1 and we fall back on the previous notion.

Otherwise, the number of subgroups L is not fixed a priori and depends on the problem. Observe that, even though there are no externalities across coalitions, the full organization of the society determines the benefit from blocking.17

The splitting of the society as captured by coalition structures may be due to exogenous restrictions to coalition formation or stem from preferences diversity. I examine these factors in turn.

Essential coalitions

In some situations, some coalitions play an essential role and stability depends only on them. Non-essential coalitions are not permitted to form or have a blocking power dominated by the essential ones (as is the case for a non-winning coalition in a simple game). The more limited the set of essential coalitions, the more likely there are stable coalition structures. One question is to which extent the set of essential coalitions must be limited to guarantee stability, i.e.

the existence of stable structures whatever the preferences.

Assignment games or matching markets are well known examples where the set of essential coalitions is restricted. The society is partitioned into two sides, say men and women, buyers and sellers, colleges and students and only singletons and couples (pairs composed of one member of each side) are essential. A coalition structure (called matching or assignment) describes which couples are formed and possibly the transfers of money within each couple. When there are no transfers, a matching is stable if (a) no new couple can form in which both the man and the woman prefer each other to their standing partner (no couple blocks) (b) no person would prefer to stay single (no individual blocks). [START_REF] Gale | College Admissions and the Stability of Marriage[END_REF] define the deferred-acceptance algorithm and show its convergence to a stable matching, hence proving its existence. This algorithm serves as a basis for a huge amount of assignment procedures used in practice, especially in the academic world. Similarly, when agents in a couple can exchange money as considered by [START_REF] Shapley | The assignment game I: The core[END_REF], stable outcomes exist. These positive results have a common root: the family of singletons and couples in a two-sided setting guarantees stability. The two-sided aspect is crucial: in the so-called roommate problem where there are no sides, a stable outcome may not exist: a family of singletons and pairs does not guarantee stability.

Restrictions in communication or exchanges also induce restricted sets of essential formation, as introduced by [START_REF] Myerson | Graphs and cooperation in games[END_REF]. Let individuals be connected through a (social) network. The links in the network represent the possibility of exchanges or communication among the individuals, so that only the connected coalitions can form. When the network is a line, the game is called a consecutive game and the essential coalitions are interval; stability is guaranteed [START_REF] Greenberg | Stable Coalition Structures with Unidimensional Set of Alternatives[END_REF]. When the network is a tree, stability is guaranteed and furthermore stable outcomes, called hierarchical, 18 are easy to compute and to interpret as I show in [START_REF] Demange | On group stability in hierarchies and networks[END_REF]. 19 When the network contains a cycle, stability is no longer guaranteed. Such a result may provide a rationale for organizations such as tree-hierarchy structures. For a more recent treatment of organizations using coalition structures, see [START_REF] Morelli | Internal hierarchy and stable coalition structures[END_REF].

More generally, which families of essential coalitions guarantee stability? Let C be the set of 18 Recent works study hierarchical outcomes and related concepts as an allocation mechanism, see e.g. [START_REF] Herings | The average tree solution for cycle-free graph games[END_REF]. 19 The problem of 'sharing' a river studied in [START_REF] Ambec | Sharing a river[END_REF] shares some features of a hierarchy.

essential coalitions. It is easy to see that a set C of essential coalitions that contains a Condorcet triple (defined by (4)) does not guarantee stability. For example, letting S i , i = 1, 2, 3 be such a triple, consider the transferable utility game20 defined by the values: v(N ) = 1, v(S) = b if S is a strict subset of N that contains at least one of the S i and v(S) = 0 otherwise. For b smaller than 1 the game is super-additive but, for b strictly larger than 2/3, any feasible payoff is blocked by one of the S i . But the absence of Condorcet triples in C is only necessary for guaranteeing stability.

Mathematical characterizations for the guarantee are provided by [START_REF] Kaneko | Cores of Partitioning Games[END_REF] in terms of the extreme solutions to a system of linear equations (see also [START_REF] Breton | Strongly balanced cooperative games[END_REF].

Preferences diversity Splitting may stem from the diversity in individual tastes. For example, let the society decide on the quality of a pure public good. If the good is financed by a tax on income, with sufficient heterogeneity in taste or in income, the society may split into two communities, each producing a public good of different quality with a different tax level. Making accessible the high quality good to anyone would be more efficient but destabilised by the secession of part of the population. In general, two opposite forces -increasing returns to size and to coordination on the one hand and heterogeneity of preferences on the other-arise in a variety of contexts, including public goods choices, industrial organization, and jurisdictions boundaries (see the survey [START_REF] Demange | The stability of group formation[END_REF] for more detailed examples and references). The number of subgroups in a stable coalition structure then depends on the relative strength of these two forces. To name a few works, see [START_REF] Wooders | Equilibria, the core, and jurisdiction structures in economies with a local public good[END_REF] and [START_REF] Guesnerie | Second best taxation as a game[END_REF] for public good models, [START_REF] Greenberg | Stable Coalition Structures with Unidimensional Set of Alternatives[END_REF] for a unidimensional space and single-peaked preferences, [START_REF] Demange | Sustainable Oligopolies[END_REF] on oligopolies and [START_REF] Demange | Intermediate preferences and stable coalition structures[END_REF] and ( 2004) on games on trees when preferences are intermediate. In these works, a technique is to show that the assumptions on the preferences restrict the set of blocking coalitions one needs to consider.

To conclude, let us mention empirical works that build on the coalitional approach. Robbett [START_REF] Weese | Political mergers as coalition formation: An analysis of the Heisei municipal amalgamations[END_REF] analyzes the interaction between the national governmental transfers and the merger of municipalities in Japan.

  A (non-directed) graph on Θ is specified by a set E of unordered pairs of distinct elements of Θ called edges: (θ, θ ) in E means that θ and θ are close together. Denote G = (Θ, E) the graph. Following standard terminology, elements of Θ are called vertices and two elements linked by an edge neighbors.

  introduces the notion of families of intermediate preferences indexed by a convex set in a multidimensional space. In these two cases the characteristics and the alternatives are in the same space. In Demange (1994) I define intermediate preferences for characteristics on a tree and alternatives differing from characteristics. The following examples illustrate intermediate and single crossing preferences. Example 1 d-preferences. Consider the problem of locating a public facility on a transportation network (see for example Hansen and Thisse 1981 and the references therein). Individuals are located on the network and prefer the facility to be located as close as possible to their location: An individual located at θ prefers the public facility to be located at x rather than y if d(x, θ) < d(y, θ).

Figure 3 :

 3 Figure 3: Median graph: a 3-cube

  0, 1). The intervals are I(α , δ ) = {α , β , γ , δ }, I(α , β) = {α , β, α, β }, and I(δ , β) = {δ , β, δ, β }.

  the d-preferences are intermediate, a global Condorcet characteristic exists, necessarily equal to the local one. In an hypercube, θ may not be a global Condorcet characteristic, since d-preferences are not intermediate. To illustrate, consider θ = (α , β, β, δ , γ) in the 3-cube of Figure 2. Let us prove that β is the local Condorcet characteristic but is not a global one. Since β is the location of agents 2 and 3, let us check that, for each neighbor, at least one agent among 1, 4 and 5 prefers β to that neighbor. The neighbors of β are α, δ and β . β is closer to α for agent 4 (since d(δ , β) = 2 and d(δ , α) = 3), closer to δ for agent 1 (since d(α , β) = 2 and d(α , δ) = 3) and closer to β for agent 5 (since d(γ, β) = 2 and d(γ, β ) = 3). This proves that β is the local Condorcet characteristic. But γ beats β: Agents 1,4 and 5 all prefer γ to β because α , δ and γ are at a distance of 1 to γ and at a distance of 2 to β. Hence β is not a global Condorcet characteristic. This example also shows that the assumption of intermediate preferences in Theorem 1 is crucial.

( 2015 )

 2015 conducts laboratory experiments on how agents partition themselves into groups, Melatos and Woodland (2016) investigate trade bloc formation in a general equilibrium model, Desmet, Le Breton, Ortuno-Ortin and Weber (2011) present a model of nations where agents vote on the level of public spending,

Paris School of Economics, EHESS, Paris, France. E-Mail: demangegabrielle@gmail.com. I thank Andrés Carvajal for setting up this JME anniversary issue, Associate Editor Marina Nuñez-Oliva and an anonymous referee.

In fact the result is stronger as the 'dominance' relation associated to blocking is acyclic.

Single-crossing is satisfied under the Spence-Mirlees condition according to which the marginal rate of substitution for the decision -say public spending-is increasing in the characteristic -say income. See the text for definitions.

A convex set is thus connected, but the reverse is false, except in a line or a tree.

The Helly property for graphs resembles, but differs, from the Helly property for convex sets in a multi-dimensional real space.

Such a condition is also called 'proper'.

The dominance relation and the core depend on the set of winning coalitions W. As the set is fixed throughout the paper, it is unnecessary to index dom by W.

The proof is as follows. Let x be in X. If x is not in the core, there is x 1 that dominates x: x 1 dom R x. If x 1 is not in the core, there is x 2 such that x 2 dom R x 1 and so on. One builds a sequence x i of elements not in the core such that x i+1 dom R x i . The acyclicity of dom R implies that all the elements are distinct. Hence, because X is finite, the sequence stops and the final element is in the core. The proof extends to an infinite set under the compactness of X and continuity of the relations.

Other types of restrictions can be contemplated. For example,[START_REF] Nakamura | The core of a simple game with ordinal preferences[END_REF] shows the core is nonempty for any preference profile if the cardinality of the set of alternatives is less than some number, now called the Nakamura number.

A triple without median is one constituted of three points such that the interval for each pair is reduced to a single arc and the union of the arcs covers the cycle.

The Helly property is a kind of folk theorem.Mulder and Schriver (1980) mentions the result by applying a more general result on hypergraphs. A direct proof is much simpler.

The set of payoffs for S is defined by V (S) = {(x i ) i∈S such that x i ≤ u i (a) for a ∈ X(S)}.

In particular, stability is related to the notions of free individual mobility and free entry (i.e. free formation of coalitions). See Chapters 7 and 8 inDemange and Wooders (2005).

In a transferable utility game. all transfers among coalition's members are allowed and payoffs are linear in those transfers. The set of feasible payoffs to a coalition S is determined by its maximal attainable aggregate payoff, v(S), called its value: {(x i ) i∈S such that i∈S x i ≤ v(S)}.