Can features overlap?

Yes; overlapping subsets are central to the problem.

Does the objective require equal group sizes?

Not by itself; specify that requirement separately.

Can there be several optimal allocations?

Yes; this example has multiple labeled allocations achieving discrepancy one.

AI Glossary / Statistics and probability / Advanced

Set balancing

Definition

Set balancing is the problem of dividing a collection of items into two groups so that specified features are distributed as evenly as possible. In a common binary formulation, each feature identifies a subset of the items, and the objective is to minimize the largest difference between the two groups' counts for any listed feature.

What it means

Equal group sizes do not necessarily imply similar composition. Two groups can each contain the same number of items while one contains most of the items with a particular feature. Set balancing considers several potentially overlapping feature subsets at once.

The chosen features define what balance means. Balancing recorded attributes does not guarantee balance on unrecorded attributes, interactions or outcomes. The method solves a specified allocation problem; it does not automatically provide the randomization, representativeness or causal interpretation required by an experiment.

How it works

Represent the data with a binary matrix A: rows are features and columns are items. An entry is one when the item has the feature and zero otherwise. Represent an allocation by a vector b whose entries are +1 for one group and -1 for the other.

The product Ab gives the signed count difference for each feature. A common objective minimizes the largest absolute entry of Ab, written ||Ab|| infinity. Positive and negative discrepancies must not cancel when assessing the worst imbalance.

State any additional constraints explicitly. Exact equality of group sizes is a separate constraint; adding an all-ones feature also lets the objective account for size imbalance, without necessarily forcing it to zero. Random allocations provide one approach, while more sophisticated algorithms seek stronger or more efficient guarantees.

Three practical examples

1. Evaluation allocation: divide a set of documents between two review teams while limiting differences in listed document categories.

2. Experiment planning: assess whether proposed groups have similar counts of relevant baseline characteristics, while preserving the requirements of the experimental allocation design.

3. Work scheduling: partition tasks between two teams while balancing several overlapping task labels. If task durations matter, include an appropriate workload measure rather than assuming category counts capture effort.

Think of it this way

Think of splitting a mixed collection of cards into two piles. Equal pile heights do not ensure equal numbers of red cards, picture cards and cards from each suit. Some cards belong to several categories, so moving one card can improve one comparison while worsening another.

Worked example

Consider six fictional documents numbered 1-6. The team wants two groups of three documents each. It tracks three binary features:

Feature F1 applies to documents 1, 2 and 3.

Feature F2 applies to documents 1, 4 and 5.

Feature F3 applies to documents 2, 4 and 6.

The features overlap. The corresponding matrix rows are [1,1,1,0,0,0], [1,0,0,1,1,0] and [0,1,0,1,0,1].

First allocate documents {1,2,3} to group T and {4,5,6} to group C. Both groups have three documents, but F1 occurs three times in T and zero times in C. Its signed discrepancy is 3 - 0 = 3.

F2 occurs once in T and twice in C, giving 1 - 2 = -1. F3 also occurs once in T and twice in C, giving -1. The discrepancy vector is therefore [3,-1,-1], and its largest absolute entry is 3. Adding the entries to obtain 1 would conceal the large F1 imbalance and would not compute the stated objective.

Now allocate {1,2,4} to T and {3,5,6} to C. F1 occurs twice in T and once in C. The same is true for F2 and F3. The discrepancy vector becomes [1,1,1], so the largest absolute discrepancy is 1.

This second allocation is optimal for the stated objective and constraints. Each feature occurs in exactly three documents overall. An odd total cannot be divided equally between two groups, so every feature's absolute count difference must be at least one. The proposed allocation attains that lower bound simultaneously for all three features.

There are 20 possible choices of three documents for labeled group T, with C taking the complement. Exhaustively checking those 20 choices confirms that the minimum objective value is one and that 14 choices attain it. Swapping T and C reverses discrepancy signs but preserves absolute discrepancies, so label-swapped allocations appear separately in this count.

An optimal allocation need not be unique.

All documents and features are invented. The example proves optimality only for this six-item problem through the odd-count lower bound and an attaining allocation. It makes no claim that the same procedure finds an optimum efficiently for every larger instance.

Illustrative case study

Fictional Cedar Review splits a document set into two equal batches and assumes that the batches are comparable. Its analyst checks the feature counts and finds the first allocation's discrepancy of three.

Cedar switches to an allocation with discrepancy one under the chosen criterion. It then reviews whether length and difficulty also need representation before comparing team performance. This invented case illustrates why a mathematically optimal balance can still be incomplete for an operational question.

Common misconceptions and mistakes

"Equal-sized groups are automatically balanced." Their feature counts can differ substantially.

"Positive and negative discrepancies cancel." The maximum-absolute-discrepancy objective evaluates each feature separately.

"Perfect balance is always possible." Odd feature totals already rule it out in the example.

"Balanced recorded features establish a causal comparison." Study design and unrecorded influences still matter.

Business use

Choose features and the imbalance criterion before judging allocations. Explain whether the target concerns counts, proportions, total workload or another quantity. For binary counts, remember that a one-item difference can matter differently for a rare feature and a common one.

For AI-assisted allocation, ask for the feature matrix, constraints and achieved discrepancies. Check feasibility separately from claims of optimality. If the allocation supports an experiment, use an appropriate randomization and analysis plan rather than treating deterministic feature balance as a substitute for that design.

Check your understanding

Why is the first allocation's objective three?

Answer: F1 has the largest absolute count difference.

Why can no allocation achieve zero here?

Answer: Each feature has an odd total of three.

What changes when the group labels are swapped?

Answer: Discrepancy signs reverse, but the objective stays unchanged.

Related terms

Partition
Constrained optimization
Discrepancy
incidence matrix
randomized algorithm
feature balance
experimental design
allocation

Learn next

Add a feature present only in documents 1 and 2. Evaluate its discrepancy under the second allocation, then examine whether another equal-sized allocation improves the new worst-feature discrepancy.

Sources

Elias Koutsoupias, Probability and Computing, Oxford course notes, Lecture 9: Set Balancing: https://www.cs.ox.ac.uk/people/elias.koutsoupias/pc2018-19/lectures.html

Mohsen Ghaffari and Christoph Grunau, Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping, author abstract: https://arxiv.org/abs/2311.13771

Previous: Set Next: Set-cover problem