# Bayesian rank of game characters

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.

• Unless you can say more about the process that determines the winner in a battle, this question has no right answer. In fact, there might not exist a ranking at all. For instance, the players could be rolling intransitive dice to determine the battle outcomes.
– whuber
Commented Nov 18, 2011 at 16:08
• Can we assume that if the character size is bigger, there is a higher probability of winning the battle. A size difference is extracted as an output of the battle (call it DH)
– alan
Commented Nov 18, 2011 at 16:14
• OK, that's good. To be precise, you appear to assume all battle outcomes are independent and that the chance of an $A_i$ beating an $A_j$ never changes. Call these chances $p(i,j)$. Without any loss of generality we can assume $A_i$ is the smaller of the two--$1\le i\lt j\le 5$--and you are assuming $p(i,j)\lt 1/2$ in all such cases. Do you also assume there is some numerical attribute $q(i)$ and some function $f$ such that $p(i,j)=f(q(j)-q(i))$; in other words, that the battle probabilities can be determined by a single number associated with each character size?
– whuber
Commented Nov 18, 2011 at 17:04
• Yes, that can be assumed.
– alan
Commented Nov 18, 2011 at 17:11
• So now, post battle, we have the knowledge "Ai beats Aj", based on probability p(i, j). We also have the value q(j) - q(i) to inform the size difference.
– alan
Commented Nov 18, 2011 at 17:20

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."

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.