Random allocation of groups of objects to agents

Question

I have a poorly specified random allocation problem, which I need help in trying to tighten the definition and consider an effective algorithm.

I have groups of objects, each group containing at least one object. For, example, the group sizes could be:

• 5,3,2,2,1,1,1,1,1,1, ; OR
• 5,3,2,2

I wish to allocate these groups of object randomly to different agents. The most important constraint is that each agent gets (within +/- 1 object) the same number of objects. The lesser constraint (fuzzier) constraint is that we should try an minimise group splitting.

Thus with the first set of groups of object (18 in total), and 3 agents; If we allocate them in descending group size - it is possible to allocate the group of 5 to one agent at random; the group of 3 can go to one of the other two agents; .... and the long tail of groups of size 1 lets the allocation be even with each agent getting 6.

With the second set of groups - 12 object in total; we need to start to do some group splitting to allow 4 object to be allocated to each of the three agents. The group of 5 could be split as 4,1.

Problems can also arise even if the largest group is smaller in size than uniform distribution would allow. Allocating the second group of (5,3,2,2) to two agents - means that each should get 6. This can be done by group splitting in a number of different ways.....

Thoughts on how to take this forward would

Answer 1

The following is a Integer Linear Programming model for your problem as i understand it. You may solve it using an IP solver.

\begin{align} \min \sum_{i,k} y_{ik} \\ \sum_i x_{ik} \le t+1 &\quad \forall k \\ \sum_i x_{ik} \ge t & \quad \forall k\\ \sum_k x_{ik} = b_i & \quad \forall i\\ b_i y_{ik} \ge x_{ik} & \quad \forall i,k\\ x_{ik} \in \mathbb{N} & \quad \forall i,k\\ y_{ik} \in \{0,1\}& \quad \forall i,k \end{align}

In this model:

• $b_i$ is the size of group $i$
• index $k$ is for agents
• $x_{ik}$ is equal to the number of objects from group $i$ assigned to $k$
• $y_{ik}$ is equal to one iff at least one object of group $i$ is assigned to $k$
• $t$ is the number of objects for each agent + or - 1. Note that it can be precomputed.

For each group $i$, $\sum_{k} y_{ik}$ is equal to the number of different agents whom an object of $i$ is assigned. If no group is split, then $\sum_{i,k} y_{ik}$ equals the number of groups.

You may also view the problem as a Fixed-charge Network Flow problem (http://www.sciencedirect.com/science/article/pii/S0167637799000048#) in a bipartite graph (http://link.springer.com/chapter/10.1007%2F978-3-642-20807-2_33): the network structure is:

• one source node for each group
• one sink node for each agent
• one arc from each source to each sink
• no unitary cost
• fixed cost on each arc is 1.

Edit: Note that the problem is NP-hard. This can be proved by reduction from 2-partition to the special case with 2 agents.