Collective Decision Making under Incomplete Knowledge: Possible and Necessary Solutions

1 Introduction

In the last 20 years there has been a significant interest on collective decision making within the AI community, with the aim of designing and supporting new ways for agents to make group decisions, in a more flexible and realistic way than what classical social choice methods would allow.

One reason why collective decision making in modern applications has to be flexible is that preferences can often not be assumed to be elicited entirely and in a single pass. This leads to viewing collective decision making as an interactive process, and ask questions such as: when agents' preferences are partly known at some stage, should we simply wait, or do we know the outcome already, or at least part of it?

Beyond preferences, incomplete knowledge can also bear on the mechanism itself, for various reasons (including reducing the impact of strategic behaviour).

For both sources of incomplete knowledge, a notion that has been used in several subfields of computational social choice is what I will call possible and necessary solutions. It has been used in voting under the terminology possible and necessary winners, and more recently in fair division and coalition structure formation.

This survey, and the chapter Incomplete Information and Communication in Voting [Boutilier and Rosenschein, 2016], in the Handbook of Computational Social Choice, complement each other. The handbook chapter has a much wider scope, as it covers more generally information and communication issues in voting. Its Section 10.3.1 covers possible and necessary winners in voting, with much less details and structure than this survey. Also, the handbook chapter deals only with voting, and not with other social choice domains.

As most of the work I am about to survey bears on incomplete preferences, in each section I start by this setting, and consider incompletely specified mechanisms later.

2 Possible and NecessaryWinners in Voting 2.1 Definitions

An election consists of a set N of n agents, a set C of m candidates, and a preference profile R = (≻1, . . . ,≻n), where each ≻i is a linear order 1 over C, called a preference relation or vote. A property F (of candidates) maps R to a subset of C. If F(R) is always nonempty then F is a voting rule; and if F(P) is always a singleton then it is a resolute voting rule. An example of a property is 'being a Condorcet winner' (CW) : c ∈ C is a CW is for any c′ ∈ C \ {c}, a majority of voters prefers c to c′ , that is, |{i, c ≻i c′ }| > n2 . An example of a voting rule is plurality (Fplu): it outputs candidates ranked with largest plurality score, defined as the number of votes in whih they are ranked on top. A voting rule can be made resolute by composing it with a tie-breaking mechanism, usually a priority relation ▷ over C. For instance, if R = (a≻b≻c, a≻b ≻c, b≻c ≻ a, b≻c ≻a, c≻a ≻b) then the CW property outputs the empty set, the plurality rule outputs {a, b}, and resolute plurality with tie-breaking prior-

ity a ▷ b ▷ c (denoted by Fplu,a▷b▷c) outputs {a}.

A natural model of incomplete information about votes consists in assuming that only a partial order for each voter is known. 2 A partial (or incomplete) vote Pi is a strict partial order (an irreflexive and transitive relation) over C. A (complete) vote ≻i is a completion of Pi if it is contains Pi. A partial profile P is a collection (P1, . . . , Pn) of incomplete votes. A (complete) profile R = (≻1, . . . ,≻n) is a completion of P if for all i, ≻i is a completion of Pi.

Given a candidate c ∈ C, a voting rule or property F and an incomplete profile P, c is a possible winner (for P and F) if there exists a completion R of P such that x ∈ F(R);

1 We stick here to rules defined from ordinal preferences, which is a usual view in voting and more generally in social choice.

2 This is nevertheless not the only possibility. See Section 2.4.

and c is a necessary winner if for every completion R of P, x ∈ F(R) [Konczak and Lang, 2005].

If F is a voting rule then any necessary winner is a possible winner, and there is at least one possible winner. If moroever F is resolute, then there is at most one necessary winner.

Example 1. We take n = m = 3, C = {a, b, c}. Voter 1 only specifies that a is her top candidate. Voter 2 only says that she prefers b to a. Voter 3 reports a complete preference relation. Figure 1 shows the partial profile (left) and its six completions (right). (We note abc instead of a ≻ b ≻ c, etc.)

We show below the winners for all completions of P , for the Condorcet winner property, irresolute plurality, and resolute plurality with tie-breaking priority b ▷ a ▷ c.

