Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability.Reportar como inadecuado




Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability. - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 University of Calabria 2 LAMSADE - Laboratoire d-analyse et modélisation de systèmes pour l-aide à la décision

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.

Mots-clés : knowledge representation social choice





Autor: Greco Gianluigi - Jérôme Lang -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados