Show simple item record

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

dc.contributor.authorGianluigi, Greco
dc.contributor.authorLang, Jérôme
dc.date.accessioned2017-03-30T15:26:10Z
dc.date.available2017-03-30T15:26:10Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16471
dc.language.isoenen
dc.subjectknowledge representationen
dc.subjectsocial choiceen
dc.subject.ddc003en
dc.titleGroup Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability.en
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages3008-3014en
dc.relation.ispartoftitleProceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)en
dc.relation.ispartofeditorYang, Qiang
dc.relation.ispartofeditorWooldridge, Michael
dc.relation.ispartofpublnameAAAI Press / IJCAIen
dc.relation.ispartofpublcityPalo Alto (USA)en
dc.relation.ispartofdate2015
dc.relation.ispartofpages4429en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-1-57735-738-4en
dc.relation.conftitle24th International Joint Conference on Artificial Intelligence (IJCAI 2015)en
dc.relation.confdate2015-07
dc.relation.confcityBuenos Airesen
dc.relation.confcountryArgentinaen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-03-30T12:12:50Z
hal.person.labIds146682
hal.person.labIds989
hal.identifierhal-01498923*


Files in this item

Thumbnail
Name:
Group-Decision_ijcai15.pdf
Size:
704.3Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record