• a and c are possible Condorcet winners. There is no necessary Condorcet winner.
• for irresolute plurality: a, b and c are possible winners, and c is a necessary winner.
• for Fplu,b▷a▷c: b and c are possible winners, and there is no necessary winner.

If we further learn that voter 2 prefers a to c, only completions (abc, bac, cab) and (acb, bac, cab) remain; now a is a necessary CW and b a necessary winner for Fplu,b▷a▷c.

In the case of a resolute rule, the existence of a necessary winner is a sufficient and necessary condition for the elicitation process to be considered terminated (as there is enough information for the outcome to be known). This question has been considered first in [Conitzer and Sandholm, 2002] and [Walsh, 2008]. 3 [Ding and Lin, 2013] go further by determining which are the relevant queries voters should be asked.

2.2 Computation

Because the number of completions of a partial profile is exponential, deciding whether a candidate is a possible or a necessary winner is not guaranteed to be easy, and indeed it os often hard. The complexity of these decision problems for a variety of rules is addressed first in [Xia and Conitzer, 2011]

3 In the case of irresolute rules, whether the elicitation process is considered terminated once some necessary winner has been found depends on the context.

for a variety of rules, and further in [Betzler and Dorn, 2010; Baumeister and Rothe, 2012] for the specific case of positional scoring rules.

The parameterized complexity of the problems is initiated in [Betzler et al., 2009], where the relevant parameters are the number of candidates, number of voters, and degree of incompleteness (number of undetermined pairs in votes). Kernelization complexity results with number of candidates as parameter are given in [Dey et al., 2016]. The impact of the degree of incompleteness is investigated further in [Dey and Misra, 2017], who determine, for several rules, the smallest number of undetermined pairs for which the possible winner problem remains hard.

2.3 Special Cases

Missing Votes

A partial profile P = (P1, . . . , Pn) is of the missing voters (MV) type if for every i, either Pi is either complete or empty. Without loss of generality, let us renumber the voters such that Pi is complete for each i ≤ k and empty for i > k.

There are at least two interpretations of these MV profiles. Under the strategic interpretation, {k + 1, . . . , n} is a coalition of manipulating voters who, knowing the votes of {1, . . . , k}, can coordinate and turn the outcome to their advantage. These two problems are defined in [Bartholdi et al., 1989]: for a resolute rule F, given the votes of {1, . . . , k}, coalition {k + 1, . . . , n} has a constructive (resp. destructive) manipulation for (resp. against) c ∈ C if there is a way for them to vote so that c is the winner (resp. so that c is not the winner). Clearly, in a MV profile, c is a possible winner if and only if the missing voters have a coalitional manipulation for c, and a necessary winner if and only if they have no destructive manipulation against c.

These definitions assume that the manipulating voters have full knowledge of the nonmanipulators' votes. This assumption is relaxed in [Conitzer et al., 2011], who assume nonmanipulators' votes to be partial orders and define a dominating manipulation as a collection of votes by the manipulators making the winner preferable (to them) to the winner obtained with truthful votes. In a similar setting, [Dey et al., 2018] study a notion of weak manipulation that corresponds to the possible winner problem given k partial votes and n-k empty votes (see Section 2.4 for further discussion).

Under the temporal interpretation, votes come in an asynchronous way. At time t, the set of voters who have sent their votes is V (t); we usually assume V to be monotonic 4 and as soon as we have necessary winner, we can stop waiting for more votes to come. This situation occurs typically in date-finding polls. In such a context, during the elicitation process voters can be asked to block the dates mentioned in the poll, and identifying the possible winners before the end of the elicitation process allows them to block less dates.

4 Although one may argue that there may be cases where some voters can cancel their vote after some time.

Example 2. F is the irresolute plurality rule. At time t, let st(x) be the plurality score of x ∈ C. The number of voters who have already voted is |V (t)| = ∑x st(x). x is a necessary winner if st(x) ≥ maxy̸=x st(y) + n - |V (t)| and a possible winner if st(x) + n - |V (t)| ≥ maxy̸=x st(y).

