I bet you were not expecting a photo of 22 youngsters in swimsuits in a math blog, were you? The first time I heard about this reality TV show called "Are You The One?", my nerdiness and love for OR yelled at me: "There is so much math in this show!!!"

I'm sure producers did not mean it that way, but I saw mathematical optimization in it and just HAD to code it. Season 7 is premiering August 15th, and if you are as nerdy as I am, you should use my code to figure out the solution way before the all the participants do.

**The show**

According to Wikipedia, "Are You The One?" is a reality TV show produced by MTV, in which a group of men and women are secretly paired into male-female couples via a matchmaking algorithm. Then, while living together, the contestants try to identify all of these "perfect matches." If they succeed, the entire group shares a prize of up to $1 million.

In each episode, the participants get two new pieces of information about the coupling:

- They get to choose one couple to go to the "truth booth" and ask if that couple is a perfect match or not.
- They all pair up in a "matching ceremony" and get to know how many couples they got right (not which ones though).

This way, after each episode they have an increasing amount of information to find their matches. If they don't find it by episode 10, they lose.

**The math**

This problem can be solved through constraint programming because we're attempting to find all possible solutions (couples matches) that satisfy certain constraints (such as "Pete and Lola are NOT a couple" or "out of these given 10 couples only 2 are correct"). The more information you get as the weeks go by, the more constrained your problem is and the fewer feasible solutions you have - until you are left with only one (hopefully at most by week 10).

With SAS/OR Constraint Programming (PROC OPTMODEL or PROC CLP), we are able to discover this perfect matching much earlier than the participants.

The formulation shown in the next section uses a set of binary decision variables called Assign[b,g], with the interpretation that Assign[b,g] = 1 if boy b is assigned to girl g in the matching. The first two sets of constraints enforce a one-to-one matching between boys and girls. The Ceremony_Matches constraint makes sure that each solution respects the matching ceremony results. The Truth_Booth constraint forces Assign[b,g] = 1 or 0 (depending on the truth booth outcome) for the couple (b,g) that entered the truth booth.

**The code**

Here is the SAS code I used to solve this problem. To run it for the next season, just copy all the code and update the "STEP 1" portion each week.

