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. ^{[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.

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. ^[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}.

Necessarily-agreeable subset

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]}

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 ${\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]

Necessarily-agreeable subsets

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}

Computing a smallest agreeable subset

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 m^c/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. ^{[2] : Thm.7-13}

Extensions

• The agreeable subset problem was studied with additional constraint represented by a matroid. ^[6]

See also

• Envy-free item allocation
• Participatory budgeting algorithm
• Multiwinner elections
• Consensus halving
• Fair division among groups - a variant of fair division in which the pieces of the resource are given to pre-determined groups rather than to individuals.

References

1. Suksompong, Warut (2016-07-09). "Assigning a small agreeable set of indivisible items to multiple players". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 489–495. arXiv: 1606.08077 . doi:10.1016/j.artint.2018.10.001. ISBN   978-1-57735-770-4.
2. Manurangsi, Pasin; Suksompong, Warut (2019-03-01). "Computing a small agreeable set of indivisible items". Artificial Intelligence. 268: 96–114. arXiv: 1606.08077 . doi:10.1016/j.artint.2018.10.001. ISSN   0004-3702. S2CID   124836295.
3. Brams, Steven J.; Kilgour, D. Marc; Klamler, Christian (2011). "The undercut procedure: An algorithm for the envy-free division of indivisible items" (PDF). Social Choice and Welfare. 39 (2–3): 615. doi:10.1007/s00355-011-0599-1. S2CID   253844146.
4. Aziz, Haris; Gaspers, Serge; MacKenzie, Simon; Walsh, Toby (2015). "Fair assignment of indivisible objects under ordinal preferences". Artificial Intelligence. 227: 71–92. arXiv: 1312.6546 . doi:10.1016/j.artint.2015.06.002. S2CID   1408197.
5. Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2020). Chen, Xujin; Gravin, Nikolai; Hoefer, Martin; Mehta, Ruta (eds.). Consensus Halving for Sets of Items. Lecture Notes in Computer Science. Vol. 12495. Cham: Springer International Publishing. pp. 384–397. arXiv: 2007.06754 . doi:10.1007/978-3-030-64946-3_27. ISBN   978-3-030-64946-3.{{cite book}}: |journal= ignored (help)
6. Gourvès, Laurent (2019-04-01). "Agreeable sets with matroidal constraints". Journal of Combinatorial Optimization. 37 (3): 866–888. doi:10.1007/s10878-018-0327-1. ISSN   1573-2886. S2CID   254654045.