Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability.
Gianluigi, Greco; Lang, Jérôme (2015), Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability., in Yang, Qiang; Wooldridge, Michael, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), AAAI Press / IJCAI : Palo Alto (USA), p. 3008-3014
TypeCommunication / Conférence
Conference title24th International Joint Conference on Artificial Intelligence (IJCAI 2015)
Conference cityBuenos Aires
Book titleProceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)
Book authorYang, Qiang; Wooldridge, Michael
Number of pages4429
MetadataShow full item record
University of Calabria
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)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.
Subjects / Keywordsknowledge representation; social choice
Showing items related by title and author.
Butler, George; Pigozzi, Gabriella; Rouchier, Juliette (2019) Article accepté pour publication ou publié
Logic, Language, and Computation, 7th International Tbilisi Symposium on Logic, Language, and Computation, TbiLLC 2007, Tbilisi, Georgia, October 1-5, 2007. Revised Selected Papers Bosch, Peter; Gabelaia, David; Lang, Jérôme (2009) Communication / Conférence