This assumes that the set of voters is fixed from the beginning. When it is not, all-or-nothing notions no longer make sense; one can try instead to identify candidates who are winners with a large enough probability [Dey et al., 2017].

Missing Candidates

A partial profile is of the missing candidates (MC) type if the partial votes consist of complete rankings over some subset of candidates (the same for all voters), with no information at all on the other candidates. Concrete situations include polls about meeting dates where some dates that were initially considered impossible (for instance because the meeting room was thought to be unavailable) have become possible in the meantime, or applicants to a job that are known only after the first set of applicants have been interviewed and ranked by the members of the committee.

A partial profile of the missing candidates type

Clearly, for any reasonable voting rule, these new candidates are possible winners. The question is which of the initial candidates are possible winners, that is, can still win after we learn how the voters compare the new candidates to them.

Example 3. n = 12. {a, b, c} are the initial candidates and y the only new candidate. The rule is plurality with tie-breaking priority a ▷ b ▷ c ▷ y. The initial plurality scores (before preferences about y are known) are a : 5, b : 4, c : 3. Clearly, a can still win (for instance if noone ranks y first); b will win provided that at least two (and at most three) voters who used to rank a first now decide to rank y first (third column); c cannot win, because to make the scores of a and b lower than its, we would need too many voters ranking y first, and y would become the winner (rightmost column).

If there are two new candidates y1, y2 instead of one, then c is a possible winner if it has priority over y1 or over y2.

Characterizing possible winners in this specific context has been considered for positional scoring rules [Chevaleyre et al., 2012] and a few other rules [Xia et al., 2011].

Truncated Ballots

Asking voters to rank all candidates is often too much of a communication burden on them. To limit the amount of elicitation, we may ask them to rank only their top k candidates, for some k. This leads to a partial profile of the top-k type:

A partial profile of the top-k ballots type (here k = 2)

A possible variation is to allow each voter i to choose their own ki. Another one consists in double-truncated ballots: each voters reports their k+ top candidates and their bottom k-. Truncated ballots have been considered in quite many papers; those that focus explicitly on possible and necessary winners are [Baumeister et al., 2012a; Kalech et al., 2011; Ayadi et al., 2019], the latter two in the context of designing low-communication protocols. A protocol studied in [Kalech et al., 2011] starts by eliciting the top-1 ballots, then top-2, and so on, until there is a necessary winner; in practice, this "next-best queries" protocol saves a lot of communication.

Incomplete Lists

A partial profile is of the incomplete lists (IL) type if the voters rank only some candidates, namely those they know (the films they have seen, the candidates they have interviewed etc.) The crucial difference with truncated ballots is that here the candidates that do not appear in a ranking can be ranked anywhere and not necessarily below those that appear. The crucial difference with the "missing candidates" setting is that the ranked and the missing candidates are voter-dependent.

This situation occurs in information retrieval, when one has to merge the ordered lists of documents returned by different search engines, and in systems where individuals rank restaurants, films etc. However, unlike other types of partial profiles, the IL type is less suited to the possible and necessary winner notions: the information is generally too incomplete so that typically, almost all candidates are possible winners. Dealing with IL profiles calls for either the counting version of possible winners (cf. Subsection 2.4), or to specific aggregation methods: for instance, [Caragiannis et al., 2015] aggregate such incomplete lists in the context of peer grading in Massive Online Open Courses, where each student ranks a small number of other students' exams.

Cloning

Assume we know the voters' preference relations over C, and that now we add p clones a1, . . . , aq of candidate a ∈ C. Let C(a) = {a0 = a, a1, . . . , aq}. The voters' preference relations ≻′i over the new set of candidates C ∪ {a1, . . . , aq} are such that, for each i, (1) for each aj ∈ C(a) and each x ∈ C \ C(a), aj ≻′i x if and only if a ≻i x and x ≻′i aj if and only if x ≻i a; (2) for each x, y ∈ C \ C(a), x ≻′ y if an only if x ≻ y. It is not possible to predict how voters will rank the elements of C(a) with respect to one another. We obtain a partial profile P of the cloning type:

A resolute rule F is clone-proof if whenever the winner in the initial profile (without clones) is x ̸= a, the only possible winner in P is x, and whenever the winner in the initial profile is a, the possible winners in P are all in C(a). When F is not clone-proof, determining the possible winners can be challenging; this is studied in [Elkind et al., 2011].

2.4 Variants and Extensions

More quantifier alternations. Possible and necessary winners correspond to simple existential and universal quantification, or, in epistemic logic terms, to possibility and knowledge: x is a necessary winner if x is known to be a winner (Kwinx), and x is a possible winner if x is not known not to be a winner (¬K¬winx), where possible worlds corresponds to profile completions. The notion of strong manipulation [Dey et al., 2018] uses one more level: given k partial votes, the remaining n - k voters have a strong manipulation for x if there exists a way for them to cast their votes so that for any completion of the first k votes, x is a winner. More formally, given an incomplete profile P and a partition (N1,N2) of the voters, x is a ∃N1∀N2-winner for F if there is a completion R1 = (≻i, i ∈ N1) of (Pi, i ∈ N1) such that for any completion R2 = (≻i, i ∈ N2) of (Pi, i ∈ N2), x ∈ F(R1,R2). Other quantifier alternations could be considered.

Probabilistic possible winners. If the incompleteness of the profile is significant, determining possible winners can be disappointing: typically, all candidates, or almost all, are then possible winners. In such a case one may instead want to count completions. [Bachrach et al., 2010] define the winning probability of a candidate c as the proportion of completions for which c is a winner; they show that although computing the exact winning probability is hard, giving a good additive approximation of it by sampling is tractable for some rules. [Kenig and Kimelfeld, 2019] obtain results for multiplicative approximation ratios, and beyond the uniform distribution over profile completions, they consider a more realistic family of distributions: the repeated insertion model. Finally, [Hazon et al., 2012] consider a different uncertainty model about votes: instead of a partial order, each voter comes with a probability distribution over complete votes.

Resoluteness with incomplete preferences. As said above, in some cases there are typically too many possible winners and we may want to define resolute (or at least, more resolute) rules from incomplete profiles. A first way to resoluteness, followed in [Lu and Boutilier, 2011; Benabbou et al., 2016; Lu and Boutilier, 2020] is to select the minmax regret winner, that is, the one which is closest to optimal in the worst case. A necessary winner is also a minmax regret winner but, perhaps unexpectedly, a minimax regret winner may not be a possible winner [Lu and Boutilier, 2011]. Another way to resoluteness is to define rules from incomplete profiles as maximum likelihood estimators [Xia and Conitzer, 2011].

Other models of uncertainty. [Shiryaev et al., 2013] consider a type of incomplete knowledge about votes which is generally not representable by partial orders: a 'default' (or 'reference') vote of each voter is known, but the voter may report a vote that is within a maximal number of swaps away from her default vote. A robust winner is then like a necessary winner, but for this type of incomplete knowledge. Both this model, and possible and necessary winners, are specialisation of swap bribery [Elkind et al., 2009].

In the specific case of approval voting, [Barrot et al., 2013] assume that voters' preferences are fully known, and that incomplete knowledge bears on the approval ballots they report. Assuming these ballots are sincere (i.e., a ballot consists of all candidates above some 'threshold' candidate), they characterize and compute the possible (sets of) approval winners. [Benabbou and Perny, 2016] also consider possible approval winners, in a group knapsack context where a common set of objects is to be selected.

Voting and databases. [Kimelfeld et al., 2018] relate possible and necessary winners to possible and necessary answers in incomplete databases, and enrich the possible and necessary winner setting with conjunctive database queries: given an incomplete profile and some attributes describing the candidates, they consider questions such as the existence of a set of possible winners satisfying some conjunctive query.

2.5 Incomplete Knowledge on the Mechanism

Instead of bearing on the votes, incomplete knowledge can bear on some parameters of the voting rule, such as:

