Gale Shapley matching algorithm with Polygamy by Men Upto four Marriages Using Bipartite Graph

Question

How to modify Gale Shapley matching algorithm with Polygamy by Men Upto four Marriages Using Bipartite Graph

I want to add weights to each node of bipartite graph based on certain criteria for example age, height , education etc after all the nodes are assigned weight algorithm will be executed that recommend best possible stable matches as per the priorities of the men and women.

Conditions:

1. One man can marry one women, One man can marry two women, one man can marry three women but not more than four women at a time

2. In case of divorce or death of any women a men can get one more.

3. If man dies all females could get marry again after three months.

4. One women could marry one man at a time.

5. In case of divorce female can remarry after three months.

Import Python Libraries

import networkx as nx
import matplotlib.pyplot as plt

Example preference lists for 3 men and 3 women

men_prefs = {
    'm1': ['w2', 'w1', 'w3'],
    'm2': ['w1', 'w2', 'w3'],
    'm3': ['w1', 'w3', 'w2']
}
women_prefs = {
    'w1': ['m3', 'm1', 'm2'],
    'w2': ['m2', 'm1', 'm3'],
    'w3': ['m1', 'm3', 'm2']
}

Create the bipartite graph

B = nx.Graph()
B.add_nodes_from(men_prefs.keys(), bipartite=0)
B.add_nodes_from(women_prefs.keys(), bipartite=1)
for man, prefs in men_prefs.items():
    for woman in prefs:
        B.add_edge(man, woman)

Run the Gale-Shapley algorithm

free_men = set(men_prefs.keys())
engaged = {}
while free_men:
    man = free_men.pop()
    woman = men_prefs[man][0]
    if woman in engaged:
        current_man = engaged[woman]
        if women_prefs[woman].index(man) < women_prefs[woman].index(current_man):
            engaged[woman] = man
            free_men.add(current_man)
        else:
            free_men.add(man)
    else:
        engaged[woman] = man

Draw the graph with the new matching

pos = nx.bipartite_layout(B, men_prefs.keys())
plt.figure(figsize=(6, 4))
nx.draw_networkx_nodes(B, pos, node_color=['lightblue'])
nx.draw_networkx_edges(B, pos, edgelist=engaged.items(), edge_color='red', width=2)
nx.draw_networkx_labels(B, pos, font_size=12, font_family='sans-serif')
plt.axis('off')
plt.show()

Answer 1

Make a number of copies of each man. Run the usual algorithm. Recombine men to get your answer.

More general variations can be solved by writing it as a max flow problem and then using https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm.