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
TypeArticle accepté pour publication ou publié
Journal nameArtificial Intelligence
MetadataShow full item record
Department of Automatics [AGH-UST]
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 / KeywordsProportional representation; Ordered weighted average; Chamberlin–Courant rule; Computational complexity; Computational social choice; Approximation; Elections; Voting
Showing items related by title and author.