M, military ruler of Logistan, has deferred to international pressure and agreed to hold an election in which he will run against his arch-nemesis, B. Both M and B, being politicians, are liars. You have been engaged as an independent consultant and charged with devising a representative voting procedure, i.e., your mission is to tally the true preference of each citizen who has a consistent, determinable opinion, and no other.

The chief complication relates to the fact that the Logistani electorate is composed of five (to your eyes) indistinguishable ethnic groups, each of which have a distinctive relationship to the truth. When expressing their voting preference:

• Knights respond honestly.
• Liars negate their true view.
• Subversives consider how a a knight with the same views would respond, then say the opposite.
• Revisionists admire knights and liars, and despise subversives. A revisionist will copy the most recent knight or liar to have voted, unless a subversive has voted more recently. In this latter case, the revisionist will vote for the opposite of that subversive.
• Contrarians reverse the answer of the most recent voter.

A contrarian or revisionist would respond randomly if he were the first voter queried.

You are to hold the election at the national stadium, to which the entire Logistani electorate has been invited. After some thought, you decide you can conduct the vote by asking members of the assembled electorate a single yes/no question. This is an open ballot, so each voter will call out his/her answer to the question for all to hear.

Suggest a viable question and any procedural arrangements, explaining how they enable you to fulfill your mission.

Hmm. Let me try a small adjustment to your suggested question.

"Are you one of the following:

1) A knight who prefers B, or

2) A subversive who prefers M, or

3) A liar who prefers M ?"

Then count yes votes for B and no votes for M.

How would an M supporter respond?

1) If he were a knight, he would answer no (correct result)

2) If he were a liar, he would answer no (correct result)

3) If he were a subversive, he would answer no (correct result)

It looks like this question works, although I am downheartened at arriving at a solution that doesn't require the use of a revisionist as transducer/translator/oracle. (My own solution required this step). Nonetheless, it is a valid solution. (Congratulations Dej Mar!)

I will publish my own solution. If you are still interested, perhaps you can see if you can think up a variation where the revisionist/transducer is unavoidable. (One possibility I had considered was to require that the tally be made by observing the responses of just one voter. I rejected this though as it was a very pregnant hint).

Thanks everyone for enjoying this with me!

Edited on March 26, 2008, 12:44 pm

Posted by FrankM on 2008-03-26 12:40:41