Hugo Hadjur
email: hugo.hadjur@ens-lyon.fr

Doreid Ammar
email: ammar@em-lyon.com

Laurent Lefevre
email: laurent.lefevre@ens-lyon.fr

ANALYSIS OF ENERGY CONSUMPTION IN A PRECISION BEEKEEPING SYSTEM

Keywords: internet of things, energy consumption, benchmarking, smart agriculture, precision beekeeping

Honey bees have been domesticated by humans for several thousand years and mainly provide honey and pollination, which is fundamental for plant reproduction. Nowadays, the work of beekeepers is constrained by external factors that stress their production (parasites and pesticides among others). Taking care of large numbers of beehives is time-consuming, so integrating sensors to track their status can drastically simplify the work of beekeepers. Precision beekeeping complements beekeepers' work thanks to the Internet of Things (IoT) technology. If used correctly, data can help to make the right diagnosis for honey bees colony, increase honey production and decrease bee mortality. Providing enough energy for on-hive and in-hive sensors is a challenge. Some solutions rely on energy harvesting, others target usage of large batteries. Either way, it is mandatory to analyze the energy usage of embedded equipment in order to design an energy efficient and autonomous bee monitoring system. This paper relies on a fully autonomous IoT framework that collects environmental and image data of a beehive. It consists of a data collecting node (environmental data sensors, camera, Raspberry Pi and Arduino) and a solar energy supplying node. Supported services are analyzed task by task from an energy profiling and efficiency standpoint, in order to identify the highly pressured areas of the framework. This first step will guide our goal of designing a sustainable precision beekeeping system, both technically and energy-wise.

Introduction

Whether it is used by companies or individuals, technology applied to agriculture (smart agriculture or precision agriculture) has brought a whole new dimension to farming. With the new modern constraints of growing demand and farming area shrinking, the need is no longer to expand, but to optimize, while taking into consideration the environmental challenges. To do so, farmers nowadays make use of IoT technologies that collect relevant data regarding their plantations and data-related tools to optimize their work.

Recently, several stress factors emerged from the agricultural industry and apiculture, among others, is affected. Precision beekeeping is a branch of precision agriculture linked to apiculture. The goal is to support beekeepers so that crucial events are detected as early as possible. Such events may include the swarming state, queenless state, infected colony, attacked colony and dead colony. Designing a precision beekeeping system deployed into wild zones usually requires efficient use of the energy budget, which is mainly provided by batteries.

Monitoring and profiling energy consumption of large scale systems is a real challenge [START_REF] Orgerie | A Survey on Techniques for Improving the Energy Efficiency of Large-Scale Distributed Systems[END_REF]. The objective of this work is to observe and analyze the energy consumption of all deployed hardware, software and services components of a precision beekeeping system. Through this analysis, we can embed all costs of specific steps (idle mode, boot up, shutdown, stress) combined with required services (sensors data collection, image capture, data exchanges) and propose a complete energy consumption overview.

The paper is organized as follows: Section 2 provides a brief overview of selected previous works addressing precision beekeeping. In Section 3, we give an overview of the precision beekeeping system, describe the data collection process, and present the experimental setup used to analyze the energy consumption. Section 4 focuses on the analysis of energy consumption of some specific steps (idle, boot, shutdown) while in Section 5 we present an analysis of the energy consumption of the beekeeping services. In Section 6, we analyze the energy consumption of the system in several temperature conditions. Section 7 concludes the paper and shares directions for future work.

Background and Related work

In recent years, several studies have underlined the potential of integrating intelligent digital technologies for monitoring honey-bees. Edwards-Murphy et al. propose in [START_REF] Edwards-Murphy | b+wsn: Smart beehive with preliminary decision tree analysis for agriculture and honey bee health monitoring[END_REF] a bee monitoring system to describe the internal conditions of a beehive using data from sensors that are embedded within the beehive. The collected data are: temperature, humidity, Carbon Dioxide (CO 2 ) levels, and Oxygen (O 2 ). A machine model is developed in [START_REF] Edwards-Murphy | b+wsn: Smart beehive with preliminary decision tree analysis for agriculture and honey bee health monitoring[END_REF] to detect a subset of beehive status and alert the beekeeper when an important beehive change is detected. An audio-based monitoring system for detecting the presence of the queen bee inside the beehive is introduced in [START_REF] Nolasco | Audio-based identification of beehive states[END_REF], using data from the NU-Hive project [START_REF] Cecchi | A preliminary study of sounds emitted by honey bees in a beehive[END_REF]. The proposed system exploits the sound emitted by the beehives to determine the presence of the queen bee inside the beehive. Similarly, audio-based monitoring systems are also used to detect a beehive state known as "swarming", such as the work conducted in [START_REF] Ferrari | Monitoring of swarming sounds in bee hives for early detection of the swarming period[END_REF]. Although beekeepers who decide to integrate sensors to their beehives still heavily rely on weight (to be correlated with honey quantity), companies release monitoring systems capable of tracking real time temperature of the inside of beehives, humidity, sound and gas levels. A variety of products is available on the market. Label Abeille 4 and Arnia5 cover a wide range of metrics outside the beehive (temperature, humidity, weight of the beehive and other environmental data). Mellisphera6 allows monitoring temperature and humidity from inside the beehive. Pollenity7 develops a sensor that can be attached to an in-hive frame and collect temperature, humidity and sound up close from the bees. The paper from Ammar et al. [START_REF] Ammar | The makers' beehives: Smart beehives for monitoring honey-bees' activities[END_REF] introduces the system which is analyzed in this paper. Here, an in-depth analysis of the energy consumption of each step of the precision beekeeping system is conducted, in order to design an autonomous, energy-efficient and sustainable connected beehive.

Precision Beekeeping System

This paper aims to analyze the energy consumption of a precision beekeeping system built at emlyon business school and previously described in [START_REF] Ammar | The makers' beehives: Smart beehives for monitoring honey-bees' activities[END_REF]. The name of the system (beehive equipped with IoT components) is the "Makers' Beehives". Figure 1 shows a picture of two Makers' Beehives that are deployed on the roof of emlyon business school.

In this section, we give a brief overview of the architecture and the electronic components of a Makers' Beehive, as well as, the data acquisition process. Following that, we elaborate on the experimental setup used to analyze the energy consumption of this precision beekeeping system.

System Overview of a Makers' Beehive

A Makers' Beehive consists of a commonly used Dadant beehive to which two extra parts are added, namely, a wooden base and a solar roof that are placed respectively under and on top of the beehive. The base functions as both a stand for the beehive and a scale thanks to four load sensors located at the corners of the base frame. The roof hosts the electronics, and is equipped with a solar panel tilted to an optimum angle for maximum annual energy production.

Data Acquisition in a Makers' Beehive

The data acquisition process in a Makers' Beehive consists of the following steps :

Step 0: The Trinket turns ON and the boot up of the Makers' Beehive system is done.