/***********************************************/ /******* STEP 1 - UPDATE YOUR INPUTS ***********/ /***********************************************/ /* Input number of weeks of data */ %let num_weeks = 5; /* Input weekly matches (from matching ceremony) up to current week */ /* For example, in Season 6, as of week 5, these were the couples in each ceremony */ data input_ceremony_pairs(keep=week boys_name girls_name); array girl_week{&num_weeks.} $; input boys_name $ girl_week{*}; do week = 1 to &num_weeks.; girls_name = girl_week[week]; output; end; datalines; Anthony Geles Diandra Jada Keyana Nicole Clinton Uche Uche Uche Uche Jada Dimitri Diandra Nicole Nurys Alexis Uche Ethan Jada Jada Alexis Nicole Geles Joe Zoe Audrey Zoe Zoe Zoe Kareem Alivia Alivia Alivia Diandra Alivia Keith Alexis Alexis Diandra Nurys Alexis Malcolm Nurys Nurys Geles Alivia Diandra Michael Keyana Keyana Audrey Geles Nurys Shad Audrey Geles Keyana Audrey Audrey Tyler Nicole Zoe Nicole Jada Keyana ; /* Input number of correct matches (from matching ceremony) up to current week */ /* For example, in Season 6, as of week 5, these were the correct guesses */ data input_ceremony_correct_matches; input week correct_guesses; datalines; 1 3 2 1 3 2 4 3 5 1 ; /* Input couples that went to truth booth and their outcome (1 if they are a match, 0 otherwise) up to current week */ /* For example, in Season 6, as of week 5, these were the truth booths */ data input_truth_booth; input week boys_name $ girls_name $ outcome; datalines; 1 Ethan Keyana 0 2 Anthony Geles 0 3 Malcolm Nurys 0 4 Dimitri Nicole 0 5 Clinton Uche 0 ; /***********************************************/ /****** STEP 2 - RUN WITHOUT MODIFYING CODE ****/ /***********************************************/ /* Constraint Programming Formulation */ proc optmodel; /* SETS */ set <num,str,str> CEREMONY_PAIRS; set BOYS = setof {<w,b,g> in CEREMONY_PAIRS} b; set GIRLS = setof {<w,b,g> in CEREMONY_PAIRS} g; set WEEKS = 1..&num_weeks.; set <num,str,str> TRUTH_BOOTH_PAIRS; set SOLS init 1.._NSOL_; num correctMatches{WEEKS}; num truthBoothOutcome{TRUTH_BOOTH_PAIRS}; /* READ DATA */ read data input_ceremony_pairs into CEREMONY_PAIRS=[week boys_name girls_name]; read data input_truth_booth into TRUTH_BOOTH_PAIRS=[week boys_name girls_name] truthBoothOutcome=outcome; read data input_ceremony_correct_matches into [week] correctMatches=correct_guesses; /* DECISION VAR */ /* Assign[b,g] = 1 if boy b is assigned to girl g in the matching; 0 otherwise */ var Assign{BOYS,GIRLS} BINARY; /* CONSTRAINTS */ con One_Girl_Per_Boy{b in BOYS}: sum{g in GIRLS} Assign[b,g] = 1; con One_Boy_Per_Girl{g in GIRLS}: sum{b in BOYS} Assign[b,g] = 1; /* WEEKLY CONSTRAINTS */ con Ceremony_Matches{w in WEEKS}: sum{<(w),b,g> in CEREMONY_PAIRS} Assign[b,g] = correctMatches[w]; con Truth_Booth{<w,b,g> in TRUTH_BOOTH_PAIRS}: Assign[b,g] = truthBoothOutcome[w,b,g]; /* SOLVE */ solve with clp / FINDALLSOLNS; /* CREATE OUTPUT */ num couplesCount{BOYS, GIRLS} init 0; for{s in SOLS} do; for{b in BOYS} do; for{g in GIRLS: Assign[b,g].sol[s] > 0.5} do; couplesCount[b,g] = couplesCount[b,g] + 1; leave; end; end; end; create data output_couples from [BOYS GIRLS] couplesCount; call symputx('Number_Solutions',_NSOL_); quit; |

**The solution**

To visualize the solution we can use the SAS SGPLOT procedure to create a heat map that illustrates the number of feasible solutions that contain a certain couple matched.

proc sort data=output_couples; by boys girls; run; proc sgplot data=output_couples noautolegend; title "Couples Occurrence Count in &Number_Solutions. Solutions"; heatmap y=boys x=girls / weight=couplesCount colormodel=(white pink red) outline x2axis; text y=Boys x=Girls text=couplesCount / textattrs=(size=10pt); xaxis display=none; x2axis display=(nolabel); yaxis display=(nolabel) reverse; run; |

For example, if we run the code above with the given data (Season 6, Week 5) we can see this diagram:

In this output we can see, for example, that Ethan and Geles are for sure not a couple (bummer) and that Tyler and Nicole seem to be the most promising couple (so far).

**Your turn**

Now use the following data (Season 6, Week 8) and my optimization and heat map code. Be ready for a surprise!

/***********************************************/ /******* STEP 1 - UPDATE YOUR INPUTS ***********/ /***********************************************/ /* Input number of weeks of data */ %let num_weeks = 8; /* Input weekly matches (from matching ceremony) up to current week */ /* For example, in Season 6, as of week 8, these were the couples in each ceremony */ data input_ceremony_pairs(keep=week boys_name girls_name); array girl_week{&num_weeks.} $; input boys_name $ girl_week{*}; do week = 1 to &num_weeks.; girls_name = girl_week[week]; output; end; datalines; Anthony Geles Diandra Jada Keyana Nicole Keyana Keyana Alivia Clinton Uche Uche Uche Uche Jada Geles Geles Geles Dimitri Diandra Nicole Nurys Alexis Uche Diandra Diandra Diandra Ethan Jada Jada Alexis Nicole Geles Jada Zoe Alexis Joe Zoe Audrey Zoe Zoe Zoe Alexis Uche Jada Kareem Alivia Alivia Alivia Diandra Alivia Nurys Nurys Nurys Keith Alexis Alexis Diandra Nurys Alexis Zoe Jada Audrey Malcolm Nurys Nurys Geles Alivia Diandra Alivia Alexis Uche Michael Keyana Keyana Audrey Geles Nurys Uche Audrey Keyana Shad Audrey Geles Keyana Audrey Audrey Audrey Alivia Zoe Tyler Nicole Zoe Nicole Jada Keyana Nicole Nicole Nicole ; /* Input number of correct matches (from matching ceremony) up to current week */ /* For example, in Season 6, as of week 8, these were the correct guesses */ data input_ceremony_correct_matches; input week correct_guesses; datalines; 1 3 2 1 3 2 4 3 5 1 6 4 7 5 8 3 ; /* Input couples that went to truth booth and their outcome (1 if they are a match, 0 otherwise) up to current week */ /* For example, in Season 6, as of week 8, these were the truth booths */ data input_truth_booth; input week boys_name $ girls_name $ outcome; datalines; 1 Ethan Keyana 0 2 Anthony Geles 0 3 Malcolm Nurys 0 4 Dimitri Nicole 0 5 Clinton Uche 0 6 Keith Alexis 0 7 Keith Alivia 0 8 Michael Audrey 0 ; |

FYI - The participants in Season 6 did not find the perfect matching till week 10. I bet they would have loved to have SAS Constraint Programming handy.

**Full season summary**

To understand better how the number of possible matches (feasible solutions) decreases with each additional data piece (constraints), you can see the following super cool animation (thanks, Rob Pratt!):

Notice that the truth booths in weeks 4 and 6 were wasted because the status of the selected couple was already able to be deduced, so the number of possible solutions did not change. In a later update, I'll show how to optimally select which couple should go to the truth booth.

**Going forward**

So, now that you know how to use SAS Constraint Programming, let's help these poor guys find their perfect matches in Season 7. Follow this blog and see how much faster than the contestants we'll figure out the matching!

**Season 7 Week 1 update**

And so it begins. After the first "truth booth" and "matching ceremony" (and lots of drama), here is the first heat map.

Teaser from Rob:

If the contestants have a choice, they should choose either Shamoy-Maria or Tomas-Morgan to go to the next truth booth, but NOT because those couples appear in the most remaining solutions.

**Season 7 Week 2 update**

Unfortunately the contestants did not follow Rob's suggestion. After the second truth booth and matching ceremony, we now have 287,580 solutions and actually Shamoy-Maria is now the most promising couple! Here is the heat map.

Update from Rob:

The fate button required the contestants to pair Andrew or Cam with Asia or Nutsa for the truth booth. Because the four pairs (Andrew-Asia, Andrew-Nutsa, Cam-Asia, Cam-Nutsa) all appeared in the same number of solutions (165,326) after week 1, these four choices were equally desirable to send to the truth booth, with respect to reducing the number of possible solutions. After week 2, Shamoy-Maria would be the best choice for the truth booth, but again NOT because they have the highest solution count (136,848). More details next week...

**Season 7 Week 3 update**

The third truth booth revealed that Shamoy and Maria are in fact a perfect match. After the third matching ceremony, there are 37,681 solutions.

Optimal truth booth recommendation from Rob:

Choosing either Cam-Kayla or Tevin-Kenya would yield the smallest number of resulting solutions in the worst case.

**Optimal truth booth strategy**

