Conditional Importance Networks: A Graphical Language for Representing Ordinal, Monotonic Preferences over Sets of Goods

Sylvain Bouveret, Ulle Endriss, Jérôme LangIJCAI 2009

Abstract

CI-nets (Conditional Importance Networks) are introduced as a compact graphical language for representing ordinal, monotonic preferences over bundles of goods. Unlike numerical utility functions or standard CP-nets, CI-nets allow for conditional importance statements between arbitrary sets of items. This paper establishes the formal semantics, operational proof theory via worsening flips, and computational complexity of reasoning within this framework.

Introduction

In domains such as fair division and combinatorial auctions, agents must express preferences over bundles of items. The exponential growth of the bundle space makes exhaustive listing infeasible. While numerical valuations are cognitively demanding and CP-nets are often redundant for monotonic goods, CI-nets bridge the gap by providing a purely ordinal, set-based representation that assumes monotonicity.

Methodology: CI-nets and Worsening Flips

The core of a CI-net is the conditional importance statement: $S^+, S^- : S_1 \rhd S_2$. This denotes that given the presence of $S^+$ and absence of $S^-$, the set $S_1$ is preferred over $S_2$, ceteris paribus.

The semantics are operationalized through "worsening flips." A bundle $X$ is preferred over $Y$ if $Y$ can be reached from $X$ through a sequence of atomic changes: either removing an item (monotonicity) or applying a CI-statement to replace a preferred set with a less preferred one.

Induced partial order over bundles in a CI-net. The arrows represent worsening flips derived from monotonicity and specific CI-statements.

Key Insights and Complexity

CI-nets are fully expressive, capable of representing any strict monotonic preference relation. This universality is achieved by allowing comparisons between sets rather than just singletons, capturing complex synergies and substitutions. By baking monotonicity into the semantics, the language avoids the need to specify whether "having an item" is better than "not having it" — it always is.

However, expressivity comes at a cost. Dominance checking—determining if one bundle is preferred over another—is PSPACE-complete in the general case. To address this, the authors identify tractable fragments, such as SCI-nets (precondition-free, singleton-comparing), where dominance can be checked in polynomial time using bipartite matching.

Applications and Conclusion

The framework is particularly useful for fair division under incomplete preferences. By distinguishing between "necessarily" and "possibly" envy-free allocations, CI-nets provide a robust foundation for multi-agent resource allocation. Future work will focus on efficient elicitation methods and handling specific item relationships like complements and substitutes.

Summary updated

BibTeX
@inproceedings{bouveret2009conditional,
  author = {Sylvain Bouveret and Ulle Endriss and Jérôme Lang},
  title = {{Conditional Importance Networks: A Graphical Language for Representing Ordinal, Monotonic Preferences over Sets of Goods}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
}
Figure