Facematch Puzzle

I saw the movie The Social Network about a week ago. It was quite good, I might add. As those who saw the movie will know, while still a Harvard student, Facebook creator Mark Zuckerberg created a site in which he posted pairs of pictures of female Harvard students and asked student to rank which one was more attractive. The object, I think, was to give each girl a rating, as judged by the users of the site.

It got me to thinking. Suppose you had a x such pictures, and wished to sort them in attractiveness order yourself. What would be the most efficient strategy? You are limited to comparing two pictures at a time. I'm open to how "efficient" should be defined, but I would suggest minimizing either expected matches required, or maximum matches.

I'll hold off on posting my strategy for the moment. However the following table will show the minimum and maximum number of pairings it would produce.

Faces	Min matches	Max matches
2	1	1
4	5	5
8	15	20
16	49	76
32	169	288
64	609	1104
128	2273	4288
256	8705	16832
512	33921	66560
1024	133633	264448
2048	529921	1053696
4096	2109441	4205568
8192	8415233	16801792
16384	33611777	67162112

I would expect that in this type of subjective ranking/sorting, the issue of consistency would be more problematic than the issue of efficiency. By this I mean that if I rank A higher than B and B higher than C, I am still not certain that I would necessarily rank A higher than C in a direct comparison.

Edit: Or that I would necessarily rank A higher than B if I repeated the comparison.

I may not understand what is required, but looking at your table.

Suppose we have 3 (A,B,C)-I would compare AB and put them in order. I would then compare C to the best (most attractive), assuming it was A, if C is more attractive then I would have my minimum matches (2), with CAB order, if C was not more attractive then I would compare CB an put them in order for a max match number of 3.

Now for four (A,B,C,D). I would take the same strategy. Compare AB, put them in order and compare C to the best (assume A), if C most attractive, then my order is CAB (at this point), I then would compare D to C, If D more attactive my work is done with a minimum 3 matches and a DCAB order. If D is not more attractive I would compare D to A, if more attractive then my work is done (4 matches), with an order of CDAB, if not then a 5th match will determine the DB order.

I would do the same strategy with more faces. It seems it is possible that the minimum could be the number of faces minus 1, however improbable.

Quote: Wizard

It got me to thinking. Suppose you had a x such pictures, and wished to sort them in attractiveness order yourself. What would be the most efficient strategy? You are limited to comparing two pictures at a time. I'm open to how "efficient" should be defined, but I would suggest minimizing either expected matches required, or maximum matches.

You're asking about sorting algorithms and computational complexity, two fundamental topics in computer science. Start here:

http://en.wikipedia.org/wiki/Sorting_algorithm

"Efficiency" depends on several factors like whether you care more about runtime or storage space, or what you know about your data (e.g. is it nearly-sorted or very out-of-order).

More info: the presumption in your question is that you have a collection of N objects and a binary-comparison function f(a, b) which returns >0 if a > b, 0 if a == b, and <0 if a < b. If you don't have that, for example you sometimes rank a > b and other times a < b (entirely possible when dealing with "attractiveness"), then it's a different problem that doesn't map well to existing algorithms.

This is only slightly related to the original question, but, I believe that attractiveness is normally distributed. If average attractiveness is a 5 out of 10, I believe the standard deviation is 1.5. I think 95% of people fall into the 2-8 category. Meaning that only 1 in 40 women would really be considered a 9 or a 10.

My wife asked me what she was. I told her that of course she's a 10.

Quote: MathExtremist

You're asking about sorting algorithms and computational complexity, two fundamental topics in computer science. Start here:

http://en.wikipedia.org/wiki/Sorting_algorithm...

Thanks, good answer. I was trying to do something like a merge sort, but my method was not optimal. I'll need some more time, but hope to answer my own question tomorrow.

Quote: MathExtremist

... the presumption in your question is that you have a collection of N objects and a binary-comparison function f(a, b) which returns >0 if a > b, 0 if a == b, and <0 if a < b. If you don't have that, for example you sometimes rank a > b and other times a < b (entirely possible when dealing with "attractiveness"), then it's a different problem that doesn't map well to existing algorithms.

Hmmm. I think that just might be the mathematician's way of saying what I tried to convey about the issue of consistency in my earlier post. Or did I misunderstand once again?

This seems so obvious to me. And I can do it without getting all mathy:

Take two pictures. Rank them in order of attractiveness.

Take the third picture, and compare it to the bottom picture. If Pic 3 is lower in attractiveness than the bottom picture, put it at the bottom. If higher, compare it to the top picture, and place Pic 3 either in the middle or above the top picture, according to the results of the comparison. You now have three pictures in ranked order.

Take Pic 4 and compare it to the middle picture. This will tell you whether to move it up or down. In each case, compare it to the next picture in the relevant direction, and use that comparison to place Pic 4 either between the middle and that pic, or at the top or bottom. You now have four ranked pics.

Repeat this procedure with each successive pic, starting as close to the middle as possible. If a given comparison preserves the existing position of the new pic, leave that pic there. For example:

Seven pics have been ranked. Take Pic 8 and compare it to the fourth-ranked pic. If it is more attractive, compare it to the third-ranked pic. Repeat until the pic stops moving up, then place the pic in that position. Same procedure if the initial comparison shows the new pic to be less attractive than the middle pic; keep moving down until it stops, then place the new pic in that position.

No math necessary.

Quote: mkl654321

This seems so obvious to me. And I can do it without getting all mathy...

That is an acceptable way to do it. It would be more efficient than the standard bubble sort. However, the question is can you prove it minimizes the expected or maximum number of comparisons?

Quote: Wizard

That is an acceptable way to do it. It would be more efficient than the standard bubble sort. However, the question is can you prove it minimizes the expected or maximum number of comparisons?

Not mathematically, but it would seem that making each new placement by comparing that picture with the current middle-ranking picture, and then moving up or down as needed, would minimize the number of comparisons, as any new entrant is most likely to wind up as near the middle of the existing group as possible (if there are eight existing ranked pictures, the new picture would be more likely to wind up #5 in the resultant group of nine than in any other position).

To put it another way, a comparison with the middle of the existing group gives the most information; comparing a new entrant with the top or the bottom ranking picture gives minimum information; so the optimal comparison method is to start in the middle.