The Algorithm for Facemash in The Social Network

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

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 look math-y enough for the brief moment they are onscreen.
3) I’m misconstruing the E and/or R terms.

I’m interested, because I happen to be building a number of websites that use a “bake-off” method very similar to that of Facemash. Currently, I’m working on Lepidoptera – an online to-do list with bake-off priority contests.

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.

Anyone else interested in figuring this out? Leave me comments or blog back.

About these ads

31 thoughts on “The Algorithm for Facemash in The Social Network

  1. Pingback: UPDATE: The Algorithm for Facemash in The Social Network « The Shotgun Approach

  2. Haseeb

    Your recollection of the equation is fairly accurate. the * 400 is instead divided by 400. Everyone starts off at a rating of 1400, which I assume is the number of total girls that Mark has in the data base. Now suppose girl A and girl B battle it out in cyberspace, their fate decided by the click of testosterone fueled horny Harvard guy late on a Friday night with no gf. The guy chooses girl A. Ea and Eb are now both 1 (assign 1400 to both Rb and Ra). The question is, how do these values of Ea and Eb change. The second part of the equation is not shown on the Social Network.
    Rnew = R + C1 * ( W – E )
    C1 is a measure of how conservative or dynamic the rating system is (does a single event have a high likelihood of changing the existing rankings)
    W measures the performance of the player. Assign 100% for a win, and 0% for a loss. E is either Eb, or Ea, depending on which players new rating we are calculating. The losing players rating will decrease, while the winning players rating will stay the same (assuming they both started out with exactly the same rating, both ratings will change if players start out with ratings that are at all different). The highest rated girl is ranked the highest.
    The beauty of the game as set up in Facesmash is that you have the opportunity to have the game played a lot of times, and the ability to set up players (girls faces) at random. This would give an extremely accurate ranking of whose girls face is really considered hot by the community of horny college guys.

  3. Mariano Tomatis

    Ea is the probability of “a” winning a match against “b”.
    The correct equations are:
    Ea = 1 / (1 + 10 ^ ((Rb-Ra)/400) )
    Eb = 1 / (1 + 10 ^ ((Ra-Rb)/400) )
    Being two probabilities, Ea+Eb=1

    Ra is the “rating” of “a”.
    As Haseeb well explained, the rating changes after every match, according to this formula:
    Ra(t+1) = Ra(t) + K * ( W – Ea )
    where W=1 if “a” wins / W=0 if “a” loses.
    The same for Rb.

  4. Rade

    Mariano, you said
    “Ra(t+1) = Ra(t) + K * ( W – Ea )
    where W=1 if “a” wins / W=0 if “a” loses.
    The same for Rb.”

    What is ‘t’ here?

  5. shotgunapproach Post author

    t is time. At time+1, the new rating of A is the old rating of A plus a constant multiplied by the delta.
    Ra(t+1) = new rating for A.
    Ra(t) = previous rating for A.
    K = constant – choose a lower number for more stable ratings, and a higher number for ratings that update more quickly.
    (W – Ea) = the delta. The actual outcome W minus the expected outcome Ea.

  6. Runal

    Please elaborate the Expectations part when the base for Ra, Rb is considered as “Zero”

    Thanks in advance

  7. a

    Inspired from Facemash, is there a desktop application that:
    1) Scans the pictures in a folder
    2) Shows two random pictures and asks me to choose which one I prefer
    3) The picture I prefer will be the winner and gets a higher rating (as in chess ratings), while the losing picture loses rating
    4) Repeats steps 2 and 3 indefinitely till it decides the ratings the pictures are accurate
    5) Sorts the images by their rating

  8. Terez

    Hi guys! Great break-down of the algorithm, thanx!:)
    Actually I am working on an application that will also calculate rating of e.g.person based on the “duel”. But in my application the total number of users from which I will pick two for the duel will increase during the time. So I have two problems… I dont know how should I set the initial score of a new user and how to handle the fact, that at a time some user had already been to e.g.500 duels and other only to 2 beacause he is new. I guess the only answer to the second problem would be to pick the users for duel based on number of duels they have already been in, in order to set more appropriate score as fast as possible. But it is not really desirable for my application to show one person to often.
    What would be your thoughs on this one…? Any feedback is appritiated. And I am sorry for my english:)
    Tereza

  9. a

    @Terez Use the algorithm used to calculate chess ratings. That was the same one used in facemash (at least according to the movie the social network).
    It is a proven algorithm and accurately tells you how good you are at chess. IIRC its starting rating is 1200

  10. Zunde

    In the movie, the guy wrote
    Ea = 1 / (1 + 10 (Rb-Ra)/400 )
    Eb = 1 / (1 + 10 (Ra-Rb)/400 )

    I was like, wtf there’s a division by zero !

    I guess in the true formula, the constants 10 and 400 can be changed.

    Also It’s weird the guy have to wait for his friend to get the “algorithm” (not an algorithm in fact, it’s a formula) whereas it can be easily found.(Thank god there’s no intellectual property on math theories).

  11. Carlos

    You can try this one from IMDB:

    http://www.imdb.com/chart/top

    The formula for calculating the Top Rated 250 Titles gives a true Bayesian estimate:

    weighted rating (WR) = (v ÷ (v+m)) × R + (m ÷ (v+m)) × C

    where:

    * R = average for the movie (mean) = (Rating)
    * v = number of votes for the movie = (votes)
    * m = minimum votes required to be listed in the Top 250 (currently 3000)
    * C = the mean vote across the whole report (currently 6.9)

    for the Top 250, only votes from regular voters are considered.

  12. Dec

    It’s a movie, so lots of Artistic License can be used to stretch the truth around the story.

    Zuck used wget to leech all the dorm facebook pics, when Curl would do a much better job for only a slightly more complex command line. Please don’t tell me that he actually used wget – I’ll have to delete my FB profile in disgust :-)

    Parker woke up in a strange bed, and took the credit for founding Napster, when really it was S. Fanning who did all the early work. Parker was there early on, sure, but the Fannings had got the company off the ground before he got involved.

    And one of the Winklevi compared thefacebook (a website with inherent parallel capacity) signing up so many users, to a drug dealer (limited parallel capacity even if you use both hands) trying to give free drugs away to the same amount of people in the same amount of time.

    Fincher and Sorkin never claimed this was a true-facts movie: they want the audience to decide where each character is, on the “good guy / bad guy” scale.

  13. Luke

    I don’t mean to sound retarded, but surely it’s easier to give each girl a rating of 0, and add 1 to their rating depending on the amount of ‘votes’ they get. The girl with the highest rating at the end wins.

  14. commonsense

    Could the same Algorithm be used to elect the next President!
    Could the same Algorithm be used to determine what is the best car?
    Could the same Algorithm be used to determine who painted the best painting in history?
    Could the same Algorithm be used to determine what people think the best is on every subject.
    About the only thing that came out of Facemash is the fact You can hack a website and obtain photos of people. As far as the Algorithm goes if you think it works let’s use it to determine what is the best for everything.

  15. shotgunapproach Post author

    @Luke Consider the case in which Girl X has participated in 100 faceoffs and won 6. Girl Y has participated in 5 faceoffs and won all 5. By your point system, Girl X scores 6 and wins out over Girl Y with her score of 5, when the evidence seems to suggest that Girl Y is probably prettier than Girl X.

    Your scoring system would work perfectly if we held a round-robin and every girl faced off against every other girl. Every contestant would have an equal number of faceoffs and have faced the same pool of opponents.

    The Elo algorithm (and similar algorithms) allows for good scoring when we can’t meet those two criteria. New contestants can be added at anytime and we don’t have to try to match the difficulty of the “playing field” for different contestants.

  16. shotgunapproach Post author

    @commonsense I’m not necessarily an advocate for the Elo rating system, although I think it is good enough for a lot of ordering problems. There are a lot of voting systems that are better than our current method of voting:
    http://en.wikipedia.org/wiki/Voting_system

    Although keep in mind the limitations pointed out by Arrow’s Theorem:
    http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem

    In general, I think more things can and should be presented as an ordered list. There will always be quibbles about the exact ordering, but a rough ordering is oftentimes very useful.

  17. Matt Smith

    Great post — thanks for putting it up. I’m building a new site using the Elo System, and your insights, along with the associated comments were very helpful. Thanks.

  18. Matt Smith

    Thanks for the e-mail follow up Jason.

    One question has come up: in Haseeb’s comment he said “The losing player’s rating will decrease, while the winning players rating will stay the same (assuming they both started out with exactly the same rating)”. I have not found this to be te case.

    When 2 items start at 1400, each having the same E (of 0.5), I’m finding that the loser’s rating goes down and the winner’s goes up, the magnitude being determined by the factor “K” or “C1″ (as it’s been called).

    Have I missed something in my implementation, or was Haseeb mistaken? In other words, should the winner’s score really remain the same if they started with the same score? The math doesn’t seem to support that idea.

    Example:

    Ra = 1400
    Fb = 1400

    Ea = 0.5
    Eb = 0.5

    Rnew (winner) = 1400 + K (1 – 0.5)
    = 1400 + 0.5k

    How can Rnew = Rold = 1400 ? This can only happen when K = 0 which it never will.

    Thanks.

  19. shotgunapproach Post author

    @Matt Smith, Your math is correct. The winning player’s rating will go up – as it should, given that he/she just defeated a player rated at that previous level. Maybe Haseeb may have been wanting to make another point and gotten confused. If Ea = Eb = 0.50 and the two players DRAW, neither rating will change.

  20. Matt Smith

    Thanks for the confirmation Jason. Just completed the initial version of the site using the Elo System. You can see it in action at http://www.beerversusbeer.com.

    Also, one thing I picked up from another discussion, many Elo implementations default a new player’s rating to the current average. After experimenting with it, I’ve found this is a good way to handle new players being added at anytime.

  21. Brady Moseson

    I was wondering if anyone could provide me with an elaborate code and tutorial for creating a Facemash. Mine currently isnt working because only one of the pictures shows up when i initiate my prep site of facemash. If someone knows how to do this i would greatly appreciate it. I would also enjoy to be able to place names above each picture that is displayed as i am doing it with pictures of students at my high school. You can email me @ bmose24@yahoo.com

  22. Pingback: Proposal : Final Project : Photography | One step forward, making two steps back

  23. thisismohit

    Yo whats up people…

    I figured out a much easier way to do this

    Where
    Sum = Ra + Rb
    Ea = Ra/Sum
    Eb = Rb/Sum

    The values differ a lil bit but they work

    For eg

    A’s rating is 1505 and b’s 1450 ;
    Sum = 1505 + 1450 = 2955

    Ea = 1505/2955 = 0.509
    Eb = 1450/2955 = 0.490

    What you all say ?

    Matter of fact i made a my version of facemash and made all the girls go crazy of my highschool in just 2 days my highschool was on fire lol . But the very next day my friends started to doubt me And some of the girls came in group to my house and they checked my laptop and i was caught shit and i was suspended for 3 months so dont try this website it will make all the girls hate u and the boys will envy you !!

Leave a Reply

Fill in your details below or click an icon to log in:

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