I want to model the problem of household formation by a finite number of individuals, each of whom has preferences over sets of housemates. A collection of households is unstable if there is a set of individuals who can all be made happier by leaving their current households and forming a new household together.

More precisely, let ${\cal A}$ be a finite set of individuals and ${\cal P}$ the power set of ${\cal A}$.

For each $A\in{\cal A}$, let $>_A$ be a total ordering on $\lbrace X| A\in X\in {\cal P}\rbrace$.

Given a partition ${\cal X}$ of ${\cal A}$ and an individual $A\in{\cal A}$ write ${\cal X}(A)$ for the (unique) element of ${\cal X}$ that contains $A$.

Then $\cal{X}$ is unstable if there exists $Y\in{\cal P}-{\cal X}$ such that for all $A\in Y$, $Y>_A{\cal X}(A)$. A partition is stable if it is not unstable.

Here is an example with three individuals and no stable partition:

$$\lbrace A,B\rbrace>_A\lbrace A,C\rbrace >_A \lbrace A\rbrace >_A \lbrace A,B,C\rbrace$$ $$\lbrace B,C\rbrace>_B\lbrace A,B\rbrace >_B \lbrace B\rbrace >_B \lbrace A,B,C\rbrace$$ $$\lbrace A,C\rbrace>_C\lbrace B,C\rbrace >_C \lbrace C\rbrace >_C \lbrace A,B,C\rbrace$$

Question 1: Does this question have a name? Obviously it is related to, but not identical with, the stable marriage problem.

Question 2: Are there any general conditions under which it is true but not obvious that a stable partition exists?


This problem has been studied under the name hedonic coalition formation, and your stability notion is called core stability. See this survey by Gerhard Woeginger, arxiv:1212.2236.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.