Step 1: The Raspberry Pi runs a Python script that collects the measurements (i.e., temperature, humidity, noise, light, Carbon monoxide (CO), Nitrogen dioxide (NO 2 ), and the beehive's weight) from various sensors on the METRO 328.

Step 2: The Raspberry Pi camera captures a series of 20 top view photos of the beehive entrance (one per second).

Step 3: The captured pictures are converted to a single gif file that is uploaded to an online image sharing website.

Step 4: The collected measurements and the url of the uploaded gif file are uploaded to a remote server. By the end of this step, a software update check is performed and the git pull command is executed when an outdated software is detected.

Step 5: The system is granted a time interval of 5 minutes to accomplish the data acquisition process. Once the data is successfully uploaded, the Raspberry Pi shuts off completely. However, if the data acquisition process is not accomplished within the granted time, the Trinket turns OFF leading to a system shutdown.

The Makers' Beehive periodically executes sensing cycles. Every hour, the system wakes up, performs the data acquisition process and then goes into sleep mode again. It is also worth noting that the data acquisition steps are performed over a short time interval of 1 to 5 minutes.

The following sections describe an experimental replica of the Makers' Beehive and its power consumption in various situations.

Testbed for Monitoring and Profiling the Energy Consumption of IoT nodes

To measure the energy consumption of our precision beekeeping system we developed an indoor experimental setup capable of monitoring and profiling the energy consumption of the IoT nodes.

Figure 2 shows an overview of our testbed. The testbed consists of a duplicated version of the sensor nodes that are responsible for performing the data acquisition process in the Makers' Beehive. However, the solar panel, converter, battery and Trinket were removed and replaced by a microUSB power connector that is directly connected via a 5V

Benchmarking the energy consumption of the precision beekeeping system

We first observe the energy consumption of specific conditions and steps (idle, boot, shutdown and stress) in order to analyze several costs.

Idle Mode

A first step toward analyzing the energy consumption of the setup and its tasks is to understand the fixed costs of the hardware. The consumption of the data acquiring Raspberry Pi was recorded while in Idle mode (Raspberry Pi logged in, the operating system launched and at a resting state). This experiment repeats itself four times, to determine the power consumption of the peripherals. First, the full setup is tested (Arduino sensor node plugged in and Pi Camera plugged in). Then, each peripheral is plugged in alone. Finally, the Idle consumption of the setup without any peripheral is recorded.

Figure 3 shows the extra 0.5W of power cost by the connection of the Arduino sensor node via USB. It is important to note that the energy impact of the camera peripheral (not in use) seems negligible.

Boot and Shutdown Profiling

Since the in-hive system wakes up every hour, it is mandatory to analyze the details of each boot up and shutdown phase. Figures 4 and5 show the power evolution of a standard boot up phase (with Arduino plugged in) and the comparison of two shutdown phases.

Observing Boot up step For the boot up phase, the recorded Raspberry Pi was turned off (0s-10s window in Figure 4), plugged out of the power supply (10s-20s) and plugged back in (20s mark). The boot up phase, thanks to its quickness (10 seconds, between the 20s and 30s mark on Figure 4), does not require much energy (14.5 Joules in the case of Figure 4): the time window where the power is greater than the resting phase is only 4-second long (26-30s).

Observing Shutdown step For the shutdown phase, a graceful shutdown approach was used. During a graceful shutdown phase, all running processes are sent a shutdown message. It is only once those processes are closed that the interface is turned off and the filesystems unmounted (described in [START_REF] Amirtharaj | Profiling and improving the duty-cycling performance of linux-based iot devices[END_REF]). A forced shutdown alternative also exists. It does not notify the running processes of the incoming shutdown. In our case, both were tested and although the forced approach turns off the system in less than one second, the small gain of energy is not worth the risk of potential memory errors. The presented results focus on the graceful approach. The results of Figure 5 follow the previous section findings, as the extra USB peripheral adds a fixed cost of energy while turned on. If the Raspberry Pi is turned off and still plugged in, there is no impact of the Arduino. The slight peak of power usage at the moment of the shutdown (10s mark) is explained by the messages sent to running processes and the stop of these processes.

Stress Testing

To better understand the limits of the services of a Raspberry Pi 3, its performances in extreme situations are analyzed.

Stress testing aims at pushing a CPU to its full power. Experimental Conditions In this section, we benchmark two stress tasks, both available on a Raspbian Lite operating system:

• Stress (stress): here, the CPU is run at its full power, all the while controlling the temperature of the chip.

• CPU Burn (cpuburn-a53): here, the Raspberry Pi is maxed out completely without any restriction.

Results Figure 6 and Figure 7 show the temperature and power consumption for the two tasks along several minutes. The absolute maximal power used from the Raspberry Pi 3 lies around 4.5W, whereas the safer approach only requires between 2.6W and 2.7W, which is comparable to the energy of some tasks performed in the field.

Analyzing The Energy Consumption of Beekeeping services

The second part of our analysis concerns the measurement of the energy consumption of the data acquisition process that is detailed in Section 3.2. More precisely, we profile the power usage of the collected measurements and compute the consumed energy (Step 1: 6.2 Joules on average), captured images (Step 2: 23.7 Joules on average), resized and converted images (Step 3: 126.1 Joules on average), and transmitted data (Step 4: 13.5 Joules on average). This analysis relies on the embedded Python code that runs inside the beehive, every hour.

Figure 8 shows the overall consumption of one execution of the in-hive script. It is mainly divided into four energy phases, one for each step, allowing us to estimate the power cost of each. The most energy-consuming phase is the longest: the third one (20s-80s window) which converts images into a GIF and uploads it. The GIF file, which is then uploaded to the dashboard website 8 allows beekeepers to inspect the entrance of their beehive at a glance. An improved future version of the script should take care of the speed of the network, in order to balance the time of upload and the time of conversion, with the ultimate goal of shortening the whole process to decrease the energy consumption of the system.

Collecting data from sensors

The temperature, humidity, noise, light, Carbon monoxide (CO) and Nitrogen dioxide (NO2) are captured at the beginning of the hourly script. It usually takes 1 to 2 seconds to perform this step (step 1 of Figure 8).

Image Capturing

The series of captured images is represented in step 2 of Figure 8.

There is a challenge for choosing the quantity and the resolution of images. The resolution affects the performances of deep learning computer vision algorithms: the better the quality, the higher the efficiency of the learning model. The process of training such a model is also linked to the size of the training set: in general, a large number of images as input is able to train a deep learning model well. But at the same time, capturing and transferring a large number of high-quality images is time-consuming and CPU-consuming. Our goal is to find the right balance between the energy cost of the system and the quality of recommendations to beekeepers.

The Raspberry Pi camera (Raspberry Pi Camera Rev 1.39 ) and its Python module allow to pre-select the resolution of the still pictures so that there is no need to uselessly take high-resolution pictures to then downsize them. It was the case of the first version of the code which was running in the Makers' Beehive. Since then, this was changed to a better approach.

In this section, the cost of time and energy of capturing different quantities of images at different resolutions was analyzed.

Experimental Conditions Once a picture is taken, the program loops without any pause and directly runs the capture of the next one. For consistency, the camera was always placed at the same spot and with the same angle of view.

The first experiment consists of measuring the time to capture different batch sizes of 800×600px images. The batches are made from 1 to 50 images, are each one at least repeated 6 times.

The second experiment focuses on the time taken to capture 10-image batches at different resolutions (list of resolutions: 640×480px, 800×600px, 960×720px, 1024×768px, 1280×960px, 1400×1050px, 1440×1080px, 1600×1200px, 1856×1392px, 1920×1440px, 2048×1536px and 2592×1944px). For each image resolution, the experiment of capturing a 10-image batch was repeated 12 times.

Results Figure 9a shows that the average time per image is 0.515s, which is also the fastest frame rate at this resolution when taking pictures (the camera module also allows video capturing, not treated in our work).

The results presented in Figure 9b underline the disability of the camera module to consistently capture image at its optimal speed. This irregularity aside, there is also a non-linearity of the relationship between the duration of capture and the resolution of images.

Network Testing

The flow of data transmitted in the sensor network is bidirectional. On one hand, the Raspberry Pi updates the software at each iteration of the main loop: a download triggered by a git pull command (step 4 of Figure 8). On the other, data from environmental sensors and the GIF file are uploaded to a server, where it can be manually accessed (end of step 3 and step 4 of Figure 8).

The goal of this section is to profile the data transmission energetically for both wired and wireless connexion types. The energy consumption of such scenarios was analyzed thanks to the iPerf3 tool [START_REF] Dugan | iperf website[END_REF], which allows transferring network packets at the maximum achievable bandwidth.

Experimental Conditions

The replica of the in-hive Raspberry Pi was connected to a local network, located in Lyon, France (Internet provider: SFR). This network has a maximum download speed of around 190Mbits/s and a maximum upload speed of around 20Mbits/s. The Ethernet cable has a maximum speed of 100Mbits/s. The server which was used to test sending and receiving data is a public server located at bouygues.iperf.fr. Its bandwidth is 10Gbits/s.

Once the Raspberry Pi connected to the network (either through Ethernet or Wi-Fi), a 50MB upload was tested thanks to the command iperf3 -c bouygues.iperf.fr -bytes 50M, as well as the download equivalent (-R added at the end of the command). 50MB is enough to get at minimum a few seconds of execution for the fastest rate of transfer (downloading through Ethernet). The Internet transport protocol used is TCP (Transmission Control Protocol) and there is no bandwidth restriction.

Results

The results in Figure 10 and in Figure 11 show the comparison between the types of connection. Although it is obvious that a wired connection is faster than a wireless, downloading data with the first reaches a higher spike of power than the latter, while uploading data show the opposite results. • While downloading through Wi-Fi, the speed seems to be limited by the Raspberry Pi's Wi-Fi card.

• While downloading through Ethernet, the speed is limited by the Ethernet cable.

• While uploading through Wi-Fi, the speed seems to be limited by the Raspberry Pi's Wi-Fi card.

• While uploading through Ethernet, the speed is limited by the local network's upload bandwidth. This could explain the rather small increase of power in this case.

Table 1 also shows that it is more efficient to use an Ethernet connection while exchanging data. However, while in Idle mode or performing other tasks that do not stress the network, having an Ethernet cable plugged into a Raspberry Pi introduces an extra energy cost of around 0.07W to 0.10W. It represents the energy required to handle the Ethernet peripheral. The longer a Raspberry Pi is performing tasks that do not require the Internet, the better the Wi-Fi connection compared to Ethernet.

Beekeeping system in different temperature conditions

Precision beekeeping systems will be deployed on-site in wild zones. The system is supposed to run without interruption outdoors and yearly. How varying temperature conditions can impact the energy consumption of the system?

Experimental Conditions The testbed (Figure 2) was placed in two different temperature conditions: at a cold temperature (inside a fridge; between 3°C and 5°C) and at room temperature (between 19°C and 22°C), all the while maintaining power supply connection. For each one (Figure 12), ten iterations of the main script were executed, each of them followed by a 3-minute break, to retrieve a resting state. Since the pictures captured in an open place (room temperature situation) are different than the ones taken inside a closed dark fridge (cold temperature situation), the size can differ too, leading to different performance for compressing images and converting them into a GIF file. To avoid this potential issue, the same batch of images was always chosen to create the GIF file.

Results Over 10 iterations of the main script, the average energy consumption is on average 169.6 Joules at room temperature, with a standard deviation of 3.1 Joules (average temperature of Raspberry Pi chip: 45.7°C ; standard Practically, the system (full setup with Raspberry Pi and Arduino plugged in) alternates between a 60-minute OFF mode and the 5-minute data collection window. The latter is a combination between the Raspberry Pi boot up, the execution of the script, and the shutdown. According to the observations in the previous sections, the total cost of energy is 1800 Joules for the 60-minute OFF mode phase and 548 Joules for the 5-minute script window. All in all, that is an average of 2167 Joules per hour, being 120.4 mAh at 5V. In the example of the currently deployed system [START_REF] Ammar | The makers' beehives: Smart beehives for monitoring honey-bees' activities[END_REF], the capacity of the solar-powered battery is 33000 mAh. So if a fully charged battery were to lose its link to its charging source, the system would still function for around 11 days and 10 hours (274 cycles of 1 hour).

Conclusion and Future Work

This work presents a complete analysis of energy consumption and the thermal performance of a precision beekeeping system. This is the first step towards optimizing the energy consumption of the deployed services of a connected beehive.

Based on our analysis, it seems like the temperature of the system does not significantly affect the energy consumption of the execution of a script. The current approach of the Makers' Beehive, which consists of shutting down completely the system and waking it up every hour in order to perform the data collection seems to be an energy efficient solution because the residual consumption of an idle Raspberry Pi 3 has a significant impact on energy consumption. The consumption of the USB connection of the Arduino sensor node is significant. It adds an extra fixed cost of energy, so future work will explore other ways for the plugging sensor (sensor shield) in order to determine the most energy efficient solution.

Future work will focus on deploying new services of data processing like deep learning applications in the precision beekeeping system. Taking care of the energy consumption is mandatory since there are multiple ways to proceed: either performing the computation on chip (energy-heavy task) and only sending the results (few bytes), or not performing any computation and sending the uncompressed data streams.

Figure 1 :

 1 Figure 1: Two precision beekeeping systems deployed on site

Figure 2 :

 2 Figure 2: Experimental setup for monitoring energy consumption

Figure 3 :

 3 Figure 3: Power consumption of a Raspberry Pi in Idle mode over a 60-second time window

Figure 4 :

 4 Figure 4: Power consumption of the full setup (Arduino plugged in) during boot up

Figure 5 :

 5 Figure 5: Power consumption of the full setup -Arduino plugged in -(blue) and Arduino plugged out (green) during shutdown

Figure 6 :Figure 7 :

 67 Figure 6: Power consumption of stress task

Figure 8 :

 8 Figure 8: Power usage graph of one execution of the in-hive script

Figure 9 :

 9 Figure 9: Time needed by the PiCamera to capture (a) different batch sizes of 800×600px images and (b) 10 images with different resolutions.

Figure 10 :

 10 Figure 10: Power consumption of the full setup downloading 50MB from a distant server. Two types of connectivity were tested: Wi-Fi (blue) and ethernet (red).

Figure 11 :

 11 Figure 11: Power consumption of the full setup uploading 50MB to a distant server. Two types of connectivity were tested: Wi-Fi (blue) and ethernet (red).

Figure 12 :

 12 Figure 12: Power usage and temperature of the Raspberry Pi chip for one script run at different temperature conditions

Table 1 :

 1 Average energy consumed while performing connectivity tests (transferring 50MB)

	Network	Data-rate		Power consumption
		download	upload	download	upload
	Wi-Fi	25.7 Mbits/s 9.5 Mbits/s 34.0 Joules 93.9 Joules
	Ethernet 86.4 Mbits/s 19.2 Mbits/s 10.8 Joules 42.5 Joules

Table 1

 1 helps to understand what is the limiting factor and the pressure point in each case:

https://www.label-abeille.org

https://www.arnia.co.uk

https://www.mellisphera.com

https://pollenity.com

https://makersbeehives.herokuapp.com

https://www.raspberrypi.org/documentation/hardware/camera/


Eric Danan
email: eric.danan@cyu.fr

Thibault Gajdos
email: thibault.gajdos@univ-amu.fr

Jean-Marc Tallon
email: jean-marc.tallon@psemail.eu

Franz Dietrich

Georgios Gerasimou

Itzhak Gilboa

Philippe Jehiel

Antonin Macé

Tigran Melkonyan

Efe Ok

Marcus Pivato

Daniel Read

Régis Renault

Zvi Safra

Tailored Recommendations *

Keywords: Recommendation systems, incomplete preferences, extension, aggregation, Pareto principle, collaborative filtering. JEL Classification. D71, D81

Many popular internet platforms use so-called collaborative filtering systems to give personalized recommendations to their users, based on other users who provided similar ratings for some items. We propose a novel approach to such recommendation systems by viewing a recommendation as a way to extend an agent's expressed preferences, which are typically incomplete, through some aggregate of other agents' expressed preferences. These extension and aggregation requirements are expressed by an Acceptance and a Pareto principle, respectively. We characterize the recommendation systems satisfying these two principles and contrast them with collaborative filtering systems, which typically violate the Pareto principle.

Introduction

The digitalization of our societies has enabled the personalization of advice to an extent never seen before.

We now routinely receive recommendations or advertisements not for the "best" possible product, but, rather, for the one that is "best fit" for us. Netflix, for instance, adjusts the movies and shows it suggests to each user based on her profile, what she has seen and how much she appreciated it. Different users receive different recommendations. As for many other internet platforms using so-called "collaborative filtering" recommendation systems (Facebook, Twitter, Amazon, Spotify, Last.fm, LinkedIn, . . . ), the recommendation for a given user will hinge upon other users that are "similar" to her in one way or another. How this notion of similarity between users is modeled is crucial for the properties of the recommendation system.

The present paper approaches the issue of personalized, tailored recommendation from a normative perspective. Abstracting from the sophistication of actual recommendation systems, we explore the implications of imposing basic axiomatic principles in a simple formal framework. More specifically, we view a recommendation system as a way to "extend" an agent's preferences to alternatives she has not yet rated, on the basis of some aggregate of other agents' preferences. Preferences here encode the information available to the recommendation system -typically based on a user's ratings or viewing behavior.

Agents might actually be able to rank more alternatives than those they have rated, but such additional rankings are not modeled as the recommendation system cannot take them into account. We implicitly interpret the available information as being truthful, thereby leaving aside strategic considerations. We allow all agents' preferences to be incomplete, i.e. not rank all alternatives -and actually expect these rankings to be quite sparse in practice, given the vast amount of alternatives the above platforms cope with.

Formally, we consider a society of + 1 agents, = 0, 1, … , . Agent 0 is the one to whom we want to give a recommendation. Each agent is endowed with a possibly incomplete preference relation and we look for a recommendation in the form of another possibly incomplete preference relation. The actual list of alternatives suggested to agent 0 can then be generated from this recommendation ranking in various ways -e.g. suggesting the top-ranked alternatives among those available at a given time, or the top-ranked alternatives agent 0 has rated along with the top-ranked ones she has not rated. We do not model this stage and instead focus on desirable properties of the recommendation ranking. We consider two basic axioms:

Acceptance principle Whenever agent 0 has expressed a preference for an alternative over another, the former is recommended over the latter.

Pareto principle Whenever agents 1, … , have expressed a unanimous preference for an alternative over another, the former is recommended over the latter.

The Acceptance principle captures the requirement that the recommendation to agent 0 must extend her preferences whereas the Pareto principle captures the requirement that it must aggregate the other agents'

preferences. As we first show through illustrative examples, this formalization of the recommendation problem makes it apparent that existing collaborative filtering systems violate the Pareto principle.

We then provide a simple and tractable characterization of the recommendations satisfying these two principles. To this end, we assume all agents have expected utility preferences over lotteries. Such preferences, when complete, can be represented by a (cardinal) expected utility function [START_REF] Von Neumann | Theory of games and economic behavior[END_REF] and, when incomplete, by a set of "possible" expected utility functions in the sense that a lottery is preferred to another if and only if all functions in the set unanimously assign a higher expected utility to the former than the latter [START_REF] Baucells | Multiperson utility[END_REF][START_REF] Dubra | Expected utility theory without the completeness axiom[END_REF].

When there is no such unanimity in favor of one of the two lotteries, they are unranked. While in practice the alternatives at stake are usually sure prospects rather than lotteries, one can always take as primitive agents' ratings over sure prospects and derive their preferences over lotteries "parsimoniously" under the expected utility axioms [START_REF] Dubra | A Model of Procedural Decision Making in the Presence of Risk[END_REF].

Our main result establishes that the recommendations satisfying the Acceptance and Pareto principles are those that are based on possible utilities for agent 0 that are also positive linear combinations of possible utilities for agents 1, … , . Roughly speaking, such recommendations hinge upon tailored "virtual guides" who have complete preferences exactly agreeing with those of agent 0 on the alternatives she has ranked, while (linearly) aggregating those of agents 1, … , . The class of such recommendations contains, at one extreme, complete recommendations based on a single virtual guide and, at the other extreme, the most incomplete recommendation based on the whole set of virtual guides. As we illustrate below, even this most incomplete recommendation generally ranks alternatives that agent 0 has not ranked.

The paper is built as follows. We end this introduction with a very brief literature review. Section 2 presents two stylized examples illustrating how the virtual guide recommendations we will later characterize work and contrasting them with typical collaborative filtering systems, in particular with respect to the Pareto principle. Section 3 presents the formal model and results. Besides the main characterization mentioned above, we also characterize a more general class of "signed" virtual guide recommendations and analyze the computation of (signed) virtual guides as well as how to select among them. Section 4 concludes and highlights avenues for future research to go beyond the illustrative examples and simple model presented here. Proofs appear in the Appendix.

There is obviously a huge literature in computer science on recommendation systems that we will not attempt to summarize (see e.g. the survey by [START_REF] Chen | A Survey of Collaborative Filtering-Based Recommender Systems: from Traditional Methods to Hybrid Methods Based on Social Networks[END_REF]. Applications of the axiomatic approach based on social choice concepts seem scarce in this literature [START_REF] Pennock | Social Choice Theory and Recommender Systems: Analysis of the Axiomatic Foundations of Collaborative Filtering[END_REF][START_REF] Altman | An Axiomatic Approach to Personalized Ranking Systems[END_REF]. There is, on the other hand, a large axiomatic literature in economics on preference aggregation (for expected utility preferences in particular, see e.g. [START_REF] Harsanyi | Cardinal Utility in Welfare Economics and in the Theory of Risk-taking[END_REF][START_REF] Harsanyi | Cardinal Welfare, Individualistic Ethics, and Interpersonal Comparisons of Utility[END_REF][START_REF] Weymark | A reconsideration of the Harsanyi-Sen debate on utilitarianism[END_REF][START_REF] Mongin | Social Preference and Social Welfare Under Risk and Uncertainty[END_REF]. A few papers in this literature allow for incomplete preferences [START_REF] Pivato | Risky social choice with incomplete or noisy interpersonal comparisons of wellbeing[END_REF](Pivato, , 2013(Pivato, , 2014;;[START_REF] Danan | Aggregating sets of von Neumann-Morgenstern utilities[END_REF]Danan et al., , 2015[START_REF] Danan | Robust Social Decisions[END_REF]. The standard preference aggregation problem can be seen as the special case of our tailored recommendation problem in which the preferences of the agent to which the recommendation is made are "void" -rank no alternatives. Non-tailored recommendations have been explored axiomatically by e.g. [START_REF] Demange | A ranking method based on handicaps[END_REF]Demange ( , 2017)). [START_REF] Eliaz | The Model Selection Curse[END_REF] consider the problem of providing a tailored recommendation to a user through statistical models estimated on other users rather than aggregation of their preferences. They take the models as given and focus on strategic issues that we ignore here.

Examples

Rich ratings

Consider five alternatives , , , , and three agents 0, 1, 2. Agents' preferences are represented by the following utility functions 0 , 1 , 2 , that one can for instance assimilate to ratings on a scale between 0 and 10 given on an internet platform:

0 3 4 6 -- 1 5 2 10 5 8 2 1 6 2 9 1
We want to give a recommendation to agent 0 by extending her preferences to alternatives and that she has not yet rated, based on the preferences of agents 1 and 2 who have rated all alternatives. The collaborative filtering systems used by popular internet platforms typically fill agent 0's missing rating for alternative = , with:

̄ 0 + 0,1 1 ( ) -̄ 1 + 0,2 2 ( ) -̄ 2 | 0,1 | + | 0,2 | ,
where ̄ is the average of the ratings expressed by agent = 0, 1, 2 -̄ 0 ≈ 4.33, ̄ 1 = 6, ̄ 2 = 3.75 -and 0, is some measure of the similarity between the ratings of agent 0 and those of agent = 1, 2 on the commonly-rated alternatives , , . A typical similarity measure is the Pearson correlation coefficient -0,1 ≈ 0.76, 0,2 = 0 -leading to fill agent 0's missing ratings for alternatives and with 3.33 and 6.33, respectively. This yields the recommendation ranking ≻ ≻ ≻ ≻ .

The "virtual guide" recommendations characterized by the Acceptance and Pareto principles, on the other hand, are based on positive linear combinations of agents 1 and 2's ratings that agree with agent 0's ratings on the commonly-rated alternatives , , . The unique such combination -or virtual guide -is 0.5 1 + 0.5 2 . Hence there is a unique such recommendation, which fills agent 0's missing ratings for and with 0.5 1 ( ) + 0.5 2 ( ) = 7 and 0.5 1 ( ) + 0.5 2 ( ) = 4.5, respectively. This yields the recommendation ranking ≻ ≻ ≻ ≻ . In particular, is recommended over , whereas collaborative filtering systems recommend over . Also, the recommendation follows agents 1 and 2's unanimous preference for over , whereas collaborative filtering systems violate the Pareto principle by recommending over .

Sparse ratings

The above example has two very peculiar features: first, all agents except 0 have rated all alternativestheir preferences are complete -and, second, agent 0 has rated enough alternatives to pin down a unique linear combination of the other agents' ratings. To illustrate how collaborative filtering and virtual guide recommendations cope with sparser ratings, we now consider the same example but taken at an earlier stage when only the following ratings have been expressed:

0 3 4 --- 1 5 2 10 -8 2 1 6 2 9 -
We again want to give a recommendation to agent 0 based on these ratings. For collaborative filtering systems, computing the average ratings and the Pearson correlation coefficients on the commonly-rated alternatives , leads to fill agent 0's missing rating for alternative with 0.375. For alternative , the same approach, discarding agent 1 who has not rated this alternative, leads to filling agent 0's missing rating with ̄ 0 + 2 ( ) -̄ 2 = 8. Finally, for alternative , we similarly discard agent 2 and fill agent 0's missing rating with ̄ 0 -1 ( ) + ̄ 1 = 1.75. This yields the recommendation ranking ≻ ≻ ≻ ≻ , which violates the Pareto principle since both agents 1 and 2 have rated above .

For virtual guide recommendations, we instead look for positive linear combinations 1 1 + 2 2 + that agree with 0 on the commonly-rated alternatives , , where 1 and 2 fill agent 1 and 2's missing ratings for and with any numbers 1 and 2 between 0 and 10, respectively. Such combinations are characterized by the system:

3 = 5 1 + 2 + , 0 ≤ 10 1 + 2 2 + ≤ 10, 0 ≤ 1 , 4 = 2 1 + 6 2 + , 0 ≤ 1 1 + 9 2 + ≤ 10, 0 ≤ 2 , 0 ≤ 8 1 + 2 2 + ≤ 10, 0 ≤ 1 ≤ 10, 0 ≤ 2 ≤ 10,
which is equivalent to:

0 ≤ 1 ≤ 17 14 , 2 = 0.2 + 0.6 1 , 0 ≤ 1 ≤ min 10, 0.2 + 5.4 1 , = 2.8 -5.6 1 , 0 ≤ 2 ≤ min 10, 36 -12 1 1 + 3 1 .
Any such vector ( 1 , 2 , , 1 , 2 ) defines a virtual guide filling agent 0's missing ratings for , , and with 3.2 + 5.6 1 , 4.6 + ( 1 -0.2) 1 , and 2.8 + 0.2 2 + (0.6 2 + 2.4) 1 , respectively. Any set of such virtual guides defines a virtual guide recommendation. All these recommendations have in common that ≻ and ≻ ≻ . At one extreme, the most incomplete of these recommendations is based on unanimity among all virtual guides and makes no further ranking -note though that it does rank some alternatives that agent 0 has not ranked. At the other extreme, complete recommendations are based on a single virtual guide and fully rank the five alternatives -i.e. also rank with respect to and as well as with respect to the other four alternatives). For instance, selecting the single virtual guide 0.5 1 + 0.5 2 with 1 = 5 and 2 = 1 yields the same recommendation ranking ≻ ≻ ≻ ≻ as in the rich ratings example, whereas selecting the single virtual guide 0.1 1 + 0.26 2 + 2.24 with 1 = 5 and 2 = 8 yields the recommendation ranking ≻ ≻ ≻ ≻ .

Model

Expected multi-utility

We let be a finite set of alternatives and consider the set of lotteries -probability distributionsover . A preference relation on is a binary relation ≿ on , where ≿ is interpreted as lottery being weakly preferred to lottery . A preference relation ≿ ′ on extends a preference relation ≿ on if for all , ∈ , ≿ implies ≿ ′ . A preference relation ≿ on is complete if for all , ∈ , either ≿ or ≿ (or both), and incomplete otherwise. Definition 1. A preference relation ≿ on is an expected multi-utility preference relation if there exists a non-empty, compact, convex set of utility functions ∶ → ℝ such that for all , ∈ :

≿ if and only if E ( ) ≥ E ( ) for all ∈ .
Expected multi-utility preferences are generally incomplete and are axiomatized by [START_REF] Baucells | Multiperson utility[END_REF] and [START_REF] Dubra | Expected utility theory without the completeness axiom[END_REF]. They generalize standard expected utility preferences by allowing the set to contain more than one utility function or, equivalently, by allowing ≿ to be incomplete. A lottery is weakly preferred to a lottery if and only if all functions in the set assign a weakly higher expected utility to . If has a strictly higher expected utility for one of these functions whereas has a strictly higher expected utility for another one, the two lotteries are not ranked. The interpretation is that the agent is unsure about her utility function and considers all functions in as possible. The utility functions in are cardinal in the sense of being unique up to positive affine transformations. 1 For technical convenience, we restrict attention to expected multi-utility preferences that can be represented as above with being the convex hull -set of convex combinations -of finitely many utility functions.2 Such preferences are axiomatized in [START_REF] Dubra | A Model of Procedural Decision Making in the Presence of Risk[END_REF]. They naturally arise, in particular, if ≿ is derived from some primitive cardinal ratings of some alternatives in as per Definition 1 with consisting of all possible ways to fill in the missing ratings. 3 For instance, in the rich ratings example, denoting by , 0 the utility function filling agent 0's missing ratings for and with and , respectively, we take 0 = , 0 ∶ , ∈ [0, 10] , 1 = 1 , 2 = 2 and we note that 0 is then the convex hull of the four utility functions 0,0 0 , 0,10 0 , 10,0 0 , 10,10 0 .

We say as usual that two lotteries and are indifferent, denoted, ∼ , if both ≿ and ≿ , and that is strictly preferred to , denoted ≻ , if ≿ but not ≿ . We further say that is strongly preferred to , denoted ⪼ , if ′ ≻ ′ for every lotteries ′ and ′ "sufficiently close" to and , respectively. Formally, with the usual notation for mixed lotteries, ⪼ if for all ′ , ′ ∈ , there exists

∈ (0, 1) such that + (1 -) ′ ≻ + (1 -) ′ .
We have that ∼ if and only if E ( ) = E ( ) for all ∈ , and ≻ if and only if E ( ) ≥ E ( ) for all ∈ with strict inequality for at least one ∈ . We further have, without loss of generality, that ⪼ if and only if E ( ) > E ( ) for all ∈ . 4 Strong preference is thus equivalent to strict preference for complete preferences but more demanding for incomplete preferences. For instance, in the rich ratings example, we have ⪼ 0 ⪼ 0 and ∼ 0 , 2 3 ; , 1 3 -the lottery yielding and with probabilities 2 3 and 1 3 , respectively -as well as ≻ 0 , 6 7 ; , 1 7 but not ⪼ 0 , 6 7 ; , 1 7 .

The recommendation problem

We consider a finite set {0, 1, … , } of at least two agents. Each agent = 0, 1, … , is endowed with an expected multi-utility preference relation ≿ on . We want to give a recommendation to agent 0, in the form of another expected multi-utility preference relation ≿ on satisfying the following two simple properties:

Axiom (Acceptance principle). For all , ∈ , if ≿ 0 then ≿ and if ⪼ 0 then ⪼ . Axiom (Pareto principle). For all , ∈ , if ≿ for all = 1, … , then ≿ .
Acceptance means that the recommendation must extend agent 0's preferences, more specifically preserve her weak and strong preferences. In the rich ratings example, we must therefore have ⪼ ⪼ and ∼ , 2 3 ; , 1 3 as well as ≿ , 6 7 ; , 1 7 but not necessarily ≻ , 6 7 ; , 1 7 . The Pareto principle, on the other hand, expresses the requirement that the recommendation must be based on the preferences 1 More precisely, the closure of the set { + ∶ ∈ , ∈ ℝ + , ∈ ℝ} is unique.

of agents 1, … , . If those agents have a unanimous weak preferences then the recommendation must follow it. In the rich ratings example, we must therefore have ≿ ≿ , ≿ , and ≿ .

We will see below that the Acceptance and Pareto principles together imply that the recommendation must also follow unanimous strong preferences from agents 1, … , in most cases -and in the two examples above in particular, so that we must have ⪼ , ⪼ , and ⪼ in the first example. We will also explain there why we generally do not expect the recommendation to preserve agent 0's strict preferences or follow unanimous strict preferences from agents 1, … , .

Definition 2. The preference relations ≿ 0 , ≿ 1 , … , ≿ are coherent if there are no lotteries and such that ⪼ 0 whereas ≿ for all = 1, … , .

Coherence is obviously necessary for the Acceptance and Pareto principles to be mutually compatible. 5 We will show below that it is sufficient as well. 6 We will also consider below a weakening of the Pareto principle that is more often compatible with the Acceptance principle.

Virtual guide recommendations

We now provide a characterization of the recommendations satisfying the Acceptance and Pareto principles within the expected multi-utility model. Let 0 , 1 , … , be representations of ≿ 0 , ≿ 1 , … , ≿ as per Definition 1, respectively.

Definition 3. A utility function ∶ → ℝ is a virtual guide (for agent 0) if ∈ 0 and = ∑ =1 + for some 1 ∈ 1 , … , ∈ , 1 , … , ∈ ℝ + , ∈ ℝ.
A virtual guide is thus a possible utility function for agent 0 that is also a positive linear combination of possible utility functions for agents 1, … , . It corresponds to a complete preference relation agreeing with that of agent 0 on the alternatives she has ranked while aggregating complete preference relations agreeing with those of agents 1, … , on the alternatives they have ranked, respectively.

We let denote the set of all virtual guides. Because of the cardinal uniqueness of expected multiutility representations, is essentially determined by the preference relations ≿ 0 , ≿ 1 , … , ≿ , independently of their particular representations 0 , 1 , … , . More precisely, choosing different representations 1 , … , leaves unchanged and only affects the coefficients 1 , … , and corresponding to a given virtual guide. Choosing a different representation 0 , on the other hand, causes the virtual guides in to be rescaled accordingly but leaves the corresponding expected utility preferences unchanged.

Proposition 1. A recommendation ≿ satisfies the Acceptance and Pareto principles if and only if it can be represented as per Definition 1 by some set ⊆ of virtual guides.

The recommendations satisfying the Acceptance and Pareto principles are thus exactly those that are based on virtual guides. Any recommendation that is not of this form violates at least one of the two principles -in particular, as we illustrated above, collaborating filtering systems violate the Pareto principle. In the rich ratings example, there is a unique virtual guide and, hence, the corresponding (complete) preference relation is the only possible recommendation. In the sparse ratings example, there are multiple virtual guides and, hence, any subset of corresponds to a possible recommendation. It is possible, in particular, to select a single virtual guide, yielding a complete recommendation as in the first example, but it is also possible to select multiple virtual guides, yielding an incomplete recommendation.

Selecting the whole set yields the most incomplete such recommendation.

Our recommendation problem generalizes the classical preference aggregation problem, which corresponds to the particular case where ≿ 0 is void -or agent 0 has not rated more than one alternative.

In this case the Acceptance principle is trivially satisfied and Proposition 1 boils down to the following statement: ≿ satisfies the Pareto principle with respect to ≿ 1 , … , ≿ if and only if each utility function in is a positive linear combination of some utility functions in 1 , … , . This generalization of [START_REF] Harsanyi | Cardinal Welfare, Individualistic Ethics, and Interpersonal Comparisons of Utility[END_REF]'s aggregation theorem was proved in Danan et al. (2015). Assuming further that ≿ as well as ≿ 1 , … , ≿ are complete, we recover Harsanyi's theorem itself. When ≿ 0 is not void, the Acceptance principle requires each utility function in to be a positive affine transformation of some utility function in 0 . Note that this generally places restrictions on the possible weights entering the linear combinations -sometimes pinning down unique weights as in the rich ratings example -whereas these weights are arbitrary in the pure aggregation setting.

When ≿ 0 contains at least one strong preference -or agent 0 has given different ratings to at least two alternatives -a corollary to Proposition 1 is that the recommendations satisfying the Acceptance and Pareto principles also follow unanimous strong preferences from agents 1, … , : if ⪼ for all = 1, … , then ⪼ . 7 This principle generalizes to incomplete preferences the "Weak Pareto" or "P 2 " principle analyzed by Weymark (1993Weymark ( , 1995) ) and de Meyer and [START_REF] De Meyer | A note on affine aggregation[END_REF] in the aggregation context. On the other hand, recommendations satisfying the Acceptance and Pareto principles generally neither preserve agent 0's strict preferences nor follow unanimous strict preferences from agents 1, … , . For instance, in the sparse ratings example, we have ≻ 0 , 6 7 ; , 1 7 but selecting a single virtual guide filling agent 0's missing rating for alternative with 10 leads to ∼ , 6 7 ; , 1 7 . We also have , 1 2 ; , 1 2 ⪼ 1 and , 1 2 ; , 1 2 ≻ 2 but selecting a single virtual guide filling agent 0's missing ratings for and with 3.2 and 2.8, respectively, leads to , 1 2 ; , 1 2 ∼ . 8

Signed virtual guides

A limitation of the concept of virtual guide is that the weights in the linear combination cannot be negative. Collaborative filtering systems, on the other hand, allow for negative weights, so that the recommendation can possibly draw information from agents whose ratings are negatively correlated with the ratings of agent 0. In order to characterize virtual guide recommendations with possibly negative weights, we now weaken the Pareto principle as follows:

Axiom (Pareto-Indifference principle). For all , ∈ , if ∼ for all = 1, … , then ∼ .

The Pareto-Indifference principle merely requires the recommendation to follow unanimous indifferences from agent 1, … , . It does not require the recommendation to follow unanimous weak preferences from agents 1, … , when some of these weak preferences are strict or strong, opening the possibility to weigh some of these agents negatively.

7 Indeed, in that case, 0 can not contain constant utility functions and, hence, any virtual guide = ∑ =1 + ∈ 0 must be such that > 0 for at least one = 1, … , . 8 In this example, the recommendation could possibly preserve agent 0's strict preferences and/or follow unanimous strict preferences from agents 1, … , , depending on which virtual guides are selected. Other examples can be constructed where that is not possible. Definition 4. The preference relations ≿ 0 , ≿ 1 , … , ≿ are weakly coherent if there are no lotteries and such that ⪼ 0 whereas ∼ for all = 1, … , .

Weak coherence is substantially weaker than coherence and we expect it to hold in most practical cases. It is obviously necessary for the Acceptance and Pareto-Indifference principles to be mutually compatible and we will show below that it is also sufficient.

Definition 5. A utility function ∶ → ℝ is a signed virtual guide (for agent 0) if ∈ 0 and

= ∑ =1 - + for some 1 , 1 ∈ 1 , … , , ∈ , 1 , 1 , … , , ∈ ℝ + , ∈ ℝ.
A signed virtual guide is thus a possible utility function for agent 0 that is also the difference of two positive linear combinations of possible utility functions for agents 1, … , . In the sparse ratings example, the utility function = 3 0 2 -2.8 1 2 + 2.8, where 0 2 and 1 2 fill agent 2's missing rating for alternative with 0 and 1, respectively, is a signed virtual guide but not a virtual guide. 9 We let denote the set of all signed virtual guides. Like the set of virtual guides, is essentially determined by the preference relations ≿ 0 , ≿ 1 , … , ≿ , independently of their particular representations 0 , 1 , … , .

Proposition 2. A recommendation ≿ satisfies the Acceptance and Pareto-Indifference principles if and only if it can be represented as per Definition 1 by some set ⊆ of signed virtual guides.

Computing (signed) virtual guides

We now show that the set of (signed) virtual guides can be computed simply by solving a finite linear system. This allows us to deduce some properties of this set and, in particular, to identify the cases where it is empty -or, equivalently, where (signed) virtual guide recommendations do not exist. To this end, we enumerate as { 1 , … , } the finite set of alternatives, where ≥ 1 denotes the number of alternatives. For all = 0, 1, … , , we also enumerate as { ,1 , … , , ( ) } the finite set of utility functions of which is the convex hull, where ( ) ≥ 1 denotes the number of such functions. A utility function ∶ → ℝ then belongs to if and only if = ∑ ( ) =1 , , for some ,1 , … , , ( ) ∈ ℝ + such that ∑ ( ) =1 , = 1. Virtual guides then correspond to solutions to the finite system:

∑ (0) =1 0, 0, ( ) = ∑ =1 ∑ ( ) =1 , , ( ) + , = 1, … , , 1 = ∑ ( ) =1 , , = 0, 1, … , , 0 ≤ , , = 0, 1, … , , = 1, … , ( ), 0 ≤ , = 0, 1, … , .
Defining , =

, for all = 1, … , and = 1, … , ( ), it is sufficient to solve the finite linear system:

∑ (0) =1 0, 0, ( ) = ∑ =1 ∑ ( ) =1 , , ( ) + , = 1, … , , 1 = ∑ (0) =1 0, , 0 ≤ 0, , = 1, … , (0), 0 ≤ , , = 1, … , , = 1, … , ( ).
(1) Proposition 3. is non-empty if and only if ≿ 0 , ≿ 1 , … , ≿ are coherent. Moreover, is then the convex hull of finitely many utility functions.

Similarly, signed virtual guides correspond to solutions to the finite system:

∑ (0) =1 0, 0, ( ) = ∑ =1 ∑ ( ) =1 ( , - , ) , ( ) + , = 1, … , , 1 = ∑ ( ) =1 , , = 0, 1, … , , 1 = ∑ ( ) =1 , , = 1, … , , 0 ≤ , , = 0, 1, … , , = 1, … , ( ), 0 ≤ , , = 1, … , , = 1, … , ( ), 0 ≤ , = 0, 1, … , , 0 ≤ , = 0, 1, … , .
Defining , = , -,1 for all = 1, … , and = 1, … , ( ), it is sufficient to solve the finite linear system:

∑ (0) =1 0, 0, ( ) = ∑ =1 ∑ ( ) =1 , , ( ) + , = 1, … , , 1 = ∑ (0) =1 0, , 0 ≤ 0, , = 1, … , (0).
(2) Proposition 4. is non-empty if and only if ≿ 0 , ≿ 1 , … , ≿ are weakly coherent. Moreover, is then the convex hull of finitely many utility functions.

Selecting among (signed) virtual guides

As the sparse ratings example illustrates, which (signed) virtual guides are selected can critically impact the recommendation. Axiomatically characterizing particular subclasses of virtual guide recommendations -or even a single recommendation -would therefore provide useful guidance in this regard. To this end, it seems natural to extend the present framework by considering a recommendation rule associating a recommendation ≿ = ≿ 0 , ≿ 1 , … , ≿ to each preference profile ≿ 0 , ≿ 1 , … , ≿ in some domain . We shall more specifically consider the domains and of coherent and weakly coherent profiles, respectively, and say that satisfies the Acceptance (resp. Pareto, Pareto-Indifference) principle if ≿ 0 , ≿ 1 , … , ≿ satisfies this principle for all ≿ 0 , ≿ 1 , … , ≿ ∈ . This extended framework makes it possible to express additional principles, such as the following ones.

Axiom (Anonymity principle). For all ≿

0 , ≿ 1 , … , ≿ , ≿ 0 , ≿ ′ 1 , … , ≿ ′ ∈ , if ≿ ′ 1 , … , ≿ ′ is a permutation of ≿ 1 , … , ≿ then ≿ 0 , ≿ ′ 1 , … , ≿ ′ = ≿ 0 , ≿ 1 , … , ≿ . Axiom (Internal-Robustness principle). For all ≿ 0 , ≿ 1 , … , ≿ , ≿ ′ 0 , ≿ 1 , … , ≿ ∈ , if ≿ ′ 0 extends ≿ 0 then ≿ ′ 0 , ≿ 1 , … , ≿ extends ≿ 0 , ≿ 1 , … , ≿ . Axiom (External-Robustness principle). For all ≿ 0 , ≿ 1 , … , ≿ , ≿ 0 , ≿ ′ 1 , … , ≿ ′ ∈ , if ≿ ′ extends ≿ for all = 1, … , then ≿ 0 , ≿ ′ 1 , … , ≿ ′ extends ≿ 0 , ≿ 1 , … , ≿ .
Anonymity means that no agent = 1, … , has more "intrinsic" influence on the recommendation than another. The Internal-Robustness and External-Robustness principles express the idea that as agent 0 or agents 1, … , rate more alternatives, and provided the preference profile remains coherent or weakly coherent, the recommendation becomes more complete without reversing previous rankings. For instance, ≿ from the rich ratings example extends ≿ from the sparse ratings example for = 0, 1, 2. If all virtual guides are kept in the sparse ratings example, then the rich ratings recommendation ranking extends the sparse ratings recommendation ranking, in accordance with the two robustness principles. If, on the other hand, the single virtual guide 0.1 5 1 + 0.26 8 2 + 2.24 is selected in the sparse ratings example, then the sparse ratings recommendation ranking is partly reversed by the rich ratings recommendation ranking, violating at least one of these two principles.10 Proposition 5. There exists a unique recommendation rule on satisfying the Acceptance, Pareto, and Internal-Robustness principles, which consists in selecting all virtual guides for all profiles. This rule also satisfies the Anonymity and External-Robustness principles.

Proposition 6. There exists a unique recommendation rule on satisfying the Acceptance, Pareto-Indifference, and Internal-Robustness principles, which consists in selecting all signed virtual guides for all profiles. This rule also satisfies the Anonymity and External-Robustness principles.

The most incomplete (signed) virtual guide recommendation rule is thus the only one that is compatible with the Internal-Robustness principle. In view of this result, we may call this rule the robust (signed) virtual guide recommendation rule. Note that the statements in Propositions 6 and 7 are well defined because, as explained above, the set of (signed) virtual guides is essentially determined by the preference profile independently of the chosen representations. One may therefore choose arbitrary representations in order to compute the recommendation ranking. A feature of this rule that might be of practical interest is that the recommendation ranking can be computed "incrementally" by dropping (signed) virtual guides as new ratings arrive.

Although the Internal-Robustness principle is clearly a very demanding requirement, the above results suggest that a certain degree of incompleteness in the recommendation ranking might help obtaining more "stable" recommendations. We note in this regard that the External-Robustness principle is weaker than the Internal-Robustness principle in our framework.11 It is nevertheless incompatible with complete recommendation rules.

Proposition 7. If contains at least three alternatives then there exists no recommendation rule on (resp. ) satisfying the Acceptance, Pareto (resp. Pareto-Indifference), and External-Robustness principles that yields a complete recommendation for all profiles.

Conclusion

We view the present paper's contribution as mainly conceptual: the illustrative examples and simple model we presented demonstrate how an axiomatic analysis of recommendation systems in terms of preference aggregation and extension can provide important insights into their normative properties. We showed in particular that collaborative filtering systems -used by popular internet platforms -typically violate the Pareto principle and characterized a new class of recommendation rules -based on virtual guides -satisfying this principle. Finally, we extended our formal framework to identify a particular rule within this class -the robust virtual guide recommendation rule. This rule has interesting stability properties but is arguably quite extreme. A natural avenue for future research is therefore to characterize more complete rules in this extended setting. It also seems interesting to go beyond this setting and do away with lotteries or allow for strategic behavior.

On the practical side, one may want to go beyond illustrative examples to assess how frequently do collaborative filtering systems violate the Pareto principle and how different are collaborative filtering and virtual guide recommendations from each other. Doing so would require an empirically relevant dataset, perhaps stochastically generated to avoid the endogeneity that some real datasets are based on the use of a particular recommendation system. We may wonder, in particular, whether virtual recommendation rules help alleviate some of the difficulties typically associated with collaborative filtering systems.

A first such difficulty is that collaborative filtering systems generally struggle to produce recommendations for "gray sheep" users, i.e. agents whose ratings are not highly correlated -positively or negatively -with those of any other agent. One may expect this issue to be less prevalent for virtual guide recommendations, because they rely on virtual agents whose ratings exactly match those of agent 0 rather than on real agents whose ratings are "close" to those of agent 0. These virtual agents are aggregates of real agents, but these real agents can as well be "close" or "remote" to agent 0.

A second difficulty is that collaborative filtering systems tend to forgo "diversity" by focusing on alternatives that have been rated by many agents, at the expense of less rated -perhaps newer -ones.

Virtual guide recommendations seem to suffer less from this bias: even if an alternative has received no or few ratings, there will generally be virtual guides assigning a range of ratings to it. Opting for an incomplete recommendation rather than a complete one may in fact be useful in this regard, because more such alternatives will be at the top of the recommendation ranking.

A third difficulty is that collaborative filtering systems can be manipulated by "shilling attacks", i.e.

by injecting a large number of fake ratings in order to promote or demote some alternatives. Although the present model leaves strategic considerations aside and considers a fixed set of agents, we may note that virtual recommendations are not immune to the injection of a fake agent either, as this may enlarge the set of virtual guides and, hence, affect the recommendation. The set of virtual guides is, however, immune to injecting additional "clones" of this fake agent, as it does not depend on how many agents with a given preference relation there are. Furthermore, injecting additional agents that are "close" to the first one generally does not affect this set substantially. Whether and how the recommendation is affected by the injection of additional clones then depends on which virtual guides are selected.

Appendix: Proofs

We derive Propositions 1 and 2 from slightly more general results. To this end we consider the following weakening of the Acceptance principle.

Axiom (Weak Acceptance principle). For all , ∈ , if ≿ 0 then ≿ .

Lemma 1. Let be a representation of ≿ as per Definition 1.

(a) ≿ satisfies the Weak Acceptance and Pareto principles if and only if, for all ∈ , there exist

0 ∈ 0 , 1 ∈ 1 , … , ∈ , 0 , 1 , … , ∈ ℝ + , 0 , ∈ ℝ such that: = 0 0 + 0 = ∑ =1 + . ( 3)
(b) ≿ satisfies the Weak Acceptance and Pareto-Indifference principles if and only if, for all ∈ , there

exist 0 ∈ 0 , 1 , 1 ∈ 1 , … , , ∈ , 0 , 1 , 1 , … , , ∈ ℝ + , 0 , ∈ ℝ such that: = 0 0 + 0 = ∑ =1 ( - ) + . (4)
Proof. (a) It is obvious that if (3) holds then ≿ satisfies the Weak Acceptance and Pareto principles. Conversely, assume (3) does not hold. Then at least one ∈ must lie outside at least one of the two sets = { 0 0 + 0 ∶ 0 ∈ 0 , 0 ∈ ℝ + , 0 ∈ ℝ} and

= ∑ =1 + ∶ 1 ∈ 1 , … , ∈ , 1 , … , ∈ ℝ + , ∈ ℝ .
Note that both and are closed, convex cones in ℝ .

Case 1. If ∉ then, by the separating hyperplane theorem, there exists ℎ ∈ ℝ , ℎ ≠ 0, such that

∑ ∈ ℎ( ) ( ) > 0 ≥ ∑ ∈ ℎ( ) (
) for all ∈ . Since + ∈ for all ∈ and ∈ ℝ, this can only be the case if ∑ ∈ ℎ( ) = 0, for otherwise we could make

∑ ∈ ℎ( )( ( ) + ) = ∑ ∈ ℎ( ) ( ) + ∑ ∈ ℎ
( ) arbitrarily large by taking sufficiently close to +∞ or -∞. Hence, letting = ∑ ∈ |ℎ( )| and defining , ∈ ℝ by ( ) = max{ℎ( ),0} and ( ) = max{-ℎ( ),0} , we have > 0, , ∈ , and ℎ = ( -). Since ∑ ∈ ℎ( ) ( ) > 0, it follows that E ( ) > E ( ), so it cannot be the case that ≿ by Definition 1. But since 0 ⊂ , it also follows that 0 ≥ ∑ ∈ ℎ( ) 0 ( ) and, hence, E 0 ( ) ≥ E 0 ( ) for all 0 ∈ 0 , so that ≿ 0 by Definition 1. This contradicts the Weak Acceptance principle.

Case 2. If ∉ then, by the separating hyperplane theorem, there exists ℎ ∈ ℝ , ℎ ≠ 0, such that

∑ ∈ ℎ( ) ( ) > 0 ≥ ∑ ∈ ℎ( ) (
) for all ∈ . By the same argument as in Case 1, we must have ∑ ∈ ℎ( ) = 0 and, hence, we can write ℎ = ( -) with > 0 and , ∈ . Since ∑ ∈ ℎ( ) ( ) > 0, it follows that E ( ) > E ( ), so it cannot be the case that ≿ by Definition 1. But for all = 1, … , , since ⊂ , it also follows that 0 ≥ ∑ ∈ ℎ( ) ( ) and, hence, E ( ) ≥ E ( ) for all ∈ , so that ≿ by Definition 1. This contradicts the Pareto principle.

(b) It is obvious that if (4) holds then ≿ satisfies the Weak Acceptance and Pareto-Indifference principles. Conversely, assume (4) does not hold. Then at least one ∈ must lie outside at least one of the two sets and:

′ = ∑ =1 ( - ) + ∶ 1 , 1 ∈ 1 , … , , ∈ , 1 , 1 , … , , ∈ ℝ + , ∈ ℝ .
We then proceed as in the proof of Part (a), except that in Case 2, since ′ is a linear subspace of ℝ , the separating hyperplane theorem now implies that

∑ ∈ ℎ( ) ( ) > 0 = ∑ ∈ ℎ( ) (
) for all ∈ ′ . Hence for all = 1, … , , we now have E ( ) = E ( ) for all ∈ , so that ∼ by Definition 1, which contradicts the Pareto-Indifference principle.

Proof of Proposition 1. It is obvious that if ≿ can be represented as per Definition 1 by some set ⊆ of virtual guides, then it satisfies the Acceptance and Pareto principles. Conversely, assume ≿ satisfies these two principles and fix some representation of ≿ as per Definition 1. Then for all ∈ , (3) holds by Lemma 1(a). It is sufficient to show that (3) actually holds with 0 > 0 for some 0 ∈ 0 , since then the closed convex hull of the set -0 0 ∶ ∈ also represents ≿ as per Definition 1 and is a subset of . So suppose (3) does not hold with 0 > 0 for any 0 ∈ 0 . Note that this implies that is a constant function whereas 0 contains no constant function. Hence, by the separating hyperplane theorem, there exists ℎ ∈ ℝ , ℎ ≠ 0, such that ∑ ∈ ℎ( ) 0 ( ) > ∑ ∈ ℎ( ) for all 0 ∈ 0 and ∈ ℝ. By the same argument as in Case 1 of the proof of Lemma 1(a), we must have ∑ ∈ ℎ( ) = 0 and, hence, we can write ℎ = ( -) with > 0 and , ∈ . For all 0 ∈ 0 , since ∑ ∈ ℎ( ) 0 ( ) > 0, it follows that E 0 ( ) > E 0 ( ) and, hence, ⪼ 0 . The Acceptance principle then implies that ⪼ , contradicting the fact that contains a constant function.

Proof of Proposition 2. Similar to the proof of Proposition 1.

Proof of Proposition 3. Letting = + --with + , -∈ ℝ + in (1), is non-empty if and only if the following finite linear system has a non-negative solution: Suppose ≿ cannot be represented as per Definition 1 by . By the uniqueness of expected multiutility representation and our finiteness assumption, we must then have { + ∶ ∈ , ∈ ℝ + , ∈ ℝ} ≠ { + ∶ ∈ , ∈ ℝ + , ∈ ℝ} and, hence, there must exist some ∈ that does not belong to { + ∶ ∈ , ∈ ℝ + , ∈ ℝ}. By the same argument as in Case 1 of the proof of Lemma 1(a), it follows that there exist , ∈ such that E ( ) > ( ) whereas E ( ) ≥ E ( ) for all ∈ . Hence, letting ≿ ′ 0 be represented as per Definition 1 by 0 , we have ⪼ ′ 0 . On the other hand, letting ≿ ′ = ( ≿ ′ 0 , ≿ 1 , … , ≿ , we have ≿ ′ by the Internal-Robustness principle. This contradicts the Acceptance principle.

0 = ∑ (
Proof of Proposition 6. Similar to the proof of Proposition 5.

Proof of Proposition 7. Assume contains at least three alternatives , , , let , ′ ∶ → ℝ be such that ( ) = ′ ( ) = 1 and ( ) = ′ ( ) = ( ) = ′ ( ) = 0, and let denote the convex hull of { , ′ }. Note that for all , ∈ , if ≠ then there exist , ∈ such that E ( ) > E ( ) whereas E ( ) > E ( ). Now let be a recommendation rule on (resp.

) satisfying the Acceptance and Pareto (resp. Pareto-Indifference) principles that yields a complete recommendation for all profiles.

Let ≿ be represented as per Definition 1 by and ≿ ′ = ≿, ≿, … , ≿ . Then by Proposition 1 (resp. 2), ≿ ′ can be represented as per Definition 1 by { } for some ∈ . Let ≿ ′′ be represented by some ∈ ⧵ { } and ≿ ′′′ = ≿, ≿ ′′ , … , ≿ ′′ . Again by Proposition 1 (resp. 2), ≿ ′′′ can be represented as per Definition 1 by { }. Hence ≿ ′′′ does not refine ≿ ′ , so does not satisfy the External-Robustness principle.

  Lemma, this system has a non-negative solution if and only if there exist no ℎ ∈ ℝ and ∈ ℝ such that: , and Internal-Robustness principles. Consider a profile ≿0 , ≿ 1 , … , ≿ ∈ and let ≿ = ≿ 0 , ≿ 1 , … , ≿ . Fixing arbitrary representations 0 , 1 , … , of ≿ 0 , ≿ 1 , … , ≿ , respec-tively, let denote the corresponding set of virtual guides. Then by Proposition 1, ≿ can be represented as per Definition 1 by some set ⊆ .

This allows us to dispense with the closure operator in the uniqueness statement above as well as the closedness assumption ofDanan et al. (2015).

While in the examples above we consider possible any rating within the allowed scale, our framework can accommodate alternative specifications (for instance, one might consider intermediate ratings only).

It is without loss of generality in the sense that we can always choose a representation such that this holds.

Indeed, if there are lotteries and such that ⪼ 0 whereas ≿ for all = 1, … , , then the Acceptance principle implies ⪼ whereas the Pareto principle implies ≿ , a contradiction.

This is not trivial because of our restriction to expected multi-utility preferences.

Indeed, fills agent 0's missing ratings for alternatives , , and with 3.2, 4.6, and 0, respectively, whereas all virtual guides fill agent 0's missing rating for with at least 2.8. Note that cannot be obtained as a linear combination 1 1 + 2 2 + with 1 ∈ 1 , 2 ∈ 2 , and 1 , 2 , ∈ ℝ.

Collaborative filtering systems, on the other hand, satisfy the anonymity principle but violate the two robustness principles.

For instance, any recommendation rule that selects a single (signed) virtual guide whenever ≿ 1 , … , ≿ are complete but keeps all (signed) virtual guides otherwise satisfies the Acceptance, Pareto (resp. Pareto-Indifference) and External-Robustness principles but not the Internal-Robustness principle.

the conference Times, Uncertainty and Strategy (Dec. 2018) and the CHOp Workshop, for useful feedback. This work is part of the project "Coping with Heterogeneous Opinions", which benefits from the support of the grant ANR-17-CE26-0003. Danan acknowledges financial support from the grants ANR-11-LBX-0023-01 and ANR-16-IDEX-0008. Tallon acknowledges financial support from the grant ANR-17-EURE-001.

or, equivalently, if there exists no ℎ ∈ ℝ such that:

By the same argument as in Case 1 of the proof of Lemma 1(a), this is equivalent to the non-existence of lotteries , ∈ such that ⪼ 0 and ≿ for all = 1, … , . The fact that is then the convex hull of finitely many functions simply follows from the finiteness and linearity of the above system as well as the fact that is a subset of the compact set 0 .

Proof of Proposition 4. Letting , = + , -- , and = + --where + , , - , , + , -∈ ℝ + in (2), is non-empty if and only if the following finite linear system has a non-negative solution:

By Farkas' Lemma, this system has a non-negative solution if and only if there exist no ℎ ∈ ℝ and ∈ ℝ such that:

or, equivalently, if there exists no ℎ ∈ ℝ such that:

By the same argument as in Case 1 of the proof of Lemma 1(a), this is equivalent to the non-existence of lotteries , ∈ such that ⪼ 0 and ∼ for all = 1, … , . The fact that is then the convex hull of finitely many functions simply follows from the finiteness and linearity of the above system as well as the fact that is a subset of the compact set 0 .

Proof of Proposition 5. It is obvious that the recommendation rule on consisting in selecting all virtual guides for all profiles satisfies the Acceptance, Pareto, Internal-Robustness, Anonymity, and External-Robustness principles. Conversely, let be a recommendation rule on satisfying the Ac-