"The traditional form of the algorithm is optimal for the initiator of the proposals and the stable, suitor-optimal solution may or may not be optimal for the reviewer of the proposals."
"The traditional form of the algorithm is optimal for the initiator of the proposals and the stable, suitor-optimal solution may or may not be optimal for the reviewer of the proposals."
Assume a preference function P(s: student, x: school) -> [0,1]. Consider a matching M(s: student) -> x: school. We can define the utility U{M} = sum[s over all students](P(s, M(s)). The function M which maximizes U may not be unique.
Now consider a random weighting function W(s: student) -> [0,1]. For any r >= 0, we can consider the r-biased utility under X to be U(r, W){M} = sum[s over all students]((1 + r W(s))P(s, M(s))). I then define an optimal matching under the weighting X to be the pair (M, r) such that: -U(r, W) has a unique matching which produces a maximal utility, which is M -for all q < r, q >= 0, U(q, W) either does not have such a matching or the matching is equivalent to M
Of course if a matching exists for r = 0 then no weighting is required, but this is not guaranteed even for only two students going to two schools.
Anyway, since M is a global maximum of U(W, r) in the space of matching functions, it is automatically Pareto-optimal, thus solving the swapping question. And because it is not possible to predict r without knowing everyone's preferences and the weighting function, gaming the system should be intractable without supernatural intervention. It is also optimal with respect to W because bias is minimized, although optimizing over possible choices of W is intractable. One way to generate W(s) is to perform a Fisher-Yates shuffle and assign W(s_0) = 1/S, W(s_1) = 2/S, etc, where S is the number of students. In this case an optimal matching is guaranteed to exist in the limit of large r (proof left as an exercise to the reader).
However, I do not have a procedure to calculate (r, M) for minimal r.
... which is politics in a nutshell. That's partly why I support the complete privatisation of education, at all levels.
https://mises.org/library/what-if-public-schools-were-abolis...