Problem : Give a worst-case $O(n^2)$ algorithm to determine if a matching is stable. The machinists will be labelled $1$ through $n$ and the welders will be numbered likewise. The input to your algorithm should be an array match so that match[n] gives the index of the welder machinist number $n$ is matched with, and two 2-D arrays prefM and prefW so that prefM[i][j] gives the index of the welder that machinist number $i$ ranked $j$th and similarly for prefW. You may assume that the match array gives a valid perfect matching. Explain clearly why your algorithm runs in worst case time $O(n^2)$.

Problem :

• Suppose we have a stable perfect matching $S$ and machinist $m$ quits. We then find the welder $w$ matched with $m$ and remove $(m, w)$ from $S$. We now modify the definition of instability to account for free welders: $(m, w')$ is an instability with respect to $S$ if there exist $m'$ and $w$ such that $(m, w) \in S$, $(m', w') \in S$ and $m$ prefers $w'$ to $w$ and $w'$ prefers $m$ to $m'$ OR if there is a $w$ such that $(m, w) \in S$ and there is no $m'$ such that $(m', w') \in S$ and $m$ prefers $w'$ to $w$ (the first part is the original definition of instability; the second part says there is also an instability when there is a machinist who prefers a free welder to the welder they are currently matched with).

  Is $S - \{(m, w)\}$ always stable under this new definition? Prove or give a counterexample.

• Suppose we have a stable perfect matching $S$ and a new welder $w$ is hired. The machinists then add $w$ to their preferences; $w$ can be added anywhere in each machinist's preference list.

  • Can the original matching $S$ still be stable with the updated preferences (using the definition of instability that accounts for free welders)? If so, give an example to illustrate; if not the prove that the old matching is always unstable.
  • Is it possible that all machinists must be rematched to restore stability (using the new definition). Again, give an example or prove that there is never a need to rematch all machinists.

Problem : A squash match ("match" here used in the sense of a contest between two sides) between two teams each with $n$ players consists of $n$ individual matches between players from opposite teams so that each player plays in exactly one individual match. Before the match, the teams determine a sequence of players to play in the individual matches. Assuming that the $2n$ players can be ordered by skill (with no ties) and that a player of higher skill always beats a player of lower skill, is it always possible, no matter the skill order, to create the sequences so that neither team can increase the number of individual matches it will win by unilaterally changing its sequence (so the sequences are stable, in some sense)?

For example, if the players on team 1 are A, B, and C and the players on team 2 are X, Y, and Z, the skill order from most to least skilled is A, B, X, Y, Z, C, and team 1's sequence is A, B, C and team 2's is Z, X, Y then A beats Z, B beats X, and Y beats C, making 2 wins total for team 1, and this does not change if team 1 changes its sequence unilaterally or if team 2 changes its sequence unilaterally, so there are stable sequences for the given skill order.

Devise an efficient algorithm to find such stable sequences, explain its worst-case running time, and prove that it is correct, or give an example of a skill order so that there are no stable sequences and explain why there are no stable sequences.

Problem : Suppose that there are two trade unions representing the machinists, each with $n$ members. There are $n$ non-unionized welders. The unions have reached an agreement requiring that any matching must use ${n \over 2}$ machinists from each union (assume $n$ is even). The machinists and welders have preferences as usual and the welders' preferences may have machinists from both unions in any mixed-up order. Because there are more machinists than welders, there will be always be free machnists, and so we modify our notion of stability much as we did before in problems with more welders than machinists: $(m, w')$ is an instability with respect to $S$ if there exist $m'$ and $w$ such that $(m, w) \in S$, $(m', w') \in S$, $m$ prefers $w'$ to $w$, and $w'$ prefers $m$ to $m'$ OR if there is no $w$ such that $(m, w) \in S$ and there is an $m'$ such that $(m', w') \in S$ and $w'$ prefers $m$ to $m'$ (the first part is the original definition of instability; the second part says there is also an instability when there is a welder who prefers a free machinist to the machinist they are currently matched with).

• Using the new definition of stability, is it always possible to find a stable matching with ${n \over 2}$ machinists from each union and all $n$ welders? If not, give an example of preference lists so that there is no stable matching; if so then give an efficient algorithm to find a stable matching, explain what its worst-case asymptotic running time is, and prove that it is correct.
• Suppose we further update the definition of stability to account for the unions' agreement: $(m, w')$ is an instability with respect to $S$ if there exist $m'$ and $w$ such that $m$ and $m'$ are in the same union, $(m, w) \in S$, $(m', w') \in S$, $m$ prefers $w'$ to $w$, and $w'$ prefers $m$ to $m'$ OR if there is no $w$ such that $(m, w) \in S$ and there is an $m'$ such that $m$ and $m'$ are in the same union, $(m', w') \in S$, and $w'$ prefers $m$ to $m'$.

  Now is it always possible to find a stable matching? If not, give an example of preference lists so that there is no stable matching; if so then give an efficient algorithm to find a stable matching, explain what its worst-case asymptotic running time is, and prove that it is correct.

---