### Marriage Problems in Math

March 4, 2011 There's a cute teen/tween television series on Nickelodeon called iCarly. Surprisingly, no vampires are involved. I mentioned iCarly in a previous article about base-11 numbers (The Number Dirf, November 23, 2010). In one episode of the show, "iDream of Dance,"[1] the three tween protagonists announced a video contest on their web site and got a huge response. As a result, they needed to screen three thousand video clips, a task they decided to do as six nights of five hundred videos a night. A little mathematical magic, as I'll reveal below, shows that they might have reduced their workload by a significant percentage. There are at least two math problems known as "marriage" problems. One is called the "stable marriage problem," which I'll review later. The other is simply "the marriage problem," although it's known by other names, such as the "fussy suitor problem" and the "secretary problem." The problem is an optimal stopping problem, sort of like a law of diminishing returns when selecting from a group. The goal is a process that will likely result in your choosing the best candidate without interviewing everyone. The problem is simply stated.[2]• There is a single position to fill. You're looking for either a secretary to hire, or a wife.The solution to this problem is often called the 37% rule because the optimum strategy is to decide that you have enough information to make a wise choice after interviewing

• There's a known number of applicants for the position.

• It's possible to rank the applicants from best to worst, with no ties.

• You interview the applicants sequentially in a random order.

• After each interview, you can accept or reject the candidate.

• Your decision can be based only on the relative ranks of the applicants that you've interviewed to that point.

• When you reject an applicant, that applicant can't be recalled.

• When you accept an applicant, the remaining interviews are canceled.

• You want to select the best applicant.

**1/e**people, where

**e**is the base of natural logarithms. Since

**e**= 2.71828..., then

**1/e**is 0.367879..., and we get about 37%. If we interview 37% of the candidates, and then choose the next candidate better than any one of these, we have a good chance of having made the best choice. Even if we somehow don't get the very best, we're not that far wrong. One caveat, however, is that we're sometimes forced to choose the last person on the interview list, no matter what her qualifications. It's very easy to write a program to analyze this problem, so I did. You can view the C source code, here.

*The probability of selection as a function of candidate suitability for the marriage problem using the 1/e cutoff rule. Graphics via Gnumeric.*

So, how good is our choice when we decide to use the

**1/e**rule? The graph above, which uses data from my analysis program, tells the story. The program did ten thousand trials of interviews of a hundred candidates for various cutoffs, including

**1/e**. If we use the

**1/e**cutoff, then we're about 37% likely to find the best candidate. Even if we don't find the very best, our odds of finding a very good candidate are quite high, as the following table shows. There's about a 63% chance that you'll get someone in the top 5%.

Rank | Likelihood (%) |

1 | 37.10 |

2 | 13.63 |

4 | 6.46 |

4 | 3.38 |

5 | 1.96 |

6 | 1.17 |

7 | 0.85 |

8 | 0.55 |

9 | 0.43 |

**1/e**rule, for which the probability of selecting the best candidate stays about the same.

*The probability of selecting the best candidate as a function of cutoff for the marriage problem. There a wide range around the 1/e cutoff where the probability is essentially the same. Graphics via Gnumeric.*

The other mathematical marriage problem is the stable marriage problem. This problem is more complicated than the marriage problem analyzed above. Essentially, you have a group of men and a group of women of equal number, and the individuals of each group rank the suitability of all individuals of the other group (Sorry, no "civil unions" are considered here). The optimization problem in this case is to match men and women such that there's no man and woman who would rather have each other than their current partner. It might be worthwhile to reread that last sentence. It doesn't mean that every man gets the woman of his dreams, and vice-versa. It just means that any lusting is unrequited. It's been proven that such a matching is always possible, and there's a simple algorithm to do the matching. I didn't write a C implementation; but, as the textbook authors say, "The exercise is left to the reader." It's not surprising that there's a related problem, the "stable roommates problem," that's more useful. In this case, all participants are in the same pool. Unfortunately, the stable roommates problem may not always have a solution, so it's probably still better to marry than to just live together.

