Algorithms are behind everything we do - it is just that sometimes we don't notice or don't want to notice.We have lots of different algorithms for finding a date, but what about deciding if this is the one for you?

The problem of deciding who to marry or settle down is not usually thought of as one to solve algorithmically. The prospect of a life long commitment is something that most people don't like to think of as a cold and hard trade off between what you have and what you could have. But in algorithmic terms this is just a decision process and one that has been studied before - it is called the Secretary Problem. 

This was first brought to a wider audience by Martin Gardiner in his Scientific American column. The problem is that you are given a list of n potential candidates for the position of your secretary (or other close helper). You are allowed to interview them, in a random order, and you have to either accept or reject each candidate before moving on to the next one. And you can't change your mind later.

The problem is essentially that of finding a statistical stopping rule. You need to work out how good a candidate has to be to make it a good bet that you won't see a better one in the remainder of the list.

The standard solution to the problem is to reject n/e and then accepting the first applicant that is better than the best interviewed so far. If there isn't one you accept the last applicant. If you follow this rule you will reject the best candidate about 37% of the time. 

Now you might notice that this problem is very similar to the marry or dump problem posed at the start. You sequentially meet potential partners and at each stage you either reject and move on or attempt to hang on to what you have. It is the secretary problem but with the twist that the evaluation of the candidate is a bit different.

A recent paper titled “Should I break up with my girlfriend? Will I find another?” Or: An Algorithm for the Forecasting of Romantic Options by Rashied B. Amini describes some of the ideas behind a service he has constructed called Nanaya. 

This takes the analysis of the secretary problem a stage further by taking information about you, your significant other, you life status and groups of people you interact with. The idea is that it attempts to work out a probability that you will meet someone "better" than your current attachment. 

Oddly for an academic paper, it doesn't detail the exact methods used by Nanaya because the author wants to keep the methods to himself. However, the program does output some standard information on the opportunities to find a match, but most importantly it outputs:

Whether remaining in a relationship or returning to being single will probably provide maximum utility.

Of course, there is one factor that Nanaya doesn't seem to take into account. You may maximize your utility function but your prospective partner is also maximizing theirs. You might ask for a permanent relationship but you might be rejected because they perceive that they can easily do better. 

At this point the whole situation changes from a simple statistical stopping rule into a large chunk of game theory where the best you can hope for is a Nash equilibrium. 

Romance is not so easy.

It makes NP hard look simple. 

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info