Show simple item record

Conference Program Design with Single-Peaked and Single-Crossing Preferences

hal.structure.identifierSchool of Electrical and Computer Engineering, National Technical University of Athens [ICCS]
dc.contributor.authorFotakis, Dimitris
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGourvès, Laurent
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2017-01-06T15:34:20Z
dc.date.available2017-01-06T15:34:20Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16132
dc.language.isoenen
dc.subjectchoix social computationnelen
dc.subject.ddc006.3en
dc.titleConference Program Design with Single-Peaked and Single-Crossing Preferencesen
dc.typeCommunication / Conférence
dc.description.abstractenWe consider the Conference Program Design (CPD) problem, a multi-round generalization of (the maximization versions of) q-Facility Location and the Chamberlin-Courant multi-winner election, introduced by (Caragiannis, Gourvès and Monnot, IJCAI 2016). CPD asks for the selection of kq items and their assignment to k disjoint sets of size q each. The agents receive utility only from their best item in each set and we want to maximize the total utility derived by all agents from all sets. Given that CPD is NP-hard for general utilities, we focus on utility functions that are either single-peaked or single-crossing. For general single-peaked utilities, we show that CPD is solvable in polynomial time and that Percentile Mechanisms are truthful. If the agent utilities are given by distances in the unit interval, we show that a Percentile Mechanism achieves an approximation ratio 1 / 3, if q=1, and at least (2q−3)/(2q−1), for any q≥2. On the negative side, we show that a generalization of CPD, where some items must be assigned to specific sets in the solution, is NP-hard for dichotomous single-peaked preferences. For single-crossing preferences, we present a dynamic programming exact algorithm that runs in polynomial time if k is constant.en
dc.identifier.citationpages221-235en
dc.relation.ispartoftitleWeb and Internet Economicsen
dc.relation.ispartofeditorCai, Yang
dc.relation.ispartofeditorVetta, Adrian
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofdate2016
dc.relation.ispartofpages482en
dc.relation.ispartofurl10.1007/978-3-662-54110-4en
dc.subject.ddclabelIntelligence artificielleen
dc.relation.ispartofisbn978-3-662-54109-8en
dc.relation.conftitle12th International Conference, WINE 2016en
dc.relation.confdate2016-12
dc.relation.confcityMontrealen
dc.relation.confcountryCanadaen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-662-54110-4_16en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-01-06T08:18:14Z
hal.identifierhal-01428949*
hal.version1*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record