Let’s Agree to Agree: Targeting Consensus for Incomplete Preferences through Majority Dynamics

1 Introduction

Groups of agents often need to make decisions by finding a consensus between different individual opinions: Among friends, hiring committees and teams of reviewers, as well as multiagent systems, reaching collective consensus is not always easy. Such situations become even less straightforward when agents hold incomplete opinions,which is often the case in real life, due to uncertainty, lack of knowledge, or reduced interest about the issues in question. Consider an example:

Example 1. Five organisers of an online conference must collectively decide about which video-conferencing app to use: AppEar (a), Bridge (b), or C-nnect (c)? Having never used Bridge, two organisers hold no opinion on it, but think that AppEar is better than C-nnect (denoted by a c). Two organisers familiar with AppEar and Bridge find Bridge superior, while one organiser has never heard of any app:

A consensus alternative for these opinions is not obvious. △ In two rapidly growing streams of literature within computational social choice, opinion diffusion and liquid democracy, agents adopt the opinions of their peers during collective decision processes-either directly by embracing them or indirectly by delegating their vote [Bredereck and Elkind, 2017;

∗Contact Author

Brill and Talmon, 2018; Botan et al., 2019; Bloembergen et al., 2019]. In our model, agents also consult their peers, but only about issues on which they initially hold no opinion. Supposing that the group discusses one issue at a time (here the comparison between two alternatives), as commonly happens in practice, all agents with a missing opinion on it will adopt the opinion of the majority. For agents who trust all their peers equally, following majority is indeed the best option, both if they aim at maximising agreement within the group, or at having the highest chances of making the correct decision [de Condorcet, 1785; May, 1952]. 1

Limited by constraints on time and energy, agents do their best to reach consensus locally for each single issue that is being discussed, but the group still targets consensus globally, after all issues have been addressed. Majority dynamics (MD) can help with that, as illustrated below.

Example 1 (continued). Suppose that the discussion starts with AppEar in comparison to Bridge. Since only two organisers have a relevant opinion (that b is better than a), everyone will adopt it. Those who find a better than c will also rank b above c, as a matter of consistency. 2 Next, suppose that Bridge and C-nnect are discussed. Note that only two organisers rank them, and both rank b above c, so this opinion will be adopted by everyone. The last issue addressed is the comparison between AppEar and C-nnect. Again everyone will adopt the only existing opinion: a above c.

(c) after discussing a and c

An obvious consensus now exists: alternative b. 3 △

1 Rawls [1971] also advocated the idea that agents hold twofold preferences-in the first level, their intrinsic preferences on the issues; in the second level, they wish to agree with their group.

2 Formally, this consistency requirement is transitivity.

3 In our specific example, the group reached a strong consensus,

Does MD assist with consensus beyond our example? Does the order of discussion matter? In this paper, we introduce a novel framework of majority dynamics for incomplete preferences, and use analytical and experimental tools to investigate its consequences with respect to a number of established consensus notions. Our main contributions show that (i) majority dynamics can damage even majority-based consensus alternatives such as the Condorcet winner (though not in some restricted preference domains); (ii) a chair can control the resulting consensus by determining the order of discussion, leading to controversial collective decisions; and (iii) the worst-case effects described in (i) and (ii) are in fact rare.

Earlier work has employed notions of consensus as a way to rationalise voting rules that minimise the distance from an ideal decision, given complete preferences [Elkind et al., 2015]. Moreover, recent research has examined incomplete preferences from various static perspectives, e.g., axiomatic ones [Pini et al., 2009; Terzopoulou and Endriss, 2019]. This paper's angle is different. Instead of applying a voting rule, we search for direct agreement within the group in the form of a consensual alternative, which leads to outcomes that are less debatable and better explainable to the participating agents (note that choosing the best voting rule is a long-standing discussion in the social choice community). The process investigated by Eklund et al. [2007] bears a similar motivation, but assumes that agents evaluate alternatives with fixed criteria in mind, and that a chair has the (often unjustified) power to force the change of someone's preference. Auletta et al. [2018] also study (majority-based) consensus in settings of opinion diffusion, but focus on social networks, and their results are limited to a single binary issue.

