Title: Computing an Approximately Optimal Agreeable Set of Items,
Abstract: We study the problem of finding a small subset of items that is
\emph{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.