Thursday, July 25, 2024

Knights and Knaves reimagined by Jacob Glazer and Ariel Rubinstein

 Knights and Knaves are a venerable class of logical puzzles in which knights always tell the truth and knaves always lie, and the task is to think of a way to interrogate a knight or knave to learn the truth about something.  Here's a paper by Glazer and Rubinstein that looks like it opens a new vista of such problems (but don't trust me, I could be a knave...)

Magical Implementation by Jacob Glazer and Ariel Rubinstein, July 21, 2024

"Abstract: A principal would like to decide which of two parties deserves a prize. Each party privately observes the state of nature that determines which of them deserves the prize. The principal presents each party with a text that truthfully describes the conditions for deserving the prize and asks each of them what the state of nature is. The parties can cheat but the principal knows their cheating procedure. The principal “magically implements” his goal if he can come up with a pair of texts satisfying that in any dispute, he will recognize the cheater by applying the “honest-cheater asymmetry principle”. According to this principle, the truth is with the party satisfying that if his statement is true, then the other party (using the given cheating procedure) could have cheated and made the statement he is making, but not the other way around. Examples are presented to illustrate the concept."

Before getting technical, the paper begins with this delightful example.

"Two invigilators, A and B, have witnessed a student receiving a whispered message from another student during an exam. The invigilators have not seen the questions on the exam but would be able to solve them. It is known that A does not like the student who received the message while B does. The exam includes multiple questions but only one refers to the variable α and reads as follows: “Solve the equation α + 1 = 4.” The student answers the question correctly. Invigilator A claims that the whispered message was: “α = 3.” This is a serious allegation and if correct, the student’s exam will be disqualified. Invigilator B claims that the whispered message was: “Solve the equation α+1 = 4 first.” If he is right, then the student’s answer genuinely reflects his knowledge of the material and there will not be any serious consequences. Who should be believed: A or B?

"Although there is no definitive proof one way or the other, we would choose to believe B. The reasoning would be that if the message was “Solve the equation α + 1 = 4 first”, then A (who dislikes the student) could solve the equation himself and claim that the message was “α = 3”. On the other hand, if the message was “α = 3” it is very unlikely that B (who likes the student and who, as mentioned, has not seen the exam questions) could guess that the equation to be solved is α+1 = 4 rather than any other equation with the same solution. Hence, there is an asymmetry between the two conflicting claims which makes it possible to reasonably conclude that B’s claim is the truthful one."


No comments:

Post a Comment

Note: Only a member of this blog may post a comment.