An agreeable subset is a subset of items that is considered, by all people in a certain group, to be at least as good as its complement. 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. Since their car is limited in size, they cannot pick all items, so they have to agree on a subset of items which are most important. If they manage to find a subset of items such that all family members agree that it is at least as good as the subset of items remaining at home, then this subset is called agreeable.
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. Subject to that, the committee size should be as small as possible.
There is a set S containing m objects. There are n agents who have to choose a subset of S. Each agent is characterized by a preference-relation on subsets of S. The preference-relation is assumed to be monotone - an agent always weakly prefers a set to all its subsets. A subset T of S is called agreeable if all agents prefer T to S\T.
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.
As an example, suppose there are two objects - bread and wine, and two agents - Alice and George. The preference-relation of Alice is > > > . If the preference-relation of George is the same, then there are two agreeable subsets: and . But if George's preference-relation is > > >, then the only agreeable subset is .
If the agents' preference relations on the subsets are given, it is easy to check whether a subset is agreeable. But often, only the agents' preference relations on individual objects are given. In this case, it is often assumed that the agents' preferences are not only monotone but also responsive. A subset T of S is called necessarily agreeable if all agents prefer T to S\T according to the responsive set extension of their preferences on individual objects.
A closely related property of subsets is:
To satisfy property (*), the subset T should contain the best object in S; at least two of the three best objects in S; at least three of the five best objects in S; etc.
If a subset T satisfies (*) for all agents, then it is necessarily-agreeable. The converse implication holds if the agents' preference relations on indivisible objects are strict.[3] [4]
What is the smallest agreeable subset that we can find?
Consider first a single agent. In some cases, an agreeable subset should contain at least
\lceilm/2\rceil
\lceilm/2\rceil
(this is because S\V1 contains V2 and S\V2 contains V1 and the preferences are monotone).
This can be generalized: For any n agents and m objects, there always exists an agreeable subset of size
\lfloor
| m+n | |
| 2 |
\rfloor
k:=\lfloor
| m+n | |
| 2 |
\rfloor
KG(m,m-k)
m-2(m-k)+2=n+1
When there are at most three agents, and their preferences are responsive, an agreeable subset of size
\lfloor
| m+n | |
| 2 |
\rfloor
When there are any number of agents with additive utilities, or a constant number of agents with monotone utilities, an agreeable subset of size
\lfloor
| m+n | |
| 2 |
\rfloor
When there are two agents with responsive preferences, a necessarily-agreeable subset of size
\lfloor
| m+n | |
| 2 |
\rfloor
When there are n ≥ 3 agents with responsive preferences, a necessarily-agreeable subset of this size might not exist. However, there always exists a necessarily-agreeable subset of size
m/2+(n+1)\lceil4nlog{m}\rceil
m/2+(log3{m})/4
There exists a randomized algorithm that computes a necessarily-agreeable subset of size
m/2+O(\sqrt{m})
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.