Moreover, many consensus measures have been defined to study the degree of discordance between the agents' preferences in a group, without the goal of selecting a final alternative [Herrera-Viedma et al., 2011]. These measures are usually based on distances and are associated with normative properties such as unanimity, suggesting that a group of agents with the same preferences has the highest possible consensus [Bosch, 2005; Alcalde-Unzu and Vorsatz, 2011].

Finally, manipulation by the chair has been explored under the name of agenda manipulation in judgment aggregation [Dietrich, 2016], and notions of bribery and control in voting [Faliszewski et al., 2009; Faliszewski et al., 2015]. Although related in flavour, these works are technically far from ours.

This paper proceeds as follows. Section 2 defines our model and the basic consensus notions. Section 3 studies the worst-case effects of the process of majority dynamics on consensus, including special cases of restricted domains. Section 4 solves the same exercise for the problem of consensus control by the chair, and Section 5 includes our experimental design and results. Finally, Section 6 concludes.

2 The Model

This section presents our model, terminology, and notation.

fully agreeing on the complete preference order. We will later discuss much weaker notions of consensus too.

2.1 Preliminaries

Let N = {1, . . . , n} be a finite set of agents, and A = {a, b, c, ...} a finite set of m ≥ 3 alternatives. 4 Each agent i ∈ N reports a strict partial order ≻i (an acyclic and transitive binary relation), which we call her preference and draw as a directed acyclic graph. We can also represent each preference as a set of pairwise rankings over alternatives. By ab we refer to the ordered pair of the alternatives a and b. For instance, if agent i prefers a to b and b to c (and thus also prefers a to c because of transitivity), her preference is the set {ab, bc, ac}.

A special kind of incomplete preferences are strict weak orderings: they represent alternatives ranked in different levels, with alternatives of the same level being incomparable. Concretely, ≻i is a strict weak ordering if there exists some ordered partition Si = (S1 i , . . . , S k i ) of A such that:

• (i) for any a, b ∈ Sg i we have ab ̸∈ ≻i and ba ̸∈ ≻i, and
• (ii) for any Sg i and Sh i such that g < h, it must be the case that a ≻i b for all a ∈ Sg i and b ∈ Sh i .

Top-truncated and bottom-truncated preferences are natural types of strict weak orderings, strictly ranking a subset of the alternatives and placing the remaining-incomparable-ones

below or above them, respectively [Baumeister et al., 2012]. 5

A vector profile P = (≻1, . . . ,≻n) of preference of size n is called a (possibly incomplete) profile. We will denote by N P ab = |{i ∈ N | a ≻i b}| the support of ab, i.e., the number of agents who prefer alternative a over b in the profile P .

There are special structural characteristics exhibited by a preference profile that make the achievement of a collective decision an unequivocal task (recall Example 1). Each of the following notions of consensus generalises an existing one from the literature on complete preferences [Elkind et al., 2015]. We start with a traditional concept:

• An alternative a is a Condorcet winner (CW) in P if N P ab > N P ba for all b ∈ A \ {a}.

Next, we distinguish two notions that capture an alternative being on "top" of an incomplete preference, which are unambiguous in the complete case: An alternative a is undominated (abbreviated 'UD') in ≻ if there is no b ∈ A such that b ≻ a, and, a is dominant (abbreviated 'Dom') if a ≻ b for all b ∈ A \ {a}. We define consensus for the former notion, and the latter is analogous.

• An alternative a is unanimity undominated (UnanUD) in P if it is undominated in ≻i for all i ∈ N.
• An alternative a is majority undominated (MajUD) in P if |{i ∈ N | a is undominated in ≻i}| > |N|/2.
• An alternative a is plurality undominated (PlurUD) in P if |{i ∈ N | a is undominated in ≻i}| > 0 and a ∈ argmaxb∈A |{i ∈ N | b is undominated in ≻i}|.

4 Our counterexamples use the minimum number of needed alternatives, but extend to any larger number by including dummy ones.

