Dear election methods fans,
I hope that someone finds this interesting... I've been working on
applying some of the tools of voting methods theory to other areas.
Specifically, well, to the area of romance! And at the same time, to
things like college admissions and the interaction between a work force
and a job market. It's a slightly different set of problems which
nevertheless feel relatively familiar to me after working with voting
systems.
Actually, I've been working on this paper for some time, developing
different methods, putting off the actual writing of the paper. Still I
have some uncertainties left, but at this point I'm tired of staying
private with it, so here goes. The paper itself is a very early draft, but
eventually it's something that I'd like to try to get published. (Well,
that would probably be a shorter version of the paper, though, I guess.)
It's important that people speak up if any of these ideas are already in
circulation. I have thought of them very much on my own, but of course
it's not hard to imagine someone else doing the same.
I invite any comments or questions about the paper that pop into your
mind. At this point I am trying to get real feedback.
The paper can also be found as an html document at
http://fc.antioch.edu/[EMAIL PROTECTED]/voting_methods/reciprocal.htm
And by the way, if anyone is interested in starting an internet business
with me based on this idea, let me know.
my best,
James Green-Armytage
_______________________________________________
James Green-Armytage
Reciprocal Pairing
Introduction
Imagine a high school class with 100 people in it, some boys and some
girls. Imagine that each person was to fill in a secret ballot with their
first choice of boyfriend or girlfriend, as well as their second choice,
their third choice, and so on? If you could get all those secret ballots
together, could you play matchmaker and find everyone the best possible
partner?
Imagine a public employment service which is trying to place 1,000
applicants into roughly the same number of job positions. Each of the
possible employers has a preference ranking of which applicants they
prefer over the others, and each of the possible workers have a preference
ranking of which jobs they would prefer. Is there a simple algorithm that
would combine these preference rankings into an optimal outcome?
When students apply to colleges in the US, there is a complex system of
early action, early admission, waiting lists, and so on. The problem is
that colleges don’t know how many of the students they accept will enroll,
and therefore they don’t know how many students to accept in order to
reach the target enrollment. Is there an easier way?
These three questions are mathematically very similar to each other. They
are similar to standard election methods theory, except that not only are
people voting on different options, but those options are other people who
are voting on them. Thus an optimal outcome depends on optimal
reciprocity, and a procedure which attempts to generate such an outcome
can be called a reciprocal pairing procedure.
Queue (line-up) method
Let me start with a simple case. Let’s say that there is a small group of
prospective employees, and there is a small group of prospective
employers, each offering one job opening. The employees and employers rank
each other in order of preference.
The most basic algorithm that can be used to determine the outcome is
best described using this metaphor:
1. The employers stand side by side, facing in the same direction.
2. The workers then line up in front of the employer who is at the top of
their list.
3. If more than one worker is lined up in front of an employer, the
employer then picks the worker who is most highly ranked on their own
list, and rejects the rest.
4. The rejected workers then line up in front of the next employer on
their list, that is, the one highest on their list whom they have not yet
been rejected by.
5. Step 3 repeats; the employers keep the workers whom they like the best.
It is possible that an employee who was previously accepted will now be
rejected because a more preferred applicant has filtered down.
6. Step 4 repeats, that is, newly rejected applicants will then continue
to the next employers on their lists.
7. The process ends by itself. That is, motion according to the above
rules will eventually stop. Some workers may not be paired with an
employer; such a worker will have been rejected by everyone on their list.
Some employers may not be paired with an worker. These employers will not
have had anyone lining up in front of them at all, or if someone did, it
wasn’t someone the employer considered an acceptable applicant.
Note: Again, the actual process of lining up, changing places, etc.
doesn’t actually need to occur in real life; rather it is mathematically
simulated using the ranked information provided. Disclosure of the
preferences of other actors is optional, and in most cases probably
undesirable.
Note: It is perfectly permissible for either employers or employees to
truncate their rankings, indicating that they would rather not be paired
at all than be paired with that particular option. An employee will never
line up in front of an employer not on their list, even if they have been
rejected by everyone else, and an employer will never accept an employee
not on their list, even if there are no other applicants.
Now for an example. Let’s say that there are four prospective employees A
B C and D, there are three prospective employers R S and T (with only one
job opening each), and the rankings are as follows:
A: R>S>T
B: R>S>T
C: S>R>T
D: T>R>S
R: A>B>C>D
S: A>B>C>D
T: C>B>D>A
The procedure would go like this:
R S T
1st lineup AB C D
rejections B
2nd lineup A BC D
rejections C
3rd lineup A B CD
rejections D
final outcome: A+R, B+S, C+T, D+nobody
To sum up, B lost his contest with A for the job at R, so he applied to S
and beat out C for that job. C then applied to T and got the job over D,
leaving D unemployed.
Note that in this case, the outcome would be the same if the roles of the
employers and employees were reversed, that is if the employees were
‘stationary,’ and the employers would ‘actively’ seek out their choices
from first to last.
A B C D
1st lineup RS T
rejections S
2nd lineup R S T
final outcome: A+R, B+S, C+T, D+nobody
Paradox
In many cases, these two approaches should produce the same results.
However, they will not always do so. Consider an example with two workers
A and B, and two employers X and Y, where the preference rankings are as
follows:
A: X>Y
B: Y>X
X: B>A
Y: A>B
If employers to be ‘stationary’ in the count procedure, then the
procedure goes like this:
X Y
1st lineup A B
Since employers X and Y are only presented with one candidate, there are
no rejections, and the pairs A+X, B+Y are the final outcome. However, if
workers are ‘stationary’, then you have:
A B
1st lineup Y X
The outcome is A+Y, B+X.
This is one of the simplest illustrations of the basic paradox that
occurs in reciprocal pairing. A prefers X, who prefers B, who prefers Y,
who prefers A. To make a non-random decision between outcome [A+X, B+Y]
and outcome [A+Y, B+X], we will have to make a judgment as to whose
preferences are more important.
So far we have been dividing the set of people into the two separation
groups of employer and employee. A similar separation can be made between
males and females, colleges and applicants, etc. So far our procedure has
made one group ‘stationary’ and the other group ‘active.’ It turns out
that the preferences of the group who is ‘active’ take precedence in the
case of a paradox, as illustrated above.
Hence, if you would like to prioritize the preferences of workers over
employers, then you would conduct the procedure such that the workers
‘line up’ in front of the employers, etc. In my opinion, this would work
reasonably well.
However, when you are dealing not with employers and workers but rather
with males and females trying to form relationships, this simple procedure
is more problematic to apply. There are two reasons for this: The first is
that people may not be comfortable with prioritizing the preferences of
one sex over another. The second is that in some cases pairing preferences
are not strictly heterosexual. These problems compel us to develop more
complex procedures.
Random-order method
It is possible to use a random procedure which neither prioritizes the
preference of one sex over another, nor assumes heterosexuality. Again,
the procedure will be explained with the use of some metaphor.
1. The people line up in a random order at the entrance to a room.
2. Person 1 enters the room. Person 1 is now ‘stationary’, at least for
the time being.
3. Person 2 enters the room. Person 2 is now ‘active’.
If person 1 is on person 2’s list, 2 will line up in front of 1. If 1 is
not on 2’s list, then 2 will stand by himself and wait; both will be
stationary.
If 2 lines up in front of 1 but is not on 1’s list, 1 will reject 2, and 2
will again stand by himself. If they are both on each other’s lists, then
they will be paired for the time being.
4. Person 3 enters the room, and goes up to her first choice.
If 3’s first choice is unpaired, and 3 also appears on her first choice’s
list, they will be paired.
If her first choice is already paired and they prefer the person they are
paired with to person 3, they will reject person 3. She will then approach
her second choice, or if she is out of choices, she will stand by herself
and wait.
If her first choice is already paired, but they prefer person 3 to the
person they were paired with, they will reject the other person and enter
into a pair with person 3.
That other person will now become active once again, and seek out their
own choices starting from the first and continuing down to the last.
5. As each person enters the room, there may be a flurry of pairings and
unpairings, which should eventually die down on its own accord (except in
an unlikely case which I will discuss later). Once this happens, the next
person is invited into the room.
6. This continues until everyone has entered the room, and the last series
of pair changes is finished.
To illustrate this procedure in action, I’ll return to the previous
example.
A: X>Y
B: Y>X
X: B>A
Y: A>B
Let’s say that the random ordering is 1.A 2.X 3.Y 4.B
round 1, enter A: A
round 2, enter X, X is active X+A?
X+A
round 3, enter Y, Y is active Y+A or X+A?
X+A, Y
round 4, enter B, B is active B+Y?
B+Y, X+A
To summarize, A entered first. X entered, approached her A (A being her
first and only available choice) and was accepted. Y entered and
approached A (her first choice) but was rejected in favor of X (A’s first
choice), therefore going to stand alone. B entered and approached Y (his
first choice), and was accepted (since he was not in competition with
anyone else for the pairing). In the end, A is paired with X, and B with Y.
If the order was different, the result could have been different, for
example 1.B 2.A 3.X 4.Y
round 1, enter B B
round 2, enter A, A is active B, A
round 3, enter X, X is active X+B?
X+B, A
round 4, enter Y, Y is active Y+A?
Y+A, X+B
It is theoretically possible that in some circumstances the deterministic
action of the simulated people in the room will not stop of its own accord
during a given round. For example, imagine that there are a group of four
people (homosexual, bisexual, whatever), whose pairing preferences for
each other are as follows:
A: B>D>C
B: C>D>A
C: A>B>D
D: B>A>C
Let’s say that the ordering is 1.A 2.B 3.C 4.D
round 1, enter A A
round 2, enter B, B is active B+A?
B+A
round 3, enter C, C is active C+A or B+A?
B+A, C
C is active C+B or A+B
C+B, A
A is active A+C or B+C
A+C, B
B is active B+A or C+A?
B+A, C
To summarize, B enters after A and they are paired. C then enters and
first approaches his first choice, A. A rejects him in favor of B, so C
proceeds to his next choice, B. B prefers C and rejects A. Now A, having
just been rejected by B, turns to his next choice, C. C prefers A and
rejects B, who then approaches A and gets him to dump C. A very weird
dynamic.
At this point the situation [B+A, C] is identical to the way it was
earlier in round 3, and it’s clear that this will go on repeating itself
forever, never even giving D a chance to enter the room. So in order to
make the random procedure work, you have to make a rule to govern this.
For example, you can say that when you repeat a completely identical
situation as above, the round ends without further changes taking place,
and all actors become stationary. Thus, if there is another person left to
enter the room, they will do so, and the next round will begin with them
as the only active person. If that is the last round, then the pairings
made at the time of the freeze are final.
The primary drawback of the random method is that it’s, well, random. It
is often distasteful to make important decisions by random chance. So, we
should develop a reciprocal pairing system that is nonrandom, that does
not assume division into two categories, and does not prioritize the
preferences of one category over another. It is possible to develop
various systems where first choices have greater priority than second
choices, etc. but those seem to be clumsy and in some cases indecisive.
Instead, I’ll skip directly to the method which I like the best.
Mutual favorite method, with utility-based paradox resolution
The method I am proposing is to supplement people’s ordinal rankings of
each other with cardinal ratings, such that the cardinal ratings are used
to resolve cycles. The essence of the proposal is to identify a set of
appropriate outcomes which make sense with regard to people’s ordinal
rankings, and then to choose the outcome from that set which has the
highest utility in terms of the sum of people’s cardinal ratings.
Here are the different steps to the procedure:
1. All people concerned should rank each other in terms of comparative
desirability. Equal rankings should not be allowed. People are not
required to rank everyone else who is up for consideration. They should
also rate each other on a cardinal scale, for example 1 to 100. Rankings
and ratings should be consistent with each other. (For example, I
shouldn’t rank A below B if I give A a higher rating.) There is no reason
to rate someone who you haven’t ranked; all ratings are positive.
If some people don’t bother to fill out the ratings, it would be easy
enough to assign default ratings based on their rankings, for example
rating the first choice 100, the last choice 1, and all the intermediate
choices at regular intervals between.
2. If there is any person X who doesn’t appear on person Y’s list at all,
delete Y from X’s list as well. (If a first choice is deleted from a list,
then the second choice effectively becomes the first choice, and so on.)
3. If there are any two people who are each other’s first choice, pair
them together.
4. Delete those who have been paired together from the rankings of
remaining people.
5. Repeat steps 3 and 4 until everyone has been paired or no more pairings
can be made according to these rules.
6. If all people have been paired, or if the only ones who haven’t been
paired are those such that no two people both appear on each other’s
lists, then the procedure is over and the pairings are final. If the
remaining people don’t fit this description, then we enter the more
complex part of the procedure, as follows:
7. Begin creating ‘appropriate’ outcomes, that is, outcomes which can be
reached by the following rules. The system should identify all possible
outcomes which can be reached using these rules given the indicated
preferences.
8. Identify cycles of first choice preferences, for example if A’s first
choice is B, whose first choice is C, whose first choice is D, whose first
choice is A. Identify the people who are a part of such cycles.
9. Take one person whose first choice preference is part of a cycle, and
‘relax’ their preference, so that their first choice is suspended and
their second choice becomes their first choice.
10. If there are no more cycles at this point, then continue pairing those
who are each other’s mutual first choice. If cycles still exist, then
repeat step 8.
Note: If there is a cycle which includes a person whose preference has
already been relaxed once, as well as people who have not yet relaxed a
preference, then the person who has already relaxed once should not
double-relax. In general, if members of a cycle have relaxed their
preferences a different number of times, the member who has relaxed the
fewest preferences (or one of the members are tied in terms of having
relaxed the fewest preferences) should be the next one to relax in the
attempt to resolve the cycle.
11. Steps 9 and 10 should be repeated for each divergent ‘appropriate’
outcome until they come to rest at a point where the only unpaired people
are those such that no two people appear on each other’s lists.
12. This procedure can create a tree branch of appropriate outcomes
diverging from each other given different the relaxation of different
people’s preferences to resolve cycles. All legitimate resolutions to
cycles should be accounted for, including all legitimate resolutions to
cycles that occur after other cycles were resolved.
This creates a set of appropriate outcomes. There may be one appropriate
outcome, or there may be several. Different resolutions of cycles can
often eventually lead to identical outcomes. Such redundant outcomes can
be treated as a single outcome.
13. A utility score for each outcome is calculated as follows. The utility
of the outcome for each person is defined as the desirability rating which
they gave to the person who they are paired with in that outcome. If they
are not paired with anyone in an outcome, the utility of that outcome for
them is considered to be 0.
The utility score for the outcome itself is the sum of the outcome’s
utility score for each person.
14. From the set of appropriate outcomes, the outcome with the highest
utility score wins. If there is an absolute tie between the utility scores
of different outcomes (which seems very unlikely in most circumstances),
one of the tied outcomes can be selected at random.
Now I will apply the new method to the previous example, with utility
ratings added.
A: B100>D55>C1
B: C100>D55>A1
C: A100>B55>D1
D: B100>A55>C1
initially, no mutual first choice pairs; a first preference cycle,
A-->B-->C-->A
Possible resolution 1: relax A-->B preference to A-->D
another cycle encountered, A-->D-->B-->C
Possible resolution 1-1: relax B-->C preference to B-->D
B+D pair, therefore A+C pair.
outcome 1-1 is [A+C, B+D]
Possible resolution 1-2: relax C-->A preference to C-->B
B+C pair, therefore A+D pair
outcome 1-2 is [A+D, B+C]
Possible resolution 1-3: relax D-->B preference to D-->A
A+D pair, therefore B+C pair
outcome 1-3 is [A+D, B+C]
Possible resolution 2: relax B-->C preference to B-->D
B+D pair, therefore A+C pair
outcome 2 is [A+C, B+D]
Possible resolution 3: relax C-->A preference to C-->B
B+C pair, therefore A+D pair
outcome 3 is [A+D, B+C]
all possible resolutions accounted for; appropriate outcomes are [A+C,
B+D], [A+D, B+C].
utility score [A+C, B+D] = 1(A)+100(C)+55(B)+100(D) = 256
utility score [A+D, B+C] = 55(A)+55(D)+100(B)+55(C) = 265
[A+D, B+C] has the highest utility score of appropriate outcomes, and is
selected as the final result. Note that the actors in this example
indicated larger utility gaps between their second and third choices than
between their first and second choices. If they had done the opposite,
then the outcome [A+C, B+D] would have won instead.
I will now illustrate this method with one more example, an example which
involves more people, and yet is somewhat less paradoxical and more
straightforward. The example is imagined as a group of 14 friends who
agree to write their preferences for each other on secret ballots and
submit them to an online service which uses this reciprocal pairing
algorithm. Their names are Alex, Ben, Cliff, Dan, Ed, Fred, Greg, Jodie,
Kate, Lucy, Mary, Nell, Olga, and Pam. This example is intended to be
somewhat realistic. The rankings and ratings are as follows.
Alex: Jodie100>Lucy90>Kate80
Ben: Jodie100>Kate95>Lucy70
Cliff: Dan100>Alex90>Kate20
Dan: Jodie100>Mary85>Kate60>Lucy50
Ed: Lucy100>Kate50>Jodie45>Mary35>Nell30
Fred: Kate100>Lucy90>Jodie85>Olga75>Pam70>Nell60>Mary50
Greg: Dan100>Cliff95>Ben75>Alex70
Jodie: Alex100> Ben80>Dan60>Ed30
Kate: Ben100>Alex90>Cliff85>Ed70>Dan60
Lucy: Alex100>Dan90>Cliff85>Ed80>Ben50
Mary: Cliff100>Ed90>Dan85>Ben80>Alex75>Fred60
Nell: Jodie100>Kate95>Pam85>Lucy80>Olga75>Mary70>Fred65>Cliff60
Olga: Alex100>Ben95>Dan90>Fred85>Ed80>Cliff75>Greg70
Pam: Lucy100>Kate60>Nell55>Olga50>Mary45>Jodie40
preferences redrawn so that people no longer rank people who do not rank
them
Alex: Jodie100>Lucy90>Kate80
Ben: Jodie100>Kate95>Lucy70
Cliff: Kate20
Dan: Jodie100>Mary85>Kate60>Lucy50
Ed: Lucy100>Kate50>Jodie45>Mary35
Fred: Olga75>Nell60>Mary50
Greg:
Jodie: Alex100> Ben80>Dan60>Ed30
Kate: Ben100>Alex90>Cliff85>Ed70>Dan60
Lucy: Alex100>Dan90>Ed80>Ben50
Mary: Ed90>Dan85>Fred60
Nell: Pam85>Fred65
Olga: Fred85
Pam: Nell55
Greg has no one left on his list, so he cannot be paired.
pairs of mutual first choice: Alex+Jodie, Fred+Olga, Nell+Pam
preferences redrawn to omit paired couples
Ben: Kate95>Lucy70
Cliff: Kate20
Dan: Mary85>Kate60>Lucy50
Ed: Lucy100>Kate50>Mary35
Kate: Ben100>Cliff85>Ed70>Dan60
Lucy: Dan90>Ed80>Ben50
Mary: Ed90>Dan85
pair of mutual first choice: Ben+Kate
preferences redrawn to omit paired couple
Cliff:
Dan: Mary85>Lucy50
Ed: Lucy100>Mary35
Lucy: Dan90>Ed80
Mary: Ed90>Dan85
Cliff has no one left on his list, so he cannot be paired
there is a first preference cycle, Dan-->Mary-->Ed-->Lucy-->Dan
possible resolution 1: relax Dan-->Mary preference to Dan-->Lucy
Dan+Lucy pair, therefore Ed+Mary pair
outcome 1 is [Alex+Jodie, Fred+Olga, Nell+Pam, Ben+Kate, Dan+Lucy, Ed+Mary]
possible resolution 2: relax Mary-->Ed preference to Mary-->Dan
Dan+Mary pair, therefore Ed+Lucy pair
outcome 2 is [Alex+Jodie, Fred+Olga, Nell+Pam, Ben+Kate, Dan+Mary, Ed+Lucy]
possible resolution 3: relax Ed-->Lucy preference to Ed-->Mary
Ed+Mary pair, therefore Dan+Lucy pair
outcome 3 is [Alex+Jodie, Fred+Olga, Nell+Pam, Ben+Kate, Dan+Lucy, Ed+Mary]
possible resolution 4: relax Lucy-->Dan preference to Lucy-->Ed
Ed+Lucy pair, therefore Dan+Mary pair
outcome 4 is [Alex+Jodie, Fred+Olga, Nell+Pam, Ben+Kate, Dan+Mary, Ed+Lucy]
All possible resolutions accounted for; the two appropriate outcomes are
[Alex+Jodie, Fred+Olga, Nell+Pam, Ben+Kate, Dan+Lucy, Ed+Mary],
[Alex+Jodie, Fred+Olga, Nell+Pam, Ben+Kate, Dan+Mary, Ed+Lucy]
utility score [Alex+Jodie, Fred+Olga, Nell+Pam, Ben+Kate, Dan+Lucy,
Ed+Mary, Cliff, Greg] =
100(Alex)+100(Jodie)+75(Fred)+85(Olga)+85(Nell)+55(Pam)+95(Ben)+100(Kate)+50(Dan)+90(Lucy)+35(Ed)+90(Mary)
= 960
utility score [Alex+Jodie, Fred+Olga, Nell+Pam, Ben+Kate, Dan+Mary,
Ed+Lucy, Cliff, Greg] =
100(Alex)+100(Jodie)+75(Fred)+85(Olga)+85(Nell)+55(Pam)+95(Ben)+100(Kate)+85(Dan)+85(Mary)+100(Ed)+80(Lucy)
= 1045
[Alex+Jodie, Fred+Olga, Nell+Pam, Ben+Kate, Dan+Mary, Ed+Lucy, Cliff,
Greg] has the highest utility score of appropriate outcomes, and is
selected as the final result.
Multi-valent combination
The same methods (the queue method, the random-order method, the mutual
favorite method) can be used equally well in situations when single actors
can combine with more than one other actor. For example, in an employment
service situation where different employers can each accept more than one
worker. When the number of available spaces for a single actor are very
large, methods that allow equal rankings might be desirable, primarily as
a time-saving measure.
In the queue method, for example, if an employer has 10 openings, and at
any given stage during the computation procedure there are 15 workers in
line for them, the employer will accept the top 10 and reject the bottom 5.
In the mutual favorite method, if a job is paired with a worker, but that
job still has more openings, then it is simply not deleted from the
preference rankings and continues forming pairs until all positions are
filled.
It would even be theoretically possible to use these methods to determine
which students will be admitted to and attend which colleges. Students
could rank the colleges they are applying to in order of preference.
Colleges could create rough rankings of students, where many students
might be equally ranked towards the top (those that are assured of
admission if they want it), and where some students may be unranked, but
there would be more fine distinction between students in the area of the
expected cutoff point. The criteria for admission could of course be the
same as they are now (grades, essays, etc.) but by the use of this system
colleges could come extremely close to their target enrollment without
putting students through the uncertainty of being on a waiting list.
By the way, the queue method should be wholly adequate for college
admissions purposes, and probably for employer-worker pairing as well. The
more complex mutual favorite completed by cardinal ratings method is more
intended for romantic pairing, although there may be some circumstances
where the queue method would be sufficient here as well. Of course, if
there are no top-preference cycles, then all of the methods should choose
the same result.
Strategic incentives
The possibility of top-preference cycles creates the possibility of
strategic incentive in reciprocal pairing methods. It is doubtful that
there are any circumstances where it is advantageous to actually reverse a
sincere preference ordering, but there are circumstances where it can be
advantageous to truncate your rankings. That is, to not rank someone
despite the fact that you prefer being paired to them over not being
paired.
Such truncation incentives depend on the method that is being used, and
an actor’s role in that method. In the queue method, only the group of
actors who are ‘stationary’ in the tally have strategic incentive to
truncate. If they sincerely prefer another actor to remaining unpaired,
then there is no reason not to indicate that preference, because in any
case they will not ‘line up’ in front of that option until all other
more-preferred possibilities have been exhausted. For those who are
‘stationary’, however, it is theoretically possible that rejecting an
acceptable candidate will dislodge a more-preferred applicant from
elsewhere and cause him to apply there. While the possibility exists that
such a strategy can succeed, the incentive to do so in the interest of an
uncertain benefit is should most often be outweighed by the marginal
utility of the less-preferred candidate over no one at all. In the
mutual-favorite method, a very mild truncation incentive exists for
everyone.
If the method includes rating scores, than those will also be subject to
some degree of strategic manipulation. That is, people may take into
account the probability of a preference cycle among certain actors and
adjust their ratings accordingly, rather than basing them on a ‘pure’
assessment of relative strength of preference. However, the importance of
any such distortion is likely to be limited. It will not make the change
the result from an ‘appropriate’ outcome to an ‘inappropriate’ outcome (as
defined by the mutual favorite rules), but will simply tip the balance in
favor of one appropriate outcome over another. Since the correlation of
the ratings data to the actual utility value of the pairing is likely to
be imprecise anyway, this isn’t really a big deal.
The no-mutual-advantage criterion
An outcome meets the ‘no-mutual-advantage-to-change’ criterion if,
starting from that outcome, no new pair can be formed which is perceived
as an improvement from the original outcome by both members of the new
pair.
If only one no-mutual-advantage outcome exists given a preference
ranking, then that outcome should be selected. If more than one exists,
then those outcomes and only those outcomes should be considered in a
ratings-based tiebreaker. I'm not sure how close the current version of
the mutual favorite method comes to achieving this. It is possible that no
no-mutual-advantage outcome will exist for a given set of rankings, but
such rankings are likely to be quite rare.
Applying the methods
While these methods are mathematically fun, is there any chance that they
will actually be used? I don’t know, but honestly I hope so. Their purpose
is to insert rational order and efficiency into processes that are often
fraught with uncertainty, error, and wasted effort.
As for the employment service application, that could theoretically be
applied by any employment service with an appropriate critical mass of
workers and jobs. I personally would like to see the government develop
more well-funded and effective employment services in the future; ones
which can keep abreast of a large proportion of the openings in the job
market. I hope that these methods will be a part of that effort.
As for college admissions, I think that the procedure can start on a
relatively small scale and work its way up. For example, it could be
employed first by consortiums of colleges, state school systems, and
things like that. If it works well, maybe it could eventually be
centralized nationally.
As for romantic pairing, it would be fairly easy to start an online
business around the principle. Student organizations in high schools or in
college fraternities, etc., might be willing to spend a few dollars of
their activities money to buy a round of pairings. Everyone could securely
punch their preferences in, via the internet or whatever, and then log in
later to find out the result. At the beginning it would be possible to
give the group a choice as to whether to use the simple queue method (with
either males or females as ‘stationary’) or the ratings-accompanied mutual
favorite method.
Of course, the notion of taking such an intensely rational and
straightforward approach to romantic pairing is likely to seem very alien
to a lot of people. And for it to work you’d need to get a decent number
of people involved. So maybe it wouldn’t catch on, I don’t know. I sort of
wish they had thought of it at my high school, though.
There are probably quite a few other uses for these simple algorithms
that haven’t occurred to me. It they can be useful in many different
situations where partnerships are formed from a pool of people or
institutions where everyone has more than one choice.
----
Election-methods mailing list - see http://electorama.com/em for list info
