Your weakness is not your technique

July 16, 2014

[Pre-post post-note: an amazing alignment of the stars! Just hours after writing this, I came across the much stronger Lockhart’s Lament. A must read, I daresay.]

Professors, teaching assistants, professional exam-writers, lend me your ears; I come to fix the exam, not to praise it. The exams that students solve, live after them; the results are oft interred with their bones.

This week I had my final examination in quantum mechanics 1. It had three open questions, two of which can basically be reduced to something as follows:
1) Apply the second order correction according to the scheme you learned in class to the following perturbation: …
2) Diagonalize a 3×3 matrix. Using the basis transform, express some vectors as a linear combination of other ones. Use these to obtain a wavefunction and integrate it.

In essence, the questions were just (very) technical mathematics exercises, not-so-cleverly disguised with an excuse for a physical background. This type of question is exactly what keeps me off my ass when studying for these exams. Is this a test in integration? A test in algebra? I already had those last year. I want to do some physics! In this case, converting the physical premise to the mathematical relations, or identifying the right equation in the formula sheet definitely didn’t count as “physics”.

As an analog, imagine a computer science class; over the semester, you went over the whole deal – sorting, graph flow, DFS/BFS, pattern matching. Now comes the final exam, and as you open up the questionnaire, your eyes grow wide with despair.

Question 1: Apply the quicksort algorithm to sort the following array. Make sure to write the complete derivation; a final answer only will not be accepted:
318, 330, 44, 304, 181, 472, 80, 245, 185, 45, 250, 285, 404, 370, 430, 194, 273, 180, 233, 146, 132, 473, 331, 291, 265, 444… [74 more items omitted]

What, isn’t that a legitimate question? After all, you learned about the quicksort method in class; here is your chance to show that indeed you know it, earning your exam points in earnest.
Oh, what’s that? It would be a dull and error-prone thing to do, that doesn’t really show the student’s proficiency in algorithms? It would be much better to have the student invent a similar but distinct algorithm to show that they grasp the concepts? In fact, inventing new algorithms and proving correctness and bounds is what actually happens in algorithms tests?!

It’s certainly possible to ask interesting questions, that actually require invoking the student’s physics-neurons instead of just the high-speed-integration ones. In fact, we had plenty of those in our classical mechanics lessons. And they might involve some difficult mathematics in order to get the right answer.

But when I compare my classical mechanics 1 exam with my quantum mechanics 1, I notice that the former’s (great) difficulty was in understanding what the hell I needed to do, while the latter’s was in diagonalizing quickly and keeping track of the trillions of minus signs, \sqrt{2}‘s and \hbar‘s. Admittedly, I am no expert, but for some reason I am quite certain that it is not quantum mechanics that is at fault here – certainly there is no dearth of physical reasoning which can also be backed up by mathematics (see Feynman vol. III, for example).

Professors, teaching assistants, professional exam-writers, lend me your ears! Cease the technical absurdity, and return physical insights to your exams! They shall make your students all the wiser, in addition to sparing them the sprained wrists and CTS. And if you claim that the exam should portray only what has been taught in class; well, what exactly have you been teaching then?

Zero knowledge in the real world?

July 5, 2014

[Written under the influence of QCSD]
Not so long ago, I happened to watch the totally-accurate-in-every-possible-way film, “Travelling Salesman”. tl;dw: a squad of government-hired mathematicians are finally able to prove that P = NP, giving the state the power to answer every important computational question they can imagine (aka rob banks and fight terrorism). But when requested to hand over their findings, the mathematicians begin to doubt that they are doing the right thing (as opposed to, say, publishing the results and letting everyone enjoy the spoils). A difficult question indeed – unleashing a polynomial algorithm for an NP-complete problem does imply breaking almost all cryptosystems in use today, in addition to creating better flight plans for cross-country salesmen. Definitely, if we ever prove P = NP, the history of mankind will be divided into distinct “before” and “after” phases.
But what if the mathematicians aren’t interested in breaking ciphers, but just want their well deserved fame and glory for solving a very hard problem? It is here that I wonder if the computer science and mathematics communities are ready for non analytical proofs as part of science-doing, and not just as part of complexity classes.

A brief word of explanation first. The rigour with which results are demonstrated differs in various academic fields. In sociology and medicine, statistical significance is basically all there is, so saying “there is a less than 2% chance of our hypothesis being wrong given the clinical tests” is pretty darn good. In experimental physics, too, we can never be more sure than our measurement error. However, in theoretical physics, mathematics and computer science, an analytical proof, filled with lemmas, propositions and an abundance of silly symbols, is needed. Indeed, even computer-assisted proofs, ala the Four Color Theorem, are frowned upon and looked at with a wary eye.
One reason for the wariness of computers, of course, is that computer programs and hardware naturally have bugs, and who’s to say that the calculation was correct? Before stating that something is an irrevocable mathematical truth, one must be sure! Of course, humans make mistakes when writing and reading proofs as well; a small bug hiding in a 300 page manuscript might be able to evade all the reviewers and find itself in publication, impostering as a profound truth.

If printed mathematical texts can be wrong (god forbid!), why not accept that fact and welcome probabilistic proofs – proofs that are probably correct (why probably? because there is randomness involved), up to an error as small as we choose. Computer science already has this well defined – the BPP, MA, SZK, and PCP complexity classes, for example – but what about real-life science? (gee, now I know why Scott complains about naming conventions in complexity theory…)

I propose the following scheme: say our mathematician Bob wants to show the world that he has proved P = NP (and therefore, also P = co-NP), and in fact has discovered an algorithm for solving NP complete problems. However, he does not want to give away the algorithm, just show that he knows it. He thus set up a private server which handles incoming requests, and starts playing a sort of zero knowledge interactive proof protocol with the mathematical community. The community sends him boolean expressions of increasingly larger size n. For each expression s: if s is satisfiable, the server replies with a satisfying assignment. If not, the server replies with a proof that verifies that there does not exist a satisfying assignment. In other words, the server replies whether s is in SAT or in SAT-complement, and either way provides a proof for it. These are NP and co-NP complete problems, so solving them in polynomial time shows that P = NP.
Now, all currently known algorithms take super-polynomial time to run. So if Bob only had access to known algorithms, he would not be able to solve the problems as n becomes larger. However, assuming that the polynomial in Bob’s algorithm isn’t of very high degree, and that its leading coefficients aren’t gigantic, he can answer the questions even for large expressions. Knowing Bob’s computational power, the community could very well know if he runs in exponential or polynomial time, proving that he does not lie.
Where does probability come into play? Well, it may be that Bob is guessing. Bob might be a fraud, and whenever he gets a boolean expression, he randomly generates polynomial-sized certificates, and sees if they prove satisfaction / unsatisfaction of the expression. Of course, his chances of succeeding are exponentially small as n gets larger, but for every finite number of tests the community presses upon him, there is always a finite chance that he gets it right. Also, even if Bob runs a deterministic super-polynomial algorithm, for some lucky expressions he might be able to get the right answers quickly** (see problem below), so the community itself needs to randomize the expressions they send.

As it is, will this kind of “proof” catch on among fellow mathematicians? I doubt it. Even if you exclude the whole “his algorithm runs fast so it must be polynomial” problem, I think we are still far off from a more ideal world: one that has, in addition to science journals, an international array of servers dedicated to interactive, zero knowledge, and other probabilistic proofs (actually, under plausible assumptions, most those can be de-interactivated, no?), representing those theorems and propositions which we almost know are true; we’re just missing an ε.

Notes on note:
Note and future thoughts: The solution I have given is a bit awkward, in that it requires Bob to solve a lot of NP and co-NP problems, instead of just giving a normal zero knowledge proof to the expression “P = NP”. Suppose Bob only knows an algorithm for SAT. Can he encode it in such a way so that he can prove that it is indeed a polynomial algorithm for SAT, but that no one else will be able to use it? This is different from the zero-knowledge that I know of, in the sense that we aren’t just asking whether a specific string is in some language (aka an expression is in SAT) – we want to show that a string (program / proof) has some properties, without showing that actual string. If there are any real complexity theorists reading this, please do leave a comment.

Note to note to note: I recall hearing somewhere about encrypted zero knowledge computation – that is, Bob could send his algorithm to the community in an encrypted form, so that the community will do the calculations but have no idea what they are doing (and the computation will be different for each input, so they will not be able to reproduce the algorithm on different inputs than what they already asked). First of all, this is cool. Second, this will help base the fact that the algorithm is polynomial – but still won’t get around the lucky guesses that Bob could make if he frauds up a super-polynomial algorithm.

Too cool not to note: On the subject of “errors in human-reviewed manuscripts”: if rigour and no-chance-for-error is what you are looking for, why not submit formal proofs to the leading journals? This would constitute a sequence of lines; the first few would be the axioms, and the rest would be logically irrefutable inferences from the previous lines. The last would be the theorem you want to prove, stemming irrevocably from the axioms. Any monkey / mathematician / computer could go over these proofs and verify that they are true, no chance of error involved. Of course, I’m not the one to think of this idea, many have done so before me; for example, the QED manifesto (now, that’s a name I could live by…).

**Problem with solution: I assume here that expressions the mathematical community sends are, probabilistically, hard enough to solve with modern SAT solvers. I know that some of these solvers can work very well in some cases, failing miserably only, for example, on expressions with just one satisfying assignment. In this specific case, the assumption is that enough of the expressions only have one satisfying assignment (I seem to recall that this applies to a lot of boolean expressions).

They should have sent a poet

June 13, 2014

My O(1) readers are probably restlessly wondering where I’ve been, why I have no more posts about the mathematics of toilets, and what’s up in general.
Well, the truth is, I did have a wonderful post on the mathematics of toilets (regarding putting the sit up or down in a mixed male/female environment), but have been beaten to the topic by another enthusiast.
The real deal though, is that the past few weeks have seen an investment of effort in, not science, but poetry (although between us, is there any difference?). And lo, just this week I came back from the International World Championship Poetry Slam in Paris.

To put it nicely, Poetry Slam is a spoken word combination of poetry, rap, and doom prophecy. Admittedly, my style is pretty much none of the three, but I still enjoy doing it, and have been performing in Israel for about a year. There are many, both here and abroad, who, with just a few words and tone of voice, can wreck you to tears and collapse your stomach in anguish; fill you with laughter; or light an otherwise gloomy day. I do not consider myself to be of that caliber, but last December I happened to (against 1/3 odds) win the National competition (with this amusing poem as a starter), and before I knew it was sortied off to France in order to pit my skills against the champions of the world.

With high probability, Paris is a really wonderful city. The rain was refreshing. The Love-Locked bridge collapsed. The cheese has fungi. The pollution is persistent. And to top it all off, the Mona Lisa winked at me (she never returned my calls though).
But really, the competition itself was great. The people were awesome (really, I was in awe); the crowds were supportive; but most importantly, the poetry was crushing (lmytfy). Finnish is like music to my ears.
All in all, I reached the finals and then placed 6th. But what can you expect from a mathematics major, really?

Here are some good English ones (not from Paris), to get you started (one for every season):

Unfathomable

April 27, 2014

Sometimes, people ask me why I study physics. Lately I’ve been asking myself that as well, especially with respect to my future studies. Then again, sometimes, when I read a book or walk about in the garden, I happen to accidentally look at my arm and HOLY SHIT MY HAND IS MADE OF 1026 PROTONS AND ELECTRONS THAT ARE HELD TOGETHER BY THROWING PHOTONS AND GLUONS AT EACH OTHER AT THE SPEED OF LIGHT.

I guess that’s why, in a way.

Intelligence is inexplicable

April 8, 2014

So, the question still remains – after spending endless nights in front of a bright screen, surrounded by empty pizza boxes and the soft hum of cooling fans – when does your program finally count as “intelligent”? It may have started out as a simple “hello_world.c”, but now it’s a raging monstrosity, fully imbued with seven layered neural networks, evolutionary algorithms and a taste for human blood. Doesn’t that make it an artificial intelligence, even if it can’t pass the Turing test? (To be honest, I know many real-life people who wouldn’t pass the Turing test themselves).
Yes, many papers have been written on this, and the walls of a myriad rooms are covered with Eastasian symbols, but still, it will do no harm to spew out my own two cents. I guess I could search the relevant literature first, but there’s no fun in that, is there?

tl;dr? The main points, summarized:

- An intelligent machine must be able to solve problems it has never encountered before.
– If a machine can be reduced to an algorithm which humans understand, it is not intelligent.

These are necessary, but perhaps not sufficient, conditions.

Since this is just a definition, and we won’t do anything rigorous with it, I can afford to simply look at some specific cases and use inductive arguments in rashful abundance.

We’ll start with an example. Consider the task of sorting numbers: we have a list of numbers, and we want to arrange them from smallest to largest.
I think it’s safe to agree that a preprogrammed computer running “heapsort” would not be considered intelligent. After all, it’s just using a predefined algorithm, one which was mathematically proven to work, line after line. There’s no intelligence in that. It’s a simple mechanical process, with a sole and not-very-surprising outcome.
But give a child (i.e – anyone with no knowledge of heapsort) a stack of cards and ask her to sort them, and she’ll eventually succeed. Perhaps she won’t do it in the most efficient way possible, but let’s look at the circumstances – she was not preprogrammed with a built-in sorting algorithm. All she had to start with was the goal – “I’ll give you some chocolate if you sort these cards for me” – and eventually she found a way to solve the problem – perhaps by gathering on her previous experiences, or perhaps by some Divine Inspiration – who am I to judge?

I say then, that an intelligent being is one which is not designed to specifically solve one type of task – except, perhaps, for the task of solving other tasks. An artificial intelligence must be capable of solving problems it has never encountered before. In that sense, in my opinion, programs whose sole purpose is to pass the Turing test should not be considered intelligent (then again, I don’t think that the Turing test is a definitive way to decide artificial intelligence in any case).
You might get a bit angry and interject, “but a Turing-test solving-machine may encounter questions and dialogues that it was never pre-programmed to answer!” To this I say, that such a machine is closer to a linear-equation solver, which, much to its delight, was just given as input a set of coefficients which it was never given before. I think solving the Turing test is much closer to that side of the spectrum, rather than to the “solve types of problems it never saw before”. You might say that a general problem solver is the same, only with problems as inputs and not coefficients, but there is a vast difference between “solve the problem of talking to humans” and “solve the problem of solving problems”.

One thing I do take from the Turing test, is the fact that it puts a main emphasis on humans. We don’t really work hard on creating a machine that is indistinguishable from a dog, or perhaps, an ant. I bet most people are willing to crush ants, but are less willing to crush dogs, partly for the reason that ants are much more mechanistic than dogs. But humans, now, those are a different matter. How does a human work? What inner mechanisms drive thought forward? How can it be that a set of neurons firing can lead to differentiation of continuum and discrete infinities? We don’t know, and hereby lies our intelligence.
To put it plainly: if we have an algorithm for solving new problems, and we understand how that algorithm works (perhaps, by some miraculous wonder, we also proved that it is correct!), then a machine implementing that algorithm is not intelligent. How would it be any different than the machine implementing heapsort?
Now, eventually, all machines (both silicon and carbon based) can be reduced to transistors opening and closing / if-else clauses / neurons firing, so we have to be careful here – reducing a machine to mechanical actions is not enough to deprive it of its intelligence – indeed, I do not claim that there is some non-physical or non-algorithmic process involved, or that our intelligence is found in some sort of “soul” or whatnot. Rather, the keyphrase here, is “we understand how that algorithm works”. To put it in other words, intelligence is subjective.

Consider our favorite pastime learning technique of artificial neural networks. We create a large batch of randomly connected neurons, and give them zounds of data sets to learn. At the end, the weights between the neurons are such, that the network is capable of solving the specified problem rather well.
But given the network, we cannot (well, at least I cannot) say that we understand why it works. It’s just the way the weights, the reverse-feedbacks, the interconnected relations turn out. Hell, we even started with a random network! We have programmed the network using our design; we understand the learning algorithm; but the network itself? Given the connections and weights, it’s very hard to say why these particular values work; it’s also hard to say why these are the ones that we got, and not any other ones.

I am aware that there is a not-so-comfortable disadvantage in this argument, stemming from its conclusion. If ever we were to reduce, in totality, the human brain to a series of provable algorithmic steps – we would be forced by this criterion to revoke our own status of intelligence. That would totally suck for our collective ego. Also, if intelligence is subjective – if ever there was an alien race which could comprehend our brain – they would consider us mindless automata, while we currently consider ourselves the prime of all Creation. Humbling, isn’t it?

The conditions I give are necessary, but I would not hasten to call them sufficient. If you merely obfuscate your algorithm, making it incomprehensible, that wouldn’t make the machine running the code any smarter. Likewise, solving new problems by brute forcing through a gargantuan configuration space does not grant further IQ points.
If you show me a neural network program which successfully solves a large set of new unencountered problems, I’ll probably agree on calling it intelligent. But most things less than that are either too narrow, or too comprehensible.
What good is this definition? I don’t know, what good is any definition of artificial intelligence? We are still far away from machine ethics, and until then, such definitions have no practical use. Perhaps it would deem to be useful, in case we ever prove, mathematically, that the brain contains inherently unprovable algorithms. But that’ll take a while.

A short note on large numbers

March 4, 2014

It is not very often that we encounter large numbers in mathematics; in fact, in some fields it’s sometimes quite common not to encounter numbers at all. Most numbers you meet are relatively benign and harmless: 0, 1, 2, 3, e, π; you don’t need much apart from those. In any case, even to an aspiring toddler, they are not large.
But sometimes there naturally appears a number that is obscenely large. Well, it depends on what you mean by naturally, I suppose, for there are so many possible questions to ask, some of them must give large results. But as far as I have seen from my studies, usually when you ask nice questions, you get nice answers (well, if you get answers at all). As an example, the infinite sum \sum_{n=1}^{\infty} \frac{1}{n} diverges, but the infinite sum \sum_{n=1}^{\infty} \frac{1}{n^2} converges to \frac{\pi^2}{6}. Somewhere along the way, you can find a value of α such that the sum \sum_{n=1}^{\infty} \frac{1}{n^{\alpha}} converges to any number you want, but that would be picking a rather specific target, and the problem sounds contrived. Asking about n and n2 seems very natural, though.
But today I ran into the prime counting function – π(x) – which counts how many primes there are from 1 to x. It’s not that easy to calculate, but we can use approximations. A relatively-ok one is called li, for logarithmic integral, defined as

li(x) = \int_{0}^{x} \dfrac{dt}{\ln t}.

It’s not an entirely bad approximation: here you can see the number of primes, and the li(x) function in the same graph:

num_of_primes

It may seem by looking at the data that li(x) is always larger than π(x), but this is not the case. In fact, the quantity li(x) – π(x) changes sign infinitely often (proven by Littlewood). At what value does the first sign change happen? Meaning, what is the first x such that that π(x) > li(x)?
We don’t know, and whenever we don’t know the exact answer, we try to bound it from above and from below. Lower bounds are found by computing both functions for increasing x values, while upper bounds require theoretical results.
Currently, we know that the first sign change happens at

10^{14} < x < e^{727.95135}

I find this surprising.
First, the current upper bound is enormously large. There is always room to wonder when we encounter numbers in proofs that are larger than the number of atoms in the universe. It may be just an artifact of the proof, the real number may be much smaller, but for me, it certainly causes eyebrow movement.
Second, the lower bound isn’t miniscule either. For a phenomenon that happens infinitely often, it sure is taking its time. Many interesting prime properties can be found early on in the prime sequence (I suppose that’s how we bothered looking for them in the first place), but this one can not. You may say, of course, that the question isn’t that natural – after all, li(x) is just another approximation function – but as an approximation, its relative simplicity and straightforwardness are quite attractive.
Primes are rooted deep in number theory; if we wish to understand mathematics, we must understand primes.
And this causes me to ponder:
Mathematics does not care about our lovely intuition of what constitutes a “big number”. It laughs in the face of the adorable humans, trying to understand the world within their own references and scales. There is an infinite amount of natural numbers. Period. There is an infinite amount of primes. Period. Name a number as large as you like, but once you name it, know that it is insignificant and tiny when compared to the vastness and infinity of those that follow it. It is hard to comprehend just how many natural numbers there are; perhaps the real surprise should be the sheer amount of results we have that do not involve incredibly large numbers.
Don’t you find that reassuring?

