Proposal - Round Robin Gift Exchange

[jack]

Several people have suggested gift exhanges, or secret santas, or the like. The idea being, for people who don't know, that a group of people who would like to get each other presents, but don't have time, money or ideas enough, buy and receive one gift from people chosen randomly. (Normally by drawing names, so no-one occurs twice.)

I would use a computer algorithm, making the procedure:

* Sign up on a website listing 5-10 people you would buy a gift for one of.[1]

* You or it emails them and invites them to do the same.

* Next week, everyone is conveniently matched so they get an email giving them one person to buy a present for (ETA: from the list of people they specified they knew!), and will get one gift but they don't know who from yet.

* ETA: the matching may start from a friends list, but would probably need to be confirmed by hand.

I like the idea, and the tech necessary should be minimal.

Yes, I know a website that does that. (Comment with details.)
Jack should write one.
I'd do it.
Your algorithm isn't going to work because [comment].
Comments:

[1] Or more if you like, but there shouldn't be much point. And don't choose your best friends necessarily. Miss out anyone you're buying for anyway, and anyone you can't think of anything for. And choose randomly so no-one's offended.

Comments

[miss-next.livejournal.com]

Which reminds me. If you would like a card, could you let me know your address? Many thanks! :-)

[chess]

So you sign up on the website and list 5-10 people you'd like to spam. The website obligingly spams them for you, and invites them to come and spam other people and/or agree that they'll buy a present for some random person. The whole thing gets out of hand and you find that you are shipping your present to Outer Mongolia.

Um. You first need to think about things like 'how are the least-connected of the people likely to end up signed up connected and how is the gift going to get between them' and 'how much should each person spend' and 'are there any appropriateness limits / allergic reactions we will need to take into account'.

[cartesiandaemon.livejournal.com]

Doh! I'm sorry, it seems I *am* an idiot when it comes to explaining things. The point is that you're matched to one of the people you listed "I would buy a present for this person". So it might be a big network, but that doesn't matter except that you can join when you know some but not all of the people involved.

Obviously there are existing websites that let 50 people exchange gifts.

Does that it less stupid?

[yrieithydd.livejournal.com]

Does that it less stupid?

No!

[cartesiandaemon.livejournal.com]

ROFL. OK, my brain is just completely dead tonight. Nevermind.

[simont]

I have most of a ready-written piece of code which can do the matching, if you'd find that useful.

As you may remember from Graph Theory, a perfect matching of this type can fail to exist iff there is any set of too-selective givers such that the union of all the recipients they'd be willing to buy presents for has smaller size than the set itself. (By complementing both sets you can also derive a set of unlucky recipients such that there aren't enough givers willing to buy presents for them.) In that situation my code can also tell you what that set is, although it's unclear what you'd do about it if it happened. Perhaps mail all the people in the too-selective set and politely suggest that they choose at least one additional recipient from the unlucky set?

[angelofthenorth.livejournal.com]

I suggested that it should be done based on f-list interactions. The simple thing to do would be to cross-reference, because at that point it becomes a matter of beginning with the most difficult to match and then finishing with the easiest.

[cartesiandaemon.livejournal.com]

Sorry, I was going to say something about that but forgot to put it in the post.

It's a very good way of getting started, because it's a ready made list of people you know about that well, but I think it would require manual editing, (a) because my flist includes virtual people and (b) I wanted to include people who don't lj.

[angelofthenorth.livejournal.com]

It's easy enough - you simply use the function that allows people to create a virtual LJ name and create a virtual flist....

[cartesiandaemon.livejournal.com]

And also, I want to get *real* presents ;)

[angelofthenorth.livejournal.com]

*grins*

[cartesiandaemon.livejournal.com]

I remember that theorem, yes. I figured it would *probably* work, and if not someone can bodge it by hand then, eg. making someone buy a gift for a friend-of-a-friend.

If it comes to it, the code would probably indeed be very useful; I knew it would be a solved problem.

[simont]

The code in question is in my puzzle collection: it's used in the puzzle "Tents", for which one of the criteria defining a correct solution is that the bipartite adjacency graph between tents and trees contains a perfect matching. (I think that's the single silliest winning condition in any puzzle I've ever seen. Most puzzles require at most linear-ish time to check a solution; finding perfect matchings is O(N³).)

So if you wander into the Subversion repository (a web interface to which is linked from the main puzzle page), you should find maxflow.h and maxflow.c which define a set of functions which use the Ford-Fulkerson algorithm to solve the max-flow/min-cut problem. This is a superset of the perfect matching problem, which is why I wrote that rather than a simpler matching-finder.

To solve a perfect matching problem, first construct a network containing one source, one node for each giver, one node for each recipient, and one sink. You need a graph edge going from the source to each giver, one from each recipient to the sink, and one going from each giver to each recipient iff that giver is willing to buy for that recipient. Hence, the maximum flow in that network is also the largest available matching. So then run the maxflow function; it will return you a flow array stating whether each graph edge is part of the matching. It will also return a total maximum-flow value telling you how many edges were in the matching, from which you can quickly tell whether it was complete or not. If not, you can examine the cut array to see which vertices were the cause of the problem: giver vertices with a 0 in the cut array are the too-selective set, and recipients with a 1 are the unlucky people who not enough givers will buy for.

An example of most of this code is given in the function new_game_desc() in tents.c, and again in the execute_move() function.

I hope that's of the slightest use :-)

[(Anonymous)]

Hopefully! It depends if anyone's interested, I'll look at the matching when I get there. But it's certainly more satisfying to reuse something than hack it by hand.

[stephdairy.livejournal.com]

What's the little image at the bottom of the form?

(S)

[(Anonymous)]

Help capture refer urls so I know who said what. I know, I know, lj polls are better :)

[numberland.livejournal.com]

When you say "I'd do it" in the poll are you asking if we'd sign up or if we'd write the code. If the former, then yes I would.

[cartesiandaemon.livejournal.com]

You know me too well. I meant "sign up to the exchange", but when I reread it, it couldn't have meant anything but "code it". I did *not* write this post well.