# Remove cycles from a stochastic comparison matrix, while doing the least amount of editing

Let $$\mathcal P_n$$ be the collection of all matrices $$M \in [0, 1]^{n \times n}$$ such that $$M_{ij} + M_{ji} = 1$$ for all $$i, j \in [n]$$. Such matrices are called comparison matrices. A comparison matrix $$M \in \mathcal P_n$$ is said to be strongly stochastically transitive (SST) if $$M_{ik} \ge \max(M_{ij},M_{jk})$$ whenever $$i,j,k$$ are distinct and $$\min(M_{ij},M_{jk}) \ge 1/2$$. Let $$\mathcal T_n \subseteq \mathcal P_n$$ be the set of all SST. Given $$M \in \mathcal T_n$$, consider the following problem

Problem. Find $$T^* \in \mathcal T_n$$ such that $$\Delta(M,T^*)$$ is minimal, where $$\Delta(M,T) := \|M-T\|_1 = 2\sum_{i < j} |M_{ij}-T_{ij}|$$.

$$\Delta(M,T^*)$$ is just a measure of the amount of editing done on the input matrix $$M$$, in order to make it into an SST matrix.

## Question

Is the above problem reducible to some standard problem in computer science which can be solved efficiently (i.e in time polynomial in $$n$$) at least apprimately, say an algorithm which returns $$\widehat{T} \in \mathcal T_n$$ such that $$\Delta(M,\widehat{T}) \le (1+\epsilon)\Delta(M,T^*)$$ ?