# Predicting the winner of a contest, given history

In one of the online games I play, there's a daily contest where users can make bets. I'm hoping I can place more profitable bets by analyzing the contest's history :) (Though really I just wanna crack this problem; it's been bugging me for a while xP)

Here's what we know about the contest:

• 4 NPC players (that is, automated, not real people) enter the contest each day.
• There are 4 features associated with each player, made public at the start of the day.
• Let $F(p, f)$ be the value of feature $f$ for player $p$.
• For example, $F(1, 1)$ might be how hungry player 1 is, and $F(2, 1)$ is how hungry player 2 is.
• At the end of the day, betting is closed and one of the 4 players is announced as the winner. No other information regarding the contest's outcome is available.
• (There's more to say about odds and how bets work, but, for now, I'm just interested in the subproblem of computing each player's probability of winning.)

Now, here's what I hypothesize happens behind the scenes:

• There is some secret function $S(p)$ that computes the "score" of each player.
• $S(p)$ is a linear function of player $p$'s features.
• That is, $S(p) = c_1 F(1, 1) + c_2 F(1, 2) + c_3 F(1, 3) + c_4 F(1, 4)$.
• These scores are normalized into probability of winning.
• That is, $P(\text{player 1 wins}) = \dfrac{S(1)}{S(1)+S(2)+S(3)+S(4)}$.

Given a large set of historical contests, how can I infer the coefficients of $S(p)$?

If each player's scores were revealed at the end of the day, I could do a pretty straightforward linear regression. But they're not; could I maybe infer the scores somehow? My gut says you could kinda get there from looking at a particular feature vector's historical win/lose ratio, but I'm not sure how to take the normalization into account.

I'm also not sure whether inferring scores would even be effective. Most feature vectors only occur a handful of times, so I wouldn't be confident in the inferred score, and therefore would be hesitant to trust the coefficients we derive. (Note that the rarity of some feature vectors is why I even care about deriving the coefficients. Never-before-seen feature vectors arise often, and I want to be able to evaluate a vector the very first time I see it, rather than relying on its individual history.)

• May be of interest: en.wikipedia.org/wiki/TrueSkill – conjectures Jul 14 '15 at 22:42
• Hmm, I do like that :) I think our problem can probably be solved more directly, though, since the players in the contests are NPCs, and the features really are just 4 numerical stats that describe each player rather than some features that I've inferred. Still, I wonder how well something like TrueSkill would do... if we didn't have the feature vectors and just the NPC identities, probably pretty darn well, eh? – Matchu Jul 15 '15 at 4:43
• There are some more in depth lecture slides on it at: mlg.eng.cam.ac.uk/teaching/4f13/1415 – conjectures Jul 15 '15 at 9:19
• It sounds like you first need to estimate $S(p)$ based on the linear function you've provided and then go on to calculate $P(win_{p_1})$. This feels like a generalized additive model. See the Element of Statistical Learning by Hastie, Tibshirani, and Friedman, Chapter 9. – StatsStudent Jul 17 '15 at 14:34

Let's accept your hypotheses that the score function is linear in the features and that the coefficients do not change. You'd like to find the most likely tuple of coefficients $c$ given the records at hand.

If we consider that the daily contests are independent, we can do something similar to a maximum likelihood estimation.
The likelihood of observing all the records in history if we consider that we are given $c$ is: $$\mathcal{L}(c;records) = P(records | c) = \prod_{r \in records} P(r|c)\\ \mathcal{L}(c;records) = \prod_{r \in records} S_{normalized}(winner(r), r)$$ Where $winner(r)$ is the player who won in the record $r$.
The maximum likelihood estimator for $c$ would then be: $$c = (c_1, c_2, c_3, c_4) = \underset{c}{argmax}(\mathcal{L}(c; records)) = \underset{c}{argmax} (\prod_{r \in records} S_{normalized}(winner(r), r))$$

Where $S_{normalized} (p) = \frac{S(p)}{\underset{q \in players}{\sum S(q)}}$ which is $P(player\ p\ wins)$ in your post.

You could compute this estimator by doing a gradient descent or another optimization technique on the likelihood function. Though the function is not differentiable everywhere, I'd say everything could still be fine with a gradient descent ;).

If you don't mind linking to part of your data we could try and look further into it.

Let me know if something does not make sense to you.

• Sweet, thanks! I'll read over this when I get the chance—I'm realizing that I'm not sure I actually have time to really pursue this project right now, but I'll ping you when I get back to it :) – Matchu Jul 17 '15 at 3:26
• Ok. This may look sophisticated if you are not familiar with the notations but it is actually fairly simple to implement. – ldirer Jul 17 '15 at 7:56
• Yeah, I remember enough from stats class to recognize it, but not enough to analyze it on the fly to confirm that it matches my mental model of the problem. Once I parse it all I'll let you know xP Thanks! – Matchu Jul 17 '15 at 14:07
• Actually, I think $P(r|c)$ might be more nuanced than that. The player with the highest score doesn't automatically win; instead, the scores are weights that normalize into probability of winning. For example, if the 4 players' scores are 2, 4, 6, and 8, then their respective chances of winning are 10%, 20%, 30%, and 40%. I don't think that changes the fundamentals of your answer, though: just plug in that definition instead, and we can do whatever local search strategy we want. Cool :D – Matchu Jul 17 '15 at 14:10
• Woops you're right. I used S(p) instead of the normalized score. – ldirer Jul 17 '15 at 14:13