Question

1 universal preference

suppose that preferences in a stable matching instance are universal, i.e., all \\(n\\) jobs share the preferences \\(c_1 > c_2 > \dots > c_n\\) and all candidates share the preferences \\(j_1 > j_2 > \dots > j_n\\).

(a) what matching do we get from running the propose-and-reject algorithm with jobs proposing? prove that this happens for all \\(n\\).

hint: start with small examples and go through the algorithm. do you see a pattern?

(b) what matching do we get from running the propose-and-reject algorithm with candidates proposing? explain.

(c) what does this tell us about the number of stable matchings? justify your answer.

Explanation:

Analyze the job-proposing Gale-Shapley algorithm

In the propose-and-reject (Gale-Shapley) algorithm with jobs proposing:

1. Every job \(J_i\) has the preference list \(C_1 > C_2 > \dots > C_n\).
2. In Round 1, all jobs \(J_1, \dots, J_n\) propose to their top choice, candidate \(C_1\).
3. Candidate \(C_1\) receives proposals from all jobs. Since \(C_1\) prefers \(J_1 > J_2 > \dots > J_n\), \(C_1\) holds onto \(J_1\) and rejects all other jobs \(J_2, \dots, J_n\).
4. In Round 2, the rejected jobs \(J_2, \dots, J_n\) propose to their next choice, candidate \(C_2\).
5. Candidate \(C_2\) receives proposals from all these jobs. Since \(C_2\) prefers \(J_2 > J_3 > \dots > J_n\), \(C_2\) holds onto \(J_2\) and rejects \(J_3, \dots, J_n\).
6. By induction, in Round \(k\), jobs \(J_k, \dots, J_n\) propose to candidate \(C_k\). Candidate \(C_k\) holds onto \(J_k\) and rejects the rest.
7. This process terminates with the matching \(M = \{(J_i, C_i) \mid 1 \le i \le n\}\).

Analyze the candidate-proposing Gale-Shapley algorithm

In the propose-and-reject algorithm with candidates proposing:

1. Every candidate \(C_j\) has the preference list \(J_1 > J_2 > \dots > J_n\).
2. In Round 1, all candidates \(C_1, \dots, C_n\) propose to their top choice, job \(J_1\).
3. Job \(J_1\) receives proposals from all candidates. Since \(J_1\) prefers \(C_1 > C_2 > \dots > C_n\), \(J_1\) holds onto \(C_1\) and rejects all other candidates \(C_2, \dots, C_n\).
4. In Round 2, the rejected candidates \(C_2, \dots, C_n\) propose to their next choice, job \(J_2\).
5. Job \(J_2\) receives proposals from these candidates. Since \(J_2\) prefers \(C_2 > C_3 > \dots > C_n\), \(J_2\) holds onto \(C_2\) and rejects \(C_3, \dots, C_n\).
6. By induction, in Round \(k\), candidates \(C_k, \dots, C_n\) propose to job \(J_k\). Job \(J_k\) holds onto \(C_k\) and rejects the rest.
7. This process terminates with the exact same matching \(M = \{(J_i, C_i) \mid 1 \le i \le n\}\).

Determine the number of stable matchings

1. The job-proposing Gale-Shapley algorithm always yields the job-optimal stable matching.
2. The candidate-proposing Gale-Shapley algorithm always yields the candidate-optimal stable matching.
3. Since both algorithms yield the exact same matching \(M = \{(J_i, C_i) \mid 1 \le i \le n\}\), the job-optimal and candidate-optimal stable matchings coincide.
4. In any stable matching instance, any stable matching \(M'\) lies between the job-optimal and candidate-optimal matchings in the weak-order lattice of stable matchings.
5. Since the upper and lower bounds of this lattice are identical, there is exactly 1 unique stable matching.

By symmetry, when candidates propose, all candidates \(C_1, \dots, C_n\) propose to their top choice, \(J_1\). Job \(J_1\) accepts \(C_1\) and rejects the rest because \(J_1\) prefers \(C_1 > C_2 > \dots > C_n\). In each subsequent step \(k\), the remaining candidates \(C_k, \dots, C_n\) propose to job \(J_k\), which accepts \(C_k\) and rejects the rest. This symmetric process yields the identical matching \(M\).

Question 3

(c) There is exactly \(1\) unique stable matching.

Justification:
The job-proposing Gale-Shapley algorithm yields the job-optimal stable matching, while the candidate-proposing version yields the candidate-optimal stable matching. Since both algorithms result in the same matching \(M\), the job-optimal and candidate-optimal matchings are identical. Because any stable matching must lie between the job-optimal and candidate-optimal matchings, \(M\) is the unique stable matching for this instance.
</answer>

Answer:

Question 1

(a) We get the matching \(M = \{(J_i, C_i) \mid 1 \le i \le n\}\), where each job \(J_i\) is matched with candidate \(C_i\).

Proof:
We prove by induction on the round \(k\) of the algorithm.

• Base case (\(k=1\)): All jobs \(J_1, \dots, J_n\) propose to their first choice, \(C_1\). Since \(C_1\) prefers \(J_1 > J_2 > \dots > J_n\), \(C_1\) accepts \(J_1\) and rejects \(J_2, \dots, J_n\). Thus, \(J_1\) is permanently matched to \(C_1\).
• Inductive step: Assume that for all \(i < k\), job \(J_i\) has been matched to \(C_i\), and candidates \(C_1, \dots, C_{k-1}\) are no longer available. In round \(k\), the remaining unmatched jobs \(J_k, \dots, J_n\) propose to their highest-ranked available candidate, which is \(C_k\). Since \(C_k\) prefers \(J_k > J_{k+1} > \dots > J_n\), \(C_k\) accepts \(J_k\) and rejects \(J_{k+1}, \dots, J_n\). Thus, \(J_k\) is matched to \(C_k\).

By induction, this holds for all \(n\), resulting in the matching \(M = \{(J_i, C_i) \mid 1 \le i \le n\}\).

Question 2

(b) We get the exact same matching \(M = \{(J_i, C_i) \mid 1 \le i \le n\}\).

Explanation:
By symmetry, when candidates propose, all candidates \(C_1, \dots, C_n\) propose to their top choice, \(J_1\). Job \(J_1\) accepts \(C_1\) and rejects the rest because \(J_1\) prefers \(C_1 > C_2 > \dots > C_n\). In each subsequent step \(k\), the remaining candidates \(C_k, \dots, C_n\) propose to job \(J_k\), which accepts \(C_k\) and rejects the rest. This symmetric process yields the identical matching \(M\).

Question 3

(c) There is exactly \(1\) unique stable matching.

Justification:
The job-proposing Gale-Shapley algorithm yields the job-optimal stable matching, while the candidate-proposing version yields the candidate-optimal stable matching. Since both algorithms result in the same matching \(M\), the job-optimal and candidate-optimal matchings are identical. Because any stable matching must lie between the job-optimal and candidate-optimal matchings, \(M\) is the unique stable matching for this instance.