Hacker News Reader

Comment by mitko | Hacker News Reader

I wonder if Arrows Impossibility Theorem has something to do with the puzzle.

My money on that it is possible to solve it without knowing AIT and most likely there is a way to construct a counter example using a script.

View on HN

I think the 1024 (2^10) count is more important. We're not really looking for a community-wide preference -- instead, we're essentially looking to identify the size of the biggest possible Smith set [0], as defined for Condorcet methods.

[0] https://en.wikipedia.org/wiki/Smith_set

(This is nominally different from the general "smallest dominating set" problem, in that we have the preference ordering constraints.)

I'd expect the solution to somehow turn the selection process into a binary search so that each element in L is chosen such that (at least) half of the remaining people must satisfy some criterion. But, I haven't thought through exactly how that'd work.

Yes, that's almost exactly how it works. First option can be chosen to beat at least 511 others, second option to beat 255 others of the remaining, and so on. Just add up total number of group preferences among each subset and divide by number of options to show that.

The number of people is irrelevant. This works with a million people just as well. Ignore people, only look at group pairwise preferences.

I'm guessing this comment is about puzzle 13?

I'd expect this to be about the Caterer's Problem (i.e. the current problem, which shows up on the linked page).

Reply on news.ycombinator.com