Crush Games (11 Nov 2003)

This new MP isn't very good at replying to letters. The last one at least wrote something back.

(prompted, of course, by today's ID card announcement)

I meant to post this a while ago. It's an extract of an email I sent. Firstly you'll need a little background: someone setup a website for registering `crushes' (I guess it goes around like those quiz things) and then opened up the database for a while before having a pang of consience and closing it again. First I hear was spikeylady complaining:

but am most unimpressed that I can't now find out if anyone had a crush on me

Actually, that's a really interesting game problem. You want to know about all incoming arcs (people who have a crush on you) but are unwilling to disclose any outgoing arcs (people who have a crush on you). Except I guess that you are willing to disclose if you are sure the other party has a crush on you.

I didn't see the "crush thing", but I'm guess you could register your crushes on other people and it would tell you about any two node cycles (e.g. if they also fancied you). Of course, you could just falsely register everyone and find out exactly who has a crush on you. You've not given any information away because you picked the trivial subset. Of course, anyone else can do that so your number of false positives goes up as more people choose this strategy. So pretty soon any kind of service is like that is going to be useless.

(esp if they start publishing the results)

Which reminds me of one of the answers to the two-party signature problem (you have a contract that two people need to sign. Neither will sign first so they take turns saying "With 1% probability I agree to this", "With 2%" ... and so on).

Assume a fully connected, directed graph of all the people in the set of interest. Each person assigns a probability is crush to each outgoing node and at each time slice that is the probability that you'll `ping' the other node.

Pings will be pretty random and you might see a higher than average number of pings from a given node. It could be random, but it could be that they have assigned a higher probability to you. If you crush on them, you can assign a higher probability and see if they respond. That way, pairs of crushers will rise out of the mess and noone has to disclose a non-reciprocated crush.

A little like flirting, but could be made so that noone else sees any of the interactions by blinding the pings.