Finding Stable Matches: The Mathematics of Computer Dating

17 FEBRUARY 2014

  FINDING STABLE MATCHES:  THE MATHEMATICS OF COMPUTER DATING   PROFESSOR TONY MANN     Good evening.    In my lectures tonight and next week I will be exploring mathematics used in computer algorithms. In this talk I shall be introducing some fascinating mathematics, which has valuable applications in, for example, allowing us to pair off people for dating purposes, or to assign workers to employment vacancies.   Naturally, mathematics is enormously helpful in matters of love. Here, for example, is a beautiful equation which describes a heart: (x2 + y2 – 1)3 – x2y3 = 0   So you cannot have love without mathematics!   However, given the popular image of mathematicians, you might question whether we are the right people to talk about dating. A common public perception of mathematicians is reflected in an interview some years ago in which the actress Molly Ringwald said, “My love life is not really going anywhere these days. Of course you will not find me dating any mathematicians… “ And apparently (although the book is not in my own library) Graham Masterson’s How to drive your man wild in bed gives guidance on how to choose a lover, listing professions to avoid: “mathematician” is top of this list. But if you think mathematicians are incapable of romance, I invite you to think again. You are probably familiar with the Möbius strip – a band with a twist in it, like the wristband I am wearing if I remembered to put it on this morning. The Möbius strip has only one side and only one edge. You can make one by cutting a strip of paper, giving it a twist and taping the ends together. It has interesting properties – try cutting it in half lengthwise and see what you get, or cutting similarly at a third of the width of the strip.   For this exercise I have made two Möbius strips, with the twists in the opposite directions (that is important). I join them together at right angles, with a generous amount of tape. I now cut each strip in half. What do I get? The result is two linked hearts! What could be more romantic than that?   So, having dispelled the myth that mathematics and romance do not go together, let us move on to the mathematics of Internet dating. This is big business. The first thing we can learn from mathematics is that Internet dating offers the potential to enhance considerably our chances of finding a suitable mate. Most of us do not meet many people outside our limited social circles and so expanding our pool of potential partners via the internet means that there is much more likelihood that there is someone compatible (if we can find them). This does work – my boss met his wife in this way! But for this to work dating agencies need to be able to match people who are compatible. This is a problem that requires both mathematical methods and psychological insights (and Professor Glenn Wilson, whose lectures at Gresham College many of you will be familiar with, has written about this topic). You do not have to take my word for it that mathematics is involved: the fictional Professor Tony, hero of Charlotte Cory’s radio drama series findtheperfectpartner4u.com last year, gave a paper at a conference on “New directions in applied mathematical modelling”: his presentation was on “The Mathematics of Internet Dating”. Just how complex the problem is can be seen from a case history, which attracted some publicity last month. Chris McKinlay is a mathematician who was hoping to find love through an online dating site. Members answered about 350 questions from a bank of several  thousand and the site’s algorithm used these answers to generate promising matches. But McKinlay was not having any success, so, being a mathematician, he worked out what was going wrong.   He concluded that the questions which he had chosen to answer were not those that were being answered by the women he wanted to meet. It was not enough to provide the right answers to the questions, but he had to choose which questions were most likely to match those chosen by his most compatible prospective partners. Fortunately, his mathematical training and computing skills enabled him to undertake a comprehensive data mining exercise. He divided the profiles of 20,000 women into seven clusters, worked out which clusters were most likely to contain women of interest to him, and performed an optimisation exercise to choose which questions to answer in order to attract women in his preferred clusters. He was successful, and one of the women he met through this strategy is now his fiancée.   How else can mathematics help suitors? One useful piece of mathematical guidance comes from what was once called “The Marriage Problem” but is today more often referred to as “the Secretary Problem”. Suppose during the course of my life I expect to meet a succession of n potential wives. As soon as I choose one, I am out of the market. Each one must be accepted or rejected before I meet the next, and I cannot go back to someone I have previously rejected. My only basis for choice is comparison with previous candidates - I have no absolute numerical scale on which I rate partners, but I can say whether the current candidate is better or worse than previous ones. How do I give myself the best possible chance of finding the best partner?   There is a mathematical answer to this: I reject the first n/e possibles (where e is Euler’s number, 2.71828…, the base of the natural logarithms), and then I accept the next woman I meet who is better than all those I have already rejected. My probability that I will be matched with the best potential partner is 1/e – about 0.368, or just over 1 in 3.   This suggests that if I expect to meet about eleven potential partners, I should reject the first four and then accept the next one who is better than any of these four. If I expect to have 100 to choose from then I will reject the first 37.   This is an impressive piece of mathematics, and it gives a surprisingly high probability of finding the best partner. But how useful is it in practice? The assumption is that the selection of a partner is a one-person decision: I choose my preferred partner, but I do not consider the possibility that she might reject me! So the conditions necessary for the mathematics to work may not apply in a real-life situation.   There is another question that comes to mind. Do I want to maximise my chance of finding the best-possible partner (which is still less than 37%), or would it be more pragmatic to aim for a higher probability of finding a pretty good partner? Perhaps I would prefer a 90% chance of an acceptable partner to a 37% chance of the best. Now, in fact maths can help me with that, but the point I want to make is that any applied mathematics rests on assumptions. The assumptions behind some of the most interesting maths that appears to apply to our romantic relationships may not be entirely realistic, but these scenarios still help us understand some very useful mathematics. So applying the Secretary Problem to the selection of a spouse may be slightly artificial, but what mathematics do dating agencies use? They are generally trying to generate a reasonable number of possible matches for their clients. I want to step back a bit from that problem, and look at more basic mathematics. I am going to start with some work by the British mathematician Philip Hall, one of the great algebraists of the last century.   Most of Hall’s most famous work was in the subject of group theory, an increasingly important branch of pure mathematics. But he also gave his name to Hall’s Marriage Theorem. Here is one formulation:   Let E be a non-empty finite set and let F = {S1, S2, …, Sm} be a family of non-empty subsets of E. Then we can find a set of m elements of E, one chosen from each Si, if and only if the union of any k of the subsets Si contains at least k elements, for 1 ≤ k ≤ m.   That may not be entirely clear, and even when one has worked out what it means, its relevance to marriage may be obscure. But we can rewrite it in more direct language. Here is the traditional formulation. Suppose we have a set of m women and a set of men, some of whom are known to some of the women.  Then we can marry each woman to a man that she knows, if and only if every set of k women collectively know at least k men, for every k with 1 ≤ k ≤ m.   What is this saying?   Suppose woman W1 knows men M1 and M2; woman W2 knows men M1 and M3; woman W3 knows men M3 and M4; and woman W4 knows men M2 and M4. Then each woman knows at least one man; every pair of women know at least two men between them; any three women know at least three men; and the set of all four women between them know all four men. This, the theorem tells us, proves that we can pair them off, and indeed we can: for example matching W1 with M1, W2 with M3, W4 with M2, and W3 with M4, (There are other equally valid pairings).   But now suppose the connections are slightly different. Suppose woman W1 knows men M1 and M2; woman W2 knows men M1 and M2; woman W3 knows men M1 and M2; and woman W4 knows all four men M1, M2, M3 and M4. Now we have more connections between the men and the women, so you might think it would be easier to find a matching. But consider the three women W1, W2, and W3.  Between them they know only the two men M1 and M2. There is no way we can find three husbands from these two men. So in this case a matching is not possible, and this is because the Hall condition is not satisfied. We have three women who know only two men between them, and this makes it impossible for us to marry them all off.   In fact, it is clear that if Hall’s condition is not satisfied, then we cannot pair off our women and men so that each marries someone they know. What Hall proved is that the converse is also true: that is, if the condition is satisfied, then we can find a pairing. That is a very nice, possibly surprising, result.   At this point, from the point of view of a mathematician, the marriage problem is solved. We have a necessary and sufficient condition to tell us whether or not a solution is possible. There is no further interest in the marriage problem for a pure mathematician: tedious details like how to find a suitable pairing can be left to others.   But for those like computer scientists, who are not satisfied to be told that a solution exists but who want to know how actually to find that solution, there is still work to be done. And there are also human issues. The formulation of this problem uses only one criterion – a woman can marry a man so long as she knows that man. That is actually a rather weak criterion for marrying someone. There are people I know who I would not want to marry, but the theorem does not allow for that. Neither does it allow for preferences: I might be prepared to marry A, B or C but I probably have preferences between them.   So we are now going to explore algorithms, which match people, taking into account their preferences between potential partners. For this discussion I shall assume that we have m women and m men, and that each man has ranked the women in the order of his preference, while each woman has similarly ranked the men (and there are no ties in the ranking: for any two potential partners, you have a preference for one over the other, and this is consistent, so that if you prefer A to B and B to C, then you prefer A to C).   (As an aside, it is this consistency of preferences that makes possible old jokes like “Which is better, eternal happiness or a ham sandwich?” The answer is the ham sandwich, because nothing is better than eternal happiness, and a ham sandwich is better than nothing).   Suppose we have four pairs with the preferences as follows:     Woman  A prefers man X to Y to Z to W. Woman  B prefers man Y to Z to W to X. Woman C prefers man Z to W to X to Y. Woman D prefers man W to X to Y to Z. Man W prefers woman D to C to B to A. Man X prefers woman A to D to C to B. Man Y prefers woman B to A to D to C. Man Z prefers woman C to B to A to D.   There are many ways we can pair people off. We could simply match A with W, B with X, C with Y, and D with Z. In this case that means that everyone is matched with the person who is their least-desired partner, so this is not a very good matching. If we are simply pairing people off for some not very important reason – tennis partners for an afternoon, perhaps, or passengers to drivers for the trip between a wedding and the reception – this may not matter too much, but if we are marrying people off, this particular matching is not likely to be well-received.   What else could we do? People would like to be paired with their first choice. In this case we could have A with X, B with Y, C with Z and D with W. Clearly, if we pair everyone with their first choice, that is the ideal matching. If we could do that, the problem would be solved. But it may not be possible – it may be that two people share the same first choice. A may be the most beautiful and charming woman and W may be the handsomest man (or the richest), and all the men might make A their first choice and all the women might rate W above all the others. In this case only one person can get their first choice partner, so assigning people to their most preferred partner is not, in general, going to work.   So what can we do? Well, here is a situation we would like to avoid. Suppose that we have a possible matching in which we assign A to be married to W and B to be married to X. But A prefers X to her assigned husband W, while X prefers A to his assigned wife B. So A and X are unlikely to go along with this matching. We say that A and X are a “rogue couple”, and we can see that any matching which includes a rogue couple is going to be unstable. So we will say that we have a “stable matching” if there are no rogue couples – no pair who prefer each other to their assigned partners.   If we have a stable matching, then none of the people involved can be tempted to swap their current partner for someone they prefer who would be prepared to have them. So it makes sense that, while we cannot ensure that everyone has their most preferred partner, at least we aim for a stable matching.  And it turns out that we can always find a stable matching, so it is sensible that we make this our objective.   Here is our method. It is called the Gale-Shapley Algorithm, and it was devised by David Gale and Lloyd Shapley in 1962.   Shapley was awarded the Nobel Prize for Economics in 2012 for his work in this field.   The algorithm begins by (hypothetically) seating each woman at a desk. There are then a number of rounds during which all currently unpaired men go to the desk of their highest-ranked woman who has not yet rejected them. If every woman has exactly one man at her desk, we have finished, and the pairing we have is a stable matching, as we shall see. Where a woman has more than one man at her desk, she rejects all her suitors except for the one she ranks highest, who she accepts for the time being.  We then proceed to the next round.   Let us see how this works in practice. Suppose we have four women and four men with the following preferences:   So, we being by sitting each woman at a desk and inviting the men to go to the desk of their first choice woman. What happens is that M3 goes to W3, M4 goes to W4, and M1 and M2 both go to W1. So W1 has to choose between her suitors, and we see from her preferences that she prefers M1 to M2. So M2 is rejected, while the other men are all (temporarily) paired.   For Round 2, M2 is the only unpaired man. He has been rejected by his first choice, W1, so he goes to the desk of his second choice, W3. Now W3 has two men at her desk: she has to choose between M3 and M2. Since she prefers M2, she rejects M3.   In Round 3, the only unpaired man, M3, has been rejected by his first choice, W3, so he goes to the desk of his second choice, W2. There is now one man at each desk, so we have found what I am claiming is a stable matching, pairing W1 with M1, W2 with M3, W3 with M2 and W4 with M4.   Before discussing this result, let us see what we can deduce about the operation of the algorithm. First, it is guaranteed to terminate, so there is no danger that we go on forever without reaching a conclusion. How do we know? Well, if there are n women and n men, then initially there are n2 possible pairings. In any round, either no man gets rejected, in which case we have found a matching and the algorithm terminates, or at least one man gets rejected. In the latter case, since that man’s attempted pairing has been eliminated, we have discarded one of the n2 original possible pairings. So in any round in which the algorithm does not terminate, we have reduced the number of potential pairings by at least one, so after n2 rounds we can be sure that the algorithm has terminated since we have no more possibilities to consider.   Secondly, we can see that once a woman has a provisional partner at her desk, she will never be unmatched, because she only rejects that partner if someone better comes to her. So once she has been matched with someone, she is guaranteed to finish the process assigned to someone at least as good as that provisional partner. And finally we see that the outcome is a stable matching. How do we know that? Well, can a man be a member of a rogue couple? Consider any one of the men (call him M). Because of the way the algorithm works, he has already approached all the women he ranks above the partner he is assigned by the algorithm, and has been rejected by them. He could only be rejected if that woman had at that point an alternative partner she rated above M. But in that case, by our previous comment, the algorithm has assigned her a partner she rates at least as high as that temporary partner, and therefore she prefers him to M. So there is no woman who can form a rogue couple with M. And so, since no man can be part of a rogue couple, there can’t be any rogue couples and our matching must be stable.   So the Gale-Shapley algorithm guarantees to find a stable matching for n women and n men in at most n2 steps. The next question you might want to ask is about the implementation. In our algorithm, we put the women at the desks and let the men circulate. What happens if we do it the other way round, with the men at desks and the women  going to their top choice?   (Incidentally, a recent study has suggested that in the case of speed dating, where couples meet briefly and each indicates at the end of the evening which of their partners they would like to meet again, the question of who sits still and who moves around apparently has a significant effect on the outcomes. Usually, I am told, the women sit at tables and the men move from one table to the next every few minutes. In this situation women on average put fewer than 10% of the men they meet on their “willing to meet again” list. But where the men sit at the tables and the women move around, the women seem to be much less choosy. The psychology of this is unclear!)   That consideration does not apply to the Gale-Shapley algorithm, which works with the pre-defined preferences of the participants. So what happens when we apply the algorithm with the men at the desks?   In the first round, W1 and W2 go to the desk of M1, W3 goes to M2 and W4 goes to M4. M1 has to choose between W1 and W2, and he prefers W1, so W2 is rejected. In round 2, W2 goes to her second choice, M3: now each man has a single woman at his desk so we have found a matching. In fact this is the same matching as before, so perhaps we might think it does not matter which role is taken by the women and which by the men.   Let us try another example.     If we carry out the algorithm with the women at the desks, M1 goes to W2, M2 goes to W3, M3 goes to W4 and M4 goes to W1. Every person is matched, and we have a found a stable matching in which every man has his first choice of partner, so it looks pretty good for the men. What is it like for the women? Well, we see that every woman has the man she least wants! The matching is stable, because all the men are happy so none of them is tempted to stray, but the women have not done very well.   If we tackle this problem with the men at the desks, then W1 goes to M1, W2 to M2, W3 to M3 and W4 to M4. Again, this is a stable matching: this time every woman has her first choice, and every man has his second choice. You might think that this is a fairer matching than the previous one.     What this example shows us is that, although the matching found by the Gale-Shapley algorithm has the desirable property of stability, it does not necessarily give ideal results for all the people involved. So let us think about what we can hope to achieve. We know we cannot guarantee that everyone gets their first choice of partner. And we know that if a matching is not stable then it is not going to work. So we will define a stable matching as “female-optimal” if there is no possible stable matching in which any woman gets a partner she prefers to the one assigned in this matching: in other words, if we consider only stable matchings, then no woman can do better than this one. We can define “male-optimal” similarly: a stable matching is male-optimal if there is no alternative stable matching in which any man is assigned a partner he prefers to the one he has in this matching.   Similarly we can define female- and male- “pessimal”. A female-pessimal stable matching is one in which every woman gets the worst partner she can be assigned in any stable matching. So when we had our example in which every man got his first choice partner and every woman got her last choice, that example was male-optimal and female-pessimal. It turns out (in fact it is not difficult to show) that the matching found by the Gale-Shapley algorithm, with the women at the desks and the men “proposing” to their most-favoured potential partner who has not yet rejected them, is both male-optimal and female-pessimal, while if we apply it with the men at desks and the women proposing, it is female-optimal and male-pessimal. (Incidentally this means that if, as in our first example, both algorithms find the same solution, then there is only one possible stable matching).   So we have a slightly unfortunate situation. We can apply our algorithm to give the best possible results for women, but in that case the men get their worst possible outcome. Or we can do it the other way round, with the men getting their optimal outcome, and the women their pessimal.   Now, you can find analysis on the web applying this to human dating behaviour. The suggestion is that traditional patterns, where the men take the initiative (as in the women-at-desks-and-men-proposing implementation of the Gale-Shapley algorithm) lead to outcomes which are good for men and less so for women. A suggested lesson is that you are more likely to find the best possible partner for you if you take the initiative in approaching potential mates rather than wait to be asked.  As one, widely-circulated, academic PowerPoint presentation of this material says, “Advice to females: learn to make the first move.” Another lesson might be that, if you want to find your best possible partner, you have to be prepared to face rejections on the way.   These lessons may or may not be valid, but before rushing to conclusions I think we need to check on the reality of the situation. Let us look at the basic assumptions behind the algorithm (I am assuming the male-optimal version for the sake of discussion):   • There is a fixed population of men and women • Every man and every woman can rank the opposite sex into an order of preference • These preferences do not change • While she is provisionally attached to one man, every woman is looking to trade up to a better partner • Everyone would rather be married to somebody, even the person they consider to be the worst possible partner, than not be married.   Now all of these assumptions are, it seems to me, either wrong or at least highly questionable. We have a constantly changing human population as people grow up and move around. While we might be able to rank a small number of potential partners, we cannot assign a realistic rank to people we hardly know. Our opinions of other people change all the time as we find out more about them, so our preferences certainly change. Most people try to make a relationship work rather than using the courtship period as an opportunity to trade up. And many people would prefer single life to marriage to someone unsuitable.   Human courtship (at least at this point in our history) is about getting to know someone better, and finding out how compatible a potential partnership is: it does not really resemble the Gale-Shapley algorithm process at all. That is not a criticism of the algorithm. The algorithm works very well in appropriate situations. A common one is the matching of trainee doctors to hospitals. The hospitals want the best trainees to meet their specific needs: the trainees might prefer certain hospitals depending on specialism, location and other factors. A similar position arises in matching law students to internships. These are common situations, and historically, different approaches have been taken. It is claimed that where the method used did not result in matchings which were, in our terminology, stable, this led to many problems. Employers would sign up trainees very early in their studies, to secure those they thought were the best, and they would make offers which were valid only for a very short length of time (perhaps even only a couple of hours) in order to force trainees’ hands. The Gale-Shapley algorithm has led to much better results for this kind of matching and has reduced the use of what might be perceived as sharp practice. Of course, there is always the issue of whether one is seeking the best possible placements from the point of view of the trainees, or from that of the employers.   But it is worth noting that small changes to the problem are not necessarily easy to accommodate. The Gale-Shapley algorithm will match n trainee doctors to n hospital placements in at most n2 steps, which means that in computational terms it is an efficient algorithm: the time it takes to implement is a polynomial function of the size of the problem. Indeed in this case it is a second-degree polynomial, which is pretty good.   Suppose however that in this problem, some of the trainee doctors are couples and wish to have placements in the same hospital or in nearby ones. The problem of allocation to meet this extra condition turns out to be computationally much harder – it is NP-complete, which means that as far as we know there is no efficient way to solve this problem! This shows that seemingly very similar problems can present quite different levels of difficulty.   Here is another situation in which the Gale-Shapley algorithm will be useful. Suppose we have a number of tennis players wishing to take part in a doubles tournament. In this situation there is a fixed pool of potential partners, it is reasonable to suppose that every player can rank every other as a possible partner, and everyone wants to compete so no-one will withdraw if they do not like their assigned partner. But a matching has to be stable, otherwise any “rogue couple” could withdraw from the allocation and chose to partner each other instead.   Let us suppose Gresham College decides to organise a tennis tournament. Unfortunately the budget will extend only to three top players of each sex, so Valerie Shrimplin and I have to step in to make up numbers. We have four men – let us call them Djokovic, Federer, Murray and Mann – and four women – Williams, Azarenka, Li and Shrimplin – to be assigned into partnerships for a mixed doubles.   I am assigning hypothetical preferences:   Djokovic prefers Williams to Azarenka to Li to Shrimplin Federer prefers Williams to Li to Azarenka to Shrimplin Murray prefers Azarenka to Li to Williams to Shrimplin Mann prefers Li to Williams to Azarenka to Shrimplin Williams prefers Djokovic to Federer to Murray to Mann Azarenka prefers Federer to Murray to Djokovic to Mann Li prefers Murray to Djokovic to Federer to Mann Shrimplin prefers Murray to Federer to Djokovic to Mann   (Since none of the pros have seen myself or Valerie play, it seems reasonable to suppose that they would prefer a partner of known quality.)   If we apply the algorithm with the women at the desks, the first round sees Williams choosing between Djokovic and Federer (she chooses Djokovic) while Murray is provisionally paired with Azarenka and Mann with Li. Federer is rejected so in the second round of the algorithm, he tries his second preference, Li. Li now prefers Federer to Mann, so Mann is rejected and in the third round Mann tries his second preference, Williams, but Williams prefers her current provisional partner, Djokovic. Mann now tries his third choice, Azarenka, but her current partner is Murray, who she prefers to Mann, so Mann is rejected again. When Mann tries his fourth choice, Shrimplin, the matching is complete. As we know, it is stable: both Mann and Shrimplin have been assigned the partner they least wanted, but that reflects the reality that no better partner was realistically available.   So the algorithm works well in that case. But what about the Men’s Doubles? Here the preferences amongst the four men might be as follows:   Djokovic prefers Federer to Murray to Mann Federer prefers Murray to Djokovic to Mann Murray prefers Djokovic to Federer to Mann Mann prefers Murray to Federer to Djokovic   Can we find a stable matching?  Well, any matching must assign Mann to one of the other three.   • If Mann partners Murray and Federer Djokovic, then Murray would rather be partnering Federer, and Federer prefers Murray to his assigned partner Djokovic, so Murray and Federer form a rogue couple and the matching is not stable. • If Mann partners Federer and Djokovic Murray, then Federer would rather be partnering either of the others, and Djokovic would rather partner Federer than his assigned partner Murray, so Federer and Djokovic form a rogue couple. • If Mann partners Djokovic and Murray Federer, then Djokovic would rather play with either of the others and Murray prefers Djokovic to his partner Federer, so Djokovic and Murray form a rogue couple.   So however we assign partnerships in this situation, there is a rogue couple.  What we have found is that in the Men’s Doubles situation, there may not exist a stable matching.  It seems counter-intuitive that there should be such a big difference between arranging a mixed doubles and a single-sex doubles.  In one case good (that is, stable) matchings exist and can be found efficiently by a simple algorithm, while in the other there may not even exist any satisfactory matching! Again, before one attempts to apply this conclusion to bisexual or gay dating (a temptation that some web accounts fail to resist) one should remember that the basic assumptions behind this analysis do not accurately represent human courtship behaviour. Presenting this theory in terms of dating and marriage is a good way of making it interesting, but the real applications are in different areas (such as matching trainees to internships). While the Gale-Shapley algorithm undoubtedly has some relevance to computer dating, the basic algorithm as I have presented it is unlikely to make a fortune for any potential match-maker, because it solves the wrong problem. Dating agencies want to generate a reasonable number of possible matches for all their clients, not to find a single match for everyone. More complex versions of the algorithm would be needed.   So, let us sum up. We have seen a number of mathematical approaches to finding matchings. The Secretary Problem addresses one aspect of the problem. If we have constraints on who may marry whom, Philip Hall’s theorem tells us whether or not it is possible to find a matching which meets these constraints. For the situation where we know everyone’s preferences regarding partners, the Gale-Shapley algorithm gives us an efficient way of allocating people which is guaranteed to be (in a precise sense) the best possible matching for one of the sexes (and equally is guaranteed to be the worst possible matching for the other sex!) We have seen that whereas viable matchings exist when we are pairing one set with another, the situation is rather different when we are pairing off members of a single set – for example, the problem of assigning room-mates. In this situation, no good matching may be possible.   Although I have tried to show that the idealisation required to mathematise the problem means that the mathematics I have presented today is (in its simplest form) of limited value for real-life matchmakers, it does solve other important problems, like matching trainee doctors to hospitals. But even though the mathematics is effective, the choices that have to be made – do we prioritise the wishes of the doctors, or of the hospitals?  – show that sometimes decisions about implementing mathematical algorithms require sensitive, non-mathematical choices to be made.   After investigating the mathematics of love – and although Cupid’s darts may be random, you will notice that our mathematics has been entirely deterministic - my next lecture, on Monday 17 March, will explore how mathematicians use randomness to solve non-random problems. I hope to see you then.       © Professor Tony Mann, 2014