Rank aggregation aims at producing a single ranking from a co llection of rankings of a fixed set of alternatives. In social choice theory (e.g., Moulin 1991), where the alternatives are candidates to an election and each ranking represents the preferences o f a voter, aggregation rules are called Social Welfare Functions (SWFs). Apart from social choice, rank aggregation has prov ed useful in many applications, including preference learning (Cheng a nd H ullermeier, 2009; Cl emen con et al., 2018), collaborative filtering (Wang et al., 2014), genetic map creation (Jackson et al., 2008), similarity search in databases systems (Fagin et al., 2003) and design of web search engines (Altman and Tennenholtz, 2008; Dwork et al., 2001). In the fo llowing, we use interchangeably the terms "input rankings" and "preferences", "output rank ing" and "consensus ranking", as well as "alternatives" and "'candidates". The well-known Arrow's impossibility theorem states that t here exists no aggregation rule satisfying a small set of desirable properties (Arrow, 1950). In the absense of an "ideal" rule, various aggregation rules have been proposed and studied. F ollowing Fishburn's classification (1977), we can distinguish between the SWFs for which the out put ranking can be computed from the majority graph alone, those for which the output ranking can be computed fro m the 1 Table 1: Results of setwise contests in Example 1. set c

We consider a voting setting where candidates have preferences about the outcome of the election and are free to join or leave the election. The corresponding candidacy game, where candidates choose strategically to participate or not, has been studied by Dutta et al. [6], who showed that no non-dictatorial voting procedure satisfying unanimity is candidacy-strategyproof, that is, is such that the joint action where all candidates enter the election is always a pure strategy Nash equilibrium. In [7] Dutta et al. also showed that for some voting tree procedures, there are candidacy games with no pure Nash equilibria, and that for the rule that outputs the sophisticated winner of voting by successive elimination, all games have a pure Nash equilibrium. No results were known about other voting rules. Here we prove several such results. For four candidates, the message is, roughly, that most scoring rules (with the exception of Borda) do not guarantee the existence of a pure Nash equilibrium but that Condorcet-consistent rules, for an odd number of voters, do. For five candidates, most rules we study no longer have this guarantee. Finally, we identify one prominent rule that guarantees the existence of a pure Nash equilibrium for any number of candidates (and for an odd number of voters): the Copeland rule. We also show that under mild assumptions on the voting rule, the existence of strong equilibria cannot be guaranteed.

We consider multi-agent systems where agents' preferences are aggregated via sequential majority voting: each decision is taken by performing a sequence of pairwise comparisons where each comparison is a weighted majority vote among the agents. Incompleteness in the agents' preferences is common in many real-life settings due to privacy issues or an ongoing elicitation process. In addition, there may be uncertainty about how the preferences are aggregated. For example, the agenda (a tree whose leaves are labelled with the decisions being compared) may not yet be known or fixed. We therefore study how to determine collectively optimal decisions (also called winners) when preferences may be incomplete, and when the agenda may be uncertain. We show that it is computationally easy to determine if a candidate decision always wins, or may win, whatever the agenda. On the other hand, it is computationally hard to know wheth er a candidate decision wins in at least one agenda for at least one completion of the agents' preferences. These results hold even if the agenda must be balanced so that each candidate decision faces the same number of majority votes. Such results are useful for reasoning about preference elicitation. They help understand the complexity of tasks such as determining if a decision can be taken collectively, as well as knowing if the winner can be manipulated by appropriately ordering the agenda.

In many practical contexts where a number of agents have to find a common decision, the votes do not come all together at the same time. In such situations, we may want to preprocess the information given by the subelectorate (consisting of the voters who have expressed their votes) so as to ``compile'' the known votes for the time when the latecomers have expressed their votes. We study the amount of space necessary for such a compilation, as a function of the voting rule, the number of candidates, and the number of votes already known. We relate our results to existing work, especially on communication complexity.