Equivalent Optimal Matchings Produced by the Priority Mechanism

The priority mechanism introduced in (Roth et al., 2005) may produce many maximal matchings depending on the structure of the compatibility graph. In this article, I show that there are two maximal matchings for some priority ordering if there is a 4-cycle in the compatibility graph. Further, if the compatibility graph induces a complete subgraph, then the number of maximal matchings for patients involved in that subgraph can be computed by evaluating a double factorial.

Model of Matching Pairs of Patients with Priorities

There are $n$ number of patients contained in the set $N=\{1, \ldots, n\}$. Pairs $i, j$ are mutually compatible if $j$ has a compatible donor for the patient of $i$ and $i$ has a compatible donor for the patient of $j$, that is, $k_j \in K_i$ and $k_i \in K_j$. A mutual compatibility matrix $R=\left[r_{i, j}\right]_{i \in N, j \in N}$ is defined as for any $i, j \in N$,

$r_{i, j}=\left\{\begin{array}{ll}1 & \text { if } i \text { and } j \text { are mutually compatible } \\ 0 & \text { otherwise }\end{array}.\right.$

A compatibility graph consisting of mutually compatible patients can be defined as $G=(N, E)$ where $E$ is the set of edges connecting mutually compatible patients.

A matching of patients $\mu$ is a set that contains pairs of mutually compatible patients that are matched with one another and patients matched with themselves. Patient $p_i \in N$ is matched with patient $p_j \in N$ in the matching $\mu$ if and only if $\mu=\left\{p_i p_j\right\}$. In this model, cycles of matched patients are not considered. Hence, it cannot be the case that $\mu=\left\{p_i p_j p_k\right\}$ for some $p_i, p_j, p_k \in N$. Note that a matching can contain multiple elements, and patients who are matched with one another are of the form $p_i p_i$ (e.g. $\mu=\left\{p_1 p_2, p_3 p_4, p_5 p_5\right\}$). A patient is matched with themselves only if he cannot be matched with any others. A priority ordering $\left(p_1, \ldots, p_n\right)$ among the patients orders each patient $p_i$ from 1 being the highest priority to $n$ being the lowest. Each patient has a distinct integer representing their priority.

As described in (Roth et al., 2005), there is a manager who is given a priority ordering $p=\left(p_1, \ldots, p_n\right)$ and wishes to find the set of exchanges that maximizes a preference relation $\succ_p$ defined over matchings. The preference relation $\succ_p$ is defined as for any matching $\mu$ and $v, \mu \succ_p v$ if and only if whenever matchings $\mu$ and $v$ differ in only one patient, the matching with the higher priority patient is preferred, and adding additional matched patients to an existing matching always results in a preferred matching. Given a priority ordering, $\mu$ is a maximal matching if $\mu \succ_p v$ for all other matchings $v$.

The goal of this article is to quantify and characterize maximal matchings. Hence, given a priority ordering $p$, matching $\mu \sim_p v$ (i.e. matching $\mu$ is equivalent to $v$) if and only if for all matchings $m \neq$ $\mu$ and $m \neq v, \mu \succ_p m$ and $v \succ_p m$. The set of maximal and equivalent matchings is contained in the equivalence class $[\mu]_p:=\left\{v\right.$ is a maximal matching $\left.\mid v \sim_p \mu\right\}$. Roth showed that the greedy algorithm in the form of the priority algorithm produces these maximal matchings. See my previous post for more details on the priority mechanism.

To understand the relationship between maximal matchings and priority orderings, I define an important concept from graph theory. A 4-cycle in the graph $G=(V, E)$ is a set of vertices $\left\{v_1, \ldots, v_4\right\} \subseteq V$ such that $v_i \neq v_j$ for all $i, j \in\{1, \ldots, 4\}$ and $\left\{v_1, v_2\right\},\left\{v_2, v_3\right\},\left\{v_3, v_4\right\}$, and $\left\{v_4, v_1\right\}$ are its edges contained in $E$.

Analysis of Maximal Matchings in the Priority Mechanism

In this section, I present the relationship between the structure of the compatibility graph and maximal matchings. The priority algorithm may produce many maximal matchings. Hence, given the structure of the compatibility graph, I provide propositions relating this structure and maximal matchings.

$\textbf{Proposition.}$
If an induced subgraph of the compatibility graph $G$ contains a 4-cycle, then there is a priority ordering $p$ such that patients in the cycle can be matched in $\mu$ and $v$ and, further, $\mu \sim_p v$.

$\textit{Proof}$. Suppose a generated subgraph of $G$ contains a 4-cycle. Let $p_1, \ldots, p_4$ be the patients in the cycle. Hence, this implies that $p_1$ is adjacent to $p_4$ and $p_2, p_i$ is adjacent to $p_{i-1}$ and $p_{i+1}$ for $i=2,3$, and $p_4$ is adjacent to $p_1$ and $p_3$. Let $p_5, \ldots, p_n$ be the other patients. Consider the priority ordering $p=\left(p_1, \ldots, p_4, p_5 \ldots, p_n\right)$. Then $\left\{p_1 p_2, p_3 p_4\right\}$ and $\left\{p_1 p_4, p_3 p_2\right\}$ will always be two optimal matchings such that $\left\{p_1 p_2, p_3 p_4\right\} \sim_p\left\{p_1 p_4, p_3 p_2\right\}$.

$\textbf{Proposition.}$
For every induced, simple, complete subgraph of the compatibility graph $G$ with $i \geq 4$ vertices, there exists a priority ordering $p$ such that for the equivalence class of maximal matchings, $[\mu]_p$,

$\left|[\mu]_p\right|=\left\{\begin{array}{c} (i-1)!!\text { if } i \text { is even } \\ (i-2)!!\text { if } i \text { is odd } \end{array}\right.$

where $n!!$ is the double factorial of $n$ (i.e. $n!!=n(n-2)(n-4) \ldots(3)(1)$ for odd $n$).

$\textit{Proof}$. Let the induced complete subgraph of the compatibility graph $G$ with $i \geq 4$ vertices be denoted as $K_i$. Since $K_i$ is complete, a maximal matching requires that $i$ patients are matched if $i$ is even and $i-1$ patients are matched if $i$ is odd. Hence, if $i$ is even, then select any priority ordering such that $q=\left(p_1, \ldots, p_i, \ldots, p_n\right)$ where $p_1, \ldots, p_i$ are the $i$ patients and $p_{i+1}, \ldots, p_n$ are the others. By the number of perfect matchings of a complete graph theorem, $\left|[\mu]_q\right|=(i-1)!!$. Similarly, if $i$ is odd, then consider the priority ordering $w=\left(p_1, \ldots, p_{i-1}, p_i, \ldots, p_n\right)$ where $p_1, \ldots, p_{i-1}$ are the $i-1$ matched patients, $p_i$ is not matched, and $p_{i+1}, \ldots, p_n$ are the others. By the same theorem, the number of perfect matchings among $p_1, \ldots, p_{i-1}$ is $\left|[\mu]_w\right|=(i-2)!!$.

References

1. Roth, A. E., Sönmez, T., & Ünver, M. U. (2005). Pairwise kidney exchange. Journal of Economic Theory, 125(2), 151–188.