4 ms·
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 t
by mitko 6y ago
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.
- pronoiac 6y agoI'm guessing this comment is about puzzle 13?
- vitus 6y agoI'd expect this to be about the Caterer's Problem (i.e. the current problem, which shows up on the linked page).
- vitus 6y agoI 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 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.
- deleted 6y ago[deleted]
- ikeboy 6y agoYes, 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.