Matching plus Allocation

Suppose we are given red balls and black balls. All of these balls are labeled with a real number. For example

We now pair red balls with black balls. There are such matchings, as illustrated below

Additionally, suppose that a pair composed of a red ball with label and a black ball with label can be exchanged for a white ball with label . For example

Since there are matchings, in general there will be collections of white balls, as depicted below

Note that the sum of the labels of the white balls is always , regardless of the matching. This is due to the fact that addition is commutative and associative. Note also that the resulting collections of white balls are not necessarily distinct.

Suppose now that we would like to allocate the white balls to bowls such that the sum of the labels of the white balls in each bowl is 50% of the total sum of the labels of the white balls. Pictorially, we have

and, since the sum of the labels of the white balls in each bowl is exactly , the allocation is feasible. Nonetheless, this allocation is not unique: we could also have allocated ball with label 3 to bowl 1 and balls with labels 1 and 2 to bowl 2. If we wanted to allocate 1/3 of the total to bowl 1 and 2/3 of the total to bowl 2, we could have allocated ball with label 2 to bowl 1, and balls with labels 1 and 3 to bowl 2, for instance. This allocation would also be feasible.

However, not all desired allocations are feasible. For example, suppose that we want to allocate 90% to bowl 1 and 10% to bowl 2. This allocation is unfeasible. We can allocate a total of 5 to bowl 1 and 1 to bowl 2, which corresponds to 83.3% and 16.7% instead of 90% and 10%.

Though we cannot attain the desired allocation exactly, we are able to get relatively “close” to it. We could use, for instance, a quadratic criterion to measure how “far” a particular allocation is from the desired one.

In each bowl we are attempting to reconstruct a given real number from a finite collection of real numbers. Hence, the unfeasibility of a desired allocation stems from the “chunkiness” of the “parts” we have at our disposal. But here is the interesting aspect of this problem: we can change the “parts” (i.e., the white balls) by matching the red and black balls in a different way. Therefore, allocation can not be “decoupled” from matching, so to say. The two operations are now intertwined. When performing the matching, we should strive to build a good collection of white balls so that the actual allocation is as “close” as possible to the desired one.

If we have red balls and black balls, then there are matchings. Each red-black pair is then allocated to one of bowls. Hence, our search space has points, and an exhaustive search will run in time which is intractable for “large” values of . For example, if and , the search space has over billion points! Yet once again, we are doomed by the curse of combinatorial explosion.

Our challenge (and only hope) is to design a heuristic-based algorithm which, although not optimal, is “good enough” most of the time. Any ideas?

This problem seems to have some of the ingredients of many classical problems such as integer partitions, knapsack, and bipartite / tripartite matching. It is not difficult to formulate the problem as a constrained quadratic binary optimization problem, but solving it is hard.

Tags: Combinatorial Optimization, Recreational Mathematics