19 ms·

Why a Dutch court stopped high school students from swapping schools (2017)

170 points by m4lvin 8y ago

nightcracker 8y ago
TL;DR: students are not allowed to swap because (in the current system) that would enable strategizing. It encourages people to list popular schools rather than their preferred choices for the lottery, and then trade their popular spot for their true preferences afterwards. 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.
- zodiac 8y ago
  I think it's precisely mechanism design (sometimes called "inverse game theory")
- karmakaze 8y ago
  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.
  - dshields1 8y ago
    > 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.
    - karmakaze 8y ago
      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.
  - rzwitserloot 8y ago
    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.
- Zyst 8y ago
  >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?
- IncRnd 8y ago
  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.
  - simion314 8y ago
    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.
- tzs 8y ago
  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.
  - throwaway1982x 8y ago
    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.
- gowld 8y ago
  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 https://en.wikipedia.org/wiki/Stable_marriage_problem
  - scythe 8y ago
    >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.
    - DONT_BE_A_MORON 8y ago
- mcv 8y ago
  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.
  - dnautics 8y ago
    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.
    - nightcracker 8y ago
      If you read the results (http://www.moniquedehaan.nl/wp-content/uploads/2016/08/schoolchoice2016july.pdf 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 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.
- closeparen 8y ago
  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?
  - throwaway2048 8y ago
    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.
  - Avshalom 8y ago
    The particular skills considered necessary to succeed in a meritocratic society tend to get defined post hoc.
  - Barrin92 8y ago
    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.
  - sdhgaiojfsa 8y ago
    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.
- bodyfour 8y ago
  > 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?
- emilfihlman 8y ago
  Only a marginal amount of students strategise.
GreeniFi 8y ago
This is really interesting - thanks for posting. What strikes me is that a court ruling implicitly took a view on the meaning of “fairness”. But fairness is a deeply subjective concept, something courts in a lot of countries would avoid going anywhere near! What’s interesting is that concepts of fairness vary greatly across cultures - and it makes me wonder how in multi-cultural, multi-ethnic Europe we will arrive at newly-agreed definitions of fairness and what that will be.
- riquito 8y ago
  Fairness in statistic is not not a subjective concept, it's a property of an algorithm.
  - Thiez 8y ago
    Fairness is absolutely a subjective concept. E.g. in the context of school choice, which is fair? Let's say there are 20 students applying to a school, and there are 10 spots available. a) All students applying to the school have the same chance to get a spot: 50% b) The best 10 students (by some definition of 'best', e.g. grades or an entry exam) get in. c) The 10 students with the richest parents get in. d) The 10 students that live closest to the school get in. We could go further: when 15 of the applicants are boys and 5 are girls (or vice versa), wouldn't it be more fair when 5 of each are chosen? How about racial distributions? Ultimately how you define fairness is subjective. Obviously once you have defined fairness you can attempt to measure it using mathematics / statistics.
    - zwily 8y ago
      The person you responded explicitly said “fairness in statistics”.
      - Thiez 8y ago
        What does "fairness in statistics" even mean? Perhaps there is a very obvious definition that I don't know about? Would you please define it for me, and (if this is non-obvious) explain how it relates to the school choice problem?
rukittenme 8y ago
Optimizing for fairness is antithetical to human rights. More people would be better off if you allowed swapping. But because some people would not be better off they don't allow it for anyone.
- Angostura 8y ago
  > More people would be better off if you allowed swapping. What makes you assume that?
  - andrenth 8y ago
    Two people engaging in consensual trade would be better off by the definition of trade. The judges are keeping them unhappy in the name of “fairness”, but is it fair that this exchange among willing individuals is forbidden? This can be reduced to an argument against free trade, because scarcity makes things unfair to those who can’t engage in the trade, which in my opinion is absurd.
    - danharaj 8y ago
      > Two people engaging in consensual trade would be better off by the definition of trade. No, the definition of consensual trade is that they would think they were better off. That people know their exact preferences and calculate with ease whether a transaction brings them closer to those preferences is a charade. > The judges are keeping them unhappy in the name of “fairness”, but is it fair that this exchange among willing individuals is forbidden? If you only focus on the individual level, maybe. But it's at least plausible that preventing locally favorable actions can create globally superior conditions for everyone in aggregate. This is obvious and arguments that center on "two individuals engaging in consensual trade" are trying to distract from that fundamental aspect of reality, either knowingly or unknowingly.
      - andrenth 8y ago
        So when you buy a discounted item is it a charade? How can two people being prevented to perform an exchange make things better globally? I don’t think that obvious at all. In fact allowing the exchange will make things better globally, by definition, because more people will be better off, while no one not engaging in the exchange will be worse off (unless you consider maybe envy).
ericpts 8y ago
What would be a good reason for distributing students based on luck (which is what I gathered from the article), versus having everyone take a standardized test and then assigning pupils to schools based on their performance in their test? The test approach seems the fairest to me, as a grade A student should have a higher priority of getting into a top school than a lower grade student. Contrast this with having a high achieving student not getting into the school of his choice due to sheer bad luck, and I do not see much benefit from the lottery system.
- frostburg 8y ago
  Consider that with this system everyone is a stakeholder in having every school be good enough.
- Radle 8y ago
  What you are suggesting is actually unfair. You want preffered treatment for grade A students.
  - wycs 8y ago
    Reality is unfair for distributing cognitive ability and grit the way it does. Preventing our institutions from responding to this reality is far more "unfair" than otherwise.
    - dctoedt 8y ago
      Nature and nurture probably dealt you a pretty good hand, even to endowing you with grit. Had it been otherwise, though, you might now feel somewhat differently about how our institutions should respond to the fact that people get dealt unequal hands.
      - 5DFractalTetris 8y ago
        I know this person to be a scholar by their concept of a "Reality," but they still have reading to do if they don't recognize that there may be at least three.
blockpress 8y ago
And another reason to avoid the public "education" system. They will make you pay (via taxes) for services you do not want or need.... to enroll at a place you do not want to be. How lovely.
- IkmoIkmo 8y ago
  That's not quite right. We're talking about a fundamental shortage of capacity for popular schools here. i.e. there are 10k spots and 8k students, but the top schools have fewer spots than interested students. A private system wouldn't solve this problem. It'd only allow profit-seeking schools to admit the richest students only. It's not a recipe for societal success because you're giving children a ticket not based on merit, but based on their parents' riches. This is closer to a plutocracy than a meritocracy. But either way, merit is hard to define because we're talking about 11 year old kids deciding on secondary school in the Netherlands starting around age 12. So you need some way of ranking students. The first one is student preference. It's not the case that you get enrolled at a school you had no interest in. The vast majority of students are enrolled in their schools of choice, but some of them may need to accept their 2nd or 3rd choice. In any case, the game theoretically driven choice affords students the highest chance of getting into a school closest to their preference. The Dutch public school system does quite well and has good outcomes, a testament to how few private schools there are despite private schools being given ample room to thrive here.
  - StudentStuff 8y ago
    > The Dutch public school system does quite well and has good outcomes, a testament to how few private schools there are despite private schools being given ample room to thrive here. I beg to differ, there is not ample room for private schools to thrive. This is primarily due to higher social cohesion as compared to other countries, the social acceptance of sending your kid to a private school in the US is generally assumed, whereas one is apt to be looked down on if they choose to have their children go to a less resourced, private school in the Netherlands. Despite private schools here in the US providing students with a lower quality teacher (here in Seattle, they pay $10k less a year to private school teachers than the school district does on average), while also permitting students to spread disease and not vaccinate, many upper class and middle class families send their kids to these schools. Its a testament to a lack of information and push back against objectively shitty schools. On the topic of vaccines, its crazy that the Catholic Church allows kids in their private schools to not be vaccinated. They're single handedly bringing back diseases that hadn't been a notable issue in decades.
danielvf 8y ago
While this isn't a surprising tradeoff for the Netherlands, what does surprise me is the size of the tradeoff they are willing to make. Almost eight percent of the entire student body would be going to a not-first choice school as a result of stopping the trades. (Using the numbers in the article) That's quite a hit. There are approximately 8,000 students per year entering Amsterdam high schools. According to the article, in 2015 when the new lottery system was introduced, 600 students would be able to attend their top choice school by swapping with someone else after the lottery.
- fmihaila 8y ago
  > While this isn't a surprising tradeoff for the Netherlands, what does surprise me is the size of the tradeoff they are willing to make. Almost eight percent of the entire student body would be going to a not-first choice school as a result. (Using the numbers in the article) That's quite a hit. It is, but it needs to be balanced against the percentage of disappointed students in a regular, non-lottery system. The article doesn’t say what that is, unfortunately.
  - danielvf 8y ago
    It's certainly true that the current state is better than a non-lottery system. That's not what the judge's decision changed though - it changed from preference+lottery with trades to preference+lottery without trades. This creates a strictly worse outcome for that school year, since only students who would mutually benefit from a trade would trade, and students who did nothing or could not trade would remain unchanged.
    - fmihaila 8y ago
      > This creates a strictly worse outcome for that school year, since only students who would mutually benefit from a trade would trade, and students who did nothing or could not trade would remain unchanged. That's true. My understanding is that they did that for two reasons. The first was that a property of this particular algorithm is that mutually beneficial swaps are only possible if there is a third student placed at a third school who would also prefer one of the two being swapped, but whose school is not desirable, so he doesn't have a choice, which was deemed unfair (I don't know how I feel about this argument). The second was that allowing trades for this school year would encourage strategizing in the following years, which would lead to worse outcomes over time. These two things were addressed when they changed the lottery system once again.
mabbo 8y ago
I wonder if the Gale–Shapley algorithm[0] would work in this situation. That algorithm applies to the stable marriage problem: N men and N women need to be paired such that no two members in each set would both prefer to be with each other over their partners. The algorithm has each person rank every member of the opposite gender in preferential order. Then, one side (let's presume the women) take turns picking from the other in order of their preferences. If the woman A's top choice is man X, but man X is already taken by woman B, then he will swap iff he prefers woman A over woman B. If he prefers woman B over woman A, then woman A moves down to her next choice in the list. If you follow this pattern to conclusion, everyone is paired and there will not exist a man and woman who both want to be with each other more than their current partners. We could apply this to school selection. Every student ranks all schools from most to least preferred. All schools then 'rank' students via any criteria they want. Want to put students with siblings in the school ahead of all others? Easily done. For any equally-preferred students, sort randomly. The "women" translates to students, and the "men" translates to "spot in this school". Might not stop strategizing, but it's a great way to handle pairings with preferences involved. [0]https://en.wikipedia.org/wiki/Stable_marriage_problem#Solution https://en.wikipedia.org/wiki/Stable_marriage_problem#Soluti...
- niftich 8y ago
  In the US, this algorithm is used to place medical graduates at teaching hospitals, by the National Resident Matching Program. And of course, college admissions was the topic of Gale and Shapley's 1962 paper, 'College Admissions and the Stability of Marriage' which publicized the algorithm [1]. [1] https://doi.org/10.2307%2F2312726 https://doi.org/10.2307%2F2312726
- dfee 8y ago
  That’s definitely an option that satisfices, but would it reduce the amount of satisfaction by increasing the number of “acceptable” solutions while decreasing the number of “desired” solutions? Humans are greedy, and that’s where these algorithms seem to fall apart in the real world.
- VHRanger 8y ago
  Edit: the deferred acceptance algorithm they refer to in the article __is__ the Gale algorithm. Those sort of algorithms (actually refined versions) are starting to be deployed for those problems. It's being used to match kidney donors to recipients, and freshly minted doctors to residencies. School districts have more problems implementing it due to regional politics. I would encourage you to look into the research by people like Al Roth, Itai Ashlagi or Atila Abdulkadiroglu.
jotadambalakiri 8y ago
> In fact, whenever two students win each other’s jackpot trade, there must always be a third student that’s higher on the ranking at one of the schools — and that wants a spot at this school I don't think that's true, what if in both schools they were ranked last place and last place plus one?
- pfedak 8y ago
  The algorithm won't assign them that way in that case. A more thorough explanation is elsewhere in the comments, but essentially if Alice got placed at B despite preferring A, they had to have gotten bumped from A, then bumped someone (or found an open space) at B. But Bob can't have been the person that bumped them: if there was an open space at B, Bob would never even have considered A; if Alice bumped someone at school B, then in your situation it must have been Bob, and so for Bob to end up at A when Alice couldn't there had to be someone else with priority between Alice and Bob for A, exactly the person getting screwed over by the swap.
csense 8y ago
Fascinating article. The obvious research question: Is there an assignment system where the best strategy is to list your true preferences, and is Pareto efficient (no win/win trading of assignment is possible)? What's wrong with simply randomizing the list of students, then walking the randomized list and giving each student his/her highest-ranked school that hasn't yet been filled by the assignment of students higher on the list? Does some variant of Arrow's impossibility theorem [1] apply to this situation? It might also shed light on the causes and dynamics of poverty to figure out the exact causal mechanism by which "students from poorer neighborhoods make more strategic mistakes." Is poor strategic decision-making ability a cause of poverty (the poor are poor because they don't make smart strategic decisions about money and life choices)? Or is it an effect of poverty (having a single parent or parents working multiple jobs means less intellectual stimulation and help with homework, not being able to afford nutritious food or have time to cook it causes poor nutrition which affects brain development, etc., which leads to lower general intelligence and strategic thinking ability)? [1] https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theore...
- gowld 8y ago
  > "students from poorer neighborhoods make more strategic mistakes." It's likely simpler than you guess, and not because poorer people are dumber (I'm not even sure why you assumed that making strategic mistakes in college planning is caused by low intelligence): students in poorer neighborhoods aren't plugged into the privilege networks, that tell them which are the best schools to apply to.
  - Scarblac 8y ago
    But having wrong preferences in the first place isn't the kind of strategic mistake they're talking about. It's thinking of the type "my 1st preference is school A, but I probably won't get in, so I'll say my preference is B so that I get that at least" in cases where they would have got into A if they had stated it as their #1.
  - Wh1zz 8y ago
    Students in poorer neighbourhoods don't have internet in the Netherlands?
elygre 8y ago
As a European exchange student, I took a sociology class as a senior in a US high school. Our teacher ran an experiment with "money", where those with lots of "money" were allowed to change the rules for each round, creating an unfair playing ground favoring the rich. I objected to the game and the rules, and did not want to play. After the game, in class, he commented that "Exchange students always object that the rules are unfair, while local students always accept that the rich get to set them." Without even knowing where people are from, I sense a similar trend in this discussion: Europeans are more willing (trained and socialized) to sacrifice individual preferences in favor of the "greater good". (Your mileage will vary. Not exact science. Not science at all. Just a feeling.) (Edit: Spelling)
- aianus 8y ago
  Surely the Netherlands has private schools? I don't think the rich are sacrificing anything by this lottery. Some middle-class kids might have to go to a worse school to allow some poor kids to go to a better school but the rich are unaffected.
  - elygre 8y ago
    No idea about the Dutch school system, and my comment is not about the rich vs the poor. My reflection is more about the general discussion: Is it OK that the court prioritizes "the greater good" over these two individual students? I think I sense different priorities between Europeans and Americans.
    - mcv 8y ago
      It's not so much "the greater good" that's prioritised, but fairness. They don't want rich or savvy kids to have an advantage that other kids don't get. But I think it's possible to improve over these systems in a way that increases efficiency without harming fairness.
    - aianus 8y ago
      I see, I thought you were commenting on the implementation of the lottery in the first place vs. our North American system of rationing good schools using money (either directly through tuition or expensive nearby real estate).
shagie 8y ago
From 9 months ago... https://news.ycombinator.com/item?id=15062125 https://news.ycombinator.com/item?id=15062125
- m4lvin 8y ago
  Oops, sorry. I did check whether this had been posted before, but missed the old entry because the article URL changed... https://hn.algolia.com/?query=https:%2F%2Fmedium.com%2Fpopular-choice https://hn.algolia.com/?query=https:%2F%2Fmedium.com%2Fpopul... https://hn.algolia.com/?query=https:%2F%2Fmedium.com%2Fsocial-choice https://hn.algolia.com/?query=https:%2F%2Fmedium.com%2Fsocia...
  - shagie 8y ago
    No worries. It’s interesting seeing new discussions about it and how the points line up with older discussions.
Illniyar 8y ago
I don't see why strategizing is a problem. Rather then ban it, encourage it, everyone should make the best strategy. Once everyone does, I think it will become clear that the best strategy is to choose the schools you want.
nemetroid 8y ago
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.
- eridius 8y ago
  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?
  - nemetroid 8y ago
    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.
rufusroflpunch 8y ago
Why not go one step further and randomize the teaching pool? Just tell teachers where they can and can't work, just to make sure that all students get a shot at the best teachers. What isn't justifiable in the name of fairness?
- Tijdreiziger 8y ago
  That actually seems like quite a good proposal. If a teacher applies to a school in a certain part of a city, presumably they'd also be happy to work at any other school in that part of the city. It would also be a win for the teachers, because they'd only have to apply once for multiple schools.
  - kalleboo 8y ago
    In Japan they actually do shuffle teachers around the school district every couple of years.
- ychen306 8y ago
  The article briefly explains. The reason is that there is no single metrics to measure the "goodness" of a school -- why would anyone want to swap schools otherwise? The example the article gives is some schools have better arts programs, and some have better sports, etc
- deleted 8y ago
  [deleted]
49bc 8y ago
Reminds me of something predicted in “Weapons or Math Destructive” an opique algorithm deciding our fate that’s difficult (impossible?) to fully audit. It’s a cruel fate we’re leaving ourselves too if we don’t leave a lot of room for common sense.
m4lvin 8y ago
For details about the voting algorithms, alternative methods based on genetic optimisation and Haskell implementations, have a look at the the MSc thesis "Genetic-Algorithmic Optimisation for School-Allocation Mechanisms - A Study of Amsterdam’s Student to High-School Allocation Problem" by Philip W.B. Michgelsen: https://eprints.illc.uva.nl/982/1/MoL-2016-10.text.pdf https://eprints.illc.uva.nl/982/1/MoL-2016-10.text.pdf
closeparen 8y ago
The intuition that lotteries are substantially more fair than markets is a strange one. There are already lotteries that redistribute money. If we accept that random windfalls are the right way to allocate resources, why is it preferably to hand out million-dollar discounts on condos or school slots that confer millions-dollar lifetime earning bumps vs. simply writing million dollar checks? The check winner has strictly more options than the condo owner, who is deed-restricted on resale, or the school slot winner, who might prefer to retire early instead. Lotteries get around unequal capability to spend, but so does the right tax policy or even an alternate currency scheme where you get non-tradable points to allocate across the various socialized axes of life. In a system with several independent lotteries, it’s possible to lose all of them, win the ones you don’t care about and lose the ones you do, or win them all. Allocating money gets you a kind of conservation effect: maybe you don’t care about school, so you got a nice house instead. Maybe the opposite. But with roughly the same spending capacity as everyone else, you definitely won’t win or lose big on all axes at once, and can make tradeoffs to win when it’s more important to you.
himom 8y ago
At least they had some choice. Growing up, I had no choice and couldn’t go to an elementary school a block from my house because of race quotas and forced busing to a magnet school to improve their stats. 1.5 hours each way, 3 hours total each school day. I was up at 4:50a. I thank the social justice warriors whom used more discrimination instead of equity to ostensibly make things “better.” (Equity is fairer and more advantageous than equality because it’s customized and resourced equally, instead of one-sized-fits-some.)
fallingfrog 8y ago
It's really weird to see the Dutch authorities using math to determine which system is better; it's even more bizarre to see them caring about fairness. Here in the states such an approach would be unthinkable. Whoever had the most money would get their way, and any kind of math is viewed as tricksy confusing lefty crap.
fouc 8y ago
>The central point is that efficiency and fairness were in conflict. Allowing trading would make the outcome a bit more efficient: some students would get a better outcome. But it would come at a price. The price is that the system would be less fair. Wow. It never occurred to me before that efficiency could create unfairness.
- Terr_ 8y ago
  Is that sarcasm? I mean, the most "efficient" algorithm for distributing surplus money to citizens' bank-accounts would be to transfer the entire sum into the first person you see..
Ice_cream_suit 8y ago
"Almost 70 percent of schools in the Netherlands are administered by private school boards, and all schools are government funded equally. The instrumental variables results show that private school attendance is associated with higher test scores. Private school size effects in math, reading and science achievement are 0.19, 0.31 and 0.21" http://documents.worldbank.org/curated/en/705501468323653171/Private-education-provision-and-public-finance-the-Netherlands http://documents.worldbank.org/curated/en/705501468323653171...
nickpp 8y ago
"Spread the unhappiness as equally as possible." This could be Socialism's new motto!
jupp0r 8y ago
Is it only me, or is denying gifted children good education based on pure luck unfair in the first place?
- eloisant 8y ago
  They're not denying gifted children good education. They're giving good education to everyone, and don't reserve the best to the students who are doing well already and will succeed anyway.
emilfihlman 8y ago
"Blah blah blah." If both students prefer the trade simply because of their preference for the school there is _no_ reason to prohibit that. No argument will change that.
topkai22 8y ago
This does beg the question: why aren’t the popular schools expanding to meet demand? My guess from other comments is that the center city location is often the driving reason for the pick, so the cost of acquiring similar real estate is prohibitive (also meaning that the the students selected for those schools are “unfairly” enjoying a high imputed income by enjoying that location) An interesting feature of the US charter school system in my area is that because their funding is directly tied to headcount (I believe there is bonus money for special ed students too), they are typically always looking at how to expand. Each school runs its own lottery, and being over-subscribed is looked at as a signal they need to expand their offerings.
overdrivetg 8y ago
For some reason I am able to understand single-DA better as: 1. All students are sequentially ranked via lottery 2. You walk down the list, and each student gets their pick of schools with remaining spaces open Side note, but it also seems IMO that "fairness" could improve if your lottery position is impacted by your past academic performance. Then the better student you have been, the more chance you have of being higher in the lottery order to select a school. And similar in the debate over which voting system is best, there is also something to be said for preferring that the system being used is easily understandable and feeling fair to the individual, even in the case where it is (slightly) less fair in the aggregate. Then you have the added bonus of fewer annoyed parents suing you, and only the mathematician parents will complain =) And then if you also add in the idea of academic performance playing a role, parents can rationalize their situation as having been under their control all along - if their child had performed better, they would have had the ability to choose earlier in the list. Of course, this is all assuming you believe that grades should convey some preferential status. But if you don't believe that, then why have grades at all?

