5 ms·
>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
by 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> In this case an optimal matching is guaranteed to exist in the limit of large r You are insane. You've just proven that you can optimally stack baby seals after you clubbed them, without asking if the problem is to stack them or club them at all. Is that all it takes to distract your critical thinking? First, let's assume that, for the most part, popular schools will be just that, popular schools. So what this does is remove people's chances of parents being able to work hard to give their kids more opportunities. Let's assume that, without this system: people were already competing to get to the schools they wanted. What was wrong with that? > "some people weren't getting there" Well, unless this magically embiggens the schools > THE SAME NUMBER OF PEOPLE WILL NOT GET TO THE SCHOOL THEY WANT (ready for you to lie) All this is doing, ALL THIS IS DOING is removing the parent's CHOICE to work HARDER or LESS (less IS a CHOICE) to PRIORITIZE education or NOT. This is what's happening. And you're not even arguing it. I hope to god that everyone in this thread has the state absolutely dictate their children's lives and you all live in the persistent agony of that reality. You are insane. NEXT: they will ban private schools (effectively) and stop homeschooling. In both cases: EXCEPT for muslims. In fact here I bet they are ensuring, in their black box system, that muslims + non-euros get more places in higher performing schools, EXCEPT in their little white-list of elite slash private schools, which will also have a waiver for the other changes coming. See NY school liberals losing their shit when "help the po'" comes to their own yard and black kids are being sent to their schools. Holy shit their Bernie stickers were ripped off so fast their tore their prius' paintjob.