The Perfect Match

February 14, 2014

Valentine’s day is upon us, a cheerful reminder that the main purpose of every living creature is to copulate as much as possible and spray the world with its offspring; the more, the merrier.
This is certainly easy enough for all those twice blessed prokaryotes; twice blessed, first, for their asexual reproduction via mitosis, obliviating the need for a mate; second for their lack of consciousness, avoiding the misery induced by the absence of aforementioned mate.
However, for the rest of us, finding that special someone is tricky business; it’s a game of both chance and skill, bluffing and honesty, combinatorics and probability (well, if you’re into that kind of stuff). It’s no wonder that the world is filled with attempts to make the whole process easier: dating sites, religious / traditional matchmaking, random-blind-date-generators, etc. But in the end, it all comes down to basic mathematics.

Let’s look at some of the well known algorithms and theorems for matching couples under different conditions. In quite stereotypical behaviour, mathematicians always assume that it’s possible to rank others by order of preference in a unique and unambiguous way, or that you can reject a suitor at point blank range without remorse, stating that “Sorry Billy, Roger is 0.2 [pretties] more handsome than you”, only to dump Roger two days later because the next person in the list comes along.
Oh well. Mathematics, thou art a harsh mistress.

Hall’s Marriage Theorem:
Our first theorem discusses whether it’s possible to get everyone married in a group of n men and n women, assuming that not everyone is willing to marry everyone else (sounds reasonable). The procedure is this: for each man and woman, ask them if they see themselves as a married, middle-age couple. If so, then they are potential wedlock candidates; otherwise, you won’t pair them up. Equivalently, you could ask every man to make a list of the women he would be ok marrying with, then have the women look at the lists and cross themselves out if they don’t agree.
The result can be given as a bipartite graph:

hall_bipartite

Each of the upper nodes represents a woman, each of the bottom nodes represents a man. An edge means that both are ok with an eternal life together. It’s quite possible that a very attractive, high quality person will have many edges, meaning, a lot of people are interested in marrying him/her, while other people might have little or no edges at all. In the above example, Lisa is very popular – everyone wants to marry her, and she agrees to marry with everyone – while Fae only has one possible mate. Thus, some people have more options than others, and the question is, can we assign couples, meaning, pick edges, so that *everyone* gets married in the end?
A simple case where the answer is a straightforward yes is:

bipartite_match

Each man is connected to one woman, and vice-versa – meaning that the couples are already picked here, and we have no real choice.
A case where the answer is no is:

bipartite_no_match

You can try picking out couples and seeing that a solution indeed does not exist.
Hall’s marriage theorem states that a complete matching exists, meaning, everyone can be paired, if and only if the following condition applies: look at all the possible subsets of men (i.e first look at all the men individually, then at all the pairs of men, then at all the triplets, etc.). For each subset M, count the number of different women that they can marry, G(M). Then |M| <= G(M).

We can see that the condition applies in the first case – for each man in the set, there is an appropriate woman, and thus M = G(M), and we have a matching. In the second case, however, the condition does not hold: look at Joe, Frank, and Mark: the three of them only have two potential mates: Jill and Lisa. The theorem does not hold, and indeed, there is no matching.
A proof of this theorem (actually a slightly more generalized one) can be found in wikipedia. Notice that the theorem doesn’t tell you at all how to find the matching, only that it exists.

Happy Marriage: The Hungarian Method:
Suppose now that our n bachelors and bachelorettes have had enough of the single life, and they decide that everyone should get married, no matter what. So instead of asking every pair whether or not they agree to marry each other, we ask them to rank the match. The result is a number for each (man, woman) pair; the higher it is, the more miserable they will be with their marriage. We want to find a matching between all men and women, such that the overall happiness is highest, meaning that the sum over all rankings of the chosen pairs is the lowest it can be.
A way of looking at this is the following: create a n x n matrix, where the (i,j) entry contains the ranking of matching the i-th man with the j-th woman. An example might be as follows:

hungarian_matrix

