A B S T R A C T

This thesis presents research I conducted since obtaining my PhD in computational social choice, an interdisciplinary field of research which lies between artificial intelligence (in particular multi-agent systems, knowledge representation and reasoning), economics, and political science, and whose aim is the analysis of collective decisionmaking processes with tools from theoretical computer science.

My work aims at enriching social choice models under three aspects, corresponding to the three main chapters of this document: (a) take into account the interactions between voters with the introduction of an influence network or a communication network, (b) model the strategic behaviour of voters, (c) increase the expressiveness of the voting ballots whilst keeping the computational complexity of the decision process tractable. The introductory chapter presents the main lines of research of my work, gives a summary of the chapters, and defines the basic concepts for understanding the results that follow. The technical sections are supplemented with examples to quickly grasp the interest and scope of the results presented.

In Chapter 2 I augment the classic model of social choice with a network that connects voters and that can represent a network of influence or of communication between the agents. A large part of the chapter is dedicated to study models of opinion diffusion on a network which are adapted to voting situations and to proposing a model of strategic opinion diffusion. Two problems of algorithmic design are then presented. The first which enriches the system of liquid democracy with multi-agent and ranked delegations, and the second which proposes a notion of collective evaluation which is more resistant to bribery thanks to the use of the underlying network.

Chapter 3 introduces the notion of a voting game, in which the strategic dimension of voters' behaviour is taken into account. First, I define and study a class of games named after the famous Gibbard-Satterthwaite theorem, which allow to zoom in on a subset of strategic agents with restricted actions. Next, in a voting situation on several binary questions, I show how the use of pre-vote negotiations can be used as a selector of desirable Nash equilibria. The chapter concludes with the presentation of several results on iterative voting, using techniques from multi-agent simulation, reinforcement learning, and experimental economics.

Chapter 4 focuses on the expressiveness of voters, especially in the case of combinatorial voting, when the set of alternatives is of exponential size. Several approaches are presented, developing on a motivating example of planning a group activity. I begin with a detailed comparison of several judgment aggregation frameworks in terms of succinctness (i.e., the size of the representation of a problem). Then, I present a voting system based on the elicitation of propositional goals. Finally, I analyse the axiomatic properties and the computational complexity of three voting rules inspired by the majority rule. Increasing further in expressiveness, I then study the aggregation of incomplete conditional preferences and I define a voting rule for the analysis of a collective sentiment enriched with the extraction of comparative preferences.

Each chapter is concluded by a presentation of the main open problems and of future directions of research specific to the materials presented in the chapter. In the conclusion (Chapter 5) I sketch a research project motivated by the development of autonomous artificial agents which can act as intermediaries in a collective decision.

R É S U M É E N F R A N Ç A I S

Dans ce document, je présente les résultats de mes recherches depuis l'obtention de mon doctorat en suivant un fil conducteur qui en montre les évolutions. Mes recherches se situent en choix social computationnel, c'est-à-dire, l'analyse avec des outils d'informatique théorique de processus de décisions collectives prises par un ensemble d'agents autonomes. Il s'agit d'un champ de recherche multidisciplinaire qui se situe entre l'intelligence artificielle (notamment les systèmes multiagents, la représentation et le raisonnement sur des connaissances), l'économie, et les sciences politiques. Pour ce qui concerne les travaux présentés ici, les techniques d'analyse utilisées et les applications visées, ils sont tous pour la plupart dans le domaine de l'intelligence artificielle.

Mes travaux ont pour but d'enrichir les études de choix social sous trois aspects, correspondants aux trois chapitres principaux de ce document: (a) prendre en compte les interactions entre votants avec l'introduction d'un réseau d'influence ou de communication, (b) modéliser le comportement stratégique des votants et, (c) augmenter l'expressivité des bulletins de vote (qu'il ne faut pas imaginer en papier!) tout en restant dans des classes de complexité computationnelle acceptables. Le chapitre introductif présente les grandes lignes de recherche dans lequel mon travail s'inscrit, donne un résumé du contenu des chapitres et définit les notions de bases pour la compréhension des résultats qui suivent. La plupart des sections techniques sont agrémentées d'exemples pour pouvoir rapidement saisir l'intêrét et la portée des résultats présentés.

Dans le Chapitre 2, j'augmente le modèle classique du choix social avec un réseau qui connecte les votants et qui peut représenter un réseau d'influence ou de communication entre agents. Une grande partie du chapitre est dédiée à étudier des modèles de diffusion d'opinion sur un réseau qui sont adaptés à des situations de vote et à ébaucher un modèle de diffusion stratégique. Deux études de conception algorithmique sont ensuite présentées. La première qui enrichit le système de démocratie liquide avec des délégations multiagents et classées. La seconde définit une notion d'évaluation collective qui est plus résistante à la subornation grâce à l'utilisation d'un réseau.

Le Chapitre 3 introduit la notion d'un jeu de vote, dans lequel la dimension stratégique des votants est prise en compte. Premièrement, je définis et étudie la classe des jeux de Gibbard-Satterthwaite, qui permet de zoomer sur un sous-ensemble d'agents stratégiques avec actions restreintes. Ensuite, dans une situation de vote sur plusieurs questions binaires, je montre comment l'utilisation de négociations précédant le vote peut être utilisée comme sélecteur d'équilibres de Nash désirables. Le chapitre se conclut avec la présentation de plusieurs travaux autour du vote itératif, avec des techniques de simulation multiagents, d'apprentissage par renforcement et d'économie expérimentale.