The "Couples Occurrence Count" table provides a way to determine which couple should go to the truth booth if you want to minimize the worst-case (maximum) resulting number of solutions. If couple (b,g) goes to the truth booth, there are two possibilities:

- If that couple is a perfect match, then the resulting number of solutions is couplesCount[b,g].
- If that couple is not a perfect match, then the resulting number of solutions is _NSOL_ - couplesCount[b,g].

So in the worst (worse?) case, the resulting number of solutions is max(couplesCount[b,g], _NSOL_ - couplesCount[b,g]), that is, the larger of these two counts. Because we want to reduce the number of solutions, the best strategy is to choose a couple that minimizes this quantity. Equivalently, we want to choose a couple that comes the closest to appearing in half the solutions. The following statements implement this idea:

/* find best pair for truth booth by minimizing the maximum number of resulting solutions */ num maxSolsTruth {b in BOYS, g in GIRLS} = max(couplesCount[b,g], _NSOL_ - couplesCount[b,g]); num min_maxSolsTruth init constant('BIG'); set <str,str> BEST_PAIR; for {b in BOYS, g in GIRLS} do; if min_maxSolsTruth > maxSolsTruth[b,g] then do; min_maxSolsTruth = maxSolsTruth[b,g]; BEST_PAIR = {<b,g>}; end; else if min_maxSolsTruth = maxSolsTruth[b,g] then do; BEST_PAIR = BEST_PAIR union {<b,g>}; end; end; put BEST_PAIR= min_maxSolsTruth; create data output_truth from [BOYS GIRLS] maxSolsTruth; |

After week 3, the PUT statement reports in the log:

BEST_PAIR={<'Cam','Kayla'>,<'Tevin','Kenya'>} 21889 |

The interpretation is that by choosing either of these two couples to go to the truth booth, the resulting number of solutions will be at most 21,889, and this number is best possible in the sense that choosing any other couple could yield a larger number of solutions.

As before, it is useful to display the results in a heat map:

proc sort data=output_truth; by boys girls; run; proc sgplot data=output_truth noautolegend; title "Maximum Number of Solutions if Couple goes to Truth Booth"; heatmap y=boys x=girls / weight=maxSolsTruth colormodel=(white pink red) outline x2axis; text y=Boys x=Girls text=maxSolsTruth / textattrs=(size=10pt); xaxis display=none; x2axis display=(nolabel); yaxis display=(nolabel) reverse; run; |

The lowest numbers appear in the lightest cells.

**Season 7 Week 4 update**

Here's the update after last night's episode. We are down to 12,860 solutions.

Using Rob's optimal strategy, the contestants should send Tevin and Kenya to the booth next episode such that in the worst-case scenario, the number of solutions will be down to 7,081.

**Avoiding a blackout**

If the matching ceremony yields no matches (a "blackout") beyond those confirmed by the truth booth, the prize pool gets cuts in half. So it would be good to figure out a way to avoid a blackout if possible. After the week 4 truth booth (before the matching ceremony), here was the heat map:

To avoid a blackout, you can solve an auxiliary optimization problem that maximizes the minimum number of matches. The formulation shown in the next code snippet uses a set of binary decision variables called IsCeremonyPair[b,g], with the interpretation that IsCeremonyPair[b,g] = 1 if boy b is paired with girl g in the matching ceremony. The first two sets of constraints enforce a one-to-one matching between boys and girls. The PerfectMatch constraint makes sure that any couple that is confirmed a "perfect match" by the truth booth is also paired together in the matching ceremony. The MaxMinCon constraint linearizes the maximin objective, as in the Fun with Flags post from July 2017. The following statements build and solve this auxiliary problem:

