Algorithm for pairing people using messages

Question

Imagine you've got a bunch of people who all want to find a partner from among that bunch of people. Each person can make an announcement to the whole group, or to any specific person. The goal is that they all end up in pairs where possible.

New people can enter the group while the pairing process is going on. Once two people are paired as optimally as possible, they drop out of the group.

Each person has a "score" for each other person. People should be paired with higher-scoring partners where possible. However, it is more important that people find pairs at all than that those pairs are strictly optimal. So it is reasonable, for example, to have two people "provisionally paired" and then wait a bit to see if a better partner for either comes along; if one does not, then properly pair the two and they drop out of the group.

There is no central controlling entity: all the work has to be done by passing messages between people (or broadcast to the whole group).

What's the best algorithm for doing so?

Obviously the problem I'm trying to avoid is that A randomly chooses B and says "hey, be my partner" and at the same time B says to C "hey, be my partner". Also, A can't just announce "someone be my partner!" because A will get responses back from everyone, and if B has also announced "someone be my partner" should B respond to A's announcement or not?

This is similar-ish to the http://en.wikipedia.org/wiki/Stable_roommates_problem but (a) that's about finding a "stable" (strictly optimal) solution, which is useful but not required in my problem, and (b) it assumes the group is fixed in size and doesn't change, whereas my problem allows new entrants to the group while the "pairing election" is going on.

Answer 1

You don't seem to give a method for describing the "goodness" of a pairing, or what information is needed to determine that. For example, can I know my "goodness" of fit with someone without messaging them? Do I have perfect information? In this case there are some well known and fast network flow type formulations which will find the best total solution. As long as everyone "independently" comes to this conclusion there will be no problem.

Its also extremely important to know if this goodness measure is symmetric. Is the score(A,B) = Score(B,A)? Transitivity is also useful if it can be established. But that seems unlikely.

If on the other hand, I need to message someone to find out our fit, then we have a menu type problem. Look up, for example, Feynmann's Restaurant problem, which tells you how many dishes you should try in a menu of fixed size if you want to get maximum utility from some number of selections.

Its also unclear if you intended this to be a representative agent type problem (everyone has to use the best solution) or a game theory type solution (what should a user to to maximise their personal score). For example, the best solution might be some kind of mixed equilibrium, where some people broadcast their attributes, and other people work out their scores and approach the best looking.

This is a fascinating problem, but I am not sure that it is very well defined yet.