5 Our results for strict weak orderings hold for bottom-truncated preferences. Top-truncated preferences differ very little from complete ones in the context of consensus, and are thus less interesting.

More than one alternative in a profile P may satisfy the undominated consensus definitions (and the plurality dominant one). Importantly, we only say that a profile exhibits consensus when there is a unique such alternative.

Given a consensus notion C ∈ {'CW', 'UnanUD', 'UnanDom', 'MajUD', 'MajDom', 'PlurUD', 'PlurDom'} and a preference profile P , we define C(P ) ∈ A ∪ {⊥} to be the consensus alternative in P, with respect to C; if such a consensus alternative does not exist, we write C(P ) = ⊥.

2.2 Majority Dynamics

Let σ = (p1, . . . , pℓ) be an ordering of pairs of alternatives, s.t. for any two alternatives a and b, exactly one of ab or ba are in σ. We define the process of majority dynamics MDσ such that MDσ(P) is the stable profile that results from the application of the dynamics on the initial profile P where pairs are discussed following the update order σ. Let P 0 := P . When the pair pt = ab is discussed, preferences are updated from P t-1 = (≻t-1 i )i∈N to P t = (≻ti )i∈N such that:

Here, �≻� is the transitive closure of ≻, ensuring we never violate transitivity. For example, an agent with preference set {bc} that adds ab, will also have to add ac. This means that individual agents' hold (possibly incomplete) transitive preferences with no cycles at every step of the dynamics. The profile MDσ(P) is thus a profile of complete preferences over the set of alternatives. Note that we always break ties in favour of the first alternative in the considered pair.

2.3 Effects on Consensus

All possible effects that MD may have on group consensus are categorised into four types: (i) preserving, (ii) losing, or (iii) generating consensus, and (iv) preserving the absence of consensus. Moreover, given a profile of incomplete preferences, different update orders may lead to different consensus alternatives. With this in mind, effects (i) to (iii) further distinguish between the existence of any consensus alternative, and the identity of a specific consensus alternative.

Table 1 shows that five definitions below capture all nontrivial cases regarding effects on consensus, meaning that together they are expressively complete. We begin with definitions that refer to effects regarding all possible update orders.

Definition 1. Given a consensus notion C, MD preserves C existence if for all profiles P:

Definition 2. Given a consensus notion C, MD preserves C identity if for all profiles P and alternatives a ∈ A:

We next weaken consensus preservation, by quantifying over some order instead of all orders. Positive control captures scenarios where MD enables the mechanism designer to select a suitable update order to preserve consensus.

Definition 3. Given a consensus notion C, MD enables positive C existence control if for all profiles P:

Definition 4. Given a consensus notion C, MD enables positive C identity control if for all profiles P and alt. a ∈ A:

While positive control enables the achievement of consensus, negative control prevents a specific consensus from forming. This may be done either by imposing no consensus at the end of the dynamic process, or by inflicting different consensus alternatives, depending on the update order.

Definition 5. Given a consensus notion C, MD enables negative C control if for all profiles P with C(P) = ⊥, one of the following conditions hold:

• C(MDσ(P)) = ⊥, for some order σ;
• C(MDσ(P)) ̸= C(MDσ′(P)), for some orders σ, σ′ .

Table 2 summarises the results we will prove in Sections 3 and 4-notably, we will see that issues regarding existence and identity coincide for our consensus notions. Full proofs for all our results can be found in the supplementary material.

3 Preserving Consensus

We examine whether MD preserves consensus, starting with the notion of a Condorcet winner. For the special case of three alternatives, we can report some good news.

Proposition 1. For m= 3, MD preserves CW existence, but not CW identity.

Proof. Let A = {a, b, c}, and let σ = (ab, ac, bc) be the update order (for different orders the proof is analogous). Consider any profile P 0 . If alternative a is a Condorcet winner in P 0 we know that the support of ba or ca will not increase throughout MDσ, and a will remain Condorcet winner in MDσ(P 0 ). Thus, we only need to consider alternative b or c being the Condorcet winner. As the proofs proceed similarly, we only consider one of the two cases.

Suppose alternative b is the Condorcet winner in P 0 . When the pair ab is discussed at time t = 1, the agents who update their preference will support b over a, and transitivity requirements can lead them to support b over c, but never c over b.

Now, if N P 1 ac ≥ N P 1 ca , then, the support of cb will not increase at time t = 2. We thus have N P 2 cb = N P 0 cb < N P 0 bc ≤ N P 2 bc . Hence, after time t = 3, bc will havemore support than cb and b will still be the Condorcet winner in MDσ(P 0 ).

Suppose instead that N P 1 ac < N P 1 ca . Then, at time t = 2, the support of ca will increase, and potentially also that of cb. At time t = 3, if N P 2 bc ≥ N P 2 cb , b will remain the Condorcet winner in MDσ(P 0 ). If instead N P 2 bc < N P 2 cb , then c will be the Condorcet winner in MDσ(P 0 ), as a majority of agents supported c over a at time t = 2. Note that this results in a change of the identity of the Condorcet winner.

However, the situation is not as bright when m > 3.

Proposition 2. For m > 3, MD does not preserve CW existence (thus neither CW identity).

Proof. Consider the 3-agent profile P described below (ignoring the dotted edges) where w is the Condorcet winner.

Let σ be any update order starting with bc and bw. MDσ on this profile results in the inclusion of the dotted edges. Note that no Condorcet winner exists in MDσ(P ).

When it comes to undominated alternatives and PlurDom, we find that MD violates consensus preservation even for m = 3. The opposite holds for UnanDom and MajDom.

Proposition 3. Take C ∈ { 'PlurUD', 'MajUD', 'UnanUD', 'PlurDom'}. Then MD does not preserve C existence (thus neither identity).

Partial proof. We present the proof for PlurUD and MajUD. Consider the profile below (ignoring the dotted edges) where a is the plurality and majority undominated consensus.

Let σ be an order that starts with the sequence (ba, ca). As the majority of agents prefer both b and c to a, we will end up including the dotted edges. Overall, both b and c will be dominant in exactly two individual rankings.

Proposition 4. Take C ∈ {'UnanDom', 'MajDom'}. Then MD preserves C identity (thus also existence).

Proof sketch. Suppose a ∈ A is the consensus alternative according to UnanDom or MajDom. Then, any update on a pair ab or ba, for any b ∈ A \ {a}, will be made in favour of a. For the same reason, no b ∈ A \ {a} can be preferred to a because of transitivity. The consensus will thus remain.

Quality of Consensus. In cases where consensus is preserved, but the identity of the consensus alternative is not, we explore how "bad" the new consensus can be. Unfortunately, the answer is not very positive. Before diving in, we need the following definition: An alternative a is a Condorcet loser in P if N P ab < N P ba for all b ∈ A \ {a}.

Proposition 5. For m ≥ 5, MD can turn a Condorcet loser into a Condorcet winner.

Proof. Let A = {w, ℓ, a, b, x}, and consider the 7-agent profile P 0 below (ignoring the dotted edges), where w is the Condorcet winner and ℓ is the Condorcet loser.

Consider what happens if the update order σ starts with ax, bx, ℓw. After time t = 2, agents have updated their preferences on ax and bx and ℓ is preferred to w by a majority. Updating on ℓw at time t = 3 makes ℓ the Condorcet winner, and that cannot change. The updated preferences after time t = 3 are represented by the dotted edges.

Proposition 6. For m ≥ 8, MD can turn a plur. dominated (or undominated) alternative into a plur. dominant one.

A unanimity (majority) undominated alternative can become a dominated alternative in all agents' preferences as this is a relatively weak consensus requirement. We will thus focus on UnanDom and MajDom. We say an alternative is unanimity (majority) dominated if it is dominated by all alternatives in the preferences of all (a majority of) of agents.

Proposition 7. A unan. (majority) dominated alternative cannot become the unan. (majority) dominant alternative.

Restricted Preference Domains. When reducing our scope to strict weak orderings, we find good news.

Proposition 8. For profiles of strict weak orderings, MD is CW-identity preserving.

Proof. Let w be the Condorcet winner in P 0 . Consider a given agent i, and some alternative a ̸= w. We claim that it is not possible to have a ≻ti w at any time step t of the majority dynamics, unless a ≻0i w. The proof is by induction.

Suppose our claim holds for all rounds t′ < t and all alternatives z ̸= w. Then w is a Condorcet winner in round t - 1. If agent i has already have expressed either that a ≻i w or that w ≻i a in a round before t, no update can be done on this pair, so we need only consider the case where a, w ∈ Sg i for some g, where Sg i is the g-th tier of i's preferences. There are two cases we need to examine for the update in round t.

Suppose the update is performed on aw or wa directly. Then, i will support wa since w is a Condorcet winner.

Suppose instead we are updating on a pair that is neither aw nor wa, leading i to prefer a over w because of transitivity.

Then, there must exist some alternative b such that a ≻t-1 i b and b ≻t-1 i w. This, however, contradicts our assumption that ≻i is a strict weak ordering, as this-in combination with our assumption that aw ̸∈ ≻t-1 i and our induction hypothesis-precludes the existence of an alternative that is dominated by one of a and w, while dominating the other. We conclude that if a Condorcet winner exists in P 0 , then that alternative must remain a Condorcet winner in MDσ(P 0 ).

The proof of Proposition 3 uses strict weak orderings, except for UnanUD, and that of Proposition 4 also holds with strict weak orderings. Only the case of UnanUD is left then.

Proposition 9. For profiles of strict weak orderings, MD is UnanUD-identity preserving.

Proof. Consider a profile P 0 that represents strict weak orderings. Let A′ = ⋃i∈N S1 i be the set of all alternatives that are in the top tier of at least one agent.

Suppose there exists a unique unanimity undominated alternative w in P. Then for any a ∈ A′ \ {w}, there exists at least one i ∈ N such that w ≻i a, and that for no agent i′ ∈ N we have a ≻i′ w. Hence, for any update order σ, when updating on the pair wa or aw, agents will update in favour of w and that for all a ∈ A′ \ {w}. Since preferences are strict weak orderings, all alternatives in A\A′ are initially unanimously dominated by w. Overall, for any σ, w will be the unanimity undominated consensus in MDσ(P 0 ).

4 Controlling Consensus

We now investigate control issues. Note that all our proofs in this section use profiles consisting only of strict weak orderings. We start by exploring positive control.

