Bayesian rank of game characters

Question

I have a set of game characters of a single shape (A) but a different size (small (1) to big (5)) and so the set of characters is (A1,A2,A3,A4,A5). They interact with eachother in a game grid in a pair-wise fashion, an interaction during which one will win and one will lose a battle. This goes on for a finite amount of time.

Is there a way I can use Bayesian inference to:

1. create a ranking of these characters in terms of who has won the most, and
2. create a variable that represents the gradual acquisition of knowledge about the difference in size between the characters?

I currently have a list of Beta variables to characterise the rank, and can see how one could possibly use some kind of inference to rank them, but I am unsure as to make the second part work. The size difference needs to be used in some way to inform a variable, but I am unsure beyond that.

So in sum, help greatly appreciated on points 1 and 2.

Answer 1

Here's a reformulation of your model broken down by component assumptions.

1. We have an unknown matrix of win probabilities, $P=(p_{ij})$, indexed from 1 to 5, where $0 \leq p_{ij} \leq 1$ and $p_{ij}=1-p_{ji}$ for all $i$, $j$. For every $(i,j)$ with $i \leq j$, we observe $n_{ij}$ independent draws from each corresponding Bernoulli($p_{ij}$) distribution.
2. There is some ranking $r(1),...,r(5)$ of the indices where $r(1)$ is the index of the "best" character and $r(5)$ is the index of the worst character. More precisely, we have (i) $p_{r(i)r(j)}\leq 1/2$ for all $i \leq j$ and (ii) $p_{r(i)r(j)} \geq p_{r(i)r(k)}$ for all $j \leq k$.
3. We observe "size" covariates $s_i$, and would like to find a relationship of the form $p_{ij}= f(s_i-s_j) + \epsilon$ where $f$ is some monotonic function and $\epsilon$ is a small error term.

I will describe a simple way of doing it using Maximum Likelihood, before outlining a more technically difficult Bayesian approach.

Maximum Likelihood

Background: see definition of logit, EM Algorithm.

Let $\tilde{P}=(p_{r^{-1}(i)r^{-1}(j)})$ be the matrix $P$ permuted so that the indices correspond to the true ranking. Reparameterize $\tilde{P}$ by writing $$ \tilde{p}_{ij}=(1/2)\text{logit}(\sum_{k=i}^5 \sum_{l=1}^{i-1} e^{u_{kl}})+1/2 $$ for $i < j$. This is done so that your transformed variables $u_{21},u_{31},u_{32},...,u_{54}$ have a 1-1 relationship with valid $\tilde{P}$ but can take any real values.
For every possible ranking, use the EM algorithm to find the likelihood of the ranking, and keep the ranking which has the highest likelihood. For this ranking, use the maximum likelihood estimates of $u_{21},...,u_{54}$ to convert back to the ML estimate of the matrix $P$, which we call $\hat{P}=(\hat{p}_{ij})$.

Now, to determine the "consistency" of the relationship between $p_{ij}$ and $s_i-s_j$, carry out a logistic regression $\hat{p}_{ij} \sim \text{logit}(\beta_0 + \beta_1 (s_i-s_j))$ for all $i < j$. The residuals give you an idea of the consistency. You can try high-order regression formulae, (eg quadratic) but then you may not preserve monotonicity.

Bayesian Approach

Specify a prior on $P$ by assigning uniform (or optionally, beta-weighted) probability to all 5 by 5 matrices with entries in $[0,1]$ which satisfy condition 2, and zero probability to all such matrices which violate condition 2; this gives you the prior density $p(P)$. Sample from the posterior be using resampling (see any intro text on Markov Chain Monte Carlo). From each posterior draw, compute the posterior of the sum or residuals (or whatever measure of consistency you use) based on priors for the regression coefficients $\beta_0, \beta_1$, weighting by the likelihood $$ \exp[-\sum_{i <j}(\text{logit}(\beta_0 + \beta_1 (s_i-s_j))-p_{ij})^2] $$ to get the joint posterior for $P$ and your measure of "consistency."

Answer 2

I don't know if the following model is too "simplistic". Suppose that you have $k\geq 1$ rounds of battles between every pair of the $5$ players sitting on each grid node. Define parameters $$\Theta_{ij}\sim \mathrm{Beta}(1,1) \, ,$$ and let $$X_{ij}^{(k)}\mid \Theta_{ij}=\theta_{ij}\sim\mathrm{Bernoulli}(\theta_{ij})$$ be the indicator of player sitting at node $i$ beating player at node $j$ during the $k$-th battle, for $1\leq i<j\leq 5$, with the necessary (conditional) independence assumptions. The posterior density of the $\Theta_{ij}$'s is proportional to $$ \prod_{1\leq i<j\leq 5} \left(\theta_{ij}^{\,\sum_{\ell=1}^k x_{ij}^{(\ell)}}(1-\theta_{ij})^{k-\sum_{\ell=1}^k x_{ij}^{(\ell)}}\right) \, .$$ To establish the ranking, take $(i,j,k,l,m)$ to be one of the $5!=120$ permutations of $\{1,2,3,4,5\}$, and sample (it's easy) from the posterior distribution to obtain the probability $$ P\{ \Theta_{ij} > \Theta_{jk} > \Theta_{kl} > \Theta_{lm} \mid \mathrm{Data} \} =: p_{ijklm} \, .$$ The biggest $p_{ijklm}$ gives you the ranking.