Agreeable subset
Agreeable subset
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.
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.
Definitions ### Agreeable subset 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.
Worst-case bounds on agreeable subset size What is the smallest agreeable subset that we can find?
Agreeable subsets Consider first a single agent. In some cases, an agreeable subset should contain at least <math>\lceil m/2 \rceil</math> objects. An example is when all m objects are identical. Moreover, there always exists an agreeable subset containing <math>\lceil m/2 \rceil</math> objects. This follows from the following lemma:
- For every agent i, if two subsets V1 and V2 are disjoint, then at least one of S\V1 or S\V2 is agreeable to i.
(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 <math>\bigg\lfloor \frac{m+n}{2} \bigg\rfloor</math>, and it is tight (for some preferences this is the smallest size of an agreeable subset). The proof for two agents is constructive. The proof for n agents uses a Kneser graph. Let <math>k := \bigg\lfloor \frac{m+n}{2} \bigg\rfloor</math>, and let G be the Kneser graph <math>KG(m, m-k)</math>, that is, the graph whose vertices are all subsets of m-k objects, and two subsets are connected iff they are disjoint. If there is a vertex V such that all agents prefer S\V to V, then S\V is an agreeable subset of size k. Otherwise, we can define a color for each agent and color each vertex V of G with an agent who prefers V to S\V. By the theorem on chromatic number of Kneser graphs, the chromatic number of G is <math>m-2(m-k)+2 = n+1</math>; 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. But this contradicts the above lemma. Hence there must be an agreeable subset of size k.
Necessarily-agreeable subsets When there are two agents with responsive preferences, a necessarily-agreeable subset of size <math>\bigg\lfloor \frac{m+n}{2} \bigg\rfloor</math> exists and can be computed in polynomial time.
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 <math>m/2+(n+1)\lceil 4 n \log{m} \rceil</math>, and such a set can be computed in polynomial time. 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 <math>m/2+(\log_3{m})/4</math>. Both proofs use theorems on Discrepancy of permutations.
There exists a randomized algorithm that computes a necessarily-agreeable subset of size <math>m/2+O(\sqrt{m})</math>.