Thursday, July 7, 2011

The Arrow of Fairness

The Arrow of Fairness

By Bobby Neal Winters
I have passed the age of eating chili late in the day without having to suffer dire consequences.  I am also beyond the point where I can watch very much in the way of politics right before I go to bed.  To be so stupid as to combine Frito Chili Pies with onions while watching election returns is almost beyond imagining, but I don’t have to imagine it because I actually did it.
The election coverage kept me up late, and, when I did go to bed, it took me a while to go to sleep, and, when I did go to sleep, it was one of those wakeful sleeps where one is not sure whether one is awake drifting into sleep or asleep rising toward wakefulness.  It was in such a state that I began to dream.
In my dream, I was in a modest, rural community.  The roads were dirt and the buildings were unpainted wood, stained gray by weather.  In the center of town there was an official looking building, still of unpainted, weathered wood but official none the less.
It was clear there was an election going on, because there were signs everywhere touting the three candidates that were running: Abraham Lincoln, Bobby Kennedy, and Calvin Coolidge.  I recognized them by their pictures because the names on the signs were simply Abe, Bob, and Cal.
I walked toward the official looking building and entered in to it.  There inside was a glowing, golden cube that sported a 21-inch touchscreen monitor upon which was written: “Election results here.”
I was asking myself what this could be when, in the manner of dreams like this, there was a voice at my elbow with an answer.
“That’s our guaranteed fair voting machine,” the voice said.
I turned to see a man dressed in old style.  He was wearing a black “boss of the plains” hat. This is a round hat with a broad, round brim that curves down.
His shirt was white but everything else was black: coat, tie, and pants.  His tie was actually a neck cloth and tied into a horse collar knot.
The word ‘fair’ caught my attention.  It means so many things to so many people.  When mathematicians refer to a fair coin, they mean one that will come up heads or tails equally often, but, when most people use it, they mean something different.
“A fair voting machine,” I echoed. “Does that mean it counts every ballot correctly?”
“Oh,” he said, “it does much more than that. Come and see.”
I followed him and he showed me a ballot with three names on it: Abe, Bob, and Cal.  The voters were instructed to mark each of these with a 1, 2, or 3, according to preference with 1 being most preferred and 3 being least preferred.
“By fairness, we mean the following two rules are followed,” he said. “The first rule is that if everyone prefers one candidate to another, say Abe to Bob, then Abe will be rated above Bob in the election.  The second is that this will remain unchanged even if the voters change the relative ratings of other candidates.  That is to say, moving Cal higher or lower will not effect whether Abe is preferred to Bob or not.”
I nodded my head as that seemed fair to me.
My stomach rumbled and called me briefly toward--but not actual to--wakefulness and I remembered something vague about this kind of situation, but I rolled over and pushed myself into a deeper sleep.
The town was there as before and the man, who I began to call ‘The Parson,’ was standing there with me.  In front of us, queueing up to the voting machine, were the people of the town.  All of the men were dress in the same manner as the Parson and all of the women where dressed in gray woolen dresses.
“What are they lined up for?” I asked.
“They are lined up to vote,” the Parson said.  “They are lined up in the order in which they have voted from time immemorial and always shall vote.  They put there ballot in and walk past and allow the next to vote.  Then the machine gives us the town’s preferences in order.”
“So you get more than just a winner?” I asked.  “You get the town’s collective preference?”
“What you say is so,” the Parson replied.
“I am curious,” I said.  “Would you mind if I did some experiments with your machine?”
The Parson’s expression then changed from the grim one he’d been wearing into a smile.
“It is your dream,” he said. “Go for it.”
I turned to the line of voters and began to speak.
“The first experiment will have several parts,” I said.  “The first thing I want you to do is to mark your ballots with Bob as your third, that is last, choice and then vote.  If your machine is working as you say, this should give us that Bob loses.”
The line, dourly dressed men and women alike, filed past the machine inserting their ballots.  When all were done, I looked at the results on the machine’s screen: Bob was last.
I’d never doubted the machine was accurate, I just wanted them to have an initial state in which a particular candidate, Bob in this case, was last.
“Okay,” I said, “the next part of the experiment will be more complicated.  We know that if everyone lists Bob as their first preference that he will be the winner.  What I want to do, is to ferret out a particular key voter.  To do this we will have to vote many times.  The first time, I want the first person in line to switch Bob from last to first while preserving the order of the other two candidates and for everyone else to leave their ballots alone.  We will then check to see whether Bob has been moved from the bottom.  
“If Bob hasn’t been moved from the bottom,  the first and second people in line will then both move Bob to the top while leaving Abe and Cal with the same relative position to each other as before on their ballots while all the rest of the voters’ ballots will remain as in the initial phase of the experiment. After everyone has voted, we will check again to see whether Bob has been moved from the bottom.
“We will continue in this manner until, as must happen, Bob has been moved from the bottom. Do you understand?”
Much to my surprise, they all nodded that they did understand.  
The process began and the whole line of voters modified their ballots and voted and revoted numerous times, each time checking whether Bob was still the loser.  At some point, the Parson checked the winner and called for a halt.
“It’s done,” he said.  “Bob is no longer the loser.  It was our own brother Nimrod who did the deed.”
“Nimrod,” the rest of the voters chanted in unison.  It was kind of spooky.
I nodded my head.  
“I will now tell you something,” I said.  “Not only is Bob not the loser; he is now the winner.”
It was the Parson’s turn to be spooked.
“How do you know that?” he asked.
“Just mathematical reasoning,” I said.  “For the sake of argument, assume that Bob is not the winner but, say Abe, is.  Then Abe beats Bob and Bob beats Cal.  Now pretend that Nimrod and everyone before him vote for Bob, Cal, and Abe in that order and everyone after them in line to vote Cal, Abe, and Bob in that order.  The relative positions of Bob and Abe haven’t changed so Abe beats Bob.  Similarly, the relative positions of Bob and Cal are still the same so Bob still beats Cal; therefore Abe beats Cal.  The kicker is that every voter prefers Cal to Abe, so Cal must beat Abe.  As we can’t have Abe beating Cal and Cal beating Abe, the only alternative is that Bob must be the winner.”
Fear was in the Parson’s eye.
“Truly, you are a sorcerer,” he said.
“Sorcerer,” the votes chanted as one.
At that point my wife started shaking me.
“You are having a bad dream,” I heard through the haze.
I couldn’t rouse myself but turned over to my other side.
In my dream, the Parson was there again.
“You said you had experiments, Sorcerer,” he said.  “That means there is more than one.  Tell us your second, as the night grows short.”
“Okay,” I said.  “I will now show you that Nimrod can always dictate Abe and Cal’s relative positions with respect to each other.”
“Show us, Sorcerer,” the Parson said.
I noticed that Nimrod was now wearing a little square mustache on his upper lip. Everyone else was clean shaven.
“We will vote only four times,” I said.  “This time Nimrod will vote so that he prefers Abe to Cal.  He can vote Bob in any position he wishes and everyone else can vote as they please.
“In vote 2, change the ballots in vote 1 so that everyone who votes before Nimrod has Bob and the top of the ballot but that Nimrod and everyone after him has Bob at the bottom.  The relative positions of Abe and Cal to each other should remain the same on each ballot.
“In vote 3, change from vote 1 so that Nimrod and all of the voters before him put Bob at the top and all those after Nimrod put Bob at the bottom.  In other words, this is just like vote two, but Nimrod has moved Bob from last to first.
“Finally, in vote 4, everyone before Nimrod votes exactly as they have in two and three, Nimrod votes Abe over Bob over Cal, and everyone after Nimrod votes as they did in two and three. Now don’t tell me what happens in vote 1.”
They did as they were told, and the following happened.  Bob lost in vote 2.  This had to happen because Nimrod didn’t vote for him  We knew from the first experiment that Nimrod had to be the voter to raise Bob from the bottom because the “fairness” of the magic cube guarantees changing the relative positions of Abe and Cal on any of the other ballots will not change the position of Bob in the final vote.  We know that Bob wins in vote 3 by the same reasoning.
In vote 4, we know that Bob beats Cal because of experiment 1 and the fact that we get to ignore Abe because “fairness” assures us that only relative preferences matter.  We also know that Abe beats Bob by the same reasoning.  So Abe beats Bob who beats Cal, and it follows that Abe beats Cal in vote 4.  
Since only the position of Bob changed from vote 1 to vote 4, I know that Abe beat Cal.  I told them.
“Yes, Sorcerer,” the Parson said, “you are correct.”  He glanced toward Nimrod, who seemed to be growing in stature with the rest.  
I began to feel sweaty.  I heard my wife say, “You will never learn.”
I turned over yet again.
This time I was in the clouds.  I began to think.  Is Nimrod so special?  I could have done the first experiment with Cal being on the bottom instead of Bob and then Michael might have been able to dictate the relative positions of Abe and Bob.  I might’ve done it with Abe being on the bottom and turned out with Paul being able to dictate the relative positions of Bob and Cal.
But then Micheal could vote for Abe over Bob and Paul for Bob over Cal, so Abe would beat Bob who would beat Cal, but then Nimrod could come along and vote for Cal over Abe.  It wouldn’t make sense.  I turned it over several other ways in my head and the only way it made any sense was for Nimrod to be the sole dictator.
Suddenly, the clouds were gone and Nimrod was there with the Parson and the other voters with pitchforks and sickles.  
“The Sorcerer is there!” the Parson screamed.  
“Get him,” Nimrod said.
And they were coming for me, and then I heard bells ringing.  It was the alarm clock.

In the shower, I recalled consciously what I’d been dealing with in my subconscious all night: Arrow’s Theorem, which is named after the economist Kenneth Arrow.  Given any sort of voting scheme with more that two candidates that attempts to order them while keeping the two the fairness criteria described, there must be one voter who will be able to dictate the outcome, which, paradoxically, doesn’t seem fair.
It’s enough to keep anyone awake at night.

[Based on a proof by John Geanakoplos]

No comments: