Hacker News Reader

It's important to remember that the Gale-Shapely algorithm generates a "stable" solution, AKA a local optimum. It doesn't generate a global optimum (which is impossible, since utility function is N-dimensional -- one for each mate -- and projecting that onto 1 dimension requires picking whose utility matters how much).

"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."

https://en.wikipedia.org/wiki/Stable_marriage_problem

>It doesn't generate a global optimum (which is impossible...)

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.

"requires picking whose utility matters how much"

... 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...

While I understand the need for fairness and the desire to make strategising pointless, it's still weird if two students win each other's jackpot.

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.

It's because having distributed lotteries result in a non stable system. This was resolved by having a single lottery. It's totally crazy that they didn't do it from the start.

If you read the results (http://www.moniquedehaan.nl/wp-content/uploads/2016/08/schoo...) the choice makes a lot of sense.

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.

The stable marriage problem and the Gale-Shapley algorithm for it are good for introducing someone who is a good, self-taught programmer but whose mathematical background is a bit lacking to the idea of proving that a program works by reasoning about it instead of just doing empirical testing.

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 found this example exceptionally difficult to read and comprehend.

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 just an example, not a political manifesto. Feel free to copy the comment and replace the words you object to.

If it's an example and not a political manifesto, then perhaps it could be written without misogynist and heteronormative (i.e. political) undertones.

It's not an illustrative example because we have to assume an unrealistic misogynist take before it even starts to make sense.

> 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.

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?

My solution is to encode the swapping in the placement algorithm so that any pair of students can be swapped if they both get a more preferred school. This way you eliminate the gaming aspect since you can't later decide that you want to trade for a school lower on your list. Simple. Fair.

> any pair of students can be swapped if they both get a more preferred school.

This is the meaning of stable in the stable marriage problem. And the Gale-Shapley algorithm does this.

The important part is that the algorithm is applied by the system without human interaction after the initial input of preferences. Placements are still final.

I'm not so sure. I haven't done the math but I think you can strategize here: pick your #1 preference as #1 on your list... But then put the most popular school as your #2 (instead of your personal actual second preference). Odds that you end up getting picked by the algorithm for a mutually beneficial trade is high.

I think it's precisely mechanism design (sometimes called "inverse game theory")

So it ensures that unequal outcomes are always the result of random chance, and never the result of a skill gap. That seems exactly backwards: you would want egalitarian policy to minimize random factors like your parents’ wealth so that factors like the student’s own skills dominate. Can anyone elaborate?

Its much more likely to be a result of a "parental wealth gap", because its those who are going to pay consultants lots of money (and likely conspire with other wealthy people to rig the system) to ensure optimal placement.

The particular skills considered necessary to succeed in a meritocratic society tend to get defined post hoc.

the ability of a student to strategize is strongly correlated to the education and wealth of the parents. (as pointed out in the post).

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.

Generally speaking, we're not trying to reduce random factors. We're trying to reduce hereditary factors. There are already plenty of intrinsic hereditary factors (intelligence, appearance, health). We want to limit the ability of extrinsic hereditary factors (wealth, connections) to influence egalitarian processes, and in some cases even correct for them.

>It absolutely is. It's called game theory. And 'no strategizing' is a criterion you can optimize for.

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?

Only a marginal amount of students strategise.

I don't believe that he origin and provenance of the system matter as much as the effect. What does matter is that two people who would each prefer the others' place, where that swap wouldn't affect others, should be allowed to swap positions. The rest of the article is a clear attempt to justify the intentional spreading of misery.

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 article explained that if swapping is allowed then in next years students will strategise, the algorithm that caused the sqaping issue was changed in the next year.