Efficiently Computing Smallest Agreeable Sets Article Swipe

PDF

Related Concepts

parameterized complexity complement (music) set (abstract data type) rank (graph theory) computer science combinatorics mathematics existential quantification theoretical computer science discrete mathematics gene phenotype programming language biochemistry complementation chemistry

Robert Bredereck , Till Fluschnik , Nimrod Talmon ·

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.3233/faia230285 · OA: W4387185267

We study the computational complexity of identifying a small agreeable subset of items. A subset of items is agreeable if every agent does not prefer its complement set. We study settings in which agents either can assign arbitrary utilities to the items; can approve or disapprove the items; or can rank the items (in which case we consider Borda utilities). We prove that deciding whether an agreeable set exists is NP-hard for all variants; and we perform a parameterized analysis regarding the following natural parameters: the number of agents, the number of items, and the upper bound on the size of the agreeable set in question.