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.




How to Cite

Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Knop, D., & Niedermeier, R. (2020). Parameterized Algorithms for Finding a Collective Set of Items. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1838-1845.



AAAI Technical Track: Game Theory and Economic Paradigms