An attempt at formalizing deception, seeing what goes right, what goes wrong, and what compromises have to be made.

Introduction

In a police interrogation one of the key challenges is working out whether a suspect is being deceptive. In a game of poker, one of the main goals is figuring out whether your opponents are being deceptive. But what are we talking about when we talk about deception, like, mathematically? I will propose a definition and give an example that illustrates how this definition operates.

Interrogation Investigation

Take a police officer, Alice, who is interrogating a suspect, Bob, in order to determine whether or not he is guilty of murder. Alice can either convict Bob or let him go, and Bob is either guilty or innocent. The payoff matrix is as follows:

Whether or not Bob is guilty, he would prefer to be let go; on the other hand, Alice only wants to convict if Bob is guilty, and she wants to let him go otherwise.

When Bob enters the room, it is predetermined that he is either guilty or innocent, Bob does not get to make a decision about this in advance. If Bob is guilty he will behave slightly differently under interrogation than if he isn't: he may have a weaker alibi, there may be inconsistencies in his story, he may exhibit physical symptoms associated with lying, but all of these things can also happen if Bob is innocent; sometimes innocent people have bad alibis, are inconsistent, and look nervous.

Now in order to define deception, we introduce Judy, an omniscient observer of the interrogation. Judy has the same goal as Alice, but unlike Alice, Judy also knows whether Bob is guilty or not. Further, Judy knows exactly how Bob's behaviors impact the likelihood of Alice convicting Bob (i.e. Judy can read both Alice's and Bob's minds). We call any subset of observations made by Alice deceptive if Judy would rather Alice make her decision to convict with this set of observations removed from her consideration (as though any memory of seeing these observations had been completely wiped from Alice's mind).

Formalization

Now let's try and formalize this story of deception. We'll describe Alice as a function from a series of observations to a probability space over actions:

with the series of observations $P^n$ given by:

$(F_n^1{)}_{n=1}^N$ defines a series of functions where each function $F_n^1$ represents the decision algorithm Alice uses. This function takes the series of observations Alice makes, $P^n$, as inputs and returns a probability distribution representing the likelihood Alice takes any action. In the interrogation context, this would return the probability that Alice convicts after receiving $n$ observations. For example: $F_1^1$ represents how likely Alice is to convict based on just one observation of Bob. 

For some of our later considerations we will want to repeat the game and have Alice update her decision algorithm between repetitions. For this reason we track which round of interrogation we are in by the superscript on the function, so that $F_n^1$ represents how Alice makes her decision in the first interrogation, $F_n^2$ represents how Alice makes her decision in the second interrogation, and so on.

Now introduce Judy into the formalization. If Judy would rather Alice had not made some number $m<n$ of observations, then we define these observations to be deceptive. Alice does not actually get to decide whether to convict or not based on the observations that have been pruned by Judy, instead this pruning process is only present to define what we mean when we say observations are deceptive (this should remove the possibility of Alice metagaming, where e.g. Judy might always remove all observations whenever Bob is guilty, and remove none whenever Bob is innocent).

Comments on the Formalization

This definition has a few curious properties:

• If Alice if a random hash function from observed data to actions, then Judy will classify observations as deceptive seemingly at random as well. More generally, observations get classified as deceptive by virtue only of their effects on Alice's decision algorithm.
• Even when Bob is completely innocent and being entirely honest, if there are 'inconvenient truths' in Bob's story (e.g. that he was the last person to be seen with the victim alive), then these 'inconvenient truths' may be classified as deceptive.
• We may have a set of observations that gets classified as deceptive, despite any subset of this set not being classified as deceptive. Similarly, we may have two observations that are individually classified as deceptive but Judy does not classify their union as deceptive.
• Bob might, even when innocent, decide to try lying and coming up with a more convincing alibi than the truth (this is the converse of 'inconvenient truths'). If Alice doesn't detect that Bob is lying about his alibi, these observations will not be classified as deceptive, despite Bob actually 'deceiving' Alice about what he was doing at the time of the murder. More generally, this definition is entirely agnostic about Bob's internal motivations.

