Aggregating Incomplete Pairwise Preferences by Weight

Zoi Terzopoulou, Ulle EndrissIJCAI 2019 · DOI

TL;DR

This paper introduces a new model for aggregating preferences that aren't necessarily complete or transitive, a common scenario in real-world decision-making. They propose "weight rules" where an agent's influence depends on how many preferences they express, and show that two key axioms – restricted majoritarianism and splitting – lead to specific, well-behaved aggregation rules.

What Problem Does This Paper Address?

In many AI applications, like recommendation systems or planning, we need to combine the preferences of multiple agents. Traditionally, this has relied on agents providing complete and transitive rankings of all alternatives. However, in reality, people often have incomplete preferences (they might not have an opinion on every pair of items) and their preferences might not be perfectly rational (e.g., cyclical preferences). This paper tackles the challenge of aggregating these "bona fide incomplete preferences" – where the incompleteness is inherent, not just due to a lack of information. They aim to develop aggregation rules that are both normative (fair and reasonable) and flexible enough to handle these realistic preference structures.

Methods

The core of the paper is the introduction of "weight rules" for aggregating pairwise preferences. These rules have two main components:

  1. Weight Function (w): This function assigns a weight to an agent's reported pairwise preference based on the size of their ballot (i.e., how many pairs they ranked). The idea is that an agent who expresses fewer preferences might deserve more weight per preference than someone who ranks everything.
  2. Type (T): This specifies the desired format of the collective outcome. The paper considers four types:
  3. L: Complete linear orders (standard rankings).
  4. W: A single winner.
  5. Wk: A set of k winners.
  6. C: Chains (partial rankings).

A weight rule $F^T$ selects the outcome(s) of type T that maximize the total weighted sum of preferences across all agents.

The authors then analyze these rules through the lens of two normative axioms:

  • Restricted Majoritarianism: This axiom states that if a majority prefers 'a' to 'b' for a pair of alternatives that are "independent" (meaning no agent compares them to any other alternative), then 'a' must be ranked above 'b' in the collective outcome.
  • Splitting: This axiom ensures that if a group of agents have compatible preferences and express them as a union of their individual ballots, the outcome should not change. They consider variations like "single splitting" (where each agent in the group ranks only one pair) and "equal splitting" (where agents in the group rank the same number of pairs).

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and axiomatic characterization rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Weighting Incompleteness: The paper elegantly formalizes the intuition that an agent's influence can be modulated by the effort they put into expressing their preferences (i.e., the number of pairs they rank). This moves beyond traditional models where all expressed preferences carry equal weight.
  • Axioms for Incompleteness: Restricted majoritarianism and splitting are introduced as particularly relevant axioms for handling incomplete preferences. They capture fundamental fairness and robustness properties in this context.
  • Characterizing Simple Rules: Surprisingly, even a very weak axiom like restricted majoritarianism is sufficient to uniquely characterize the "constant-weight rule" for collective rankings. Similarly, splitting axioms lead to the "equal-and-even-weight rule." This suggests that simple, intuitive weighting schemes can satisfy strong normative properties.
  • Impossibility of Coexistence: A key theoretical finding is that majoritarianism and splitting axioms are fundamentally incompatible for any weight rule. This has practical implications, suggesting a trade-off between respecting majority will and preventing strategic group manipulation.
  • Computational Efficiency: The paper highlights that their proposed weight rules are computationally efficient, often polynomial-time computable, which is a significant advantage over some existing methods for incomplete preferences (like possible winner concepts).

Key Results

  • Constant-Weight Rule: Satisfies restricted majoritarianism for collective rankings (type L).
  • Equal-and-Even-Weight Rule: Satisfies single-splitting and equal-splitting axioms for collective rankings (type L) and for single/multi-winners (types W, Wk).
  • Impossibility Result: No weight rule can simultaneously satisfy weak restricted majoritarianism and any form of the splitting axiom (single, equal, or arbitrary).
  • Computational Tractability: For all considered output types (L, W, Wk), weight rules are computationally efficient, contrasting with some existing approaches for incomplete preferences.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on axiomatic characterization. An experimental study to compare these rules in practice is suggested.
  • Exploring Other Axioms: The authors acknowledge that their work is a starting point and suggest identifying further axioms and the weight rules they characterize.
  • Beyond Weight Rules: The paper focuses on a specific family of rules (weight rules). Future work could explore other aggregation mechanisms for incomplete preferences.
  • Strategic Behavior: While splitting axioms aim to disincentivize manipulation, a deeper analysis of strategic behavior under these new rules could be beneficial.

Summary updated

BibTeX
@inproceedings{terzopoulou2019aggregating,
  author = {Zoi Terzopoulou and Ulle Endriss},
  title = {{Aggregating Incomplete Pairwise Preferences by Weight}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/84},
}
Figure