To elaborate on the example in the article, the main reason that swapping is disallowed is that by necessity, there exists a third student which is screwed by the swap.
The deferred acceptance algorithm always creates a stable matching, which means that it does not contain any blocking pairs. A blocking pair is a pair <student, school> where the student is not assigned to the school, but prefers the school to their current assignment, and the school prefers the student above their worst ranked admitted student.
When executed as described in the article, the algorithm produces a student-optimal solution, which means that for all students, no other stable matching exists where the student is better off.
In the example, where student a preferred school A over B (their current assignment) and student b preferred school B over A (their current assignment), both students would become better off by swapping. Thus, the matching produced after swapping cannot be stable: there must exist some student x who now forms a blocking pair together with either school A or B.
To explain how this happens:
Say that student a is the first to select schools (the iteration order of the students does not matter for the end result, this just makes the steps a bit clearer). Then, at the start, we have this assignment:
A: a
Since a is not assigned to A in the final solution, at some point a has worse rank than all students assigned to A and is pushed out:
A: x, y, z (say that the capacity of A is three)
This means that A ranks x, y and z higher than a. If any subsequent students push out x, y or z, they too will have higher rank than a.
At some point b is then assigned to A. This means that b has higher rank than x, y and z. At least one of them, say x, has been pushed out by now.
If a and b were allowed to swap, then <x, A> would form a blocking pair since x prefers A to their current assignment, and A prefers x to their lowest ranked admitted student (a). Thus the solution would no longer be stable.
I'm confused, why must b push one of x, y, or z out? Why isn't one of x, y, or z already b? Or to put it another way, why can't a be the most-preferred non-accepted student for A?
You are right, I forgot to state an assumption, which is that "a gets pushed out of A" happens before "b gets pushed out of B" (and then goes on to apply to A).
One of those things must happen before the other (each step in the algorithm is a currently-unassigned student applying to their next choice). In your case, if a is the most-preferred non-accepted student for A, then b must have been pushed out of B first, so the argument applies to B instead.
The deferred acceptance algorithm always creates a stable matching, which means that it does not contain any blocking pairs. A blocking pair is a pair <student, school> where the student is not assigned to the school, but prefers the school to their current assignment, and the school prefers the student above their worst ranked admitted student.
When executed as described in the article, the algorithm produces a student-optimal solution, which means that for all students, no other stable matching exists where the student is better off.
In the example, where student a preferred school A over B (their current assignment) and student b preferred school B over A (their current assignment), both students would become better off by swapping. Thus, the matching produced after swapping cannot be stable: there must exist some student x who now forms a blocking pair together with either school A or B.
To explain how this happens:
Say that student a is the first to select schools (the iteration order of the students does not matter for the end result, this just makes the steps a bit clearer). Then, at the start, we have this assignment:
A: a
Since a is not assigned to A in the final solution, at some point a has worse rank than all students assigned to A and is pushed out:
A: x, y, z (say that the capacity of A is three)
This means that A ranks x, y and z higher than a. If any subsequent students push out x, y or z, they too will have higher rank than a.
At some point b is then assigned to A. This means that b has higher rank than x, y and z. At least one of them, say x, has been pushed out by now.
If a and b were allowed to swap, then <x, A> would form a blocking pair since x prefers A to their current assignment, and A prefers x to their lowest ranked admitted student (a). Thus the solution would no longer be stable.