Algorithm for pairing people using messages

10
votes

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.

3
algorithm
Interesting problem! Can you shine a light on your intended use, then it is easier to propose ideas. For instance, should the system be incentive compatible? That seems tricky for this particular case. – Vincent van der Weele
I don't think I know what "incentive compatible" means? – sil
In game theory, if you let the agents (people in this case) decide something, you want to prevent them from "cheating". In this case, it would be sort of cheating if all people wait forever, afraid to bond before a their perfect match shows up. Do you want to prevent strategies like that? – Vincent van der Weele
I do want to prevent strategies like that, but my plan there is to basically have a timeout: choose a provisional partner (somehow) as early as possible, trade for a better partner whenever you can, and at the end of the timeout, go with whoever your provisional partner is. – sil
Is the timeout known in advance? How much worse is a solution when two people remain unpaired than a suboptimal pairing score? – biziclop

3 Answers

2
votes

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.

0
votes

Seems like you just need a "stick or twist" weighting for each pair to allow 'good enough' exit, think "closing time at the disco".

Each person starts with some stickiness factor = 0. Start by choosing a provisional partner (through some reasonable heuristic/random hash/whatever)

Then iterate over something like this:

  1. if your provisional partner has chosen you too, you are a pair
  2. if your provisional partner has not chosen you yet, and you are 'sticky enough', they remain your provisional partner
  3. if your provisional partner has not chosen you yet, and you are 'not sticky enough': choose another partner
  4. if a suitor has stuck around, consider them more attractive in the next round
  5. if you're still in the running, increase your 'stickiness'
0
votes

Depends on the number of people involved, you might be able to store all the incoming data in one client and sent it along with the message when the client broadcasts itself. Example:

right now only 3 people A B C

A broadcasts

B stores, { A , msg:xxx }

B broad casts { A, msg:xxx } { me (B) , msg:yyy }

A stores, {B, msg:yyy}

C stores, { A , msg:xxx }, { B, msg:yyy }

D joins, broad cast with get all person request

A sends back { B, msg:yyy } { me(A), msg:xxx }

B sends back { A, msg:xxx} {me (B), msg:yyy}

C is not broad casting so not sending anything

D processes all the incoming requests and do some analysis to determine possible people in the area

A and B matches

A, B broadcasts remove A, B

C stores, {}

D stores, {}