Algorithm to match preferred partners into groups of three

Question

What's a good algorithm to solve this problem?

I have three groups of people - group A, group B, and group C. There are the same number of people in each group. They each have a list of people in the other groups that they're willing to work with. I want to group all these people together in groups of 3 (one from A, one from B, and one from C) such that everyone in a group wants to work with the other people in their group.

How can I find these groups in a fast way? If there's no way to make everyone happy, then the algorithm should first make as many groups have three people who want to work with each other, and then make as many people in the other groups happy.

One final point: people agree on who they want to work with (if person x wants to work with person y, then y also wants to work with x). If you could also give a big-O of the running time of your algorithm, that'd be great!

Toboggan

I think you should rename your title to actually describe your problem so in relevant searches something will actually come up. – Antiscorbutic

Answer 1

This is like the stable marriage problem, but with 3 parties instead of two.

Have a look at efficient solutions for former problem (bi-partite graph matching) and adapt them to your needs.

http://en.wikipedia.org/wiki/Stable_marriage_problem

One adaptation could be to first build working pairs from groups A and B only. Then these pairs have to be paired with a worker from group C each. Let the pairs only prefer workers which both members of the pair agree on (given their lists). Note that this will only give a local optimum.

An optimal solution to k-partite matching is NP-hard to find:

http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps

See this paper for a non-optimal solution to the k-partite matching problem:

http://books.google.com/books?id=wqs31L1MF4IC&pg=PA309&lpg=PA309&dq=k-partite+matching&source=bl&ots=kgBuvi7ym_&sig=j3Y-nyo51y8qp0-HwToyUlkao4A&hl=de&sa=X&oi=book_result&resnum=1&ct=result

I'm sure you can find others on Google yourself now that you know the terms to search for. I don't know if there is an efficient algorithm giving the optimal solution for k=3.

Reflex

Answer 2

This is different from an extension of the stable marriage problem, since as I understand the OP's question, the people in each group do not have an ordered list of who they want to work with from most to least; it's a binary relationship (willing/not willing).

This can be formulated as an integer programming problem that can be solved quite quickly. I give the mathematical formulation of the problem below; you can use a package like glpk or AMPL/CPLEX to process the data.

Define the following matrices:

M1 = |A| x |B| matrix, where

M1(a,b) = 1 if a (given member of A) is willing to work with b (given member of B), and 0 otherwise

M2 = |A| x |C| matrix, where M2(a,c) = 1 if a (given member of A) is willing to work with c (given member of C), and 0 otherwise

M2 = |B| x |C| matrix, where

M3(b,c) = 1 if b (given member of B) is willing to work with c (given member of C), and 0 otherwise

Now define a new matrix we will use for our maximization:

X = |A| x |B| x |C| matrix, where

X(a,b,c) = 1 if we make a, b, and c work together.

Now, define our objective function:

//Maximize the number of groups

maximize Sum[(all a, all b, all c) X(a,b,c)]

subject to the following constraints:

//To ensure that nobody gets placed in two groups

For all values of a: Sum[(all j, k) X(a, j, k)] <= 1

For all values of b: Sum[(all i, k) X(i, b, k)] <= 1

For all values of c: Sum[(all i, j) X(i, j, c)] <= 1

//To ensure that all groups are composed of compatible individuals

For all a,b,c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3

Casavant

Answer 3

Just a quick note to this problem. First, it is not an example of the stable marriage problem, nor in fact an extension of it (i.e. the 3D stable matching problem). Regardless though, it is a 3D matching problem which known to be NP-hard (see Garey and Johnson). To solve such a problem in a reasonable way, it is likely that you will need to use some form of constraint, integer, or linear programming (others methods exist). Something that might be of use is the new Microsoft Solver Foundation, so check it out.

Guffaw

Answer 4

To start with, you can eliminate any facts where the two parties have disjoint lists of who they will work with in the third group. Then start a brute force, depth first search, always picking from least popular to most popular.

Alternatively, equivalent to the above elimination, form a list of all possible trios and work from that instead.

Resolvable

Answer 5

I ran into a similar problem and just wrote a script that brute-forces it... http://grouper.owoga.com/

My initial thoughts were: for a larger group that was too large to brute force, some type of genetic algorithm? Make N random swaps M times. Score each new arrangement by some 'happiness' function. Take the best few, breed, repeat.

For small groups I ended up getting better results by looping over a few groups, finding the 'best' swap (the one that produced the highest overall 'happiness' gain), making that, then repeating.

Cooney

Answer 6

May be, the following article can help you: https://en.wikipedia.org/wiki/Lattice_of_stable_matchings

In its simplest form, an instance of the stable matching problem consists of two sets of the same number of elements to be matched to each other, for instance doctors and positions at hospitals. Each element has a preference ordering on the elements of the other type: the doctors each have different preferences for which hospital they would like to work at (for instance based on which cities they would prefer to live in), and the hospitals each have preferences for which doctors they would like to work for them (for instance based on specialization or recommendations). The goal is to find a matching that is stable: no pair of a doctor and a hospital prefer each other to their assigned match. Versions of this problem are used, for instance, by the National Resident Matching Program to match American medical students to hospitals.

In general, there may be many different stable matchings. For example, suppose there are three doctors (A,B,C) and three hospitals (X,Y,Z) which have preferences of:

A: YXZ   B: ZYX   C: XZY  
X: BAC   Y: CBA   Z: ACB

There are three stable solutions to this matching arrangement:

• The doctors get their first choice and the hospitals get their third: AY, BZ, CX.
• All participants get their second choice: AX, BY, CZ.
• The hospitals get their first choice and the doctors their third: AZ, BX, CY.

The lattice of stable matchings organizes this collection of solutions, for any instance of stable matching, giving it the structure of a distributive lattice.

Zaneta