Optimal pairings with possible lengths

Question

There are 8 people; $x_1, x_2, x_3, x_4, y_1, y_2, y_3, y_4$.

They have all visited a dating cafe and each have to take someone home tonight, they have given their preferred preferences.

$x_1: y_2 > y_4 > y_1 > y_3$

$x_2: y_3 > y_1 > y_2 > y_4$

$x_3: y_4 > y_2 > y_3 > y_1$

$x_4: y_1 > y_3 > y_4 > y_2$

$y_1: x_1 > x_3 > x_2 > x_4$

$y_2: x_2 > x_4 > x_3 > x_1$

$y_3: x_3 > x_1 > x_4 > x_2$

$y_4: x_4 > x_2 > x_1 > x_3$

Each pair is randomly allocated for example;

$x_1 + y_3, x_2 + y_4, x_3 + y_1, x_4 + y_2$

Then you go through and find an $x$ and a $y$ that would prefer to be with each other than their current pairing. In this case $x_1 + y_1$ would prefer to be together. So they swap.

$x_1 + y_1, x_2 + y_4, x_3 + y_3, x_4 + y_2$

Now we see $x_2 + y_2$ would prefer to be together so we swap them.

$x_1 + y_1, x_2 + y_2, x_3 + y_3, x_4 + y_4$

Now there are no pairs that would prefer to be together than with their current assigned partners so we stop swapping.

If there are 2 options of swaps then one is done first then the other is done on the next occasion.

We call each swap a link and the whole thing is called a chain.

What is the length of the longest chain? and what is the length of the longest chain that features at least every pairing?

Currently I am stuck with where to even begin with a problem like this.

Answer 1

First, determine the overall optimal pairings. Let's assign the value $1$ to a pairing with the first preference, the value $2$ to a pairing with the second preference, etc. The value of a pairing between $x_i$ and $y_j$, as seen by $x_i$, will be called $V_x(i,j)$ and the value of a pairing between $x_i$ and $y_j$, as seen by $y_j$, will be called $V_y(i,j)$. The total value of a pairing between $x_i$ and $y_j$ will be $V(i,j) = V_x(i,j) + V_y(i,j)$. If we then look at all possible pairings of $x_i$ and $y_j$ we get the following:

We see that the pairings with the lowest combined score and therefore the overall optimal pairing, is the pairing with a score of $16$, namely the pairing: $x_1+y_1, x_2+y_2, x_3+y_3, x_4+y_4$.

That was the "hard" part. It should be easy to see that turning a non-optimal pairing into an optimal pairing can at most take $3$ swaps. First swap the right $y_i$ partner to $x_1$, then (if needed) swap the right $y_i$ partner to $x_2$, and finally (if needed) swap the right $y_i$ partner to $x_3$. An example of a worst case starting scenario would be: $x_1+y_2, x_2+y_3, x_3+y_4, x_4+y_1$.