Algorithm Design Chapter 1 Exercise 8: and the stream or input 2 Were Switched o

Question

Algorithm Design Chapter 1 Exercise 8:

and the stream or input 2 Were Switched onto output 2, then both streams Would pass through the junction box at the meeting of Input 1 and Output 2-and this is not allowed. 8. For this problem, we will explore the issue of truthfulness in the stable Matching Problem and specifically in the Gale Shapley algorithm. The basic question is: Can a man or a woman end up better off by lying about his or her preferences? More concretely, we suppose each participant has a true preference order. Now consider a woman w. Suppose w prefers man m to m but both m and m' are low on her list of preferences. Can it be the case that by switching the order of m and m' on herlist of preferences (i.e., by falsely claiming that she prefers m' to m) and running the algorithm with this false preference list, uy will end up with a man m" that she truly prefers to both m and m'? (We can ask the same question for men, but will focus on the case of women for purposes of this question.) Resolve this question by doing one of the following two things: (a) Give a proof that, for any set of preference lists, the order of a pair on the list cannot improve a woman's partner in the Gal Shapley algorithm; or

Explanation / Answer

#include <iostream>

#include <string.h>

#include <stdio.h>

using namespace std;

// Number of Men or Women

#define N 4

// This function returns true if woman 'w' prefers man 'm1' over man 'm'

bool wPrefersM1OverM(int prefer[2*N][N], int w, int m, int m1)

{

    // Check if w prefers m over her current engagment m1

    for (int i = 0; i < N; i++)

    {

        // If m1 comes before m in lisr of w, then w prefers her

        // cirrent engagement, don't do anything

        if (prefer[w][i] == m1)

            return true;

        // If m cmes before m1 in w's list, then free her current

        // engagement and engage her with m

        if (prefer[w][i] == m)

           return false;

    }

}

// Prints stable matching for N boys and N girls. Boys are numbered as 0 to

// N-1. Girls are numbereed as N to 2N-1.

void stableMarriage(int prefer[2*N][N])

{

    // Stores partner of women. This is our output array that

    // stores paing information. The value of wPartner[i]

    // indicates the partner assigned to woman N+i. Note that

    // the woman numbers between N and 2*N-1. The value -1

    // indicates that (N+i)'th woman is free

    int wPartner[N];

    // An array to store availability of men. If mFree[i] is

    // false, then man 'i' is free, otherwise engaged.

    bool mFree[N];

    // Initialize all men and women as free

    memset(wPartner, -1, sizeof(wPartner));

    memset(mFree, false, sizeof(mFree));

    int freeCount = N;

    // While there are free men

    while (freeCount > 0)

    {

        // Pick the first free man (we could pick any)

        int m;

        for (m = 0; m < N; m++)

            if (mFree[m] == false)

                break;

        // One by one go to all women according to m's preferences.

        // Here m is the picked free man

        for (int i = 0; i < N && mFree[m] == false; i++)

        {

            int w = prefer[m][i];

            // The woman of preference is free, w and m become

            // partners (Note that the partnership maybe changed

            // later). So we can say they are engaged not married

            if (wPartner[w-N] == -1)

            {

                wPartner[w-N] = m;

                mFree[m] = true;

                freeCount--;

            }

            else // If w is not free

            {

                // Find current engagement of w

                int m1 = wPartner[w-N];

                // If w prefers m over her current engagement m1,

                // then break the engagement between w and m1 and

                // engage m with w.

                if (wPrefersM1OverM(prefer, w, m, m1) == false)

                {

                    wPartner[w-N] = m;

                    mFree[m] = true;

                    mFree[m1] = false;

                }

            } // End of Else

        } // End of the for loop that goes to all women in m's list

    } // End of main while loop

    // Print the solution

    cout << "Woman   Man" << endl;

    for (int i = 0; i < N; i++)

       cout << " " << i+N << " " << wPartner[i] << endl;

}

// Driver program to test above functions

int main()

{

    int prefer[2*N][N] = { {7, 5, 6, 4},

        {5, 4, 6, 7},

        {4, 5, 6, 7},

        {4, 5, 6, 7},

        {0, 1, 2, 3},

        {0, 1, 2, 3},

        {0, 1, 2, 3},

        {0, 1, 2, 3},

    };

    stableMarriage(prefer);

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.