Academic Journal
Declarative Approaches to Outcome Determination in Judgment Aggregation.
| العنوان: | Declarative Approaches to Outcome Determination in Judgment Aggregation. |
|---|---|
| المؤلفون: | Conati, Ari, Niskanen, Andreas, Järvisalo, Matti |
| المصدر: | Journal of Artificial Intelligence Research; 2024, Vol. 81, p793-836, 44p |
| مصطلحات موضوعية: | SOCIAL choice, POLYNOMIALS, MACHINE learning, ALGORITHMS, MACHINE theory |
| مستخلص: | Judgment aggregation offers a general 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 judgment aggregation 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Artificial Intelligence Research is the property of AI Access Foundation and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| قاعدة البيانات: | Supplemental Index |
Full Text Finder | ResultId |
1 |
|---|---|
| Header |
edo Supplemental Index 182234216 1060 6 Academic Journal academicJournal 1060.20434570313 |
| PLink |
https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edo&AN=182234216&custid=s6537998&authtype=sso |
| FullText |
Array
(
[Availability] => 0
)
Array ( [0] => Array ( [Url] => https://resolver.ebscohost.com/openurl?custid=s6537998&groupid=main&authtype=ip,guest&sid=EBSCO:edo&genre=article&issn=10769757&ISBN=&volume=81&issue=&date=20240901&spage=793&pages=793-836&title=Journal of Artificial Intelligence Research&atitle=Declarative%20Approaches%20to%20Outcome%20Determination%20in%20Judgment%20Aggregation.&id=DOI:10.1613/jair.1.16595 [Name] => Full Text Finder (s6537998api) [Category] => fullText [Text] => Full Text Finder [Icon] => https://imageserver.ebscohost.com/branding/images/FTF.gif [MouseOverText] => Full Text Finder ) ) |
| Items |
Array
(
[Name] => Title
[Label] => Title
[Group] => Ti
[Data] => Declarative Approaches to Outcome Determination in Judgment Aggregation.
)
Array ( [Name] => Author [Label] => Authors [Group] => Au [Data] => <searchLink fieldCode="AR" term="%22Conati%2C+Ari%22">Conati, Ari</searchLink><br /><searchLink fieldCode="AR" term="%22Niskanen%2C+Andreas%22">Niskanen, Andreas</searchLink><br /><searchLink fieldCode="AR" term="%22Järvisalo%2C+Matti%22">Järvisalo, Matti</searchLink> ) Array ( [Name] => TitleSource [Label] => Source [Group] => Src [Data] => Journal of Artificial Intelligence Research; 2024, Vol. 81, p793-836, 44p ) Array ( [Name] => Subject [Label] => Subject Terms [Group] => Su [Data] => <searchLink fieldCode="DE" term="%22SOCIAL+choice%22">SOCIAL choice</searchLink><br /><searchLink fieldCode="DE" term="%22POLYNOMIALS%22">POLYNOMIALS</searchLink><br /><searchLink fieldCode="DE" term="%22MACHINE+learning%22">MACHINE learning</searchLink><br /><searchLink fieldCode="DE" term="%22ALGORITHMS%22">ALGORITHMS</searchLink><br /><searchLink fieldCode="DE" term="%22MACHINE+theory%22">MACHINE theory</searchLink> ) Array ( [Name] => Abstract [Label] => Abstract [Group] => Ab [Data] => Judgment aggregation offers a general 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 judgment aggregation 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. [ABSTRACT FROM AUTHOR] ) Array ( [Name] => Abstract [Label] => [Group] => Ab [Data] => <i>Copyright of Journal of Artificial Intelligence Research is the property of AI Access Foundation and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) ) |
| RecordInfo |
Array
(
[BibEntity] => Array
(
[Identifiers] => Array
(
[0] => Array
(
[Type] => doi
[Value] => 10.1613/jair.1.16595
)
)
[Languages] => Array
(
[0] => Array
(
[Code] => eng
[Text] => English
)
)
[PhysicalDescription] => Array
(
[Pagination] => Array
(
[PageCount] => 44
[StartPage] => 793
)
)
[Subjects] => Array
(
[0] => Array
(
[SubjectFull] => SOCIAL choice
[Type] => general
)
[1] => Array
(
[SubjectFull] => POLYNOMIALS
[Type] => general
)
[2] => Array
(
[SubjectFull] => MACHINE learning
[Type] => general
)
[3] => Array
(
[SubjectFull] => ALGORITHMS
[Type] => general
)
[4] => Array
(
[SubjectFull] => MACHINE theory
[Type] => general
)
)
[Titles] => Array
(
[0] => Array
(
[TitleFull] => Declarative Approaches to Outcome Determination in Judgment Aggregation.
[Type] => main
)
)
)
[BibRelationships] => Array
(
[HasContributorRelationships] => Array
(
[0] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Conati, Ari
)
)
)
[1] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Niskanen, Andreas
)
)
)
[2] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Järvisalo, Matti
)
)
)
)
[IsPartOfRelationships] => Array
(
[0] => Array
(
[BibEntity] => Array
(
[Dates] => Array
(
[0] => Array
(
[D] => 01
[M] => 09
[Text] => 2024
[Type] => published
[Y] => 2024
)
)
[Identifiers] => Array
(
[0] => Array
(
[Type] => issn-print
[Value] => 10769757
)
)
[Numbering] => Array
(
[0] => Array
(
[Type] => volume
[Value] => 81
)
)
[Titles] => Array
(
[0] => Array
(
[TitleFull] => Journal of Artificial Intelligence Research
[Type] => main
)
)
)
)
)
)
)
|
| IllustrationInfo |