So a marriage between Frank and Anne would be a happy one, while a marriage between Joe and Jill would be rather miserable in its own way.
The question reduces to this: we need to choose n squares overall, each one in a different row and a different column, so that the sum of all the chosen squares is minimal.
The simplest way to solving this is the brute force approach: just go over all the possible matchings, and pick the best one. But when there are n men and n women, there are n! different possibilities. Try doing this for 30 men and women; tell me about it when the universe ends.
Something more clever is needed, and indeed, there exists an algorithm called the Hungarian Algorithm which can solve it in O(n3) moves. In general, it relies on the fact that you can add or subtract any number from an entire row or an entire column of the matrix, and this will not change the optimal matching. Think about it this way: if you add a number to an entire row, the total sum will change, but you are going to have to pick an entry in that row anyway, so whichever matching you choose, you will always get a larger sum.
The aim of the Hungarian algorithm is to add and subtract values from the different rows and columns in a clever way, so that the values in the matrix are always non-negative. Eventually, as if by magic mathematics, there appears an arrangement of zeros that can be picked as a matching. The algorithm is not simple, and will not be given here; conveniently, it can be found at this nice site (in the context of assigning jobs to workers, but hey, once you get to a matrix formulation, the mathematics is all the same).

Stable Marriages:
The previous algorithm gave us a global maximum for happy marriages – when we summed the total “miserableness” of the matching, it was the lowest possible between all possible matchings. However, it may be that one couple was a very bad match, and they live grumply and miserably, but in the overall matching, its still the minimum. We will now ask the question – can we make everyone happy locally?
Of course, we need to ask what that means. One interpretation is this: suppose that we match up all the couples. Some of them may be dissatisfied, and wish to break apart from the shackles of holy matrimony. If a woman desires another man more than she desires her own husband, and that man also desires that woman more than he desires his own wife, then they may each get a divorce from their current partners and marry each other instead. We say that the matching we initially had is “unstable”. If no such pairs exist, then the matching is stable.
The problem is then the following: suppose we ask each man to create a list, sorted by preference, of all the women, and we ask all the men to create a list, sorted by preference, of all the men. Can we create a stable matching, i.e, no two people will agree on replacing their partners?
It turns out that we always can, and rather efficiently, too. The basic algorithm for doing this is called the Gale-Shapley algorithm. It solves the problem in up to n2 iterations, as follows: in the first iteration, all the men approach the woman first on their list – the one they want the most. Some women may get a lot of suitors, while others may get none at all. This is ok. Each woman, from all the possible suitors, picks the man she likes best, and sends the rest away. So it goes. During every subsequent iteration, all the rejected men go to the next woman on their list, with the women picking between the new guys and the one they chose the previous iteration. The process continues until no one is rejected (this is bound to happen eventually; think why).
In the end, everyone gets matched up, and it can be proven that the matching contains no unstable couples. Of course, the scheme can also be reversed, with the women approaching the men (it turns out that this yields asymmetric results, with the active suitors getting matches that are better for them. Conclusion? It’s better to ask people out than to wait to be asked out).

Final remarks:
Feel free to assemble all your single friends and try these algorithms out. I’m sure it will create no social anxiety whatsoever, and in the end, everyone will be matched up! Hurray for mathematics.
Happy Valentine’s day.

* Note: in the problems introduced we always assumed the happy case, of an equal amount of men and women. Actually, all three problems can be extended to an unequal amount. For Hall’s theorem, instead of asking if everyone can be paired up, we can ask if all the men can find wives, or, conversely, if all the women can find husbands; the theorem stays the same. For the Hungarian algorithm, if there are, for example, more men than women, we can add fictitious “unmarriable-women” until there are an equal amount, and heavily penalize choosing them – no man would want to stay alone. The Gale-Shapely algorithm stays the same, knowing that not all participants will get a date at the end.
To sum it up and state the obvious: when there is a numerical bias towards one gender, someone always gets left out, resulting in mathematical misery. The Technion, having a whopping 35% female minority out of its 13,000 students, is a fine example of this (that’s actually a generous average term; in the physics and mathematics faculties, it’s about 20%…).


Follow

Get every new post delivered to your Inbox.

Join 45 other followers