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.


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^*)$ ?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.