Given a set of men and a set of women, an element of each set is given a total preference order over the other. We would like to match elements of these sets together, in a way such that no two people prefer each other to their assigned partner. We can represent our initial problem instance as a grid-like digraph, and reduce this digraph to a unique, smaller one, without losing any pertinent information.

I will present this representation, its reduction, and some of its properties.

The presentation is based on the paper “Of Stable Marriages and Graphs, and Strategy and Polytopes” by M. Balinski and G. Ratier.