Parameterized Algorithms for Finding a Collective Set of Items - Bredereck, Robert; Faliszewski, Piotr; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (Proceedings of the AAAI Conference on Artificial Intelligence, 2020)
We extend the work of Skowron et al. (AIJ, 2016) by considering the parameterized complexity of the following problem. We are given a set of items and a set of agents, where each agent assigns an integer utility value to each item. The goal is to find a set of k items that these agents would collectively use. For each such collective set of items, each agent provides a score that can be described using an OWA (ordered weighted average) operator and we seek a set with the highest total score. We focus on the parameterization by the number of agents and we find numerous fixed-parameter tractability results (however, we also find some W[1]-hardness results). It turns out that most of our algorithms even apply to the setting where each agent has an integer weight.