Question

2. (20 pts) a. Run Gale-Shapley Algorithm and show your steps using the preference lists tables below. Are there any unstable pairs in the final match? b. Modify Gale-Shapley Algorithm such that women will propose instead of men. Show the final match. c. Compare and discuss the matches produced above in terms of men- optimality/women-pessimality and women-optimality/men-pessimality. 1st 2nd 3rd | 2nd 3rd Xavier Amy Clare Bertha Amy Xavier Yancey Zeus Yancey Bertha Clare Amy Bertha Xavier Yancey Zeus Zeus Clare Bertha Clare Xavier Zeus O Type here to search Et gee ow 16. US 23-02-2020 2

Answer 1

woman propose to men

#include <iostream>
#include <string.h>
using namespace std;

#define N 3

bool wPrefersM1OverM(int prefer[2*N][N], int w, int m, int m1)
{
   for (int i = 0; i < N; i++)
   {
       if (prefer[w][i] == m1)
           return true;

       if (prefer[w][i] == m)
       return false;
   }
}

void stableMarriage(int prefer[2*N][N])
{
   string arrm[3]={"Xavier","Yancey","Zeus"};
   string arrw[3]={"Amy","Bertha","Clare"};
   int wPartner[N];

   bool mFree[N];

   memset(wPartner, -1, sizeof(wPartner));
   memset(mFree, false, sizeof(mFree));
   int freeCount = N;
  
   while (freeCount > 0)
   {
       int m;
       for (m = 0; m < N; m++)
           if (mFree[m] == false)
               break;
       for (int i = 0; i < N && mFree[m] == false; i++)
       {
           int w = prefer[m][i];
           if (wPartner[w-N] == -1)
           {
               wPartner[w-N] = m;
               mFree[m] = true;
               freeCount--;
           }

           else
           {
               int m1 = wPartner[w-N];
               if (wPrefersM1OverM(prefer, w, m, m1) == false)
               {
                   wPartner[w-N] = m;
                   mFree[m] = true;
                   mFree[m1] = false;
               }
           }
       }
   }

   cout << "Woman Man" << endl;
   for (int i = 0; i < N; i++)
   cout << " " << arrw[i] << "\t" << arrm[wPartner[i]] << endl;
}

int main()
{
   int prefer[2*N][N] = { { 4, 5, 3},
       {4, 3, 5},
       {3, 4, 5},
       {0, 1, 2},
       {0, 1, 2},
       {0, 1, 2},
   };
   stableMarriage(prefer);

   return 0;
}

man propose to woman

simply change arrm and arrw in code

#include <iostream>
#include <string.h>
using namespace std;

#define N 3

bool wPrefersM1OverM(int prefer[2*N][N], int w, int m, int m1)
{
   for (int i = 0; i < N; i++)
   {
       if (prefer[w][i] == m1)
           return true;

       if (prefer[w][i] == m)
       return false;
   }
}

void stableMarriage(int prefer[2*N][N])
{
   string arrm[3]={"Xavier","Yancey","Zeus"};
   string arrw[3]={"Amy","Bertha","Clare"};
   int wPartner[N];

   bool mFree[N];

   memset(wPartner, -1, sizeof(wPartner));
   memset(mFree, false, sizeof(mFree));
   int freeCount = N;
  
   while (freeCount > 0)
   {
       int m;
       for (m = 0; m < N; m++)
           if (mFree[m] == false)
               break;
       for (int i = 0; i < N && mFree[m] == false; i++)
       {
           int w = prefer[m][i];
           if (wPartner[w-N] == -1)
           {
               wPartner[w-N] = m;
               mFree[m] = true;
               freeCount--;
           }

           else
           {
               int m1 = wPartner[w-N];
               if (wPrefersM1OverM(prefer, w, m, m1) == false)
               {
                   wPartner[w-N] = m;
                   mFree[m] = true;
                   mFree[m1] = false;
               }
           }
       }
   }

   cout << "Woman Man" << endl;
   for (int i = 0; i < N; i++)
   cout << " " << arrm[i] << "\t" << arrw[wPartner[i]] << endl;
}

int main()
{
   int prefer[2*N][N] = { { 4, 5, 3},
       {4, 3, 5},
       {3, 4, 5},
       {0, 1, 2},
       {0, 1, 2},
       {0, 1, 2},
   };
   stableMarriage(prefer);

   return 0;
}

hope you can compare both the codes output as both codes are working.

don't forget to rate