Proposition 10. Take C ∈ {'CW', 'UnanUD', 'UnanDom', 'MajDom′ }. Then MD enables positive C identity (and thus also existence) control.

Proposition 11. Take C ∈ {'PlurUD', 'PlurDom', 'MajUD'}. Then MD does not enable positive C existence (and thus neither identity) control.

Negative control is more difficult to achieve.

Proposition 12. Take C ∈ {'CW', 'UnanUD'}. Then MD enables negative C control.

Proof. We first consider the case of CW. Let P be a profile without a Condorcet winner. Then, for any alternative a ∈ A, there is another alternative b ∈ A \ {a} such that N P ba ≥ N P ab . Now, for the update order σ starting with the pair ba, we must have CW(MDσ(P)) ̸= a. If there is no Condorcet winner in MDσ(P), we are done. In the other case, let w = CW(MDσ(P )). Because the previous also applies to w, there is σ′ such that w is not the Condorcet winner in MDσ′(P). Now if CW(MDσ′(P)) = ⊥, we are done. Otherwise, we have two update orders σ and σ′ such that CW(MDσ(P)) ̸= CW(MDσ′ (P )), which proves the statement.

For the case of UnanUD, it is clear that for any profile P with no unanimity undominated alternative, no such alternative can arise at the end of MD. If, on the other hand, there are two unanimity undominated alternatives a and b in P, then for σ starting with ab, we will have UnanUD(MDσ(P)) = a. However, for σ′ starting with ba, we would obtain UnanUD(MDσ′ (P )) = b ̸= UnanUD(MDσ(P )).

Proposition 13. Take C ∈ { 'UnanDom', 'PlurUD', 'PlurDom', 'MajUD', 'MajDom'}. Then MD does not enable negative C control.

5 Experimental Analysis

The previous two sections showed how diverse the outcomes of MD can be. We complement this formal analysis by an experimental one in order to quantify the different effects. 6

For each experiment, only some representative results are displayed. There are overall very few distinctions between dominant and undominated-based consensus notions, so we only present the undominated case. Moreover, unanimitybased consensus imposes such a strong requirement that the relevant plots are uninformative, and have thus been omitted.

5.1 Quantifying the Effects on Consensus

We first explore the effects that MD has on consensus, including generation, preservation, and loss of consensus, as well as preservation of the absence of consensus. We applied MD on synthetic profiles and used a fixed update order.

We varied the number of agents from 1 to 25, only considering odd numbers to avoid effects that rely solely on ties. For each case, we generated 5000000 random profiles over five alternatives. To generate a partial preference, we considered each pair of alternatives {a, b} and decided with uniform probability whether a beats b, b beats a, or, a and b are not compared. We repeated this process until the generated set of pairwise comparisons was transitive.

6 The experiments have been coded in Python, run on a Debian machine with 16 cores and 16GB RAM. The code and the data is available at https://github.com/Simon-Rey/Let-s-Agree-to-AgreeMajority-Dynamics-for-Incomplete-Preferences.

Figure 1 presents the effects on consensus, depending on the number of agents. Our first observation is that MD performs particularly well according to both Condorcet and plurality undominated consensus: consensus is almost always preserved if it was there to begin with, and generated otherwise. This trend is robust wrt. the number of agents. The picture is slightly different for majority undominated consensus. Even though MD often preserves consensus , the frequency of generating consensus drops significantly with the number of agents. This is likely due to the majority threshold increasing with the number of agents, making the consensus requirement more demanding. On the other hand, Condorcet and plurality-based requirements only depend on the profile and not on external parameters, hence their robustness.

We have also studied these effects depending on the level of completeness (how close to complete a profile is), and found that the level on completeness has little impact, except when it comes to majority-based consensus (for the same reasons as above). We present the figures in the supplementary material.

5.2 Quantifying the Opportunities for Control

Through experiments, we also explore the question of controlling the consensus. Our goal is to quantify the power that the chair is granted by choosing the update order. We generated 20000 profiles of 11 agents over 4 alternatives and ran MD on each profile and for all of the 46080 update orders. We counted for how many profiles at least one update order would allow the chair to achieve each type of control. The results are presented in Figure 2. We observed that MD performs relatively well at preventing the chair from damaging consensus: Only on few occasions can the chair make consensus disappear or prevent it from being generated. A benevolent chair will however be much more successful; it is very often possible to preserve the consensus and to generate it.

6 Conclusion

We have studied an original process of majority dynamics for agents with incomplete preferences. We have asked whether consulting the majority to fill missing opinions assists group consensus, and have answered that in the worst case it does not-only alternatives that are dominant for at least half of the agents are safe. Countering this, we have provided some good news: Majority dynamics preserve a Condorcet winner within natural profiles of strict weak orderings, and also do so frequently within arbitrary ones. In addition, the chair always has the power to choose an order of discussion such that consensus is preserved (unless we care about plurality-based consensus), and she can very often generate a new one too (while she can rarely make an existing one disappear). Finally, our experiments indicate that the chair can rarely choose an order to make a specific alternative the consensus.

Yet, many questions remain open. For instance: What is the computational complexity of selecting a suitable order for control, or of minimising the number of updates until consensus is reached? In cases where consensus is not achieved, how far is the resulting profile from being consensual? These and other questions are left for future work.

Acknowledgements

Sirin Botan is supported by the ARC Laureate Project FL200100204 ("Trustworthy AI"). Simon Rey is supported by the NWO Vici grant 639.023.811 ("Collective Information"). Zoi Terzopoulou is a fellow of the Paris Region Fellowship Programme, supported by the Paris Region. This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 945298ParisRegionFP. We thank the reviewers of IJCAI-2022 for their useful feedback.