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.
(In reply to
re: Reformulated version by Dej Mar)
I did not want to be too critical about your original problem, FrankM, yet I felt it was, yes, slightly ambiguous (which may be the desire for some problems), and, in my opinion, did infer a single ballot per Logistani.
As I wrote in the (revised) comment on whether repeated questioning was allowed (this is what you are talking about, right?), I agree there was room for improvement on this point. the text, while not misleading, was unnecessarily ambiguous.
In formulating the problem text I wanted to follow a narrow path between clarity and being overly revealing. For this reason I refrained from explicitly encouraging solvers to examine multiple questioning. Rather, discovering the payoff from multiple questioning was to have been a major milestone on the way to a solution.
In fact, it is quite difficult to write a problem without missing anything. As we've seen, I also made the mistake of leaving the door open for a much less satisfying alternative solution, which is really only a variation on the solution to the original K&L problem. I've asked myself why this is and I'm beginning to think that the peer review process ought to be overhauled (at least for complicated problems, like this one) so that at least some people get to review the solutions too before publication.
I do find your reformulated version is fine*, and I hope to make an attempt at finding a solution.
I'm glad you approve of the new version. I wish you good luck!
*You state that 'a contrarian or revisionist would respond randomly if he were the first voter queried', yet, is the contrarian's/revisionist's response truly random or only seemingly random as the race of the last querant prior to the current situation was not revealed?
I'll try to address this by pointing out the motivation for including the possibility of random responses. The basic notion is that Cs and Rs determine their vote based on the actions of others. This sets them apart from KLS who act out - each according to his own idiosyncratic personality - based on their own views. The trouble with this definition is that it is incomplete: it fails to explain how a C or R would react if he had no outside voice to guide him. I was sure that some reader would object if I had let this lacuna stand. Therefore I introduced the notion of Cs and Rs acting randomly if there were no previous respondent upon which they could base their answer.
So, basically, you should not worry much over the possibility of random behaviour. In fact, the solution calls for M (or B) to be the first one to vote, so that in the situation of this problem, a random answer does not play a role.
I hope this answers your question.
|
Posted by FrankM
on 2008-03-27 14:24:30 |