Suppose there are $N$ people in a two-person game (in my case, Super Smash Bros. Melee), and imagine a simple model where the players have "skill levels" $s_i\in\mathbb{R}$ for $1\leq i\leq N$, and the probability person $i$ will win a game over person $j$ is

$$ \mathbb{P}(i\text{ wins over }j)=\sigma(s_i-s_j) $$

where $\sigma:\mathbb{R}\rightarrow[0,1]$ is some monotonically-increasing function.

Since $\mathbb{P}(j\text{ wins over }i)=1-\mathbb{P}(i\text{ wins over }j)$, the only constraint on $\sigma$ is that

$$ \sigma(x)+\sigma(-x)=1. $$

The logistic sigmoid is one choice satisfying this.

Note the probability of player $i$ having $w$ wins and $l$ losses over player $j$ is binomial-distributed,

$$ \mathbb{P}(i\text{ has }w\text{ wins, }l\text{ losses over }j)=\binom{l+w}{w} \left(1-\sigma \left(s_i-s_j\right)\right){}^l \sigma \left(s_i-s_j\right){}^w. $$

Now suppose further that we've observed a number of matches between players, with $w(i,j)$ and $\ell(i,j)$ the number of times player $i$ won and lost against player $j$. From these matches, I'd like to estimate the $s_i$, which initially are assumed distributed via some uninformative Bayesian prior $\mathbb{P}(s_i,\ldots,s_N)$.

By Bayes Theorem, we can obtain the posterior distribution of the $s_i$ by

$$ \mathbb{P}(s_i,\ldots,s_N|\text{observed matches}) = \frac{\mathbb{P}(\text{observed matches}|s_i,\ldots,s_N)\mathbb{P}(s_i,\ldots,s_N)}{C} \\ =\frac{\mathbb{P}(s_i,\ldots,s_N)}{C}\prod_{i=1}^N\prod_{j=1}^N\binom{l(i,j)+w(i,j)}{w(i,j)} \left(1-\sigma \left(s_i-s_j\right)\right){}^{l(i,j)} \sigma \left(s_i-s_j\right){}^{w(i,j)} $$

where $C=\int_{\mathbb{R}^N}\mathbb{P}(\text{observed matches}|s_i,\ldots,s_N)\mathbb{P}(s_i,\ldots,s_N)\,\mathrm{d}\mathbf{s}$ is a constant normalization factor that I'm ignoring.

I'm stuck here. In my use case, the number of players $N\approx 5000$ and the number of games $\frac{1}{2}\sum_{i,j}w(i,j)+l(i,j)\approx 100000$ (game data obtained via the Smash GG API's history of tournament matches from the past 3 years), and the posterior distribution is not (as best I can tell) separable. As a result, the problem as stated appears computationally intractable.

My question is this:

  • What tricks are commonly used to make high-dimensional Bayesian posteriors like this computationally tractable? Are there approximations I can apply to make it separable?
  • $\begingroup$ check out pymc. It can handle something like this via hamiltonian mcmc. You can also opt in for variational inference as well as an input into the model. github.com/CamDavidsonPilon/… $\endgroup$ – EDZ Feb 26 '18 at 5:05
  • $\begingroup$ Is this model identifiable? Supposing you have three players, i, j, and k, then \begin{equation} \begin{split} P[i\rightarrow j] & = \sigma(s_i - s_j) \\ & = \sigma((s_i + r) - (s_j + r)) \\ & = 1 - \sigma((s_j + r) -(s_i + r)) \\ & = 1 - \sigma(s_j -s_i ) \\ & = 1 -P[j\rightarrow i] \end{split} \end{equation} for any $r \in \mathbb{R}$. These probabilities also stay consistent for $s_k$ shifted by $r$. $\endgroup$ – Ryan Warnick Mar 1 '18 at 22:45
  • $\begingroup$ Additionally, I think you are using the data twice in that the product is over $ i \in \{1,..,N\} \times j \in \{1,...,N\} $ and not $i\neq j$. This is a problem because the likelihood evaluating $\mathcal{L}(w(i,j)) = \binom{l(i,j) + w(i,j)}{w(i,j)} (1-p_{ij})^{l(i,j)}p_{ij}^{w(i,j)})$ is the same as evaluating $\mathcal{L}(w(i,j)) = \binom{l(j,i) + w(j,i)}{w(i,j)} p_{ji}^{w(j,i)}(1-p_{ji})^{l(j,i)})$ By symmetry of the choose function this is equal to $\mathcal{L}(w(j,i)) = \binom{l(j,i) + w(j,i)}{w(j,i)=l(i,j)} p_{ji}^{w(j,i)}(1-p_{ji})^{l(j,i)})$ $\endgroup$ – Ryan Warnick Mar 1 '18 at 22:56
  • $\begingroup$ @RyanWarnick You're right, I double-counted. You're also right that the model predictions are invariant under $s_i\rightarrow s_i+r$ for all $r\in\mathbb{R}$, so the model is underspecified. For that reason, my earlier non-Bayesian approach using linear softmax fitting used a cost function that included an $L_2$-regularization cost $\Omega(\mathbf{s})=|\mathbf{s}|^2$, which makes the parameters fully specified since it forces the $s_i$ to cluster around 0. $\endgroup$ – Peter Richter Mar 2 '18 at 6:00
  • $\begingroup$ @EDZ Thanks, that looks promising! $\endgroup$ – Peter Richter Mar 2 '18 at 6:00

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.