Despite these weird properties, the value of this definition is that observations will be classified as deceptive if and only if they make it more likely for Alice to make the wrong decision. Another way of saying this is: when no observations or set of observations are classified as deceptive then Alice is very likely to make the right decision, and as the number of deceptive observations increases, so does the likelihood that Alice makes the wrong decision.

The strange properties of the definition above seem to me to be more likely to manifest themselves in a simplified toy example, such as the one we're using. If we instead took the example of a game of poker, where both players are relatively adept (e.g. Alice is not a hash function, or some such other 'insane' policy) then the observations Judy classifies as deceptive will more closely match our intuitions, because Alice making good decisions in poker depends more explicitly on Alice having an accurate model of when (and why) Bob is deceiving her.

Updates and Repetition

Now we repeat this interrogation process $N$ times, so that Alice interrogates Bob${}_1$, Bob${}_2$, $\dots$, Bob${}_N$, who are each randomly either guilty or innocent with equal probability. At the end of each interrogation, Judy will tell Alice whether she made the right decision (but not what observations Judy classified as deceptive), and allow Alice to update her decision algorithm based on this information. Then we would expect, on average, fewer sets of observations to be classified as deceptive when Alice is interrogating Bob${}_{x+1}$ than when Alice interrogated Bob${}_x$ (i.e. Alice's ability to determine Bob's guilt will improve over time). Of course in a real interrogation setting, Alice would also update her interrogation procedure itself, but for simplicity we have removed this possibility.

Each Bob${}_i$ is drawn randomly from one of two distributions over 'behavior-space.' We have a guilty-Bob distribution of behaviors and an innocent-Bob distribution of behaviors. For Alice's updating to work at all, we would need these distributions to be distinct in behavior-space, otherwise there would be no possible way for Alice to reliably determine Bob's guilt even in principle. In fact, if there is any overlap between these two distributions, then even the theoretically optimal Alice will not be able to perfectly distinguish guilty-Bobs from innocent-Bobs.

More generally, whenever two agents are playing an incomplete information game, and one agent might try to deceive the other, it will be harder for an agent to repeatedly be deceived when they can update on the ground-truth of how their opponents have behaved in the past. (This is, of course, assuming that the behavior of their opponents is in some way correlated with the ground-truth.)

Flaws

A key point is the method by which Alice updates her decision algorithm. If Bob's actions are always entirely uncorrelated with his guilt then we would hope that Alice would converge to understanding this and, in the limit, being maximally unconfident about whether she should convict. Despite this, if we end the process of updating at any finite step, there is always some chance that Alice sees some correlation which gives her a 'superstitious belief' (e.g. up to Bob${}_N$, whenever Bob was guilty he has always yawned and scratched his ear, by random chance). If Alice starts using these 'superstitious beliefs' to make decisions, then as we repeat interrogations, we could see Judy categorize more observations as deceptive, not less. This is a problem of making sure that Alice's updating procedure doesn't overfit hypotheses to past observations, or equivalently that Alice has good priors for what could possibly be associated with lying.

As noted above, Judy only categorizes observations as deceptive by the effect they have on Alice. It would be nice to have a definition of deceptive behavior that tracks whether Bob is representing his best understanding of the ground-truth (i.e. whether Bob is knowingly lying). It, however, seems to me as though these two notions are in tension with each other, and there simply might not exist one definition that captures both. If this is indeed the case, consider that Alice cares more about making the wrong decision than having an accurate picture of the world, so I would argue this definition of deceptive observation is more robust. (Also, when Alice needs a more accurate picture of the world to make better decisions, this definition will be responsive to that).

Remaining Questions

• Are there any huge flaws with this definition that I've missed? Are there ways to fix them?
• How might Alice's updating procedure change depending on Judy only telling her the truth about Bob's guilt vs Judy also telling her what information was classified as deceptive?
• In the limit, will the number of observations Judy classifies as deceptive be some function of the size of the intersection between the guilty-Bob distribution and innocent-Bob distribution (i.e. a function of Alice's best-case accuracy)?
• Does this definition apply to different examples in interesting or unexpected ways?