Each question is out of 2.5, for a total of 10 marks overall. For questions about the assignment or about the marking scheme, please contact Theresa at theresa (dot) deering (at) mail.mcgill.ca. View the questions here.
Most people correctly answered unstable for A1 and stable for A2. The only common error was using only one case of instability (either the case where one man is single or the case where both men have partners) when proving A2's stable solution.
A1: An unstable solution may occur using this algorithm.
The easiest way to prove this statement is by counterexample.
Suppose there are two men, M1 and M2, and only one woman, W. M1 and M2 both have preference list {W}, and W has preference list {M2, M1}. Let M1 propose first.
M1 proposes
W accepts
The algorithm terminates.
At this point W is married to M1 when she prefers to be married to M2, and M2 is single when he prefers to be married (to W).
This is an unstable solution.
A2: A stable solution is always reached.
Proof by contradiction: Assume that an unstable solution occurs.
This means that there exists a man M that prefers woman W over his current situation (either married to another woman or single).
If M has not proposed to W by the end of the algorithm this means that his current partner (or being single) must be higher on his list of preferences than W. A contradiction.
If M has proposed to W at some point during the execution of this algorithm then he was rejected by W in favour of some man X whom W prefers to M. Her current partner is either X or some man that she prefers over X (hence, she prefers him over M as well). A contradiction.
Therefore, a stable solution is always reached.
Overall I was impressed that most people correctly identified that this problem is just an application of the stable marriage problem.
For solution, see here.
Not many people managed to handle all the cases to prove P3.
a (P2):
Let B be an admissible subset. By definition, this means that there is some matching M in G that contains all the vertices in B (M may contain other vertices as well). In other words, B is a subset of M.
If A is a subset of B and B is a subset of M, then by transitivity A is a subset of M. This means that the matching M in G contains all the vertices in A.
Therefore, A is admissible.
a (P3):
Let A and B be admissible subsets and let |A| < |B|. By definition, this means that there are some matchings M1 and M2 in G that contain all of the vertices in A and B, respectively.
Case I: M1 U M2 is a matching, let's call it
M3.
M1 is a subset of M3, and M2 is a subset of
M3.
All the elements of A are in M1 and all the elements
of M1 are in M3, so by transitivity all the elements
of A are in M3.
All elements x in B\A are in B, all
elements in B are in M2, and all elements in
M2 are in M3. So by transitivity all elements x
are in M3.
Therefore, all the elements of A U {x} are in the
matching M3, and A U {x} is admissible.
Case II: M1 U M2 is not a matching.
Since |B| > |A| then there is at least one element
x in B\A that is not matched by M2 with
an element in A (otherwise there would be the same number of
elements in A and in B). Therefore, the edge
{x, y} where y is the vertex matched with
x by M2 can be added to M1 to form a new
matching, call this M4.
All elements of A are in M1 and all elements of
M1 are in M4. So all the elements of A are in
M4.
x is a member of the edge {x, y}, which is a
member the matching M4.
Therefore, all the elements of A U {x} are in the
matching M4, and A U {x} is admissible.
b: There are many possible correct answers. This is just one example.
Note that a common mistake with this question was to add weights to the edges of the graph rather than the vertices. For the weighted selection problem, the weights must be assigned to the elements of the set S.
Let each vertex be a person interested in meeting exactly one new friend, and let there be an edge between two vertices if those two people are willing to becomes friends with one another. Each person is willing to pay some number of dollars in order to meet a suitable new friend; this is the weight on each vertex.
Suppose you are an agency that is in charge of pairing up people to become friends. You are only paid by the people that you accept into your program and you can only accept a person p into your program if you know that there exists a pairing of people (i.e. a matching) such that p can meet a new friend. Find the set of people to accept into your program that maximizes the amount of money you will make.
For this question it is not enough to just order the jobs by weight and it is not enough to just order the jobs by time; you need to take both into consideration to get the optimal solution.
For solution, see here.