/* MATCHES_sol[s] = the set of pairs <b,g> for which Assign[b,g] = 1 in solution s */ set <str,str> MATCHES_sol {SOLS} init {}; for{s in SOLS} do; for{b in BOYS} do; for{g in GIRLS: Assign[b,g].sol[s] > 0.5} do; MATCHES_sol[s] = MATCHES_sol[s] union {<b,g>}; leave; end; end; end; /* find best ceremony pairs by maximizing the minimum number of matches (to avoid blackout) */ var IsCeremonyPair{b in BOYS, g in GIRLS} binary; con One_Girl_Per_Boy_Ceremony{b in BOYS}: sum{g in GIRLS} IsCeremonyPair[b,g] = 1; con One_Boy_Per_Girl_Ceremony{g in GIRLS}: sum{b in BOYS} IsCeremonyPair[b,g] = 1; con PerfectMatch{<w,b,g> in TRUTH_BOOTH_PAIRS: truthBoothOutcome[w,b,g] = 1}: IsCeremonyPair[b,g] = 1; var MaxMin >= 0 integer; max MinNumMatches = MaxMin; con MaxMinCon{s in SOLS}: MaxMin <= sum{<b,g> in MATCHES_sol[s]} IsCeremonyPair[b,g]; problem CeremonyProblem include IsCeremonyPair MaxMin MinNumMatches One_Girl_Per_Boy_Ceremony One_Boy_Per_Girl_Ceremony PerfectMatch MaxMinCon; use problem CeremonyProblem; solve; put (min{s in SOLS} sum{<b,g> in MATCHES_sol[s]} IsCeremonyPair[b,g])=; num couplesCountCeremony {b in BOYS, g in GIRLS} = (if IsCeremonyPair[b,g].sol > 0.5 then couplesCount[b,g] else .); create data output_couples from [BOYS GIRLS] couplesCount couplesCountCeremony; |

For week 4, the solver recommends an optimal matching ceremony that guarantees at least three matches and hence avoids a blackout. You can use the following PROC SGPLOT code to display the resulting solution:

proc sort data=output_couples; by boys girls; run; proc sgplot data=output_couples noautolegend; title "Couples Occurrence Count in &Number_Solutions. Solutions"; heatmapparm y=boys x=girls colorResponse=couplesCountCeremony / colormodel=(white pink red) outline x2axis; text y=Boys x=Girls text=couplesCount / textattrs=(size=10pt); xaxis display=none; x2axis display=(nolabel); yaxis display=(nolabel) reverse; run; |

Here is the resulting heat map, where the couples who are not in the matching ceremony are grayed out:

It turns out that the actual matching ceremony chosen by the contestants in week 4 could have yielded a blackout. That is, there was at least one remaining solution that contained no matches from the ceremony.

**Season 7 Week 5 update**

Now we're down to 1,696 solutions:

Optimal truth booth recommendation from Rob:

Cam-Kayla would yield at most \(\max(884, 1696-884) = 884\) solutions, and they are the best choice. Note that Tevin-Kenya appear in more solutions together but have a higher worst-case count of \(\max(1005, 1969-1005) = 1005\) solutions.

**Season 7 Week 6 update**

We're getting there: 574 possible solutions left.

Optimal truth booth recommendation from Rob:

Cam-Kayla would yield at most \(\max(285, 574-285) = 289\) solutions, and they are still the best choice. Also, we can now conclude that Brett-Kayla are not a match, even though they never went to the truth booth.

**Season 7 Week 7 update**

The contestants voted to send Zak and Nutsa to the truth booth, and they were not a match, so \(574-36=538\) possible solutions remain.

**Optimal matching ceremony strategy**

We already saw one way to avoid a blackout by solving an auxiliary optimization problem to maximize the minimum number of matches. But there might be many such possible matching ceremonies that yield the same number of matches, and (as with the truth booth strategy) we would like to minimize the number of resulting solutions in the worst case. We can solve a different auxiliary problem to both avoid a blackout and minimize the number of solutions. This problem involves the IsCeremonyPair[b,g] variables and related constraints from before, as well as additional binary variables IsBeamCount[s,c] with the interpretation that IsBeamCount[s,c] = 1 if and only if the beam count for solution s is c. Because Shamoy and Maria are the only perfect match so far, we need at least two beams to avoid a blackout. The following statements build and solve this auxiliary problem:

