You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
It’s an algorithm commonly used in AI that tries to find the global
minimum (or maximum) of a function
The name comes from the idea that if you freeze a hot liquid
quickly it won’t form nice crystals, but if you do it slowly it
will because the particles are more likely to find the lowest
energy (lattice) state.
Likewise, when our system is “hot” it is more likely to jump over
“energy barriers” (i.e. make decisions that initially appear unfavourable
but might lead to less overall unhappiness on the other
side). The slower we cool it, the more likely our system is to
find the global minimum.
It starts by randomly allocating people per category
All category 1 applicants are matched to a random hospital.
Anyone below will have this process applied to them:
If there are more applicants than spots, HETI’s server
randomises the list of applicants and takes from the top however
many would fill the remaining spots.
Now for the fancy AI part
At this point, everyone who is in a hospital will have a certain
“unhappiness score” calculated from what position the hospital they got
was in their preferences list minus 1 (so, zero if you got your favourite).
The algorithm will try swapping two people. If it results in a net
increase in happiness and doesn’t overload hospital capacity, the swap
is more likely to be followed through with. If not, nothing happens.
The algorithm keeps doing this for a large number of iterations.
Henceforth for brevity this method will be referred to as the “AI algorithm”
Other conceptions
Categorical allocation has also been previously understood as the method for allocation.
This basically involves allocating people first by category, then according
to preference. The last iteration of this article was based on this conception.
Implementation
These scenarios were tested:
Everybody preferences hospitals entirely randomly
Everybody stacks
Everybody stacks but moves a random hospital of their choice to
first place
Everybody stacks but moves random hospitals of their choice to
1st and 12th places
Everybody stacks but moves random hospitals of their choice to
1st and 14th places
Everybody stacks but moves random hospitals of their choice to
1st and 2nd places
Incomplete list of deviations from reality, simplifications and
assumptions:
With unweighted randomness, it is assumed that no hospital is
more favourable than another.
With weighted randomness, hospital favourability at all levels is
assumed to be similar to that at the first preference. That is,
the probability-weight of a simulated applicant selecting each
hospital is correlated with their popularity based on last year’s
survey.
Either everybody having the same stack or using two different
variants of the stack were tested.
Everyone who applies accepts the first job offer they get.
DRA and other pathways that cannot be considered part of the
optimised allocation algorithm have not been accounted for in
running the simulation. However, parts of it are included as options
in the code if you want to try it yourself.
Only 1 round of offers is simulated. Rejections are not accounted for.
Corollary from 4-6: Category 1 applicants are basically guaranteed
a job.
Corollary from 7: Anyone category 3 or below will not get a job.
[from a reader] IRL, category 2 placements and beyond tend to be based
more on luck of the draw (offer timing, rounds, category 1
rejections).
Corollary from 8,9: in terms of informing you as to what to do,
this simulation is basically worthless for anyone outside of
category 1, and maybe 2.
The ones you should be looking at are the AI algorithm + weighted
random selection. The unweighted is included merely for comparison.
For nerds: the actual code of this simulation is on
Github. Parameters used in the simulation:
Parameter
Value
α
0.0002
T
10000
Results
How to read the tables:
nth
Number of applicants that got their nth preference
catn
Category n applicants
placed
Applicants who matched into any hospital
not_placed
Applicants who did not match into any hospital
AI algorithm + weighted random selection
Weighted random
total
cat1
cat2
cat3
cat4
cat5
cat6
1st
174
161
13
0
0
0
0
2nd
169
158
11
0
0
0
0
3rd
136
128
8
0
0
0
0
4th
116
106
10
0
0
0
0
5th
85
77
8
0
0
0
0
6th
86
78
8
0
0
0
0
7th
70
65
5
0
0
0
0
8th
36
31
5
0
0
0
0
9th
31
25
6
0
0
0
0
10th
25
23
2
0
0
0
0
11th
29
28
1
0
0
0
0
12th
18
17
1
0
0
0
0
13th
14
13
1
0
0
0
0
14th
6
6
0
0
0
0
0
15th
1
0
1
0
0
0
0
placed
996
916
80
0
0
0
0
not_placed
543
0
122
158
148
101
14
total
1539
916
202
158
148
101
14
Total
Category 1
Category 2
All stack
total
cat1
cat2
cat3
cat4
cat5
cat6
1st
64
59
5
0
0
0
0
2nd
71
67
4
0
0
0
0
3rd
51
47
4
0
0
0
0
4th
54
49
5
0
0
0
0
5th
49
46
3
0
0
0
0
6th
76
69
7
0
0
0
0
7th
121
112
9
0
0
0
0
8th
40
36
4
0
0
0
0
9th
125
113
12
0
0
0
0
10th
74
70
4
0
0
0
0
11th
51
45
6
0
0
0
0
12th
68
61
7
0
0
0
0
13th
66
62
4
0
0
0
0
14th
63
56
7
0
0
0
0
15th
27
24
3
0
0
0
0
placed
1000
916
84
0
0
0
0
not_placed
539
0
118
158
148
101
14
total
1539
916
202
158
148
101
14
Total
Category 1
Category 2
Mixed stacks
total
cat1
cat2
cat3
cat4
cat5
cat6
1st
63
54
9
0
0
0
0
2nd
72
67
5
0
0
0
0
3rd
51
44
7
0
0
0
0
4th
54
51
3
0
0
0
0
5th
49
47
2
0
0
0
0
6th
76
68
8
0
0
0
0
7th
92
85
7
0
0
0
0
8th
69
62
7
0
0
0
0
9th
125
117
8
0
0
0
0
10th
74
68
6
0
0
0
0
11th
51
46
5
0
0
0
0
12th
79
72
7
0
0
0
0
13th
55
52
3
0
0
0
0
14th
63
59
4
0
0
0
0
15th
25
24
1
0
0
0
0
placed
998
916
82
0
0
0
0
not_placed
541
0
120
158
148
101
14
total
1539
916
202
158
148
101
14
Total
Category 1
Category 2
All same stack with weighted random first
total
cat1
cat2
cat3
cat4
cat5
cat6
1st
74
68
6
0
0
0
0
2nd
64
60
4
0
0
0
0
3rd
49
46
3
0
0
0
0
4th
68
64
4
0
0
0
0
5th
54
51
3
0
0
0
0
6th
51
48
3
0
0
0
0
7th
125
114
11
0
0
0
0
8th
66
62
4
0
0
0
0
9th
121
106
15
0
0
0
0
10th
63
58
5
0
0
0
0
11th
76
66
10
0
0
0
0
12th
54
51
3
0
0
0
0
13th
40
37
3
0
0
0
0
14th
51
48
3
0
0
0
0
15th
40
37
3
0
0
0
0
placed
996
916
80
0
0
0
0
not_placed
543
0
122
158
148
101
14
total
1539
916
202
158
148
101
14
Total
Category 1
Category 2
All same stack with weighted random first and 12th
total
cat1
cat2
cat3
cat4
cat5
cat6
1st
71
67
4
0
0
0
0
2nd
76
69
7
0
0
0
0
3rd
64
56
8
0
0
0
0
4th
125
112
13
0
0
0
0
5th
54
49
5
0
0
0
0
6th
54
45
9
0
0
0
0
7th
68
65
3
0
0
0
0
8th
51
47
4
0
0
0
0
9th
121
114
7
0
0
0
0
10th
74
66
8
0
0
0
0
11th
51
50
1
0
0
0
0
12th
66
61
5
0
0
0
0
13th
49
44
5
0
0
0
0
14th
40
38
2
0
0
0
0
15th
37
33
4
0
0
0
0
placed
1001
916
85
0
0
0
0
not_placed
538
0
117
158
148
101
14
total
1539
916
202
158
148
101
14
Total
Category 1
Category 2
All same stack with weighted random first and 14th
The algorithm converges on the minimum global unhappiness fastest when
everyone stacks, slowest when everyone selects a weighted-random preference
list.
I seriously don’t know where HETI gets the “millions of iterations”
figure from, these models converged far faster than that. And it can’t
be a pure brute force algorithm either (that’s \(O(M× N!)\),
where N is the number of applicants and M the number of hospitals for
you nerds out there), as that would require testing more combinations
than there are atoms in the universe.
How to read the legend:
min_unhappiness
Minimum possible global unhappiness determined so far
current_unhappiness
Global unhappiness of the current iteration
All random
Weighted random
All stack
Mixed stacks
All same stack with random first
All same stack with weighted random first
All same stack with random first and 12th
All same stack with weighted random first and 12th
All same stack with random first and 14th
All same stack with weighted random first and 14th
All same stack with random first and 2nd
All same stack with weighted random first and 2nd
Mixed stacks with random first
Mixed stacks with weighted random first
Mixed stacks with random first and 12th
Mixed stacks with weighted random first and 12th
Mixed stacks with random first and 14th
Mixed stacks with weighted random first and 14th
Mixed stacks with random first and 2nd
Mixed stacks with weighted random first and 2nd
Global unhappiness when compared to categorical matching
The AI algorithm does not appear to always lead to an improved
reduction in global/total unhappiness when compared to categorical
matching. However I didn’t simulate for millions of iterations like
HETI claims to. Calling on anyone with a fancy graphics card (or even
a cryptocurrency mining rig) to try it out though. Bonus points if you
can fix my code to implement CUDA optimisation.
Allocation mode
Anneal method
Categorical method
All random
559
1012
Weighted random
3452
2025
All stack
6830
7208
Mixed stacks
6821
7070
All same stack with random first
7157
7231
All same stack with weighted random first
6641
7117
All same stack with random first and 12th
7573
7107
All same stack with weighted random first and 12th
6326
7629
All same stack with random first and 14th
6801
6997
All same stack with weighted random first and 14th
6314
6602
All same stack with random first and 2nd
6897
7188
All same stack with weighted random first and 2nd
6452
8022
Mixed stacks with random first
4479
3989
Mixed stacks with weighted random first
4209
5475
Mixed stacks with random first and 12th
4192
6111
Mixed stacks with weighted random first and 12th
4560
5946
Mixed stacks with random first and 14th
5180
4800
Mixed stacks with weighted random first and 14th
4822
4528
Mixed stacks with random first and 2nd
5067
5481
Mixed stacks with weighted random first and 2nd
4618
5450
Discussion
In short, under each strategy, with weighting for random choices:
All random
Gradual gradation of ranks from top to bottom
Nobody actually selects like this IRL (unless you’re a weirdo)
All stack
It’s basically communism for internships.
You have a near-equal chance at landing just about every
hospital.
Stack heterogeneity does not seem to change this overall effect.
All stack but put a random on top
Slightly improves your chance of getting first preference, but
otherwise probability of landing other hospitals is similar to
when everyone stacks.
This appears to be most consistent with the strategy people use
IRL.
All stack but put a random at 1 and 12
Similar chances of getting your first, but strengthens chance
at 12th.
Weakens both if stacks are heterogenous.
All stack but put a random at 1 and 14
Similar shot at 14th but definitely worsens your first.
Better shot at 1st and worst at 14th if stacks are heterogenous.
All stack but put a random at 1 and 2
Similar shot at 2nd, definitely worsens first.
Only slightly levels the chances at both if stacks are
heterogenous.
Key differences from a categorical allocation method:
Wherever the stack is used, the near-equal chances of getting
every hospital after your first (two) is preserved
If everyone selects randomly, less people get their first
preference.
Strategy 3 perhaps represents the best idea - you are more likely
to get your best, but otherwise you get an equal chance of getting
everything else.
Counterintuitively, simulated annealing does not always result in a
net increase in happiness, when compared to a categorical allocation
approach. However, this may be an effect of low iteration count.
Regarding common rumours:
“The last 4 are the most important” - under this algorithm this is
no longer true. If the matching system was categorical, it would
be.
“Stacking hurts your chances of getting to preferences 1-6”
(HETI, 2020) - definitely true but this seems to miss the point of
stacking. The true advantage herein is that the chance of getting
to a hospital now becomes proportional to the number of vacancies.
Limitations
Assumptions and deviations from reality have been addressed under
Implementation.
Regarding DRA: it is possible to factor DRA into this model. The
source files now include DRA counts from last year and include
those values in Hospital.__init__(). Feel free to tinker around
with the source code if you want to account for DRA, I just cbf to
implement it atm. Also I’m unsure how much it will actually affect
the conclusions of the simulation, the only real difference is
that the number of spots changes. But basically the schema for the
algorithm, as outlined in the 2019 Annual Report[fn:2] is this
(document is unclear about what to do about the other DRA-eligible
categories):
ifcat1.count<=dra.spots:
dra.spots.allocate(cat1)
else:
dra.spots.allocate(random.select(cat1, dra.spots.count))
# ???how to account for other categories???
The exact parameters of the annealing process can affect the end
result. Which ones HETI plans to use are unknown to us.
I only used two stack variants to demonstrate the effect of mixed
stacks. It could be a lot worse if there are more.
What should you do?
There is no way to really draw any definitive conclusions on what
the “best” strategy is, especially since a lot of simplifications
were made to run this model.
For the moment, one might conclude that:
Strategy 3 has been in use for the longest time and probably
represents the most advantageous idea.
Strategy 2 is best if you don’t care where you end up.
It is unclear whether any other strategy will be advantageous in
real life.
Fork me, submit a pull request or an issue on Github to help me
improve the simulation so future generations can know what to do
with greater accuracy. There’s probably a lot of higher-level
math/CS knowledge that could be applied here that I don’t know about.
Future directions/todos
[ ] Fix the algorithm so it’s more consistent with the real data
[ ] GPU optimisation of simulated annealing
[ ] Significance analysis of results
[ ] Further strategic analysis of ways to “beat the algorithm”
[ ] Implement mixed strategies (data on rough proportioning of
strategies among applicants is needed)
[ ] Try “mixed stacks” with >2 stack variants (how many stack
variants actually exist in the wild?)
[ ] As the number of stack variants increases towards infinity, does
the behaviour of the stack algorithm tend to approximate that of
pure-random preferencing?
[ ] Implement random Category 1 rejections and multiple rounds of
offers so this simulation actually becomes useful for Categories 2-6
[ ] Implement DRA pre-allocation
[ ] Implement all the other pathways
Sources
AMSA Internship Guide[fn:1] and HETI’s Annual Report[fn:2]