A Knights and Knaves Game on Paths

Abstract

We study a nonzero-sum game in which two players label the N vertices of a path as being either Knights (i.e., truth-tellers) or Knaves (i.e., liars). Each vertex utters the sentence “An even number of my neighbors are Knights” and can be consistent (the truth value of its sentence agrees with its type) or inconsistent. The Knight player favors consistent vertices and the Knave player inconsistent ones. After characterizing the pure Nash equilibria of the game, we concentrate on the study of best-response dynamics. It turns out that these are the dynamics of a Rule 90 affine cellular automaton: x(t+1)=ANx(t)+dN, where AN is the adjacency matrix of the N-path and the arithmetic is performed in the Galois field F2. Using the characteristic polynomial of AN, we study the properties of the best response dynamics with special emphasis on its periodic behavior.