There's also a great Freakonomics podcast about this story http://freakonomics.com/podcast/make-me-a-match-a-new-freako...

NPR RadioLab did an amazing story on this!

http://www.npr.org/sections/health-shots/2015/06/11/41222485...

Isn't the donor-patient problem a vertex cycle cover? Finding a minimum one is NP-complete, how exactly is this one applied?

edit:

found a bit more information https://www.siam.org/news/news.php?id=1474

You are right that the general problem is intractable; a lot of the advances in these match making algorithms come from better heuristics and computing power.

Pretty powerful stuff. Puts paid to the notion that economics is "not real" or all handwaving, as you sometimes read here.

Not sure this particular algorithm has anything to do about economics, except its author is an economist.

Matchmaking is arguably the core of economics.

It seems to have been often studied by Economists in the area of game theory. This very nice book is by two of them:

http://www.amazon.com/Two-Sided-Matching-Game-Theoretic-Econ...

To be fair, it is also studied by computer scientists, as in the other main book on the stable marriage:

http://www.amazon.com/The-Stable-Marriage-Problem-Foundation...

macroeconomics is all handwaving

There's a great EconTalk podcast episode about Matching Markets with Alvin Roth (the Stanford economist mentioned in the article):

http://www.econtalk.org/archives/2015/07/alvin_roth_on_m.htm...

Might be related, but I recently discovered this

http://demonstrations.wolfram.com/SocialGolferProblem/

That is actually not related, but the beginning of an entirely different field of mathematics. Design theory is the study of mathematical objects called combinatorial designs[1], which are basically fancy ways of partitioning finite sets into subsets with a pre-specified structure. The thing you linked to is a specific instance that shows the existence of designs in a few specific cases.

While Kirkman essentially posed the first design theory question in the 1850's, both the authors of one of the standard textbooks[2] in the field are still alive and (IIRC) still working today!

[1] https://en.wikipedia.org/wiki/Combinatorial_design . Incidentally, the field is called "design theory," but it's not a great search term outside of MathSciNet.

[2] http://www.amazon.com/Design-Edition-Discrete-Mathematics-Ap...

As someone who just certified a residency match list last night, I'm glad this system exists.

Is there a patent on this?

The basic Gale-Shapley algorithm was published in 1962.

https://en.wikipedia.org/wiki/Stable_marriage_problem

Is this the algorithm that was discussed in the article? I couldn't find a link.

Yes, from the article: "In the 1960s, researchers David Gale and Lloyd Shapley embarked upon research to take up an unlikely subject: matchmaking."

Not that I'm aware of. (I've read a fair bit on the topic.)