Given an $N\times N$ doubly stochastic matrix $\pi$, Birkhoff-von Neumann theorem states that $\pi$ can be expressed as a convex combination of permutation matrices.

One probabilistic interpretation of the result is that there exists a distribution over matchings between disjoint sets $A, B$ each of size $N$ s.t. the probability that $A_i$ is assigned to $B_j$ is given by $\pi_{ij}$.

The question: suppose we have conditional probabilities $\pi_{kj|ls} = P(k\to j|l\to s)$, where $i\to j$ denotes the event that $i$ is matched to $j$. Does there exist a distribution over matchings that respects the given conditional probabilities? If so, is there a known algorithm for computing any such distribution?

I am more generally interested in non-square matrices, in case it makes a difference.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.