More Effort Towards Multiagent Knapsack

In this paper, we study two multiagent variants of the knapsack problem. Fluschnik et al. [AAAI 2019] studied the model in which each agent expresses its preference by assigning a utility to every item. They studied three preference aggregation rules for finding a subset (knapsack) of items: individually best, diverse, and Nash welfare-based. Informally, diversity is achieved by satisfying as many agents as possible. Motivated by the application of aggregation operators in multiwinner elections, we extend the study from diverse aggregation rule to Median and Best scoring functions. We study the computational and parameterized complexity of the problem with respect to some natural parameters, namely, the number of agents, the number of items, and the distance from an easy instance. We also study the complexity of the problem under domain restrictions. Furthermore, we present significantly faster parameterized algorithms with respect to the number of agents for the diverse aggregation rule.