Suppose that a population of size 3n is partitioned into three subsets: n contractors, n carpenters, and n plumbers. Each person in this population has two preference relations: a preference relation over each one of the two subsets listed above to which he does not belong. For example, each contractor has a preference relation over the set of carpenters, and a preference relation over the set of plumbers, and so on. A matching A in this case is a partition of the population into n triples, each composed of a contractor, a carpenter, and a plumber. A trio composed of a contractor x, a carpenter y, and a plumber z has an objection to A if

(a) the matching A does not contain the set {x, y,z}, and

(b) every pair of workers within this trio who are not matched to each other under A prefer each other to the corresponding workers to whom they have been matched under A.

In other words, x prefers y to the carpenter to whom he is matched under A (if he is matched to a carpenter other than y), x prefers z to the plumber to whom he is matched under A (if he is matched to a plumber other than z), y prefers x to the contractor to whom he is matched under A (if he is matched to a contractor other than x), and so on.

A matching is stable if there is no trio composed of a contractor, a carpenter, and a plumber who object to it.

Does there always exist a stable matching in this model?

If your answer is no, provide a counterexample. If your answer is yes, provide an algorithm for finding a stable matching, and prove that this algorithm always terminates in finding a stable matching.