JoeSal

04-30-2007, 07:42 PM

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.

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.