Simplex Algorithm and How Dating Web Sites Match Singles


Mathematical Background:

The simplex method was created by George Dantzig (1914-2005)  who was Professor Emeritus of Transportation Sciences and Professor of Operations Research and Computer Science at Stanford University.  George Dantzig created the simplex method as an algorithm for solving a system of linear equations.  The algorithm is used in linear programming to find optimum solutions to these equations.  The equations typically consist of one objective function which you are trying to minimize (i.e. cost) or the dual problem which would consist of an equation your are trying to maximize(i.e. profit). In addititon to the objective function you will have some sort of constraints which will limit your optimum solution.  These constraints could be in the form of storage capacity, capital budgets, time constraints, labor expenses, substitutability of inputs and a host of other factors can play a part in defining the set of constraints.

The original applications to the simplex method were to linear programming.  Linear programming was used during WWII was as a way of minimizing cost to the army and increase losses to the enemy through superior planning and utilization of resources. Examples of the uses of the simplex method and linear programming include the transportation problem where the algorithm minimizes the cost of shipping between n number of warehouses and m number of destinations.  The diet problem is another application where the nutritional needs of an army are taken into account as we try and minimize the combination of foods that will yield the minimal nutritional value with the lowest cost.

Finally, one of the most interesting and recent applicatons of the simplex algorithm has been to the assingment problem in on-line dating services.  The objective of the simplex method in an on-line dating site would be to maximize the matchings of male and females based on the numerical value of potential matches.  In turns out that in this case it is as much an art as it is a science since the value of a match must be determined based on characteristics of the individuals, then and only then can the simplex method be used to maximize the matches.

Example: (Adapted from Dr. Reese, Pepperdine University Graziano Graduate School of Business and Economics 146 at UCLA 2009)

There are 4 single females interested in dating 4 single males. Female i has a value of   ScreenHunter_01 Aug. 14 21.28 for a date with male j.  We make the assumption that the value of the date has a lower bound of zero. An optimal dating equilibrium consist of a pairing of couples such that there is no other allocation of females to males that are feasible.  In other words the best allocation is one where people get the best partner they can and are able to get.

Here is the matrix which represents the value derived from matching a female with a male.   Note:  These values are subjective and they are calculated using compatability questionaires and are in no way meant to be objective.

ScreenHunter_13 Aug. 14 23.44

The matrix represents the value of of the match which can be represented by the difference between the score of a female and the score of a male; based on attractiveness, personality, sense of humor etc. The numbers in the matrix can be represented by the following formula

ScreenHunter_05 Aug. 14 22.10. Females are trying to maximize this formula because it means that they were matched up with a male whose score is relatively large in comparison to their own scores, which means they got a good “catch” .  Males are trying to minimize this formula because that means that they are matched with a person whose relative attractiveness far exceeds their own based on some agreed upon criteria. This is very much like a supply and demand model but with discrete instead of continuous variables and where the “suppliers” are the females and the “consumers” are the males.  In essence what females are trying to do is maximize this formula:

ScreenHunter_07 Aug. 14 22.49


This kind of optimization problem can be solved by using the Excel solver in the following steps:

1)  The Excel formlas that correspond to the constraints are given by the following matrix

ScreenHunter_09 Aug. 14 23.00

Assuming that your value matrix started was at   B4:E7  and that your objective matrix was at B10: E13

2) Use the solver with the following settings to get the matches:

ScreenHunter_10 Aug. 14 23.07

ScreenHunter_11 Aug. 14 23.08

The matches should be (Female 1, Male 1), (Female 2, Male 2), (Female 3, Male 4), and (Female 4, Male3)

ScreenHunter_12 Aug. 14 23.09