James H Roberts
email: james.roberts@jhuapl.edu

O S Barnouin

M G Daly

K J Walsh

M C Nolan

R T Daly

Patrick Michel

Y Zhang

M E Perry

G A Neumann

J A Seabrook

R W Gaskell

E E Palmer

J R Weirich

S Watanabe

Na Hirata

S Sugita

D J Scheeres

J W Mcmahon

D S Lauretta

Rotational states and shapes of Ryugu and Bennu: Implications for interior structure and strength

Keywords: Ryugu, Bennu, Asteroids, Rotational Dynamics, Shape Model

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

At first glance, the asteroids (162173) Ryugu and (101955) Bennu look similar.

Images acquired by the Hayabusa2 [START_REF] Watanabe | Hayabusa2 arrives at the carbonaceous asteroid 162173 Ryugu -a spinning top-shaped rubble pile[END_REF] and OSIRIS-REx (Origins, Spectral Interpretation, Resource Identification, and Security-Regolith Explorer) (DellaGuistina and Emery et al., 2019;[START_REF] Walsh | Craters, boulders and regolith of (101955) Bennu indicative of an old and dynamic surface[END_REF] missions reveal that both are rocky worlds covered in rubble, including numerous boulders with diameters of tens of meters or larger. Both bodies have low albedos and spectra consistent with a carbonaceous chondrite-like composition [START_REF] Watanabe | Hayabusa2 arrives at the carbonaceous asteroid 162173 Ryugu -a spinning top-shaped rubble pile[END_REF]DellaGuistina and Emery et al., 2019;[START_REF] Hamilton | Evidence for widespread hydrated minerals on asteroid (101955) Bennu[END_REF]. To first order, both are shaped like spinning tops (Barnouin et al., 2019a;[START_REF] Watanabe | Hayabusa2 arrives at the carbonaceous asteroid 162173 Ryugu -a spinning top-shaped rubble pile[END_REF]. Their shapes are not hydrostatic, so they must possess some level of internal friction and/or cohesion even if they have no tensile strength [START_REF] Zhang | Creep stability of the[END_REF][START_REF] Hirabayashi | Stress and failure analysis of rapidly rotating asteroid (29075) 1950 DA[END_REF]. Understanding the deviation of the shapes from idealized surfaces can therefore help constrain the mechanical properties of the two asteroids' interiors.

Shape models of Ryugu and Bennu have been developed from spacecraft images using multiple techniques, including stereophotoclinometry (SPC) (Gaskell et al., 2008b;Barnouin et al., 2019a[START_REF] Barnouin | Digital terrain mapping by the OSIRIS-REx mission[END_REF] and geometric stereo (SfM) [START_REF] Hirata | Initial results of shape modeling on the asteroid Ryugu from observations by Hayabusa2 for landing site selection[END_REF], as well as from lidar ranging data collected by the OSIRIS-REx Laser Altimeter (OLA) [START_REF] Daly | The OSIRIS-REx Laser Altimeter (OLA) Investigation and Instrument[END_REF][START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF][START_REF] Barnouin | Digital terrain mapping by the OSIRIS-REx mission[END_REF] in the case of Bennu. Examples of shape models of Bennu and Ryugu are shown in Figure 1.

The rotational states and shapes of these bodies are key to understand their histories and predict future dynamic evolutions. The geologic evolution of rubble-pile asteroids is driven in large part by migration of surface material [START_REF] Walsh | Rotational breakup as the origin of small binary asteroids[END_REF][START_REF] Walsh | Physical Characterization and Origin of Binary Near-Earth Asteroid (175706) 1996 FG3[END_REF][START_REF] Harris | On the shapes of "rubble pile" asteroids[END_REF][START_REF] Richardson | Investigating the combined effects of shape, density, and rotation on small body surface slopes and erosion rates[END_REF], which may be dislodged by a suite of processes 47 Ryugu model v20190802 was determined using stereophotoclinometry from imaging data collected by Hayabusa2 [START_REF] Watanabe | Hayabusa2 arrives at the carbonaceous asteroid 162173 Ryugu -a spinning top-shaped rubble pile[END_REF]. For scale, the mean equatorial diameters of Bennu and Ryugu are 557 m and 1.02 km, respectively.

including re-accumulation [START_REF] Michel | Collisional formation of top-shaped asteroids and implications for the origins of Ryugu and Bennu[END_REF][START_REF] Holsapple | Equilibrium figures of spinning bodies with self-gravity[END_REF], impactinduced surface changes, and thermally driven processes [START_REF] Dombard | Boulders and ponds on the Asteroid 433 Eros[END_REF][START_REF] Delbo | Thermal fatigue as the origin of regolith on small asteroids[END_REF][START_REF] Molaro | In situ evidence of thermally induced rock breakdown widespread on Bennu's surface[END_REF]) that include thermal fragmentation. Sub-kilometer bodies are susceptible to changes in rotation due to the Yarkovsky-O'Keefe-Radzievskii-Paddack (YORP) effect [START_REF] Rubincam | Radiative Spin-up and Spin-down of Small Asteroids[END_REF][START_REF] Walsh | Rotational breakup as the origin of small binary asteroids[END_REF][START_REF] Cotto-Figueroa | Coupled spin and shape evolution of small rubble-pile asteroids: Self-limitation of the YORP effect[END_REF], in which asymmetric reflection, absorption, and re-emission of solar radiation from the surface cause torques that systematically increase or decrease the spin.

Bennu rotates with a period of 4.3 hours [START_REF] Hergenrother | The operational environment and rotational acceleration of asteroid (101955) Bennu from OSIRIS-REx observations[END_REF], nearly twice as rapidly as Ryugu, which has a 7.6-hour rotational period [START_REF] Watanabe | Hayabusa2 arrives at the carbonaceous asteroid 162173 Ryugu -a spinning top-shaped rubble pile[END_REF]. The rotation rate of Bennu has been observed to increase [START_REF] Nolan | Detection of Rotational Acceleration of Bennu Using HST Light Curve Observations[END_REF][START_REF] Hergenrother | The operational environment and rotational acceleration of asteroid (101955) Bennu from OSIRIS-REx observations[END_REF] since its discovery in 1999, at a rate of 2.7´10 -4 rad s -1 Myr -1 , which, if sustained, would double the rotation rate every 1.5 Myr [START_REF] Scheeres | The dynamic geophysical environment of (101955) Bennu based on OSIRIS-REx measurements[END_REF]. The rotation of Ryugu has not been observed to increase in this way; however, the baseline for observations is much shorter than for Bennu, and detection of YORP of a similar magnitude on Ryugu is not feasible. The asteroids also have different sizes: Ryugu, with a mean diameter of 850 m, is much larger than Bennu at 490 m. Ryugu thus has higher self-gravity and moment of inertia, rendering it less susceptible to YORP torques and rotation-related deformation than its smaller counterpart. The rotational and size properties of these two asteroids that are important controls on their sensitivity to YORP are summarized in Table 1.

The shapes of these asteroids may reveal information about their interior mechanical properties and implications for their dynamical evolution. Although some differences in the shapes of Ryugu and Bennu are immediately apparent, identification of important features by eye is challenging, and subsequent interpretation could thus be subjective. Here we perform spherical harmonic decompositions of the two asteroids' shapes to quantify the patterns at a variety of length scales. In section 2, we briefly describe the rotational stability of cohesionless rubble-pile bodies and relate the rotation periods to the long-wavelength shapes, so that we have a baseline equilibrium shape against which to compare the actual shapes of Bennu and Ryugu. In section 3, we present a detailed spherical harmonic analysis of the shapes of these two bodies, and in section 4 we relate their observed long-wavelength topography to their internal strengths and interior structures. In section 5, we discuss how observed topography contributes to spin evolution.

Because observations of a sustained increase in rotation rate exist for Bennu [START_REF] Nolan | Detection of Rotational Acceleration of Bennu Using HST Light Curve Observations[END_REF][START_REF] Hergenrother | The operational environment and rotational acceleration of asteroid (101955) Bennu from OSIRIS-REx observations[END_REF], but not for Ryugu, we take a deeper dive into the spin evolution of Bennu and show how its distinctive long-wavelength shape may be particularly susceptible to YORP spin-up.

Rotational Stability

Equilibrium Figures

The simplest model of a rotating figure is a Maclaurin spheroid, which is an oblate spheroid that arises when a fluid, self-gravitating body of uniform density rotates with a constant angular velocity. To first order, these approximations of density and angular velocity are appropriate for small rubble-pile asteroids. Although rubble piles are not fluids, the relationship can be generalized to cohesionless solids with an internal friction angle [START_REF] Holsapple | Equilibrium figures of spinning bodies with self-gravity[END_REF]. The maximum stable spin rate Ω is a function of the friction angle 𝜙 and the ratio 𝛼 of the lengths of the polar axis C and equatorial axis A:

Ω ! 𝜋𝐺𝜌 = 2𝛼√𝑚 + 2𝛼 ! 𝑚(1 -𝛼 ! ) "/! cos $% 𝛼 - 2(𝑚 + 2)𝛼 ! 𝑚(1 -𝛼 ! )
where 𝐺 is the gravitational constant, 𝜌 is the density, and

𝑚 = (1 + sin 𝜙) (1 -sin 𝜙)
As the friction angle increases, higher spin rates can be supported without deformation. In Figure 2, we plot the Maclaurin curves for several friction angles, illustrating the maximum stable dimensionless spin rate as a function of axis ratio. Over this, we plot the present states of Ryugu and Bennu, as well as three other representative asteroids for which we have high-resolution shape models, and which can be approximated as Maclaurin bodies. Because these bodies are not perfectly oblate, we have used the mean equatorial axis when calculating 𝛼. Not shown are corresponding curves for the minimum stable spin rates, which are relevant for extremely slow rotators.

The physical properties of the asteroids and their associated references are reported in Table 2. There are many other asteroids for which radar shape models exists (e.g., Walsh 2018); however, we have chosen the ones with high-quality image-based shape models available from the Planetary Data System (PDS) as the most relevant comparisons to Bennu and Ryugu. We have also included (66391) Moshup, the first known top-shaped asteroid [START_REF] Ostro | Radar Imaging of Binary Near-Earth Asteroid[END_REF], for comparison.

An object with the observed rotation rate and density of Bennu (Table 2) [START_REF] Lauretta | The unexpected surface of asteroid (101955) Bennu[END_REF]Barnouin et al., 2019a, Scheeres et al., 2019, Hergenrother et al., 2019;[START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF] requires 𝜙 > 17° in the absence of cohesion. Alternatively, cohesion c could provide some tensile strength, reducing or eliminating the internal friction required.

Internal friction is related to cohesion through the Factor of Safety [START_REF] Das | Principles of geotechnical engineering[END_REF], which is a ratio of the frictional or cohesive forces to the driving forces: 𝐹 &'()*(+, = tan 𝜙 tan 𝜃 ; 𝐹 )+-./(+, = 𝑐 𝜌𝑔ℎ sin 𝜃 where 𝑔 is the surface gravity, 𝜃 is the slope, and ℎ is the thickness of the regolith layer.

On Bennu, with a gravity of 6 micro-g and a density of 1.19 g cm -3 , 6 Pa of cohesion would be sufficient to maintain the shape without internal friction (the presence of a solid core at depth could reduce ℎ and therefore the required c), although evidence of mass migration at the surface [START_REF] Jawin | Global Patterns of Recent Mass Movement on Asteroid (101955) Bennu[END_REF]Barnouin et al., 2019a;[START_REF] Walsh | Craters, boulders and regolith of (101955) Bennu indicative of an old and dynamic surface[END_REF] suggests that cohesion is probably minimal. Some combination of these levels of internal friction or cohesion is required to prevent further flattening, despinning, and, potentially, binary fission.

Although Ryugu has a similar overall shape, its lower rotation rate indicates that it is much closer than Bennu to the Maclaurin curve (Figure 2), and only a very small amount of internal friction (𝜙 > 3°) or ~ 2 Pa of cohesion would be necessary to maintain its shape.

Not all asteroids are well approximated as a deviation from an oblate spheroid.

Similar relationships exist for prolate spheroids, albeit with more complicated functions of friction angle and axis ratio. The scaled spin for these bodies is:

Ω ! 𝜋𝐺𝜌 = 2 𝜆 0 𝐴 0 + 𝜆 1 𝛽 ! 𝐴 1 + 𝜆 2 𝛼 ! 𝐴 2 𝜆 0 + 𝜆 1 𝛽 !
where 𝛽 is the ratio between the short and long equatorial axes b and a. For a prolate body, 𝛼 = 𝛽. The constants 𝜆 ( have the values -1, 0, and m (as defined for the Maclaurin case), ordered according to the minimum, intermediate, and maximum stress directions.

The coefficients Ai are log functions [START_REF] Holsapple | Equilibrium figures of spinning bodies with self-gravity[END_REF]:

𝐴 ! = 𝑏 " %-4((𝑎 " -𝑏 " ) + 4𝑎 tanh #$ 1𝑎/((𝑎 " -𝑏 " )3 + 2𝑎 log 1-1/((𝑎 " -𝑏 " )3 + 𝑎 log (𝑎 " -𝑏 " ) 9 2(𝑎 " -𝑏 " ) % " 𝐴 & = 𝐴 ' = = -𝑎 %-4𝑎((𝑎 " -𝑏 " ) + 4𝑏 " tanh #$ 1𝑎/((𝑎 " -𝑏 " )3 + 2𝑏 " log 1-1/((𝑎 " -𝑏 " )3 + 𝑏 " log (𝑎 " -𝑏 " ) 9 4(𝑎 " -𝑏 " ) % "
The upper curve is determined by the lower of the solutions where the stress in the zdirection (along the rotation axis) is the most negative. The lower curve is the solution where the stress in the x-direction (along the prolate bulge) is the most negative.

One complexity is that there are no stable situations for strengthless prolate spheroids (except in the degenerate case of a sphere). We have illustrated this in Figure 3, superposed with values for five prolate asteroids for which high-resolution shape models are available (Table 2). For very low (but finite) internal friction angles (𝜙 < 6°), there are stable regions for nearly spherical and very elongated bodies (red curve in Figure 3), and at higher friction angles, there are both upper and lower bounds on the rotation rate.

Although neither Bennu nor Ryugu have a prolate shape, the rotational stability analysis of prolate bodies may still be instructive. Itokawa, for example, may be most similar to Bennu in terms of its internal properties. It is a rubble pile asteroid as well (Fujiwara et al., 2006), but, as shown in Figure 3, requires nearly 15° of internal friction to maintain this rotational state and shape. The variable densities of the two lobes [START_REF] Kanamaru | Density distribution of asteroid 25143 Itokawa based on smooth terrain shape[END_REF] may indicate the presence of some larger fragments in the interior that have inherent strength, consistent with findings for Bennu [START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF][START_REF] Scheeres | Heterogenous mass distribution of the rubble-pile asteroid (101955) Bennu[END_REF]. In contrast, Ryugu does not require much strength and may consist of relatively homogenous rubble throughout its interior. Likewise, the other prolate asteroids examined here have scaled spin rates that do not require substantial strength, although all prolate bodies require some finite internal friction or cohesion to maintain their shape.

Finite element analysis to determine the cohesion necessary to prevent failure of asteroids under rotation results in failure mode diagrams (Hirabayashi and Scheeres, 2016). An analysis of these failure mode diagrams has been done for several contact-binary, elongated, and spheroidal asteroids, including Bennu and Itokawa [START_REF] Hirabayashi | Rotationally induced failure of irregularly shaped asteroids[END_REF]. Assuming friction angles of 35° (common for granular materials), these bodies would require cohesion to prevent failure once the the peak centrifugal stress balances the local gravity. This occurs at somewhat faster rotation periods than at present (3.7 h and 5.73 h, for Bennu and Itokawa respectively). At faster spin rates, tens of Pa of cohesion would be required to prevent failure [START_REF] Hirabayashi | Rotationally induced failure of irregularly shaped asteroids[END_REF].

Deviation from Equilibrium Figures

Having established the range of equilibrium figures (i.e., the shapes these bodies would take on if they were fluids or frictionless granular material), it is instructive to examine their deviations from these idealized surfaces (i.e., the difference between their real shapes and the black curve in Figure 2). For each body, we took the equatorial radius (257.5 m for Bennu (Barnouin et al., 2019); 501 m for Ryugu [START_REF] Watanabe | Hayabusa2 arrives at the carbonaceous asteroid 162173 Ryugu -a spinning top-shaped rubble pile[END_REF]) defined a reference spheroid consistent with the axis ratio a given in Table 2. In Figure 4, we show the shape models of Bennu (derived from ranges obtained by OLA) and Ryugu (derived from SPC), colored according to the height of the surface above a reference spheroid consistent with the axis ratio.

When scaled by their respective radii, the deviations of Bennu and Ryugu from their respective equilibrium figures are similar. The most prominent features that deviate from the equilibrium figures on these bodies are their equatorial bulges and their equatorial ridges. Although similar-sounding, these equatorial features have different origins and expressions. The equatorial bulge arises through centrifugal force that is a natural consequence of the body's rotation. A fluid body in hydrostatic equilibrium deforms to an oblate (Maclaurin) spheroid. This feature would arise on a strengthless body, though strength could permit some deviation from the equilibrium surface. In contrast, the ridge is a much narrower, topographic feature superposed on top of the bulge. It is completely supported by internal strength and is absent in the hydrostatic case.

As viewed from the pole, Bennu's equatorial ridge shows a squarish outline (see Figure 1a). This deviation from circularity is caused by four north-south longitudinal ridges (Barnouin et al. 2019). These ridges extend from pole to pole, although two of these are obscured in the southern hemisphere by surface material [START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF]. These ridges are broad and contribute to the overall shape of Bennu rather than appearing as spines on top of the background shape. The squarish outline of Bennu's equator is confirmed in The deviation from the idealized surface can alternatively be described in terms of the tilt of the surface. The term "tilt" here represents the angle between the normal to a facet on the surface and the radial direction at that point. The tilt is thus a purely geometric measure, in contrast to "slope," which characterizes the orientation of a surface facet with respect to the surface acceleration direction. In Figure 5, we show the tilts of the closest-fit Maclaurin spheroid consistent with Bennu's and Ryugu's observed densities and rotation rates (left) and the tilts of the shape models (right). The Maclaurin spheroids are symmetric about the rotation axis and only have tilts in the north-south direction. For consistency, we

show the north-south component of the tilt for the actual shape models as the most relevant and these regions are confined to the flanks of the equatorial ridge, which is far less defined than on Ryugu. The tilts show a much more gradual transition from the flanks to the peak, and the peak is broad. The larger tilts on Ryugu are even more pronounced when compared to the tilts on the equivalent Maclaurin spheroid. Because Ryugu has a slower rotation rate, it is less oblate, and the peak tilt on the spheroid is only half that of the equivalent spheroid for Bennu.

Spherical Harmonic Analysis

We performed spherical harmonic decomposition of the shape models of Bennu (SPC/OLA combined, v34) and Ryugu (SPC, v20190802) to interpret the geological significance of their shapes. Because the two asteroids are roughly a factor of two different in diameter, we used shape models with the same number of facets for each body (49,000) rather than the same pixel scale. That is, the facets on each body are a similar fraction of that body's surface area. The facets on Ryugu are therefore twice as large in an absolute sense than those on Bennu. In Figure 7, we plot the orthonormalized RMS amplitude of all zonal (black), sectoral (red), and tesseral (blue) terms at a given degree (ℓ). On both bodies, the zonal terms (components that vary only with latitude) are particularly strong at ℓ = 2 due to the equatorial bulge, and at ℓ = 4, due to the equatorial ridge, that is characteristic of top-shaped asteroids.

On Bennu, the zonal powers (components that vary only with latitude) at ℓ = 6 and 8 are indicative of sharp regional changes in the slope, such as terraces (Barnouin et al., 2019b;[START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF]. Strong sectoral terms at ℓ = 4 reflect the aforementioned high-standing longitudinal ridges (Barnouin et al., 2019a;[START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF]. of hemispherically symmetric shape models of Bennu and Ryugu, and we compared them to each other and to the actual shapes of the asteroids.

In Figure 8, we show the sectoral harmonics (terms varying only with longitude)

for the actual shape of Bennu, the northern hemisphere, and the southern hemisphere.

Although the ℓ = 4 sectoral term is strongest in the north, the power at this wavelength does not vary much among the models. As reported by [START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF], one reason that the ridges are less apparent to the eye in the southern hemisphere is that surface material fills in some of the sectors between the ridges to a greater degree than in the north. This subdues the visual prominence of the longitudinal ridges; although they are present in the south, they stand less high above the background surface. This contributes to the power at ℓ = 2, which in the southern hemisphere is roughly equivalent to ℓ = 4 [START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF].

Another important variation is seen at ℓ = 5, with nearly an order of magnitude difference between the hemispheres. A closer inspection of the southern hemisphere suggests a component of five-fold (rather than four-fold) symmetry. A geological interpretation consistent with both the surface observations and the spherical harmonic decompositions is that in the southern hemisphere, one of the longitudinal ridges meanders east and west from the equator to the pole. Although there are four ridges, the spacing between them varies, shifting some of the power from degree 4 to adjacent degrees.

Ryugu does not show consistent power between the hemispheres at ℓ = 4 or at any other wavelength. The northern hemisphere is dominated by an ℓ = 2 pattern in the shape (an elongation in one direction), whereas the southern hemisphere shows a spike at ℓ = 4 that reflects the boulder distribution. At shorter wavelengths, the power in the spherical 295 harmonics in each hemisphere is essentially independent of the other, and we interpret this 296 These examples demonstrate the power of analyzing the shape in the spectral domain. Patterns are revealed in the spherical harmonics that are less obvious by inspection of the shape model that once known, can guide further geological analysis.

Internal Properties

The large-scale surface topography and rotation rates provide insight to the interior structures of the asteroids. Although both objects appear to be unconsolidated rubble piles, Bennu cannot be completely strengthless. As discussed above, Bennu's rotation rate is significantly faster than any hydrostatic body could sustain (Figure 2).

Therefore, Bennu must have some internal stiffness (Barnouin et al., 2019a).

Beyond this broad observation, knowledge of the interior structure remains somewhat speculative. However, we can use the constraints we do have to construct a base model that is consistent with the existing observations. One such possibility is that the longitudinal ridges may be the surface expression of an arrangement of about four large (~100-m) fragments that make up the core of the asteroid, which is filled in and covered by smaller rubble. Studies of rotational failure of rubble piles (Zhang et al., 2018) have found that a common result is for the body to fail in a wedge-shaped pattern, with the number of wedges controlled by the cohesion of the material. Although even homogenous interiors can fail in a wedge-shaped pattern, having some coherent large fragments in the interior could simulate a high cohesion.

We have illustrated this scenario in Figure 9. Here, the large clasts are prolate and would naturally arrange themselves into a cluster, all oriented the same direction. These large fragments are effectively zones of extremely high cohesion and would direct failure to occur primarily in a ℓ = 4 pattern. The fragments would anchor the wedges, and the longitudinal ridges would correspond to their centers [START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF]. Although Figure 9 is conceptual, we can compare characteristics to the interior structure inferred from the gravity solution from OSIRIS-REx observations. The above scenario contains an underdense core and equator, where the smaller rubble and void spaces are most prevalent. In that regard, it is consistent with the gravity field of Bennu, which points to a heterogeneous mass distribution [START_REF] Scheeres | Heterogenous mass distribution of the rubble-pile asteroid (101955) Bennu[END_REF].

If these larger clasts have some inherent tensile strength, they would resist deformation themselves, and could lock up the smaller rubble, limiting deformation of the asteroid overall. Surface landslides would still occur. It is possible that terraces on Bennu (Barnouin et al., 2019b) are the expression of downslope migration of material as the increasing rotation rate mobilized it. We note that the scenario presented here is a hypothesis, and that alternative models to explain the shape could be proposed.

The fact that terraces are not observed on Ryugu [START_REF] Matsumoto | Improving Hayabusa2 trajectory by combining LIDAR data and a shape model[END_REF] could simply be a consequence of Ryugu's slower rotation. However, if Ryugu previously had a higher spin rate, that could have triggered the formation of terraces during that era, which may have remained after spin-down. Thus, the absence of terraces may be an indication that the mechanical response of the surface on Ryugu is different than on Bennu. This, in addition to the lumpier shape of Ryugu, points to a different configuration of large central clast; to the possibility that Ryugu has no larger pieces in the center and is uniform rubble throughout; or to an entirely different mixture. For example, Ryugu's western bulge [START_REF] Hirabayashi | Rotationally induced failure of irregularly shaped asteroids[END_REF] may indicate a large fragment in the shallow subsurface rather than the center.

Spin Evolution

The configuration of rubble in the asteroid interior and the distribution of material on the asteroid surface may have implications for the spin evolution of asteroids such as Bennu and Ryugu. For example, the magnitude of YORP-induced torque is sensitive to the orientation of blocks on the surface [START_REF] Rubincam | Radiative Spin-up and Spin-down of Small Asteroids[END_REF][START_REF] Statler | Extreme sensitivity of the YORP effect to small-scale topography[END_REF]. Using the shape models of Bennu (OLA v16) and Ryugu (v20190802), and following [START_REF] Rubincam | Radiative Spin-up and Spin-down of Small Asteroids[END_REF], we compute the amount of solar energy on each facet of the shape model:

𝑆𝑑𝐴 = D𝑟 3 F • 𝑁 I J𝐹 / 𝑑𝐴
where S is the insolation, dA is the area of the facet, 𝐹 / is the solar power per unit area, and 𝑟 3 F • 𝑁 I is the component of the surface normal of that facet in the direction of the Sun.

We assume the facet is in radiative steady state, and following Lambert's law, the net force per unit area 𝑓 ⃑ on the facet is:

𝑓 ⃑ = -2 𝑆 𝑁 I 𝐹 / 3𝑐
where c is the speed of light. The torque on the facet is a product of the applied force and the distance from the center of mass, 𝑟 ⃑.

𝑑𝜏 ⃑ = 𝑟 ⃑ × 𝑓 ⃑ 𝑑𝐴

We sum over all the facets to determine the net torque on the body. We then rotate the body 5° about its axis, identify the new subsolar point, and recalculate. The calculation is repeated every 5° of rotation to determine the net and average torque over one full rotation. We repeat this iteration for every 5° of true anomaly to determine the net and average torque over one full orbital period.

In Figure 10, we show the total YORP torques about the rotational axis averaged over the body and over one rotation as a function of the true anomaly (orbital position)

for Bennu and Ryugu. The rotational torque on Ryugu oscillates over the course of one orbital period, whereas the rotational torque on Bennu is consistently in one direction.

Although the magnitude of the torque on Ryugu is ~3 times that on Bennu, Ryugu's moment of inertia is roughly 20 times that of Bennu, so the net rate of predicted change in angular velocity is substantially larger on Bennu than on Ryugu.

Although the YORP effect may be sensitive to small-scale topography [START_REF] Statler | Extreme sensitivity of the YORP effect to small-scale topography[END_REF], if the distribution of blocks on the surface has a truly random orientation, then the torques from individual surface facets should cancel each other out. Over a long timescale (greater than an orbital period), the average torque due to small-scale features on a rubble pile should average to zero. For this reason, it has been suggested that long-wavelength topography is the driver of YORP torques [START_REF] Rubincam | Radiative Spin-up and Spin-down of Small Asteroids[END_REF]. Thus, a sustained change in rotation rate due to the YORP effect would require a systematic preference in the orientation of the topography that is not likely to be caused by small-scale processes.

However, recent work (e.g., [START_REF] Statler | Extreme sensitivity of the YORP effect to small-scale topography[END_REF][START_REF] Rozitis | The influence of rough surface thermal-infrared beaming on the Yarkovsky and YORP effects[END_REF][START_REF] Golubov | Tangential component of the YORP effect[END_REF][START_REF] Nolan | Detection of Rotational Acceleration of Bennu Using HST Light Curve Observations[END_REF] have shown that small-scale topography may be potentially significant, and we explore wavelength dependence in the following section. of significant YORP spin-up, lacks these ridges, and the rubble is distributed in a more random configuration, which is less susceptible to YORP spin-up.

To test this hypothesis, we decomposed the full shape model of Bennu (SPC/OLA v34) into spherical harmonics out to degree and order 48 and created a series of shape reconstructions containing only selected spherical harmonic components. We then repeated our torque calculation on the reconstructed shape models to determine which spherical harmonic components were the dominant contributors to the spin evolution. The torque computed on the appropriate partial reconstruction should approximate that on the full shape model.

Torque is a vector and has a rotational component (aligned with the rotational axis), which serves to change the body's rotation rate, and transverse components (perpendicular to the rotational torque) that change the body's obliquity. Because Bennu's obliquity is nearly 180°, the rotation axis is almost aligned with the direction of the solar radiation. The zonal terms (which vary only with latitude), therefore, contribute most to the transverse torque, and have a minimal effect on the rotational component. Because the spin is controlled by the rotational torque, the most relevant spherical harmonics would be the sectoral terms, which vary only with longitude. The most prominent feature in this category are the longitudinal ridges, which are dominated by degree and order 4. Our first partial reconstruction contains only the degree and order 4 term (superposed on a sphere of the mean radius). We find that this shape reconstruction produces only a fraction of the torque as from the full shape model (Figure 12; compare black and red curves). The daily averaged rotational torque on each facet on this shape model is shown in Figure 13a. This result has a straightforward explanation. A net torque about the rotation axis requires that solar re-emission be preferentially oriented in one direction. If the body is symmetrical about the rotation axis, the torque sums to zero. If the longitudinal regions were a pure sectoral harmonic, then each side of the ridge would re-emit sunlight equally efficiently, and the torque applied to a ridge in the morning would be canceled by that applied in the afternoon. A shape model reconstruction with multiple components is therefore required to break the symmetry. In order to get this type of asymmetry, combinations of degrees much higher than the wavelength of the feature are required; this is analogous to the Gibbs' phenomena for Fourier series.

We next constructed a Bennu shape model with the sectoral terms at degrees 2, 3, 4, and 7, the four largest such components. The total rotational torque on this shape model is only ~25% of the total on the full shape model (Figure 12, green curve), indicating that although these four components may be dominant, there is substantial contribution from other terms. The map of the torque computed on this model is shown in Figure 13b. Thus, although the long-wavelength features such as the longitudinal ridges may enable a systematic YORP spin-up, by themselves they cannot explain the magnitude of the net torque. We created another partial reconstruction that included all the sectoral components (out to degree 48; Figure 13c); it only results in ~50% of the total torque (Figure 12, orange curve), meaning that there is significant contribution from the tesseral terms as well. Table 3 gives the globally averaged rate of change in rotation rate and obliquity, averaged over a Bennuvian year for each shape reconstruction, demonstrating that as additional terms are included, the total YORP effect increases. This result suggests that smaller-scale topography (< 15 m, ℓ > 100) is important to the full solution and an important driver of YORP on Bennu. The YORP torques are only due to an effective area that is a fraction of the surface area because it is caused only by asymmetries. The effective area for YORP can increase as finer scales are considered if the topography is non-random and the asymmetries do not cancel each other.

The torque analysis shown here is valid only for the current shape of Bennu.

Assuming that this shape remains constant, then the position of Bennu on the stability curves in Fig. 2 will continue to migrate upwards on the plot. If the observed rate of increase in the spin rate also remains constant, then in ~600 Myr, the spin rate will have

(N m) (s -2 ) (° day -2 ) (4,4) -3.61×10 -18 -1.54×10 -6 1.92×10 -18 (4,4); (7,7) -3.65×10 -18 -1.56×10 -6 2.74×10 -19
(2,2); (3,3); (4,4); (7,7) -4.99×10 -18 -2.13×10 -6 -3.36×10 -18

All sectorals (ℓ<48) -1.04×10 -17 -4.45×10 -6 -5.92×10 -18

Full shape -2.60×10 -17 -11.12×10 -6 -2.31×10 -13 increased to a level where no amount of internal friction would be sufficient to maintain a rubble pile against disruption. Such a catastrophic scenario is unlikely. As the spin increases slightly, the shape of the asteroid will be modified, and the rotational potential will also increase. In the absence of internal strength, this potential serves to increase the oblateness of the body, increasing the moment of inertia. As the oblateness increases, the spin rate will go down by conservation of angular momentum of the system, preventing unchecked spin-up (e.g., [START_REF] Walsh | Rotational breakup as the origin of small binary asteroids[END_REF][START_REF] Walsh | Physical Characterization and Origin of Binary Near-Earth Asteroid (175706) 1996 FG3[END_REF][START_REF] Hirabayashi | Stress and failure analysis of rapidly rotating asteroid (29075) 1950 DA[END_REF][START_REF] Scheeres | Landslides and mass shedding on spinning spheroidal asteroids[END_REF].

In addition to tilts of the existing surface facets driven by this change in shape, any rubble sitting on the surface with minimal cohesion will be disturbed and jostled into new orientations. If these orientations are random, then these blocks may at times become more susceptible to YORP, and at other times, less susceptible. Over long timescales, the body would experience a YORP "random walk" rather than a YORP spin-up [START_REF] Cotto-Figueroa | Coupled spin and shape evolution of small rubble-pile asteroids: Self-limitation of the YORP effect[END_REF], wherein minor mass movements result in random shifts in the orientation of the surface. The net effect of YORP would be to increase or decrease the rotation rate of the asteroid in a stochastic fashion. If, however, there are large-scale structures (e.g., the longitudinal ridges) that control the distribution and orientation of the rubble, then it may be susceptible to prolonged spin-up or spin-down, and this would be deterministic.

A further caveat to the analysis presented here is that we have considered only the normal torque due to YORP. [START_REF] Golubov | Tangential component of the YORP effect[END_REF] have suggested that asymmetric re-radiation from smaller (few centimeters-sized) rocks could create a substantial component of torque normal to the surface, called "tangential" YORP, modifying the YORP in certain circumstances. Although the images of Ryugu and Bennu can resolve features of a few centimeters in size, creating a global shape model on this scale is not currently feasible. Surface roughness (on a scale as fine as millimeters) can also dampen the degree of rotational acceleration. Radiation off such small-scale features is similar to scattered light. Identification of the dominant scattering direction is needed to estimate the influence of YORP at the finest scales. [START_REF] Rozitis | The surface roughness of (433) Eros as measured by thermal-infrared beaming[END_REF] found that the degree of rotational acceleration due to the YORP effect can be dampened by a factor of ~1/3 through the thermal beaming effect, in which multiple scatterings of radiation between surface elements can absorb more solar radiation than a flat surface, and reflect much of it back towards the Sun.

Conclusions

We performed a topographic analysis of the shapes of the top-shaped rubble-pile asteroids Ryugu and Bennu, which were each recently visited. Although the two bodies appear similar, spherical harmonic analysis of the shapes demonstrates differences, in particular a much sharper equatorial ridge on Ryugu than on Bennu, and longitudinal ridges and terraces on Bennu that are absent on Ryugu.

We find that both objects are rotating at a rate exceeding that at which a Maclaurin spheroid would be stable, indicating that some degree of internal friction or cohesion is necessary to maintain their current shapes. Bennu rotates considerably faster than Ryugu and requires a friction angle of at least 17° in the absence of cohesion to maintain itself against despinning or disruption. In contrast, Ryugu requires only ~3° of internal friction to be stable against the rotation. This result is reflected in the differences in the tilt maps of each asteroid. Ryugu on average has higher tilts than Bennu and a more prominent equatorial ridge, suggesting that the original top shape has been less modified by, for example, rotational migration than has Bennu's. The interior strength inferred here for Bennu (>17° internal friction) is similar to that of Itokawa, another rubble-pile asteroid (Fujiwara et al., 2006) of similar size to Bennu. The other prolate asteroids studied here do not require similar levels of strength (though nothing precludes their having it).

The longitudinal ridges on Bennu may indicate some large-scale strength and structure in the interior and hint at a failed disruption event earlier in the body's history [START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF]. The longitudinal ridges may themselves enable YORP spin-up (or spindown), although on their own they are not sufficient to achieve this. The torque computed on partial shape reconstructions shows that smaller-scale topography (<15 m) is important.

Sustained YORP spin-up would require that the smaller rubble be either systematically oriented in a particular direction or non-uniformly rather than randomly distributed, and this requires models of the deformation of the asteroid as a result of the rotational potential.

Because a given topographic feature creates more torque the further it is from the origin, small-scale features on the ridges are more important than those between the ridges. Thus, the ridges are critical in directing the YORP torque, even if they themselves only contribute a fraction of the total. A sustained period of spin-up would require the body to have sufficient internal strength that it would not substantially deform and redistribute surface rubble in response to small increases in rotation rate. The fact that Ryugu does not exhibit a similar rotational evolution to Bennu may point to either a lack of topographic features to promote the YORP effect, a lack of strength to sustain it, or both. However, Ryugu has a much slower rotation period and larger size than Bennu, which decreases the importance of shape to the rotational history. A change in Ryugu's rotation rate due to YORP may simply not be detectable in the available data. Given these factors, we refrain from drawing conclusions on the effect of shape on the YORP effect for Ryugu.

Figure 1 :

 1 Figure 1: Example shape models of Bennu (a) and Ryugu (b), each with ~800,000 facets. Views are shown from each principal axis. Bennu model v20 was determined from laser altimetry data acquired by OLA.Ryugu model v20190802 was determined using stereophotoclinometry from imaging data collected by Hayabusa2[START_REF] Watanabe | Hayabusa2 arrives at the carbonaceous asteroid 162173 Ryugu -a spinning top-shaped rubble pile[END_REF]. For scale, the mean equatorial diameters of Bennu and Ryugu are 557 m and 1.02 km, respectively.

Figure 2 :

 2 Figure2: Rotational stability for cohesionless, solid, oblate spheroids for a wide range of rotation rates, oblateness, and internal friction. Each curve describes the limits of the allowable dimensionless rotation rate as a function of the axis ratio. The crosses mark the dimensionless spin rates and axis ratios consistent with observed oblate asteroids.

Figure 3 :

 3 Figure3: Rotational stability for cohesionless, solid, prolate spheroids for a wide range of rotation rate, prolateness, and internal friction. Each curve describes the limits of the allowable dimensionless rotation rate as a function of the axis ratio. Two curves of the same color denote the upper and lower bound of rotational stability and the indicated friction angle. Note that the stability region at a friction angle of 5° is discontinuous. The crosses mark the dimensionless spin rates and axis ratios consistent with observed prolate asteroids.

Figure 4 :

 4 Figure 4: Deviation of Bennu's (a) and Ryugu's (b) shape models from the reference (i.e., closest-fit Maclaurin) spheroids, consistent with the asteroids' observed densities and rotation periods. Left: Equatorial view. Right: Polar view. Note that the color scales for Bennu and Ryugu have different ranges.

Figure 4 .

 4 Figure 4. The red zones at the equator and yellow zones in mid-latitudes indicating higher

Figure 5 :Figure 6 :

 56 Figure 5: Component of tilts (angle between the normal to the surface and the direction to the center) in the north-south direction from closest-fit Maclaurin spheroids consistent with Bennu's (a) and Ryugu's (b) observed density and rotation period (left) and from the shape model (right). For both asteroids, a shape model (Bennu OLA v20; Ryugu v20190802) with 49,000 facets is shown. The maximum tilt shown is capped at 50° to highlight the average tilt distribution, but tilts exceed this in places on both asteroids.

  251

Figure 7 :

 7 Figure 7: Spherical harmonic decompositions of the shapes of Bennu (a) and Ryugu (b), showing the total degree strength of the zonal, tesseral, and sectoral components on each body. A power-law fit (c.f., Vening-Meinesz, 1951) is also shown for comparison.

Figure 8 :

 8 Figure 8: RMS amplitude in the sectoral harmonics in the OLA shape model (v14) for Bennu and the SPC shape model for Ryugu. For each body, the global results (black), northern (red) and southern (blue) hemispheres are shown.

Figure 9 :

 9 Figure 9: Possible internal structure of Bennu viewed from the equator (top) and the pole (bottom). Four large prolate clasts form the bulk of the interior, and are filled in by smaller rubble.

Figure 10 :

 10 Figure 10: Rotational component of the YORP-induced torque on Bennu and Ryugu. In both cases, the highest-resolution shape models (with 3 million facets) were used.

Figure 11 :

 11 Figure 11: Reconstruction of Bennu shape model out to degree and order 4 as seen from the +x (a), -x (b), +y (c), -y (d), +z (e), and -z (f) axes; to degree and order 8 as seen from the +x (g), -x (h), +y (i), -y (j), +z (k), and -z (l) axes.

Figure 12 :

 12 Figure 12: Globally averaged rotational component of YORP-induced torque as a function of orbital position on partial shape reconstructions of Bennu based on selected spherical harmonic terms. The (4,4) curve and (4,4) + (7,7) are nearly coincident.

Figure 13 :

 13 Figure13: Daily averaged rotational torque (at a true anomaly of 180°) on a partial shape reconstruction of Bennu consisting of only the degree 0 and degree 4, order 4 components of topography (a); the degree 0 and degree 2, 3, 4, and 7 sectoral components of topography (b); and the degree 0 and all sectoral components of topography out to degree 48 (c) plotted in map projection (i.e., mean torque on each facet of the shape model, integrated over one full rotation).

Table 1 :

 1 Global physical properties of Bennu and Ryugu

	Physical Property		Bennu	Ryugu	Units
	Rotation Period	P	4.296057±0.000002 a	7.63262±0.00002 c	h
	Mass	m	7.329±0.009×10 10 b	4.50±0.06×10 11 c	kg
	Density	r	1190±13 a	1190±20 c	kg m -3
	Polar moment of Inertia Izz	26780 b	--	m 2
	Major axis	a	505.56±0.10 a	1023±2 c	m
	Median axis	b	492.4±0.18 a	986±4 c	m
	Minor axis	c	457.38±0.24 a	438±2 c	m
	Surface gravity	g	5.95±0.01×10 -5 (mean) a	1.403×10 -4 (equator) c	m s -2
				1.473×10 -4 (poles) c

a Barnouin et al. (2019a) b Scheeres et al. (2019) c Watanabe et al. (2019)

Table 2 :

 2 Physical properties relevant to rotational stability of 10 asteroids, here approximated as either oblate (Maclaurin) or prolate spheroids. Asteroids denoted by an asterisk are better approximated as tri-axial ellipsoids, but for this comparison have been classified as oblate or prolate. a, ratio of the lengths of the polar and equatorial axes. W, maximum stable spin rate. r, density.

	Asteroid	Spheroid	a	W (s -1 )	Period	r	Reference
					(hr)	(kg m -3 )
	(4) Vesta	Maclaurin	0.8242 3.27´10 -4	5.342 3.456	Gaskell (2013)
						´10 3
	(21) Lutetia	Maclaurin* 0.7182 2.14´10 -4	8.166 3.4´10 3	Farnham (2013)
	(243) Ida	Prolate	0.3679 3.77´10 -4	4.63	2.6´10 3	Stooke (2002)
	(253)	Prolate	0.7121 4.18´10 -6	417.7 1.3´10 3	Stooke (2002)
	Mathilde
	(433) Eros	Prolate	0.6512 3.31´10 -4	5.27	2.67´10 3	Gaskell (2008)
	(951) Gaspra Prolate	0.5330 2.48´10 -4	7.042 2.7´10 3	Stooke (2002)
	(25143)	Prolate*	0.4701 1.44´10 -4	12.132 1.95´10 3	Gaskell et al. (2008b)
	Itokawa
	(66391)	Maclaurin	0.8907 6.31´10 -4	2.765 2´10 3	Ostro et al. (2006)
	Moshup
	(101955)	Maclaurin	0.8874 4.07´10 -4	4.296 1.19´10 3	Barnouin et al.
	Bennu						(2019a)
	(162173)	Maclaurin	0.9317 2.29´10 -4	7.627 1.27´10 3	Watanabe et al.
	Ryugu						(2019)

Table 3 :

 3 YORP-induced change in rotation rate and obliquity for Bennu

	Components	Rotational acceleration	Obliquity torque

Acknowledgments

This material is based upon work supported by NASA under Contract NNM10AA11C issued through the New Frontiers Program. The OSIRIS-REx Laser Altimeter build and Canadian science support were provided by a contract with the Canadian Space Agency. P.M. and Y.Z. acknowledge funding support from the French space agency CNES, from the European Union's Horizon 2020 research and innovation programme under grant agreement no. 870377 (project NEO-MAPP) and from the Academies of Excellence on Complex Systems and Space, Environment, Risk and Resilience of the Initiative d'EXcellence "Joint, Excellent, and Dynamic Initiative" (IDEX JEDI) of the Université Côte d'Azur. Y. Z. acknowledges funding from the Université Côte d'Azur "Individual grants for young researchers" program of IDEX JEDI.

We thank two anonymous reviewers for insightful reviews which helped to improve the manuscript clarity and quality. We are grateful to the entire OSIRIS-REx and Hayabusa2 Teams for making the encounters with Bennu and Ryugu possible. This work made use of the Small Body Mapping Tool (SBMT), a free spacecraft data visualization and analysis tool developed at the Johns Hopkins University Applied Physics Laboratory (Ernst et al., 2018); visit sbmt.jhuapl.edu to learn more and for access to shape models of Bennu.

Apart from the top-like shape and the oscillation in the zonal harmonics, Ryugu differs from Bennu in this analysis. The ℓ = 4 sectoral component is much weaker on Ryugu, and longitudinal ridges are not observed [START_REF] Matsumoto | Improving Hayabusa2 trajectory by combining LIDAR data and a shape model[END_REF]. Viewed from above the pole, the profile of Ryugu is more circular. The strongest non-zonal contributions are the tesseral terms at ℓ = 3, indicating some large-scale asymmetry, which is prominent in topography relative to a reference shape model constructed from the even zonal harmonics [START_REF] Matsumoto | Improving Hayabusa2 trajectory by combining LIDAR data and a shape model[END_REF]. The "Western bulge" centered at 225°E, 10°S [START_REF] Hirabayashi | Rotationally induced failure of irregularly shaped asteroids[END_REF], the Tokoyo/Horai Fossae system in the southern hemisphere and a large plain in the northwestern mid-latitudes [START_REF] Watanabe | Hayabusa2 arrives at the carbonaceous asteroid 162173 Ryugu -a spinning top-shaped rubble pile[END_REF] are important contributors to this shape. At smaller scales, terraces are not evident; regolith run-ups and imbricated boulders are observed [START_REF] Sugita | The geomorphology, color, and thermal properties of Ryugu: implications for parent-body processes[END_REF].

On both bodies, zonal terms show a sharp dichotomy between the odd and even terms. By itself, the strong power in the even zonal harmonics and the relatively weak power in the odd terms does not necessarily indicate symmetry about the equator. In fact, broad hemispheric differences can be seen in the shape of Bennu. The southern hemisphere in particular appears rounder and more flattened near the pole, while the longitudinal ridges appear more prominently in the northern hemisphere [START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF]. As described for Bennu in [START_REF] Daly | Hemispherical Differences in the Shape and Topography of Asteroid (101955) Bennu[END_REF], splitting the shape model at the equator can shed light on other contributions. In this approach, two new shape models are then created by reflecting each hemisphere about the equator, forming new asteroid shapes composed of either two northern or two southern hemispheres, thus enforcing hemispheric symmetry in each model. Using this technique, we created and performed spherical harmonic decomposition

Long-wavelength topography and the spin up of Bennu.

We can examine the effects of the longest wavelengths by decomposing a shape model into its spherical harmonic components and then creating partial reconstructions of that shape out to a chosen spherical harmonic degree and order. Ground-based, Hubble Space Telescope, and OSIRIS-REx spacecraft observations of Bennu have shown that its rotation rate has been increasing since 1999 [START_REF] Hergenrother | Lightcurve, color and phase function photometry of the OSIRIS-REx target asteroid (101955) Bennu[END_REF], Nolan et al., 2013;[START_REF] Lauretta | The OSIRIS-REx target asteroid (101955) Bennu: Constraints on its physical, geological, and dynamical nature from astronomical observations[END_REF][START_REF] Nolan | Detection of Rotational Acceleration of Bennu Using HST Light Curve Observations[END_REF][START_REF] Hergenrother | The operational environment and rotational acceleration of asteroid (101955) Bennu from OSIRIS-REx observations[END_REF]. Similar rotation rate changes have not been observed for Ryugu, and would not be expected because of the shorter observational baseline. Therefore, in the following analysis, we focus exclusively on Bennu. We used the 12-m-resolution v34 shape model of Bennu generated from the combination of SPC and OLA data. In Figure 11, we show reconstructions of Bennu out to degrees 4 and 8. The ℓ = 4 reconstruction accentuates the top-like shape in the equatorial views (panels a to d). The profile of the equator as seen in the polar views (panels e and f) is noncircular. The actual profile is intermediate between these, where the "corners" indicate the longitudinal ridges. The degree 8 reconstruction (the first harmonic of degree 4) in Figure 11g-l shows that an octagonal fit is better and that there is a weaker set of longitudinal features at degree 8 contributing to the shape.

We hypothesize that the longitudinal ridges observed on Bennu may promote spinup preferentially in one direction about the rotation axis, like the blades on a windmill. Not only do these ridges constitute systematic long-wavelength topography, but they also control the distribution of smaller rubble. In contrast, Ryugu, which does not exhibit signs proposed AIDA mission target 65803 Didymos: I. Discrete cohesionless granular physics model, Icarus, 294, 98-123. Zhang, Y. et al. (2018), Rotational failure of rubble-pile bodies: influences of shear and cohesive strengths., Ap. J. 857, 15.


Arnaud Grivet Sébert
email: arnaud.grivetsebert@gmail.com

Nicolas Maudet
email: nicolas.maudet@lip6.fr

Patrice Perny
email: patrice.perny@lip6.fr

Paolo Viappiani
email: paolo.viappiani@lip6.fr

Preference Aggregation in the Generalised Unavailable Candidate Model

Keywords: Computational Social Choice, Preference Aggregation, Unavailable Candidate Model, Polynomial-Time Approximation Scheme

 have proposed to reject this hypothesis. In particular, the unavailable candidate model of Lu and Boutilier [15] considers voting situations in which some candidates may not be available and focuses on minimising the number of binary disagreements between the voters and the consensus ranking. In this paper, we extend this model and present two new voting rules based on a finer notion of disagreement, called dissatisfaction. The dissatisfaction of a voter is defined as the disutility gap between its preferred available candidate and the candidate elected by the consensus ranking. In the first approach, called ex ante dissatisfaction rule, the disutility is independent of the set of available candidates whereas the second approach, called ex post dissatisfaction rule, assumes that the disutility depends on which candidates are actually available. We provide several results for the two rules. On the one hand, we show that the ex ante rule actually coincides with standard positional scoring rules; therefore, a consensus ranking can be computed in polynomial time. On the other hand, we exhibit strong links between ex post rule and Kemeny rule and we provide a polynomial-time approximation scheme (PTAS) for the ex post problem.

Introduction

Traditional social choice theory assumes that the set of candidates is well known before voting takes place. This assumption is not always valid especially in computer science applications (such as recommender systems, decision aid tools, electronic commerce applications) but also in more traditional settings, such as choosing a candidate for a job (a candidate may accept a different job after the hiring committee made its decision). In recent years, several approaches have been proposed to address the problem of candidates' unavailability, in particular within computational social choice [START_REF] Brandt | Handbook of computational social choice[END_REF]. Among these approaches, strategic candidatures have been studied extensively [START_REF] Dutta | Strategic candidacy and voting procedures[END_REF][START_REF] Dutta | Voting by successive elimination and strategic candidacy[END_REF][START_REF] Lang | New results on equilibria in strategic candidacy[END_REF]. Some works have dealt with the problem of finding robust winners when considering the addition of new candidates [START_REF] Chevaleyre | New candidates welcome! possible winners with respect to the addition of new candidates[END_REF] or in a context where it is possible to "query" the availability of the candidates [START_REF] Boutilier | Robust winners and winner determination policies under candidate uncertainty[END_REF]. Oren et al. [START_REF] Oren | Efficient vote elicitation under candidate uncertainty[END_REF] study how many candidates the voters have to rank to ensure the true winner with high probability despite the unavailability hypothesis. Top-k voting may also be a way to deal with unavailability in [17].

An approach of particular interest is the unavailable candidate model (UCM) proposed by Lu and Boutilier [START_REF] Lu | The unavailable candidate model: a decision-theoretic view of social choice[END_REF]. It assumes that candidates may become unavailable after voters expressed their preferences; therefore there is a need to make decisions in the face of uncertain candidate availability. The optimal rankings are computed by minimisation of the expected number of disagreements over all the possible subsets of available candidates. In [START_REF] Lu | The unavailable candidate model: a decision-theoretic view of social choice[END_REF], the probability distribution on these subsets is supposed to follow a Bernoulli law whereas several other authors [START_REF] Klamler | A distance measure for choice functions[END_REF][START_REF] Baldiga | Assent-maximizing social choice[END_REF][START_REF] Gilbert | Beyond pairwise comparisons in social choice: A setwise kemeny aggregation problem[END_REF] used other distributions. Lu and Boutilier provide a clear decision-theoretic justification for producing a ranking instead of a single winner. Indeed, a ranking serves as a very compact decision policy: the winner is the output ranking's best candidate among the available ones. Yet, the binary disagreement used in [START_REF] Lu | The unavailable candidate model: a decision-theoretic view of social choice[END_REF][START_REF] Klamler | A distance measure for choice functions[END_REF][START_REF] Baldiga | Assent-maximizing social choice[END_REF][START_REF] Gilbert | Beyond pairwise comparisons in social choice: A setwise kemeny aggregation problem[END_REF] relies on strong hypotheses that can be discussed, as acknowledged by the authors: a voter is satisfied only if its favourite available candidate is elected (as in "plurality" rule) and fully unsatisfied otherwise.

We argue that the voter's satisfaction should vary more smoothly and depend on the rank it gives to the candidate declared as winner by the aggregation. In this paper, we extend the UCM by assuming that positions are associated with disutility values and compute dissatisfaction as the disutility gap between the voter's preferred available candidate and the candidate declared as winner. The goal is then to produce a ranking that minimises the expected dissatisfaction under the probability distribution on the subsets of candidates. We observe that there are two opposed ways to measure the satisfaction of the voters, either by considering the ranks of the candidates in the whole preference order of the voter (ex ante approach), or the ranks of the candidates within the subset of available candidates (ex post approach). Hence, we analyse our generalisation of the UCM from these two perspectives; we also show connections to other voting schemes.

We introduce background and notations, and review the UCM in Section 2. In Section 3, we present our framework and introduce the two different models, ex ante and ex post dissatisfactions, that we thoroughly analyse in Sections 4 and 5 respectively. Finally we provide concluding remarks (Section 6).

Background

Throughout the paper, given a set E , P(E ) denotes the set of all the subsets (powerset) of E and |E | denotes the cardinality of E . We define 1; m := {1,. . . ,m}. We now present our basic assumptions (Section 2.1) and we summarise the UCM (Section 2.2).

Basic assumptions

We assume that there are m candidates and we call C the set of all the candidates. Given a non-empty subset of candidates S ⊆ C, we use R S to denote the set of rankings (permutations) of the candidates of S. We use R without subscript to mean R C , the set of full rankings involving all candidates in C. A ranking can be represented explicitly by the tuple that lists the candidates from the most to the least preferred; for instance, the tuple (b, c, a) denotes the ranking that ranks b in first position, c in second position and a in last position. Given a ranking r, r i denotes the candidate ranked in i-th position by r. For example, if r = (b, c, a), r 1 = b, r 2 = c and r 3 = a.

We suppose that, for every voter v, the preferences of v over the candidates can be modelled by a ranking. We will then identify voters with their associated rankings and all the definitions that apply to rankings implicitly apply to voters and vice-versa. Given a ranking r ∈ R, the associated preference order is denoted as > r (and derived orders ≥ r , < r and ≤ r have the obvious meanings). For example, a and b being two candidates, a > r b means that a is better ranked (has a lower rank) than b in r.

Given a ranking r ∈ R and a candidate a ∈ C, r(a) denotes the position (rank) given to a by r. If S is a non-empty subset of C, the expression r S (a) denotes the rank of a in the restriction of ranking r that considers only elements of S. In other words, r S (a) = 1 + |{b ∈ S|b > r a}|. In particular, r C (a) = r(a). Using these notations amounts to see r as the bijection that maps a candidate a ∈ C to its rank r(a) ∈ 1; m in the whole set of candidates3 and to see r S as the bijection that maps a candidate a ∈ S to its rank r S (a) ∈ 1; |S| in the subset S. Given a non-empty subset S of C and a ranking r ∈ R, top r (S) is the candidate which is the most preferred by r among the candidates of S. In other words, top r (S) = r -1 S (1) if we identify r S with the bijection from S to 1; |S| as explained above. By convention, top r (∅) = a ∅ where a ∅ is a default alternative when none of the candidates are available (for instance, postpone the election). Another convention is that, if r is a ranking, r ∅ (a ∅ ) = r(a ∅ ) = 1 4 .

Under the assumption of anonymity, we will consider voting situations [START_REF] Berg | On probability models in voting theory[END_REF] that we here model as multisets of rankings (since the same ranking may occur several times). Considering n ∈ N fixed throughout the paper, we use V to denote the collection of the multisets of n rankings (representing voters).

Given a ranking r and i ∈ 1; m , we introduce S i (r) = {a ∈ C|a ≤ r r i } = {r j |j ∈ i; m }, the set of candidates that, in the ranking r, are in position i or worse and S i (r) = P(S i (r)) the powerset of S i (r). In addition, T i (r) = {S ∪ {r i }|S ∈ S i (r)} = {S ∈ S i (r)|r i ∈ S} is the collection of all sets of candidates that contain r i , and no candidate better than r i in the ranking r . Note that T i (r) is also equal to {S ⊆ C| top r (S) = r i } i.e. the collection of all sets of candidates whose top-element according to r is r i .

Unavailable Candidate Model

We consider a setting where the availability of the candidates is uncertain. We assume a probability distribution P on P(C) that we will refer to as the unavailability distribution (not necessarily known by the voters). For every S ⊆ C, P (S) denotes the probability that the set of available candidates is exactly S5 . We use P C to denote the set of probability distributions on P(C). Given P ∈ P C and an application g defined on P(C), the expectation of g under P is E S∼P [g(S)] := S⊆C P (S)g(S).

Definition 1. P ∈ P C is pair-sensitive if ∀S ⊆ C, |S| = 2 ⇒ P (S) > 0. Definition 2. P ∈ P C is said impartial if it satisfies ∀S ⊆ C, ∀S ⊆ C, |S| = |S | ⇒ P (S) = P (S )
. PC denotes the set of impartial probability distributions of P C . We then define, for P ∈ PC , P as follows: for k ∈ 1; m , P (k) is the probability P (S) for any S ⊆ C of cardinality k6 . P is impartial means that P treats all the candidates equally. [START_REF] Lu | The unavailable candidate model: a decision-theoretic view of social choice[END_REF] propose to evaluate a ranking with respect to the expected disagreement that measures, for each voter, the binary disagreement that evaluates to one if the winner (the elected candidate) is not the same as the voter's preferred choice among the available choices and zero otherwise. Assuming that the probability of a candidate to be unavailable is p ∈]0; 1[, the expected number of disagreements between two rankings r and r is defined as

Lu and Boutilier

D p (r, r ) := S⊆C p m-|S| (1 -p) |S| 1[top r (S) = top r (S)] (1)
Observation 1 D p is a metric.

An optimal ranking is a ranking that minimises v∈V D p (r, v). Note that D p implicitly assumes that the best decision would be to follow plurality when the set of available candidates is revealed. Since a ranking has to be produced before the set S is revealed, the optimal ranking is the one that best approximates "plurality a posteriori". Plurality is a rule that is not perceived satisfactory from the point of view of social theory [START_REF] Laslier | And the loser is[END_REF] because it only takes into account the first candidate of the voter's preference and thus loses a lot of information. Precisely, a major advantage of plurality is its simplicity and the small quantity of information needed and, thus, the cognitive load for the voters is reduced. This is not the case in the UCM where the complete ranking of preferences is anyway needed for each voter. Generalising scoring rules via ex post dissatisfaction and not only plurality provides a richer model and does not require more information, except the disutility functions which may be, in a lot of scenarios, the same for all voters.

Generalised unavailable candidate model

In this work we provide a generalisation of the UCM by evaluating a ranking with respect to the expected dissatisfaction that it imposes on the voters. A ranking defines a policy for making a choice under uncertain availability of candidates. The final choice is the top ranked candidate among the available ones. The voters suffer a degree of dissatisfaction that depends on the position of the final choice in their own ranking. In order to introduce our model, as the first thing, we need to define a function that maps rank positions to "disutility" values. Definition 3. A disutility function (DF) ρ is an increasing mapping from 1; m to R. ρ may be represented as a sequence i.e. ρ = (ρ(i)) i∈ 1;m . ρ(i) measures how much a voter is unsatisfied by the item at the i-th position in its ranking.

The overall idea of our generalised model is the following. Given a ranking r, when the set S of available candidates is observed, the candidate top r (S) is declared the winner; in other words the winner is the highest ranked candidate in S with respect to r. As far as the voter v is concerned, its most desired candidate is top v (S). We allow the disutility functions to depend on the voter and note ρ v the disutility function associated to voter v. This implies that, in the generalised UCM, considering a voter v is actually considering the ranking of the preference of v and the DF ρ v , the definition of V being consequently adapted. Nevertheless, in the absence of ambiguity and to lighten the notations, v may refer to either the voter or its preference order in the remainder of the paper. ρ v and the position in v of a candidate a determine the disutility that voter v suffers from the election of a. The dissatisfaction, with respect to S, is then the difference between the disutility of top r (S) and that of top v (S). Finally, the total dissatisfaction is the sum of the dissatisfactions of all the voters in V . When we produce a ranking, the set of available candidates is not known but we know the distribution P . We thus aim at providing the ranking that minimises the total dissatisfaction in expectation over P .

In the following we make this reasoning more concrete and discuss two different methods to compute dissatisfaction that differ on whether full or restricted rankings are considered.

Ex ante dissatisfaction

In this approach, the dissatisfaction is computed using the positions of the candidates in the whole set of candidates C. When a candidate a ∈ S is chosen as winner, with S being the set of available candidates, voter v suffers disutility ρ v (v(a)), i.e. the disutility associated with the position of a in the full ranking v, while its most preferred candidate in S would have given him disutility

ρ v (v(top v (S))); this gives ρ v (v(a)) -ρ v (v(top v (S)
)) as value of dissatisfaction. We then take the expectation of such a value under P , since the set S is not known beforehand. Finally, we obtain ∆P (v, r), that we formally define now. Definition 4. Let P ∈ P C be a probability distribution, v be a voter (or ranking), ρ v be the DF associated to v, and r a ranking. We define

∆P (v, r) := E S∼P [ρ v (v(top r (S))) -ρ v (v(top v (S)))] and, if V ∈ V , ∆P (V, r) := v ∈V ∆P (v , r).
Proposition 1. For any P ∈ P C , ∆P ≥ 0 and, for any voter v, ∆P (v, v) = 07 .

We call ∆P the ex ante dissatisfaction measure associated to P and

ρ v (v(top r (S))) -ρ v (v(top v (S))) is the ex ante dissatisfaction induced by r ∈ R in S ⊆ C to the voter v.
The ex ante dissatisfaction induced by r in the empty set to v is ρ(v(a ∅ )) -ρ(v(a ∅ )) = 0 so the empty set does not contribute to the ex ante dissatisfaction measure. Note that the singletons do not contribute either since they cannot generate dissatisfaction. We also call the application ∆P defined on V × R, the ex ante dissatisfaction measure associated to P . Definition 5. The optimal rankings for V ∈ V are defined as the elements of arg min r∈R ( ∆P (V, r)). We also write this set R * P (V ).

+ 0 + 0 + 1 1 + 1 + 1 + 2 39 (a, c, b) a a a c 0 + 0 + 0 + 2 1 + 1 + 1 + 0 29 (b, a, c) b b a b 1 + 1 + 0 + 1 2 + 2 + 1 + 2 61 (b, c, a) b b c b 1 + 1 + 2 + 1 2 + 2 + 0 + 2 62 (c, a, b) c a c c 2 + 0 + 2 + 2 0 + 1 + 0 + 0 31 (c, b, a) c b c c 2 + 1 + 2 + 2 0 + 2 + 0 + 0 42
We deduce that the only optimal ranking is (a, c, b).

Ex post dissatisfaction

In this model, we assume that the disutility felt by a voter when a candidate is elected depends on its position within the set S of the actually available candidates. More precisely, when a candidate a ∈ S is chosen as winner, voter v suffers disutility ρ v (v S (a)), that is the disutility value associated to v S (a), the position of a in the ranking obtained by restricting v to the set S. Voter v's most preferred candidate in S would have given him disutility

ρ v (v S (top v (S))) = ρ v (1), yielding dissatisfaction ρ v (v S (a)) -ρ v (1)
. The expectation of such value under P gives ∆ P (v, r), that we formally define now.

Definition 6. Let P ∈ P C , v be a voter (or ranking) with DF ρ v and r be a ranking.

∆ P (v, r) := E S∼P [ρ v (v S (top r (S))) -ρ v (1)]. and, if V ∈ V , ∆ P (V, r) := v ∈V ∆ P (v , r).
Proposition 2. For any P ∈ P C , ∆ P ≥ 0 and, for any voter v, ∆ P (v, v) = 0.

We call ∆ P the ex post dissatisfaction measure associated to P whether it is defined on R 2 or V ×R. For a voter v, a ranking r, S ⊆ C, ρ v (v S (top r (S)))-ρ v (1) is the ex post dissatisfaction induced by r in S to v. The ex post dissatisfaction induced by r in the empty set to

v is ρ v (v ∅ (a ∅ )) -ρ v (1) = ρ v (1) -ρ v (1)
= 0 so the empty set does not contribute to the ex post dissatisfaction measure. As in the ex ante approach, the singletons do not contribute either. Definition 7. The optimal rankings for V ∈ V are defined as the elements of arg min r∈R (∆ P (V, r)). We also write this set R * P (V ). Hence, the optimal ranking is (c, a, b). Note that this is a different ranking from the optimal ranking obtained in the ex ante approach, namely (a, c, b).

The question whether the ex ante or the ex post approach is more relevant is open. On the one hand, the ex ante model captures the idea that the "utility" perceived by a voter when a candidate is elected should be independent of whether another candidate is available or not. On the other hand, the ex post approach is more relevant if we want to focus on the regret of the voters: if the candidate a is elected, the more available candidates that voter v preferred to a have been excluded, the more regret v will experiment. We also believe that the ex post approach reduces the incentive of manipulating with regards to the unavailability distribution. Indeed, a voter who knows the unavailability distribution (but not the preferences of the other voters) may use this knowledge to manipulate the vote in both approaches. Nevertheless, in a situation where two candidates are much more likely to be available than the others for instance (case of a partial unavailability distribution), the benefit of manipulating must be higher in the ex ante approach since ranking these two candidates at the extreme positions (first and last) will increase the influence of the voter in the result of the aggregation. Quantitative results confirming this intuition would require further work. We will see in the following that both ex ante and ex post models are interestingly linked to several well known voting rules. Note that the ex post approach is also considered in [START_REF] Baldiga | Assent-maximizing social choice[END_REF][START_REF] Gilbert | Beyond pairwise comparisons in social choice: A setwise kemeny aggregation problem[END_REF] and, in particular, by Lu and Boutilier in [START_REF] Lu | The unavailable candidate model: a decision-theoretic view of social choice[END_REF] as the following proposition shows. Proposition 3. Let p ∈]0; 1[. D p is the ex post dissatisfaction measure ∆ P whose probability distribution is P : S ⊆ C → p m-|S| (1 -p) |S| (a Bernoulli distribution as defined in Section 5) and with the DF 1-1 {1} = (0, 1, ..., 1) for all voters. We call 1-1 {1} the binary DF.

Note that Lumet et al. [START_REF] Lumet | Reducing preference elicitation in group decision making[END_REF] also proposed a double ex ante/ex post approach in a problem of fair allocation of indivisible goods with the assumption that some goods may turn out to be in bad condition and thus unusable. Choosing between their two approaches consists of choosing whether the aggregation over the agents is performed before or after the expectation over the conditions of the objects in the computation of what the authors call the collective utility. The utility of an object in good condition is well defined and fixed. By contrast, in our work in which the aggregator over the voters is simply the sum 8 and commutes with the expectation, the ex ante/ex post distinction is based on the definition of the dissatisfaction and on the fact that the disutility can be computed either before or after knowing the actual set of available candidates.

Ex ante dissatisfaction

Link with scoring rules

We now develop the theory of ranking with respect to ex ante dissatisfaction measure and show the connection with positional scoring rules.

Definition 8. Let V ∈ V . We define s V : a ∈ C → v∈V ρ v (v(a)).
Definition 9. Let V ∈ V . We define R ↑ (V ) the set of rankings where the candidates are ranked in the increasing order of s V (there can be several such rankings if some candidates have equal scores).

The following theorem characterises the ex ante dissatisfaction rule. It shows that, regardless of the unavailability distribution P , an optimal ranking can be found by sorting alternatives with respect to their score. Moreover, if P is pair-sensitive, the set of all optimal rankings is the exact output of the scoring rule with scoring function -ρ v for voter v. This result echoes the one from [START_REF] Viappiani | Characterization of scoring rules with distances: application to the clustering of rankings[END_REF] which characterises scoring rule via minimisation of the positional Spearman semi-metric, with the restrictive assumption of strictly increasing scores.

Theorem 1 Let P ∈ P C and V ∈ V . Then, R ↑ (V ) ⊆ R * P (V ). If, besides, P is pair-sensitive, R ↑ (V ) = R * P (V ).
Sketch of proof. We show that minimising ∆ P (V, r) amounts to minimising

ψ(V, r) = E S∼P [s V (top r (S))] and that, for any S ⊆ C, s V (top r (S)) is minimal if r ∈ R ↑ (V ).
In the case where P is pair-sensitive, if r / ∈ R ↑ (V ) we can find i ∈ 1; m -1 such that s V (r i ) > s V (r i+1 ). Exchanging the positions of r i and r i+1 in r strictly reduces the value of ψ(V, r) so r is not optimal. Note that, if P is not pair-sensitive and P ({a, b}) = 0, in the case where r * ∈ R ↑ (V ) with r * m-1 = a and r * m = b, then r deduced from r * by swapping a and b is also optimal, but not in

R ↑ (V ) if s V (a) < s V (b).
Corollary 1. An optimal ranking for V ∈ V in the ex ante dissatisfaction model can be found in polynomial time in m and n.

Corollary 2. Let V ∈ V . Let P ∈ P C and P ∈ P C be two pair-sensitive probability distributions. Then R * P (V ) = R * P (V ). The previous corollary expresses that the set of optimal rankings for V does not depend on the unavailability distribution as long as the latter is pair-sensitive. ,c,a,d). We suppose that all voters have the DF ρ = (0, 1, 2, 3). We have: s V (a) = 2+1+2 = 5, s V (b) = 1+2+0 = 3, s V (c) = 3+3+1 = 7, s V (d) = 0 + 0 + 3 = 3. The rankings that rank the candidates in the increasing order of s V thus are (b, d, a, c) and (d, b, a, c). We deduce that these two rankings are the optimal rankings for V whatever is the pair-sensitive unavailability distribution.

Ex post dissatisfaction

In this section, we study ex post dissatisfaction rule from an algorithmic point of view and under natural assumptions on the unavailability distribution and the DF. It is obvious that the ex post dissatisfaction is unchanged by a translation on any of the voters' DF. Hence, without loss of generality, we will consider in the following that all the DF are null in 1 and therefore non-negative on 1; m .

V, r) ∈ V × R, ∆ P (V, r) = v∈V E S∼P ρ v (v S (top r (S))) 9 .
Definition 10. A DF ρ is discriminating at the top (DT) if ρ(1) < ρ(2). Proposition 4. Let P ∈ P C pair-sensitive. Let v be a voter with DF ρ v . We have (∀r ∈ R, ∆ P (v, r) = 0 ⇐⇒ r = v) if, and only if, ρ v is DT.

Conversely, let P ∈ P C not pair-sensitive. For any voter v, there exists a ranking r = v such that ∆ P (v, r) = 0 (ρ v being either DT or not).

Observation 2 Multiplying all voters' DF by α ∈ R * + does not change R * P (V ).

Proof. Multiplying all the voters' DF by the same α multiplies ∆ P by α.

Definition 11. A DF ρ is overnormalised if it is DT, ρ(1) = 0 and ρ(2) ≥ 1.
Proposition 4 incentives us to study only DF that are DT. In this context, Observation 2 shows that we can restrict our study to overnormalised DF without loss of generality -it suffices to multiply all the DF by 1 min v∈V ρv [START_REF] Baldiga | Assent-maximizing social choice[END_REF] . As in the work of Lu and Boutilier [START_REF] Lu | The unavailable candidate model: a decision-theoretic view of social choice[END_REF], we introduce a specific kind of probability distribution of P C . Assuming that the probability of a candidate to be unavailable is independent of the presence of the other candidates and that this probability is equal to p ∈]0; 1[ for all candidates, we get the probability distribution S ⊆ C → p m-|S| (1 -p) |S| . We call it the Bernoulli distribution of parameter p. Note that a Bernoulli distribution is impartial and pair-sensitive.

Connections with Kendall's tau metric

In the following, for any (r, r ) ∈ R 2 , κ(r, r ) := i<j 1[r i < r r j ] is the Kendall's tau metric between r and r and, for any (V, r) ∈ V ×R, κ(V, r) := v∈V κ(v, r).

Remark 2. Let us suppose that all voters have the DF ρ = (0, 1, ..., 1), i.e. the binary DF. Let P be the impartial probability distribution of P C that is nonnull only on the pairs; in other words, for S ⊆ C, if |S| = 2, P (S) = 2 n(n-1) , otherwise P (S) = 0. For any (V, r) ∈ V × R, ∆ P (V, r) = 2 n(n-1) κ(V, r). Hence, ∆ P is the Kendall's tau metric within a strictly positive factor.

A result of Baldiga and Green in [START_REF] Baldiga | Assent-maximizing social choice[END_REF] shows that the Kemeny rule and the ex post dissatisfaction rule with binary DF for all voters and general impartial unavailability distribution may produce different rankings and highlights in that way the role of the unavailability distribution.

Definition 12. For (r, r ) ∈ R 2 , i ∈ 1; m , we define x r,r (i) := |{a ∈ C|a > r r i ∧ a < r r i }| = r Si(r ) (r i ) -1 the
number of candidates ranked after r i in r but before r i in r.

We now recall a proposition established with other notations in the proof of Theorem 11 of [START_REF] Lu | The unavailable candidate model: a decision-theoretic view of social choice[END_REF] that will be useful in the following.

Proposition 5. [15] Let (r, r ) ∈ R 2 . κ(r, r )= m i=1 x r,r (i)= m-1 i=1 x r,r (i).
Definition 13. The Borda DF maps i ∈ 1; m to i-1.

The Borda DF is overnormalised. The name Borda DF is justified by the fact that, if all voters have the Borda DF and P ∈ P C is an arbitrary pairsensitive probability distribution, Theorem 1 shows that the ex ante dissatisfaction rule based on the minimisation of ∆P is equivalent to the Borda rule.

Lemma 1. If ρ is a DF, P ∈ P C is a Bernoulli distribution of parameter p ∈ ]0; 1[, (r, r ) ∈ R 2 and i ∈ 1; m , S∈Ti(r ) P (S)ρ(r S (top r (S))) = x r,r (i) j=0 ρ(j + 1) x r,r (i) j (1 -p) j+1 p x r,r (i)+i-j-1 .
The next proposition establishes the link with Kendall's tau.

Proposition 6. Let p ∈]0; 1[ and P ∈ P C be the Bernoulli distribution of parameter p. Let r ∈ R and v be a voter with the Borda DF.

It holds:

∆ P (v, r) = (1 -p) 2 m-1 i=1 x v,r (i)p i-1 .
Proposition 6 shows that the ex post dissatisfaction measure associated to the Borda DF and a Bernoulli distribution can be seen as a weighted version of the Kendall's tau metric but in a different sense than in [START_REF] Shieh | A weighted kendall's tau statistic[END_REF] or [START_REF] García-Lapresta | Consensus measures generated by weighted kemeny distances on weak orders[END_REF] since here the weight associated to an inversion in the computation of ∆ P (v, r) does not depend on the ranks of both candidates but only on the rank of the candidate ranked before in r and after in v.

Solving the ex post dissatisfaction problem

Complexity of the ex post dissatisfaction rule In the sequel, given q ∈ [1; +∞[, a DF ρ is said to be q-sub-geometrical if ρ is overnormalised and, for any k ∈ 2; m , ρ(k) ≤ q k-2 ρ(2). Theorem 2 shows that optimising ex post dissatisfaction measure is NP-hard.

Theorem 2 We suppose that all the voters have the same DF ρ and that ρ is q-sub-geometrical, for a q ∈ [1; +∞[. Let ∈]0,

1 nm(m-1)+1 [. Let p ∈ [max((1 - ) 1 m-1 , q-(1+ ) 1 m-1 q-1
); 1[ 10 . Let P ∈ P C be the Bernoulli distribution of parameter p, and V ∈ V . Any ranking in R * P (V ) is also a Kemeny consensus.

Sketch of proof. Using the assumptions on p and ρ, we prove, for all (V, r)

∈ V × R: ρ(2)(1 -p) 2 (1 -)κ(V, r) ≤ ∆ P (V, r) ≤ ρ(2)(1 -p) 2 (1 + )κ(V, r).
The bounds on and these inequalities enable us to show a contradiction if we suppose the existence of an optimal ranking which is not a Kemeny consensus.

10

> 0 so both (1 -) 1 m-1 and q-(1+ ) 1 m-1 q-1 are strictly lower than 1.

Corollary 3. For any number of candidates m ∈ N * , we suppose that the voters' DF are all q m -sub-geometrical, with q m ∈ [1; +∞[. For m ∈ N * , we consider

m ∈]0, 1 nm(m-1)+1 [, p m ∈ [max((1 -m ) 1 m-1 , qm-(1+ m) 1 m-1 qm-1
); 1[, P m ∈ P C the Bernoulli distribution of parameter p m , and V m a voting situation for m candidates. The problem of size m of finding r ∈ R minimising ∆ Pm (V m , r) is NP-hard.

Proof. Since finding a Kemeny consensus is NP-hard [START_REF] Bartholdi | Voting schemes for which it can be difficult to tell who won the election[END_REF], Theorem 2 gives us the NP-hardness of the problem where all the voters have the same DF. Therefore, the more general problem where DF depend on the voters is also NP-hard.

A polynomial-time approximation scheme We here exhibit an approximation algorithm for the ex post dissatisfaction rule and present some intermediary results that allow us to prove this is a PTAS under natural assumptions. In this subsection, P denotes the Bernoulli distribution of parameter p ∈]0; 1[. Firstly, let us introduce some definitions necessary to the construction of the algorithm. Sketch of proof. Lemma 1 shows that the while loop can be performed in O(nm 3 ). The second part of the algorithm needs to test only m! (m-K)! = O(m K ) rankings since, once the i -1 first candidates are fixed, ∆ i,i+K-1 P (V, r) only depends on the candidates between the i th and the i + K -1 th positions in r. Besides, we can reuse Lemma 1 to show that ∆ i,i+K-1 P is computed in O(nm 2 ). Hence, the second part is performed in O(nm K+2 ). The last part is done in O(m).

Observation 3 Let V ∈ V , r ∈ R. ∆ P (V,r) = m i=1 f (S i (r),r i ). Definition 15. For V ∈ V , r ∈ R, k ∈ 1; m , l ∈ k; m , we denote ∆ k,l P (V, r) := v∈V l i=k S∈Ti(r) P (S)ρ v (v S (r i )) = l i=k f (S i (r),
Lemma 3 allows us to apply Corollary 4 to subsets of C. We can then show Theorem 3 which proves that MyopicTop algorithm is a PTAS for the ex post dissatisfaction rule when the normalised DF are bounded 11 . Note that here parameter p is assumed to be fixed and independent on n and m. This differs from the assumptions made to establish the NP-hardness result in Theorem 2. The question whether the problem with p fixed is NP-hard or not remains open.

1; m , ρ v (i) ≤ M . Let > 0, K = log 1 p ( 2M (1-p) 3 ) and V ∈ V . Let r * ∈ R * P (
V ) be an optimal ranking and r be the ranking obtained via the MyopicTop algorithm with inputs C, p, V , K. If ∆ P (V, r * ) = 0 then ∆ P (V, r) = 0. Otherwise, ∆ P (V,r) ∆ P (V,r * ) ≤ 1 + .

Sketch of proof.

First of all, we show that, if the while loop runs until there is no remaining candidates, then r = r * . This happens, for instance, when ∆ P (V, r * ) = 0 and then, in this case, we also have ∆ P (V, r) = 0. If the while loop ends before, at an index i -1, where i ∈ 1; m , r coincides with r * for the first i -1 candidates and ∆ i,i+K-1 P (V, r) ≤ ∆ i,i+K-1 P (V, r * ) by construction of r. Besides, we show that ∆ i+K,m P (V, r) ≤ nM p i+K-1 and, the fact that r * i is not dominant in S i (r * ) enables us to show that f (S i (r * ), r * i ) ≥ n 2 p i-1 (1 -p) 3 . Finally, by construction of K, we get ∆ P (V,r) ∆ P (V,r * ) ≤ 1+

∆ i+K,m P (V,r) f (Si(r * ),r * i ) ≤ 1+ 2M p K (1-p) 3 ≤ 1+ .

Note that, for the algorithm to be polynomial, the bound M must not depend on the number m of candidates. The assumption whereby the DF are bounded may seem restrictive but is actually quite reasonable if we suppose that a voter cannot cognitively conceive an unbounded dissatisfaction. Indeed, one can naturally consider that, after a fixed rank, all alternatives are equally disliked by the voter, the disutility value M would then mean "I completely dislike this alternative". DF can even be strictly increasing, but converging towards M . Hence, this upperbound assumption models the increasing difficulty for the voters to discriminate between alternatives as they go further in their preference rankings.

Conclusion

We provided an extension of the UCM accounting for rank-based dissatisfaction. The voters' preferences are aggregated in a ranking that minimise the overall expected dissatisfaction and is used to select the winner once the available candidates are known. We considered two different settings, ex ante and ex post, corresponding to different ways of defining dissatisfaction, provided a theoretical analysis of both cases, and gave algorithms for finding or approximating an optimal ranking. This analysis showed that the assumption used to define dissatisfaction has a crucial impact on the complexity of the voting rule. Interestingly, we showed that this two-sided model provides a unified representation for very different voting rules, spanning from positional scoring rules to Kemeny rule.

Future works may include analysis of practical performance with simulations. We now provide some theoretical directions of research. First of all, we are interested in studying other probability distributions (including non impartial ones) than Bernoulli and thereby emphasising the fact that ex post model generalises voting rules studied in [START_REF] Gilbert | Beyond pairwise comparisons in social choice: A setwise kemeny aggregation problem[END_REF][START_REF] Baldiga | Assent-maximizing social choice[END_REF][START_REF] Lu | The unavailable candidate model: a decision-theoretic view of social choice[END_REF]. Other aggregators than the sum could enable us to include fairness considerations [START_REF] Lumet | Reducing preference elicitation in group decision making[END_REF]. A quite different idea, inspired from [START_REF] Lu | The unavailable candidate model: a decision-theoretic view of social choice[END_REF], would be to analyse the link between optimal rankings and optimal policies -i.e. choice functions -in the ex post approach. We believe that there is a connection between the comparison ex ante/ex post optimal rankings and the rationalisability of optimal policies; this would echo Theorem 1 from [START_REF] Baldiga | Assent-maximizing social choice[END_REF] that links the rationalisability of optimal policies to the influence of the unavailability distribution. More quantitavely, we could study the role of the inconsistency (in the sense of [START_REF] Apesteguia | A measure of rationality and welfare[END_REF]) of the optimal policies. Comparing ex ante and ex post approaches in terms of manipulation could also be fruitful as mentioned in Section 3.2. Finally, we are also interested in studying elicitation of preferences in a context of uncertain availability.

Example 1 .

 1 Let m = 3, C = {a, b, c}. Let P ∈ P C be the uniform probability distribution: for all S ⊆ C, P (S) = 1 8 . Let n = 11. Let V ∈ V be a set of 11 voters, 4 of them voting according to the ranking r = (a, b, c) and 7 of them voting according to the ranking r = (c, a, b). We assume that all voters have the same DF ρ = (0, 1, 2). Note that, for every r ∈ R, ∆P (V, r) = E S∼P [4ρ(r (top r (S))) + 7ρ(r (top r (S)))]-χ(V ) where χ(V ) := E S∼P [4ρ(r (top r (S)))+7ρ(r (top r (S)))] does not depend on r. The following array displays, for all r ∈ R, from left to right, the value of top r (S) for every non-empty and non-singleton S ⊆ C, S⊆C ρ(r (top r (S)), S⊆C ρ(r (top r (S)) and Σ = 4 S⊆C ρ(r (top r (S)) + 7 S⊆C ρ(r (top r (S)) = 8[ ∆P (V, r) + χ(V )]. r S abc ab ac bc ρ(r (top r (S)) ρ(r (top r (S)) Σ (a, b, c) a a a b 0

Example 2 .

 2 We will take the situation of Example 1 and study it with the ex post approach. We keep the same notations as in Example 1. Let r ∈ R. Since ρ(1) = 0, we directly have ∆ P (V, r) = E S∼P [4ρ(r S (top r (S)))] + 7ρ(r S (top r (S)))]. Let us summarise the computations in the following array, as in Example 1: r S abc ab ac bc ρ(r S (top r (S)) ρ(r S (top r (S)) Σ

Example 3 .

 3 Let C = {a, b, c, d}. Let V be the multiset of three voters among which one votes according to (d, b, a, c), one according to (d, a, b, c) and one according to (b

Remark 1 .

 1 Let P ∈ P C . If all the voters' DF are null in 1 then, for all (

Definition 14 .

 14 If there is no ambiguity on P and V , we define f : (S , a) ∈ P(P(C))×C → v∈V S∈S a∈S P (S)ρ v (v S (a)). For a ∈ C, let f (a) := f (P(C), a).

  r i ) the contribution to ∆ P (V, r) of the subsets of C for which one of the candidates of {r i |i ∈ k; l } is winning according to r.We now define our MyopicTop algorithm (Algorithm 1). It is conceptually similar to the one of Lu and Boutilier but makes use of a new notion of dominance (Corollary 4) which encapsulates the complexity of ex post dissatisfaction rule and applies to any DF. Example 4. Let C = {a, b, c, d, e}, p = 1 4 , K = 2, V constituted of three voters (a, b, c, d, e), one voter (a, c, b, d, e) and one voter (c, a, d, e, b), all voters with Borda DF. a is dominant in C. In C \ {a}, there is no dominant candidate and the rankings of C \ {a} minimising ∆ 2,3 P (V, r) are the rankings starting with (c, b). Then, MyopicTop algorithm outputs (a, c, b, d, e) or (a, c, b, e, d). Lemma 2. Let V ∈ V and a ∈ C. If there exists an optimal ranking that ranks a in first position, then, for every candidate b ∈ C, (1 + p)f (b) ≥ (1 -p)f (a).

Corollary 4 .Proposition 7 .

 47 Let V ∈ V be a voting situation and a ∈ C. If, for all b ∈ C \ {a}, (1 + p)f (a) < (1 -p)f (b), then, a is the first candidate of all optimal rankings. In this case, we call a the dominant candidate. The MyopicTop algorithm runs in O(nm max(3,K+2) ).

Algorithm 1 :

 1 MyopicTopInput: C, p, V , K Output: r = (r1, ..., rm) C ← C; i ← 1; while C = ∅ and C has a dominant candidate do ri ← the dominant candidate in C ;C ← C \ {ri}; i ← i + 1; end Determine (ri, ..., ri+K-1) ∈ C K such that, for any r ∈ R C\{r 1 ,...,r i+K-1 } , (r1, ..., ri+K-1, r 1 , ..., r m+1-i-K ) ∈ arg min r ∈R r j =r j ,j<i ∆ i,i+K-1 P (V, r );Arbitrarily order the remaining m + 1 -i -K candidates;

Lemma 3 .Theorem 3

 33 Let V ∈ V , r * ∈ R * P (V ) be an optimal ranking. For all k ∈ 1; m , (r * k , ..., r * m ) ∈ arg minr∈R S k (r * ) v∈V S∈S k (r * ) P (S)[ρ v (v S (top r (S)))] i.e. (r * k , ..., r * m )is an optimal ranking for the reduced set of candidates S k (r * ) = {r * k , .., r * m }. We consider voting situations where voters' DF are overnormalised and bounded by a fixed M ∈ R * + : for any voter v, for all i ∈

This work was mainly conducted while at LIP6, Sorbonne Université.

With this point of view, the candidate in the i-th position can be seen as the preimage of i by r, i.e. ri = r -1 (i).

These conventions are aimed at simplifying the proofs and do not interfere with the search of optimal rankings since a ∅ is not in C.

The atomic elements being the subsets of C, P should actually be defined on P(P(C)) and the probability that the set of available candidates is equal to S would be P ({S}). We nevertheless write P (S) for the sake of readability.

The notation P (k) must not be confused with the probability that the set of available candidates is of cardinality k, which is actually equal to P (k) × m k .

Referring to the definition of ∆P , one can note that the first argument of ∆P here is voter v itself while the second argument is its preference order.

Studying other aggregators is a perspective that would allow us to give more focus on fairness in the consensus production.

This remark motivates our choice of considering disutilities instead of utilities because, when ρv(1) = 0 for all v ∈ V , the ex post dissatisfaction measure can be seen as a simple sum of expectations of ρv(vS(top r (S))).

It is unclear whether there exists a PTAS if the normalised DF are not bounded.


Patrick Berthault

Overview -necessarily incomplete of 129 Xe NMR-based biosensors