Markets

The Matching Problem

In this part of the course, we will see how the network structure (studied in the Graphs part) and strategic interaction (studied in the Games part) can be combined to represent more complex real world aspects like, for example, markets.

A market is a space that provides opportunities for interactions between buyers and sellers. A network model can be used to encode access between buyers and sellers in a common market.

Bipartite Graphs and the Matching Problem

Example. For their final year projects, students need to be matched up with project supervisors. For simplicity, we assume that there are as many supervisors as there are students. Each student gets one supervisor and each supervisor gets one student. To start the process of pairing up students with supervisors, each student selects 4 preferred supervisors. The project organizers then strive to find a matching where each student gets assigned one of their preferred supervisors.

This setup can be described as a bipartite graph, that is a graph with vertex set $X \cup Y$, where $X$ is the set of students and $Y$ the set of supervisors, and each edge in the graph has one of its endpoints in $X$ and the other endpoint in $Y$.

The problem then is to find a perfect matching, that is a subset of the edges in the graph so that each node in $X \cup Y$ is involved in exactly one edge. (Of course this is only possible if the two sets have the same size, $|X| = |Y|$. A perfect matching in a bipartite graph effectively describes an explicit bijection between $X$ and $Y$.)

Example. A domino tiling of a region in the Euclidean plane is a tesselation of that region by $1 \times 2$ rectangles called dominoes.

When adjacency of $1 \times 1$ square is modelled as a (bipartite!) graph, the existence of a domino tiling is a matching problem. A particular instance of such a problem is the domino tiling of an Aztec diamond, which relates to many interesting problems in Combinatorics …

Can you tile the following region with dominoes?

chess

The bipartite graph

matching0

has a perfect matching, as indicated by the fat blue edges.

The graph

matching1

has no perfect matching, as the set $S = \{v, w, x\}$ is constricted, i.e., $|S| > |N(S)|$, where $N(S)$ is the set of neighbours (or friends) of all the nodes in $S$.

It turns out that constricted sets are the only obstruction to having a perfect matching.

The Matching Theorem

Matching Theorem (Hall, König 1935) If a bipartite graph $G = (X \cup Y, E)$ with $|X| = |Y|$ has no perfect matching then it contains a constricted set.

In other words, a bipartite graph on two equipotent sets $X$ and $Y$ either has a perfect matching or contains a constricted set.

A constructive procedure that produces from a bipartite graph either a perfect matching or a constricted set would prove the Matching Theorem.

For this, a matching (not necessarily perfect) in a bipartite graph is a subset of the edges involving each node at most once.

Proof. The central idea of this proof is that a matching can be enlarged along an alternating path with unmatched endpoints by swapping matching and nonmatching edges.

matching2

Here, an alternating path in a bipartite graph with a matching is a simple path that alternates between matching and nonmatching edges. An alternating path whose endpoints are both unmatched is called an augmenting path.

Clearly, if there is an augmenting path, then removing the matching edges on this path from the current matching, and instead adding the nonmatching edges on the path to the matching, will enlarge the matching by one more edge.

matching3

How to find an augmenting path? By alternating BFS (Breadth First Search).

Starting with an unmatched node $x \in X$, add nodes that can be reached from $x$ layer by layer, in such a way that nonmatching edges alternate with matching edges. As the graph is bipartite, the layers will alternatingly consist of nodes from $X$ and nodes from $Y$. The edges from an $X$-layer to the next $Y$-layer will be nonmatching, while the edges from a $Y$-layer to the next $X$-layer will be matching.

matching4

If this process produces an unmatched node (in an $X$-layer) then it exhibits an augmenting path.

matching5

If the process fails to produce an unmatched node then the resulting alternating BFS-tree has the property that the matching edges establish bijections between all the $Y$-layers and all the $X$-layers except for the $X$-layer $0$ containing the initial unmatched node. Hence, overall, there is one more $X$-node in the tree than there are $Y$-nodes.

matching6

Moreover, by construction, every neighbour of every $X$-node is contained in (a $Y$-layer of) the tree.

It follows that the $X$-nodes in the tree form a constricted set.

In this way, alternating BFS provides an algorithm that, given any bipartite graph, either produces a perfect matching, or exhibits a constricted set. This completes the proof of the Matching Theorem.

Maximal Matchings

When the above algorithm stops with the detection of a constricted set, we know that there is no perfect matching. But one may ask whether the matching constructed so far is maximal in size. A moment’s reflection shows that a matching in a bipartite graph is only maximal, if alternating BFS applied to any unmatched node does not yield an augmenting path. To actually check this might be a lot of work.

A variant of the above algorithm, which instead of a single unmatched node uses all unmatched nodes in $X$ as its layer $0$, can be used to grow a maximal matching more efficiently.