Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement

Abstract

Fully pairing all elements of a set while attempting to maximize the total benefit is a combinatorically difficult problem. Such pairing problems naturally appear in various situations in science, technology, economics, and other fields. In our previous study, we proposed an efficient method to infer the underlying compatibilities among the entities, under the constraint that only the total compatibility is observable. Furthermore, by transforming the pairing problem into a traveling salesman problem with a multi-layer architecture, a pairing optimization algorithm was successfully demonstrated to derive a high-total-compatibility pairing. However, there is substantial room for further performance enhancement by further exploiting the underlying mathematical properties. In this study, we prove the existence of algebraic structures in the pairing problem. We transform the initially estimated compatibility information into an equivalent form where the variance of the individual compatibilities is minimized. We then demonstrate that the total compatibility obtained when using the heuristic pairing algorithm on the transformed problem is significantly higher compared to the previous method. With this improved perspective on the pairing problem using fundamental mathematical properties, we can contribute to practical applications such as wireless communications beyond 5G, where efficient pairing is of critical importance. As the pairing problem is a special case of the maximum weighted matching problem, our findings may also have implications for other algorithms on fully connected graphs.

1. Introduction

The procedure of generating pairs of elements among all entries of a given system often arises in various situations in science, technology, and economy [1,2,3,4,5,6,7]. Here, we call such a process pairing, and the number of elements is considered to be an even number for simplicity. One immediately obvious problem is that the number of pairing configurations grows rapidly with the number of elements. The number of possible pairings is given by $(n-1)!!$, where n indicates the number of elements in the system and $!!$ is the double factorial operator. For example, when n is 100, the total number of possible pairings is on the order of ${10}^{78}$. Hence, finding the pairing that maximizes the benefit of the total system is difficult.

Notably, the pairing problem corresponds to the maximum weighted matching (MWM) problem on the complete graph. Multiple algorithms exist for solving the MWM problem [8,9,10,11,12,13,14,15]. In contrast to these conventional methods, we propose a heuristic and fast algorithm at the cost of some performance. The advantage of a fast heuristic algorithm is that it can be useful in environments where weights change dynamically or a quick pairing is required, such as in communications technology. A heuristic algorithm for the MWM problem using deep reinforcement learning was recently proposed by [16] with a similar goal. Furthermore, our research proposes algorithms that work under the limited observation constraint, which is explained later. In our previous study, we proposed an algorithm with a computational complexity of $\mathcal{O}\left(n^2\right)$ [17].

To the best of our knowledge, there is no exact algorithm that works on the order of $\mathcal{O}\left(n^2\right)$ for arbitrary weights. For example, Gabow [9] proposed a MWM algorithm with a computation time of $\left|E\right|\left|V\right|+{\left|V\right|}^{2}log\left|V\right|$, where V is a set of vertices and E is a set of edges. However, randomized or approximate algorithms can reduce computational time for some cases. For example, Cygan et al. [12] developed a randomized algorithm with a computation time of ${L\left|V\right|}^{\omega }$ for graphs with integer weights ($\omega <2.373$ is the exponent of $n\times n$ matrix multiplication [18] and L is the maximum integer edge weight). Duan et al. [15] proposed an approximate algorithm achieving an approximation ratio of $(1-ϵ)M$ with a computation time of $\left|E\right|{ϵ}^{-1}log{ϵ}^{-1}$ for arbitrary weights and $\left|E\right|{ϵ}^{-1}logN$ for integer weights ($ϵ$ is a positive arbitrary value and M is the maximum possible weight matching value). Here, $\left|V\right|=n,\left|E\right|=n(n-1)/2$. Here, we aim to improve our previous pairing problem result, i.e., to determine a higher-accuracy heuristic algorithm that works with $\mathcal{O}\left(n^2\right)$ computational complexity.

Note that the pairing problem should not be confused with the assignment problem, which is another special case of the MWM setting. The assignment problem requires the graph to be a weighted bipartite graph. Furthermore, in the assignment problem there are two classes of objects, where it is the goal to always match an object from the first class with an object from the second. However, in the pairing problem, there is only a single class of objects, and we allow any of them to be potentially paired with any other. The assignment problem is also related to the single-source shortest paths problem. Several well-known assignment algorithms [19,20,21] or single-source shortest paths algorithms [22] are known. For example, the Hungarian algorithm [19] solves the assignment problem $\mathcal{O}\left(n^3\right)$, the auction algorithm [20] works with parallelism and the Bellman–Ford algorithm runs with $\mathcal{O}\left(\right|V\left|\right|E\left|\right)$ [22]. However, in this study, we consider a fully connected graph with an even number of elements, where the MWM problem cannot be solved by assignment problem algorithms.

An example of a pairing problem is found in a recent communication technology called non-orthogonal multiple access (NOMA) [23,24,25,26,27,28,29]. In NOMA, multiple terminals simultaneously share a common frequency band to improve the efficiency of frequency usage. The simultaneous use of the same frequency band causes interference in the signals from the base station to each terminal. To overcome this problem, NOMA uses a signal processing method called successive interference cancellation (SIC) [30] to distinguish individual channel information in the power domain, allowing multiple terminals to rely on the same frequency band. For simplicity, here we consider that the number of terminals that can share a frequency is given by two. Herein, the usefulness of the whole system can be measured by the total communication quality, such as high data throughput and low error rate, which depends crucially on the method of pairing.

The most fundamental parameter of the pairing problem is the merit between any two given elements, which we call individual compatibility, while the summation of compatibilities for a given pairing is called its total compatibility. The detailed definition is introduced below. Our goal is to derive pairings yielding high total compatibility.

In general, we do not need to assume that the individual compatibility of a pair is observable, i.e., only the total compatibility of a given pairing may be observed. Our previous study [17] divided the pairing problem into two phases. The first is the observation phase, where we observe total compatibilities for several pairings and estimate the individual compatibilities. The second is the combining phase, in which a search is performed for a pairing that provides high total compatibility. This procedure is referred to as pairing optimization. The search is based on the compatibility information obtained in the first phase. In [17], we show that the pairing optimization problem can be transformed into a travelling salesman problem (TSP) [31] with a three-layer structure, allowing us to benefit from a variety of known heuristics.

However, we consider that there is substantial room for further performance optimization. This study sheds new light on the pairing problem from two perspectives. The first is to clarify the algebraic structure of the pairing optimization problem. Because we care only about the total compatibility when all elements are paired, there are many compatibility matrices (defined in Section 2) that share the same total compatibilities. In other words, we can consider an equivalence class of compatibility matrices that yield the same total compatibilities and that cannot be distinguished if individual compatibilities are not measurable. We show that the compatibility matrices in each equivalence class have an invariant value.

