Finding a small agreeable subset is a problem in computational social choice.
[1][2] An example situation in which this problem arises is when a family goes on a trip and has to decide which items to take.
Another use case is when the citizens in some city want to elect a committee from a given pool of candidates, such that all citizens agree that the subset of elected candidates is at least as good as the subset of non-elected ones.
If an agent's preference relation is represented by a subadditive utility function u, then for any agreeable subset T, u(T) ≥ u(S)/2.
[2] As an example, suppose there are two objects - bread and wine, and two agents - Alice and George.
In this case, it is often assumed that the agents' preferences are not only monotone but also responsive.
The converse implication holds if the agents' preference relations on indivisible objects are strict.
This can be generalized: For any n agents and m objects, there always exists an agreeable subset of size
, and it is tight (for some preferences this is the smallest size of an agreeable subset).
; this means that, in the n-coloring just defined, there are two adjacent vertices with the same color.
In other words, there are two disjoint subsets such that, a single agent i prefers each of them to its complement.
can be computed in polynomial time, using polynomially-many queries of the form "which of these two subsets is better?".
[2]: Thm.2-3 When there are any number of agents with additive utilities, or a constant number of agents with monotone utilities, an agreeable subset of size
can be found in polynomial time using results from consensus halving.
[5] When there are two agents with responsive preferences, a necessarily-agreeable subset of size
When there are n ≥ 3 agents with responsive preferences, a necessarily-agreeable subset of this size might not exist.
On the other hand, for every m which is a power of 3, there exist ordinal preferences of 3 agents such that every necessarily-agreeable subset has size at least
There exists a randomized algorithm that computes a necessarily-agreeable subset of size
[2]: Thm.4-6 In many cases, there may exist an agreeable subset that is much smaller than the worst-case upper bound.
For agents with general monotone preferences, there is no algorithm that computes a smallest agreeable set using a polynomial number of queries.
Moreover, for every constant c, there is no algorithm that makes at most mc/8 queries and finds an agreeable subset with expected size at most m/(c log m) of the minimum, even with only one agent.
This is tight: there exists a polynomial-time algorithm that finds an agreeable subset with size at most O(m / log m) of the minimum.
Even for agents with additive utilities, deciding whether there exists an agreeable subset of size m/2 is NP-hard; the proof is by reduction from the balanced partition problem.
For any fixed of additive agents, there exists a pseudopolynomial time for this problem; but if the number of agents is not fixed, then the problem is strongly NP-hard.
There exists a polynomial-time O(log n) approximation algorithm.