/* find best ceremony pairs by minimizing the maximum number of resulting solutions */ /* minBeamCount is minimum number of beams to avoid blackout */ num minBeamCount = 1 + sum{<w,b,g> in TRUTH_BOOTH_PAIRS} truthBoothOutcome[w,b,g]; set BEAM_COUNTS = minBeamCount..card(BOYS) diff {card(BOYS) - 1}; /* IsBeamCount[s,c] = 1 iff sum{<b,g> in MATCHES_sol[s]} IsCeremonyPair[b,g] = c */ var IsBeamCount{SOLS, BEAM_COUNTS} binary; impvar NumSolsPerBeamCount{c in BEAM_COUNTS} = sum{s in SOLS} IsBeamCount[s,c]; var MinMax >= 0 integer; min MaxNumSolutions = MinMax; con MinMaxCon{c in BEAM_COUNTS}: MinMax >= NumSolsPerBeamCount[c]; con OneBeamCount{s in SOLS}: sum{c in BEAM_COUNTS} IsBeamCount[s,c] = 1; con Link{s in SOLS}: sum{<b,g> in MATCHES_sol[s]} IsCeremonyPair[b,g] = sum{c in BEAM_COUNTS} c * IsBeamCount[s,c]; problem CeremonyProblem2 include IsCeremonyPair IsBeamCount MinMax MaxNumSolutions One_Girl_Per_Boy_Ceremony One_Boy_Per_Girl_Ceremony PerfectMatch MinMaxCon OneBeamCount Link; use problem CeremonyProblem2; solve; print NumSolsPerBeamCount; create data output_couples from [BOYS GIRLS] couplesCount couplesCountCeremony; |

For week 7, the solver recommends an optimal matching ceremony that guarantees at least two matches (and hence avoids a blackout) and yields at most 142 solutions in the worst case (three beams):

Here is the resulting heat map, where the couples who are not in the matching ceremony are grayed out:

