Author name cluster

Ari Conati

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

AAMAS Conference 2025 Conference Paper

Collective Decision Making via Automated Reasoning

Ari Conati

Collective decision-making tasks, such as voting, matching, and resource allocation, are frequently encountered in multi-agent scenarios where a consensus is sought for based on the—often conflicting— preferences of individual agents. Deciding if a consensus can be reached and finding such consensus give rise to computationally hard decision and optimization problems, characterized by NPcompleteness or even beyond-NP complexity. This complexity poses significant challenges for developing practical exact algorithms. At the same time, advances in automated logical reasoning techniques, such as Boolean satisfiability solvers, their extensions to higherlevel constraints, and optimization have proven successful for capturing and solving a wide range of computationally hard real-world problems. My doctoral research harnesses automated logical reasoning for developing novel types of practical, exact algorithms for computational social choice scenarios.

PDF

AAMAS Conference 2025 Conference Paper

Computing Efficient and Envy-Free Allocations under Dichotomous Preferences using SAT

Ari Conati
Andreas Niskanen
Ronald de Haan
Matti Järvisalo

We study the problems of computing envy-free Pareto-efficient allocations in the context of fair allocation and hedonic games under dichotomous preferences. We establish Σ p 2-completeness of deciding the existence of envy-free Pareto-efficient allocations, refining earlier related results. We also develop iterative SAT-based exact algorithms for computing envy-free Pareto-efficient allocations, and extend the approach to computing minimum-envy Pareto-efficient allocations under different combinations of aggregation functions. We provide open-source implementations of the algorithms and show empirically that the approach scales to computing envy-free Pareto-efficient allocations up to hundreds of agents.

PDF

ECAI Conference 2024 Conference Paper

Complexity Results and Algorithms for Manipulation and Bribery in Judgment Aggregation

Ari Conati
Andreas Niskanen
Ronald de Haan
Matti Järvisalo

The study of limits of strategic behavior in collective decision making is a central topic in computational social choice. Focusing on judgment aggregation, we provide complexity results and algorithms for manipulation and bribery under various aggregation rules. Specifically, we show that manipulation and bribery are complete for the second level of the Polynomial Hierarchy and detail aggregation-rule-specific strong refinements for effective counterexample-guided abstraction refinement algorithms based on iterative calls to a maximum satisfiability solver for both manipulation and bribery. We provide an open-source implementation of the approach and empirically evaluate its performance on standard PrefLib datasets, showing that the strong refinement strategies developed in this work enable scaling up to solving more instances.

Details

JAIR Journal 2024 Journal Article

Declarative Approaches to Outcome Determination in Judgment Aggregation

Ari Conati
Andreas Niskanen
Matti Järvisalo

Judgment aggregation (JA) offers a generic formal framework for modeling various settings involving information aggregation by social choice mechanisms. For many judgment aggregation rules, computing collective judgments is computationally notoriously hard. The central outcome determination problem, in particular, is often complete for higher levels of the polynomial hierarchy. This complexity barrier makes it challenging to develop practical exact algorithms to outcome determination. Taking on this challenge, in this work we develop practical exact algorithms for outcome determination under a range of the most central JA rules—namely Kemeny, Slater, MaxHamming, Young, Dodgson, Reversal scoring, Condorcet, Ranked agenda, and LexiMax—by harnessing the declarative approach, in particular, Boolean satisfiability (SAT) and integer programming techniques. For the Kemeny, Slater, MaxHamming, Young, and Dodgson rules, we detail direct approaches based on maximum satisfiability (MaxSAT) and integer programming. For the Reversal scoring, Condorcet, Ranked agenda, and LexiMax rules, we develop iterative algorithms, including algorithms based on the counterexample-guided abstraction refinement (CEGAR) paradigm, making use of recent advances in incremental MaxSAT solving and preferential SAT-based reasoning. We provide an open-source implementation of the algorithms, and empirically evaluate them using real-world preference data. We compare the performance of our implementation to a recent approach which makes use of declarative solver technology for answer set programming (ASP). The results demonstrate that our approaches scale significantly beyond the reach of the ASP-based algorithms for all of the judgment aggregation rules considered.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

SAT-based Judgment Aggregation

Ari Conati
Andreas Niskanen
Matti Järvisalo

Judgment aggregation (JA) offers a generic formal logical framework for modeling various settings where agents must reach joint agreements through aggregating the preferences, judgments, or beliefs of individual agents by social choice mechanisms. In this work, we develop practical JA algorithms for outcome determination by harnessing Boolean satisfiability (SAT) based solvers as the underlying reasoning engines, leveraging on their ability to efficiently reason over logical representations incrementally. Concretely, we provide algorithms for outcome determination under a range of aggregation rules, using natural choices of SAT-based techniques adhering to the computational complexity of the problem for the individual rules. We also implement and empirically evaluate the approach using both synthetic and PrefLib data, showing that the approach can scale significantly beyond recently proposed alternative algorithms for JA.

PDF