Second, although any compatibility matrices in the same equivalence class theoretically provide the same total compatibility, the heuristic pairing optimization process can result in different total compatibility values. These differences are not caused by incomplete or noisy observations, but are due to the convergence properties of the heuristic pairing algorithms, which yield better results on some distributions than others. We examine how the statistics of the compatibility matrix affect the pairing optimization problem and propose a compatibility matrix that yields higher total compatibility after optimization. More specifically, we propose a transformation to the compatibility matrix that minimizes the variance of the elements therein, which we call the variance optimization. We confirmed numerically that enhanced total compatibility is achieved via the compatibility matrix after variance optimization. Furthermore, the proposed variance optimization algorithm may also be applicable when no observation phase is required, i.e., when the individual compatibilities are directly observable. In other words, there are cases where a compatibility matrix unsuitable for a heuristic combining algorithm can be converted to one that is easily combinable.

The remainder of this paper is organized as follows. In Section 2, we define the pairing optimization problem mathematically. Section 3 describes the mathematical properties of the equivalence class. Section 4 explains the concept of variance optimization and presents a solution by which it can be achieved. Section 5 presents results of numerical simulations of the proposed variance optimization. Furthermore, there are two optimization problems in this paper. The first is the pairing problem we aim to solve in Section 2.1. Second is the variance optimization which enables us to enhance the performance of the PNN+p2-opt algorithm in Section 4.2. Finally, Section 6 concludes the paper.

2. Problem Setting

In this section, we provide a mathematical definition of the pairing optimization problem that we address in this study, and define some of the mathematical symbols used in the following discussion. In addition, we explain the constraints applied to the pairing optimization problem.

2.1. Pairing Optimization Problem

Here, we assume that the number of elements is an even natural integer n, while the index of each element is a natural number between 1 and n. Parts of the pairing problem can be described elegantly in set theory, while others benefit from using matrix representations. We will use either, where appropriate. Here we use $\mathbb{U}\left(n\right)$ to denote the set of n elements:

$$\begin{array}{c}\hfill \mathbb{U}\left(n\right)\equiv \{i\mid i\in \mathbb{Z},1\le i\le n\}.\end{array}$$

(1)

Then, we define the set of all possible pairs for $\mathbb{U}\left(n\right)$ as $\mathbb{P}\left(n\right)$, which contains $N(N-1)/2$ pairs:

$$\begin{array}{c}\hfill \mathbb{P}\left(n\right)\equiv \left\{\right\{i,j\}\mid i,j\in \mathbb{U}(n),i<j\}.\end{array}$$

(2)

To describe the compatibilities of these pairs, we now define a “compatibility matrix’’ C as follows:

$$\begin{array}{ccc}& & C\in {\mathbb{R}}^{n\times n},\hfill \\ & & \forall \{i,j\}\in \mathbb{P}\left(n\right),C_{i,j}=C_{j,i},\hfill \\ & & 1\le i\le n,C_{i,i}=0.\hfill \end{array}$$

The compatibility between elements i and j is denoted by $C_{i,j}\in \mathbb{R}$. The matrix C is always symmetric and the major diagonal is zero, because pairing i and j does not depend on the order of elements and an element cannot be paired with itself. The set of all possible compatibility matrices is denoted as ${\mathrm{\Omega }}_n$ when the number of elements is n. In other words, ${\mathrm{\Omega }}_n$ is the set of all $n\times n$ symmetric distance matrices, or symmetric hollow matrices. To describe a pairing, i.e., which elements are paired together, we now define a pairing matrix $S\in {\mathbb{R}}^{n\times n}$:

$$\begin{array}{ccc}& & \forall \{i,j\}\in \mathbb{P}\left(n\right),S_{i,j}=S_{j,i}\mathrm{and}{S}_{i,j}\in \{0,1\},\hfill \\ & & 1\le i\le n,S_{i,i}=0,\hfill \\ & & \forall i,\sum _{j=1}^n{S}_{i,j}=1.\hfill \end{array}$$

S is symmetric, because pairing element i with j is equivalent to pairing j with i. The pairing matrix S is also hollow, because pairing i with itself is not allowed. Each row and column contains only a single non-zero element, as each element i can only be paired once. Therefore, a pairing matrix S is an $n\times n$ symmetric and hollow permutation matrix. We define the set of all pairing matrices $\mathbb{S}\left(n\right)\equiv \left\{S\right\}$ when the number of elements is n:

$$\begin{array}{c}\hfill S\in \mathbb{S}\left(n\right).\end{array}$$

(3)

To derive the set representation of a pairing, we introduce the map $f_{\mathrm{set}}$ as follows:

$$\begin{array}{c}\hfill f_{\mathrm{set}}\left(S\right)\equiv \{\{i,j\}\mid i<j\mathrm{and}{S}_{i,j}=1\}.\end{array}$$

(4)

A function denoted by $\langle X,C\rangle$ is then defined as follows, using the Frobenius inner product ${\langle ·\rangle }_{\mathrm{F}}$:

$$\begin{array}{ccc}& & C\in {\mathrm{\Omega }}_n,\hfill \\ & & X\in {\mathbb{R}}^{n\times n},\hfill \\ & & \langle X,C\rangle =\frac{1}{2}{\langle X,C\rangle }_{\mathrm{F}}.\hfill \end{array}$$

For a given compatibility matrix C, we call $\langle S,C\rangle$ for $S\in \mathbb{S}\left(n\right)$ the “total compatibility’’ for pairing S. This formulation is equivalent to the one used in our previous work [17], and corresponds to summing the individual compatibilities $C_{i,j}$ of the pairs defined by S:

$$\begin{array}{ccc}& & \langle S,C\rangle =\sum _{\{i,j\}\in f_{\mathrm{set}}\left(S\right)}{C}_{i,j}.\hfill \end{array}$$

For any given compatibility matrix C, the pairing optimization problem can then be formulated as follows:

$$\begin{array}{ccc}& & \max :\langle S,C\rangle ,\hfill \\ & & \mathrm{subject}\mathrm{to}:S\in \mathbb{S}\left(n\right).\hfill \end{array}$$

2.2. Limited Observation Constraint

As briefly mentioned in Section 1, in practice there may often exist one more constraint on the pairing optimization problem. We will assume that initially we do not know each compatibility value. Moreover, we assume that only the value of total compatibility $\langle S,C\rangle$ for any pairing $S\in \mathbb{S}\left(n\right)$ is observable. We call this condition the “limited observation constraint’’.

Under this constraint, we must execute two phases, the “observation phase’’ and the “combining phase’’, as introduced in our previous study [17]. First, we estimate the ground-truth compatibility matrix $C^g$ through observations of the total compatibilities of several pairings in the observation phase. We denote the estimated compatibility matrix by $C^e$. Our previous work [17] calculated the minimum number of observations that are necessary for deducing $C^e$ and presents a simple algorithm for doing so efficiently.

3. Mathematical Properties of the Pairing Problem

In this section, we consider algebraic structures in the pairing problem. An equivalence relation is defined among compatibility matrices to construct equivalence classes. Then we show a conserved quantity within the equivalence class and that all members of the class yield the same total compatibility for any given pairing. Furthermore, the statistical properties of compatibility matrices are examined, forming the mathematical foundation of the variance optimization to be discussed in Section 4.

3.1. Adjacent Set

We define the adjacent set matrix $R_i(1\le i\le n)$ as follows:

$$\begin{array}{ccc}& & R_i\in {\mathbb{R}}^{n\times n},\hfill \\ & & {\left(R_i\right)}_{k,l}=\left\{\begin{array}{c}1\mathrm{if}i\in \{k,l\}\mathrm{and}k\ne l\hfill \\ 0\mathrm{otherwise}.\hfill \end{array}\right.\hfill \end{array}$$

(5)

We can also describe $f_{\mathrm{set}}\left(R_i\right)$ as follows:

$$\begin{array}{c}\hfill f_{\mathrm{set}}\left(R_i\right)=\left\{\{i,j\}\mid 1\le j\le n,j\ne i\right\}.\end{array}$$

(6)

With these adjacent sets, the following theorem holds.

Theorem 1.

$C\in {\mathrm{\Omega }}_n$ is fully determined by $\{\langle S,C\rangle \mid S\in \mathbb{S}(n\left)\right\}$ and $\{\langle R_i,C\rangle \mid 1\le i\le n-1\}$.

Note that $\langle R_n,C\rangle$ is not included, i.e., only $n-1$ terms involving $R_i$ are needed. Here, we have chosen to exclude index n without loss of generality.

Proof of Theorem 1.

Our strategy to prove this involves calculating the dimension of the involved subspaces. First, we prove the equation

$$\begin{array}{c}\hfill \mathrm{span}{\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}\cap \mathrm{span}{\left\{R_i\right\}}_{1\le i\le n-1}=\left\{O_n\right\}\end{array}$$

(7)

where $O_n$ denotes the $n\times n$ zero matrix. Then, we focus on the following equation to check linear independence. Here, we number all pairings such as $S_1,S_2,\cdots S_u\cdots S_{(N-1)!!}$. We introduce the coefficients $a_u$ and $b_v$ and calculate the overlap of the spans:

$$\begin{array}{ccc}& & 1\le u\le (n-1)!!,a_u\in \mathbb{R},\hfill \\ & & 1\le v\le n-1,b_v\in \mathbb{R},\hfill \\ & & \sum _{u=1}^{(n-1)!!}{a}_u{S}_u=\sum _{v=1}^{n-1}{b}_v{R}_v.\hfill \end{array}$$

(8)

We focus on the summation of the kth-column on both sides. Note that for every $S_u$ there is exactly one non-zero element in column k, while for $R_v$ there may be more than one if $v=k$ and $1\le k\le n-1$, or exactly one non-zero element otherwise. Then, the following equations hold:

When $1\le k\le n-1$

$$\begin{array}{c}\hfill (n-2)b_k+\sum _{l=1}^{n-1}{b}_l-\sum _{l=1}^{(n-1)!!}{a}_l=0.\end{array}$$

(9)

When $k=n$ (because of our choice in formulating Theorem 1)

$$\begin{array}{c}\hfill \sum _{l=1}^{n-1}{b}_l-\sum _{l=1}^{(n-1)!!}{a}_l=0.\end{array}$$

(10)

With Equations (9) and (10), $b_k=0(1\le k\le n-1)$ holds. This means that

$$\begin{array}{ccc}& & \mathrm{span}{\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}\cap \mathrm{span}{\left\{R_i\right\}}_{1\le i\le n-1}=\left\{O_n\right\},\hfill \end{array}$$

(11)

$$\begin{array}{ccc}& & \dim \mathrm{span}{\left\{R_i\right\}}_{1\le i\le n-1}=n-1.\hfill \end{array}$$

(12)

By our previous study [17],

$$\begin{array}{c}\hfill \dim \mathrm{span}{\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}=L_{\min }\left(n\right).\end{array}$$

(13)

Here, we denote $L_{\min }\left(n\right)\equiv (n-1)(n-2)/2$. By Equations (12) and (13), the following equation holds:

$$\begin{array}{c}\hfill \dim \mathrm{span}{\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}+\dim \mathrm{span}{\left\{R_i\right\}}_{1\le i\le n-1}=\dim {\mathrm{\Omega }}_n.\end{array}$$

(14)

Therefore, by Equations (11) and (14),

$$\begin{array}{c}\hfill \dim \mathrm{span}{\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}\cup \mathrm{span}{\left\{R_i\right\}}_{1\le i\le n-1}=\dim {\mathrm{\Omega }}_n.\end{array}$$

(15)

The pairing matrices S are a subset of ${\mathrm{\Omega }}_n$. In addition, the adjacent set matrices $R_i$ are also a subset of ${\mathrm{\Omega }}_n$. Therefore, the following equation holds:

$$\begin{array}{c}\hfill \mathrm{span}{\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}\cup \mathrm{span}{\left\{R_i\right\}}_{1\le i\le n-1}\subseteq {\mathrm{\Omega }}_n.\end{array}$$

(16)

With Equations (15) and (16),

$$\begin{array}{c}\hfill \mathrm{span}{\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}\cup \mathrm{span}{\left\{R_i\right\}}_{1\le i\le n-1}={\mathrm{\Omega }}_n.\end{array}$$

(17)

That is, ${\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}$ plus ${\left\{R_i\right\}}_{1\le i\le n-1}$ can construct ${\mathrm{\Omega }}_n$. Finally, $\langle S,C\rangle$ is a linear transformation of S which comes from the property of the Frobenius inner product. Therefore, $C\in {\mathrm{\Omega }}_n$ can be constructed as a linear combination of $\{\langle S,C\rangle \mid S\in \mathbb{S}(n\left)\right\}$ and $\{\langle R_i,C\rangle \mid 1\le i\le n-1\}$. Therefore, the theorem holds. □

Corollary 1.

$$\begin{array}{ccc}& & A,B\in {\mathrm{\Omega }}_n,\hfill \\ & & A=Bif and only if\hfill \\ & & \forall S\in \mathbb{S}\left(n\right),\hfill \\ & & \langle S,A\rangle =\langle S,B\rangle and1\le i\le n,\langle R_i,A\rangle =\langle R_i,B\rangle .\hfill \end{array}$$

(18)

This corollary is a special case of Theorem 1 because Equation (18) means that A and B have the same total compatibilities for all pairings and all adjacent sets.

Here, we present an example for Theorem 1 for the $n=4$ case to illustrate the relationship of the involved subspaces. We define the following $H_i$:

$$\begin{array}{c}\hfill H_i=\left\{\begin{array}{c}\mathrm{span}{\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}\mathrm{if}i=0,\hfill \\ \mathrm{span}\left\{R_i\right\}\mathrm{if}1\le i\le n-1.\hfill \end{array}\right.\end{array}$$

(19)

We represent $H_i$ as follows, where $D_{i,j}\in {\mathrm{\Omega }}_n$ is defined as the $n\times n$ matrix whose $(i,j)$th element is 1 and all other elements are 0:

$$\begin{array}{ccc}& & H_i=\left\{\begin{array}{c}\mathrm{if}i=0,\hfill \\ \{k_1(D_{1,2}+D_{3,4})+k_2(D_{1,3}+D_{2,4})+k_3(D_{1,4}+D_{2,3})\mid k_1,k_2,k_3\in \mathbb{R}\}\hfill \\ \mathrm{if}i=1,\hfill \\ \{k_4(D_{1,2}+D_{1,3}+D_{1,4})\mid k_4\in \mathbb{R}\}\hfill \\ \mathrm{if}i=2,\hfill \\ \{k_5(D_{2,1}+D_{2,3}+D_{2,4})\mid k_5\in \mathbb{R}\}\hfill \\ \mathrm{if}i=3,\hfill \\ \{k_6(D_{3,1}+D_{3,2}+D_{3,4})\mid k_6\in \mathbb{R}\},\hfill \end{array}\right.\hfill \end{array}$$

(20)

$$\begin{array}{ccc}& & \overline{H}=\{l_{i,j}{D}_{i,j}\mid 1\le i<j\le n,l_{i,j}\in \mathbb{R}\}.\hfill \end{array}$$

(21)

The image of these spaces is represented in Figure 1. That is,

$$\begin{array}{ccc}& & 0\le i<j\le n-1,i\ne j,H_i\cap H_j=\left\{O_n\right\},\hfill \end{array}$$

(22)

$$\begin{array}{ccc}& & \overline{H}=H_0\cup H_1\cup H_2\cup H_3.\hfill \end{array}$$

(23)

3.2. Equivalence Class

We define the relation ∼ as follows:

$$\begin{array}{ccc}& & A,B\in {\mathrm{\Omega }}_n,\hfill \\ & & A\sim B\mathrm{if}\mathrm{and}\mathrm{only}\mathrm{if}\forall S\in \mathbb{S}\left(n\right),\langle S,A\rangle =\langle S,B\rangle .\hfill \end{array}$$

(24)

This represents an equivalence relationship between A and B, leading to the construction of an equivalence class.

Regarding this equivalence class, the following theorem holds:

Theorem 2.

$$\begin{array}{ccc}& & A,B\in {\mathrm{\Omega }}_n,\hfill \\ & & A\sim Bif and only if\hfill \\ & & \forall \{i,j\}\in \mathbb{P}\left(n\right),\hfill \\ & & A_{i,j}-\frac{1}{n-2}\left(\langle R_i,A\rangle +\langle R_j,A\rangle \right)=B_{i,j}-\frac{1}{n-2}\left(\langle R_i,B\rangle +\langle R_j,B\rangle \right).\hfill \end{array}$$

(25)

That is, for any matrix C in the equivalence class, the values given by the following are conserved.

$$\begin{array}{c}\hfill \forall \{i,j\}\in \mathbb{P}\left(n\right),C_{i,j}-\frac{1}{n-2}\left(\langle R_i,C\rangle +\langle R_j,C\rangle \right).\end{array}$$

(26)

The matrix form of the conserved values is described in Appendix A.

Proof of Theorem 2.

First, we prove sufficiency. We assume that the following equation holds:

$$\begin{array}{c}\hfill \forall \{i,j\}\in \mathbb{P}\left(n\right),A_{i,j}-\frac{1}{n-2}\left(\langle R_i,A\rangle +\langle R_j,A\rangle \right)=B_{i,j}-\frac{1}{n-2}\left(\langle R_i,B\rangle +\langle R_j,B\rangle \right).\end{array}$$

(27)

With Equation (27), the following equation holds:

$$\begin{array}{ccc}& & \sum _{\{i,j\}\in \mathbb{P}\left(n\right)}\left\{A_{i,j}-\frac{1}{n-2}\left(\langle R_i,A\rangle +\langle R_j,A\rangle \right)\right\}\hfill \\ & & =\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}\left\{B_{i,j}-\frac{1}{n-2}\left(\langle R_i,B\rangle +\langle R_j,B\rangle \right)\right\}.\hfill \end{array}$$

(28)

Here, the left side can be calculated as follows because the number of pairs including element k in $\mathbb{P}\left(n\right)$ is $n-1$:

$$\begin{array}{ccc}& & \sum _{\{i,j\}\in \mathbb{P}\left(n\right)}\left\{A_{i,j}-\frac{1}{n-2}\left(\langle R_i,A\rangle +\langle R_j,A\rangle \right)\right\}\hfill \\ & =& \sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{A}_{i,j}-\frac{n-1}{n-2}\sum _{k=1}^n\langle R_k,A\rangle \hfill \\ & =& \sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{A}_{i,j}-\frac{n-1}{n-2}\sum _{k=1}^n\sum _{l\ne k}{A}_{k,l}\hfill \\ & =& \sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{A}_{i,j}-\frac{2(n-1)}{n-2}\sum _{\{k,l\}\in \mathbb{P}\left(n\right)}{A}_{k,l}\hfill \\ & =& -\frac{n}{n-2}\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{A}_{i,j}.\hfill \end{array}$$

(29)

Using Equation (29), Equation (28) is transformed into the following:

$$\begin{array}{c}\hfill -\frac{n}{n-2}\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{A}_{i,j}=-\frac{n}{n-2}\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{B}_{i,j}.\end{array}$$

(30)

Therefore,

$$\begin{array}{c}\hfill \sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{A}_{i,j}=\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{B}_{i,j}.\end{array}$$

(31)

The following equation holds for any pairing S by Equation (27):

$$\begin{array}{ccc}& & \sum _{\{i,j\}\in f_{\mathrm{set}}\left(S\right)}\left\{A_{i,j}-\frac{1}{n-2}\left(\langle R_i,A\rangle +\langle R_j,A\rangle \right)\right\}\hfill \\ & & =\sum _{\{i,j\}\in f_{\mathrm{set}}\left(S\right)}\left\{B_{i,j}-\frac{1}{n-2}\left(\langle R_i,B\rangle +\langle R_j,B\rangle \right)\right\}.\hfill \end{array}$$

(32)

Here, the following equation holds. Note that $\{i,j\}$ belongs to $f_{\mathrm{set}}\left(S\right)$; hence, $\langle R_k,A\rangle$ appears only once and all indexes k ranging from 1 to n appear over the summation:

$$\begin{array}{ccc}\hfill \sum _{\{i,j\}\in f_{\mathrm{set}}\left(S\right)}\left(\langle R_i,A\rangle +\langle R_j,A\rangle \right)& =& \sum _{k=1}^n\langle R_k,A\rangle \hfill \\ & =& \sum _{k=1}^n\sum _{l,l\ne k}{A}_{k,l}\hfill \end{array}$$

(33)

$$\begin{array}{ccc}& =& 2\sum _{\{k,l\}\in \mathbb{P}\left(n\right)}{A}_{k,l}.\hfill \end{array}$$

(34)

For B, the following equation also holds:

$$\begin{array}{ccc}\hfill \sum _{\{i,j\}\in f_{\mathrm{set}}\left(S\right)}\left(\langle R_i,B\rangle +\langle R_j,B\rangle \right)& =& \sum _{k=1}^n\langle R_k,B\rangle \hfill \end{array}$$

(35)

$$\begin{array}{ccc}& =& 2\sum _{\{k,l\}\in \mathbb{P}\left(n\right)}{B}_{k,l}.\hfill \end{array}$$

(36)

Using these transformations, Equation (32) is transformed as follows:

$$\begin{array}{c}\hfill \langle S,A\rangle -\frac{2}{n-2}\sum _{\{k,l\}\in \mathbb{P}\left(n\right)}{A}_{k,l}=\langle S,B\rangle -\frac{2}{n-2}\sum _{\{k,l\}\in \mathbb{P}\left(n\right)}{B}_{k,l}.\end{array}$$

(37)

With Equation (31),

$$\begin{array}{ccc}& & \langle S,A\rangle =\langle S,B\rangle .\hfill \end{array}$$

(38)

Then, $A\sim B$ holds.

Second, we prove the necessity. We assume that $A\sim B$ holds. We define $A^{*}\in {\mathrm{\Omega }}_n$ as follows:

$$\begin{array}{c}\hfill A_{i,j}^{*}\equiv \frac{1}{n-2}(\langle R_i,A\rangle +\langle R_j,A\rangle )+B_{i,j}-\frac{1}{n-2}(\langle R_i,B\rangle +\langle R_j,B\rangle ).\end{array}$$

(39)

By Equations (33), (35) and (39),

$$\begin{array}{ccc}\hfill \forall S\in \mathbb{S}\left(n\right),\langle S,A^{*}\rangle & =& \sum _{\{i,j\}\in f_{\mathrm{set}}\left(S\right)}{A}_{i,j}^{*}\hfill \\ & =& \langle S,B\rangle +\frac{1}{n-2}\sum _{i=1}^n\langle R_i,A\rangle -\frac{1}{n-2}\sum _{i=1}^n\langle R_i,B\rangle .\hfill \end{array}$$

(40)

We derive the relationship between ${\sum }_{i=1}^n\langle R_i,A\rangle$ and ${\sum }_{S\in \mathbb{S}\left(n\right)}\langle S,A\rangle$ here in order to transform Equation (40). By Equation (34),

$$\begin{array}{c}\hfill \sum _{i=1}^n\langle R_i,A\rangle =2\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{A}_{i,j}.\end{array}$$

(41)

For ${\sum }_{S\in \mathbb{S}\left(n\right)}\langle S,A\rangle$, we focus on the fact that the number of appearances of $A_{i,j}$ is $(n-3)!!$,

$$\begin{array}{c}\hfill \sum _{S\in \mathbb{S}\left(n\right)}\langle S,A\rangle =(n-3)!!\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{A}_{i,j}.\end{array}$$

(42)

With Equations (41) and (42), the following relationship holds:

$$\begin{array}{c}\hfill \sum _{i=1}^n\langle R_i,A\rangle =\frac{2}{(n-3)!!}\sum _{S\in \mathbb{S}\left(n\right)}\langle S,A\rangle .\end{array}$$

(43)

Therefore, the following holds by $A\sim B$ and Equation (43):

$$\begin{array}{ccc}\hfill \sum _{i=1}^n\langle R_i,A\rangle & =& \frac{2}{(n-3)!!}\sum _{S\in \mathbb{S}\left(n\right)}\langle S,A\rangle \hfill \\ & =& \frac{2}{(n-3)!!}\sum _{S\in \mathbb{S}\left(n\right)}\langle S,B\rangle \hfill \\ & =& \sum _{i=1}^n\langle R_i,B\rangle .\hfill \end{array}$$

(44)

By Equation (44), we can cancel the second and third terms of (40),

$$\begin{array}{c}\hfill \langle S,A^{*}\rangle =\langle S,B\rangle .\end{array}$$

(45)

In addition, $A\sim B$ holds. Therefore,

$$\begin{array}{c}\hfill \forall S\in \mathbb{S}\left(n\right),\langle S,A^{*}\rangle =\langle S,B\rangle =\langle S,A\rangle .\end{array}$$

(46)

Additionally, the following also holds by $A\sim B$ and Equation (44):

$$\begin{array}{ccc}\hfill \sum _{j,j\ne i}{A}_{i,j}^{*}& =& \frac{n-1}{n-2}\langle R_i,A\rangle +\frac{1}{n-2}\sum _{j,j\ne i}\langle R_j,A\rangle +\sum _{j,j\ne i}{B}_{i,j}\hfill \\ & & -\frac{n-1}{n-2}\langle R_i,B\rangle -\frac{1}{n-2}\sum _{j,j\ne i}\langle R_j,B\rangle \hfill \\ & =& \frac{1}{n-2}\left(\sum _{j=1}^n\langle R_j,A\rangle -\sum _{j=1}^n\langle R_j,B\rangle \right)+\langle R_i,A\rangle \hfill \\ & =& \langle R_i,A\rangle .\hfill \end{array}$$

(47)

By Equation (47),

$$\begin{array}{c}\hfill 1\le i\le n,\langle R_i,A^{*}\rangle =\langle R_i,A\rangle .\end{array}$$

(48)

Therefore, by Equations (46) and (48) and Corollary 1,

$$\begin{array}{c}\hfill A=A^{*}\end{array}$$

(49)

is valid. That is to say, the following equation holds:

$$\begin{array}{c}\hfill \{i,j\}\in \mathbb{P}\left(n\right),A_{i,j}-\frac{1}{n-2}\left(\langle R_i,A\rangle +\langle R_j,A\rangle \right)=B_{i,j}-\frac{1}{n-2}\left(\langle R_i,B\rangle +\langle R_j,B\rangle \right).\end{array}$$

(50)

□

3.3. Mean and Covariance

Here, we analyze statistical properties associated with the compatibility matrix and the total compatibility.

We define the mean values of compatibilities and total compatibilities as

$$\begin{array}{c}\hfill C\in {\mathrm{\Omega }}_n,\\ \hfill {\mu }_{\mathrm{element}}\left(C\right)& \equiv & \frac{2}{n(n-1)}\sum _{1\le i<j\le n}{C}_{i,j},\hfill \\ \hfill {\mu }_{\mathrm{sum}}\left(C\right)& \equiv & \frac{1}{(n-1)!!}\sum _{S\in \mathbb{S}\left(n\right)}\langle S,C\rangle .\hfill \end{array}$$

By Equation (42), ${\mu }_{\mathrm{sum}}\left(C\right)$ is transformed into

$$\begin{array}{ccc}\hfill {\mu }_{\mathrm{sum}}\left(C\right)& \equiv & \frac{1}{(n-1)!!}\sum _{S\in \mathbb{S}\left(n\right)}\langle S,C\rangle \hfill \\ & =& \frac{1}{n-1}\sum _{1\le i<j\le n}{C}_{i,j}\hfill \\ & =& \frac{n}{2}{\mu }_{\mathrm{element}}\left(C\right)\hfill \end{array}$$

(51)

where ${\mu }_{\mathrm{element}}\left(C\right)$ indicates the mean value of the elements of the compatibility matrix C and ${\mu }_{\mathrm{sum}}\left(C\right)$ is the mean of the total compatibility across all possible pairing with respect to the compatibility matrix C.

We define the square root of the covariance values for compatibilities and total compatibilities as follows:

$$\begin{array}{ccc}& & {\sigma }_{\mathrm{element}}(A,B)\equiv \sqrt{\sum _{1\le i<j\le n}\frac{2}{n(n-1)}\left(A_{i,j}-{\mu }_{\mathrm{element}}\left(A\right)\right)\left(B_{i,j}-{\mu }_{\mathrm{element}}\left(B\right)\right)},\hfill \\ & & {\sigma }_{\mathrm{sum}}(A,B)\equiv \sqrt{\frac{1}{(n-1)!!}\sum _{S\in \mathbb{S}\left(n\right)}\left(\langle S,A\rangle -{\mu }_{\mathrm{sum}}\left(A\right)\right)\left(\langle S,B\rangle -{\mu }_{\mathrm{sum}}\left(B\right)\right)}.\hfill \end{array}$$

(52)

Clearly, ${\sigma }_{\mathrm{element}}^2(C,C)$ and ${\sigma }_{\mathrm{sum}}^2(C,C)$ are variance values for compatibilities and total compatibilities when the compatibility matrix is C.

Regarding ${\sigma }_{\mathrm{sum}}^2(C,C)$, the following theorem holds.

Theorem 3.

Let $I_n$ be the $n\times n$ identity matrix, $J_n$ the $n\times n$ matrix where all elements are 1, and $C\in {\mathrm{\Omega }}_n,\widehat{C}\equiv C-{\mu }_{\mathrm{element}}\left(C\right)(J_n-I_n)$. Then, the following equation holds:

$$\begin{array}{c}\hfill {\sigma }_{\mathrm{sum}}^2(C,C)=\frac{n(n-2)}{2(n-3)}{\sigma }_{\mathrm{element}}^2(C,C)-\frac{1}{(n-1)(n-3)}\sum _{k=1}^n{\langle R_k,\widehat{C}\rangle }^2.\end{array}$$

(53)

Proof of Theorem 3.

By definition,

$$\begin{array}{ccc}\hfill {\sigma }_{\mathrm{sum}}^2(C,C)& =& \frac{1}{(n-1)!!}\sum _{S\in \mathbb{S}\left(n\right)}{\left\{\langle S,C\rangle -{\mu }_{\mathrm{sum}}\left(C\right)\right\}}^2\hfill \end{array}$$

Using Equation (51),

$$\begin{array}{ccc}\hfill {\sigma }_{\mathrm{sum}}^2(C,C)& =& \frac{1}{(n-1)!!}\sum _{S\in \mathbb{S}\left(n\right)}{\left\{\langle S,C\rangle -\frac{n}{2}{\mu }_{\mathrm{element}}\left(C\right)\right\}}^2\hfill \end{array}$$

(54)

Here, the following equation holds:

$$\begin{array}{ccc}\hfill \langle S,\widehat{C}\rangle & =& \frac{1}{2}{\langle S,\widehat{C}\rangle }_F\hfill \\ & =& \frac{1}{2}{\langle S,C\rangle }_F-\frac{1}{2}{\mu }_{\mathrm{element}}\left(C\right)\langle S,J_n-I_n\rangle \hfill \\ & =& \frac{1}{2}{\langle S,C\rangle }_F-\frac{n}{2}{\mu }_{\mathrm{element}}\left(C\right)\hfill \\ & =& \langle S,C\rangle -\frac{n}{2}{\mu }_{\mathrm{element}}\left(C\right)\hfill \end{array}$$

(55)

Therefore, by Equations (54) and (55),

$$\begin{array}{ccc}\hfill {\sigma }_{\mathrm{sum}}^2(C,C)& =& \frac{1}{(n-1)!!}\sum _{S\in \mathbb{S}\left(n\right)}{\left\{\langle S,C\rangle -\frac{n}{2}{\mu }_{\mathrm{element}}\left(C\right)\right\}}^2\hfill \\ & =& \frac{1}{(n-1)!!}\sum _{S\in \mathbb{S}\left(n\right)}{\langle S,\widehat{C}\rangle }^2\hfill \\ & =& \frac{1}{(n-1)!!}·(n-3)!!\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}^2\hfill \\ & & +\frac{1}{(n-1)!!}·(n-5)!!\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}\sum _{\begin{array}{c}\{k,l\}\in \mathbb{P}\left(n\right)\\ \{k,l\}\cap \{i,j\}=\varnothing \end{array}}{\widehat{C}}_{i,j}{\widehat{C}}_{k,l}\hfill \\ & =& \frac{1}{n-1}\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}^2+\frac{1}{(n-1)(n-3)}\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}\sum _{\begin{array}{c}\{k,l\}\in \mathbb{P}\left(n\right)\\ \{k,l\}\cap \{i,j\}=\varnothing \end{array}}{\widehat{C}}_{i,j}{\widehat{C}}_{k,l}\hfill \\ & =& \frac{1}{n-1}\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}^2+\frac{1}{(n-1)(n-3)}\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}\sum _{\begin{array}{c}\{k,l\}\in \mathbb{P}\left(n\right)\\ \{k,l\}\cap \{i,j\}=\varnothing \end{array}}{\widehat{C}}_{k,l}.\hfill \end{array}$$

(56)

Here, we focus on ${\sum }_{\begin{array}{c}\{k,l\}\in \mathbb{P}\left(n\right)\\ \{k,l\}\cap \{i,j\}=\varnothing \end{array}}{\widehat{C}}_{k,l}$. This term is transformed as follows:

$$\begin{array}{ccc}\hfill \sum _{\begin{array}{c}\{k,l\}\in \mathbb{P}\left(n\right)\\ \{k,l\}\cap \{i,j\}=\varnothing \end{array}}{\widehat{C}}_{k,l}& =& {\widehat{C}}_{i,j}+\sum _{\{k,l\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{k,l}-\sum _{k,k\ne i}{\widehat{C}}_{i,k}-\sum _{k,k\ne j}{\widehat{C}}_{j,k}\hfill \\ & =& {\widehat{C}}_{i,j}-\langle R_i,\widehat{C}\rangle -\langle R_j,\widehat{C}\rangle +\sum _{\{k,l\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{k,l}\hfill \\ & =& {\widehat{C}}_{i,j}-\langle R_i,\widehat{C}\rangle -\langle R_j,\widehat{C}\rangle +\sum _{\{k,l\}\in \mathbb{P}\left(n\right)}\left(C_{k,l}-{\mu }_{\mathrm{element}}\left(C\right)\right)\hfill \\ & =& {\widehat{C}}_{i,j}-\langle R_i,\widehat{C}\rangle -\langle R_j,\widehat{C}\rangle +\left(\sum _{\{k,l\}\in \mathbb{P}\left(n\right)}{C}_{k,l}\right)-\frac{n(n-1)}{2}{\mu }_{\mathrm{element}}\left(C\right)\hfill \\ & =& {\widehat{C}}_{i,j}-\langle R_i,\widehat{C}\rangle -\langle R_j,\widehat{C}\rangle .\hfill \end{array}$$

(57)

Then, using this formula,

$$\begin{array}{ccc}& & \sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}\sum _{\begin{array}{c}\{k,l\}\in \mathbb{P}\left(n\right)\\ \{k,l\}\ne \{i,j\}\end{array}}{\widehat{C}}_{k,l}\hfill \\ & & =\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}\left({\widehat{C}}_{i,j}-\langle R_i,\widehat{C}\rangle -\langle R_j,\widehat{C}\rangle \right)\hfill \\ & & =\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}^2-\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}\left(\langle R_i,\widehat{C}\rangle +\langle R_j,\widehat{C}\rangle \right)\hfill \\ & & =\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}^2-\sum _{i=1}^n\sum _{j\ne i}{\widehat{C}}_{i,j}\langle R_i,\widehat{C}\rangle \hfill \\ & & =\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}^2-\sum _{i=1}^n{\langle R_i,\widehat{C}\rangle }^2.\hfill \end{array}$$

(58)

By Equations (56) and (58), the following equation holds:

$$\begin{array}{ccc}\hfill {\sigma }_{\mathrm{sum}}^2(C,C)& =& \frac{n-2}{(n-1)(n-3)}\sum _{\{i,j\}\in \mathbb{P}\left(n\right)}{\widehat{C}}_{i,j}^2-\frac{1}{(n-1)(n-3)}\sum _{k=1}^n{\langle R_k,\widehat{C}\rangle }^2\hfill \\ & =& \frac{n(n-2)}{2(n-3)}{\sigma }_{\mathrm{element}}^2(C,C)-\frac{1}{(n-1)(n-3)}\sum _{k=1}^n{\langle R_k,\widehat{C}\rangle }^2.\hfill \end{array}$$

(59)

Therefore, the theorem holds. □

4. Variance Optimization

This section examines the performance enhancement from deriving a pairing that yields higher total compatibility by exploiting the algebraic structures identified in the previous section. We first show that the variance of the elements in a compatibility matrix affects the performance of the heuristic algorithm proposed in our previous study. Then we propose the transformation of a compatibility matrix to another one that minimizes the variance while ensuring that the total compatibility is maintained.

4.1. Performance Degradation through the Observation Phase

In our previous study [17], we proposed an algorithm for recognizing the compatibilities among elements through multiple measurements of total compatibility. To summarize, we estimate the compatibility matrix denoted by $\tilde{C}\in {\mathrm{\Omega }}_n$, which is given by

$$\begin{array}{ccc}\hfill & & C\in {\mathrm{\Omega }}_n,\hfill \\ & & {\tilde{C}}_{i,j}=\left\{\begin{array}{c}0\mathrm{if}1\in \{i,j\}\hfill \\ C_{i,j}-C_{1,i}-C_{1,j}+\frac{2}{n-2}\sum _{k=2}^n{C}_{1,k}\mathrm{otherwise}.\hfill \end{array}\right.\hfill \end{array}$$

(60)

This $\tilde{C}\in {\mathrm{\Omega }}_n$ is one of the elements in the equivalence class. That is, $C\sim \tilde{C}$ holds. By this property and Equation (60), the dimension of ${\left\{S\right\}}_{S\in \mathbb{S}\left(n\right)}$ is given by $(n-1)(n-2)/2$, which we refer to as $L_{\min }\left(n\right)$. This means that the number of observations required to grasp the compatibilities through an observation phase is $L_{\min }\left(n\right)$.

Indeed, our previous study proposed an observation algorithm which needs $\mathcal{O}\left(n^2\right)$ measurements. We have also confirmed numerically that the observation strategy provides a compatibility matrix, which is in the equivalence class of the ground-truth compatibility matrix $C^g$. In the numerical studies, the elements of the ground-truth compatibility matrix, $C_{i,j}^g$, were specified by uniformly distributed random numbers in the range of $[0,1]$.

However, finding a pairing yielding a greater total compatibility becomes difficult based on $C^e$, including the above-mentioned $\tilde{C}$, even though $C^e$ is in the equivalence class where the ground-truth compatibility $C^g$ is included. In searching for a better pairing, we use a heuristic algorithm, which is named Pairing-2-opt [17]. We consider the difficulty comes from the fact that the variance of the elements of the compatibility matrix ${\sigma }_{\mathrm{element}}^2(C^e,C^e)$ would be larger than those of ${\sigma }_{\mathrm{element}}^2(C^g,C^g)$, which is highly likely to cause the combining algorithm to become stuck in a local minimum.

Hence, our idea is to find a compatibility matrix X which is in the same equivalence class of matrix C

$$\begin{array}{c}\hfill \forall S\in \mathbb{S}\left(n\right),\langle S,X\rangle =\langle S,C\rangle \end{array}$$

(61)

while simultaneously minimizing the variance of the elements of ${\sigma }_{\mathrm{element}}^2(X,X)$.

4.2. Transforming the Compatibility Matrix with Minimized Variance

We solve the following optimization problem:

$$\begin{array}{ccc}\hfill \min :& & {\sigma }_{\mathrm{element}}^2(X,X),\hfill \\ \hfill \mathrm{subject}\mathrm{to}:& & X,C\in {\mathrm{\Omega }}_n,C\mathrm{is}\mathrm{fixed},\hfill \\ & & X\sim C.\hfill \end{array}$$

(62)

By Theorem 3 and ${\sigma }_{\mathrm{sum}}^2(X,X)={\sigma }_{\mathrm{sum}}^2(C,C)$, we transform this problem into the following form:

$$\begin{array}{ccc}\hfill \min :& & \sum _{k=1}^n{\langle R_k,\widehat{X}\rangle }^2,\hfill \\ \hfill \mathrm{subject}\mathrm{to}:& & X,C\in {\mathrm{\Omega }}_n,C\mathrm{is}\mathrm{fixed},\hfill \\ & & X\sim C,\hfill \\ & & \widehat{X}\equiv X-{\mu }_{\mathrm{element}}\left(X\right)(J_n-I_n).\hfill \end{array}$$

(63)

The optimal solution for this problem holds because the sum of squares is minimized when all values are 0:

$$\begin{array}{ccc}& & 1\le k\le n,\langle R_k,\widehat{X}\rangle =0.\hfill \end{array}$$

(64)

Hence, the following equation is derived:

$$\begin{array}{c}\hfill 1\le k\le n,\langle R_k,X\rangle =(n-1){\mu }_{\mathrm{element}}\left(C\right).\end{array}$$

(65)

By Equation (65) and Theorem 2, the optimal solution is represented as follows:

$$\begin{array}{ccc}& & X_{i,j}=\frac{2(n-1)}{n-2}{\mu }_{\mathrm{element}}\left(C\right)+C_{i,j}-\frac{1}{n-2}\left(\langle R_i,C\rangle +\langle R_j,C\rangle \right).\hfill \end{array}$$

(66)

Thus, the compatibility matrix with minimal variance is derived. In addition, this discussion and solution mean that the optimal-variance solution is unique with respect to the equivalence class.

5. Simulation

In this section, we evaluate the performance of the proposed method on the pairing optimization problem. There are two important points that should be clarified through the simulations. One is to quantitatively evaluate the performance reduction of the combining algorithm proposed in the previous study, based on the observation phase. The other is to demonstrate the performance enhancement due to the variance optimization discussed in Section 4.

5.1. Setting

We configure the ground-truth compatibility matrix $C^g\in {\mathrm{\Omega }}_n$ with two different distributions. The first is the uniform distribution:

$$\begin{array}{c}\hfill \forall \{i,j\}\in \mathbb{P},C_{i,j}^g\sim U(0,1).\end{array}$$

(67)

Here, we denote the uniform distribution between 0 and 1 as $U(0,1)$. The second distribution is the Poisson distribution:

$$\begin{array}{c}\hfill \forall \{i,j\}\in \mathbb{P},C_{i,j}^g\sim Poisson\left(1\right).\end{array}$$

(68)

Here, we denote the Poisson distribution whose mean is $\lambda$ as $Poisson\left(\lambda \right)$. In the numerical simulation, the number of elements in the system n varied from 100 to 1000 in intervals of 100. For each n, we conducted 100 trials with different randomly generated ground-truth compatibility matrices $C^g$ based on Equation (67) or Equation (68). We quantified the performance for each derived pairing $S\in \mathbb{S}\left(n\right)$ by $2\langle S,C^g\rangle /n$ and evaluated its average over 100 trials for each value of n.

5.2. Simulation Flow

The ground-truth compatibility matrix $C^g$ is transformed into $C^{e_1}$ by the observation algorithm based on Equation (60). The variance optimization transforms $C^{e_1}$ into $C^{e_2}$. The combining algorithm, which is called PNN+p2-opt [17], yields a pairing with the intention of achieving higher total compatibility. The exchange limit l is an internal parameter in PNN+p2-opt. This determines the number of maximum trials, and is set to 600 in the present study.

We evaluated the performance on the basis of $C^g$, $C^{e_1}$, and $C^{e_2}$, as shown in flows (i), (ii), and (iii), respectively, in Figure 2.

5.3. Performance

The blue, red, and yellow curves in Figure 3 demonstrate the performance of cases (i), (ii), and (iii), respectively, as a function of the number of elements for the uniform distribution (Figure 3a) and the Poisson distribution (Figure 3b). For the uniform distributed ground-truth we observe that the performance of case (ii) is inferior to that of case (i), demonstrating the performance degradation by the transformation from $C^g$ to $C^{e_1}$ through observation. Furthermore, the performance of case (iii) is enhanced compared with that of case (ii), which confirms the performance gain from variance optimization. The results differ for the Poisson distribution. Here, the performance of case (iii) is higher than case (i). That is, for the Poisson case the variance optimization (Flow (iii)) not only counteracted the performance loss of the observation algorithm (Flow (ii)), but actually enhanced the performance compared to the ground truth matrix $C^g$ (Flow (i)). Further numerical tests revealed that the relationship of performances for a Gaussian distribution are similar to those for the uniform distribution. Conversely, the performance for a binary distribution hardly differed between any of the algorithms.

The variance of $C^g$, $C^{e_1}$, and $C^{e_2}$ are evaluated as shown in Figure 4 as a function of the number of elements. We clearly observe that the variance of $C^{e_1}$ is higher than $C^g$ while the variance of $C^{e_2}$ becomes comparable to the ground-truth case $C^g$ for both the uniform and Poisson distributions.

From these numerical results, we can conclude that the variance optimization minimizes the variance and enhances the performance of the achieved total compatibility. It is worth noting that the performance with the uniform distribution after variance optimization is still lower than the case based on the ground-truth matrix $C^g$, as observed in Figure 3a. This occurs because the variance optimization algorithm does not transform $C^{e_1}$ to the original compatibility matrix $C^g$. In other words, there exist additional factors that influence the performance of the combining algorithm that are related to the compatibility distribution. The distribution of the original compatibility $C^g$ (uniform distribution) is seemingly beneficial for the performance of the heuristic combining algorithm, even when compared to the compatibility matrix with minimum variance $C^{e_2}$.

6. Conclusions

One of the most challenging issues in the pairing problem is how to understand the underlying compatibilities among the elements under study. An accurate and efficient approach is essential for practical applications such as wireless communications and online social networks. This study reveals several algebraic structures in the pairing optimization problem.

We introduce an equivalence class in the compatibility matrices, containing matrices that yield the same total compatibility although the matrices themselves differ. This can also be expressed through a conserved value or invariance in the equivalence class. Based on such insights, we propose a transformation of the initially estimated compatibility matrix to another form that minimizes the variance of the elements. We demonstrate that the highest total compatibility found heuristically is improved significantly with the proposed transformation relative to the direct approach.

In the future, the proposed algorithm may be applied to bipartite matching and assignment problems, for example. Therefore, if the compatibility between elements that should not be paired is set to a negative value with a relatively large absolute value, we may solve the problem heuristically. Hence, the variance optimization proposed in this study may aid in performance enhancement.