Le Chapitre 4 se concentre sur l'expressivité des votants, notamment en cas de vote combinatoire, quand l'ensemble des alternatives décisionnelles est de taille exponentielle. Plusieurs approches y sont présentées, s'appuyant sur un exemple de planification d'activités en groupe. Je commence par une comparaison détaillée des cadres d'agrégations des jugements sous l'angle de la concision (la taille de représentation d'un problème). Ensuite, je présente un système de vote fondé sur l'élicitation des buts propositionnels. Enfin, j'analyse les propriétés axiomatiques et la complexité computationnelle de trois règles de vote inspirées de la règle de majorité. Tout en montant en complexité d'élicitation, j'étudie ensuite l'agrégation des préférences conditionnelles incomplètes et je définis une règle de vote pour l'analyse du sentiment collectif enrichi avec l'extraction de préférences comparatives.

Tous les chapitres se terminent avec une présentation des problèmes ouverts et des futures directions de recherches spécifiques aux matériels présentés. Dans la conclusion (Chapitre 5) j'expose un projet de recherche fédérateur autour du développement d'agents artificiels autonomes qui puissent agir en tant qu'intermédiaires dans un processus de décision collective.

Facesti come quei che va di notte che porta il lume dietro a sè e non giova Ma dopo sè fa le persone dotte -Purgatorio, XXII 67-69

A C K N O W L E D G E M E N T S
I was very lucky in my professional life to meet a number of excellent teachers, supervisors, and colleagues who taught me how to do the complex job of a researcher (and it's certainly not over). This document should prove that I am now able to supervise the work of others, and I could not find a better image of this mission than the citation above by Dante: using one's lamp not to light up one's path, but the path of others.

Without all colleagues, PhD students, and Master students with whom I collaborated this thesis will be empty. Their names are mentioned in the relevant chapters (apologies if I forgot anyone), and they deserve one big thank for the great time we spent together.

This document was mostly written at home during the COVID-19 pandemic. Many people did not share the same luck of staying safely at home and kept vital aspects of our societies running. This thesis is dedicated to them.

Finding the motivation to write this thesis was possible thanks to the support (at times the pressure) of Sophie, who was probably preoccupied of giving me an occupation while she was busy nurturing our child in her growing belly. I am now done writing and I am excited to welcome him!

I N T R O D U C T I O N

The study of social choice was deeply transformed when computer scientists started analysing the algorithmic aspects of collective decision making, leading to the thriving field of research of computational social choice (for introductions to the field see, e.g., [START_REF] Brandt | Handbook of Computational Social Choice[END_REF] and [START_REF] Rothe | Economics and Computation, An Introduction to Algorithmic Game Theory[END_REF]). In more recent years a second transformation is ongoing, less algorithmic in nature. Researchers are moving closer to applications and real-world situations by, e.g., simulating collective decisions in a lab (see, e.g., [START_REF] Regenwetter | Behavioral Social Choice: Probabilistic Models, Statistical Inference, and Applications[END_REF]), developing online applications for voting or fair division such as Whale 1 and Spliddit, 2 collecting datasets of voters preferences, 3 or augmenting the formal models of social choice with more complex agents' architectures. 4 Research presented in this thesis belongs to this second wave, and aims at enriching social choice studies focussing on three aspects of collective decisions: the interaction among voters, their strategic behaviour, and the expressive power of the voting ballots.

But what is social choice? Social choice studies situations in which a set of autonomous agents need to take a collective decision, i.e., choosing among a set of alternatives on which each agent has individual preferences. Classical examples include the election of candidates, the allocation of resources, or the fair division of goods. It is a problem of a cooperative nature, as the alternative is chosen for the entire group of decision-makers, but the competitive aspect is dominant, as each agent has different and possibly conflicting preferences over the alternatives. The axiomatic method is one of the main techniques used by researchers in social choice theory to advance their knowledge, specifying a number of desiderata for a given collective decision rule, and then exploring the space so-defined, eventually characterising all such rules or prove that there is none. Cornerstone results using this method are Arrow's theorem and the Gibbard-Sattertwhaite theorem, which are both impossibilities, as well as the axiomatic characterisation of the majority rule proven by May's theorem. Computational and algorithmic properties have been added to classical fairness desiderata, such as requir-ing the existence of tractable algorithms for the computation of the vote outcome, or, symmetrically, that manipulating the result be computationally intractable as a barrier against malevolent behaviour by the agents involved. A complete introduction to the field can be found in the Handbook of Social Choice and Welfare [START_REF]Handbook of Social Choice and Welfare[END_REF] for the economics and political science approaches, and in the Handbook of Computational Social Choice [START_REF] Brandt | Handbook of Computational Social Choice[END_REF] for a recent survey of the computational aspects.

And why is it relevant for artificial intelligence?

Research in multiagent systems, the area of artificial intelligence (AI) that studies the interaction of autonomous agents, received modern foundations from mathematical economics, and game theory in particular (see, e.g., [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF][START_REF] Wooldridge | An introduction to multiagent systems[END_REF]). Collective decisions are examples of the possible interactions in a multiagent system, but one that requires a vast number of techniques in AI and that touches most aspects of the autonomous agents architecture. Moreover, even in applications that are far from traditional problems in AI, any computational study of a social choice problem would require knowledge of both economics and computer science techniques that are in the toolbox of an AI researcher. The fruitfulness of marrying economics models in social choice with AI and computational techniques is testified by applications such as the recent interest in e-democracy, the advent of group recommender systems, and the development of matching procedures at large scale.

motivating example: automated personal assistants

Let us consider an idealised situation, which will provide examples for the main issues that this thesis will touch upon: Example 1.1.1 (Personal assistants fixing a meal). 5 Consider five automated personal assistants which are given instructions by their owners to organise a meal at a restaurant for the five of them. Each owner specified their preference to her assistant, and gave access to her calendar. After a brief automated discussion it becomes clear that the conflicting issues to be decided upon are:

• whether the restaurant should be in the center or in the suburbs,

• lunch or dinner,

• fancy or casual restaurant.

The automated personal assistants thus form a multiagent system who has to take a collective decision on three issues.

The example above considers a collective decision of low stake such as organising a meal, but similar examples could be constructed about higher-stake decisions such as the selection of candidates in a hiring process, the choice of which products a company should invest on, or policy features.

There are three aspects of collective decisions on which this thesis focuses on, corresponding to the three main chapters. First, let us consider a network of trust that relates the five personal assistants of Example 1.1.1, modelling the interactions among the decision-makers. This will be the focus of Chapter 2:

Example 1.1.2 (Interactive social choice). Barbara told her assistant to do whatever Martin said on whether the restaurant should be fancy, or whether it should be in the center or not, but that she would prefer lunch over dinner. Cathy told her assistant that she would conform to the majority of the others about fancy or casual (except for Barbara), and that she would prefer to have dinner in the center. The other three owners gave direct preferences on the three issues to their assistants. The situation induces an influence network among the agents which can be depicted in the figure below, with dashed arrows corresponding to the first issue, and thick ones to the third issue:

Martin

Robert Ann

Cathy Barbara

The five automated assistants know which other agents they trust, and their preference for the final vote will depend on the opinions of the other assistants. Depending on the discussion protocol they chose they might end up in an infinite loop of influence constantly changing their mind. Some of them might actually have this situation as a meta-goal, to prevent a decision to be taken and gain time...

Let us now focus on the strategic abilities of the automated assistants, who can reason about each others' preferences and act accordingly. Chapter 3 will study situations such as the following one:

Example 1.1.3 (Strategic social choice). Let us focus on three automated assistants only. Barbara asked her assistant to organise the meal either in the center or for lunch (or both). Martin wishes to have either lunch or to be in a fancy restaurant (or both). And Ann would like a restaurant in the center or a fancy one, or both. Clearly, having lunch in the center in a fancy restaurant would satisfy the three of them. Their personal assistants decide to resolve the issue by a quick majority vote on each of the three questions. The result could be the following:

Barbara

Center Dinner Casual Martin Suburbs Lunch Casual Ann Suburbs Dinner Fancy

Majority Suburbs Dinner Casual

The result that the assistants will propose as the outcome of the majority vote is completely unsatisfactory as it does not satisfy any of the specified preferences. However, they all voted according to the preferences they received. Suppose now that the assistants are able to struck deals among each others before the final vote takes place. Barbara's assistant could ask Martin's one to vote for a restaurant in the center instead of the suburbs, as he is indifferent about this issue. And Martin's assistant can in turn ask Ann's one to vote in favour of lunch over dinner, as she is indifferent on this issue. Thus, by a pre-vote negotiation the three agents are able to find a voting pattern that satisfies the preferences of the three owners.

The decision that the assistants have to take has three features, making the space of possible alternative plans a combinatorial one. Expressing preferences in such domains is the subject of Chapter 4: Example 1.1.4 (Expressive social choice). As in Example 1.1.2, Robert specifies a clear preference for a casual lunch in the city center. Ann instead has the same preference as in Example 1. 1.3, that is she is indifferent about lunch or dinner, but would like a restaurant in the center or a fancy one (or both). Barbara realises that if the restaurant is in the center, then she would prefer a casual one over a fancy one, however if the restaurant is in the suburbs then she would prefer a fancy one. Robert's preferences can be easily represented as a complete judgment on the three issues at stake, while Ann's preferences rather specify a set of possible answers to the three issues, which are logically correlated. Barbara's preferences are conditional, and can be represented by means of suitably defined logical statements. Once the problem of representation of preferences is solved, the automated assistants still face the issue of how to properly aggregate such compactly represented preferences into a choice for a meal, with the usual limitations in space and time resources.

To sum up, autonomous agents involved in a collective decision can face situations which require adequate representations for the influence among the voters, for their strategic abilities, and for the expressive variety of their preferences. This document delve into each of these questions, providing models and algorithms for interactive, strategic, and expressive social choice.

the architecture of collective decisions

A different angle to present the content of this thesis is to consider the improvements that each of the three main chapters bring to the overall architecture of a collective choice problem. Each individual agent in a multiagent system is typically characterised by three features: a set of actions at his disposal, a (typically partial) knowledge of its environment, and a preference or a goal on the possible configurations of the multiagent system. In the simplest model of a collective decision, that of an election over alternatives, agents can express their vote on ballots, such as communicating their most preferred candidate or providing an ordering of the preferred three candidates. They have full or partial knowledge about the preferences or the votes of other voters. And they have preferences on the outcome of the electionoutcome that is decided by applying a voting rule on the ballots of all the voters. Figure 1 provides a visual explanation. When studying the interactions among voters defined by their mutual influence in Chapter 2, we will work on the knowledge that each agent has of other agents, specifically the ones influencing it, and its effect on the resulting actions. An agent can thus be influenced by updating its preferences or its choice of action. In Chapter 3 we will focus on the action that the agents take depending on their knowledge of what actions the other agents will play, in this way taking a full game-theoretic perspective. In doing so, we will provide the agents with computational tools to analyse the strategic structure of collective decisions. The focus of Chapter 4 is the set of actions at the agents' disposal, i.e., the voting ballots, which are a crucial aspect of a collective decision when the set of alternatives has a combinatorial structure.

structure of the document

This thesis presents the research I conducted after obtaining my PhD. It is organised in three chapters, each presenting a coherent set of results around three themes: modelling interactive, strategic, and expressive social choice.

Chapter 2 augments the classical model of social choice with a network relating the voters, which can represent the trust among the agents or a communication network. A large part of the chapter is dedicated to the study of models of opinion diffusion that are adapted to social choice situations, and to sketch a first model of strategic opinion diffusion. The last part of the chapter takes a mechanism design perspective, presenting two studies of algorithmic design. The first is a generalisation of liquid democracy accounting for multiagent ranked delegations, and the second is a study of bribery of two systems for collective rating.

Chapter 3 starts with the notion of a voting game, and thus takes the strategic aspects of collective decisions into account. The chapter begins with the introduction of a novel class of games called Gibbard-Satterthwaite games, which focuses on players with restricted sets of actions. Then, in a situation of binary vote on multiple issues, we show how the use of negotiations preceding the vote can be used as selectors of Nash equilibria. The chapter is then concluded by the presentation of a number of studies around the problem of iterative voting, with techniques from multiagent simulations, reinforcement learning, and experimental economics.

Chapter 4 focuses on the expressivity of the voters, more specifically in combinatorial vote, when the set of alternatives is of exponential size. Several approaches are presented, building on a motivating example of group activity selection. We start from a comparison of judgment aggregation languages from the point of view of succinctness, moving on to presenting a full-fledged analysis of voting based on propositional goals. Increasing the expressive power of individual ballots, we then consider the aggregation of conditional preferences that are probabilistic and incomplete, and, finally, present a voting rule for collective sentiment analysis in the presence of both polarities and comparative statements.

The introduction of each chapter presents the research problem, and details all collaborations concerning the results presented. Related work is surveyed to put my research in context. Each following Notes in the margin highlight specific results or features section is complemented with examples aimed at quickly grasping the significance of the results and the interest of the problem considered. The last section of each chapter details open problems and future research directions.

This chapter presents research on enriching the structure of a social choice problem by taking into consideration a network relating the decision-makers. The importance of network phenomena in collective decisions is difficult to underestimate. The effects of social media on real elections are under constant scrutiny, and social network analysis provides by now standard tools for political campaigners. Moreover, autonomous agents are already quite present on social media, and interact with decision-makers by filtering our access to information or directly as content producers. From the perspective of mechanism design as well, social networks can play an important role in the creation of novel collective-decision methods.

Social network analysis [START_REF] Easley | Networks, Crowds, and Markets: Reasoning About a Highly Connected World[END_REF][START_REF] Jackson | Social and Economic Networks[END_REF] provides plenty of tools for the social choice theorist who wants to embark on such an enterprise. These tools, as we shall see, need however to be adapted to fit the (often combinatorial) structure of social choice problems, and important modelling considerations are required to clarify the role of networks in different scenarios. A network among voters can be seen as a compact representation of the mutual influence or trust among the decision-makers, but also as a map of the information channels that are available to them.

This chapter focuses on two social choice problems: voting, both on binary issues and on a set of alternative candidates, and collective rating of service-providers. Most of the techniques we use come from theoretical computer science and game-theory, complemented by initial results with multiagent simulations. The first two sections are concerned with the effect that social networks can have on a collective decision. They deal with two different aspects of this problem:

Outline of the chapter social influence (Section 2.1), and non-uniform access to information (Section 2.2). The two sections that follow them take the perspective of mechanism design to exploit the presence of a social network and obtain decision mechanisms-delegative voting rules in Section 2.3 and a rating system in Section Each agent has a private and partial knowledge of the situation, and a private goal or preference. Agents exert their influence by expressing opinions, entering a process of opinion diffusion which results in a final vote.

Opinion profile agents' expressions

Opinion profile

Final Vote

agents' expressions

Opinion profile

University of Amsterdam, and Paolo Turrini from Warwick University. I wrote a survey in 2017 on social choice and social networks [START_REF] Grandi | Social Choice and Social Networks[END_REF],

Survey on social choice and social networks which introduces the reader to various approaches on this problem.

Research is however moving very fast on this topic, and many further publications appeared since then on this topic. Part of the work presented in this chapter is being conducted in the ANR-18-CE23-0009-01 SCONE project on social choice and social networks. 1

opinion diffusion as aggregation

In this section we focus on the role that social influence can play when preceding a vote. A high-level description of this process is depicted in Figure 2. This section presents results on adapting and studying models of opinion diffusion for voting situations, in which the expressed opinion of the agents take the form of binary views over interconnected issues (Section 2.1.3) and linear orders (Section 2.1.4). Results studying the effects of the presented diffusion models on voting rules are summarised in Section 2.1.5, and a full-fledged epistemic model of strategic diffusion is described in Section 2.1.6.

Related work on opinion diffusion

Accurate introductions to the field of social network analysis can be found in the classical books of Jackson [START_REF] Jackson | Social and Economic Networks[END_REF] and Easley and Kleinberg [START_REF] Easley | Networks, Crowds, and Markets: Reasoning About a Highly Connected World[END_REF]. How information, diseases, or opinions diffuse on a given network is a classical problem studied in this field. Models of opinion diffusion can be classified depending on the mathematical representation that is chosen for the agents' opinions. Continuous models, in which nodes' opinions have values x ∈ [0, 1] or equivalent, are widely studied. Perhaps the most well-known example is the DeGroot's model [START_REF] Morris | Reaching a Consensus[END_REF] (also known as the Lehrer-Wagner model [START_REF] Lehrer | Rational Consensus in Science and Society[END_REF]) in which agents update their opinions depending on the weight they attach to their neighbours opinions, defining a linear model based on iterated weighted sums. A wide literature developed around a gen-Most research is on models with continuous opinions eralisation of this model known as the Friedkin and Johnsen model (see, e.g., [START_REF] Friedkin | Social Influence Network Theory: A Sociological Examination of Small Group Dynamics[END_REF]), including recent developments which incorporate constraints on the multiple continuous beliefs held by the agents [START_REF] Friedkin | Network Science on Belief System Dynamics under Logical Constraints[END_REF]. A large number of results in this literature characterise networks and model parameters that guarantee some forms of consensus at the end of the opinion diffusion process. Discrete models, instead, typ-

Most results focus on finding consensus

ically assume that agents can only have binary (two-state) opinions such as yes-no, for-against, or a list of finite opinions, such as colours. Granovetter [START_REF] Granovetter | Threshold models of collective behavior[END_REF] and Schelling [START_REF] Schelling | Micromotives and macrobehavior[END_REF] were the first in proposing and studying threshold models, with each agent in the population being assigned a numerical value that indicates the proportion of neighbours who must have a certain opinion before the agent adopts it. A

The celebrated segregation game is a threshold model (see, e.g., ncase.me/polygons/) generalisation of these models that is widely studied in computer science are linear threshold models [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Kempe | Influential Nodes in a Diffusion Model for Social Networks[END_REF], which also include weights on agents' links, to model the strength of the influence relation. Finally, diffusion processes known as voter models study the probabilistic propagation of opinions, deciding at each time step if an individual takes the opinion of a random neighbour [START_REF] Clifford | A model for spatial conflict[END_REF][START_REF] Holley | Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model[END_REF], or, more closely to threshold models, the most approved opinion in her neighbourhood [START_REF] Nandini Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF].

More recently, a stream of papers in artificial intelligence proposed generalisations of discrete opinion diffusion models with more complex representations of opinions. What is common among these models is the view that each agent, in updating her opinion, aggregates the opinions of her neighbours. Schwind et al. [START_REF] Schwind | Is promoting beliefs useful to make them accepted in networks of agents?[END_REF][START_REF] Schwind | Belief Revision Games[END_REF] model opin-Opinion diffusion as aggregation ions as knowledge bases, i.e., sets of propositional formulas, importing aggregators from the literature on belief merging. The work I will summarise in Section 2.1.4 studies how preferences represented as linear orders diffuse following majoritarian opinions in one agent's neighbourhood [START_REF] Brill | Pairwise Diffusion of Preference Rankings in Social Networks[END_REF]. Finally, previous work which will be discussed in Section 2.1.3, as well the work of Christoff and Grossi [START_REF] Christoff | Binary Aggregation with Delegable proxy: An Analysis of Liquid Democracy[END_REF][START_REF] Christoff | Stability in Binary Opinion Diffusion[END_REF], focused on possibly interconnected binary views, importing aggrega-tors from the field of judgment aggregation. Related to this last line of research is the more general treatment of opinion transformation proposed by List [START_REF] List | Group Communication and the Transformation of Judgments: An Impossibility Result[END_REF], which however did not explicitly consider a network relating the individuals. Models of binary opinion diffusion are closely related to the literature on boolean networks (see, e.g. [START_REF] Cheng | Stability and stabilization of Boolean networks[END_REF][START_REF] Kaufmann | Homeostasis and Differentiation in Random Genetic Control Networks[END_REF]), which stems from the modelling of biological regulatory networks [START_REF] Shmulevich | Probabilistic Boolean networks: a rule-based uncertainty model for gene regulatory networks[END_REF].

My approach at opinion diffusion models was widely influenced by the work of Grabisch and Rusinowska on power indexes and influence functions [START_REF] Grabisch | A model of influence in a social network[END_REF][START_REF] Grabisch | A model of influence with an ordered set of possible actions[END_REF][START_REF] Grabisch | Different Approaches to Influence Based on Social Networks and Simple Games[END_REF][START_REF] Grabisch | A model of influence with a continuum of actions[END_REF]. Their work can in turn can be traced back Power idexes on social networks at a formal model of influencing power introduced by Isbell [START_REF] Isbell | A class of simple games[END_REF] and developed more recently by Hoede and Bakker [START_REF] Hoede | A theory of decisional power[END_REF]. Their first work focused on binary decisions, with an influence function determining the dynamics from a profile of individual opinions over n agents x ∈ {0, 1} n to the next [START_REF] Grabisch | A model of influence in a social network[END_REF][START_REF] Grabisch | Different Approaches to Influence Based on Social Networks and Simple Games[END_REF]. The key concept is the followers function, which specifies for each coalition of individuals the set of individuals that would follow their (unanimous) decision. The model was generalised to non-binary settings, with an ordered set of actions or a continuum of actions available to individuals [START_REF] Grabisch | A model of influence with an ordered set of possible actions[END_REF][START_REF] Grabisch | A model of influence with a continuum of actions[END_REF].

Basic definitions

The basic bricks of the model are a finite non-empty set of agents N = {1, . . . , n} and a directed graph E ⊆ N × N which is taken to represent a trust or influence network among the agents. While most social networks are often assumed to be undirected (e.g., modelling friendship) we take here a more general perspective, to account for situations in which influence is not necessarily mutual. We denote the set of influencers of an agent i in network E with Inf (i) = {j | (j, i) ∈ E}, reading (j, i) ∈ E as "j influences i". If E is reflexive, then for all i ∈ N we have that i ∈ Inf (i), which is a realistic assumption in most applications of opinion diffusion.

We assume that each agent i ∈ N has an individual opinion, which we denote B i for agent i, which in further sections will take different forms: a binary opinion, a ranking over a number of alternatives, a model of a propositional formula. We call opinion profile, denoted with B = (B 1 , . . . , B n ), the ordered list of individual opinions of the agents.

The model of social influence proposed here is based on aggregation: each individual i uses an aggregation function to update her opinion from those received by her influencers (and her own one). Formally, if X is the space of all possible individual opinions, we con-

B t+1 i =    F i (B t i , B t Inf (i) ) if i ∈ turn(t) B t i otherwise.
Where B t Inf (i) denotes the restriction of profile B to the agents in Inf (i). If turn(t) = N for all t we name the process synchronous. When the turn function instead selects one single individual at each turn the process is called asynchronous. 2 When individual opinions are complex, e.g., multiple binary issues or preferences, the turn function needs to be coupled with a further scheduler identifying which individual updates on which part of the opinion.

The first problem we study is the termination of the iterative process. Two notions can be defined. If we call a transition from a pro-Universal and asymptotic termination file B to a second profile B effective if B = B, then we say that an opinion diffusion process terminates universally if there exists no infinite sequence of effective transitions starting at any initial profile. Instead, we say that an opinion diffusion process terminates asymptotically if from any initial profile there exists a sequence of transitions that reaches a stable profile, where a profile B is said to be stable if F i (B) = B i for all i ∈ N. For an asynchronous model the latter notion corresponds to requiring the model to be an absorbing Markov chain.

While previous research mostly focused on identifying initial conditions to reach a consensual opinion among the agents, our perspective of studying social influence before a vote leads us to consider a wider set of situations. Let a termination profile for initial profile B 0 be We do not only focus on consensus any stable profile reachable from B 0 . We can then investigate when a process converges to a unique profile, if all termination profiles reachable from an initial one coincide. For the specific case of preferences over alternatives, we can investigate when all termination profiles are aligned, e.g., single-peaked, or if they allow for a Condorcet winner more often than the initial one.

Propositional opinion diffusion

In this section we assume that individual opinions are binary views over a set of binary issues: B i ∈ {0, 1} I where I is a finite non-empty set of issues, with 1 standing for a "yes" vote and 0 for a "no" vote.

Issues can be correlated (see Example 2.1.2), in which case we will assume that the set of feasible individual opinions is restricted by an integrity constraint. Formally, if IC is compactly represented as a propositional formula over variables I then we assume that B i | = IC for all i. Consider the following example: 3 Example 2.1.1. Consider the following influence network among three agents, Ann, Bob and Jesse: Bob Ann Jesse Suppose the three agents need to decide whether to approve the building of a swimming pool (first issue) and a tennis court (second issue) in the residence where they live. The following table presents their initial opinions and the evolution of the synchronous opinion diffusion process assuming that each agent uses the majority rule to update her opinion:

Initial opinions Profile B 1 Profile B 2 B 0 A = (0, 1) B 1 A = (0, 1) B 2 A = (0, 1) B 0 B = (0, 0) B 1 B = (0, 0) B 2 B = (0, 1) B 0 J = (1, 0) B 1 J = (0, 1) B 2 J = (0, 1)
The are two perspectives we can take when facing possibly correlated multiple issues. The first option is to use aggregation functions

Study termination

of IC-consistent aggregators that always return IC-consistent opinions (or equivalently assume that issues are independent, which corresponds to IC = ). Under these assumptions we can show the following:

Theorem 2.1.1. [START_REF] Grandi | Propositional Opinion Diffusion[END_REF] If F i satisfies ballot-monotonicity for each i ∈ N, then propositional opinion diffusion universally terminates on the class of directed acyclic graphs with loops after at most diam(E) + 1 number of steps.

The assumption of ballot-monotonicity (which is tight) requires that for each profile B = (B 1 , . . . , B m ), if F(B) = B * then for any 1 i m we have that F(B -i , B * ) = B * . That is, reinforcing a given opinion in the input does not change the result of the aggregation. diam(E) is the length of the longest path in E.

We obtained more results in this line for specific aggregators such as the majority rule or the unanimity rule, also assuming independent issues, in joint work with Emiliano Lorini and Laurent Perrussel [START_REF] Grandi | Propositional Opinion Diffusion[END_REF].

There is considerable related work on opinion diffusion on a single binary issue. Most notably, we mention the classical work of Goles and Olivos [START_REF] Goles | Periodic behaviour of generalized threshold functions[END_REF] on threshold rules, and the recent work of Christoff and Grossi [START_REF] Christoff | Stability in Binary Opinion Diffusion[END_REF] on finding sufficient conditions for universal termination of arbitrary aggregation procedures, as well as the work of Bredereck and Elkind [START_REF] Bredereck | Manipulating Opinion Diffusion in Social Networks[END_REF] focusing on asynchronous processes for the majority rule.

The second approach to deal with logical dependencies between the issues consists in using simpler aggregation functions, such as the issue-by-issue majority rule, with influence percolating on the network one issue at the time. In the presence of integrity constraints Propositionwise diffusion this approach is not straightforward to apply, as exemplified in the following situation:

Example 2.1.2. Four individuals are part of a collective decision-making process on whether to build a skyscraper (S), a hospital (H), or a new road (R). Law says that if S and H are built then R also should be built (corresponding to integrity constraint (S ∧ H) → R. The four agents are part of the following influence network:

B 1 = 010 B 2 = 100 B 3 = 111 B 4 = 000
Suppose that agent 4, which is influenced by the other three, asks her influencers their opinion on the 3 issues at the same time. Then she would face an inconsistent issue-by-issue majority result of 110, and it would be unclear how to update her opinion. However, agent 4 can also ask questions on only two issues at the time, in which case the result can be 100 or 001 depending on the order of questions. The same result can be reached by asking two 1-issue questions in sequence. Generalising on the previous example, it seems that by limiting the size of queries that agents can ask we can circumvent the problem of updating on an inconsistent aggregated view. However, when the aggregated opinion of the influencers is consistent, we would still like to be able to reach it by asking proposition-wise queries. Borrowing concepts from the theory of boolean functions, we are able to prove the following result: Theorem 2.1.2 ([11]). Let IC be an integrity constraint, and let B be reachable from an IC-consistent initial profile B by asking queries on all issues at the same time. Then, B is reachable from B by asking queries on k issues at the time iff IC is k-geodetic.

The notion of k-geodeticness is inspired by the work of Ekin, Hammer, and Kogan [START_REF] Ekin | On Connected Boolean Functions[END_REF]. Intuitively, a constraint is 1-geodetic (or geodetic tout court) if any two of its models are connected by a shortest path on the boolean cube. To give an example, a simple pXORq is not geodetic, since any shortest path between the two models 10 and 01 passes through a non-model (00 or 11). On a more positive note, we can

Transitivity or budget constraints work well with propositionwise diffusion

show that constraints used in decision-theoretic applications, such as transitivity constraints or budget constraints, are geodetic. In general, it is co-NP-complete to test if a given constraint is k-geodetic.

Further investigations of propositionwise opinion diffusion processes under integrity constraints can be found in joint work with Sirin Botan and Laurent Perrussel [START_REF] Botan | Multi-Issue Opinion Diffusion under Constraints[END_REF]. To the best of our knowledge, the only related work investigating constraints in discrete opinion diffusion is the work of Christoff and Grossi [START_REF] Christoff | Binary Aggregation with Delegable proxy: An Analysis of Liquid Democracy[END_REF] on delegation graphs, where each node has at most one influencer.

Diffusion of preferences

In voting applications agents are typically assumed to express a preference over a set A = {a, b, c . . . } of alternative candidates, with the most common assumption being a linear order (aka strict ranking). In this setting, the idea of issue-wise diffusion can be applied to pairs of alternatives that are adjacent in an individual preference order, as explained in the following example:

a 1 b 1 c c 2 a 2 b b 3 c 3 a b 4 a 4 c
The preferences of agents 1, 2, and 3 form a Condorcet cycle, i.e., the majority relation of their preferences is cyclic. In one possible asynchronous sequence of updates, agent 4 updates on pair ab, moving to preference a 4 b 4 c. After that, no further updates are possible: even though agent 4 disagrees with its influencers on pair ac, this pair cannot be swapped since it is no longer adjacent in 4 . The agents reached a stable state, and the pairwise diffusion process terminated. If we instead consider synchronous updates, with all agents updating at the same time, possibly on different pairs of alternatives, we observe that if agents 1 and 4 update repeatedly on pair ab we obtain an infinite update sequence and the diffusion process does not terminate. Agents 2 and 3 are sources, i.e., they have no influencer, and thus never update their preferences.

Recall that asymptotic termination requires that in each opinion profile (denoted as for linear orders over candidates) we can construct a path of updates that leads to a termination profile. Whilst the example above shows that asymptotic termination with synchronous pairwise majority diffusion is not always possible, we show the following result for asynchronous processes: Theorem 2.1.3 ([21]). Let 0 denote the initial preference profile. For |A| = 2, asynchronous pairwise majority diffusion asymptotically terminates on any graph E. For |A| 3, asynchronous pairwise majority diffusion asymptotically terminates on E when ( 0 , E) satisfies linear local majority.

The linear local majority assumes that all local majorities calculated on sets of influencers in any profile that is reachable by pairwise diffusion from 0 on the network E are transitive. Basically, it requires that no Condorcet cycle is encountered in the diffusion process. It is

Relaxing the linear local majority assumption is an open problem

a rather strong assumption, but observe that the termination result is shown for any graph E. We conjecture that Theorem 2.1.3 still holds without this restrictive assumption, but the proof is still an open problem.

We also initiated a qualitative study of the termination profiles. We obtained only limited results, the following one being of particular interest: Proposition 2.1.1. Let E be a DAG and let 0 be a profile such that ( 0 , E) satisfies the no-tie property (i.e., the diffusion process never leads to ties). If Opinion diffusion propagates the alignment of preferences 0 sources is aligned (single-peaked, single-crossing, Sen value-restriction), then all profiles at termination are also aligned.

The proposition shows that pairwise diffusion propagates the preferential alignment of the sources of a directed acyclic graph to all other agents. Further results in this line can be found in our joint paper with Markus Brill, Edith Elkind, and Ulle Endriss [START_REF] Brill | Pairwise Diffusion of Preference Rankings in Social Networks[END_REF].

Turn-taking and opinion diffusion in voting

Once models of opinion diffusion are adapted to voting-like situations, the next question to tackle is whether opinion diffusion is beneficial to the voting process. Ideally, an election organiser would like to know if promoting discussion (hence social influence) among voters is beneficial to the election itself, or if uninfluenced voters lead to better collective decision processes. The Master thesis of Claire Pillet [START_REF] Pillet | The influence of turn-taking on the diffusion of opinions[END_REF] which I recently supervised goes in this direction, using the tool of multi-agent simulations.

In particular, her work aims at investigating the role of the turntaking function that decides the order of the agents' expressions. For the simplest case of one binary decision and majoritarian opinion diffusion, the results mostly show the superiority of asynchronous turn-taking in reaching a stable state, and highlight the role of the underlying influence graph in determining the number of switches in the result of a majority vote (we used Erdös-Rény and Barabàsi-Albert graphs, with varying initial parameters).

More interesting results are obtained for pairwise preference diffusion, when agents have preferences over multiple candidates. Assessing the quality of a preference profile is not an easy task, and a basic measure is the existence of a Condorcet winner. We then investigated whether pairwise majoritarian diffusion can make a Condorcet winner emerge in profiles that do not admit one. Initial results with

Preference diffusion

increases the number of profiles with a Condorcet winner 31 voters and 5 alternatives show a 10-15% increase in the number of profiles that have a Condorcet winner after the opinion diffusion process with respect to the initial profiles generated with impartial culture (uniform distribution). These results are irrespective of the turn function and the graph structure used. Moreover, the profiles obtained at termination of opinion diffusion have the further property that the Plurality rule elects the Condorcet winner more often than in uniformly drawn ones, while this property is not verified for the Borda rule. These results suggest that pairwise majoritarian diffusion has a beneficial effect on Plurality elections.

Strategic opinion diffusion

From a cognitive perspective, the agents in all models described so far are extremely simple: they have no knowledge of their environment, no goal, nor strategy to attain it (recall Figure 2). In collaboration with Emiliano Lorini, Arianna Novaro, and Laurent Perrussel [START_REF] Grandi | Strategic Disclosure of Opinions on a Social Network[END_REF][START_REF] Grandi | Games of Influence[END_REF] we developed two models of strategic opinion diffusion based on a possible-world semantic. Our models are best exemplified by yet one more example:

Example 2.1.4. The are four agents: Jesse (the mother), Ann, Bob, and Cathy (the children). The family has to decide whether to go to the cinema or to make an excursion to the countryside. Jesse asks the kids what they would like to do. If they unanimously agree on the same option, then this option will be chosen. Otherwise, in case an agreement is not reached, the default option will be to go to the cinema. Each kid can decide either to abstain or to participate in the vote by declaring her/his preference. Members of the family influence each other following the influence network depicted below:

Ann Bob Cathy

Jesse

Our model aims at representing the strategic action of exerting one's influence on another agent, or abstaining from doing so. We first assume common knowledge of the private opinions. Assume in the situation of Example 2.1.4 that it is common knowledge in the family that Jesse and Bob tacitly prefer the cinema, while Ann and Cathy tacitly prefer the excursion. Nonetheless, according to the rule of the game, if a kid does not explicitly says what she/he prefers, her/his preference will not count. In this situation, Ann should ex-Modelling the strategic action of exerting one's influence plicitly declare her preference to be sure that her goal of making an excursion will be achieved. Otherwise, Jesse's preference of going to the cinema will possibly prevail. In game-theoretic terms, Ann has a winning strategy to achieve her goal of making an excursion.

We then focus on the epistemic structure of opinion diffusion, dropping the assumption that the individual preferences of the agents are common knowledge among them. Therefore, if an agent does not reveal her opinions, the others will be uncertain about them. If we con-

Full-fledged epistemic model of opinion diffusion on multiple issues

sider again the situation in Example 2.1.4, Ann would be uncertain about Cathy's preference before Cathy has publicly revealed it. Consequently, Ann does not know whether, by choosing to explicitly declare her preference, an unanimous agreement to make an excursion will necessarily be reached. While Ann does not have a uniform strategy (i.e., one that would achieve her goal in any configuration), she knows that the choice of explicitly declaring her opinions (weakly) dominates the choice of abstaining.

We assume that agents' goals are expressed compactly using a fragment of linear temporal logic (LTL) [START_REF] Sistla | The complexity of propositional linear temporal logics[END_REF], which allows them to express their preferences over future opinion configurations, and to devise sequences of strategic actions to attain them. While we only obtain limited results on characterising such strategies in specific graph structures, we show that the problem of recognising if a given strategy profile is a (subjective) Nash equilibrium can be solved in polynomial space (PSPACE)-to be interpreted as a positive result since satisfaction of an LTL formula is already PSPACE-complete [START_REF] Sistla | The complexity of propositional linear temporal logics[END_REF]. All other tasks we consider, such as the existence and uniqueness of a Nash equilibria, are significantly harder and we give upper bounds above exponential time.

social networks as information filters

Let us consider once more an election with networked voters: a set of agents N, connected on a network E ⊆ N × N, having to decide on a set of alternatives A = {a, b, c . . . }. This time, however, the network is not meant to represent mutual trust or social influence between the agents, but maps the agents' exchanges of information. Think of an idealised Facebook wall (based on an undirected graph) or a Twitter page (based on a directed graph). The information access is there-fore personalised for each voter. This is clearly an idealised situation, as typically voters do also have access to a global information poll, but leaving this aside allows us to focus on the consequences of the asymmetric access to information induced by the network.

In a recent paper which gained popular attention, 4 Lerman, Yan, and Wu [START_REF] Lerman | The "majority illusion" in social networks[END_REF] defined and studied a network phenomenon whom they named the majority illusion: the existence of social networks in

The majority illusion in social networks which the majority of the nodes belong to a given type, but for each of those nodes the majority of their neighbours belong to a different type, therefore creating the wrong perception (the illusion), that the majority type is different from the actual one. In ongoing work with Grzegorz Lisowski and Paolo Turrini we adapt the majority illusion to a voting situation, starting from the following motivating example:

Example 2.2.1. A group of 8 voters participate in a three-candidate election decided by a plurality vote (also known as first-past-the-post). Call the candidates a, b, c, and assume that ties are broken following the alphabetic order. The 8 voters are of three kinds, depicted as circles, diamonds, and stars. The figure below shows the undirected network of information exchange among the voters:

The circle voters have a preference over candidates of a > b > c, denoting that they prefer candidate a to candidate b, and candidate b to candidate c.

The star voters have a preference of c > a > b, and the diamond voters b > a > c. If a vote is taken, the plurality winner winner would be candidate a with 4 votes in favour, followed by c and b with 2 votes. Observe that candidate a is also a Condorcet winner, and that no voter would have incentive to manipulate if the sincere preferences of voters were common knowledge among them.

Sincere vote

a 4 votes b 2 votes c 2 votes
We assume that voters access information on the election solely via the undirected network depicted in the figure above, and that their strategic behaviour will respond accordingly. Consider the circle agents voting for candidate a: each see 2 other voters supporting c, and 1 voting for b. If they voted for a (sincere vote) then c would win, which is their worst option. Circle voters then have an incentive to vote for b and have their second best alternative winning (by tie-breaking). As for the star and diamond voters, they expect Asymmetric access to information leads to a worse election outcome candidate a to be the winning candidate with a margin of 2, and thus do not have incentives to manipulate since a is their second-best candidate. The new result of the election, with voters responding to the information they received, would thus be b winning with 6 votes, no vote for candidate a, and 2 for candidate c.

Strategic response to network

a 0 votes b 6 votes c 2 votes
In our ongoing collaboration we conduct a computational study of illusion phenomena like the one described in the previous example. We generalise the majority illusion of Lerman, Yan, and Wu [START_REF] Lerman | The "majority illusion" in social networks[END_REF] to allow for more than two types, and show that recognising those networks for which a labeling of nodes would constitute an illusion is an NP-complete problem. We then turn to design polynomial algorithms for repairing a network to ensure that no illusion can occur, mostly by increasing the connectivity under a budget constraint. In doing so we take a similar approcha to a recent stream of papers by Auletta, Ferraioli, and Greco [START_REF] Auletta | On the complexity of reasoning about opinion diffusion under majority dynamics[END_REF] and Castiglioni, Ferraioli, and Gatti [START_REF] Castiglioni | Election Control in Social Networks via Edge Addition or Removal[END_REF], in which the authors identify networks and initial distributions of opinions (binary case) where a minority vote can become a majority vote by updates due to social influence. We however focus on a non-binary case, and consider strategic agents that respond to their neighbours' opinions rather than conform to it.

smart voting

In contrast with the two previous sections, in which we proposed models of social influence and other network phenomena and investigated their effects on collective decision-making, we take in this section a mechanism design perspective. In particular, we are interested in how can social influence be exploited (and, first, elicited) to design novel voting procedures. Building on work on liquid democracy and proxy voting, in our collaboration with Rachael Colley and Arianna Novaro [START_REF] Colley | Smart Voting[END_REF][START_REF] Colley | Smart Voting[END_REF] we designed a delegative voting method that allows voters to express rankings and complex delegations.

Let us first provide some context. Liquid democracy sits in the mid-

A number of recent papers in AI investigate liquid democracy dle ground between a purely representative and a purely direct democratic system, allowing for transitive delegations among the voters.

Liquid democracy has been the subject of numerous recent investigations in AI, ranging from analysing its truth-tracking power [START_REF] Bloembergen | On Rational Delegations in Liquid Democracy[END_REF][START_REF] Cohensius | Proxy Voting for Better Outcomes[END_REF][START_REF] Kahng | Liquid democracy: An algorithmic perspective[END_REF] to its adaptation to multiple issues and alternatives [START_REF] Brill | Pairwise Liquid Democracy[END_REF][START_REF] Christoff | Binary Voting with Delegable Proxy: An Analysis of Liquid Democracy[END_REF]. Our work takes inspiration from the work of Christoff and Grossi [START_REF] Christoff | Binary Voting with Delegable Proxy: An Analysis of Liquid Democracy[END_REF], which were the first authors to make a connection between computing the result of a liquid democracy instance and models of opinion diffusion such as those described in Section 2.1. Also, in line with recent work of Kotsialou and Riley [START_REF] Kotsialou | Incentivising Participation in Liquid Democracy with Breadth-First Delegation[END_REF] and Escoffier, Gilbert, and Pass-Lanneau [START_REF] Escoffier | The Convergence of Iterative Delegations in Liquid Democracy in a Social Network[END_REF][START_REF] Escoffier | Iterative Delegations in Liquid Democracy with Restricted Preferences[END_REF], we allow voters to express a ranking of possible delegations, to adress potential delegation cycles. While most implementations of liquid democracy introduce a platform for the elicitation of voters' delegations, we aim at a decentralised voting system in which voters' ballots and delegations can remain private. Our first novelty is the definition of a general language for voters' ballots to express a direct vote, or a delegation to a single other agent, or a combination of the votes of multiple other agents. Second, to tackle the issue of delegation cycles we allow voters to express a number of prioritized delegations, with a final backup vote with the lowest priority. An example of what we call a smart ballot profile can be seen on the following figure: Our "smart voting" system allows for multiagent and ranked delegations and ranked delegation: she wants her vote to coincide with the majority of B, C, and D's votes, and in case this leads to a delegation cycle (i.e. such majority cannot be computed) she gives a single-agent delegation to B, denoted by a dashed arrow. Voter B delegates to D, expressing a single-agent delegation. Voter D casts a direct vote against, while C votes in favour. Voters A and B abstain (*) as their final backup option.

Formally, we start in full generality by assuming that a set of N voters needs to decide over I issues, with each issue i ∈ I having values in a domain D(i), including absention ( * ). Definition 2.3.1. A smart ballot of agent a for an issue i ∈ I is an ordering

((S 1 , F 1 ) > • • • > (S k , F k ) > x)
where k 0 and for 1 h k we have that S h ⊆ N is a set of agents, F h : D(i) S h → D(i) is a resolute aggregation function and x ∈ D(i) is an alternative.

We moreover assume that a smart ballot is valid, in the following sense: for each agent a and issue i ∈ I, for all 1 s = t k we have that (i) if S s ∩ S t = ∅ then F s is not equivalent to F t , and (ii) a / ∈ S s . A smart ballot can therefore be seen as a preference ordering over the agent's desired delegations, with a backup vote at the bottom of the ordering. The validity requirement ensures the non-redundancy of the preference ordering and forbids delegation loops.

Once smart ballots are collected-by a central authority or on a decentralised ledger-they need to be "unravelled" into a standard voting profile, one in which each voter expresses either a direct vote or an abstention, to finally apply a standard voting rule and compute the result of the election. Thus, our object of study is the following:

Smart ballot profiles are unravelled into profiles of direct votes to apply a voting rule Definition 2.3.2. An unravelling procedure U for issue i ∈ I and agents in N is any function associating with each valid smart ballot profile a profile of a direct votes:

U : (B 1i × • • • × B ni ) → D(i) n .
Note that while most of the related work in liquid democracy aims at assigning a final delegate (often named the "guru") to each voter, our unravelling procedures aim at assigning a direct voting ballot to each delegating agent.

We followed two principles in defining four greedy unravelling procedures: use the highest preference level of voters when breaking delegation cycles, and keep the unraveling procedure polynomial. We propose four procedures (details are omitted in the interest of space and can be found in our paper [START_REF] Colley | Smart Voting[END_REF]): basic update (U), update with direct vote priority (DU), update with random voter selection (RU), update with direct vote priority and random voter selection (DRU). We illustrate the first one in the following: Example 2.3.1. Consider one binary issue i with D(i) = {0, 1} and agents N = {A, . . . , E}. Their valid ballots in profile B i , stating their preferences for delegations or direct votes, are shown schematically in the table below:

1 st 2 nd 3 rd A ({B, C}, B ∧ C) ({D}, D) 1 B 1 - - C ({D}, D) 0 - D ({E}, E) 1 - E ({A}, A) ({B}, B) 0
We spell out here the unravelling Unravel(U) on B i , a procedure which looks for direct votes at the highest preference level possible, propagating them via the delegations specified by the agents at the same preference level:

• Starting at the first preference level, the direct vote of B is stored in a partial direct vote vector X = (∆, 1, ∆, ∆, ∆), with ∆ as a symbol denoting agents whose vote has not yet been computed.

• As there are no direct or computable votes at level 1 (no agent has a single-agent delegation to B), we move to the second level.

• The direct votes of C and D are thus added to X, and the vote of E is computed by copying the vote of B, obtaining a new X = (∆, 1, 0, 1, 1).

• The preference level is set back to 1.

• A's vote can now be computed from her first preference level, and vector X = (0, 1, 0, 1, 1) is thus returned as the unravelled profile of direct votes of the agents.

We show that the four greedy unravelling procedures we propose do terminate on any profile of valid ballots, and that there exists one such profile on which they output four different results. In order to prove that the computational complexity of running our unravelling procedures is polynomial, we need to fix a compact representation for the functions F s formalising multiagent delegations (an explicit representation would render the rules trivially polynomial). We therefore restrict our attention to binary-valued issues, and define Bool to be the set of smart ballot profiles where for each agent a and issue i we have that every F h ai in ballot B ai is a contingent propositional formula in DNF. We show the following:

Our four greedy unravellings terminate in polynomial time Proposition 2.3.1 ([35]). Unravel(#) Bool terminates in at most O(n 2 • max p (B) • 2 max ϕ (B)) time steps, for # ∈ {U, DU, RU, DRU}.
Where n is the number of agents, max p (B) is the highest preference level of any ballot in B and max ϕ (B) is the maximum length of any formula from an agent in B. The figure in Proposition 2.3.1 is thus polynomial in the input of the procedures.

To distinguish further our four unravelling procedures from each other, and to be able to compare them with similar procedures proposed in the literature, we initiated an axiomatic study of two properties of participation, in line with the work of Kotsialou and Riley [START_REF] Kotsialou | Incentivising Participation in Liquid Democracy with Breadth-First Delegation[END_REF]. All results we show are restricted to smart ballots with single-agent ranked delegations only. We show that all four unravelling procedure we proposed satisfy cast-participation, provided that the voting rule used on the unravelled profile is monotonic. That is, agents who vote directly have an incentive to do so, rather than to express any other ballot. We also show that this property ceases to hold if we allow for multi-agent delegations. On the other hand, none of our unravelling procedures satisfy the property of guru-participation, which focuses on the incentive that an agent has to receive and accept a delegation. Indirectly, this result shows that our unravelling procedures differ from the depth-first and breadth first procedures proposed by Kotsialou and Riley [START_REF] Kotsialou | Incentivising Participation in Liquid Democracy with Breadth-First Delegation[END_REF].

We also studied two unravelling procedures based on minimisation. We call a vector c a consistent certificate for a smart ballot profile B if each component corresponds to a delegation of the corresponding agent such that no delegation cycles is created. For instance, the certificate (1, 3, 1) implies that agent 1 uses her first delegation, agent 2 her third, and agent 3 her first (with delegation cycles to be checked reading profile B). The rule MinSum finds the consistent certificate that Unravelling by minimising the sum or the max of the delegation ranks minimises the sum of its components, corresponding to the rule that minimises the overall ranks of delegations used to unravel a profile. Similarly, the rule MinMax finds the consistent certificate that minimises the maximum component, corresponding to a classical fairness criteria of minimising the delegation rank of the worst-off voter. We show that there are profiles of multiagent delegations on which the six rules considered all have different results, but that they all coincide on standard liquid democracy ballots, i.e., ballots where each agent only expresses a single-agent delegation and a backup vote, with the exception of MinMax.

We then focused on determining the computational complexity of MinSum and MinMax, showing that they are both NP-complete, and identifying a class of smart ballots on which they are polynomial. Let BOOL be the class of all contingent propositional formulas in DNF, and let LIQUID be the language of ranked single-agent delegations. We call BoundedMinSum the decision problem associated with the search problem of finding a solutions to MinSum. The input of BoundedMinSum is a smart profile B, such that every ballot is restricted to BOOL, and a constant M ∈ N. The problem then asks if there is a consistent certificate c that unravels B such that i∈N c i M. An equivalent definition is given for BoundedMinMax. By reducing from the NP-complete problem Sat-DNF we obtain the following result.

Unravelling based on minimisation is NP-complete Theorem 2.3.1. BoundedMinSum and BoundedMinMax are both NPcomplete.

Investigating further the source of the computational complexity of these two rules, we were able to devise two polynomial algorithms for the computation of the corresponding unravelling, assuming that the agent ballots are in the LIQUID language.

Unravelling based on minimisation is polynomial on single-agent delegations Theorem 2.3.2. Finding an outcome of MinSum and MinMax can be done in polynomial time when individual ballots are restricted to LIQUID (i.e., single-agent ranked delegations).

The proof of Theorem 2.3.2 is obtained by a non-trivial adaptation of the Edmonds algorithm for minimum spanning arborescence trees for MinSum and a novel algorithm for MinSum.

Work on multiagent ranked delegations in voting is just at its beginning, and plenty of problems remain open. First, our initial study of participation should be complemented by more general results including multiagent delegations, as well as the analysis of further axiomatic properties that are typically studied in voting. Second, as the name "smart voting" suggests, its intended application is the development of collective decisions on a decentralised ledger, in line with recent initial work by Kotsialou et al. [START_REF] Kotsialou | Using Distributed Ledger Technology for Shareholder Rights Management[END_REF] and Riley et al. [START_REF] Riley | Deploying a Shareholder Rights Management System onto a Distributed Ledger[END_REF] on the design of electronic institutions. The report by Dhillon et al. [START_REF] Dhillon | Introduction to Voting and the Blockchain: some open questions for economists[END_REF] Smart voting should be implemented on a distributed ledger is a starting point in this direction, presenting a detailed analysis of smart contracts for electronic voting and liquid democracy.

personalised ratings

In this section we change the type of collective decision problem under scrutiny, moving from a classical voting situation to the realm of ratings and recommendations (see, e.g., [START_REF] Bobadilla | Recommender systems survey[END_REF]. This is the problem of a mechanism that has to provide to its users an assessment of the value of a given service-provider (we will use a restaurant as running example), based on the evaluations received by a subset of its users (which we will call customers). This problem is typically solved-and commercially exploited by well-known rating systems such as Tripadvisor-by taking the average of the evaluations received from the customers. In collaboration with Paolo Turrini and James Stewart [START_REF] Grandi | The Complexity of Bribery in Network-Based Rating Systems[END_REF][START_REF] Grandi | Personalised Rating[END_REF][START_REF] Grandi | A Network-Based Rating System and its Resistance to Bribery[END_REF] we compared this system with a personalised version, in which the rating provided to a user is the average of the evaluations of the user's neighbours in a given social network. More precisely, we evaluate the possibility of bribery by the restaurant, who can invest some of its utility to obtain fake ratings from the customers to improve its performance. We show that personalised ratings are

We study the bribery-proofness of two rating systems

superior to what we call objective ratings under two aspects. First, from an algorithmic point of view we are able to devise an algorithm for finding optimal bribing strategies for objective ratings that runs in polynomial time, while we show that the same problem is NPcomplete for the case of personalised ratings. Second, we show that the revenue of a bribing strategy for objective ratings increases with the number of users of the rating system, and is thus potentially unbounded, while we identify a bound in the personalised case that is dependent on the structure of the underlying social network.

We first need to introduce some notation and definitions to present our model. The first important assumption we make is that the rating viewed by a customer corresponds to the propensity of a customer to visit the restaurant. Assuming also for simplicity that each customer is worth

The rating corresponds to the probability of visiting the restaurant 1 utility point to the restaurant, we obtain the following formulas for the initial restaurant utilities under eval for O-rating (u 0 O ) and P-rating (u 0 P ):

u 0 O = |C|O-rating(eval) u 0 P = c∈C P-rating(c, eval)
If we now define a bribing strategy of a restaurant as a function σ : C → Val that specifies for each customer the amount of utility received from the restaurant, we can formulate our second important assumption as follows: the effect of a bribe of x ∈ Val on a customer c

The effect of a bribe is linear on the user evaluation is an increase of x on her evaluation (capped at 1). Formally, if eval σ represents the customers' evaluations after bribing strategy σ, then eval σ (c) = min{1, eval(c) + σ(c)}. Thus, we can define the utility of a bribing strategy σ for O-rating (u σ O ) and P-rating (u σ P ) as follows:

u σ O = |C|O-rating(eval σ ) - c∈C σ(c) u σ P = c∈C P-rating(c, eval σ ) - c∈C σ(c)
Finally, the revenue of a bribing strategy is the utility obtained from it minus the initial utility of the restaurant. Example 2.4.2 (P-rating). Consider now the effect of the three strategies on P-rating, starting from σ A . We have that P-rating σ A (c 1 ) = P-rating σ A (c 2 ) = 0.65 while P-rating σ A (c 3 ) = 0.3. Note already how bribing c 1 does not affect c 3 , whose P-rating stays the same. We thus have that u σ A P = 1.5 = u σ 0 P , which means r P (σ A ) = 0 and thus σ A is not a profitable strategy. Observe also that any strategy that behaves like σ A , bribing only customer c 1 , gives either a zero or a negative revenue. Conversely, σ B is different. In this case, we also have that P-rating σ B (c 1 ) = P-rating σ B (c 2 ) = 0.65. However, P-rating σ B (c 3 ) = 0.4, which means that u σ B P = 1.6 and thus r P (σ B ) = 0.1. So, the strategy σ B yields a positive revenue to the restaurant. Finally, σ C is such that P-rating σ C (c 1 ) = 0.6, P-rating σ C (c 2 ) = 0.43 and P-rating σ C (c 3 ) = 0.2, which means u σ C P = 1.13 and thus r P (σ B ) = -0.36. So, the strategy σ C yields a negative revenue to the restaurant.

Our comparison of the two rating systems under the perspective of bribery presents a number of results depending on the information available to the restaurant about the customer network and the presence of non-voters. Our main results are obtained assuming that not all customers have expressed their opinion, and that the network relating the customers is known to the restaurant.

Let an O-greedy strategy be any efficient strategy that redistributes all the initial resources u 0 O of the restaurant among the voters (without wasting utility). The following proposition shows that these are all and only the optimal bribing strategies for O-rating: Proposition 2.4.1 ([86]). Let V = C and σ a strategy. The following three statements are equivalent:

(i) σ is optimal for O-rating, (ii) σ is an O-greedy strategy, (iii) σ yields a payoff of |C| |V| -1 × min{u 0 O , c∈V (1 -eval(c))}.
Thus, a polynomial-time algorithm to find an optimal bribing strategy for O-rating is the following: starting from an evaluation vector A polynomial algorithm for finding optimal bribes under O-rating eval, distribute all available resources u 0 O to the voters, without exceeding the maximal evaluation of 1. By either exhausting the available budget or distributing it all, we are guaranteed the maximum gain by Proposition 2.4.1.

On the other hand, we show that for P-rating the same problem is computationally intractable. Let us first formalise bribery as a decision problem (NVKL stands for non-voters and known network):

BRIBE-NVKL

Instance:

Network (C, E), evaluation eval 0 , ρ ∈ Q Yes-Instance: An instance of BRIBE-NVKL s.t. there exists a strategy σ with r(σ) ρ

Optimal bribing under P-rating is computationally intractable

By providing a polynomial reduction from the known NP-complete problem of finding an independent set on 3-regular graphs, aka IS-REG(3) [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF], we are able to show the following:

Theorem 2.4.1 ([84]). BRIBE-NVKL is NP-complete.
We are also able to obtain simple quantitative results comparing the revenue that can be obtained under the two studied rating systems. We start from the following: The revenue under P-rating is bounded by the number of neighbours Proposition 2.4.2 shows that increasing the number of individuals that are not connected to an agent that is being bribed does not increase the upper bound on the revenue of the bribing strategy for P-rating. This is not true when we use O-rating: Proposition 2.4.3. Let σ be an efficient strategy bribing voters only. The revenue r O (σ) of σ is monotonically increasing in the number of non-voters.

Thus, under realistic assumptions on the network structure, such as a the presence of a very large proportion of non-voters and with customers having a small number of connections, these results show that bribing under O-rating is increasingly rewarding, while under P-rating this is no longer the case.

While our model is built on simplifying assumptions that may limit its relevance in practical applications-some of which can be easily generalised to, e.g., weighted networks, or weighted averages for the computation of ratings-our results show that taking into account the social network that relates the users of a rating system can be the key to devise mechanisms that are resistant to bribery.

conclusions and perspectives

This chapter presented research on the multiple consequences of taking into consideration the social network connecting the agents involved in a collective decision-making process. A big effort was directed towards adapting and designing diffusion models to fit voting situations, where the opinion of the agents can take a complex form (Section 2.1). An important problem that remained open is the conjecture that asynchronous issue-wise diffusion with arbitrary integrity constraints (or at least with the constraints induced by preference orders) asymptotically terminates on any network. I also presented initial studies on the effects of social network phenomena on collective decisions, be it social influence (Section 2.1.5) or information filtering (Section 2.2). Recent papers in the AI literature also perform similar studies [START_REF] Doucette | Inferring true voting outcomes in homophilic social networks[END_REF][START_REF] Tsang | The Echo Chamber: Strategic Voting and Homophily in Social Networks[END_REF], and there is ample ground for further investigations. A mechanism design perspective is however more likely to lead to impactful and lasting results. The study of delegative voting systems such as liquid democracy is a thriving topic in AI at the moment, and our proposed model of multiagent ranked delegations seems to have the right generality to encompass and analyse the various approaches proposed in the literature (Section 2.3). Also, while the study of personalised ratings presented in Section 2.4 is rather complete, the model should be tested under more realistic information assumptions (such as the restaurant knowing a distribution of the customers' evaluations) as well as with tools from the recommender systems literature.

Going further in research on social choice and social networks would require, among other things, better models of strategic reasoning in social influence. Most work focused on strategic actions by an external agent to control an election, such as adding or deleting edges of a network [START_REF] Castiglioni | Election Control in Social Networks via Edge Addition or Removal[END_REF], or manipulating individuals' opinions [START_REF] Faliszewski | Opinion Diffusion and Campaigning on Society Graphs[END_REF][START_REF] Wilder | Controlling Elections through Social Influence[END_REF] and opinion polls [START_REF] Baumeister | Manipulation of Opinion Polls to Influence Iterative Elections[END_REF]. What is missing however is a model for the strategic actions of an agent involved in a social influence process preceding an election. The model described in Section 2.1.6 is an initial attempt in this direction that simply allows agents to disclose or retain their otherwise sincere opinion. Recent work by Shepherd and Goldsmith [START_REF] Shepherd | A Reinforcement Learning Approach to Strategic Belief Revelation with Social Influence[END_REF] builds on the same assumptions as our model, but uses reinforcement learning for modelling the agents' strategic abilities. An interesting connection could also be drawn with voting games, and in particular with the results presented in Chapter 3, and Section 3.3 in particular: substituting the agents' monetary transfers with actions of social influence might lead to an alternative mechanism for equilibrium selection in aggregation games.

The theory of multiagent systems received modern foundations from economics, and more precisely game theory (see, e.g., [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF][START_REF] Wooldridge | An introduction to multiagent systems[END_REF]). An autonomous agent interacting with other peers is endowed with actions, has (typically partial) knowledge about its environment and the other agents' situations, and guide its choice of action towards the satisfaction of a goal, often represented as the maximisation of a utility function.

Voting is an interaction protocol to take collective decisions among multiple agents (typically at least 3), and as such it does not escape game-theoretical and strategic considerations. From early studies in economics to the computational complexity of manipulation, a wide number of papers have investigated the strategic behaviour of voters, of the election organiser, or of the candidates.

This chapter summarises my work on strategic aspects of voting, which focused on strategic actions by the voters (in contrast to strategic actions by the candidates, or by an election organiser). Section 3.1 introduces the strategic structure of voting and discusses some relevant related work. In Section 3.2 we introduce Gibbard-Satterthwaite games, in which multiple manipulators are faced with strategic actions in a one-shot game. Section 3.3 studies collective decisions on multiple binary issues, proposing pre-vote negotiations as a mean of equilibrium selection. Section 3.4 reports on several research directions on the framework of iterative voting, which studies agents dynamics on a voting game, presenting simulations on restricted dynamics, experiments with reinforcement learning agents, and behavioral experiments in the lab.

Most of the work presented in this chapter was initiated while I was a postdoc in Francesca Rossi's group at the University of Padova. The work on GS games was initiated during a visit of Arkadii Slinko from the University of Auckland in this university, and continued during his visits to the University of Toulouse. The interest of our research group on this topic was formalised by the organisation of the Workshop on Voting Games and Iterative Voting, 1 financed by the COST IC1205 action on computational social choice. The experimental work on iterative voting resulted from the collaborative project ANR-14-CE24-0007 Cocorico-Codec, which successfully brought together the French communities in computer science, political science, and economics, around various issues in contemporary social choice research. The use of reinforcement learning in iterative voting is a fascinating col-voting games and iterative voting laboration that aims at posing the first bricks towards the desing of AIs for voters' support. 23.1 context: the game-theoretic structure of voting One of the cornerstones of social choice theory, the theorem by Gibbard [START_REF] Gibbard | Manipulation of Voting Schemes: A General Result[END_REF] and Satterthwaite [START_REF] Satterthwaite | Strategy-proofness and Arrow's Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions[END_REF], states that there exists no onto, non-dictatorial, and strategy-proof voting rule for more than three candidates. Strategy-proofness of a voting rule requires that in all preference profiles no voter has an incentive to vote insincerely, provided that all other voters keep their vote fixed. Equivalently, in a sincere voting profile no voter regrets having voted sincerely, once the outcome and each others' votes is made public. In game-theoretic terms, strategy-proofness can be expressed as the following requirement. Construct a game in which voters are the players, the set of Voting can be studied as a game actions available to players are linear orders over the candidates, and their utility is defined by their sincere preference order over the results of a voting rule, which associates a winning candidate with each profile of rankings. If the profile of sincere votes is a Nash equilibria in any such game then the rule is strategy-proof.

Similar game-theoretic constructions were used extensively in the literature on economics, and more recently computer-science, to analyse the strategic structure of voting. A first observation-already done by Farquharson [START_REF] Farquharson | Theory of Voting[END_REF]-is the existence of a multitude of meaningless Nash equilibria in which voters submit irrational votes. If we take a simple example of a plurality vote, and we assume all voters have the same sincere preference over the candidates a > b > c, then the sincere vote profile (a, a, a) is a Nash equilibria, but so are (b, b, b) and (c, c, c) which are clearly Pareto-dominated, but still do not allow for individual deviations. This observation calls for refinements of the basic game-theoretic model of voting or of the solution concepts considered. Much work has been published in economics, starting from the seminal work of Farquharson [START_REF] Farquharson | Theory of Voting[END_REF], with one of the most popular models being that of Myerson and Weber [START_REF] Myerson | A Theory of Voting Equilibria[END_REF], which enriches voting games using utilities. Recent work in computer science have

Refinements of voting games to avoid irrational equilibria

focused on equilibrium refinement, e.g., the models of truth-biased voters [START_REF] Obraztsova | Plurality Voting with Truth-biased Agents[END_REF] and lazy voters [START_REF] Desmedt | Equilibria of plurality voting with abstentions[END_REF] which introduce micro-incentives to eliminate undesirable equilibria. The study of best-response dynamics on a voting game is still a popular subject in computer science under the name of iterative voting (for a survey see, e.g., [START_REF] Meir | Iterative Voting[END_REF]). The report of the Dagstuhl seminar on Computation and Incentives in Social Choice provides a good overview of recent research on the context of this chapter [START_REF] Elkind | Computation and Incentives in Social Choice (Dagstuhl Seminar 12101)[END_REF].

gibbard-satterthwaite games for k-approval

The Gibbard-Satterthwaite theorem implies that strategic voting is unavoidable, but focuses on the specific perspective of a single voter who has complete knowledge of the other voters' preferences. The following example illustrates what happens when more than one such strategic voter or manipulator is assumed to vote strategically:

Example 3.2.1 ([76]). The table below describes a voting situation, in which four voters rank five candidates a, b, c, d, w from the most to the least preferred, with the most preferred candidates on the left of the lists. We assume that the voting rule is the Plurality rule, i.e., the winner is the candidate with the highest number of first positions, and that ties are resolved following a predetermined ordering over the candidates w > a > b > c > d.

Voters Preferences

Voter In the situation described the plurality winner is w, thanks to tie-breaking. This result is the worst possible for the first two voters, who each have the opportunity to manipulate. Voters 1 and 2 are the only Gibbard-Satterthwaite manipulators (GS-manipulators) at this profile: voter 1's insincere strategy consists in voting for b instead of a, thus making b the winner, and voter 2 can vote insincerely in favour of a instead of b, thus making candidate a the winner. However, if both manipulate at the same time, their efforts will cancel out. If we zoom in on the situation when voter 1 and voter 2 are Two GS-manipulators can face an anti-coordination game strategically choosing between their sincere vote and their manipulative vote, while other voters are not strategic, we see that voters 1 and 2 are playing an anti-coordination game.

Let us now extend our analysis to all the voters. We observe that voter 3 is happy and does not have reasons for strategising. Voter 4 does not have any incentive to manipulate: the current winner w is in his second position, so giving her more support will not change the outcome. For instance, the voter does not have any incentive to vote for w instead of d. However, this move is a very strong countermanipulation if voter 4 fears a strategic move from any of the first three players: giving additional support to w makes any manipulation impossible, ending all strategic considerations. Moreover, in game-theoretic terms this move weakly dominates his sincere vote.

In collaboration with Edith Elkind, Francesca Rossi, and Arkadii Slinko [START_REF] Elkind | Gibbard-Satterthwaite Games[END_REF][START_REF] Elkind | Cognitive hierarchy and voting manipulation in kapproval voting[END_REF][START_REF] Grandi | Gibbard-Satterthwaite games for k-approval voting rules[END_REF] we conducted an extensive analysis of the games that Gibbard-Satterthwaite manipulators can play, adding one more tile to the analysis of the cognitive and computational complexity of strategic voting.

(i, s) (s, i) (i, i) (vi)
To showcase some of our results, consider the diagrams in Fig- ure 4. These are representations of all kind of games that two GSmanipulators can face, assuming that each of them have only one manipulation strategy (named i in the diagrams for insincere) other than their sincere one (named s). First, we observe that all GS-games so defined have at least one Nash equilibrium. However, some of them have two (they are anti-coordination games). For the plurality rule, GS-games for 2 players and 2 strategies have a simple graphical representation we characterise which diagrams can be realised, i.e., we construct a voting profile in which there are two GS-manipulators with one manipulative strategy each, playing a game depicted in our diagrams, or we prove that there exists no such profile: Theorem 3.2.1 ([76]). The only diagrams of Figure 4 realizable by Plurality are (ii), (iii), (iv) and (v).

In a companion paper, we adapted the cognitive hierarchy framework of Camerer, Ho, and Chong [START_REF] Camerer | A cognitive hierarchy model of games[END_REF] to a voting situation, in an attempt to refine our model to bounded rational voters. The main difference is at the first level of the hierarchy, since we assumed that level-0 (non-strategic) voters play their sincere strategy rather than playing a random one. At level 1 voters are strategic voters who assume that all other voters will be at level 0, and hence will vote sincerely. At level 2 voters will assume that all other voters are either at level 1, which gives them the ability to countermanipulate. We do not go further than this level in our analysis, since there is evidence that very few voters would be capable or higher-level reasoning (see, e.g, the work of Crawford, Costa-Gomes, and Iriberri, 2013).

In our paper we focus on the basic question that a voter at the level 2 of our hierarchy would face: knowing if one of her manipulation strategies weakly dominates truth-telling (or any other manipulation strategy). We analyse it from the perspective of computational complexity, and we find that under mild assumptions on the set of manipulation strategies this problem is easy for 1-approval (plurality) and 2-approval: Manipulation weakly dominates truth-telling is polynomial for 2-approval Proposition 3.2.1 ([50]). Given a GS-game, where for each voter the set of strategies A i consists of i's truthful vote and a subset of i's minimal manipulations, and two strategies v 1 , v 1 of voter 1, we can decide in polynomial time whether v 1 weakly dominates v 1 .

This results does not extend to 3-approval. Determining the complexity for this problem is still open, but we are able to show that from k 4 the problem of determining whether a manipulation strategy is at the second level of the hierarchy or whether it is an improving strategy is computationally intractable:

From k 4 reasoning about GS-games is computationally intractable Proposition 3.2.2 ([50]). For every fixed k 4, given a GS-game and a strategy v of voter 1, it is NP-hard to decide whether v is a level-2 strategy, and it is coNP-hard to decide whether v is an improving strategy.

The variety of the results we obtained show how rich the framework of GS-games is, and how complex the process of strategic voting can be to voters, from both a game-theoretic and a computational perspective. A recent position paper by Slinko [START_REF] Slinko | Beyond Gibbard and Satterthwaite: Voting Manipulation Games[END_REF] highlights a number of open problems and directions for future work on this topic.

equilibrium selection via pre-vote negotiations

As observed in Section 3.1, the simplest construction of a voting game allows for undesirable Nash equilibria in which players vote irrationally. In collaboration with Davide Grossi and Paolo Turrini [START_REF] Grandi | Negotiable Votes[END_REF], we investigate this phenomenon in games where voters decide over multiple binary issues and have quasi-dichotomous preferences. Borrowing from the work of Jackson and Wilkie [START_REF] Jackson | Endogenous Games and Mechanisms: Side Payments among Players[END_REF], we propose the introduction of pre-vote negotiations as a mean of equilibrium selection, in an attempt to model the complex process of influence that precedes a collective decision.

Our object of study are aggregation games, in which a set of voters have to decide on multiple binary issues, with an aggregation procedure deciding the collective outcome. We focus on non-manipulable aggregation rules such as quota rules and oligarchies, characterised by their sets of winning and losing coalitions. Agents are endowed

We focus on multi-issue binary voting with quasi-dichotomous utilities with simple goals represented by conjunctions of literals from the set of issues, and a payoff function that associates a utility with each outcome of the aggregation rule. The strategic actions of the agents are thus guided by so-called quasi-dichotomous preferences, in which the goal represents the uncompromising positions of the voters, and the payoff allows to compare profiles that both satisfy or both do not satisfy the goal.

We conduct a detailed study of equilibria in aggregation games. We are able to show that truthful equilibria, in which voters submit Truthful equilibria can be totally inefficient a ballot that satisfy their goals, can be totally inefficient, i.e., they can satisfy none of the agents' goals, even if goals are mutually consistent. However, if we allow for endogenous transfers, i.e., binding transfers of utility among players should a given strategy be played, we obtain two positive results. If we define an endogenous aggregation game as an aggregation game in which voters are allowed to sign binding agreements transferring utility before the game is played, and we call surviving NE any Nash equilibria of the underlying aggregation game that can be sustained by a transfer of utility in the resulting two-phase game, we are able to show the following:

Efficient equilibria can be sustained by pre-play negotiations Theorem 3.3.1 ([75]). Let A be an endogenous aggregation game for a non-manipulable aggregator F. Every efficient and truthful NE of A is a surviving NE.

Theorem 3.3.2 ([75]

). Let A be an endogenous aggregation game for a nonmanipulable aggregator F in which a coalition C of voters have consistent goals, and such that C is a winning coalition of F for the conjunction of their goals. Then, every surviving NE of A is C-efficient.

In words, the good Nash equilibria of an aggregation game (those that satisfy the goals of all the agents) are surviving NE and, conversely, all surviving NE of an aggregation game satisfy all the goals of a winning coalition of the underlying aggregation function (provided that these goals are consistent with each other).

Endogenous transfers aside, the analysis of aggregation games could be pushed further, as they augment the well-studied setting of boolean Boolean games with shared control of variables reduce to exclusive control games by adding variables that are under the shared control of a set of agents. In a related collaboration with Belardinelli et al. [START_REF] Belardinelli | Relaxing Exclusive Control in Boolean Games[END_REF] we analysed aggregation games and related mathematical structures from the perspective of the verification of logical formulas expressed in the language of alternated-time temporal logic (ATL), presenting a polynomial reduction from shared control to exclusive control in boolean games.

iterative voting: convergent dynamics, reinforcement learning, and lab experiments

In iterative voting a discrete-time process is defined starting from a classical voting situation (i.e., a profile of preferences and a voting rule), by providing information to the voters about the current state of the vote such as a poll or the current winner, and let them respond to this information by eventually changing their vote. This process is repeated until an equilibrium or a deadline is reached. Iterative voting has become an established research agenda in computational social choice in recent years, and three streams of work can be identified. First, iterative voting can model the iterative response to polls that precedes and election, with the main investigations being the convergence to an equilibrium (see among others, [START_REF] Lev | Convergence of Iterative Scoring Rules[END_REF][START_REF] Meir | Convergence to Equilibria in Plurality Voting[END_REF], and [START_REF] Meir | Iterative Voting[END_REF] for a survey) and the possible manipulations by a central authority [START_REF] Baumeister | Manipulation of Opinion Polls to Influence Iterative Elections[END_REF]. A second, normative, interpretation uses iterative voting to define novel voting rules, interpreting the iterative process preceding the decision as a pre-election deliberative step [START_REF] Airiau | Learning Agents for Iterative Voting[END_REF][START_REF] Grandi | Restricted Manipulation in Iterative Voting: Condorcet Efficiency and Borda Score[END_REF][START_REF] Obraztsova | On the Convergence of Iterative Voting: How Restrictive Should Restricted Dynamics Be?[END_REF]. The Itero3 platform we developed can be seen as an attempt to popularise and study iterative voting rules. Third, each step in an iterative vote can be used to investigate the strategic voting abilities of each agent, typically by means of experiments in the lab [START_REF] Airiau | One-shot and iterative voting for multiple referenda: an experimental study[END_REF][START_REF] Meir | Strategic voting in the lab: compromise and leader bias behavior[END_REF].

Restricted convergent dynamics

Starting from the observation that many of the dynamics initially proposed in this literature do not converge at a stable state (i.e., a Nash equilibria of the corresponding voting game), in a collaboration with Andrea Loreggia, Francesca Rossi, K. Brent Venable, and Toby Walsh [START_REF] Grandi | Restricted Manipulation in Iterative Voting: Condorcet Efficiency and Borda Score[END_REF], we focused on designing restrictions on the voters' actions that guarantee the convergence of the induced dynamics (and still have some descriptive value). Formally, we start from a set of voters each associated with a linear order P 0 i over a set of candidates, and a voting rule F which associates a single winner with each profile P of linear orders. Iterative voting is a discrete-time process, with one or possibly more voters strategically changing their vote at each time point k = 0, 1, . . . , thus defining a sequence of profiles P k for each time point k. The two restricted dynamics we considered are the following:4

Second-chance (SC): the manipulator i moves the second-best candidate in P 0 i to the top of her reported ballot P k+1 i , unless the current winner w = F(P k ) is already her best or second-best candidate in P 0 i .

Best-upgrade (BU): the manipulator i moves the most preferred candidate in P 0 i which is above w = F(P k ) in P k i to the top of her reported ballot P k+1 i , among those that can become the new winner of the election. We analysed theoretically the convergence of the two dynamics and the axiomatic properties of the iterative voting process, and evaluated experimentally the properties of the attractor profiles. To showcase one of our results, we tested the Condorcet efficiency (i.e., the percentage of Condorcet winners that are elected when one exists) of a voting rule in the set of initial profiles P 0 compared with the corresponding ones obtained at convergence of the iterative process. Fig-

Restricted dynamics

in iterative voting increase the Condorcet efficiency ure 5 shows that this parameter is increased by iterative voting under both restricted dynamics (for comparison we also plotted the results of the 2 and 3-pragmatists dynamics of Reijngoud and Endriss [START_REF] Reijngoud | Voter Response to Iterated Poll Information[END_REF]). The improvement is limited, especially under correlated preferences, but still statistically significant.

Reinforcement learning agents

Further convergent dynamics have been proposed in the literature, but all lacked some form of descriptive power: agents are assumed Most dynamics defined in the literature are myopic and memory-less to be myopic since they do not look further than one step ahead in the iterative process, and memory-less since they forget all previous actions by themselves or by the other agents. While a full-fledged theoretical analysis of a more realistic agent seemed out of reach,5 in collaboration with Stéphane Airiau and Filipo Studszinski Perotto [START_REF] Airiau | Learning Agents for Iterative Voting[END_REF] we tested experimentally the performance of autonomous agents designed with reinforcement learning. Figure 6 showcases our main result. We again focused on the Condorcet-efficiency, showing that information given to the voters (the winner of the previous election), our learning agents are able to "find" a Condorcet winner in approximately 85% of the cases. While the number of iterations required is high (about 300), this performance is superior to standard iterative voting dynamics as well as to many classical voting rules. Further results in this line have been obtained in the Master thesis of Loujayn Layka [START_REF] Layka | Multiagent Reinforcement Learning for Iterative Voting[END_REF], which I supervised in 2019, who adapted our learning agent simulation to the case of multi-issue voting.

Behavioural experiments in multiple referenda

The model of multi-issue binary voting, e.g. multiple simultaneous referenda, is particularly interesting. It has been observed that in some cases the resulting combination of accepted and rejected issues can be the worst outcome for a majority or even all the voters (the so-called paradox of multiple elections [START_REF] Brams | The paradox of multiple elections[END_REF]), and in recent years Bowman, Hodge, and Yu [START_REF] Bowman | The potential of iterative voting to solve the separability problem in referendum elections[END_REF] proposed to use iterative voting to inform voters of the possible outcome and give them a chance to steer the result towards more favourable outcomes. In collaboration with Stéphane Airiau, Jérôme Lang, and Ali Ozkes [START_REF] Airiau | One-shot and iterative voting for multiple referenda: an experimental study[END_REF] we designed a behavioural experiment to test such a protocol. A set of subjects each

We tested the framework of iterative voting in multiple referenda in lab experiments faced a different 2 × 2-matrix with each cell containing their final potential gain should the cell be elected, and had to vote in a 2-issue referenda on which column (left-right) and which row (top-bottom) should be chosen. The winner would be made public and the election repeated until the same winning cell was elected 3 times in a row (or a cap of 15 repeated elections was reached). The experiments were conducted at the Laboratoire d'Economie Experimentale de Paris (LEEP) in 2019, and our analysis of the results showed two main results. First, we analysed the behaviour of voters at the first step of the election, discovering that they tend to make optimistic choices when casting a vote on non-separable variables. Second, we observed an increase in social welfare at the end of iterative voting with respect to truthful voting, confirming the results of [START_REF] Bowman | The potential of iterative voting to solve the separability problem in referendum elections[END_REF] which were obtained via computer simulations.

conclusions and perspectives

In this chapter I presented several lines of research investigating the strategic behaviour of voters involved in a collective decision. The underlying model is that of a voting game, in which voters are players, actions are the possible voting ballots, and the players' preferences are defined by combining a voting rule with a profile of sincere preferences given to the voters. The Gibbard-Satterthwaite games presented in Section 3.2 act as magnifiers that allow the researcher to restrict the number of manipulators and their action sets to analyse in depth a specific situation of strategic voting. There are a number of problems left open in our analysis, most notably closing the gap between the computational complexity of reasoning on level-2 strategies for 3-approval. In Section 3.3 we proposed pre-vote negotiations as equilibrium selectors in voting on multiple binary issues. An interesting link could be drawn here with the research line presented in Chapter 2 by assuming that such pre-vote negotiations need to be consistent with a predetermined trust network connecting the individuals. Section 3.4 is perhaps the most exploratory of the three main research directions presented. Iterative voting is under scrutiny by researchers for a number reasons. First, as a model of repeated interactions it can be rather close to what is experienced by voters who participate in multiple elections, view polls, and learn how to respond and behave in these situations. Second, it can suggest novel voting procedures which exploit the iteration phase to inform the voters of each others' preferences. In particular, the use of reinforcement learning agents can be expanded by allowing agents to access a poll summarising the agents' vote (in line with the recent work of Baumeister, Selker, and Wilczynski [START_REF] Baumeister | Manipulation of Opinion Polls to Influence Iterative Elections[END_REF]), and their information structure can be refined by the introduction of a communication network.

The Itero platform

An important direction in my future research is the use of the Itero 6 voting platform, which was developed in 2021 by Joseph Boudou dur-ing his postdoc in the ANR SCONE research project. This platform allows the organisation of iterative elections using the plurality rule. Election organisers can decide the final deadline for the election as well as the duration of each iteration round. At each round, after the initial one, all voters can see the plurality score of the candidates at the previous rounds, and have the opportunity to update their vote. Figure 7 and 8 show screenshots of the voting interface and of the information available to the voters at each round. The platform was developed with two purposes in mind. First, as a tool for outreach workshops (such as the EU Researchers Night), building on the successful experience of the Whale 7 platform developed in Grenoble. The underlying idea is to make voters aware that reliable information about other voters' preferences can be useful to avoid undesirable voting outcomes, formalising a common experience in countries that use plurality voting in their political elections (plurality with runoff for the case of France). Going further, iterative voting can be proposed as a simple deliberative platform, with the aim of reaching consensus, or at least an equilibrium outcome. Second, specific voting experiments could be run online (taking inspiration for instance from the Voter Autrement online experiments [START_REF] Bouveret | Voter Autrement 2017 for the French Presidential Election[END_REF]) in order to obtain data about iterative voting and strategic voting.

A crucial aspect of any collective decision process is the elicitation and the representation of the voters' preferences. To give a simple example, a vote over candidates with the plurality rule only elicits the most preferred candidate from voters, while a vote with STV or Borda asks for the entire ranking over candidates. Typically, the more information is elicited the better. But in many applications the combinatorial structure of the problem can significantly bind this process, adding computational or cognitive limitations.

Example 4.0.1 (Running example: automated travel planner). 1 An automated travel planner application collects the preferences of a group of travellers and creates a custom travel plan for the group. The list of possible activities for the day are the following: ?

? ? ?

The group can do a guided tour of the city, visit the beach, have a stopover at the hotel during the day, and visit a museum. A travel plan is any subset of these activities. 2 What does the group want to do?

We first observe that in our running example there are 2 4 = 16 possible travel plans. While it is not inconceivable to ask for a complete ranking of the 16 travel plans to each traveller, we can already expect some cognitive limitations, especially if we do not allow for ties. For instance, travellers can rank just their top three activities

The combinatorial nature of the problem makes complete preference elicitation infeasible and then copy the order of presentation on the app for the remaining ones, with the risk that the 4th activity in the presentation order comes very high in the collective ranking without any grounding in the agents' real preferences. Moreover, as soon as the number of possible activities increases, the number of possible travel plans grows exponentially.

This chapter presents a number of compact languages for preference representation that can be implemented by the travel planner to elicit and then aggregate the preferences of the group members:

Judgments: the automated planner can ask yes/no questions on possibly complex propositions such as "do you want to take the guided tour and visit the museum?", or "do you require a stopover at the hotel if we visit the beach?". Section 4.1 presents a unified view on several frameworks for the aggregation of judgments, analysing the relative succinctness of the frameworks.

Goals: the members of the group can express any propositional formula over the activities, such as "I want to either visit the museum or do the guided tour, and I do not want to go to the beach". Section 4.2 presents extensive work on goal-based voting, presenting a number of rules that associate travel plans with each collection of goal-formulas.

Conditional preferences: some clever members of the group might realise that they have preferential dependencies, such as "If we visit the beach I prefer the guided tour to the museum (as I'll be dressed informally), otherwise I prefer the museum to the guided tour". In Section 4.3 we use the framework of conditional preference networks (CP-nets) to compactly express such statements, expanding it with constraints and allowing for incomplete preferential statements.

Collective sentiment analysis: the automated travel planner is complemented with a bot that collects the travellers' internet data and proposes a plan without having to ask for the group members' preferences directly. Section 4.4 presents a proposal to expand classical sentiment analysis of text with the extraction and the aggregation of individual comparative judgments.

Work presented in this chapter is the result of numerous collaborations. I started working on a unified framework for judgment aggregation languages towards the end of my doctoral studies in Amsterdam, and the project advanced considerably thanks to a course I gave at ESSLLI 2014 in Tübingen, during which Ronald de Haan (one of the co-authors) answered an open question I presented. The work on goal-based voting is the bulk of the PhD thesis of Arianna Novaro [START_REF] Novaro | Goal-based voting[END_REF], which I supervised in Toulouse from 2016 to 2019. Work on conditional preferences started at the University of Padova with the PhD thesis of Cristina Cornelio [START_REF] Cornelio | Preference reasoning and aggregation over combinatorial domains in uncertain and multi-agent scenarios[END_REF] (probabilistic extension) and a collaboration with Nicolas Maudet and Hang Luo (constraints), and continued in Toulouse during the visit of Adrian Haret from TU Wien in our research group (incomplete CP-nets). Research on sentiment analysis also started at University of Padova, during the visit of Vijay Saraswat from IBM TJ Watson laboratory.

judgments and binary views

Consider once more the situation described in Example 4.0.1. Suppose that the preferences of the travellers over the four possible activities are elicited by means of the following questions: Q1: Do you want to include a stop-by at the hotel? Q2: Do you want to take the tour of the city centre or visit the museum (or both)? Q3: Do you require a stop-by at the hotel if a visit to the beach is scheduled? Q4: Do you want to do at least one of the three activities (tour, museum, beach)?

Observe that the questions are not logically independent. There are (at least) two possible choices in the design of such an automated planner. The first is to represent each question as a propositional formula, with the travellers' answers thus being consistent sets of such formulas. If we denote with propositional variable T the guided tour, B the beach, H the hotel, and M the museum, then question Q2 corresponds to formula T ∨ M, and Q3 to formula B → H.

The second possibility is to pre-process the questions in a constraint, and represent the travellers' answers as true/false assignments to propositional variables Q 1 , Q 2 , Q 3 , Q 4 that are required to satisfy the constraint. In the example defined above such constraint would corresponds to formula:

(Q 1 → Q 3 ) ∧ [(Q 4 ∧ Q 3 ) → Q 1 ] ∧ (Q 4 → Q 2 )
In collaboration with Ulle Endriss, Ronald de Haan, and Jérôme Lang [START_REF] Endriss | Succinctness of Languages for Judgment Aggregation[END_REF], we compared four possible specification languages for such applications in terms of their succinctness, i.e., the ability of a language to compactly represent the specification of a problem such as the one described in the previous example.

We begin by introducing the basic language which represents sets of feasible combinations over m items by explicitely listing them: Definition 4.1.1. The basic language (BASIC) for the specification of collective decision problems over logically structured domains is L

0 = {X | X ⊆ {0, 1} m , X = ∅, m ∈ N}.
We focus here on formula-based judgment aggregation and binary aggregation with constraints

We then define four compact specification languages, each composed by a set L of specifications and an interpretation function τ : L → L 0 . In the interest of space, we give only two definitions corresponding to the well-studied settings of formula-based judgment aggregation (see, e.g., [START_REF] Baumeister | Judgment Aggregation[END_REF] or [START_REF] Endriss | Judgment Aggregation[END_REF]) and binary aggregation with integrity constraints [START_REF] Grandi | Lifting Integrity Constraints in Binary Aggregation[END_REF]: Definition 4.1.2. The language of judgment aggregation (JA) is defined as follows:

L JA = {{φ 1 , ¬φ 1 , . . . , φ m , ¬φ m } | φ j ∈ PL, m ∈ N} τ JA (Φ) = J(Φ),
where PL is the language of propositional logic and J(Φ) is the set of complete and consistent subsets of Φ. Definition 4.1.3. The language of binary aggregation with integrity constraints (IC) is defined as follows:

L IC = {Γ | Γ ∈ PL {p 1 ,...,p m } satisfiable, m ∈ N} τ IC (Γ ) = Mod(Γ ),
where Mod(Γ ) is the set of models of the formula Γ , and PL {p 1 ,...,p m } is the language of propositional logic over m variables.

In words, the language of judgment aggregation requires voters to submit consistent subsets of m propositional formulas built over an arbitrary set of variables, while binary aggregation with constraints asks voters to submit yes/no answers to m propositional variables subject to an integrity constraint. An example of the two languages was provided at the beginning of this section.

All frameworks we study are equally expressive, i.e., the interpretation functions τ JA and τ IC are surjective. We then focus on the relative succinctness of the two languages, inspired by the work of Cadoli et al. [START_REF] Cadoli | Space Efficiency of Propositional Knowledge Representation Formalisms[END_REF] and Gogic et al. [START_REF] Gogic | The Comparative Linguistics of Knowledge Representation[END_REF]: Definition 4.1.4. Given two specification languages L 1 and L 2 , we say that L 1 is at least as succinct as L 2 , and write L 1 L 2 , if there exists a function f : L 2 → L 1 and a polynomial p s.t., for all X ∈ L 2 , we have:

• f(X) ≡ X, and • size(f(X)) p(size(X)).

A straightforward result can be obtained by observing that propositional formulas are strictly more succinct than lists of feasible models: Proposition 4.1.1. IC is strictly more succinct than BASIC.

We then show the following less straightforward result: Theorem 4.1.1 ([54]). JA is strictly more succinct than IC, unless the Polynomial Hierarchy collapses.

That is, representing a logically structured domain for a collective decision by means of propositional formulas leads to more compact representations than a pre-processing of the problem in a constraint. This gain in the size of the representation comes with the computational cost of checking if an individual judgment is valid: it is NPhard to check if a JA set of formulas is consistent, while it is polynomial to check if a IC specification is a model of the constraints. However, in our paper we compared the computational complexity The computational complexity of aggregation tasks does not differ in the two frameworks of higher-level tasks related to the aggregation of the individual judgments, most notably the computational complexity of winner determination for a number of aggregation rules. We showed that most of the time the computational complexity of winner determination does not vary between the two specification languages, with few notable exceptions.

goal-based voting

The travelling group problem (recall the running Example 4.0.1) can be approached as a multiple referendum, asking travellers a yes/no vote on each of the four activities. Such a choice would cause wellknown problematic issues, such as those pointed out by Brams, Kilgour, and Zwicker [START_REF] Brams | The paradox of multiple elections[END_REF], but we want to focus here on the voters' problem of deciding how to vote. Suppose for instance that there are three agents: Ann who wants to do all activities, Barbara who only wants to visit the museum, and Camille who wants to do one activity among the guided tour, museum, or beach, but no more than one. In a multiple referenda they might vote as follows:

Guided Tour Beach Hotel Museum Ann Barbara × × × Camille × × ×
By taking a majority vote on each of the issues, the result would see Camille particularly unhappy, since the group will visit both the beach and the museum. Had she known the other travellers' votes she would have supported the museum, or no activity at all.

In collaboration with Arianna Novaro, Dominique Longin, and Emiliano Lorini [START_REF] Novaro | Goal-based voting[END_REF][START_REF] Novaro | Goal-Based Collective Decisions: Axiomatics and Computational Complexity[END_REF][START_REF] Novaro | Strategic Majoritarian Voting with Propositional Goals (Extended Abstract)[END_REF], we studied extensively the possibility of letting voters express a set of possible plans by means of propositional formulas over atoms representing the issues at stake. Such a setting Each voter submits a propositional goal over the issues corresponds to social choice with dichotomous preferences, with the combinatorial aspect of the problem making the aggregation nontrivial. It is also the same setting as the one studied in belief merging (see, e.g., [START_REF] Konieczny | Merging Information Under Constraints: A Logical Framework[END_REF]), while the normative properties we wish to impose on our aggregators are different. In particular, we observed a tension between fairness properties of a goal-based voting rule and its decisiveness or resoluteness, i.e., its ability to output a unique decision

We observe a tension between fairness and resoluteness in most situations. One would indeed want to avoid an automated travel planner to output a large set of equally preferred travel plans, requiring for instance a second vote to choose which of the equally preferred travel plans to implement.

Let us identify this tension formally. The setting of goal-based voting sees a non-empty finite set of agents N = {1, . . . , n} taking a collective decision over a set of binary issues I = {1, . . . , m}. We assume all issues to be independent from one another. Each agent expresses an individual goal as a propositional formula over atoms in I, which we shall call γ i . For instance, in the example described above the set of issues is {T , B, H, M} and Camille's goal is T ∨ B ∨ M. A goalprofile Γ = (γ 1 , . . . , γ n ) is the choice of a goal by each of the voters, and a goal-based voting rule F is a collection of functions for all n, m ∈ N that associates with each goal profile a non-empty set of issues: F : (L I ) n → P({0, 1} m ) \ ∅. The strongest definition we can give to formalise the resoluteness of a rule is the following:

Resoluteness (R) A rule F is resolute if and only if on all goal profiles Γ we have that |F(Γ)| = 1.
This condition can be relaxed to account for cases in which the electorate is equally split on an issue, allowing the rule to abstain:

Weak-resoluteness (WR) A rule F is weakly resolute if and only if for all profiles Γ and issues j ∈ I there exists a partial conjunction ϕ of literals in I such that F(Γ ) = Mod(ϕ).

Clearly, if a rule F is resolute then it is also weakly resolute. Let us now introduce two axiomatic properties pertaining to fairness, the first requiring that all agents are to be treated equally, and the second that no issue is biased towards acceptance or rejection: Anonymity (A): A rule F is anonymous if for any profile Γ and any permutation σ : N → N, we have that F(γ 1 , . . . , γ n ) = F(γ σ(1) , . . . , γ σ(n) ).

Duality (D):

A rule F satisfies duality if for all profiles Γ we have that

F(γ 1 , . . . , γ n ) = {(1 -v(1), . . . , 1 -v(m)) | v ∈ F(Γ)}, where γ = γ[¬1 → 1, . . . , ¬m → m].
In line with a well-known impossibility in classical social choice theory [START_REF] Moulin | The strategy of social choice[END_REF], we prove the following impossibility:

Proposition 4.2.

([126]

). There is no resolute rule F satisfying anonymity and duality.

Let us now consider a different fairness axiom, already considered in the literature on belief merging (known as IC2 in this literature):

Model-unanimity (IC2): if the conjunction of the individual goals

i∈N γ i is consistent, then F(Γ) = Mod( i∈N γ i ).
While model-unanimity seems to be a harmless condition to assume, we show the following simple impossibility result, formalising a deeper tension between resoluteness and fairness: Let also m i (j) be a twocomponent vector counting the total number of zeros and the total number of ones in the models of goal γ i : Independence (I): A rule F is independent if there are functions f j :

D n m → C for j ∈ I and n, m ∈ N + such that for all profiles Γ we have F(Γ) = j∈I f j (m 1 (j), . . . , m n (j)).

This adaptation of the axiom of independence states the existence of functions that decide the outcome of a rule F on each issue independently from the result on other issues. Such property is particularly interesting for goal-based voting, thanks to the following proposition: Proposition 4.2.3. Every independent rule F is weakly resolute.

We can therefore look into the class of independent rules to seek for goal-based voting rules that satisfy both resoluteness and fairness conditions. In our work we present three adaptations of the most classical of the independent rules: the majority rule. While the formal

We define three variations of the majority rule: TrueMaj, EMaj, and 2sMaj definitions are left out in the interest of space, as well as the formal definitions of the axioms of equality, neutrality, and monotonicity (for the details consult the PhD thesis of Arianna Novaro [START_REF] Novaro | Goal-based voting[END_REF]), we are able to characterise axiomatically one of our rules as follows: Theorem 4.2.1 ([126]). A rule satisfies equality, independence, neutrality, anonymity, monotonicity, unanimity, and duality iff it is TrueMaj.

Intuitively, the goal-based rule TrueMaj accepts a given issue if the overall sum of acceptances in the individual models, discounted by the number of models submitted by each agent, is greater than the same figure for the number of rejections. By Theorem 4.2.1 this rule seems to realise the sought trade-off between resoluteness and fairness in goal-based voting.

Given that goal-based voting rules need take a compactly represented input, their computational complexity is necessarily higher than their classical voting counterparts. We focused on the problem of winner determination, i.e., constructing the winning outcome from the voters' propositional formulas. We prove that the three adaptations of the majority rule we propose are PP-hard, where PP is the class of problems that are solvable by a non-deterministic Turing machine that accepts in strictly more than half of all non-deterministic choices if and only if the answer to the problem is yes:

L ∧ L ∨ L ⊕ E D E D E D EMaj SP SP M SP M M TrueMaj SP SP M SP M M 2sMaj SP SP SP SP M M
Table 1: Manipulation and strategy-proofness results for the three adaptations of the majority rule to goal-based voting, and the language restrictions L ∧ , L ∨ and L ⊕ . In particular E stands for erosion manipulation, D for dilatation, SP for strategy-proof, and M for manipulable.

The typical PP-complete problem is MAJSAT, asking for a given propositional formula φ if |Mod(φ)| > |Mod(¬φ)|, and the theorem is proven by a reduction from a suitable modification of MAJSAT. Problems in this class are particularly hard, the class PP containing both NP and co-NP, and P PP containing the entire polynomial hierarchy. We also provide the following upper bounds: Theorem 4.2.3 ([126]). Winner determination for TrueMaj and Emaj is in PSPACE, and for 2sMaj is in P PP .

In line with the strategic view described in Chapter 3 we also investigated the possible manipulation strategies of the voters when using propositional goals. We considered three main manipulative strategies: erosion, by submitting a more restrictive goal than the sincere one, dilatation, by submitting a less restrictive goal than the sincere one, and unrestricted manipulation. A common example of manipula-We consider three manipulative strategies: erosion, dilatation, unrestricted tion by erosion is the common behaviour on Doodle polls to report a less available agenda in order to steer the decision towards more preferred slots. As the outcome of a goal-based voting rule can contain more than one subset of the issues, we also need to consider several measures of satisfaction for assessing an agent's manipulation move. Our findings show that manipulation is ubiquitous, albeit computationally hard (but no harder than computing the result of the rules themselves). Strategy-proofness can be guaranteed by restricting the language of possible goals to conjunctions (corresponding to judgment aggregation with abstentions) or to disjunctions, in which case we obtain strategy-proofness only with respect to dilatation. Our results are summarised in Table 1.

There are two interesting problems that remain open. First, given

Characterising a goal language for tractable winner determination remains open the high computational complexity of computing the result of the three adaptations of majority we proposed, it would be interesting to identify a non-trivial subclass of propositional formulas over which winner determination is tractable (or easier than PP). Second, in a similar way it would be interesting to identify the boundary between manipulable and non-manipulable instances of goal-based voting, by suitably restricting the language for goals.

conditional preferences

In the previous two sections we dealt with languages to compactly represent dichotomous preferences over a combinatorial domain, by either expressing our best option or a set of options in the form of a propositional goal. In this section we consider a more complex form of preference named ceteris-paribus: an agent prefers the value

T BHM > T BHM > T BHM > > • • • T BHM > T BHM • • • > > • • • T BHM > T BHM • • •
A vast amount of papers considered generalisations of CP-nets and designed algorithms for their use. More recently, this line of research has been under the scrutiny of behavioural experiments, in an attempt to measure the practical use of conditional preferences by humans. The results are mostly negative, with lexicographic preferences being more common than conditional ones (preliminary results have been presented by [START_REF] Allen | Beyond Theory and Data in Preference Modeling: Bringing Humans into the Loop[END_REF]). Still, CP-nets have been an influential language in preference representation, and are still being applied in normative studies of preferences such as the recent literature on endowing artificial intelligences with ethical principles (see, e.g., [START_REF] Calegari | Modeling Contrary-to-Duty with CP-nets[END_REF][START_REF] Loreggia | Value Alignment Via Tractable Preference Distance[END_REF]).

My contributions in this area pertain to voting with conditional preferences, designing algorithms or analysing the computational complexity of computing the outcome of a known voting rule when the preferences of the voters is represented compactly using (generalisation of) CP-nets.

In collaboration with Hang Luo, Nicolas Maudet, and Francesca Rossi we tackled the problem of voting under constraints with CPnets [START_REF] Grandi | Aggregating CP-nets with unfeasible outcomes[END_REF]. When the dependencies of the voters' CP-nets are aligned (technically, there exists an acyclic topological ordering of the union of the CP-nets dependency graphs) a sequential vote can be taken using any voting rule [START_REF] Lang | Sequential composition of voting rules in multi-issue domains[END_REF]. In our paper we considered a binary setting Voting with CP-nets under feasibility constraints with the addition of a constraint that binds the possible outcomes of the vote. We characterise settings in which sequential vote by majority is guaranteed to satisfy the constraint, under very restrictive assumptions of CP-nets being separable and individuals' top outcomes satisfying the constraints. A more interesting result can be obtained when the constraint is binary, in which case sequential majority voting can be used with any profile of CP-nets that satisfies some conditions of coherence with respect to the constraint. Finally, we design an algorithm that adapts the sequential procedure of majority voting to satisfy the constraint when none of the above-mentioned restrictions hold. We show that the algorithm is correct and that it runs in polynomial time in the size of the compact input. We take a different stance in a collaboration with Cristina Cornelio, Judy Goldsmith, Nick Mattei, and Francesca Rossi [START_REF] Cornelio | Reasoning with PCP-nets in a Multiagent Context[END_REF]. We first introduce and study a generalisation of CP-nets that can quantify the uncertainty of the individual preferences (called PCP-nets) and then use it as a representation of a profile of CP-nets. We define two

We represent multi-agent preferences as a probabilistic CP-net methods to build a PCP-net from the users' preferences, and combine them with two algorithms we designed to extract the top outcome of the aggregated PCP-net. We analyse the two methods both axiomatically and experimentally, concluding that one of the two methods is superior as a voting procedure.

Finally, building on the work of Rossi, Venable, and Walsh [137] that defined voting semantics over collections of CP-nets, and on the work of Goldsmith et al. [START_REF] Goldsmith | The Computational Complexity of Dominance and Consistency in CP-Nets[END_REF] that generalised CP-nets to account for incomplete and more general logical CP-statements, in collaboration with Adrian Haret and Arianna Novaro we studied the aggregation of incomplete CP-nets [START_REF] Haret | Preference aggregation with incomplete CP-nets[END_REF]. The assumption of completeness of a CP-net needs to be relaxed with non-trivial dependency structures or in applications where the preference statements of the voters are elicited in an online or iterative fashion. In our paper we

We study the aggregation of gCP-nets use gCP-nets, which allow for conditional statements involving more than one variable, such as "if we go to the museum and to the beach then I prefer not having a guided tour", which would be represented with formula M ∧ B : T > T . We study the four semantics defined in the literature for voting with multiple CP-nets, and show that most algorithmic tasks are PSPACE-complete. Albeit being mostly negative results from the point of view of computational complexity, our results show that the aggregation of gCP-nets is not harder than reasoning with a single gCP-net. However, the assumption of working with gCP-nets do not allow us to clearly separate hard from easy aggregation problems. The recent work of Lukasiewicz and Malizia [START_REF] Lukasiewicz | Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting[END_REF] presents a clearer picture of the computational complexity of aggregation tasks by working with complete CP-nets, obtaining results ranging from polynomial algorithms to Σ p 2 -completeness.

preference and polarity

The abundance of user data on the Internet stimulated the development of applications such as recommender systems that are directly able to interact with a user or a group of users without having to elicit her preferences. A technique that is often at the basis of such applications is sentiment analysis, a collection of algorithms from natural language processing that can elicit a polarity (typically: positive, negative, or neutral) from textual data (for an introduction see, e.g., [START_REF] Liu | Sentiment Analysis and Opinion Mining[END_REF]). One can imagine the use of similar techniques in group decision-making applications such as group recommender systems, and in collaboration with Francesca Rossi and Vijay Saraswat we proposed a method inspired from social choice theory for collective sentiment analysis [START_REF] Grandi | A Borda Count for Collective Sentiment Analysis[END_REF]. We started from the observation that classical sentiment analysis falls short as soon as the number of alternatives to be considered is larger than one:

Example 4.4.1 (Adapted from [START_REF] Grandi | A Borda Count for Collective Sentiment Analysis[END_REF]). Let us take a simplified example of our running Example 4.0.1. A fully automated travel planner has access to a group of users' textual data on previous trips as well as their social media textual activity. The problem is simple: it has to decide if the group prefers a visit to the museum to a day at the beach (only one of the two activities is possible). Of the 35 group participants, sentiment analysis techniques concluded that 20 people are talking positively about going to museums while 15 are talking negatively about it, and 30 people are talking positively about going to the beach while 5 negatively. However, what the participants express on social media is just the tip of their preferences, which we can assume being a ranking of which of the two activities they would choose if they were confronted with the choice. We assume that the preferences of the voters are represented in the following table, with activities to the left being preferred to those to the right, and the bar in the center signalling the threshold of positive vs negative polarity: a number of voters from the same profile, computing at each time the new result of the rule and its distance from the winner in the complete profile, using the same notion of score as for the computation of the rule. Our results are summarised in Figure 9, which shows that the rule always behave better than a random procedure, and that its accuracy grows quickly when completeness in increased.

conclusions and perspectives

This chapter begun with a running example of social choice over a combinatorial domain, in which complete elicitation or representation of the agents' preferences is computationally intractable. We therefore introduced and studied compact languages for the representation of the agents' preferences, and rules for the computation of the collective outcome. We started in Section 4.1 with a comparison of four languages for the aggregation of judgments in terms of their relative succinctness. Section 4.2 instead assumed that the voters' input comes in the form of propositional goals, and proposed adaptations of the majority rule to this setting. Conditional preferences were introduced in Section 4.3, which presented three lines of research in voting with CP-nets: under constraints, using probabilistic CP-nets, and dealing with incomplete input. Finally, Section 4.4 considered input extracted from users' textual data, combining a polarity with comparative statements over the alternatives.

Overall, the languages we discussed in this chapter deal with applications that are purely discrete. In ongoing work with Linus Boes, Rachael Colley, Jérôme Lang, and Arianna Novaro we are generalising known aggregation rules to settings in which alternatives are associated to a numerical weight, such as participatory budgeting or collective scheduling, showing yet one more bridge from knowledge representation to collective decision-making. Building on the framework of judgment aggregation with weights, first introduced by Nehring and Pivato [START_REF] Nehring | The median rule in judgement aggregation[END_REF], we are able to show that a number of previous problems-which we name collective combinatorial optimisation problems-and the corresponding aggregation rules can be viewed as instances of a more general definition. This class of problems includes participatory budgeting, collective scheduling, and collective spanning trees.

The variety of decision problems that can be modelled with a combinatorial approach, and the vast number of techniques developed in AI to deal with the resulting exponential domains, allow for an incredible number of bridges between knowledge representation, reasoning, and social choice. A road map and a number of open problems are Bridges between knowledge representation, reasoning, and social choice sketched in an invited talk by Lang [START_REF] Lang | Knowledge Representation, Reasoning, and Computational Social Choice --Invited Talk[END_REF].

One of the main critiques to these approaches is the prohibitive computational complexity of the resulting representations or algorithms (e.g., in this chapter we saw computational problems in PP or in PSPACE). This is a fair point, and research in this area should have as a first priority to minimise complexity and maximise applicability. On the one hand, applications abound in which the scale of the problem is not central, and SAT or ILP solvers can be used efficiently to solve certain NP-hard problems. For instance, experiments on NP-hard participatory budgeting rules are often run using ILP solvers (see, e.g., [START_REF] Talmon | A Framework for Approval-Based Budgeting Methods[END_REF]). On the other hand, depending on the importance of the collective decision being taken, it can be crucial to obtain guarantees on the time execution of collective decision methods on realistic instances. Moreover, human voters can often profit from more expressivity (as many of our examples showed), and goal-oriented autonomous agents have already a hard (computational) time to reason qualitatively about their options. 3

C O N C L U S I O N S A N D P E R S P E C T I V E S

This thesis presented an overview of my past research, in which I focused on enriching models of collective decision-making to take into account the interaction among decision-makers, their strategic behaviour, and to provide expressive yet compact means for preference elicitation and aggregation.

Interactive social choice

Chapter 2 presented a number of research lines arising from the addition of a social network-represented as a graph-connecting the participants of a collective decision. It is the longest chapter and my most active research line. I started by presenting a number of attempts at adapting diffusion models to social choice settings, in which individual opinions are represented as multiple binary views over possibly interconnected issues, or linear orders over a set of alternatives, and social networks are seen as representing trust or influence among agents. Such models were analysed theoretically, mostly focusing on the problem of termination of the diffusion process or on characterising the profiles at termination, as well as with multiagent simulations, analysing whether opinion diffusion can help aligning the preferences of the decision-makers. I also presented a model of strategic opinion diffusion in which agents can choose whether to exert their influence or retain from it towards the satisfaction of given individual goals. By taking a different interpretation of networks, seen as communication channels for information flow among the agents, I presented initial results on designing algorithms to identify phenomena generalising the majority illusion. In a final change towards a mechanism design perspective, I presented work on conceiving algorithms for eliciting and exploiting the trust networks among individuals towards better decision-making. I described two models, one that proposed a personalised version of collective ratings, and the other that enhances liquid democracy with multi-agent ranked delegations.

Strategic social choice

A long-lasting research problem in social choice theory analyses the strategic behaviour of voters, and in Chapter 3 I presented my contributions in this area. First, in the classical setting of k-approval voting, I introduced and studied Gibbard-Satterthwaite games, which are magnifying lenses on a strategic vote involving multiple voters.

Our results show, both analytically and with algorithmic techniques, that manipulation is complex, perhaps too complex for the voters involved in the game, with some exceptions in the easiest settings. Second, starting from a vote on multiple binary issues with agents provided with quasi-dichotomous utilities-a setting we called aggregation game-I presented the use of pre-vote negotiations and showed that they exclude undesirable equilibria and sustain efficient equilibria of the original aggregation game. Third, iterative voting considers best or better response dynamics in voting, either as a model of a repeated response to polls or as a voting procedure in itself. I presented an experimental study directed at designing best-response dynamics that are guaranteed to terminate, a behavioural experiment in the lab aimed at investigating real voters' behaviour in iterative voting, and work on the development of reinforcement learning agents that adapt their vote in multiple repeated elections and can reach collective decisions comparable to those of well-known voting rules.

Expressive social choice

Chapter 4 linked classical social choice with knowledge representation techniques, opening the possibility of designing and studying social choice procedures over combinatorial domains. Four settings were considered, in increasing order of expressive power of the voters' ballots. I presented a comparison of judgment aggregation frameworks in terms of their succinctness in representing combinatorial domains over multiple binary issues. In this setting agents express binary views over multiple issues, or a set of propositional formulas from an agenda. This assumption can be relaxed in two ways. First, I presented and analysed rules for the aggregation of propositional goals, which represent compactly dichotomous preferences over a binary combinatorial domain. Second, I studied two generalisations of conditional preference networks and the corresponding aggregation problems, one with probabilistic statements and the second one allowing incomplete specifications. I also presented work proposing rules for collective sentiment analysis, in which the agents' preferences are not elicited but extracted with natural language processing techniques from their textual expressions.

going further

In this section I summarize the main avenues research directions that I intend to pursue in the coming years. Open problems and detailed Specific open questions and future work are discussed at the end of each chapter future research directions were described in the closing sections of each chapter.

Interactive democracy

Research in computational social choice has considerably expanded the kind of social choice problems considered in classical studies of collective decision making, as well as the set of techniques employed in their analysis, and this thesis provided several such examples. One of the factors behind the success of this contemporary view on social choice is the shift from almost-universal normative principles applied to political elections or to the construction of social welfare measures, to a problem-based approach on arguably lower-stake decisions such as participatory budgeting, committee elections, or school matching. My future research will sit in this latter line of work, more precisely in the study of collective decision mechanisms which may involve a number of back-and-forth interactions between the voters and the mechanism, a research agenda that has been termed "interactive democracy" [START_REF] Brill | Interactive Democracy[END_REF]. In particular, I plan to focus on three such interactive mechanisms:

• Starting from the research presented in Section 2.3 on liquid democracy, I plan to investigate the relation between delegative voting and opinion diffusion. The two models can be seen as being one the inverse of the other, e.g., the fact that agent a delegates to agent b can be seen as a formalisation that agent b influences agent a. Termination states of opinion diffusion models can therefore be used to characterise the possible results of delegative elections. Also, other collective decision-making mechanisms can be made delegative, 1 and a full-fledged model of delegations in multi-issue voting under constraints could be proposed as an encompassing framework.

• In participatory budgeting, a number of projects have to be funded by a collectivity with an overall budget to be respected. On the theoretical side, I plan to investigate further the relations between judgment aggregation and participatory budgeting, building on initial previous work developing an encompassing framework for collective discrete optimisation problem. On a more practical side, I started a collaboration with the Mairie de Toulouse which resulted in a student project analysing their data from their 2019 participatory budgeting campaign. In the long term I plan to extend and develop this collaboration in an attempt to popularise the numerous research results on participatory budgeting and at the same time obtain datasets for testing new rules, in line with recent research on this topic [START_REF] Laruelle | Voting to select projects in participatory budgeting[END_REF].

• A tension can be identified in many real-world situations involving a social choice: on the one hand the use of simple decision rules with bad properties is widespread, and on the other hand rules with good theoretical properties are often difficult to explain to voters and, most importantly, to election organisers. A classical example is the use of the plurality rule for political elections. Iterative voting proposes a possible solution to similar situations: the repetition of a collective decision with a bad rule can actually lead to results that have good theoretical properties. In future work I plan to investigate the use of iterative voting rules as simple deliberative processes. The Itero platform presented at the end of Chapter 3 is part of this agenda, and will be exploited in both outreach events and behavioural experiments.

Agent-mediated social choice

If we focus on those high-stake decisions that were at the core of classical research in social choice, such as political elections, there seems to be a growing consensus that democracy is experiencing serious problems entering in the XXIst century, but there is disagreement on how to cure them. Scientific and technological advancements in information technology are disrupting centuries-old institutions such as the banking and finance sector, and transportation: democratic institutions are even older, and there are repeated proposals to "redesign our political system" taking advantage of XXIst century innovations (see, e.g., [START_REF] Mancini | Why it is time to redesign our political system[END_REF]). Moreover, well-known scholars in computer science

Can solutions for democracy's problems come from innovations in IT?

are beginning to propose encompassing visions for eDemocracy and its specifications [START_REF] Chaum | Random-Sample Voting[END_REF][START_REF] Shapiro | Foundations of Internet-enabled Democracy[END_REF], complemented with more focused position papers in multi-agent systems [START_REF] Brill | Interactive Democracy[END_REF] and media studies [START_REF] Dalberg | Democracy via Cyberspace[END_REF].

When it comes to democracy, the use of AI techniques has rather bad connotations [START_REF] Helbing | Will Democracy Survive Big Data and Artificial Intelligence[END_REF], the most notorious application having been the use of automated micro-targeting in political campaigns. In my opinion there are two reasons why current artificial intelligence techniques fall short in aiming at solving democracy's current problems: the restricted scope of widespread machine learning techniques, and the mainstream game-theoretic design of agents. Machine learning's most successful techniques (classifiers, deep learning...) seem to be less adapted to help improving low-frequency but high-stake decisionmaking such as elections. Corpora of past decisions comes in the form of history books, which are hard leaning material for a machine learning algorithm. Moreover, assessing the fitness or the quality of an election result-the basic requirement to feedback a learning automated agent-is a research question in itself, and heavily relies on the values that are being (again, collectively) adopted. If we then turn to research in multi-agent systems, we see that its modern foundations lie in rational decision theory and game theory [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF][START_REF] Wooldridge | An introduction to multiagent systems[END_REF], i.e., on self-interested agents. Democracy certainly features many "egoistic" aspects, but this is not the first word that we would use to characterise a democratic process.

The ideal Athenian dream of direct democracy is often idealised and aimed at by many techno-friendly citizens, including a number of researchers. Such a system seems however to suffer foundational Direct democracy suffers of low participation and cognitive load limitations problems such as a very low voter participation, often skewed towards the extremes of the political spectrum, eroding the legitimacy of its decisions. My proposal is to assess the feasibility of voting avatars, autonomous agents that take the role of citizens in a direct democracy, voting on their behalf on the hundreds of questions on the daily political agenda [START_REF] Grandi | Agent-Mediated Social Choice[END_REF]. In the same way as autonomous Autonomous agents acting as voters' proxies in high-stakes/highfrequency collective decisions agents are taking the lead in finance, trading, and eCommerce in general [START_REF] Rajdeep | Computational-Mechanism Design: A Call to Arms[END_REF][START_REF] Feigenbaum | Computational challenges in e-commerce[END_REF][START_REF] David | On AI, Markets and Machine Learning[END_REF][START_REF] Sierra | Agent-Mediated Electronic Commerce[END_REF], the time might be ripe for the development of autonomous agents acting as proxies of human voters in collective decision-making, and the design of voting rules specific to this new user set, making high-stake collective decisions with high-frequency a reality.

Leaving aside the practical problems of privacy and security, such a project requires the construction of autonomous agents that are able to understand the reasons behind a citizen's political vote or view, to be able to take part in collective decisions on her behalf, the development of voting and debating procedures to be used by autonomous artificial proxies, and the design of computational-friendly mechanisms for modelling social influence and the diffusion of opinions. Some such techniques have been already discussed at length in this thesis, with the main challenge in my opinion being the development of voting agents that are not purely game-theoretical. An initial step in this direction could be the study of goal-based agents in voting, i.e., agents whose rationality is based on satisfaction rather than maximisation, as in our research on goal aggregation presented in Chapter 4.

To move further, a compact language for principles should be devised, together with inference mechanisms to decide which alternative is closer to such principles and decide the voting behaviour of the autonomous agents. Research in ethics and moral decisions in artificial intelligence is quite close and can suggest interesting starting points [START_REF] Conitzer | Crowdsourcing Societal Tradeoffs[END_REF][START_REF] Loreggia | Modelling Ethical Theories Compactly[END_REF]. A related approach has been taken by Stirling [START_REF] Stirling | Theory of Social Choice on Networks[END_REF], who defines individual preferences as statements that are conditional on the choices of some of the other voters. His results assume a numerical representation of preferences, but his model of collective satisficing provides one of the few examples of collective decision-making that is not based on optimisation. One further idea is not to abandon the game-theoretical view at all, but let the voting avatars play an assistance game, or inverse cooperative reinforcement learning game [START_REF] Hadfield-Menell | Cooperative Inverse Reinforcement Learning[END_REF][START_REF] Ng | Algorithms for Inverse Reinforcement Learning[END_REF], in which the voting avatar would be able to learn which fitness function to use in its implementation from observing the behaviour of the voter.

There are multiple ethical questions that this research agenda will indirectly raise. First, the actual use of voting avatars in collective decisions such as elections requires a level of security, data protection, and privacy which current techniques are not yet able to handle (but research is advancing fast in this area, as witnessed by recent applications of cryptography to collective decision-making [START_REF] Chaum | Random-Sample Voting[END_REF] or the governance of electronic institutions [START_REF] Kotsialou | Using Distributed Ledger Technology for Shareholder Rights Management[END_REF]). Second, the problem of voteselling would need to be carefully checked at the moment of prototyping. Last but not least, societies will have to decide whether foundational aspects of democracy should be left to autonomous agents which, albeit acting on behalf of a human, will still have a large degree of autonomy. Ongoing debates on ethical and societal consequences of artificial intelligence are preparing the ground for these decisions.

Figure 2 :

 2 Figure 2: A set of agents is linked by a network of trust, or mutual influence.Each agent has a private and partial knowledge of the situation, and a private goal or preference. Agents exert their influence by expressing opinions, entering a process of opinion diffusion which results in a final vote.

Example 2 . 1 . 3 .

 213 Consider a simple influence network with n = 4 agents and |A| = 3 alternatives in the figure below.

maj

  In the profile described above four agents A, B, C, and D, are taking a binary collective decision, with the possible direct votes being Yes, No or abstain, denoted with * . Voter A expresses a multiagent

  Call r the restaurant (or any service-provider), which is evaluated by a finite non-empty set of individuals C = {c 1 , . . . , c n }, called customers. Customers are connected in a network E ⊆ C × C, which we assume to be symmetric and reflexive. N(c) denotes the neighbourhood of customer c in E. The evaluations of the customers are represented as a function eval : C → Val ∪ { * }, where Val ⊆ [0, 1] is a set of evaluation values (e.g., a discrete scale or the whole [0, 1] interval) and * is the symbol for no evaluation. Let V ⊆ C be the set of customers that expressed an evaluation different than * , and call them voters. The objective rating of the restaurant ignores the network and averages over all evaluations received: O-rating(eval) = avg c∈V eval(c), Personalised ratings, on the other hand, average only over one customer's neighbours: P-rating(c, eval) = avg k∈N(c)∩V eval(k)

  Formally, r P (σ) = u σ P -u 0 P (an equivalent definition is given for r O ). We illustrate the definitions of the model in the following examples: Example 2.4.1 (O-rating). Consider the three situations in Figure 3, illustrating the effect of a single bribe of 0.1 on each of the customers. The top-left (σ A ), top-right (σ B ) and bottom (σ C ) strategies, although costing the same (0.1) to the restaurant induce different returns. In particularu σ A O = u σ B O = 3 × 0.65 -0.1 = 1.85 while u σ C O = 3 × 0.43 -0.1 = 1.2.Observe how the first two give a positive change to the O-rating while the third one does not. Hence, σ A and σ B are profitable strategies while σ C is not.

Figure 3 :

 3 Figure 3: The effect of bribing different customers with the same amount of 0.1 under O-rating and P-rating. The bribed customer is in grey.Customers' evaluations are reported above each node.

Proposition 2 . 4 . 2 .

 242 Let σ be an efficient strategy s.t. |B(σ)| = 1, and let c be such that σ( c) = 0. Then r P (σ) < |N( c)|.

  1 a b c d w Voter 2 b a c d w Voter 3 w c a d b Voter 4 d w a b c

Figure 4 :

 4 Figure 4: Diagrams for 2-by-2 GS-Games. Each vertex is a strategy profile for the two players, with s being the sincere strategy and i the insincere one. Vertical arrows indicate the preference of the first player, and horizontal ones those of the second player on the vote outcome. NE are denoted by thicker dots.

Figure 5 :

 5 Figure 5: Increase in Condorcet efficiency for different voting rules, comparing the non-iterated profiles with the second-choice, best update, 2 and 3-pragmatists dynamics. The results are obtained with 10 voters and 25 candidates-simulating a Doodle vote-averaging over 10.000 profiles obtained with the Polya-Eggenberger urn model with 10% correlation.

Figure 7 :

 7 Figure 7: Screenshot of the voting interface on the Itero platform.

Figure 8 :

 8 Figure 8: Screenshot of the results of previous rounds of an iterative election on the Itero platform.

Proposition 4 . 2 . 2 (

 422 [START_REF] Novaro | Goal-based voting[END_REF]). There is no rule F that satisfies model-unanimity and is weakly resolute.Let us now consider the adaptation of a classical-and heavilycriticised-axiom from social choice theory. Let D m = {(a, b) | a, b ∈ We adapt the classical independence axiom to goal-based voting N and a + b 2 m } and C = {{0}, {1}, {0, 1}}.

  , EMaj, and 2sMaj is PP-hard Theorem 4.2.2 ([126]). Winner determination for TrueMaj, Emaj, and 2sMaj is PP-hard.

Figure 9 :

 9 Figure 9: Mean error of the B * α -rule on incomplete profiles in terms of score.

  Figure 1: A multiagent system composed of voting agents taking a collective decision on candidate alternatives A, B, C. Each agent has preferences over the outcome of the vote, can express its opinion with voting ballots, and has partial knowledge about its environment.The voting rule is not represented, but in this case associates a winning candidate with every configuration of voting ballots. The arrow between agents are visualisations of the private knowledge of the agents, and in Chapter 2 they will also be used for representing social influence.

	Agent 1
	Preference: A > B > C
	Ballots: top 2 candidates
	Knowledge: agent 3's preferences
	Agent 4 …	Agent 5 …	… Agent 3	Knowledge: agent 1 and 3 preferences Ballots: top 2 candidates Preference: A > C > B Agent 2

  2.4-that satisfy desirable properties. I started this line of research at my arrival at IRIT in Toulouse, beginning a fruitful collaboration with Emiliano Lorini and Laurent Perrussel that is still ongoing. The results presented in this chapter include the work of two PhD students (Arianna Novaro and Rachael Colley) and three Master students (Sirin Botan, Claire Pillet, and James Stewart) whom I co-supervised in Toulouse. This research is also the result of international collaborations with Markus Brill from TU Berlin, Edith Elkind from Oxford University, Ulle Endriss from the

	social choice and social networks
		discrete time
	Agent A
	Beliefs: …
	Goals: …	Agent B
		Beliefs: …
		Goals: …
		Agent C
	Agent D	…
	…
		Opinion diffusion

  Let turn : N → 2 N indicate at each point in time the set of

	tion over models of a propositional formula, or a belief merging op-
	erator.
	Opinion diffusion is then modelled as an iterative process in dis-
	crete time. A discrete-time
	agents updating. Let B t i be the opinion of agent i at time t ∈ N, and:	iterative process
	The opinion of the
	influencers are aggregated	sider a collection of functions F i : X n → X for each n ∈ N and for each i ∈ N. The dependency on n accounts for different possible sizes of the influencers set. Notable examples of aggregation functions are
		the majority rule over binary opinions, a judgment aggregation func-

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	. . . . . . . . . . . . . . . . . . . . . . . . . . (s, s) (i, s)	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • (s, i) (i, i)	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • (s, s) (i, s) (s, i) (i, i)	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (s, s) (s, i) • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • (i, s) (i, i)
	(i)		(ii)	(iii)
	. . . . . . . . . . . . . . . . . . . . . . . . . . (i, s) (s, s)	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • (i, i) • (s, i)	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • (s, s) (i, s) (s, i) (i, i)	. . . . . . . . . . . . . . . . . . . . . . . . . . (s, s)	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •
	(iv)		(v)

. . . . . . . . . . . . . .

  Performance of the reinforcement learning agents in terms of Condorcet efficiency, with 9 voters and 7 candidates. Averaged over 7331 profiles with a Condorcet winner generated with the Polya-Eggenberger urn model with 10% correlation.

		1
		0.95
	Condorcet Efficiency	0.8 0.85 0.9
		0.75
		0.7
		0	50	100	150	200	250	300
					Number of Iterations
	One Round Plurality Copeland Borda STV Iterative 3 Pragmatist
	Iterative Best Response Iterative Learning Optimistic Greedy
	Figure 6:
	Reinforcement
	learning agents are able to reach good		in a very simple setting of iterated plurality elections, with minimal
	collective decisions
	in iterative voting

  Consider the following CP-net, built on our running Example 4.0.1. Ann, one of the users of the automated travel planner, has the following preferences: she prefers going to the beach than not going, but if she goes to the beach she prefers a stop-by at the hotel and not going to the museum. She would also like to do the guided tour of the city. This can be represented compactly as follows: let T indicates not doing the guided tour,

		Ceteris paribus
	of one of the features of the domain to another value, all other things being equal. Such statements can be represented compactly in a much-studied language called CP-nets [12] to express partial orders over a	preferences compare outcomes that differ on one variable only
	combinatorial domain.
	Example 4.3.1.

and accordingly for three other binary variables B, H, M. The two variables B and T are the parent variables for Ann, since her preference on these two activities do not depend on the other activities. We can therefore write T > T and B > B. The two variables H and M depend on the value of B, thus: B : H > H, B : M > M. Recall that preferences are interpreted all other things being equal, so the previous statements induce the following partial order over travel plans:

https://whale.imag.fr www.spliddit.org www.preflib.org Some of these topics are discussed at lenght in a recent book edited by Ulle Endriss[START_REF] Endriss | Trends in Computational Social Choice[END_REF]. The most recent advances are summarised in the proceedings of the Dagstuhl seminar on Application-Oriented Computational Social Choice[START_REF] Grandi | Application-Oriented Computational Social Choice (Dagstuhl Seminar 19381)[END_REF].

This example is based on Example

[START_REF] Baumeister | Judgment Aggregation[END_REF].1 in the thesis of Novaro[START_REF] Novaro | Goal-based voting[END_REF].

https://www.irit.fr/scone

An anonymous reviewer correctly pointed out that the existence of a clock would still make the process synchronous. For the sake of uniformity with previous publications I am still using the old but imprecise terminology.

www.technologyreview.com/s/538866/the-social-network-illusion-\ that-tricks-your-mind/

www.irit.fr/~Umberto.Grandi/iterative

A vision I sketched in a position paper[START_REF] Grandi | Agent-Mediated Social Choice[END_REF], also shared by Cesar Hidalgo in his recent TED talk (www.ted.com/talks/cesar _ hidalgo _ a _ bold _ idea _ to _ replace _ politicians).

https://itero.irit.fr/

The names used here are different than in the published version[START_REF] Grandi | Restricted Manipulation in Iterative Voting: Condorcet Efficiency and Borda Score[END_REF].

With the notable exception of the local dominance model of strategic voting[START_REF] Meir | A localdominance theory of voting equilibria[END_REF].

https://itero.irit.fr/

https://whale.imag.fr/

This example is inspired by the travelling group problem studied by Klamler and Pferschy[START_REF] Klamler | The traveling group problem[END_REF].

In contrast with the planning literature, the order in which the activities are executed is not relevant in our model. We assume that activities can be done in any order or will follow a predetermined order.

A simple example: an autonomous agent who needs to decide about the most probable of two events described by two propositional formulas has to solve an instance of MAJ-SAT which is a PP-complete problem.

See e.g. initial work by Talmon et al. presented at the Workshop of Liquid Democracy in Toulouse,

(www.irit.fr/scone/events/workshop-on-liquid-democracy/).

Sentiment analysis Beach

Majority rule Museum

With 30 participants out of 35 talking positively about going to the beach, against 20 for the museum, a sentiment analysis application would conclude that a trip to the beach is the right option to recommend to this group. How-The most popular alternative is not necessarily the best choice ever, when the group is presented with this choice, or maybe when they are already laying under the sun discussing about the possible travel options for the day, they will realise that 25 of them would have preferred going to the museum, with only 10 of them choosing a day at the beach.

The classical Borda rule-and all scoring rules in general-have been shown to be particularly flexible in adapting to non-conventional input from voters (see, e.g., the adaptations of the Borda rule to partial orders [START_REF] John Cullinan | A Borda count for partially ordered ballots[END_REF] and bucket orders [START_REF] Fagin | Comparing partial rankings[END_REF]). In our paper we chose to adapt the Borda rule to the kind of input that can be extracted from textual information via sentiment analysis techniques. First, we define a unified structure called SP-structure which can represent both polarity and comparative statements over the set of alternatives. Then,

A generalisation of the Borda rule to deal with both polarity and comparisons

we assign a score to each alternative depending on its polarity as well as on the number of alternatives that are preferred to it. We name such rule B * α -rule, with α being the vector of scores. This rule generalises both classical sentiment analysis aggregation (which would correspond to Approval voting over the alternatives marked with positive polarity) and the Borda rule: Theorem 4.4.1 ([77]). If a profile of SP-structures S is purely preferential, then for all α we have that B * α (S) = Borda(S). If a profile S is purely sentimental, then for all α such that α 2 = α 3 we have that B * α (S) = Approval(S).

We also analyse the axiomatic properties of the B * α -rule, we show that it runs in polynomial time in the size of the input (a profile of SP-structures), and that its communication complexity is Θ(nm 2 ) where n is the number of agents and m the number of alternatives (for comparison, the communication complexity of the Borda rule is Θ(nm log(m))). The social-choice specialist will be reminded of the Fallback voting rule [START_REF] Brams | Voting Systems that Combine Approval and Preference[END_REF], in which voters express a set of ranked and approved candidates. This rule can give different results than our B * α -rule, which is tailored to handle incomplete extracted data rather than an elicited voting ballot.

We also conduct and empirical analysis to assess the performance of the B * α -rule in incomplete domains. To do so, we generated profiles of SP-structures, computed the result of the B * α -rule, and then deleted