This is related to the rank aggregation question I asked previously.

I have items $I_1, \ldots, I_N$ and the observations of a number of pairwise trials which pit pairs $I_i$ and $I_j$ against eachother and select a "winner". Let $W_{ij}$ be the number of times i beats j.

Note that the number of trials between i and j is very much dependent on i and j: In some cases there may be none, in some there may be very many.

I am trying to estimate a matrix $P_{ij}$ corresponding to the probability that i beats j in a trial (I consider $P_{ii} = \frac{1}{2}$ for convenience reasons). My current, somewhat unprincipled, approach is a bayesian average

`\[ P_{ij} = \frac{ \frac{1}{2} S + W_{ij} }{S + W_{ij} + W_{ji}} \]`

where S is some smoothing constant (I currently have S = 5). This corresponds to a bayesian approach with a prior for $P_{ij}$ of $\beta(\frac{1}{2}S, \frac{1}{2}S)$ and then taking the expected value of the posterior distribution.

My problem with this is the following:

This is effectively treating each pair i, j as independent, whereas in fact we "believe" that there is a consistency between them. In particular if i tends to beat j and j tends to beat k, this should count as evidence that i tends to beat k even in the absence of pairwise trials between i and k.

There may be circumstances where we have very many trials for i, j and j, k and conclude that both $P_{ij}$ and $P_{jk}$ are high, but we have very few trials for i, k and thus conclude that $P_{ik}$ is very close to $\frac{1}{2}$ (possibly even concluding it's less than $\frac{1}{2}$ if e.g. there was only one trial and it had a surprising result). This is non-optimal.

So I'd like some sort of reasonably principled way of introducing intermediate results as evidence that the majority prefers one to the other. There are various plausible sounding things I could try, but I'd like to do this "properly" if at all possible, and most of my ideas involve more hand waving than solid mathematics.

One example of something plausible but possibly nonsensical I'm considering trying is iterating an expand/collapse process of:

Expand: $P \to P^2$

Collapse: $P \to Q$, where $Q_{ij} = \frac{P_{ij}}{P_{ij} + P_{ji}}$

The idea being that we inflate probabilities where there are a lot of large intermediate results and then collapse down to the symmetry condition that $P_{ij} + P_{ji} = 1$.

This seems to produce semi-tolerable results (I've not tested extensively yet), but it's not actually clear to me that this process converges or why it should work.

Suggestions?

Edit:

On having thought about this a little more carefully, I think the following may capture what I am trying to achieve:

I want to assume that there is some distribution on the permutations of 1..N, with a strong prior belief that this distribution is close to uniform, and that each pairwise trial consists of sampling from this distribution and comparing the positions of i and j.