Comparison with old algorithm

[ConorWilliams]

Here I provide comparison data for the 2019 ballot:

• In total 85 people entered the ballot.
• There were 58 rooms available in college.
• The code was run supplied with the the flags -m 58 for the first data set and -m 58 -h PS OX OR HR for the second.
• The initial ballot allocated some people rooms they did not choose, these are marked with a choice of INF in the data.

I leave the data to be analysed by another member of the MCR as I have a conflict of interest in the presentation of these results.

[mthunter26]

I've put this data in to some plots, sorry I know the formatting is not the best.

My main observations are that the old method prefers to give people in higher priority groups rooms at the expense of people in lower groups, even if those rooms were not initially on their preference list. My understanding is that these 'other rooms' were based on the price bracket that each person deemed acceptable to them, and so while they were not in their top 10, they most likely would have been in their top 20 for example. This ultimately results in only 1 person in priority group 2 not getting a room, and only one person in priority groups 3 and 4 getting rooms.

As far as I can tell the main consequence of the new method in short is that more people in priority groups 3 and 4 get rooms, while fewer people in priority group 2 get a room. I'm not sure this is ideally what should happen, because to me it seems like people that unbeknownst to them picked more popular rooms are punished for this, while people who similarly picked less popular rooms are rewarded, even if they're in higher/lower priority groups respectively. I think that the aspect of the old system where people in a higher priority groups were given the option of taking another room than they first chose before lower priority groups did actually prioritse them getting a room they were satisfied with, in a way that the new method doesn't. Maybe this could be solved by having more choices? This also is maybe this is just my interpretation of what being a priority means, and others disagree? Sorry if this is a bit rambly, just my initial thoughts.

[mthunter26]

To perhaps better summarise: In a big picture sense I don't think that a situation should occur where someone in Priority Group X doesn't get a room at all, while someone in Priority Group X+1 gets a room that the first person ultimately would have accepted. Or I think we should call them something other than priority groups.

[ConorWilliams]

Many thanks Micheal. I think you have drilled into the heart of the debate here, what is priority? In the old system it meant you got a room in the new it means you'll probably get a room.

In the old this was achieved by allocating rooms to people they may not have wanted. If you consider graph 1 vs 3 but move the "other room" into the "kicked" category (which I think is what happens for many people as they subsequently reject the unwanted room) it is clear to me the new algorithm is superior.

If we want priority to mean what it used to then this can be implemented in the new code by increasing the cost of kicking higher priority students. This will give us all the benefits of the new code (global fairness, everyone gets a room they want, verifiability, etc). I am still against doing this as it means students in priority groups 0/1 can force their top choice by back-filling with honey-pot rooms.

To further stir things up, I am going to propose we change the priority bands, the distinction between 1/2 currently makes no sense. I suggest: priority = num_terms_in_postgrad_accomodation // 3

[mthunter26]

Yeah, I take your point that if all of the 'other rooms' are rejected anyway then the solution using the new algorithm seems better. I suppose my point though was in part that presumably the more preferences people are able to provide, the less chance there is of people in higher groups being 'kicked,' because there is less chance that there will be crossover with other people's preferences? So in the limit where everyone is able to rank all rooms, the solution is 'the best,' but the more preferences are limited, then the more likely it will be that the solution will diverege from this, and result in people in higher groups missing out on rooms altogether that they would have been happy with if they were able to list more preferences?

I do agree though that the justification for the current priority bands does not always make a great deal of sense, at least to me.

[turnersam96]

I'd agree with Michael. I'm not comfortable with people from lower priority being kicked off in favour of those from higher priority. My suggestion would be that people who would be kicked off the ballot are assigned to 'CHOICE' which still counts as a filled room. In that case after the ballot they are contacted and invited to take a free choice from the remaining rooms which should reduce the number of people who turn down all rooms. This would remove the issue of people being able to honey-pot their way to their first choice.

Alternatively you could increase the cost slope for lower priorities in something of a half-way house between the old and the new ballot. Overall I think your code makes a big improvement on equitable distribution, and I'm happy to use your allocation in the case of people in the same priority group.

[ConorWilliams]

The latest release resolves the priority dispute. If there are more people than spaces the ballot first removes the (numerically) highest priority members. @turnersam96, this eliminates your worry that you're: "not comfortable with people from lower priority being kicked off in favour of those from higher priority".

[ConorWilliams]

Here is the latest release with the same data (no hostels):

Choice	P0	P1	P2	P3	P4
1	5	14	20	1	0
2	0	5	4	0	0
3	1	1	5	0	0
4	0	1	1	0	0
KICK	0	0	0	17	10

and with hostels:

Choice	P0	P1	P2	P3	P4
1	5	13	16	0	0
2	1	3	1	0	0
4	0	1	0	1	0
5	0	0	1	0	0
6	0	0	1	0	0
8	0	3	6	0	0
9	0	0	2	0	0
10	0	1	3	0	0
KICK	0	0	0	17	10