Answer Set Programming for Judgment Aggregation

Ronald de Haan, Marija SlavkovikIJCAI 2019 · DOI

TL;DR

This paper tackles the computational intractability of judgment aggregation (JA) by proposing a novel approach: encoding JA problems into Answer Set Programming (ASP). This allows researchers to leverage powerful ASP solvers to compute collective judgments and analyze agenda properties, paving the way for practical JA implementations and new benchmark instances.

What Problem Does This Paper Address?

Judgment aggregation (JA) is a framework for combining individual opinions on logically related issues into a single collective decision. While JA has broad applications in areas like voting and multi-agent systems, a significant hurdle to its practical use is the extreme computational complexity of most aggregation procedures. These problems are often $\Pi_2$-complete, meaning they are very difficult to solve efficiently. Consequently, there's a lack of readily available, structured implementations for these JA methods. This paper aims to bridge this gap by providing a way to harness the power of Answer Set Programming (ASP) solvers, which are known to handle computationally hard problems effectively, to solve JA problems.

Methods

The core contribution of this paper is the development of a general and modular encoding of various judgment aggregation procedures and related problems into Answer Set Programming (ASP). The authors first establish a foundational encoding for the basic JA framework, including representing voters, issues, and integrity constraints. This foundation is then extended to encode specific JA procedures such as:

  • Scoring Procedures: General encodings for procedures based on assigning scores to judgments.
  • Kemeny: Encoding the Kemeny procedure by maximizing agreement with the majority.
  • Leximax: Encoding the Leximax procedure, highlighting its symmetry with Kemeny.
  • Reversal Scoring: Encoding the reversal scoring procedure using a virtual agent and prioritized optimization.
  • Young: Encoding the Young procedure by guessing voter subsets and minimizing removed voters.
  • MSA (Maximum Subset of the Agenda): Encoding MSA using meta-programming techniques for set-inclusion minimization.
  • Ranked Agenda: Encoding the Ranked Agenda procedure using saturation techniques to verify outcomes.

Beyond computing collective outcomes, the paper also presents encodings for checking agenda properties, specifically:

  • k-Median Property: Encoding to find minimally $\Gamma$-inconsistent subsets of the agenda.
  • Agenda Separability: Encoding to find independent partitions of an agenda.

The encodings are designed to be modular, allowing different components to be reused and combined. They leverage ASP's features like disjunction, negation as failure, built-in arithmetic, and optimization statements (e.g., #maximize, #minimize).

Datasets

Not discussed in the paper. The authors mention that their encodings can be used to construct new benchmark instances for ASP solvers, potentially using real-world data (e.g., from PrefLib) by encoding it into JA problems.

Key Insights and Ideas

  • ASP as a Universal Solver for JA: The paper demonstrates that ASP's expressiveness is sufficient to encode a wide range of computationally hard JA problems, making it a powerful tool for tackling this domain.
  • Bridging Theory and Practice: By providing concrete ASP encodings, the work moves JA from a theoretical framework towards practical implementation, addressing the lack of existing tools.
  • Modular Design for Reusability: The modular nature of the ASP encodings allows for flexibility and reuse, facilitating the development of more complex JA systems.
  • New Benchmark Generation: The encodings offer a systematic way to generate challenging benchmark instances for ASP solvers, particularly for $\Pi_2$-complete problems.
  • Revealing Algorithmic Symmetries: The ASP encodings can elegantly highlight structural similarities between different JA procedures, as seen in the Kemeny and Leximax examples.

Key Results

The paper presents ASP encodings for numerous judgment aggregation procedures and agenda properties. For each encoding, theorems are provided (with proofs sketched) establishing a one-to-one correspondence between the optimal answer sets of the ASP program and the outcomes of the corresponding JA procedure or the property being checked. This means that solving the ASP program effectively solves the JA problem. The paper does not present quantitative results in terms of speedup or accuracy on specific datasets, as its focus is on the formal encoding and its theoretical correctness.

Limitations and Future Work

The authors acknowledge that their work provides a baseline for experimental evaluations of future JA implementations. Future work suggested includes:

  • Developing optimized ASP encodings for JA methods.
  • Encoding strategic behavior problems in JA, such as manipulation, bribery, and control.
  • Encoding additional agenda properties like total blockedness and negatability.
  • Extending the encodings to handle auxiliary variables for more complex JA scenarios.
  • Exploring encodings for overlapping independent partitions.

Summary updated

BibTeX
@inproceedings{haan2019answer,
  author = {Ronald de Haan and Marija Slavkovik},
  title = {{Answer Set Programming for Judgment Aggregation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/231},
}

Loading related content...

Figure