OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Goal-Based Collective Decisions: Axiomatics and Computational Complexity

Novaro, Arianna and Grandi, Umberto and Longin, Dominique and Lorini, Emiliano Goal-Based Collective Decisions: Axiomatics and Computational Complexity. (2018) In: 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), 13 July 2018 - 19 July 2018 (Stockholm, Sweden).

[img]
Preview
(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
260kB

Official URL: https://doi.org/10.24963/ijcai.2018/65

Abstract

We study agents expressing propositional goals over a set of binary issues to reach a collective decision. We adapt properties and rules from the literature on Social Choice Theory to our setting, providing an axiomatic characterisation of a majority rule for goal-based voting. We study the computational complexity of finding the outcome of our rules (i.e., winner determination), showing that it ranges from Nondeterministic Polynomial Time (NP) to Probabilistic Polynomial Time (PP).

Item Type:Conference or Workshop Item (Paper)
Additional Information:https://www.ijcai.org/proceedings/2018/65
HAL Id:hal-02316858
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Statistics:download
Deposited On:27 Sep 2019 14:06

Repository Staff Only: item control page