Consider a variation of the Stable Matching problem where we have a set P of n positions and a set

A of n applicants being considered for the positions. In this case, each position and each applicant

are not required to give each of their possible matches a distinct ranking, i$.$e$.,$ their preference lists

may include ties. When we have ties like this, we say that p strictly prefers a

$$

to a to mean that

a

$$

is ranked strictly higher than a$,($in other words a

$$

is not ranked lower than or tied with a$).$ In

this problem, an instability in a matching S occurs if:

There are two pairs $($p$,$ a$)$ and $($p

$$

$,$ a$$

$)$ in S such that p strictly prefers a

$$

to a$,$ and a

$$

strictly prefers p to p

$$

$.$

Prove that a stable matching always exists for any set of preference lists $($even with possible ties$).$

$($Hint: first come up with a way to run Gale$-$Shapley on these preference lists with ties, then prove

that the resulting matching is stable.$)$