### References:

- iCarly Television Series, Season 1, Show 3, "iDream of Dance," Adam Weissman, Director, Dan Schneider, Writer, September 16, 2007.
- Tom Ferguson, "Who Solved the Secretary Problem?" Statistical Science, vol. 4, no. 3, pp. 282-296.

*Permanent Link to this article*

Linked Keywords: Teen; tween; Nickelodeon; iCarly; vampires; dirf; base-11 numbers; stable marriage problem; the marriage problem; optimal stopping problem; diminishing returns; strategy; the base of natural logarithms; Gnumeric; stable marriage problem; civil union; optimization; unrequited love; algorithm; stable roommates problem; iDream of Dance.

### Google Search

Latest Books by Dev Gualtieri

Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!

Other Books

- Magnetocapacitive Tunnel Junctions - August 21, 2017

- Tardigrades - August 14, 2017

- Roman Concrete - August 7, 2017

- Solar Spicules - July 31, 2017

- Schroeder Diffuser - July 24, 2017

- Rough Microparticles - July 17, 2017

- Robot Musicians - July 10, 2017

- Walter Noll (1925-2017) - July 6, 2017

- cosmogony - July 3, 2017

- Crystal Prototypes - June 29, 2017

- Voice Synthesis - June 26, 2017

- Refining Germanium - June 22, 2017

- Granular Capillarity - June 19, 2017

- Kirchhoff–Plateau Problem - June 15, 2017

- Self-Assembly - June 12, 2017

- Physics, Math, and Sociology - June 8, 2017

- Graphene from Ethylene - June 5, 2017

- Crystal Alignment Forces - June 1, 2017

- Martian Brickwork - May 29, 2017

- Carbon Nanotube Textile - May 25, 2017

- The Scent of Books - May 22, 2017

- Patterns from Randomness - May 18, 2017

- Terpene - May 15, 2017

- The Physics of Inequality - May 11, 2017

- Asteroid 2015 BZ509 - May 8, 2017

- Fuzzy Fibers - May 4, 2017

- The Sofa Problem - May 1, 2017

- The Wisdom of Composite Crowds - April 27, 2017

- J. Robert Oppenheimer and Black Holes - April 24, 2017

- Modeling Leaf Mass - April 20, 2017

- Easter, Chicks and Eggs - April 13, 2017

- You, Robot - April 10, 2017

- Collisions - April 6, 2017

- Eugene Garfield (1925-2017) - April 3, 2017

- Old Fossils - March 30, 2017

- Levitation - March 27, 2017

- Soybean Graphene - March 23, 2017

- Income Inequality and Geometrical Frustration - March 20, 2017

- Wireless Power - March 16, 2017

- Trilobite Sex - March 13, 2017

- Freezing, Outside-In - March 9, 2017

- Ammonia Synthesis - March 6, 2017

- High Altitude Radiation - March 2, 2017

- C.N. Yang - February 27, 2017

- VOC Detection with Nanocrystals - February 23, 2017

- Molecular Fountains - February 20, 2017

- Jet Lag - February 16, 2017

- Highly Flexible Conductors - February 13, 2017

- Graphene Friction - February 9, 2017

- Dynamic Range - February 6, 2017

- Robert Boyle's To-Do List for Science - February 2, 2017

- Nanowire Ink - January 30, 2017

- Random Triangles - January 26, 2017

- Torricelli's law - January 23, 2017

- Magnetic Memory - January 19, 2017

- Graphene Putty - January 16, 2017

- Seahorse Genome - January 12, 2017

- Infinite c - January 9, 2017

- 150 Years of Transatlantic Telegraphy - January 5, 2017

- Cold Work on the Nanoscale - January 2, 2017

### Deep Archive

Deep Archive 2006-2008

**Blog Article Directory on a Single Page**