Bring ideas together without being told which method to use. Show the reasoning that makes your result valid.
Suggested session length: 100 minutes, as an unvalidated planning estimate. This collection contains 3 tasks; choose a manageable set and return for further sessions. Completing the whole collection may take substantially longer. This is a unit assessment, not a full course or AP examination.
Lists run from most to least preferred. Unless a task changes the assumptions, both sides are finite, equally sized, and have complete strict rankings.
Give an explicit witness for an unstable outcome and a universal argument for a general guarantee. Cardinality alone does not certify stability.
Try these unfamiliar cases before opening solutions. Public rubrics support review but do not certify independent proficiency.
Loading saved assessment responses…
0 of 3 tasks have recorded responses. No overall mastery score is assigned.
Three proposers rank receivers as A: X>Y>Z, B: Y>Z>X, C: Z>X>Y. Receivers rank proposers as X: B>C>A, Y: C>A>B, Z: A>B>C. Enumerate every perfect matching, classify it as stable or give a blocking pair, and trace deferred acceptance with each side proposing. Is every stable outcome produced by one of those two choices of proposing side? Compare each person’s rank across all stable outcomes; explain why a stable outcome need not maximize everybody’s satisfaction.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A programmer makes acceptance permanent as soon as a free receiver sees a proposal. For A: X>Y, B: X>Y, X: B>A, Y: A>B, simulate A proposing before B and test the result. Repair the rule and explain the invariant restored. Then consider incomplete mutually acceptable lists in which both A and B list only X, X ranks B>A, and Y has no acceptable partner; unmatched is worse than an acceptable partner. Describe a stable partial outcome and explain why the earlier completeness proof fails. Finally, if everyone is indifferent between both opposite-side people, distinguish weak stability (both strictly improve) from a blocking rule allowing one strict improvement and one indifference.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Under equal finite sides and complete strict preferences, let M be the proposer-optimal stable matching and N any stable matching. Prove that every receiver weakly prefers their partner in N to their partner in M: if a receiver instead strictly preferred their M-partner, use proposer optimality to find a blocking pair in N. Apply the symmetric result to receiver-proposing deferred acceptance. Deduce that the stable matching is unique if and only if the two proposing directions return the same pairs. State why this test does not mean different proposal schedules on the same proposing side can choose arbitrary stable outcomes.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Review and revisit
Use each rubric to identify a valid argument, a missing condition or a step to revise. For independent evaluation, ask a teacher or reviewer to examine the complete reasoning. Self-review and recorded responses are not verified assessment results.
Coverage and targeted lesson returns
Three proposers rank receivers as A: X>Y>Z, B: Y>Z>X, C: Z>X>Y. Receivers rank proposers as X: B>C>A, Y: C>A>B, Z: A>B>C. Enumerate every perfect matching, classify it as stable or give a blocking pair, and trace deferred acceptance with each side proposing. Is every stable outcome produced by one of those two choices of proposing side? Compare each person’s rank across all stable outcomes; explain why a stable outcome need not maximize everybody’s satisfaction.
A programmer makes acceptance permanent as soon as a free receiver sees a proposal. For A: X>Y, B: X>Y, X: B>A, Y: A>B, simulate A proposing before B and test the result. Repair the rule and explain the invariant restored. Then consider incomplete mutually acceptable lists in which both A and B list only X, X ranks B>A, and Y has no acceptable partner; unmatched is worse than an acceptable partner. Describe a stable partial outcome and explain why the earlier completeness proof fails. Finally, if everyone is indifferent between both opposite-side people, distinguish weak stability (both strictly improve) from a blocking rule allowing one strict improvement and one indifference.
Under equal finite sides and complete strict preferences, let M be the proposer-optimal stable matching and N any stable matching. Prove that every receiver weakly prefers their partner in N to their partner in M: if a receiver instead strictly preferred their M-partner, use proposer optimality to find a blocking pair in N. Apply the symmetric result to receiver-proposing deferred acceptance. Deduce that the stable matching is unique if and only if the two proposing directions return the same pairs. State why this test does not mean different proposal schedules on the same proposing side can choose arbitrary stable outcomes.