1. the voters and candidates that take part to the election [Wojtas and Faliszewski, 2012];
2. the voters' weights [Baumeister et al., 2012b];
3. the order in which voters vote, under a simple strategic behavioural assumption [Gaspers et al., 2014];
4. the initial position (or seeding) of candidates in knockout tournaments (also called voting trees) [Aziz et al., 2018; Mattei et al., 2015];
5. the scoring vector for positional scoring rules [Viappiani, 2018].

3 Beyond Voting

The epistemic principle at work for the possible winner problem (consider all possible completions of partial preferences as possible worlds and quantify over them) naturally extends to more social choice settings, and even beyond social choice.

3.1 Partial Tournaments

In [Aziz et al., 2015a], the input is a partial tournament (a directed asymmetric graph) over C, or a partial weighted tournament (a weighted directed graph w(., .), such that for all a, b ∈ C, w(a, b) + w(b, a) ≤ n, where n is independent from a and b). A partial [weighted] tournament may come from a partial profile 5 , or can be an object on its own, such as a set of partial outcomes in a sports tournament. Given a [weighted] tournament solution S, that maps a [weighted] tournament into a subset of C, c is a possible winner for partial tournament T if there is a complete tournament T ∗ extending T such that c ∈ S(T ∗ ), and a necessary winner for T if for every complete extension T ∗ of T, c ∈ S(T ∗ ). [Aziz et al., 2015a] give computational results results for various voting rules. [Brandt et al., 2018] study the social-choice theoretic properties of these extensions of tournament solutions to incomplete profiles. Earlier work [Lang et al., 2012; Pini et al., 2011] studied voting trees and the Schwartz rule defined from incomplete tournaments. [Yang and Guo, 2017] give a paramaterized study of the complexity of winner determination for partial tournament solutions.

3.2 Fair Division

A fair division problem (of indivisible items) setting consists of a set of agents N = {1, . . . , n}, a set of items O = {o1, . . . , om}, and for each agent i, a preference relation ⪰i over 2O . An allocation π maps each agent to a set of items, such that π(i)∩π(j) = ∅ for i ̸= j. It is is complete if all items are allocated. The quality of an allocation is usually evaluated through some criteria; here we give only these two:

• envy-freeness: π is envy-free if for all i, j, π(i) ⪰i π(j)
• Pareto-efficiency: π is Pareto-efficient if there is no π′ such that (a) π′ (i) ⪰i π(i) for all i, and (b) π′ (i) ≻i π(i) for some i.

Envy-freeness is a fairness criterion while Paretoefficiency and completeness are efficiency criteria. Efficiency and fairness criteria tend to conflict with each other; for instance, the existence of an allocation that is both envy-free and Pareto-efficient (or even complete) is not guaranteed.

When the number of items grows, it becomes unreasonable to ask agents to report a ranking over all subsets of O. A way to avoid this exponential communication burden consists in letting agents express preferences in a compact way, possibly leaving some incompleteness in the reported preference. Especially, they may rank individual items and then extend the preference relation to subsets of items using the responsive extension: given an order ▷ over O, the responsive extension of ▷ to 2O is the smallest (complete) preference relation ⪰ on 2O which is monotonic (if S ⊆ T then T ⪰ S) and weakly separable (if o, o′ ̸= S then S ∪ {o} ⪰ S ∪ {o′ } if and only if o ▷ o′ ). The responsive extension of o1 ▷ o2 ▷ o3 is depicted on the following figure.

5 If a partial tournament T comes from a partial profile P, i.e., if T is the majority graph of P, then the set of possible winners determined from T contains the set of possible winners determined from P (for the same tournament solution). The rule applied to partial tournaments has often a lower complexity than the same rule applied to partial profiles.

Let P = 〈▷1, . . . ,▷n〉 where each ▷i is a ranking over O. From P we derive P ∗ = 〈≻1, . . . ,≻n〉 where each ≻i is the responsive extension of ▷i. T = 〈T1, . . . , Tn〉 is a completion of P ∗ if each Ti is a linear order extending ≻i. Given a fairness or efficiency criterion Γ, an allocation π is

• possibly Γ if there exists a completion T of P ∗ such that π satisfies Γ with respect to T .
• necessarily Γ if for every completion T of P ∗ , π satisfies Γ with respect to T .

