Colored stochastic dominance problems
Jie Xue, Yuan Li · arXiv (Cornell University) · 2016
In this paper, we study the dominance relation under a stochastic setting. Let $\mathcal{S}$ be a set of $n$ colored stochastic points in $\mathbb{R}^d$, each of which is associated with an existence probability. We investigate the problem of computing the probability that a realization of $\mathcal{S}$ contains inter-color dominances, which we call the \textit{colored stochastic dominance} (CSD) problem. We propose the first algorithm to solve the CSD problem for $d=2$ in $O(n^2 \log^2 n)$ time. On the other hand, we prove that, for $d \geq 3$, even the CSD problem with a restricted color pattern is \#P-hard. In addition, even if the existence probabilities are restricted to be $\frac{1}{2}$, the problem remains \#P-hard for $d \geq 7$. A simple FPRAS is then provided to approximate the desired probability in any dimension. We also study a variant of the CSD problem in which the dominance relation is considered with respect to not only the standard basis but any orthogonal basis of $\mathbb{R}^d$. Specifically, this variant, which we call the {\em free-basis colored stochastic dominance} (FBCSD) problem, considers the probability that a realization of $\mathcal{S}$ contains inter-color dominances with respect to any orthogonal basis of $\mathbb{R}^d$. We show that the CSD problem is polynomial-time reducible to the FBCSD problem in the same dimension, which proves the \#P-hardness of the latter for $d \geq 3$. Conversely, we reduce the FBCSD problem in $\mathbb{R}^2$ to the CSD problem in $\mathbb{R}^2$, by which an $O(n^4 \log^2 n)$ time algorithm for the former is obtained.