A bipartite graph marriage problem.

[JoeSal]

Let's start with the problem:


There are N men and N women who are to be paired. Each man and each woman rank their potential partners 1 through N with 1 signifying their favorite or highest choice.

The men and women agree to let one sex be the suitor and the other sex be the pursued.

You have to determine if the process described below terminates with everyone paired and with no pairing unstable in the sense that there would not exist a “final “ pairing that one of the partners in the pair could find another potential partner in another paring so that each of them would have a pairing of higher partners than their current final pairing. In other words, they have the highest ranked partner available.


Process

1) All unpaired suitors stand before the highest ranked possible unpaired partner in their list ( initially every suitor goes before the person they ranked 1.
2) The pursued look at the suitors standing before them
a. If one of the suitors is the highest remaining ranked person in their list, they accept the suitor and they are officially paired.
b. If more than one suitor stands before them and none of them is the highest ranked person in their list, they tell the highest ranking of them they( the pursued) continue to evaluate the proposal and tell the others standing before them that under no circumstances will they be their partner and to remove the pursued’s name from the suitors list.
3) All unpaired individuals remove the names of paired individuals from their lists.
4) Until all individuals are paired go to step 1).

Does the process terminate or is it an infinite loop?

Does the suitor or the pursued get the highest ranked partner in their list who would pair with them?

---------------------------------------

From what I understand, bipartite graphs are graphs where no edges exists between nodes in the same set.

So, from what I have read in the problem description, the goal here is to have each pair of couples consist of the highest possible ranks for each invidual in the pair...and furthermore, to have no two (or more) pairs be able to break up and each all of those individuals find a partner of a higher rank.

So let's say N = 2. Therefore, there are 2 men and 2 women: M1, M2, W1, W2.

list in order of interest:
M1: W1, W2
M2: W1, W2
W1: M1, M2
W2: M1, M2

men stand before the women, so:

M1,M2 stands before W1
W1 has M1 at the top of the list, so they are paired. therefore, M2 and W2 are paired. But what if M1 and W2 were paired and M2 and W1 were paired? rather than a pair of 1,1 and 2,2; it would be a pair 1,2 and 1,2...in terms of ranks. if a pair were to break up, could both people find a person of higher rank?? No, not in either situation, either a person would find someone higher, lower, or the same. but not all higher. this is where i am confused, i should probably be looking into the math more rather than thinking to far into it.

Any help would be much appreciated.
Thanks.

 

[daon]

If this is the standard process for the pairing problem, then yes, it terminates. I studied this problem in depth a couple years ago, but I don't remember much.

If M1's list is W1,W2 and M2's list is W2, W1... W1's list is M2 M1, W2's list is M1, M2 then both of the following are stable pairs:

M1-W1 & M2-W2 (W1 prefers M2 but M2 prefers W2)
M1-W2 & M2-W1 (W2 prefers M2, but M2 prefers W2)

I believe the standard algorithm is like this (it looks close to what you have):

A man proposes to his favorite woman
....If the woman is not engaed, she accepts
....If she is engaged, she compares the two men and takes the better one
........If she prefers her current partner, the man goes onto the next woman on his list (back to beginning)
........If she prefers the proposing man, she lets go her current partner and he is added to the back of the line (or anywhere in line, doesn't matter). Choose another man and continue.

The order in which it happens does not matter and it does not matter how the men are added back to the list. The end always ends in a stable matching. We proved this in our class but I couldn't do it now for the life of me.