Abstract
We study the problem of finding a small subset of
items that is agreeable to all agents, meaning that
all agents value the subset at least as much as its
complement. Previous work has shown worst-case
bounds, over all instances with a given number of
agents and items, on the number of items that may
need to be included in such a subset. Our goal
in this paper is to efficiently compute an agreeable subset whose size approximates the size of the
smallest agreeable subset for a given instance. We
consider three well-known models for representing
the preferences of the agents: ordinal preferences
on single items, the value oracle model, and additive utilities. In each of these models, we establish
virtually tight bounds on the approximation ratio
that can be obtained by algorithms running in polynomial time