Using Algorithm in Social Media Movie

In the Facebook movie The Social Network, Mark Zuckerberg builds a website to compare the attractiveness of girls. Behind the scenes, developers made to believe, an algorithm originally developed to rank chess players is employed to rank these women by their attractiveness.

1292249449

The equations driving the algorithm are shown briefly, written on young Zuck’s dorm room window. From my (possibly incorrect) memory the two equations look like this:
Ea = 1/(1 + 10 * (Ra-Rb) * 400)
Eb = 1/(1 + 10 * (Rb-Ra) * 400)

My interpretation of the left hand of each equation is that these are expectations. I would assume Ea is the expectation that Girl A will win the match. Eb would thus be the expectation that Girl B would win. This is where my puzzlement with these equations begins. Surely Ea and Eb cannot be independently calculated.

My guess as to Ra and Rb are that these are the rates at which Girl A and Girl B have been winning their other matches. For example, if Girl A had won half her matches, Ra would be 0.50. Similarly, if Girl B has won only one of five matches, Rb would be 0.20.

That made sense to me for the brief moment it was displayed in the movie, but actually playing with the equations yields non-useful results. For example, assume Girl A has won 5 of 10 matches, and Ra is 0.50. Assume Girl B has won 2 of 8 matches, and Rb is 0.25. You might expect the algorithm to return something along the lines of Ea = .67 and Eb = .33. In other words, it is twice as likely that Girl A will win as compared to Girl B winning.

Instead the results are nonsensical. Ea = 0.000999 and Eb = -0.001001. Obviously, these cannot be interpreted as expectations/probabilities.

My guess is that one of the following issues is occurring:
1) My memory of the equations is incorrect.
2) The equations are gibberish – meant to loThe Social Network hacking sceneok math-y enough for the brief moment they are onscreen.
3) I’m misconstruing the E and/or R terms.

I searched for awhile for formal algorithms to perform ordering based on head-to-head contest results and came up empty. So the algorithm I use is based on my own best reasoning. I’d like to understand the Facemash algorithm so I can compare results.


If Player A has true strength “RA” and Player B has true strength “RB”, Elo’s original formula for the expected score of Player A is:

EA = 1 / (1 + (10^((RB - RA) / 400)))

Similarly the expected score for Player B is:

EB = 1 / (1 + (10^((RA - RB) / 400)))

You will note that EA + EB = 1. In practice, since the true strength of each player is unknown, the expected scores are calculated using the player’s current ratings.

As you can see, the IECC rating algorithm uses this idea, and calls it “Probability”.

Probability = 1 / (1 + (10 ^ -(Rating Difference / 400)))

When a player’s actual score exceeds his expected score, Elo’s system takes this as evidence that that player’s rating is too low, and needs to be adjusted upward. Similarly when a player’s actual score falls short of his expected score, that player’s rating is adjusted downward. Elo’s original suggestion, which is still widely used, was a simple linear adjustment proportional to the amount by which a player outperformed or underperformed his expected score.

The maximum possible adjustment per game can thus be set via a formula constant. For high rated players Elo suggested a maximum adjustment of 16 rating points, while for weaker players it was suggested a maximum adjustment of 32 be set.

Again the IECC uses Elo’s original idea and has set a maximum possible adjustment for players rated less than 2101 at 32. For players rated between 2100 and 2400 the maximum rating adjustment is 24, and for players rated higher than 2400 it is set at 16. These are the DeltaK values stated above.

So given that we have an expected score, and a DeltaK value for the player, we can calculate that players new rating. Elo proposed using the following:

New rating = RA + K(SA - EA)

Where SA is the actual points scored.


how-to-defend-yourself-against-hacking-on-any-device

Worked Example

Lets work through an example with the formulas. Suppose Player A has a rating of 1584. He loses to a player rated 2131. His expected score as calculated with:

EA = 1 / (1 + (10^((RB - RA) / 400)))

EA = 1 / (1 + (10^(547/400)))

EA = 1 / (1 + (10^(1.3675) ))

EA = 1 / (1 + (23.3077)

EA = 1 / 24.3077

EA = 0.04114

Therefore EB = 0.95886 (as we know EA + EB = 1). This in essence tells us, Player B would be expected to win approximately 24 from 25 games when playing against Player A.

Now we’ll enter these valves into Elo’s adjustment formula.

Player A:

New rating = RA + K(SA - EA)
New rating = 1584 + 32(0 - 0.04114)
New rating = 1584 + -1.31645
Or a negative adjustment of -1.31645 to the players rating.

Player B:

New rating = RA + K(SA - EA)
New rating = 2131 + 24(1 - 0.95886)
New rating = 2131 + 0.98735
Or a positive adjustment of 0.98374 to the players rating.

The IECC algorithm adheres to Elo’s ideas and produces:

White Adjustment = Int (WdeltaK * (Score - Probability) )
White Adjustment = Int ( 32 * (0 - (1 / (1 + (10 ^ -(Rating Difference / 400)))))
White Adjustment = Int ( 32 * (0 - (1 / (1 + (10^ -(-547/400)) ))))
White Adjustment = Int ( 32 * (0 - (1 / (1 + 23.3238))))
White Adjustment = Int ( 32 * (0 - (1 / (24.3238))))
White Adjustment = Int ( 32 * (-0.041111))
White Adjustment = Int (-1.31645)

Therefore White’s rating will be adjusted by -2. (Result rounded down to the lowest whole integer.)

Now Black’s adjustment is calculated.

Black Adjustment = Int (-1 * (White's Adjustment * BdeltaK / WdeltaK))
Black Adjustment = Int (-1 * (-2 * 24 / 32))
Black Adjustment = Int (-1 * (-2 * 24 / 32))
Black Adjustment = Int (-1 * (-1.5))
Black Adjustment = Int (1.5)
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s