170 points by m4lvin 8y ago

TL;DR: students are not allowed to swap because (in the current system) that would enable strategizing. It encourages people to list popular schools rather than their preferred choices for the lottery, and then trade their popular spot for their true preferences afterwards. 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.

zodiac 8y ago
I think it's precisely mechanism design (sometimes called "inverse game theory")
karmakaze 8y ago
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.
- dshields1 8y ago
  > 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.
  - karmakaze 8y ago
    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.
- rzwitserloot 8y ago
  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.
Zyst 8y ago
>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?
IncRnd 8y ago
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.
- simion314 8y ago
  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.
tzs 8y ago
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.
- throwaway1982x 8y ago
  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.
gowld 8y ago
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 https://en.wikipedia.org/wiki/Stable_marriage_problem
- scythe 8y ago
  >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.
  - DONT_BE_A_MORON 8y ago
mcv 8y ago
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.
- dnautics 8y ago
  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.
  - nightcracker 8y ago
    If you read the results (http://www.moniquedehaan.nl/wp-content/uploads/2016/08/schoolchoice2016july.pdf 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 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.
closeparen 8y ago
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?
- throwaway2048 8y ago
  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.
- Avshalom 8y ago
  The particular skills considered necessary to succeed in a meritocratic society tend to get defined post hoc.
- Barrin92 8y ago
  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.
- sdhgaiojfsa 8y ago
  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.
bodyfour 8y ago
> 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?
emilfihlman 8y ago
Only a marginal amount of students strategise.

GreeniFi 8y ago

This is really interesting - thanks for posting. What strikes me is that a court ruling implicitly took a view on the meaning of “fairness”. But fairness is a deeply subjective concept, something courts in a lot of countries would avoid going anywhere near! What’s interesting is that concepts of fairness vary greatly across cultures - and it makes me wonder how in multi-cultural, multi-ethnic Europe we will arrive at newly-agreed definitions of fairness and what that will be.

riquito 8y ago
Fairness in statistic is not not a subjective concept, it's a property of an algorithm.
- Thiez 8y ago
  Fairness is absolutely a subjective concept. E.g. in the context of school choice, which is fair? Let's say there are 20 students applying to a school, and there are 10 spots available. a) All students applying to the school have the same chance to get a spot: 50% b) The best 10 students (by some definition of 'best', e.g. grades or an entry exam) get in. c) The 10 students with the richest parents get in. d) The 10 students that live closest to the school get in. We could go further: when 15 of the applicants are boys and 5 are girls (or vice versa), wouldn't it be more fair when 5 of each are chosen? How about racial distributions? Ultimately how you define fairness is subjective. Obviously once you have defined fairness you can attempt to measure it using mathematics / statistics.
  - zwily 8y ago
    The person you responded explicitly said “fairness in statistics”.
    - Thiez 8y ago
      What does "fairness in statistics" even mean? Perhaps there is a very obvious definition that I don't know about? Would you please define it for me, and (if this is non-obvious) explain how it relates to the school choice problem?

rukittenme 8y ago

Optimizing for fairness is antithetical to human rights. More people would be better off if you allowed swapping. But because some people would not be better off they don't allow it for anyone.

Angostura 8y ago
> More people would be better off if you allowed swapping. What makes you assume that?
- andrenth 8y ago
  Two people engaging in consensual trade would be better off by the definition of trade. The judges are keeping them unhappy in the name of “fairness”, but is it fair that this exchange among willing individuals is forbidden? This can be reduced to an argument against free trade, because scarcity makes things unfair to those who can’t engage in the trade, which in my opinion is absurd.
  - danharaj 8y ago
    > Two people engaging in consensual trade would be better off by the definition of trade. No, the definition of consensual trade is that they would think they were better off. That people know their exact preferences and calculate with ease whether a transaction brings them closer to those preferences is a charade. > The judges are keeping them unhappy in the name of “fairness”, but is it fair that this exchange among willing individuals is forbidden? If you only focus on the individual level, maybe. But it's at least plausible that preventing locally favorable actions can create globally superior conditions for everyone in aggregate. This is obvious and arguments that center on "two individuals engaging in consensual trade" are trying to distract from that fundamental aspect of reality, either knowingly or unknowingly.
    - andrenth 8y ago
      So when you buy a discounted item is it a charade? How can two people being prevented to perform an exchange make things better globally? I don’t think that obvious at all. In fact allowing the exchange will make things better globally, by definition, because more people will be better off, while no one not engaging in the exchange will be worse off (unless you consider maybe envy).

ericpts 8y ago

What would be a good reason for distributing students based on luck (which is what I gathered from the article), versus having everyone take a standardized test and then assigning pupils to schools based on their performance in their test? The test approach seems the fairest to me, as a grade A student should have a higher priority of getting into a top school than a lower grade student. Contrast this with having a high achieving student not getting into the school of his choice due to sheer bad luck, and I do not see much benefit from the lottery system.

frostburg 8y ago
Consider that with this system everyone is a stakeholder in having every school be good enough.
Radle 8y ago
What you are suggesting is actually unfair. You want preffered treatment for grade A students.
- wycs 8y ago
  Reality is unfair for distributing cognitive ability and grit the way it does. Preventing our institutions from responding to this reality is far more "unfair" than otherwise.
  - dctoedt 8y ago
    Nature and nurture probably dealt you a pretty good hand, even to endowing you with grit. Had it been otherwise, though, you might now feel somewhat differently about how our institutions should respond to the fact that people get dealt unequal hands.
    - 5DFractalTetris 8y ago
      I know this person to be a scholar by their concept of a "Reality," but they still have reading to do if they don't recognize that there may be at least three.

blockpress 8y ago

And another reason to avoid the public "education" system. They will make you pay (via taxes) for services you do not want or need.... to enroll at a place you do not want to be. How lovely.

IkmoIkmo 8y ago
That's not quite right. We're talking about a fundamental shortage of capacity for popular schools here. i.e. there are 10k spots and 8k students, but the top schools have fewer spots than interested students. A private system wouldn't solve this problem. It'd only allow profit-seeking schools to admit the richest students only. It's not a recipe for societal success because you're giving children a ticket not based on merit, but based on their parents' riches. This is closer to a plutocracy than a meritocracy. But either way, merit is hard to define because we're talking about 11 year old kids deciding on secondary school in the Netherlands starting around age 12. So you need some way of ranking students. The first one is student preference. It's not the case that you get enrolled at a school you had no interest in. The vast majority of students are enrolled in their schools of choice, but some of them may need to accept their 2nd or 3rd choice. In any case, the game theoretically driven choice affords students the highest chance of getting into a school closest to their preference. The Dutch public school system does quite well and has good outcomes, a testament to how few private schools there are despite private schools being given ample room to thrive here.
- StudentStuff 8y ago
  > The Dutch public school system does quite well and has good outcomes, a testament to how few private schools there are despite private schools being given ample room to thrive here. I beg to differ, there is not ample room for private schools to thrive. This is primarily due to higher social cohesion as compared to other countries, the social acceptance of sending your kid to a private school in the US is generally assumed, whereas one is apt to be looked down on if they choose to have their children go to a less resourced, private school in the Netherlands. Despite private schools here in the US providing students with a lower quality teacher (here in Seattle, they pay $10k less a year to private school teachers than the school district does on average), while also permitting students to spread disease and not vaccinate, many upper class and middle class families send their kids to these schools. Its a testament to a lack of information and push back against objectively shitty schools. On the topic of vaccines, its crazy that the Catholic Church allows kids in their private schools to not be vaccinated. They're single handedly bringing back diseases that hadn't been a notable issue in decades.

danielvf 8y ago

While this isn't a surprising tradeoff for the Netherlands, what does surprise me is the size of the tradeoff they are willing to make. Almost eight percent of the entire student body would be going to a not-first choice school as a result of stopping the trades. (Using the numbers in the article) That's quite a hit. There are approximately 8,000 students per year entering Amsterdam high schools. According to the article, in 2015 when the new lottery system was introduced, 600 students would be able to attend their top choice school by swapping with someone else after the lottery.

fmihaila 8y ago
> While this isn't a surprising tradeoff for the Netherlands, what does surprise me is the size of the tradeoff they are willing to make. Almost eight percent of the entire student body would be going to a not-first choice school as a result. (Using the numbers in the article) That's quite a hit. It is, but it needs to be balanced against the percentage of disappointed students in a regular, non-lottery system. The article doesn’t say what that is, unfortunately.
- danielvf 8y ago
  It's certainly true that the current state is better than a non-lottery system. That's not what the judge's decision changed though - it changed from preference+lottery with trades to preference+lottery without trades. This creates a strictly worse outcome for that school year, since only students who would mutually benefit from a trade would trade, and students who did nothing or could not trade would remain unchanged.
  - fmihaila 8y ago
    > This creates a strictly worse outcome for that school year, since only students who would mutually benefit from a trade would trade, and students who did nothing or could not trade would remain unchanged. That's true. My understanding is that they did that for two reasons. The first was that a property of this particular algorithm is that mutually beneficial swaps are only possible if there is a third student placed at a third school who would also prefer one of the two being swapped, but whose school is not desirable, so he doesn't have a choice, which was deemed unfair (I don't know how I feel about this argument). The second was that allowing trades for this school year would encourage strategizing in the following years, which would lead to worse outcomes over time. These two things were addressed when they changed the lottery system once again.

mabbo 8y ago

I wonder if the Gale–Shapley algorithm[0] would work in this situation. That algorithm applies to the stable marriage problem: N men and N women need to be paired such that no two members in each set would both prefer to be with each other over their partners. The algorithm has each person rank every member of the opposite gender in preferential order. Then, one side (let's presume the women) take turns picking from the other in order of their preferences. If the woman A's top choice is man X, but man X is already taken by woman B, then he will swap iff he prefers woman A over woman B. If he prefers woman B over woman A, then woman A moves down to her next choice in the list. If you follow this pattern to conclusion, everyone is paired and there will not exist a man and woman who both want to be with each other more than their current partners. We could apply this to school selection. Every student ranks all schools from most to least preferred. All schools then 'rank' students via any criteria they want. Want to put students with siblings in the school ahead of all others? Easily done. For any equally-preferred students, sort randomly. The "women" translates to students, and the "men" translates to "spot in this school". Might not stop strategizing, but it's a great way to handle pairings with preferences involved. [0]https://en.wikipedia.org/wiki/Stable_marriage_problem#Solution https://en.wikipedia.org/wiki/Stable_marriage_problem#Soluti...

niftich 8y ago
In the US, this algorithm is used to place medical graduates at teaching hospitals, by the National Resident Matching Program. And of course, college admissions was the topic of Gale and Shapley's 1962 paper, 'College Admissions and the Stability of Marriage' which publicized the algorithm [1]. [1] https://doi.org/10.2307%2F2312726 https://doi.org/10.2307%2F2312726
dfee 8y ago
That’s definitely an option that satisfices, but would it reduce the amount of satisfaction by increasing the number of “acceptable” solutions while decreasing the number of “desired” solutions? Humans are greedy, and that’s where these algorithms seem to fall apart in the real world.
VHRanger 8y ago
Edit: the deferred acceptance algorithm they refer to in the article __is__ the Gale algorithm. Those sort of algorithms (actually refined versions) are starting to be deployed for those problems. It's being used to match kidney donors to recipients, and freshly minted doctors to residencies. School districts have more problems implementing it due to regional politics. I would encourage you to look into the research by people like Al Roth, Itai Ashlagi or Atila Abdulkadiroglu.

jotadambalakiri 8y ago

> In fact, whenever two students win each other’s jackpot trade, there must always be a third student that’s higher on the ranking at one of the schools — and that wants a spot at this school I don't think that's true, what if in both schools they were ranked last place and last place plus one?

pfedak 8y ago
The algorithm won't assign them that way in that case. A more thorough explanation is elsewhere in the comments, but essentially if Alice got placed at B despite preferring A, they had to have gotten bumped from A, then bumped someone (or found an open space) at B. But Bob can't have been the person that bumped them: if there was an open space at B, Bob would never even have considered A; if Alice bumped someone at school B, then in your situation it must have been Bob, and so for Bob to end up at A when Alice couldn't there had to be someone else with priority between Alice and Bob for A, exactly the person getting screwed over by the swap.

csense 8y ago

Fascinating article. The obvious research question: Is there an assignment system where the best strategy is to list your true preferences, and is Pareto efficient (no win/win trading of assignment is possible)? What's wrong with simply randomizing the list of students, then walking the randomized list and giving each student his/her highest-ranked school that hasn't yet been filled by the assignment of students higher on the list? Does some variant of Arrow's impossibility theorem [1] apply to this situation? It might also shed light on the causes and dynamics of poverty to figure out the exact causal mechanism by which "students from poorer neighborhoods make more strategic mistakes." Is poor strategic decision-making ability a cause of poverty (the poor are poor because they don't make smart strategic decisions about money and life choices)? Or is it an effect of poverty (having a single parent or parents working multiple jobs means less intellectual stimulation and help with homework, not being able to afford nutritious food or have time to cook it causes poor nutrition which affects brain development, etc., which leads to lower general intelligence and strategic thinking ability)? [1] https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theore...

gowld 8y ago
> "students from poorer neighborhoods make more strategic mistakes." It's likely simpler than you guess, and not because poorer people are dumber (I'm not even sure why you assumed that making strategic mistakes in college planning is caused by low intelligence): students in poorer neighborhoods aren't plugged into the privilege networks, that tell them which are the best schools to apply to.
- Scarblac 8y ago
  But having wrong preferences in the first place isn't the kind of strategic mistake they're talking about. It's thinking of the type "my 1st preference is school A, but I probably won't get in, so I'll say my preference is B so that I get that at least" in cases where they would have got into A if they had stated it as their #1.
- Wh1zz 8y ago
  Students in poorer neighbourhoods don't have internet in the Netherlands?

elygre 8y ago

As a European exchange student, I took a sociology class as a senior in a US high school. Our teacher ran an experiment with "money", where those with lots of "money" were allowed to change the rules for each round, creating an unfair playing ground favoring the rich. I objected to the game and the rules, and did not want to play. After the game, in class, he commented that "Exchange students always object that the rules are unfair, while local students always accept that the rich get to set them." Without even knowing where people are from, I sense a similar trend in this discussion: Europeans are more willing (trained and socialized) to sacrifice individual preferences in favor of the "greater good". (Your mileage will vary. Not exact science. Not science at all. Just a feeling.) (Edit: Spelling)

aianus 8y ago
Surely the Netherlands has private schools? I don't think the rich are sacrificing anything by this lottery. Some middle-class kids might have to go to a worse school to allow some poor kids to go to a better school but the rich are unaffected.
- elygre 8y ago
  No idea about the Dutch school system, and my comment is not about the rich vs the poor. My reflection is more about the general discussion: Is it OK that the court prioritizes "the greater good" over these two individual students? I think I sense different priorities between Europeans and Americans.
  - mcv 8y ago
    It's not so much "the greater good" that's prioritised, but fairness. They don't want rich or savvy kids to have an advantage that other kids don't get. But I think it's possible to improve over these systems in a way that increases efficiency without harming fairness.
  - aianus 8y ago
    I see, I thought you were commenting on the implementation of the lottery in the first place vs. our North American system of rationing good schools using money (either directly through tuition or expensive nearby real estate).

shagie 8y ago

From 9 months ago... https://news.ycombinator.com/item?id=15062125 https://news.ycombinator.com/item?id=15062125

m4lvin 8y ago
Oops, sorry. I did check whether this had been posted before, but missed the old entry because the article URL changed... https://hn.algolia.com/?query=https:%2F%2Fmedium.com%2Fpopular-choice https://hn.algolia.com/?query=https:%2F%2Fmedium.com%2Fpopul... https://hn.algolia.com/?query=https:%2F%2Fmedium.com%2Fsocial-choice https://hn.algolia.com/?query=https:%2F%2Fmedium.com%2Fsocia...
- shagie 8y ago
  No worries. It’s interesting seeing new discussions about it and how the points line up with older discussions.

Illniyar 8y ago

I don't see why strategizing is a problem. Rather then ban it, encourage it, everyone should make the best strategy. Once everyone does, I think it will become clear that the best strategy is to choose the schools you want.

nemetroid 8y ago

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.

eridius 8y ago
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?
- nemetroid 8y ago
  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.

rufusroflpunch 8y ago

Why not go one step further and randomize the teaching pool? Just tell teachers where they can and can't work, just to make sure that all students get a shot at the best teachers. What isn't justifiable in the name of fairness?

Tijdreiziger 8y ago
That actually seems like quite a good proposal. If a teacher applies to a school in a certain part of a city, presumably they'd also be happy to work at any other school in that part of the city. It would also be a win for the teachers, because they'd only have to apply once for multiple schools.
- kalleboo 8y ago
  In Japan they actually do shuffle teachers around the school district every couple of years.
ychen306 8y ago
The article briefly explains. The reason is that there is no single metrics to measure the "goodness" of a school -- why would anyone want to swap schools otherwise? The example the article gives is some schools have better arts programs, and some have better sports, etc
deleted 8y ago
[deleted]

49bc 8y ago

Reminds me of something predicted in “Weapons or Math Destructive” an opique algorithm deciding our fate that’s difficult (impossible?) to fully audit. It’s a cruel fate we’re leaving ourselves too if we don’t leave a lot of room for common sense.

m4lvin 8y ago

For details about the voting algorithms, alternative methods based on genetic optimisation and Haskell implementations, have a look at the the MSc thesis "Genetic-Algorithmic Optimisation for School-Allocation Mechanisms - A Study of Amsterdam’s Student to High-School Allocation Problem" by Philip W.B. Michgelsen: https://eprints.illc.uva.nl/982/1/MoL-2016-10.text.pdf https://eprints.illc.uva.nl/982/1/MoL-2016-10.text.pdf

closeparen 8y ago

The intuition that lotteries are substantially more fair than markets is a strange one. There are already lotteries that redistribute money. If we accept that random windfalls are the right way to allocate resources, why is it preferably to hand out million-dollar discounts on condos or school slots that confer millions-dollar lifetime earning bumps vs. simply writing million dollar checks? The check winner has strictly more options than the condo owner, who is deed-restricted on resale, or the school slot winner, who might prefer to retire early instead. Lotteries get around unequal capability to spend, but so does the right tax policy or even an alternate currency scheme where you get non-tradable points to allocate across the various socialized axes of life. In a system with several independent lotteries, it’s possible to lose all of them, win the ones you don’t care about and lose the ones you do, or win them all. Allocating money gets you a kind of conservation effect: maybe you don’t care about school, so you got a nice house instead. Maybe the opposite. But with roughly the same spending capacity as everyone else, you definitely won’t win or lose big on all axes at once, and can make tradeoffs to win when it’s more important to you.

himom 8y ago

At least they had some choice. Growing up, I had no choice and couldn’t go to an elementary school a block from my house because of race quotas and forced busing to a magnet school to improve their stats. 1.5 hours each way, 3 hours total each school day. I was up at 4:50a. I thank the social justice warriors whom used more discrimination instead of equity to ostensibly make things “better.” (Equity is fairer and more advantageous than equality because it’s customized and resourced equally, instead of one-sized-fits-some.)

fallingfrog 8y ago

It's really weird to see the Dutch authorities using math to determine which system is better; it's even more bizarre to see them caring about fairness. Here in the states such an approach would be unthinkable. Whoever had the most money would get their way, and any kind of math is viewed as tricksy confusing lefty crap.

fouc 8y ago

>The central point is that efficiency and fairness were in conflict. Allowing trading would make the outcome a bit more efficient: some students would get a better outcome. But it would come at a price. The price is that the system would be less fair. Wow. It never occurred to me before that efficiency could create unfairness.

Terr_ 8y ago
Is that sarcasm? I mean, the most "efficient" algorithm for distributing surplus money to citizens' bank-accounts would be to transfer the entire sum into the first person you see..

Ice_cream_suit 8y ago

"Almost 70 percent of schools in the Netherlands are administered by private school boards, and all schools are government funded equally. The instrumental variables results show that private school attendance is associated with higher test scores. Private school size effects in math, reading and science achievement are 0.19, 0.31 and 0.21" http://documents.worldbank.org/curated/en/705501468323653171/Private-education-provision-and-public-finance-the-Netherlands http://documents.worldbank.org/curated/en/705501468323653171...

nickpp 8y ago

"Spread the unhappiness as equally as possible." This could be Socialism's new motto!

jupp0r 8y ago

Is it only me, or is denying gifted children good education based on pure luck unfair in the first place?

eloisant 8y ago
They're not denying gifted children good education. They're giving good education to everyone, and don't reserve the best to the students who are doing well already and will succeed anyway.

emilfihlman 8y ago

"Blah blah blah." If both students prefer the trade simply because of their preference for the school there is _no_ reason to prohibit that. No argument will change that.

topkai22 8y ago

This does beg the question: why aren’t the popular schools expanding to meet demand? My guess from other comments is that the center city location is often the driving reason for the pick, so the cost of acquiring similar real estate is prohibitive (also meaning that the the students selected for those schools are “unfairly” enjoying a high imputed income by enjoying that location) An interesting feature of the US charter school system in my area is that because their funding is directly tied to headcount (I believe there is bonus money for special ed students too), they are typically always looking at how to expand. Each school runs its own lottery, and being over-subscribed is looked at as a signal they need to expand their offerings.

overdrivetg 8y ago

For some reason I am able to understand single-DA better as: 1. All students are sequentially ranked via lottery 2. You walk down the list, and each student gets their pick of schools with remaining spaces open Side note, but it also seems IMO that "fairness" could improve if your lottery position is impacted by your past academic performance. Then the better student you have been, the more chance you have of being higher in the lottery order to select a school. And similar in the debate over which voting system is best, there is also something to be said for preferring that the system being used is easily understandable and feeling fair to the individual, even in the case where it is (slightly) less fair in the aggregate. Then you have the added bonus of fewer annoyed parents suing you, and only the mathematician parents will complain =) And then if you also add in the idea of academic performance playing a role, parents can rationalize their situation as having been under their control all along - if their child had performed better, they would have had the ability to choose earlier in the list. Of course, this is all assuming you believe that grades should convey some preferential status. But if you don't believe that, then why have grades at all?