Life Tips & Miscellaneous Navigation of this blog Travel and History Zen and Life Tips Machine Learning Digital Transformation Artificial Intelligence Deep Learning Economy and Business
The stable marriage problem algorithm
The Stable Marriage Problem (SMP) algorithm is a type of problem and solution method for achieving ‘stable matching’ between two groups. The most famous solution to this problem is the Gale-Shapley Algorithm (Gale-Shapley Algorithm), which can efficiently find stable combinations, and this algorithm has been used in particular for matching medical students with hospitals, job applicants with companies It will be applied to many real-life matching problems, such as matching medical students and hospitals, and job seekers and companies.
The stable marriage problem aims to find matches that satisfy the following conditions.
1. there are two groups (men and women or two types of candidates), each member having an order of preference for members of the opposite sex
2. the matching must be ‘stable’. Here, ‘stable’ refers to a state in which no pair of two people prefer each other to the current pairing (the presence of such a pair is ‘unstable matching’).
The Gale-Shapley algorithm will seek stable matching by the following procedure. The algorithm is divided into a ‘suitor’ and a ‘chooser’, where the suitor actively makes a proposal (application) and the chooser decides whether to accept it or not.
1. initial setup: each member has a list of preferences for members of the opposite sex, and all pairings are undetermined
2. courting and establishing a tentative match: the courting member (e.g. male) proposes to the chooser (e.g. female) at the top of the preference list, and the chooser acts according to the following rules if the proposal is accepted.
If there is no pairing yet, accept the proposal temporarily (provisional matching).
If already provisionally paired with another person, the current provisional pair is compared with the new proposal and the one with the higher preference is kept. The one with the lower preference is rejected.
3. retry if rejected: if a member of the suitor side is rejected for a proposal, the member goes to the next option on the list and proposes again, repeating this procedure until a stable pairing is finally achieved.
4. completion of stable matching: stable matching is established when all members have been paired and there are no longer any new pairs arising.
Such an algorithm is applicable in the following cases.
Male preference list:
– Man A: Woman X > Woman Y > Woman Z
– Man B: Female Y > Female X > Female Z
– Man C: Female X > Female Z > Female Y
Women’s preference list:
– Female X: Male B > Male A > Male C
– Female Y: Male A > Male B > Male C
– Female Z: Male A > Male B > Male C
In the above case, as the algorithm progresses, all members eventually form stable pairs.
Features and characteristics of the Gale-Shapley algorithm include
- Guaranteed stability: the Gail-Shapley algorithm always provides stable matches, which prevents unstable combinations from occurring.
- Results in favour of the suitor: the algorithm is known to produce stable matches in favour of the proposer (the suitor).
- Efficiency: it is also computationally efficient, and by repeating the courtship and selection procedure, a stable matching can be obtained in a relatively short time.
The algorithm can efficiently produce matches that are easily acceptable to both parties, which is expected to increase the utility of society as a whole.
implementation example
An example Python implementation of the Gale-Shapley algorithm (stable marriage problem algorithm) is shown below. In this code, the man is set as the suitor and the woman as the chooser, and the stable pairs are created using the man’s preference list and the woman’s preference list.
def stable_marriage(men_preferences, women_preferences):
# Number of men and women
num_men = len(men_preferences)
# Continue until everyone is matched.
free_men = list(range(num_men)) # List of men with no confirmed matches.
engaged_to = [None] * num_men # Lists holding who women are engaged to.
proposals = [[False] * num_men for _ in range(num_men)] # Whether it has been proposed or not
# Putting women's preferences in dictionary form for fast access.
women_rank = [
{man: rank for rank, man in enumerate(preferences)}
for preferences in women_preferences
]
# Matching process
while free_men:
man = free_men[0] # Select one free man.
man_pref = men_preferences[man]
# Propose in turn to women who can propose.
for woman in man_pref:
if not proposals[man][woman]: # For women who have not yet proposed.
proposals[man][woman] = True # Proposed and recorded
if engaged_to[woman] is None:
# Engagement if the woman is free.
engaged_to[woman] = man
free_men.pop(0) # Remove them from the free men's list.
break
else:
# If engaged, compare whether the man is more likeable
current_partner = engaged_to[woman]
if women_rank[woman][man] < women_rank[woman][current_partner]: # Renew engagement if women prefer new men.
engaged_to[woman] = man free_men.pop(0) free_men.append(current_partner) # Free your ex-fiancee.
break # Final matching results
matches = [(man, woman) for woman, man in enumerate(engaged_to)] return matches # List of preferences (e.g.)
men_preferences = [ [0, 1, 2], # Preference of male 0 (female 0 > female 1 > female 2)
[1, 0, 2], # Male 1's preference.
[1, 2, 0] # Male 2's preference.
]
women_preferences = [
[2, 0, 1], # Preference of female 0 (male 2 > male 0 > male 1)
[0, 1, 2], # Women 1 Preference.
[1, 2, 0] # Women 2 Preferences.
]
# execution
result = stable_marriage(men_preferences, women_preferences)
for man, woman in result:
print(f"Man {man} is matched with Woman {woman}")Code description:.
- Initial settings:
- FREE_MEN: List of free men. It is retained until a man is matched.
- ENGAGED_TO: records who the woman is engaged to; a value of None indicates that the woman is not yet engaged.
- proposals: this will be a list for men to keep track of the women they have already proposed to.
- Main loop:
- Until all men are engaged, select free men and propose to women in order of preference.
- If a woman is free, she becomes engaged to the man who proposed to her.
- If already engaged, she compares the preferences of her current fiancé and the newly proposed man and chooses the man she prefers better. The former fiancée becomes free again.
- Display of final matching results:
- When all pairs have reached a stable match, the result is stored in the matches list.
Example execution result: execution of the above code produces the following output.
Man 0 is matched with Woman 0
Man 1 is matched with Woman 1
Man 2 is matched with Woman 2Application examples
The Stable Marriage Problem and the Gale-Shapley algorithm have been used in a variety of real-life areas where there are multiple decision-making actors. Typical applications are listed below.
1. matching medical students with hospitals (residency matching):
– Summary: The problem of stably matching medical students‘ preferences with hospitals’ acceptance preferences when selecting hospitals for residencies after graduation.
– Countries where it is used: matching systems using this algorithm are in operation every year in the USA, Canada, Japan and other countries.
– Effectiveness: optimal placements based on the wishes of both medical students and hospitals have been achieved, contributing to improved hospital quality and medical student satisfaction.
2. matching job seekers with companies:
– Summary: The problem of stably matching job seekers with the skills and aptitudes required by companies with the desired conditions of the job seekers.
– Example of use: used for matching candidates and companies in graduate recruitment, internships, etc.
– Effectiveness: stabilises the matching between job seekers and companies, reduces turnover and promotes the optimum allocation of human resources.
3. school choice programmes:
– Summary: The issue of allocation to schools based on the wishes of parents and students. It is difficult to ensure that all students are allocated according to their preferences for schools with a high concentration of applicants, e.g. in urban areas.
– Cities where it has been used: introduced into school choice systems in cities such as Boston, New York and Denver.
– Effectiveness: has helped to achieve stable school placements based on parent and student preferences and has contributed to higher levels of satisfaction.
4. organ transplant networks:
– Summary: Organ transplantation requires stable matching of patient waiting lists with organ donor lists. Stable matching is particularly required when paired donations (e.g. transplant requests between relatives) such as kidneys are involved.
– Effectiveness: more efficient matching of organ donors and patients, enabling more patients to receive compatible organs in a timely manner.
5. shared house/roommate matching:
– Summary: Some, mainly students and young adults, use the Gale-Shapley algorithm for roommate selection. It allows for stable matching based on preferences and lifestyle.
– Effectiveness: living with people who are mutually preferable makes long-term room-sharing possible.
6. online dating and matching apps:
– Summary: attempts are being made to stabilise matching in dating and other applications, taking into account users’ preferences and interests.
– Effectiveness: ‘stable’ combinations that take into account users’ preferences are possible, facilitating the formation of compatible couples.
7. pair programming and team building:
– Summary: The algorithm is used in companies and schools to select suitable partners for projects and pair programming.
– Effectiveness: having pairs that are deemed to be compatible with each other improves team performance and increases the efficiency of collaborative work.
8. engagement and matching services:
– Summary: The field of matching services also makes use of the Stable Marriage Problem algorithm to reflect user preferences and achieve matching stability.
– Effectiveness: stable, mutually favourable matching is possible, which is expected to improve the marriage rate.
The Gale-Shapley algorithm enables stable matching that respects each other’s preferences, which improves the satisfaction of the parties with the matching outcome. It is also expected to enable each entity to realise the optimal use of resources and to increase social efficiency as a whole.
reference book (work)
Reference books related to the stable marriage problem algorithm and matching theory are discussed.
4. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis
コメント