Algorithm for best suiting people's choices from a definite list of items where there is only one of each available?

Question

Ladies and Gents,

My best friends and I do a "Secret Santa" type gift exchange every year, this year I've been trying to think of a couple of ways to make it interesting. There are six of us involved and I want to design a small program that allows the six of us to rank their preferred gift-recipients from 1 to 5 as well as their preferred gift-givers.

So, let's say we're called A, B, C, D, E and F.

A submits two lists:

List 1 - People I would most like to give a present to: B, D, C, F, E

List 2 - People I would most like to recieve a present from: F, D, E, B, C

All six of us will submit both these lists, so I'll have 12 lists all together. I suppose my question is what is the best algorithm to now go ahead and assign each person a gift recipient?

I thought of something like this:

If two people have both selected each other in their opposing lists (i.e. A most wants to give to B, B most wants to get from A) then I immediately assign A to B. So now A is removed from our list of gift-recipients and B is removed from our pool of gift-givers.

Once I've assigned the "perfect matches" I'm kind of lost though, is there an establish algorithm for situations like this? Obviously it's only for entertainment value but surely there must be a "real" application of something similar? Perhaps timetabling or something?

My Google-fu has failed me but I have a feeling it might just be due my own lack of precision in search terms.

Cheers, (and Happy Holidays I guess), Rob

---

Update / Part 2

Okay, Ying Xiao came to the rescue by recommending the Gale Shapley Algorithm for the Stable Marriage Problem and I've implemented that in Python and it works a treat. However, this is just a thought that occurred to me. I guess within our group of six best friends there are three pairings of "extra-best" friends so I have a feeling we'll just end up with three pairs of AB, CD, EF and BA, DC, FE in terms of gift giving and recieving.

Is there an algorithm we could design that did take peoples rankings into account but also restricted two people forming a "closed group"? That is, if A is assigned to buy a gift for B, B can not be assigned to buy a gift for A? Perhaps I need to solve the Stable roommates problem?

Related questions:

• Secret santa algorithm.
• What is the best low-tech protocol to simulate drawing names out of a hat and ensure secrecy?

Answer 1

The Gale-Shapley algorithm (for the Stable Marriage problem) applies only when each person has a ranked list of all other participants -- you may or may not be able to convert your problem to that form (make everyone rank everyone).

Also, note that the thing it is optimizing for is something different: it tries to find a set of stable marriages, where no pair of people will "elope" because they prefer each other to their current partners. This is not something you care about in your Secret Santa application.

What you want (depending on your definition of "best") is a maximum-weight bipartite matching, which fixes both the above objections: put the "givers" on one side, the "receivers" on the other (so two copies of each person, in this case), give each edge a weight corresponding to how highly that giver ranks that receiver, and it is now the assignment problem. You can use the Hungarian algorithm for this, or simpler (slower) ones. You can also vary how you assign the weights to optimize for different things (e.g. maximize the number of people who get their first choice, or minimize the worst choice that anyone gets, etc.)

If you do use the Gale-Shapley stable marriage algorithm, note that it is optimal for the "proposers" (male-optimal and female-pessimal), so be sure to put the "givers" as the "proposers", and not vice versa.

Answer 2

For each person, create two virtual people, a "giver" and a "receiver". Now match the set of givers against the set of receivers using the Gale Shapley Algorithm. Runs in O(n^2) time.

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