TL;DR
This paper surveys the field of collective decision-making under incomplete knowledge, focusing on the concepts of "possible" and "necessary" winners. It explores how these concepts, originally developed for voting, are extended to other social choice problems like fair division and coalition formation, offering a unified perspective on handling uncertainty in group decisions.
What Problem Does This Paper Address?
In real-world collective decision-making, it's often impractical or impossible to fully elicit everyone's preferences or to have complete knowledge of the decision-making mechanism. Traditional social choice theory, however, typically assumes perfect information. This paper addresses the challenge of making collective decisions when preferences are only partially known or when the aggregation mechanism itself is not fully specified. The core problem is how to determine potential outcomes or guaranteed outcomes in the face of this uncertainty.
Methods
The paper's primary method is a survey of existing research, organizing it around the concepts of "possible" and "necessary" solutions.
- Possible Winner: A candidate is a "possible winner" if there exists at least one way to complete the incomplete information (e.g., fill in missing preferences) such that the candidate wins according to the decision rule. This is akin to existential quantification over possible worlds.
- Necessary Winner: A candidate is a "necessary winner" if they win regardless of how the incomplete information is completed. This is akin to universal quantification over possible worlds.
The paper then systematically applies these concepts to various scenarios:
- Voting: This is the foundational area, where "possible" and "necessary" winners are defined based on incomplete preference profiles.
- Extensions to Other Domains: The paper details how these modal notions are adapted to:
- Partial Tournaments: Analyzing outcomes in scenarios where pairwise comparisons are not fully known.
- Fair Division: Determining allocations of indivisible items that are possibly or necessarily envy-free or Pareto-efficient, given incomplete agent preferences over bundles of items.
- Hedonic Games: Examining coalition structures that satisfy stability concepts under incomplete agent preferences over coalition members.
- Incomplete Mechanisms: The paper also touches upon scenarios where the uncertainty lies not in preferences but in the parameters of the decision-making mechanism itself (e.g., voter weights, scoring vectors).
- Variants and Extensions: It discusses more complex quantifier alternations (beyond simple "possible" and "necessary"), probabilistic approaches, and different models of uncertainty.
Datasets
Not discussed in the paper. The paper focuses on theoretical frameworks and computational complexity rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Unified Framework for Uncertainty: The "possible" and "necessary" winner framework provides a powerful and general way to reason about outcomes under various forms of incomplete information, applicable across different social choice problems.
- Bridging Theory and Practice: The paper highlights the practical necessity of handling incomplete information, as it's a common feature of real-world decision-making processes.
- Complexity Trade-offs: While dealing with incomplete information is necessary, it often introduces significant computational complexity. The paper surveys research that analyzes these complexities for different rules and problem types.
- Beyond Voting: The extension of these concepts to fair division, tournaments, and hedonic games demonstrates the broad applicability of modal reasoning in collective decision-making.
- Mechanism Design Implications: Understanding possible and necessary outcomes can inform the design of more robust and informative elicitation processes, potentially leading to faster or more reliable decisions.
Key Results
The paper is a survey, so it doesn't present new empirical results. Instead, it synthesizes findings from numerous research papers. Key qualitative findings include:
- For many decision rules, determining possible and necessary winners is computationally hard (often NP-hard).
- The existence of a necessary winner can serve as a stopping criterion for preference elicitation, indicating that the outcome is already determined.
- In some cases, incomplete information can lead to a situation where almost all candidates are "possible winners," making the concept less discriminative and prompting research into probabilistic or approximation approaches.
- The paper provides characterizations and complexity results for possible and necessary winners under various rules (e.g., Condorcet, plurality, positional scoring) and for different types of incomplete information (e.g., missing votes, missing candidates, truncated ballots, incomplete lists).
Limitations and Future Work
- Computational Complexity: A persistent limitation is the inherent computational difficulty of determining possible and necessary winners, especially as the number of candidates or voters grows.
- Elicitation Strategies: While the paper discusses how identifying possible/necessary winners can inform elicitation, a key open question is how to best interleave reasoning about possible outcomes with active preference elicitation to speed up the decision-making process.
- New Models of Incomplete Preferences: The authors suggest exploring other forms of incomplete preferences, such as multichotomies (where voters group candidates into broad categories) and multi-attribute preferences with uncertain attribute importance.
- Beyond Binary Logic: While the paper focuses on "possible" (existential) and "necessary" (universal) quantifiers, it hints at the possibility of exploring more complex logical structures or quantifier alternations for richer decision-making scenarios.
- Practical Applications: Further research is needed to translate these theoretical frameworks into practical, user-friendly tools for real-world collective decision-making.
Summary updated