title: Algorithm for pairing people using messages
body: <p>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.</p>
  
  <p>New people can enter the group <em>while the pairing process is going on</em>. Once two people are paired as optimally as possible, they drop out of the group.</p>
  
  <p>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.</p>
  
  <p>There is no central controlling entity: all the work has to be done by passing messages between people (or broadcast to the whole group).</p>
  
  <p>What's the best algorithm for doing so?</p>
  
  <p>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?</p>
  
  <p>This is similar-ish to the <a href="http://en.wikipedia.org/wiki/Stable_roommates_problem">http://en.wikipedia.org/wiki/Stable_roommates_problem</a> 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.</p>