Agenda Separability in Judgment Aggregation

Jérôme Lang, Marija Slavkovik, Srdjan VesicAAAI 2016 · DOI

Introduction

In multi-agent systems, combining conflicting individual opinions into a single collective decision is a fundamental challenge known as Judgment Aggregation (JA). A persistent hurdle in JA is that desirable properties often lead to mathematical impossibilities, most notably the "dictatorship" result, where the collective outcome is always determined by a single agent. This paper, originally presented at AAAI-16 by Lang, Slavkovik, and Vesic, introduces Agenda Separability as a middle ground that maintains modularity and computational efficiency without necessitating a dictatorship.

The Independence Dilemma

The core of the problem lies in the Independence property, which dictates that the collective judgment on a specific proposition should only depend on individual judgments of that proposition. While intuitive—for example, a decision on one geographical fact shouldn't influence another—Independence is mathematically restrictive. Standard impossibility results show that any rule satisfying Independence along with basic fairness criteria must be a dictatorship. To circumvent this, researchers seek relaxations that are intuitive, computationally useful, and capable of distinguishing between aggregation rules.

Methodology: Agenda Separability

The authors propose Agenda Separability (AS). A rule satisfies AS if an agenda (the set of issues) can be partitioned into logically independent sub-agendas, allowing the final result to be obtained by aggregating each sub-agenda separately and merging the results.

An example of an agenda partitioned into independent sub-agendas $P_1$ and $P_2$.

As shown in Figure 1, the agenda is split into $P_1$ (concerning $p, q, p \wedge q$) and $P_2$ (concerning $t$). If a rule is agenda-separable, the collective decision for $P_1$ can be calculated independently of $P_2$. This "divide and conquer" approach is central to the paper's contribution to computational efficiency.

The authors further introduce Overlapping Agenda Separability (OAS). This stricter version applies when sub-agendas share common variables but remain "conditionally independent" in a logical sense.

Illustration of overlapping agenda separability with conditionally independent components.

Figure 2 demonstrates a more complex scenario where components (color-coded) share variables but can still be decomposed under the OAS framework. The authors evaluated seven well-known JA rules, including the Median rule and Max Condorcet rule, against these properties using an axiomatic, proof-based approach.

Key Insights

  • Decomposability of Agendas: A significant finding is that "preference agendas" (standard voting rankings) are generally not decomposable. The transitivity requirement (if A > B and B > C, then A > C) links all candidates, preventing the split of a ranking problem into independent parts.
  • Computational Efficiency: Agenda-separable rules allow for efficient algorithms. Complex problems can be solved by processing smaller sub-problems in parallel, significantly reducing computational overhead.
  • Strategyproofness: Separability offers a degree of protection against manipulation. An agent cannot influence the outcome of one sub-agenda by misrepresenting their views on an unrelated sub-agenda.

Results and Taxonomy

The paper categorizes major aggregation rules based on their separability:

  • Satisfy Agenda Separability (AS): Median (MED), Reversal Scoring ($R_{rev}$), Max Condorcet (MC), Maxcard Condorcet (MCC), Ranked Agenda (RA), and Full Hamming (FULLH).
  • Satisfy Overlapping Agenda Separability (OAS): Only Max Condorcet (MC) and Ranked Agenda (RA).
  • Fail Both: The Minimax Hamming rule ($RdH,MAX$).

These results demonstrate that AS is a "discriminant" property—it is selective enough to exclude some rules while being achievable by others.

Conclusion and Future Work

While agenda separability is a powerful tool, it has limitations. Tie-breaking mechanisms can sometimes break the separability of an otherwise separable rule. Furthermore, because preference agendas are not easily decomposable, AS is most applicable to complex AI tasks like multi-agent belief revision or crowdsourced labeling rather than traditional political voting. Future research aims to fully characterize the class of rules satisfying agenda separability to discover new, optimized aggregation methods.

Summary updated

BibTeX
@inproceedings{lang2016agenda,
  author = {Jérôme Lang and Marija Slavkovik and Srdjan Vesic},
  title = {{Agenda Separability in Judgment Aggregation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2016},
  doi = {10.1609/aaai.v30i1.10097},
}
Figure