Finding a collective set of items: From proportional multirepresentation to group recommendation
Skowron, Piotr; Faliszewski, Piotr; Lang, Jérôme (2016), Finding a collective set of items: From proportional multirepresentation to group recommendation, Artificial Intelligence, 241, p. 191-216. 10.1016/j.artint.2016.09.003
Type
Article accepté pour publication ou publiéDate
2016Journal name
Artificial IntelligenceNumber
241Publisher
Elsevier
Pages
191-216
Publication identifier
Metadata
Show full item recordAuthor(s)
Skowron, PiotrOxford University
Faliszewski, Piotr
Department of Automatics [AGH-UST]
Lang, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of K items that maximize the total derived utility of all the agents (i.e., in our example we are to pick K movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.Subjects / Keywords
Proportional representation; Ordered weighted average; Chamberlin–Courant rule; Computational complexity; Computational social choice; Approximation; Elections; VotingRelated items
Showing items related by title and author.
-
Skowron, Piotr; Faliszewski, Piotr; Lang, Jérôme (2015) Communication / Conférence
-
Lang, Jérôme; Skowron, Piotr (2018) Article accepté pour publication ou publié
-
Lang, Jérôme; Skowron, Piotr (2016) Communication / Conférence
-
Do, Virginie; Hervouin, Matthieu; Lang, Jérôme; Skowron, Piotr (2022) Communication / Conférence
-
Faliszewski, Piotr; Gourvès, Laurent; Lang, Jérôme; Lesca, Julien; Monnot, Jérôme (2016) Communication / Conférence