More effort towards multiagent knapsack

DOI10.1007/978-3-031-23101-8_4MaRDI QIDQ6169510zbMATH OpenOpenAlexFDO

Authors Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman

Publication date 14 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.02766

zbMATH Keywords

complexitysocial choicevoting

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Social choice (91B14)

Abstract: In this paper, we study some multiagent variants of the knapsack problem. Fluschnik et al. [AAAI 2019] considered the model in which every agent assigns some 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 voters 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 voters, 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 voters for the diverse aggregation rule.

Recommendations

• Solving multi-agent knapsack problems using incremental approval voting
• Multiagent resource allocation in k-additive domains: preference representation and complexity
• Cooperative and axiomatic approaches to the knapsack allocation problem
• On a cooperative game in the knapsack problem
• DP-based algorithm and FPTAS for the knapsack sharing and related problems

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• Approximating optimal social choice under metric preferences
• Axiomatic characterization of committee scoring rules
• Exact and approximate bandwidth
• Finding a collective set of items: from proportional multirepresentation to group recommendation
• Fundamentals of parameterized complexity
• Gerrymandering on graphs: computational complexity and parameterized algorithms
• scientific article; zbMATH DE number 3709576 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 7657254 (Why is no real title available?)
• Optimal social choice functions: a utilitarian view
• Parameterized algorithms
• Properties of multiwinner voting rules
• Randomized social choice functions under metric preferences
• Voting almost maximizes social welfare despite limited communication

This page was built for publication: More effort towards multiagent knapsack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169510)