Optimal Strategy for Matching Pairs

Question

I found a reality TV show recently that I thought would make a fun puzzle. On the show are 10 men and 10 women that have been "matched by experts" (ie. randomly paired). Their goal is to determine which men were paired with which women (all couples are heterosexual); either they get all 10 correct and everyone wins or everyone loses. With 10! (more than 3.6 million) ways of pairing up this would be nearly impossible without more information.

How they get information:

• Each week the players can "test" one pair to determine if they are a correct match (e.g. are Alice and Andrew a correct couple, yes or no).
• After the previously stated test, all 20 people pair up into 10 couples and they are told how many of the couples are correctly paired. (e.g. 4/10 couples are correct).

What is the minimum number of weeks to guarantee all people have been correctly paired into couples? What is the optimal testing strategy to achieve this result?

Answer 1

Update:

You can adapt the ideas below to create a random "decision tree" and successively optimize sub-parts of it to get a bound on the worst case. I was able to get a worst case bound of 25 (13 single matches and 12 multi-matches), or 13 weeks. The expected number of weeks is 8.1

The tree is (obviously) large, 5713029 nodes, so there is no convenient way of sharing it.

Again, I have no idea how far it is from optimal. 24 might be possible, but I will be surprised if it can be less.

---

It will be difficult to establish an optimal strategy (personal opinion).

As "baseline" we can consider picking a random action (either a single matching or 10-10 pairing) which is consistent with all previous data. Here are the results of a 100 simulated runs of this strategy:

Number of "weeks" : times out of 100 tries

5: 2
6: 4
7: 17
8: 30
9: 32
10: 10
11: 4
12: 1

In each week there is one additional "single" matching test/result and one 10-10 pairing. This suggests that even without optimality you can usually get it done in 8 to 10 weeks.

For illustration, here are the number of consistent permutations for one run, in the format: start,after-single-pair,after-10-10-pair.

week 1: 3628800,3265920,1186632

week 2: 129523,47240,41311

week 3: 14998,13369,4783

The numbers drop relatively fast. You might be able to devise a close to optimal strategy when the number falls below 5000 or so.

Answer 2

Starting with no optimization, then adding more with each strategy:

Using only the first clue (test A):

10 men each get tested with 10 women each = 10*10 = 100 weeks

Assuming the worst luck (AtWL), man 1 gets tested with 10 women. Man 2 gets tested with the remaining 9 unpaired women, and so on = 10+9+8+...+1 = 55 weeks

Using strategy 2, AtWL, man 1 doesn't need to get tested with the 10th woman because she is the only woman who isn't not paired with him. The same can be applied to the other 9 men = 9+8+7+...+0 = 45 weeks

Incorporating the second clue (test B):

Using strategy 3, suppose man 1 doesn't get paired with woman 1 in test A. Pair man 1 with woman 2 in test B. If there is at least 1 pair, put man 1 with woman 2 in the next test A. If there are no pairs, we can assume that man 1 and woman 2 aren't a pair, and therefore pair man 1 with woman 3 in the next test A. When we begin to test man 2, always pair man 1 with the correct woman in test B. Now, if there's only 1 pair, we know that that is man 1, and can assume that man 2's pair doesn't work. This can repeat with all men. AtWL, it will still take 45 weeks, but the odds are slightly better.

I know that this isn't nearly optimized, but it's a good upper bound for the time being.

Answer 3

General Principles of the Approach

So I've started trying to tackle this myself and here are a few things I am observing and considering.

First thing is I can think of two possible strategies for trying to solve this problem. (not using spoilers since this is just speculation).

1. At each step try to minimize the total number of possible solutions in the worst case scenario as posted in a prior blog looking at this problem.
2. At each step try to minimize the entropy of the worst case scenario.

I see the rationale for minimizing the number of possible solutions as you are effectively narrowing your total search space. However, my gut says minimizing the entropy may be more effective as it seems more optimal to have slightly more possible solutions where most people have only one or two possible partners, than to have fewer possible solutions but more possible outcomes per person.

I also want to note, both of these approaches assume the success of a greedy strategy. I have no justification for this, but I cannot think of a computationally tractable way of approaching the problem otherwise. Additionally I will assume the worst case scenario outcome can also be found using a greedy strategy for the same reason.

During this post I will refer to the two members of each couple using capitol letters ("A", "B", "C", etc.) with each letter A-J referring to one man and the same letters A-J representing one woman. A couple pair will be indicated by a hyphenation of the two letters ("A-A", "A-B") where the position represents the gender of the person.

Week 1

First observation is that at week one:

It does not matter what couple is chosen to test as they are all equivalent at this state nothing distinguishes any of the members.

For ease of communication we will designate the first couple to be tested as:

A-A

For both strategies the worst case scenario is:

A-A is not correct.

This gives the following matrix of possible options were the number in each box of the grid represents the number of possible scenarios where the person in each row is correctly paired with the person in each column.

Going into the couple matching test for week 1 we can observe that

All the couples that haven't been paired are still equivalent so there is only one choice to make; Do you keep the first tested (and failed) couple together for the ceremony or do you match them with new partners.

At this point came my first big surprise. I assumed that the optimal choices for the two strategies would be very similar for the most part but instead I discovered

The optimal choice for reducing the number of options was to give A-A new partners (1334961 options for stay, 1201464 for switch), but the optimal choice for reducing the entropy was to keep them together (entropy 0.99483 for stay, 0.99516 for switch)!

In both cases

The worst case scenario is for 1/10 couple to be a correct match.

Which produces the following matrix for strategy which minimized the number of possible options:

With black outlines representing the tested couples and white text representing best choices of couples to evaluate next week. For the entropy based strategy, the matrix is: