"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...
If you don't want students to trade because some are better at it than others, you could still do an automated trading round at the end. Start with the students that got their lowest choice (or possibly even no listed choice at all), and check for all of their preferred schools if there are students there that would prefer to be at this student's school.
Every trade would improve efficiency, but because students have no control over it, it wouldn't hurt fairness.
Though listing popular schools high can also be prevented by banning down-trades. But that would still be unfair because skilled traders will still be better at it. Automating it would solve that problem.
Look at figure 4: https://i.imgur.com/TUInR0Q.png
The multiple lottery system, while resulting in less people with their #1 pick, results in a vastly less people not getting in their top 3 picks.
Define a person's unhappiness as one less than the position in their ranking of the person they paired with. If someone is not paired, define their unhappiness as N, where N is the number of men and the number of women being paired.
For example, in a set of 10 men and 10 women, a women paired with her 1st choice man has unhappiness 0. A man in that set not yet paired has unhappiness 10.
The key to understanding Gale-Shapley is female unhappiness (in the version where the men propose to the women...if you do it with women proposing to men, then male unhappiness is the key).
When the algorithm runs a man through the gauntlet and his proposal is tentatively accepted by a women, her unhappiness decreases (and no other woman's happiness changes). Hence total female unhappiness decreases every round. Total female unhappiness is a non-negative integer, and it is bounded by N^2 where N is the number of females. This shows that the algorithm must terminate, and must do so in at most N^2 rounds. It is also easy to see that the algorithm only terminates when all men are paired. Thus, we can conclude that the algorithm will produce a final pairing in which everyone is paired, and it will do this in at most O(N^2).
Consider any man, M1, paired by this algorithm with woman W1. Because men propose in order of their rankings, M1 has already proposed to every woman he prefers over W1. Either they were rejected (meaning those women were already paired with men they prefer over M1) or they were tentatively accepted but then later he was jilted when someone better came along. From this, we see that the pairings produced by the algorithm (including the partial pairings after each round) are such that no man is willing to cheat on his currently assigned partner. Hence, they are stable.
I recognise that this is known as the "Stable Marriage Problem", yet I still feel an aversion to marriage being defined as between a man and a woman (and further, than a man must propose to a woman). So, this scenario cranked my unhappiness up to 11. I was not able to follow it at all beyond "male unhappiness".
Surely it is possible to write this example in a way which recognises diversity of sexuality and does not need to play up to sexist stereotypes - employees looking for work and employers should work fine.
It's not an illustrative example because we have to assume an unrealistic misogynist take before it even starts to make sense.
The flaw is even more fundamental than that. Even if everyone plays without strategic mistakes the results are still poor.
What the system is trying to do is assign students based on what school they want. So they want each student to give an ordered list of their true preferences and the lottery algorithm will do its best to hand them out.
Once you add trading to the system, the optimum strategy appears quite quickly: list the most desirable schools first. If you get lucky you'll have lots of in-game currency for the "trading phase" of the game.
If every student followed this strategy, you'd have lost all preference input to the system: every student would turn in a nearly-identical ranked list of schools by "trading value". Now the algorithm has no chance of working -- instead the system has devolved into a purely random lottery where lucky students will randomly be given more "points" (i.e. a desirable school worth trading for)
Outside of the pure game-theory issues with a trading scheme it also adds risk of other pressures being introduced. For example, suppose you're a parent and your boss suggests letting your child trade schools with their child... are you able to refuse?
This is the meaning of stable in the stable marriage problem. And the Gale-Shapley algorithm does this.
the discrepancy in strategic aptitude is itself a result of chance. Only through this absolute form of randomness, you are actually eliminating the wealth, education and aptitude bonus of upper-class households.
Your comment is a nice signifier of the difference in American and Dutch culture. Dutch people don't buy the idea that individual strategizing is going to advantage the interests of lower-class students, because they recognise that lower class students are already disadvantaged when they enter the system.
True but I think if the optimum becomes “answer honestly which schools you want to go to, in order” then their goal has been reached, no?
For example, "we can’t make every student entirely happy with a lottery system. But we can try to spread the unhappiness as equally as possible."
In my opinion schools should be for teaching, even if only a few students are able to learn. Schools should be about having the same limits on all. That comes from the false metric of wanting all to leave the system with the same qualifications instead of the best qualities that each can individually have.
The system has been designed to not allow strategizing, as strategy often backfires on the student, as well as it's argued that students from lower class backgrounds make more strategic mistakes.
A nitpick from me on the article though:
> Designing a lottery system to place students at the different schools is not just a mathematical optimization problem. Different design choices can have far-reaching effects. On whether everyone gets equal opportunities, for example.
It absolutely is. It's called game theory. And 'no strategizing' is a criterion you can optimize for.
This has close relations to the well-known stable marriage problem. The seminal paper on both these problems is Gale and Shapley, College Admissions and the Stability of Marriage.