## 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?

The bipartite graph

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

The graph

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**.

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.

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.

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

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.

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.