Goal-Based Collective Decisions: Axiomatics and Computational Complexity

Goal-Based Collective Decisions: Axiomatics and Computational Complexity

Arianna Novaro, Umberto Grandi, Dominique Longin, Emiliano Lorini

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 468-474. https://doi.org/10.24963/ijcai.2018/65

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).
Keywords:
Knowledge Representation and Reasoning: Knowledge Representation and Game Theory ; Social Choice
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Voting