6

This is an open ended question in that the desired end result is not well posed. Still, it may be of some interest.

Suppose you have a number of teams which play against each other in two team competitions (all pairings occur with equal likehood, no ties allowed). Let $P(A,B)$ be the probability that A triumphs in a match between A and B. Clearly, if you know all the $P(A,B)$ you can compute the team average $P(A)$, the probability that A will win against an unknown opponent. You can't go the other way, though. To see this, look at 3 teams $A,B,C$ and suppose $P(A) = P(B) = P(C) = \frac{1}{2}$. One way we might have gotten this outcome is if $P(X,Y) = \frac{1}{2}$ for any pair of teams X,Y. In some vague sense, I suppose this is the "most natural" guess. But it is not the only possibility. We might, for instance, be in "Rock, Paper, Scissors" world, where A always beats B, B always beats C, and C always beats A.

The Question: Given all the P(A), is there a reasonably natural way to produce a list of probabilities P(A, *)?

Of course the probabilities must be consistent (so that the list of P(A,B)'s does imply the given list of team averages).

Sample attempt: attach a "greatness factor" $\lambda_i$ to each team and then define $$P(A_i,A_j) = .5 + \lambda_i - \lambda_j$$ You can even make the $\lambda$'s sum to 1. This is easily computable and gives plausible results so long as all the team averages are reasonably near .5. In more extreme cases, though, you get unphysical results (probabilities greater than 1 and so on). For baseball statistics, where this problem first arose, this crude method works fairly well.

Absent any actual ideas, my impulse is to minimize variance. That is: "choose the solution which is as nearly constant as possible." That is obviously one way to go, but perhaps someone has a better idea?

nonuser
  • 90,026
lulu
  • 70,402
  • @Alex: That last sentence isn't right; that would indeed make the problem trivial. It's interesting because of the constraint $P(A,B)+P(B,A)=1$. (Also, your equation seems confusing -- are you using $P(A)$ to mean the probability that $A$ wins but $P(B)$ to mean the probability that $B$ is chosen as $A$'s opponent?) – joriki Jul 12 '15 at 19:42
  • @joriki Exactly. Constant solutions obviously don't work in general. Minimum variance works tautologically, because you confine yourself to the space of solutions. – lulu Jul 12 '15 at 19:47
  • @joriki,@lulu: OK that's a lot clearer, thanks! – Alex R. Jul 12 '15 at 20:17
  • @Alex R. No problem. to be clear, I don't know anything specifically wrong with "minimal variance" as a solution, it just seems unsatisfying. I'd prefer a set of fair assumptions (like: "P(A) > P(B) $\Rightarrow$ P(A,B) > $\frac{1}{2}$") which specified a result (or narrowed the range). – lulu Jul 12 '15 at 20:26

2 Answers2

3

Your solution $P(A_i,A_j) = .5 + \lambda_i - \lambda_j$ is the stationary point of $\sum_{ij}(P(A_i,A_j)-.5)^2$ under the given equality constraints. (I guess that's how you derived it, so it's no coincidence that your "greatness factors" look like Lagrange parameters :-)

However, this is not the solution to the complete problem, since we also have the inequality constraints $0\le P(A_i,A_j)\le1$. You mentioned that these are not automatically satisfied, but to solve the problem of minimizing the objective function under the given constraints, we have to make them satisfied.

This would generally be a quadratic programming problem, but I suspect that in the present case you can get away with simply deactivating the variables one by one. I haven't tried this, but the prescription would be: Calculate $P(A_i,A_j) = .5 + \lambda_i - \lambda_j$, determining the $\lambda_i$ up to an additive constant from the equality contraints: $\lambda_i=P(A_i)-.5+\left<\lambda_j\right>_{j\ne i}$. Set all negative probabilities to $0$ (and thus, by symmetry, all that are above $1$ to $1$). Then recalculate the $\lambda_i$; but now the $P(A_i,A_j)$ that hit the inequality constraints are no longer given by $.5+\lambda_i-\lambda_j$, but by their fixed values $0$/$1$. So you get a different system of equations for $\lambda_i$. If you're lucky, solving it and recalculating the probabilities will lead to the same probabilities exceeding the constraints, and then you're done. If not, you can either iterate until you get consistency, or if that doesn't work, use a proper quadratic programming algorithm. In any case, in the end you'll find the solution to your minimization problem under the given constraints.

My personal favorite, by the way, for a "natural" determination of the pairwise probabilities, would be to model a team's performance in any of their games by a Gaussian, with identical variances for all teams but different means. Then you have $n$ parameters (the means) to fit to the $n$ given data (the $P(A_i)$), with one "zero mode" in each (the probabilities have to average to $.5$ and shifting all the means by an additive constant makes no difference). The fitting isn't as nicely linear as in your approach, and I'm not even sure there would always be a solution, but if there is, then it gives you a nice model that to me feels closer to how a game is actually decided than the "greatness factors".

joriki
  • 238,052
  • Ha! In practice I have adopted the "absorbing model" you propose as a way to improve the simple handicapping method (which was indeed arrived at in the manner you suggest). I have been widely mocked for doing so, which is why I began this comment with "Ha!". I have tried the Gaussian model you suggest, but it needs tinkering too...and in practice it doesn't differ much from the crude method. As you probably imagine, I prefer the "greatness" method because it gives me an easy handle to hold on to. I'm reluctant to let go of that... – lulu Jul 12 '15 at 21:20
  • I'll revisit the Gaussian approach. Thanks. But is it really intuitive? Would it not be more natural to assume a stable mean but a variable variance? Granted the latter is more difficult to model, but doesn't that better capture the feeling of wildcard games? – lulu Jul 12 '15 at 21:27
  • @lulu: Not sure what you mean by "stable". If you mean constant across teams, that would make all the pairwise probabilities $.5$, independent of the variances. If you mean constant across time: I didn't suggest to make the mean depend on time, just to have a different mean per team, but the same in every game. – joriki Jul 12 '15 at 21:34
  • @lulu: Since you've actually been doing this: Was I right in thinking that you get consistency after one iteration? Or after a few iterations? Or did you have to do proper quadratic programming? – joriki Jul 12 '15 at 21:37
  • I did proper quadratic programming, though perhaps out of habit rather than necessity. In practice, as you suggest, consistency is easily obtained. That's what made me imagine (hope?) that there was a principle in play rather than just the fact that, in practice, things are relatively even. As to the Gaussian, I withdraw my comment until I can revisit (in truth, I have forgotten how it plays out). – lulu Jul 12 '15 at 21:40
  • 1
    As I think you understand, I am looking for tactile parameters here. I like the Lagrange style numbers but they do let you down...even for basketball, say, where an average of 650 is not unheard of. I gave up on the Gaussian model in the past because I felt it didn't add enough but you have inspired me to revisit it properly. – lulu Jul 12 '15 at 21:54
  • I'm curious: do you have a precise objection to "minimal variance"? – lulu Jul 12 '15 at 21:59
  • @lulu: I wouldn't call it precise. I studied physics; I guess that may have given me a preference for models that give you an idea how something works, what "the mechanism behind it" is, over abstract principles, but who knows why we prefer what we prefer... To my mind, the variance thing is "just" a principle, even if you can give some a posteriori meaning to the Lagrange parameters, whereas the Gaussian thing is something I came up with trying to capture the basics of what determines the outcomes of games -- the sort of things one does in physics. – joriki Jul 12 '15 at 22:04
  • @joriki: The approach with gaussian distributions also convinces me, but i think that one has to understand the "right" variance to use in order to get a sensible result. Maybe a resonable choice is to use $P(A)^2+P(B)^2+P(C)^2$. – Capublanca Jul 12 '15 at 22:17
  • 1
    @Capublanca: The result is independent of the variance; the variance just sets the scale for the differences between the means. A solution for variance $\sigma^2$ is transformed to a solution for variance $(2\sigma)^2$ by scaling up the means by a factor of $2$. – joriki Jul 12 '15 at 22:19
  • @joriki: yes, you are completely right! – Capublanca Jul 12 '15 at 22:22
0

The Gaussian performance model of joriki seems nice, but a little expensive computationally. In contrast the additional constraints of the greatness model make it a little unwieldy.

I've previously used a model of the form,

$$ P(A,B) = \frac{\lambda_A}{\lambda_A+\lambda_B} $$

with the additional constraints that $\lambda_X > 0$ and $\sum\lambda_X =1$ (needed since scaling all $\lambda_X$ by a constant gives the same probabilities).

Note: I was not doing exactly the same as you, I was trying to estimate the $P(A,B)$ from a limited number of observations (and used a maximum likelihood method), so I'm not certain this form will lead to anything solvable analytically, or even produce nice results for your data.

Michael Anderson
  • 526