Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability

Greco, Gianluigi; Lang, Jérôme

Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 3008-3013.

Abstract

We study a general class of multiagent optimization problems, together with a compact representation language of utilities based on weighted propositional formulas. We seek solutions maximizing utilitarian social welfare as well as fair solutions maximizing the utility of the least happy agent. We show that many problems can be expressed in this setting, such as fair division of indivisible goods, some multiwinner elections, or multifacility location. We focus on the complexity of finding optimal solutions, and we identify the tractability boarder between polynomial and NP-hard settings, along several parameters: the syntax of formulas, the allowed weights, as well as the number of agents, propositional symbols, and formulas per agent.

Gianluigi Greco, and Jérôme Lang. 2015. Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 3008–3013. https://ijcai.org/proceedings/2015/425

@inproceedings{ijcai2015p425,
  title     = {Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability},
  author    = {Greco, Gianluigi and Lang, Jérôme},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {3008--3013},
  year      = {2015},
  month     = {7},
  note      = {Special Track on Knowledge Representation and Reasoning},
  url       = {https://ijcai.org/proceedings/2015/425},
}

TY  - CPAPER
TI  - Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability
AU  - Greco, Gianluigi
AU  - Lang, Jérôme
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 3008
EP  - 3013
UR  - https://ijcai.org/proceedings/2015/425
ER  -