Suggestions for Constructing a Random Variables from Correlated Observations Let $\mathcal{X} \neq \phi $ be a finite set. Let $P_{XY_1Y_2}$ be a fixed  joint distribution over $\mathcal{X}\times\mathcal{X}\times\mathcal{X}\ $ and that a random sample $(X,Y_1,Y_2 )$ is drawn using $P_{XY_1Y_2}$.
Suppose there are two parties, $A$ and $B$ such that $A$ gets to observes $Y_1$ and $B$ gets to observes $Y_2$. Additionally $A$ knows the conditional distribution $P_{Y_1|X}$ and similarly $B$ knows the distribution $P_{Y_2|X}$.
I'm interested in finding a method which makes party $A$ construct $\hat{X}_1$ using the information $P_{Y_1|X}$ and $Y_1$ and similarly $B$ construct $\hat{X}_2$ using the information $P_{Y_2|X}$ and $Y_2$ such that $P(\hat{X}_1 \neq \hat{X}_2)$ is 'small' and $P(\hat{X}_1\neq X)$ is 'small'.
In other words I am interested in constructing a random variable based on correlated observations.
I do agree that the problem is not well posed. I look for only informal suggestions. Any relevant literature would also be really helpful. 
Thanks in advance for your help. 
 A: Here is a trick to map an instance of your problem to the framework of the paper "Distributed Stochastic Optimization via Correlated Scheduling" (IEEE Trans Netw. April 2016): http://ee.usc.edu/stochastic-nets/docs/distributed-optimization-ton.pdf
Let's perform a notation shift: 
\begin{align}
(Y_1,Y_2) &\leftrightarrow (\omega_1, \omega_2) \quad \mbox{[distributed observations]} \\
(\hat{X}_1, \hat{X}_2) &\leftrightarrow (\alpha_1, \alpha_2) \quad \mbox{[distributed actions]} 
\end{align}
Fix $\delta \geq 0$.  Suppose you want each device $i \in \{1,2\}$ to choose an estimate $\hat{X}_i \in \mathcal{X}$ as a (potentially random) function of its observation $Y_i$ to solve the following optimization: 

Problem 1:
\begin{align}
\mbox{Maximize:} & \quad P\left[\hat{X}_1 =X\right]\\
\mbox{Subject to:} & \quad P\left[\hat{X}_1 \neq \hat{X}_2\right] \leq \delta
\end{align}
Notice that Problem 1 is always feasible (so it is possible to satisfy the constraint, for any $\delta \geq 0$), since we can choose the trivial strategy of always using $\hat{X}_1=\hat{X}_2=c$ for some pre-agreed-upon constant $c \in \mathcal{X}$. Intuitively, relaxing the value of $\delta$ allows for a larger utility $P[\hat{X}_1 = X]$. 

Define the following utility function $u(\cdot)$ and penalty function $p(\cdot)$:
\begin{align}
p:\mathcal{X}^4 \rightarrow \mathbb{R} &,  \quad p(x_1,x_2, y_1, y_2) = 1\{x_1\neq x_2\}\\
u:\mathcal{X}^4 \rightarrow \mathbb{R} &, \quad u(x_1,x_2,y_1,y_2) = \sum_{a\in \mathcal{X}}\sum_{b \in \mathcal{X}}\sum_{c \in \mathcal{X}} 1\{y_1=a, y_2=b,  x_1=c\}P[X=c|Y_1=a,Y_2=b]
\end{align}
where $1\{F\}$ is a binary indicator function for the event $F$. 
This fits the general structure for $u(\cdot)$ and $p(\cdot)$ functions in the paper. So the "trick" is to define the utility function in terms of the conditional mass function $P[X=c|Y_1=a,Y_2=b]$. This allows treatment of the random variable $X$ that nobody knows. The paper considers optimal selection of $\hat{X}_1$ and $\hat{X}_2$ to solve the following:

Problem 2:
\begin{align*}
\mbox{Maximize:} & \quad E[u(\hat{X}_1, \hat{X}_2, Y_1,Y_2)] \\
\mbox{Subject to:} & \quad E[p(\hat{X}_1,\hat{X}_2, Y_1,Y_2)] \leq \delta
\end{align*}
With some thought, it can be shown that Problem 2 is equivalent to Problem 1.

Hence, Theorem 1 of the paper can be applied to this problem with $K=1$ constraint, to show that optimality can be achieved by timesharing over $K+1=2$ pure strategies. Specifically, there exists a probability $\theta \in [0,1]$, together with two deterministic functions (called "pure strategies") of the form: 
\begin{align}
\mbox{Pure strategy 1:}& \quad f:\mathcal{X}^2 \rightarrow\mathcal{X}^2 , \quad f(y_1,y_2)=(f_1(y_1), f_2(y_2)) \\
\mbox{Pure strategy 2:}& \quad g:\mathcal{X}^2 \rightarrow\mathcal{X}^2 , \quad g(y_1,y_2)= (g_1(y_1), g_2(y_2))
\end{align}
so that the following strategy is optimal for problem 2 (and hence for problem 1):  Let both devices 1 and 2 share a commonly known random variable $B \in \{0,1\}$ with $P[B=1]=\theta$, where $B$ is chosen in advance and is independent of $(X,Y_1,Y_2)$.  Then: 
Case 1:  If $B=1$, both devices use pure strategy 1.  So if device $i$ observes $Y_i$, it chooses $\hat{X}_i=f_i(Y_i)$. 
Case 2: If $B=0$, both devices use pure strategy 2.  So if device $i$ observes $Y_i$, it chooses $\hat{X}_i = g_i(Y_i)$.
The same structure of using only 2 pure strategies would hold even for a larger number of devices $N \geq 2$. 

By the way, if you changed the problem to an unconstrained one of maximizing $P[\hat{X}_1 = X] - \gamma P[\hat{X}_1 \neq \hat{X}_2]$, then $K=0$ (there are no constraints) and so a single pure strategy is optimal.  Based on this, the "drift-plus-penalty" framework later in the paper develops a sequential way of choosing pure strategies that, over time, solves the constrained problem of interest.  
