Glazer and Rubinstein: "A Model of Persuasion with Boundedly Rational Agents" (2012)

Suppose you have a belief or opinion about the logical atoms p, q, and r. Somebody then asks you what you think about these three issues and tells you that you will get 100$ if your opinions satisfy the following rules:

1. If p and q, then r
2. If q and ¬r, then p
3. If ¬p and ¬q, then ¬r
4. If ¬p and q, then ¬r
5. If r and ¬q, then ¬p
6. If p and r, then ¬q

The person awarding the prize actually have no way of checking your actual beliefs, so you can really say anything you like which is consistent with these rules.

However, most people will probably find it difficult to synthesize a coherent story from these rules, and they will respond by hacking a little about with their actual beliefs until they find some modified version of the truth which is consistent or close to consistent with the rules.

One plausible hypothesis about how this hacking is carried out is that you find one or more rules that are violated by your actual beliefs and then revise your statement about the conclusion of the if-then rule. This is easier than revising the antecedent of the rule, since the consequent always contains a single bit only.

If you use this revision scheme, then a series of revisions can be seen as a walk around the three-dimensional hypercube which represents the possible truth assignments to p, q, and r. The six rules mentioned above, for instance, corresponds to the following steps around the hypercube:

In this particular case, each "profile" (assignment) violates exactly one rule and points in the direction of a unique other profile which does not. If you keep revising your statement according to the bit-fixing procedure described above, you will thus always eventually end up in the accepted state 000 (unless you happened to start in the accepted state 100). But there are many other rule collections that do not have this property.

However, in this paper, Jacob Glazer and Ariel Rubinstein collect a number of interesting facts about such accessibility relations on the hypercube. They argue that rule set is consistent (satisfiable) if it has no symmetric connections. They also discuss how to convert arbitrary rule sets into "canonical" rule sets where each profile has at most one arrow emanating from it. Throughout most of the paper, they assume that ordinary agents are incapable of taking more than one step through these diagrams.

From a mechanism design standpoint, the most interesting question is of course when one can design a rule set with the property that boundedly rational agents with the "wrong" beliefs are tricked into submitting statements that actually violate the rules, while agents that have the "right" beliefs are led to submit statements that are consistent with the rules.

It turns out that the crucial feature which allows for such sorting of the agents is that all connected components of the "rejectable" region contain a cycle. If this is the case, then the designer can pick a rule set that will send all rejectable profiles around in a circle inside the rejectable region. In Glazer and Rubinstein's formulation, such agents will be trapped in "a circle of lies."

There is a number of interesting parallels that the paper doesn't touch on, but which would be natural to follow up on. From an information-theoretic standpoint, for instance, the collections of arrows on the hypercube could be taken to represent a decoding procedure, and a solution to the design problem would then be a zero-error decoding method. From a statistical perspective, the arrows correspond to a certain type of Gibbs sampling, and it is in fact known that a Markov chain Monto Carlo scheme very similar to this one is a useful solution method for Boolean satisfiability problems.