;; The Triumph of the Median ;; http://lesswrong.com/lw/isk/a_voting_puzzle_some_political_science_and_a_nerd/ ;; And originally from Sideways Stories from Wayside School by Louis Sachar ;; The students have Mrs. Jewl's class have been given the privilege ;; of voting on the height of the school's new flagpole. She has each ;; of them write down what they think would be the best height for the ;; flagpole. The votes are distributed as follows: ;; 1 student votes for 6 feet. ;; 1 student votes for 10 feet. ;; 7 students vote for 25 feet. ;; 1 student votes for 30 feet. ;; 2 students vote for 50 feet. ;; 2 students vote for 60 feet. ;; 1 student votes for 65 feet. ;; 3 students vote for 75 feet. ;; 1 student votes for 80 feet, 6 inches. ;; 4 students vote for 85 feet. ;; 1 student votes for 91 feet. ;; 5 students vote for 100 feet. ;; At first, Mrs. Jewls declares 25 feet the winning answer, but one ;; of the students who voted for 100 feet convinces her there should ;; be a runoff between 25 feet and 100 feet. In the runoff, each ;; student votes for the height closest to their original answer. But ;; after that round of voting, one of the students who voted for 85 ;; feet wants their turn, so 85 feet goes up against the winner of the ;; previous round of voting, and the students vote the same way, with ;; each student voting for the height closest to their original ;; answer. Then the same thing happens again with the 50 foot ;; option. And so on, with each number, again and again, "very much ;; like a game of tether ball." ;; Question: if this process continues until it settles on an answer ;; that can't be beaten by any other answer, how tall will the new ;; flagpole be? ;; The most interesting part of this problem is to work out an incantation in emacs ;; that can turn ;; 1 student votes for 6 feet. ;; 1 student votes for 10 feet. ;; 7 students vote for 25 feet. ;; 1 student votes for 30 feet. ;; 2 students vote for 50 feet. ;; 2 students vote for 60 feet. ;; 1 student votes for 65 feet. ;; 3 students vote for 75 feet. ;; 1 student votes for 80 feet, 6 inches. ;; 4 students vote for 85 feet. ;; 1 student votes for 91 feet. ;; 5 students vote for 100 feet. ;; into (def votes (concat (repeat 1,6) (repeat 1,10) (repeat 7,25) (repeat 1,30) (repeat 2,50) (repeat 2,60) (repeat 1,65) (repeat 3,75) (repeat 1,80.5) (repeat 4,85) (repeat 1,91) (repeat 5,100))) ;; which I leave as an exercise to the reader. ;; the lucky winner is 25 feet, with seven votes, and 100 feet getting 5 votes (reverse (sort-by second (frequencies votes))) ;-> ([25 7] [100 5] [85 4] [75 3] [60 2] [50 2] [30 1] [91 1] [10 1] [6 1] [65 1] [80.5 1]) ;; how do we do a run off between two options? ;; firstly let's ask whether a single voter would prefer option 1 (defn closer [vote option1 option2] (< (Math/abs (- option1 vote)) (Math/abs (- option2 vote)))) (closer 26 25 100) ;-> true (one who likes 26 prefers 25 to 100) (closer 50 25 100) ;-> true (closer 75 25 100) ;-> false (one who prefers 75 prefers 100 over 25) ;; given this choice between 100 and 25, how many prefer 25? (frequencies (map (fn[x] (closer x 25 100)) votes)) ;-> {true 14, false 15} ;; So 100 is (just) stable against challenges from 25 ;; But although 100 survived the challenge from 25, it still has to face ;; a second challenge from partisans of 85 (defn winner [incumbent challenger votes] (let [v (frequencies (map (fn[x] (closer x incumbent challenger)) votes))] (if (< (v false 0) (v true 0)) incumbent challenger))) (winner 25 100 votes) ;-> 100 (winner 85 100 votes) ;-> 85 ;; Now 50 gets its turn.... (winner 50 85 votes) ;-> 50 ;; as do all the other attempts (distinct votes) ;-> (6 10 25 30 50 60 65 75 80.5 85 91 100) ;; fifty can survive a lot of challenges but eventually 65 can beat it. (reductions (fn [a b] (winner a b votes)) 50 (distinct votes)) ;-> (50 50 50 50 50 50 60 65 65 65 65 65 65) ;; but 65 can survive any challenge (reductions (fn [a b] (winner a b votes)) 65 (distinct votes)) ;-> (65 65 65 65 65 65 65 65 65 65 65 65 65) ;; But it's not at all clear that this outcome is inevitable (reduce (fn [a b] (winner a b votes)) (rand-nth votes) (shuffle votes)) ;-> 65 ;; Careful examination of various possible run-offs shows that (for [a (distinct votes)] (for [b (distinct votes)] (winner a b votes))) ((6 10 25 30 50 60 65 75 80.5 85 91 100) (10 10 25 30 50 60 65 75 80.5 85 91 100) (25 25 25 30 50 60 65 75 80.5 85 91 100) (30 30 30 30 50 60 65 75 80.5 85 91 100) (50 50 50 50 50 60 65 75 50 50 50 50) (60 60 60 60 60 60 65 60 60 60 60 60) (65 65 65 65 65 65 65 65 65 65 65 65) (75 75 75 75 75 60 65 75 75 75 75 75) (80.5 80.5 80.5 80.5 50 60 65 75 80.5 80.5 80.5 80.5) (85 85 85 85 50 60 65 75 80.5 85 85 85) (91 91 91 91 50 60 65 75 80.5 85 91 91) (100 100 100 30 50 60 65 75 80.5 85 91 100)) (count votes) ;-> 29 ;; There's an easier way to get this answer: (def m (quot 29 2)) (nth (sort votes) m) ;; The votes will settle on the median. By symmetry I imagine that if ;; there were an even number of people there might be two stable ;; answers, and whichever got picked first would win forever. ;; This sort-of-explains why: ;; (a) Two ice-cream stalls will set up right next to each other in ;; the middle of a beach, rather than far apart ;; (b) Political parties in a democracy end up having very similar ;; views, which means that voters get no effective choice in an ;; election, whilst nevertheless getting a government that is ;; reasonably in tune with the popular mood.

## Search This Blog

## Tuesday, October 22, 2013

### The Triumph of the Median

Subscribe to:
Post Comments (Atom)

If (winner 85 100 votes) ;-> 85

ReplyDeletethen the next call should not be (winner 50 100 votes), but (winner 50 85 votes)

per your problem description.

Well spotted! Thanks. Fixed it.

Delete