2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ May be of interest: en.wikipedia.org/wiki/TrueSkill $\endgroup$ – conjectures Jul 14 '15 at 22:42
  • 1
    $\begingroup$ 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? $\endgroup$ – Matchu Jul 15 '15 at 4:43
  • $\begingroup$ There are some more in depth lecture slides on it at: mlg.eng.cam.ac.uk/teaching/4f13/1415 $\endgroup$ – conjectures Jul 15 '15 at 9:19
  • $\begingroup$ 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. $\endgroup$ – StatsStudent Jul 17 '15 at 14:34
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – Matchu Jul 17 '15 at 3:26
  • $\begingroup$ Ok. This may look sophisticated if you are not familiar with the notations but it is actually fairly simple to implement. $\endgroup$ – ldirer Jul 17 '15 at 7:56
  • $\begingroup$ 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! $\endgroup$ – Matchu Jul 17 '15 at 14:07
  • $\begingroup$ 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 $\endgroup$ – Matchu Jul 17 '15 at 14:10
  • $\begingroup$ Woops you're right. I used S(p) instead of the normalized score. $\endgroup$ – ldirer Jul 17 '15 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.