It turns out that the actual matching ceremony chosen by the contestants in week 7 (the results of which were left as a cliffhanger to be revealed in next week's episode) could yield up to 296 solutions, so the matching ceremony proposed here is better in the sense that it guarantees a much smaller worst-case number of solutions.

Update from Rob: The matching ceremony yielded four beams, and this implies several no-matches, four of which the contestants realized, and an inferred match (Tevin-Kenya), which the contestants did not realize and instead sent them to the truth booth. Although the truth booth result was treated as a cliffhanger to be revealed in the next episode, we already know the result. (In fairness to the contestants, there does not seem to be a simple explanation that Tevin and Kenya are a perfect match, without enumeration. For example, if you fix Assign['Tevin','Kenya'] = 0, the resulting problem is MILP infeasible but LP feasible.) There are now 128 remaining solutions, and that number will not change when the truth booth confirms the Tevin-Kenya match.

For next week, the solver recommends an optimal matching ceremony that guarantees at least three matches (and hence avoids a blackout) and yields at most 35 solutions in the worst case (five beams):

Here is the resulting heat map, where the couples who are not in the matching ceremony are grayed out:

**Season 7 Week 8 update**

As we already knew would happen, the truth booth confirmed that Tevin and Kenya are a perfect match. The matching ceremony, which could have yielded a blackout, leaves 34 solutions possible:

**Season 7 Week 9 update**

The contestants sent Cam and Samantha to the truth booth, but the results above already showed they were not a match, so that is two wasted truth booths in a row. The solver recommends an optimal matching ceremony that guarantees at least three matches (and hence avoids a blackout) and yields at most 8 solutions in the worst case (four or five beams):

Here is the resulting heat map, where the couples who are not in the matching ceremony are grayed out:

The contestants chose a different matching ceremony, which could have yielded a blackout. They got four beams, and now only five solutions remain:

By adding a PUT statement, you can write these solutions to the log:

for {s in SOLS} put s= MATCHES_SOL[s]; |

Here they are:

s=1 {<'Andrew','Cali'>,<'Brett','Nutsa'>,<'Cam','Bria'>,<'Daniel','Jasmine'>,<'Kwasi','Lauren'>,<'Lewis','Samantha'>,<'Moe','Kayla'>,<'Shamoy','Maria'>,<'Tevin','Kenya'>,<'Tomas','Asia'>,<'Zak','Morgan'>} s=2 {<'Andrew','Cali'>,<'Brett','Samantha'>,<'Cam','Lauren'>,<'Daniel','Bria'>,<'Kwasi','Asia'>,<'Lewis','Jasmine'>,<'Moe','Kayla'>,<'Shamoy','Maria'>,<'Tevin','Kenya'>,<'Tomas','Nutsa'>,<'Zak','Morgan'>} s=3 {<'Andrew','Cali'>,<'Brett','Samantha'>,<'Cam','Lauren'>,<'Daniel','Nutsa'>,<'Kwasi','Kayla'>,<'Lewis','Bria'>,<'Moe','Asia'>,<'Shamoy','Maria'>,<'Tevin','Kenya'>,<'Tomas','Jasmine'>,<'Zak','Morgan'>} s=4 {<'Andrew','Samantha'>,<'Brett','Bria'>,<'Cam','Nutsa'>,<'Daniel','Cali'>,<'Kwasi','Asia'>,<'Lewis','Jasmine'>,<'Moe','Kayla'>,<'Shamoy','Maria'>,<'Tevin','Kenya'>,<'Tomas','Lauren'>,<'Zak','Morgan'>} s=5 {<'Andrew','Samantha'>,<'Brett','Nutsa'>,<'Cam','Morgan'>,<'Daniel','Lauren'>,<'Kwasi','Asia'>,<'Lewis','Jasmine'>,<'Moe','Cali'>,<'Shamoy','Maria'>,<'Tevin','Kenya'>,<'Tomas','Bria'>,<'Zak','Kayla'>}

**Season 7 Week 10 update**

Brett and Nutsa are headed to the final truth booth. Out of the four choices allowed by the fate button, they are the only couple whose status is unknown, so that was a good decision. From the latest heat map, we can see that there will be either two solutions (if Brett-Nutsa is a match) or three solutions (if not) left after the truth booth results. So it is not possible for the contestants to have logically deduced the correct matching in time for the final ceremony. It will take some guesswork for them to win the $1 million prize.

The final truth booth revealed that Brett-Nutsa is a perfect match, so we are down to two solutions (s=1 and s=5 above):

The contestants used solution s=1 for the final matching ceremony, and...

...they won the $1 million! Thanks for following along with us this season.

**Season 7 data**

You can reproduce these results by using the following data.

/* Input number of weeks of data */ %let num_weeks = 10; /* Input weekly matches (from matching ceremony) up to current week */ data input_ceremony_pairs(keep=week boys_name girls_name); array girl_week{&num_weeks.} $; input boys_name $ girl_week{*}; do week = 1 to &num_weeks.; girls_name = girl_week[week]; output; end; datalines; Andrew Lauren Morgan Lauren Nutsa Samantha Lauren Lauren Samantha Cali Cali Brett Cali Asia Cali Kayla Nutsa Nutsa Nutsa Nutsa Bria Nutsa Cam Kayla Kayla Kayla Asia Kayla Kayla Cali Lauren Morgan Bria Daniel Nutsa Nutsa Samantha Lauren Bria Samantha Samantha Asia Lauren Jasmine Kwasi Asia Lauren Jasmine Bria Jasmine Asia Asia Jasmine Nutsa Lauren Lewis Samantha Jasmine Asia Kenya Lauren Bria Bria Bria Asia Samantha Moe Jasmine Bria Nutsa Samantha Asia Jasmine Jasmine Kayla Kayla Kayla Shamoy Maria Maria Maria Maria Maria Maria Maria Maria Maria Maria Tevin Kenya Kenya Kenya Jasmine Kenya Kenya Kenya Kenya Kenya Kenya Tomas Morgan Cali Bria Cali Cali Cali Kayla Morgan Jasmine Asia Zak Bria Samantha Morgan Morgan Morgan Morgan Morgan Cali Samantha Morgan ; /* Input number of correct matches (from matching ceremony) up to current week */ data input_ceremony_correct_matches; input week correct_guesses; datalines; 1 3 2 3 3 3 4 2 5 4 6 4 7 4 8 4 9 4 10 11 ; /* Input couples that went to truth booth and their outcome (1 if they are a match, 0 otherwise) up to current week */ data input_truth_booth; input week boys_name $ girls_name $ outcome; datalines; 1 Tomas Maria 0 2 Andrew Asia 0 3 Shamoy Maria 1 4 Brett Kenya 0 5 Zak Bria 0 6 Brett Cali 0 7 Zak Nutsa 0 8 Tevin Kenya 1 9 Cam Samantha 0 10 Brett Nutsa 1 ; |

## 8 Comments

Nifty application of constraint programming! Great job Natalia and Rob!

Thanks Lindsey - couldn't have done it without your CLP!

This seems like a variant of the MasterMind game. For that game, there is an optimal strategy that enables you to guess the solution by using a technique similar to the "matching ceremony." Of course, the "truth booth" is a nice variant, and can be awesome if you get it right!

Hi Rick - yes! The "truth booth" definitely adds an interesting layer. Rob will be posting a follow-up soon where he optimizes the strategy to select which couple should be sent to the "truth booth" - stay tuned!

Excellent bit of programming. We found this show for the first time recently and are more into the logic and probabilities than the drama. I thought I was going overboard by creating a spreadsheet, assuming certain matches in the final 3 spotlights, and working back to eliminate the NO's.

Brett-Nutsa, Shamoy-Maria, Tevin-Kenya and Zak-Morgan pretty much have to be matches.

If any of the other couple combinations happen to garner 4 lights for 3 straight weeks, it results in matches > lights in prior weeks.

Lewis-Samantha works for week 1

Moe-Bria or Kwasi Lauren for week 2. (I'm leaning towards Moe-Bria)

after that you have

cam-jasmine

tomas-lauren

kwasi is cali or kayla (assuming lauren is NOT a kwasi match)

andrew is asia or cali or kayla

daniel is asia or cali or kayla

Not much was accomplished with their terrible plan. Doesn't anyone sit down in that house and say: we had 4 lights for 3 weeks, and 4 of the same couples for 3 weeks... so we have 4 matches.

Oh and by the way, we can look back at weeks with 2 or 3 lights, know who the matches were, and figure out pretty easily the couples that were -wrong-. Unless MTV is editing out actual 'game talk' in figuring things out, I doubt they get it right.

Brett-nutsa/zak-morgan/shamoy-maria/tevin-kenya

lewis samantha (week 1)

moe bria (week 2)

daniel-asia(mysterious 4th match this week)

tomas-lauren

cam-jasmine

andrew (cali or kayla)

kwasi(cali or kayla)

possibility of kwasi-lauren week 2, which would mean moe-cali, andrew-kayla

*shrug*

Seeing Andrew and Cali getting together at the start of the episode has sorted some things out...

Andrew Cali

Brett Nutsa

Cam Jasmine

Daniel Asia

Kwasi Kayla

Lewis Samantha

Moe Bria

Shamoy Maria

Tevin Kenya

Tomas Lauren

Zak Morgan

Leaked by kwasi..lauren is his match