The Problem

Decide whether the following statement is true or false:

If you state true then you will have to formally argue why the statement is correct. If you state false, then you have to give a counter-example.

The Problem

Exercises $1$ and $2$ in Chapter $1$.

The Problem

It is the year 2035 and only two online video content platforms have survived the frenzied competition to get people to watch their ``TV" online. ¹ In the future, Amazing and Bombastic are the two surviving platforms. As is the case now, both these platforms release all the episodes of a new show on the same day and the future consumer has been trained to watch all of the episodes in one sitting. However, Amazing (henceforth just called $A$) and Bombastic (henceforth just called $B$) are still competing with each other and they have to figure out how to schedule the release dates of their new shows for fall of 2035.

In particular, $A$ and $B$ have $n$ shows in their roster that they want to schedule on the same $n$ release dates.

Since this is 2035 both $A$ and $B$ have the entire TV show preferences of every human being on the planet, given a show $m$ it can accurately predict a rating for $m$. You can assume that the rating is an integer and a larger rating the larger number of viewers will watch that show (and hence make more money). We say for a given release date a platform wins the release date if its released show on that date has a higher rating than any other show released on the same day.

At the beginning of each fall, $A$ reveals a schedule $S$ and $B$ reveals a schedule $T$. A schedule for a platform assigns each of its $n$ shows to the $n$ release dates. Thus, given the schedules $S$ and $T$, each release date has exactly two shows being released on that date: one from $A$ and another from $B$. The goal of the studios in designing the schedules $S$ and $T$ is to win on as many release dates as possible.

In this problem, you will explore the notion of stability in this context. In particular, a given pair of schedules $(S,T)$ is said to be stable if no platform can unilaterally change its own schedule and end up winning on more release dates. More precisely, the pair of schedule $(S,T)$ is stable if for any alternate set of schedules $S'$ for $A$, $A$ wins on no more release dates with the pair of schedules $(S',T)$ than with the pair $(S,T)$. Further, for any other schedule $T'$ for $B$, $B$ wins on no more release dates with the pair of schedules $(S,T')$ than with the pair $(S,T)$.

Here is an example to illustrate the above. Consider the case of $n=3$ and $A$ has show/rating pairs of $(m_1,100), (m_2,101), (m_3,102)$ while $B$ has pairs $(m_4,1), (m_5,2), (m_6,3)$, where each $m_i$ is a show and the corresponding number is its rating. In this case every pair of schedule $(S,T)$ is stable (since $A$ wins on all the release dates irrespective of the schedule).

The corresponding question to one we asked in class is the following: For every set of $n$ shows and their corresponding ratings, does there always exist a stable pair of schedules?

Here are the two parts:

• Part (a): Show that the answer is yes for the following special case: the lowest rating of any show in $A$ is strictly larger than the largest rating of any show in $B$.
• Part (b): Resolve the question for the general case in one of the following two ways:
  • Give an algorithm that for any set of shows for $A$ and $B$ and their corresponding ratings, computes a stable pair of schedules (aka the answer is yes); OR
  • Give an example of shows and their corresponding ratings, for which there does not exist any stable pair of schedules (aka the answer is no).

  Note

  It is helpful for this problem, to formally write down in first order logic, what the problem is asking for. To help y'all out, here is an overview of what you need to do:

  • If you are providing an algorithm then for every input, your algorithm should output a pair of schedules $(S,T)$ that is stable. You will also have to prove that your algorithm outputs a pair of stable schedules on every input.
  • if you are providing a counter-example, then you have to present only one input and then prove that every possible pair of schedules $(S,T)$ is NOT stable.

The Problem

In class we will shortly see that every stable matching instance has at least one stable matching. We have also seen a stable matching instance that has two stable matchings. In this problem, you will be asked to come up with stable matching instance that have (many) more stable matchings. Here are the two parts:

• Part (a): Show that for every large enough $n$, there is a stable matching instance on $n$ men and $n$ women such that the instance has at least $\Omega(n)$ distinct stable matchings.
• Part (b): For every $n \ge 2$ that is a multiple of $2$, show that there is a stable matching instance on $n$ men and $n$ women such that the instance has at least $2^{n/2}$ distinct stable matchings.

  To get full credit, you should be able to present an instance for every $n \ge 2$ that is a multiple of $2$.

  Hint

  First try and construct such an instance for $n=2$. Try and extend the instance to every $n$ that is a multiple of $2$.

  Note

  If you show a family of instances with (many) more stable matchings than $2^{n/2}$ that is of course fine. In fact, if you are looking for a puzzle, try and prove as large a lower bound on the number of stable matching as you can. If you get something better than say $3^n$ come talk to me. Warning: Be warned that doing so might not be easy (it took many decades for such a result to be proven).

The Problem

Given an input for the stable matching problem, output all stable matchings for that instance.

Input

The input is an instance of the stable marriage problem in a text file of the following format:

                n                                 <- Number of men and women (each)
                m11  m21  m31 ...  mn1              <- Preference of the 1st woman (most preferred first)
                m12  m22  m32 ...  mn2              <- Preference of the 2nd woman (most preferred first)
                m13  m23  m33 ...  mn3              <- Preference of the 3rd woman (most preferred first)
                .
                .
                .
                m1n  m2n  m3n ...  mnn              <- Preference of the nth woman (most preferred first)
                w11  w21  w31 ...  wn1              <- Preference of the 1st man (most preferred first)
                w12  w22  w32 ...  wn2              <- Preference of the 2nd man (most preferred first)
                w13  w23  w33 ...  wn3              <- Preference of the 3rd man (most preferred first)
                .
                .
                .
                w1n  w2n  w3n ...  wnn              <- Preference of the nth man (most preferred first)

For example

                4                               <- Number of men and women (each)
                3   4   2   1                   <- Preference of the 1st woman (most preferred first)
                2   4   3   1                   <- Preference of the 2nd woman (most preferred first)
                2   3   4   1                   <- Preference of the 3rd woman (most preferred first)
                4   1   2   3                   <- Preference of the 4th woman (most preferred first)
                1   2   3   4                   <- Preference of the 1st man (most preferred first)
                3   1   4   2                   <- Preference of the 2nd man (most preferred first)
                2   1	4   3                   <- Preference of the 3rd man (most preferred first)
                4   1   2   3                   <- Preference of the 4th man (most preferred first)

Output

The output is the set of all stable matchings for the input in a text file of the following format:

                x                                             <- Number of stable matchings found
                [(m11,1),(m21,2),(m31,3),(m41,4),...,(mn1,n)]       <- Pairing of the form (m,w)
                [(m12,1),(m22,2),(m32,3),(m42,4),...,(mn2,n)]       <- Each stable matching is sorted by women (1...n)
                [(m13,1),(m23,2),(m33,3),(m43,4),...,(mn3,n)]
                .
                .
                .
                [(m1x,1),(m2x,2),(m3x,3),(m4x,4),...,(mnx,n)]       <- xth stable matching

Please note that each stable matching outputted is sorted by women first. For example:

                3                               <- Number of stable matchings found
                [(3,1),(1,2),(2,3),(4,4)]       <- Pairing of the form (m,w)
                [(4,1),(2,2),(1,3),(3,4)]
                [(4,1),(3,2),(1,3),(2,4)]

Please note that the above output is an example just for illustration purposes and is not the correct solution to the input example given above. For correct pairs of input and output, please look at any of the provided input/output pairs.