Marriage Problem Algorithm Based on Maximum-Preferred Rank Selection Method

In this paper I propose a simple optimal solution seeking algorithm to a stable marriage problem. The proposed algorithm firstly constructs an n×n matrix of the sum of each gender’s preference of the other gender Pij. It then selects the minimum sum preference minPij in the constructed matrix and deletes its corresponding row i and column j. This process is repeated until i=0 ∩ j=0, after which the algorithm compares initially or last chosen minPij its alternatives to finally determine one that yields the maximum marginal increase in preference. When applied to 7 stable marriage problems, the proposed algorithm has improved on initial solutions of existing algorithms.