Question

State a complete proof or disprove with an explicit counterexample:

a) Every stable matching is also Pareto optimal.

b) Every Pareto optimal matching is also stable.

Answer 1

a) Every stable matching is also Pareto optimal.

Ans:-

A matching is stable when there does not exist any match (A, B) which both prefer each other ton their current partner under the matching. A stable matching always exists, and the  algorithmic problem solved by the Gale–Shapley algorithm is to find one.

An individually rational matching z extends the individually rational matching x if z is a weak Pareto improvement of x. If z and x are simple we say that z is a simple extension of x. A matching x is Pareto- simple if it is simple and does not have any simple extension.

That is, matching x is Pareto- simple if it is simple and it is not weaklydominated by any other simple matching. Pareto-simple matchings always exist since the set of simple matchings is non-empty, finite and preferences are transitive. The following example, due to Gale and Shapley (1962), shows that the set of Pareto-simple matchings may be disjoint from the set of Pareto-optimal matchings, as well as from the set of Pareto-stable matchings.

Ex:-

Consider the Roommate model where the set of boys is N={1,2,3,4}.

The boys’ preferences over acceptable partners are given by:

P(1)=2,3,4,1 P(3)=1,2,4,3 P(2)=3,1,4,2 P(4)=arbitrary The set of Pareto-stable matchings is empty.

There is no Pareto-simple matching that is Pareto-optimal. In fact, matching x where every agent is unmatched is the only simple matching because any other matching has a blocking pair where at least one boy is matched. Then it is Pareto-simple.

However, it is not Pareto-optimal since it is weakly dominated by,

for example,

matching x 1 , which matches 1 to 2 and 3 to 4. Matching x 1 is Pareto-optimal but it is not simple.

The set of Pareto-optimal matchings also includes x 2 , which matches 1 to 3 and 2 to 4 and x 3 which matches 1 to 4 and 3 to 2.

b) Every Pareto optimal matching is also stable.

Ans:-

In this case, the condition of stability is that no unmatched pair prefer each other to their situation in the matching (whether that situation is another partner or being unmatched). With this condition, astable matching will still exist.

Ex:-

Consider a decentralized setting where a set of eight boys, 1,2,…,8, wish divide up into pairs of roommates. The boys’ preferences over acceptable partners are represented by the following ordered lists, where P(j) denotes boy j’s list for all j=1,…,8: P(1)=8, 2, 1 P(5)=8, 6, 5 P(2)=[3, 1], 2 P(6)=[3, 5], 6 P(3)=2,6, 4, 3 P(7)=4, 8, 7 P(4)=[3, 7], 4 P(8)= [1, 5, 7], 8

The brackets in the preference lists of boys 2, 4, 6 and 8 mean that these agents are indifferent among the boys inside the brackets. The matching z, where z(1)=2, z(3)=4, z(5)=6, z(7)=8, doesn’t have any blocking pair, so it is stable. This means that no two boys can be both better off by becoming roommates.