A Course on Cooperative Game Theory

Let G = (U, V, E) be a bipartite graph with |U| = |V| = n and the edges in E have one end-point in U and the other end-point in V. A matching μ in G is a set of vertex disjoint edges, i.e., μ is a set of edges such that no two edges are co-incident on the same vertex. Since the edges in a matching have to be vertex disjoint, no matching can have more than n edges. A perfect matching is a matching containing n edges. There are well-known algorithms to find a perfect matching (if one exists).

In this section, we will address a different matching problem. An instance still consists of two sets U and V, but, the constraints are different. Let U = {u1, …, un} and V = {v1, …, vn}. Let π1, …, πn be permutations of the set V and let σ1, …, σn be permutations of the set U. The problem instance is given by the following relations. For 1 ≤ i ≤ n and 1 ≤ j ≤ n,

ui ↦ πi; vj ↦ σj.

The permutation πi is a linear ordering of the vertices in V and similarly, the permutation σj is a linear ordering of the vertices in U. Consider the vertices in U to represent n distinct men and the vertices in V to represent n distinct women. The permutation πi represents the ranking of the n women by the man ui; similarly, the permutation σj represents the ranking of the n men by the woman vj.

A matching μ is a pairing of a man and a woman and can be thought of as a marriage. Let the partner of the man ui be denoted by μ(ui) and the partner of woman vj be denoted by μ(vj). Suppose there is a man ui and a woman vj such that πi(vj) precedes πi(μ(ui)) and σj(ui) precedes σj(μ(vj)).