Preference Orders on Families of Sets - When Can Impossibility Results Be Avoided?

Jan Maly, Miroslaw Truszczynski, Stefan WoltranIJCAI 2018 · DOI

TL;DR

This paper investigates when we can avoid "impossibility results" in preference aggregation, which state that certain desirable properties for ranking sets of items are incompatible. The authors show that by restricting the families of sets considered to those that induce connected subgraphs in a given graph, these impossibilities can often be overcome. They provide characterizations of which graph structures allow for such "orderable" families of sets under various preference axioms.

What Problem Does This Paper Address?

Decision-making often requires not just ranking individual items but also ranking collections of items. For example, when allocating resources or choosing a set of options under constraints, we need a way to compare entire sets. This is typically done by "lifting" an existing preference order on individual items to an order on sets of items. However, a significant body of research in social choice theory has revealed "impossibility theorems" – results showing that it's impossible to satisfy a set of seemingly reasonable axioms (like dominance, independence, and extension) when ranking all possible non-empty subsets of items.

This paper tackles the question: can these impossibility results be avoided if we only consider specific, structured families of subsets, rather than all possible subsets? The authors focus on families of sets that correspond to connected subgraphs within a given graph. This is motivated by real-world scenarios where only certain configurations of items are meaningful (e.g., contiguous rooms in a building, connected plots of land). They aim to characterize which graph structures allow for the existence of "lifted" preference orders on these structured families of sets, satisfying key axioms.

Methods

The core of the paper is an axiomatic approach to preference lifting. They define several axioms that a lifted preference order on sets should satisfy:

  • Extension Rule: If item x is preferred to item y, then the set {x} should be preferred to the set {y}.
  • Strong Extension: If x is the most preferred item in set A and y is the most preferred item in set B, and x is preferred to y, then set A should be preferred to set B.
  • Dominance: If all items in set A are less preferred than item x, then A is less preferred than A ∪ {x}. Conversely, if all items in A are more preferred than x, then A ∪ {x} is less preferred than A.
  • Independence: If set A is preferred to set B, then adding a new item x (not in A or B) to both sets should preserve this preference: A ∪ {x} is preferred to B ∪ {x}.
  • Strict Independence: A stronger version of independence, where A being strictly preferred to B implies A ∪ {x} is strictly preferred to B ∪ {x}.

The authors then define "orderable graphs" based on whether these axioms can be satisfied for the family of sets corresponding to connected subgraphs (or induced trees) of that graph. They introduce the concepts of "strongly orderable" (holds for every linear order on elements) and "weakly orderable" (holds for at least one linear order). They then systematically analyze which graph classes (trees, forests, bipartite graphs, cycles, complete graphs) satisfy these orderability properties under different combinations of axioms.

Datasets

Not discussed in the paper. The paper deals with abstract mathematical structures (graphs and sets) and axiomatic properties, rather than empirical data.

Key Insights and Ideas

  • Structure is Key: The paper's central insight is that restricting the family of sets to those induced by connected subgraphs in a graph can circumvent the general impossibility results. This highlights the importance of structural constraints in preference aggregation.
  • Graph Topology Matters: The specific structure of the graph (e.g., being a tree, bipartite, or containing cycles) directly determines whether preference lifting is possible under certain axioms. This connects graph theory to social choice theory in a novel way.
  • Strict Independence is Powerful: The authors find that "strict independence" is a much stronger axiom than "independence" in enabling orderability. Weakening strict independence to independence only offers a modest extension of the classes of orderable graphs, suggesting strict independence plays a more crucial role in avoiding impossibilities.
  • Trees are "Perfect": Forests (graphs without cycles) are shown to be strongly orderable under dominance, strict independence, and strong extension. This means for any linear order on the vertices, a compatible order on connected subgraphs can always be found.
  • Bipartite Graphs are "Good Enough" for Weak Orderability: While not all bipartite graphs are strongly orderable, they are all weakly orderable under dominance, strict independence, and strong extension. This means for at least one linear order on the vertices, a compatible order on connected subgraphs exists.

Key Results

  • Strong Orderability: Forests are precisely the graphs that are strongly orderable with respect to dominance, strict independence, and strong extension. Complete graphs $K_n$ are strongly orderable for $n \le 3$.
  • Weak Orderability: Bipartite graphs are precisely the graphs that are weakly orderable with respect to dominance, strict independence, and strong extension.
  • Impact of Independence vs. Strict Independence: The class of strongly orderable graphs under dominance and strict independence is much smaller than under dominance and independence. Specifically, adding cycles (beyond $K_3$) generally breaks strong orderability with strict independence.
  • Characterizations Provided: The paper provides complete characterizations for graphs that are strongly/weakly DI(S)E(S)-orderable (dominance, strict independence, extension/strong extension) and weakly DI(S)E(S)-orderable (dominance, strict independence, extension/strong extension).

Limitations and Future Work

  • Focus on Specific Axioms: The paper primarily focuses on combinations of dominance, independence (strict or regular), and extension/strong extension. Other combinations of axioms might yield different results.
  • Weak Orderability for General Graphs: While bipartite graphs are characterized for weak orderability, a complete picture for general graphs under weaker axiom sets (like just dominance and independence) is still developing.
  • Logical Representations: The authors suggest that their work on graph-based implicit representations could be extended to other formalisms, such as logic programs, where formulas represent sets of models. Investigating lifting problems in these contexts is a promising avenue.
  • Complexity: The paper mentions that deciding orderability for arbitrary families of sets is NP-complete. Future work could explore the complexity of deciding orderability for graph-defined families and develop efficient algorithms for computing lifted orders.
  • "Reverse" Problem: The paper suggests investigating the "reverse" problem: deriving an order over individuals from a given order over sets of individuals.

Summary updated

BibTeX
@inproceedings{maly2018preference,
  author = {Jan Maly and Miroslaw Truszczynski and Stefan Woltran},
  title = {{Preference Orders on Families of Sets - When Can Impossibility Results Be Avoided?}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/60},
}
Figure