TL;DR
This paper introduces "Majority Dynamics" (MD), a novel process where agents with incomplete preferences collectively make decisions by discussing issues one by one and adopting the majority opinion on undecided matters. While MD can sometimes damage existing consensus, especially for complex scenarios, it often preserves or even generates consensus, and a "chair" can strategically influence the outcome by controlling the discussion order.
What Problem Does This Paper Address?
In many real-world scenarios, groups need to make collective decisions, but individuals often have incomplete information or preferences. This makes reaching a consensus challenging. Imagine a committee deciding on software for an online conference: not everyone might have an opinion on every app, or they might only know about a subset of them. How can such a group arrive at a decision that reflects their collective will, especially when preferences are not fully formed? This paper tackles this by exploring a specific process, Majority Dynamics (MD), to see how it affects different notions of group consensus when preferences are incomplete.
Methods
The core of the paper is the formalization and analysis of Majority Dynamics (MD). In this process, a group of agents with potentially incomplete preferences discusses pairwise comparisons of alternatives one at a time, following a predetermined order. When an agent has no opinion on a particular pair, they adopt the opinion of the majority of agents who do have an opinion on that pair. This update is applied transitively to maintain consistency in individual preferences. The authors then analyze how this dynamic process impacts various established consensus notions, such as the Condorcet Winner (an alternative that beats all others in pairwise comparisons), and introduce new ones like "unanimity undominated" and "majority undominated" alternatives. They investigate four types of effects: preserving consensus (existence and identity), losing consensus, generating consensus, and preserving the absence of consensus. The analysis involves both theoretical proofs and experimental simulations.
Datasets
Not discussed in the paper. The authors generated synthetic preference profiles for their theoretical analysis and experimental simulations.
Key Insights and Ideas
- MD is not a silver bullet for consensus: While intuitive, simply following the majority on undecided issues doesn't guarantee consensus. In the worst-case scenarios, it can even damage existing consensus, particularly for more stringent definitions like the Condorcet Winner when there are many alternatives.
- The "Chair" has power: The order in which issues are discussed (the "update order") is crucial. A strategic "chair" can influence whether consensus is achieved, lost, or even which specific alternative becomes the consensus. This highlights the potential for manipulation.
- Strict weak orderings offer some robustness: When agents have preferences that are "strict weak orderings" (a common and structured form of incomplete preferences), MD is much better behaved. It preserves the existence and identity of Condorcet Winners and unanimity undominated alternatives, offering a more stable outcome in these restricted domains.
- Worst-case scenarios are rare: Despite the theoretical possibility of MD damaging consensus, experimental results suggest that these negative effects are often mild in practice. MD tends to preserve consensus and generate it more often than not.
- Different consensus notions behave differently: The impact of MD varies significantly depending on the definition of consensus used. More demanding notions (like Condorcet Winner) are more susceptible to being damaged, while weaker ones (like majority undominated) are more robust.
Key Results
- For scenarios with only three alternatives, MD preserves the existence of a Condorcet Winner but not necessarily its identity.
- For more than three alternatives, MD can fail to preserve the existence (and thus identity) of a Condorcet Winner.
- MD does not preserve the existence of plurality or majority undominated/dominated alternatives in general.
- However, MD does preserve the identity (and thus existence) of unanimity and majority dominated alternatives.
- MD can turn a Condorcet loser into a Condorcet winner for 5 or more alternatives.
- A chair can exert "positive control" to ensure consensus exists or preserve its identity for certain consensus notions, and "negative control" to prevent specific consensus outcomes for others.
- Experimental results show that MD frequently preserves or generates consensus, especially for Condorcet and plurality undominated notions, and the effects are generally robust to the number of agents.
Limitations and Future Work
The authors acknowledge that their analysis focuses on specific types of consensus and dynamics. Future work could explore:
- Computational Complexity: Determining the complexity of finding an optimal discussion order for control or minimizing the number of updates to reach consensus.
- Degree of Consensus: Quantifying how "far" a resulting profile is from being consensual when consensus is not fully achieved.
- Alternative Dynamics: Investigating other opinion diffusion or consensus-building mechanisms.
- More Complex Preference Structures: Extending the analysis to more intricate forms of incomplete preferences.
Summary updated