text: 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.
  @cite_7: Preferences can be aggregated using voting rules. We consider here the family of rules which perform a sequence of pairwise majority comparisons between two candidates. The winner thus depends on the chosen sequence of comparisons, which can be represented by a binary tree. We address the difficulty of computing candidates that win for some trees, and then introduce and study the notion of fair winner, i.e. candidates who win in a balanced tree. We then consider the situation where we lack complete informations about preferences, and determine the computational complexity of computing winners in this case.
summary: The most related work is @cite_7 Like our paper, this considers the computational complexity of determining winners for sequential majority voting. However, they start from an incomplete majority graph which throws away information about individual votes, whilst we start from an incomplete profile.