For some properties Γ, the characterization of possibly Γ and/or necessarily Γ is easy. For instance, π is necessarily envy-free if for all agents i, j, and all k ≤ |πi|, i prefers his kth best item in πi to the kth best item in πj [Bouveret et al., 2010]. For some other properties, there is no simple characterization. Such characterizations (when they exist) as well as the computation of allocations that satisfy some properties or combination of properties are given in [Bouveret et al., 2010] and [Aziz et al., 2015b]. 6 Finally, Section 4 of [Aziz et al., 2019] characterizes possibly and necessarily Pareto-optimal allocations under responsive preferences.

Example 4.

▷1: a ▷ b ▷ c ▷ e ▷ d ▷ f

▷2: a ▷ d ▷ b ▷ c ▷ e ▷ f

▷3: b ▷ a ▷ c ▷ f ▷ d ▷ e

Because 1 and 2 have the same most preferred item, there is no complete necessarily envy-free allocation, and a fortiori no possibly Pareto-efficient, necessarily envy-free allocation. If 1 leaves, then the allocation π such that π(2) = {a, d, e} and π(3) = {b, c, f} is necessarily envy-free. It is also possibly Pareto-efficient, but not necessarily Pareto-efficient, because in a completion where {c, d, e, f} ≻2 {a, d, e} and {a, b} ≻3 {b, c, f}, π is Pareto-dominated by π′ defined by π′ (2) = {c, d, e, f} and π′ (3) = {a, b}.

Incomplete knowledge can also bear on the mechanism itself. [Aziz et al., 2015c] and [Cechl´arov´a et al., 2017] consider sequential allocation mechanisms where agents pick items in sequence, following a predefined order. In Example 4, if the picking sequence is 123321, 1 picks a, 2 picks d, 3 picks b and c, 2 picks e and 1 picks f. If it is only known that the sequence will be xyzzyx for some permutation xyz of 123, then c is possibly allocated to any agent, a is possibly allocated to 1 or 2, and d is necessarily allocated to 2.

6 [Bouveret et al., 2010] focus on envy-freeness. [Aziz et al., 2015b] also consider proportional fair share, which needs preferences to be expressed by utility functions.

3.3 Hedonic Games

In a hedonic game, agents form coalitions, and have preferences about who is in their coalition. The classical task consists in finding coalitions structures that satisfy some rationality or stability concepts. However, expressing preferences over coalitions needs exponential space. This lead to studying hedonic games under various compact representations. In [Lang et al., 2015], this is done via a generalization of the responsive extension, where an agent partitions other agents between friends, enemies, and neutral agents, and rank friends and enemies. Since the resulting preferences over sets of agents are incomplete, concepts are modalized: given a concept X, a coalition structure is possibly X if it satisfies X for some completion of the partial profile. The characterizations and complexity results in [Lang et al., 2015] have been complemented by those in [Kerkmann and Rothe, 2019].

Beyond social choice, possible and necessary solution concepts have also been studied in noncooperative games [Brill et al., 2016].

4 Discussion

A quick look at the bibliography shows that while in years 2005-2015 there was a focus on the classical possible winner problem in voting, in the last 5 years the focus moved to variants and extensions of the model and expanded to other social choice settings.

A key question for future research is the interleaving between reasoning about possible outcomes and eliciting further the agents' preferences. To say it differently: how can identifying possible and necessary winners help in making the decision quicker? The existence of a necessary winner is a safe stopping criterion for the elicitation process, but before this point is reached, how can the identification of possible winners help? Removing necessary losers is generally not a good idea, as it could change the result; but sometimes removing some of them is safe (see e.g., [Ayadi et al., 2019] for the special case of the STV rule).

One may also wonder if other meaningful classes of incomplete preferences are yet to be considered. The answer is yes: one should devote some attention to multichotomies (each voter divides candidates in clusters, such as good, acceptable and unacceptable candidates, with all candidates in a cluster being initially incomparable), and multi-attribute preferences with incompletely specified importance over attributes.

Acknowledgements

This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program ANR-19-P3IA0001 (PRAIRIE 3IA Institute).