# Agreeable subset

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Agreeable_subset
> Markdown URL: https://mediated.wiki/source/Agreeable_subset.md
> Source: https://en.wikipedia.org/wiki/Agreeable_subset
> Source revision: 1348277925
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

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](/source/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](/source/Monotone_preferences)* - 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](/source/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](/source/Responsive_preferences). 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 \lceil m/2 \rceil objects. An example is when all *m* objects are identical. Moreover, there always exists an agreeable subset containing \lceil m/2 \rceil objects. This follows from the following lemma:

- For every agent *i*, if two subsets *V*1 and *V*2 are disjoint, then at least one of S\*V*1 or S\*V*2 is agreeable to *i*.

(this is because S\*V*1 contains *V*2 and S\*V*2 contains *V*1 and the preferences are monotone).

This can be generalized: For any *n* agents and *m* objects, there always exists an agreeable subset of size \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](/source/Kneser_graph). Let k := \bigg\lfloor \frac{m+n}{2} \bigg\rfloor, and let *G* be the Kneser graph 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](/source/Kneser_graph#chromatic), the chromatic number of *G* is 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 \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 \bigg\lfloor \frac{m+n}{2} \bigg\rfloor can be found in polynomial time using results from [consensus halving](/source/Exact_division).[5]

### Necessarily-agreeable subsets

When there are two agents with responsive preferences, a *necessarily*-agreeable subset of size \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 m/2+(n+1)\lceil 4 n \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 m/2+(\log_3{m})/4. Both proofs use theorems on [Discrepancy of permutations](/source/Discrepancy_of_permutations).

There exists a [randomized algorithm](/source/Randomized_algorithm) that computes a necessarily-agreeable subset of size 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 *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](/source/Additive_utility), deciding whether there exists an agreeable subset of size *m*/2 is NP-hard; the proof is by reduction from the balanced [partition problem](/source/Partition_problem). For any fixed of additive agents, there exists a [pseudopolynomial time](/source/Pseudo-polynomial_time) for this problem; but if the number of agents is not fixed, then the problem is [strongly NP-hard](/source/Strong_NP-completeness). There exists a polynomial-time O(log *n*) [approximation algorithm](/source/Approximation_algorithm).[2]: Thm.7-13

## Extensions

- The agreeable subset problem was studied with additional constraint represented by a [matroid](/source/Matroid).[6]

## See also

- [Envy-free item allocation](/source/Envy-free_item_allocation)
- [Participatory budgeting algorithm](/source/Participatory_budgeting_algorithm)
- [Multiwinner elections](/source/Multiwinner_elections)
- [Consensus halving](/source/Exact_division)
- [Fair division among groups](/source/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.
- [Cake sharing](/source/Cake_sharing)

## References

1. Suksompong, Warut (2016-07-09). ["Assigning a small agreeable set of indivisible items to multiple players"](https://dl.acm.org/doi/abs/10.5555/3060621.3060690). *Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*. IJCAI'16. New York, New York, USA: AAAI Press. [arXiv:1606.08077](https://arxiv.org/abs/1606.08077). [doi:10.1016/j.artint.2018.10.001](https://doi.org/10.1016/j.artint.2018.10.001). ISBN 978-1-57735-770-4.

1. Manurangsi, Pasin & Suksompong, Warut (2019-03-01). ["Computing a small agreeable set of indivisible items"](https://www.sciencedirect.com/science/article/pii/S0004370218300808). *Artificial Intelligence*. **268**: 96–114. [arXiv:1606.08077](https://arxiv.org/abs/1606.08077). [doi:10.1016/j.artint.2018.10.001](https://doi.org/10.1016/j.artint.2018.10.001). [ISSN 0004-3702](https://www.worldcat.org/issn/0004-3702). [S2CID 124836295](https://api.semanticscholar.org/CorpusID:124836295)

1. Brams, Steven J.; Kilgour, D. Marc; Klamler, Christian (2011). ["The undercut procedure: An algorithm for the envy-free division of indivisible items"](https://mpra.ub.uni-muenchen.de/12774/1/MPRA_paper_12774.pdf). *Social Choice and Welfare*. **39** (2–3): 615. [doi:10.1007/s00355-011-0599-1](https://doi.org/10.1007/s00355-011-0599-1). [S2CID 253844146](https://api.semanticscholar.org/CorpusID:253844146)

1. 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](https://arxiv.org/abs/1312.6546). [doi:10.1016/j.artint.2015.06.002](https://doi.org/10.1016/j.artint.2015.06.002). [S2CID 1408197](https://api.semanticscholar.org/CorpusID:1408197)

1. Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2020). ["Consensus Halving for Sets of Items"](https://link.springer.com/chapter/10.1007/978-3-030-64946-3_27). *Web and Internet Economics*. Vol. 12495. Lecture Notes in Computer Science. Chen, Xujin (ed.). Cham: Springer International Publishing. pp. 384–397. [arXiv:2007.06754](https://arxiv.org/abs/2007.06754). [doi:10.1007/978-3-030-64946-3_27](https://doi.org/10.1007/978-3-030-64946-3_27). ISBN 978-3-030-64946-3.

1. Gourvès, Laurent (2019-04-01). ["Agreeable sets with matroidal constraints"](https://doi.org/10.1007/s10878-018-0327-1). *Journal of Combinatorial Optimization*. **37** (3): 866–888. [doi:10.1007/s10878-018-0327-1](https://doi.org/10.1007/s10878-018-0327-1). [ISSN 1573-2886](https://www.worldcat.org/issn/1573-2886). [S2CID 254654045](https://api.semanticscholar.org/CorpusID:254654045)

---
Adapted from the Wikipedia article [Agreeable subset](https://en.wikipedia.org/wiki/Agreeable_subset) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Agreeable_subset?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.