"Are You The One?" Finding the matching through SAS Constraint Programming

8

Are You The One? Season 7 CR: Brian Bielmann/MTV

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:

  1. They get to choose one couple to go to the "truth booth" and ask if that couple is a perfect match or not.
  2. 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:

  1. If that couple is a perfect match, then the resulting number of solutions is couplesCount[b,g].
  2. 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
;
Share

About Author

Natalia Summerville

Natalia Summerville is Principal Operations Research Specialist at SAS Institute where she leads design, development and implementation of optimization applications for a variety of industries. Natalia is also Adjunct Professor at the Institute of Advanced Analytics as well as the Department of Industrial Engineering, both at North Carolina State University (NCSU). She holds a PhD in Operations Research from NCSU and a PhD in Industrial Engineering from Tecnologico de Monterrey, Mexico.

8 Comments

  1. 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!

    • Natalia Summerville
      Natalia Summerville on

      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!

  2. 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

  3. 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*

  4. 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

Leave A Reply

Back to Top