Parameterized Algorithms for Finding a Collective Set of Items

  • Robert Bredereck Technische Universität Berlin
  • Piotr Faliszewski AGH University
  • Andrzej Kaczmarczyk Technische Universität Berlin
  • Dušan Knop Czech Technical University in Prague
  • Rolf Niedermeier Technische Universität Berlin


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.

AAAI Technical Track: Game Theory and Economic Paradigms