TL;DR
This paper introduces a new framework for collective decision-making where agents express propositional goals rather than full preference rankings. They propose and axiomatize a majority rule for these goal-based decisions and analyze the computational complexity of determining the outcome, finding it ranges from NP to Probabilistic Polynomial Time (PP). This work is crucial for more realistic multi-agent systems that need to make collective choices on complex issues.
What Problem Does This Paper Address?
Traditional social choice theory often assumes agents can express complete preference orderings over all possible outcomes. However, in many real-world scenarios, especially those involving combinatorial choices (like planning a trip with multiple destinations or configuring a complex product), this becomes computationally intractable or overly burdensome for agents. Agents might have simpler, more focused "goals" (e.g., "I want to visit at least one museum") rather than a strict ranking of all possible itineraries. Existing methods like judgment aggregation, while useful, can be too rigid. This paper addresses this gap by developing a framework for collective decision-making based on propositional goals, aiming for rules that are both fair and decisive, and exploring their computational properties.
Methods
The authors adapt concepts from Social Choice Theory and Judgment Aggregation to their new framework of "goal-based voting." Key methods include:
- Propositional Goals: Agents express their preferences as consistent propositional formulas over binary issues. This is a more compact representation than full preference lists.
- Axiomatic Characterization: They define and analyze several desirable properties (axioms) for collective decision rules, such as anonymity, neutrality, independence, unanimity, and positive responsiveness. They then use these axioms to characterize a specific majority rule, "TrueMaj," showing it's the unique rule satisfying a particular set of fairness and decisiveness criteria.
- Majority Rule Variants: They propose and compare three variants of a majority rule: EMaj, TrueMaj, and 2sMaj, each aggregating goals in a slightly different way.
- Computational Complexity Analysis: They investigate the difficulty of determining the outcome of these rules. This involves defining winner determination problems for both resolute (single outcome) and irresolute (multiple outcomes) rules and analyzing them using standard complexity classes like NP and PP.
Datasets
Not discussed in the paper. The paper focuses on theoretical framework development and axiomatic analysis, using hypothetical examples rather than empirical datasets.
Key Insights and Ideas
- Propositional Goals as a More Realistic Model: The paper highlights that representing preferences as propositional goals is often more natural and computationally feasible for agents in complex combinatorial domains than full preference rankings. The example of Camille wanting to visit any single place illustrates this well.
- The Tension Between Fairness and Resoluteness: A central theme is the trade-off between having a unique, decisive outcome (resoluteness) and ensuring fairness to individual agents and issues. The proposed majority rules are designed to balance this tension.
- TrueMaj as a Principled Majority Rule: Through axiomatic analysis, TrueMaj emerges as a well-characterized rule that satisfies a strong set of fairness properties, making it a strong candidate for goal-based collective decisions.
- Computational Cost of Goal-Based Voting: The paper reveals that moving from simpler preference representations to propositional goals significantly increases computational complexity, pushing problems into classes like NP and even PP, which are generally harder to solve efficiently.
Key Results
- Axiomatic Characterization: The paper proves that the "TrueMaj" rule is uniquely characterized by a set of axioms including egalitarianism, independence, neutrality, anonymity, positive responsiveness, unanimity, and duality.
- Computational Complexity:
- Winner determination for the conjunction rule (Conj) is NP-hard.
- Winner determination for the approval rule (Approval) is Σ₂-complete.
- Winner determination for threshold rules (TrSh) with uniform weights is NP-complete.
- Winner determination for the majority rules (2sMaj, EMaj, TrueMaj) is PP-hard.
- Comparison of Majority Rules: The paper demonstrates that the three proposed majority rules (EMaj, TrueMaj, 2sMaj) can produce different outcomes for the same input, illustrating the impact of their specific aggregation mechanisms.
Limitations and Future Work
- Limitations:
- The paper acknowledges that the proposed majority rules are not "grounded," meaning the collective outcome might not satisfy the goal of any individual agent. This is presented as a trade-off for achieving compromise.
- The computational complexity results show that goal-based voting can be very demanding, with some problems falling into the PP complexity class, which is challenging to solve efficiently.
- Future Work:
- Investigate restrictions on the language of goals that could lead to more tractable winner determination problems.
- Develop efficient approximation algorithms for computing outcomes.
- Explore novel voting procedures for related domains (e.g., non-binary combinatorial domains, more expressive preference languages).
- Study the impact of integrity constraints on collective decisions.
- Further explore the PP complexity class in the context of propositional goal-based reasoning.
Summary updated