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.[2]

As an example, suppose there are two objects - bread and wine, and two agents - Alice and George. The preference-relation of Alice is {bread,wine} > {bread} > {wine} > {}. If the preference-relation of George is the same, then there are two agreeable subsets: {bread,wine} and {bread}. But if George's preference-relation is {bread,wine} > {wine} > {bread} > {}, then the only agreeable subset is {bread,wine}.

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:

• (*) For every k in 1, ..., m, the subset T contains at least k/2 of the best k objects for agent i.

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]

Consider first a single agent. In some cases, an agreeable subset should contain at least ${\displaystyle \lceil m/2\rceil }$ objects. An example is when all m objects are identical. Moreover, there always exists an agreeable subset containing ${\displaystyle \lceil m/2\rceil }$ objects. This follows from the following lemma:

• For every agent i, if two subses V₁ and V₂ are disjoint, then at least one of S\V₁ or S\V₂ is agreeable to i.

(this is because S\V₁ contains V₂ and S\V₂ contains V₁ and the preferences are monotone).

This can be generalized: For any n agents and m objects, there always exists an agreeable subset of size ${\displaystyle {\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}$, 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 ${\displaystyle k:={\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}$, and let G be the Kneser graph ${\displaystyle KG(m,m-k)}$, 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 ${\displaystyle m-2(m-k)+2=n+1}$; 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.[2]^: Thm.1

When there are at most three agents, and their preferences are responsive, an agreeable subset of size ${\displaystyle {\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}$ 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 ${\displaystyle {\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}$ 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 ${\displaystyle {\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}$ 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 ${\displaystyle m/2+(n+1)\lceil 4n\log {m}\rceil }$, 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 ${\displaystyle m/2+(\log _{3}{m})/4}$. Both proofs use theorems on Discrepancy of permutation hypergraphs.

There exists a randomized algorithm that computes a necessarily-agreeable subset of size ${\displaystyle m/2+O({\sqrt {m}})}$.[2]^: Thm.4-6