Dealing with Misdirection

Content warning: nerd sniping.

A murder has been committed. You have five suspects: Alice, Bob, Charlie, Denise, and Eve. A priori, you have no reason to suspect any one over any other.

Fortunately, you have several pieces of evidence to guide you towards the true murderer. A footprint that’s too large to belong to any of the ladies; a knife missing from Charlie’s knife block; Eve’s fingerprints on the door handle; and so on.

Unfortunately, whoever did the deed, they knew who the obvious other suspects would be, and may have laid some false tracks. In the worst case, they even knew what real evidence would be available to you, and tailored their false evidence to be maximally confusing in the context of that real evidence.

How do you figure out who the murderer is?

I. A Smidge of Rigor

Let’s get some Bayes up in here. You start off with some a priori odds for the suspects (e.g. 1:1:1:1:1, you have no idea which one did it). Model each piece of evidence as another set of odds, telling you how you should update your current odds (e.g. Charlie’s missing knife might correspond to the odds “1:1:10:1:1”: it obviously implicates Charlie, but somebody else might’ve swiped it).

If you know that all your evidence is real, then this problem is super-simple! Just multiply your a priori odds with your evidence-odds to get your posterior odds, just as you’re used to:

\[\begin{array}{lllllllllll} & & A & & B & & C & & D & & E \\ & \text{a priori} & 1 &:& 1 &:& 1 &: & 1 &:& 1 \\ \times & \text{footprint} & 1 &:& 3 &:& 3 &: & 1 &:& 1 \\ \times & \text{fingerprints} & 1 &:& 1 &:& 1 &: & 1 &:& 3 \\ \times & \text{knife} & 1 &:& 1 &:& 10 &:& 1 &:& 1 \\ \hline = & & 1 &:& 3 &:& 30 &:& 1 &:& 3 \end{array}\]

Pretty open-and-shut case: Charlie’s guilty.

…but if you know that one piece of evidence was planted by the malefactor, then very likely that knife was planted there to frame Charlie – unless that’s exactly what Charlie wants you to think – and from there, it’s meta all the way down.

II. More Formalization

Clearly we need to nail down specifics if we want to accomplish anything concrete. We can’t keep muddling along speculating on Charlie’s psychology.

Let’s define the problem as follows:

• There are $S$ suspects.
• $R$ pieces of real evidence are generated. (This includes some subtlety – see below.)
• The criminal gets to look at the real evidence and add $F$ pieces of fake evidence to the pool.
• The detective looks at all of the evidence, and makes a guess who the criminal is.
• If the detective correctly identifies the criminal, the detective wins; else, the criminal wins.
• So the detective’s goal is to maximize the probability of identifying the criminal; the criminal’s goal is to minimize that probability.

(I think we just invented a party game, by the way.)

I believe, although it’s not immediately obvious, that we need to define exactly how the real evidence is generated. The detective needs some PDF over evidence-space in order to reason about how how likely it is each piece of evidence is real. Suppose evidence is generated by sampling from – oh, say, a log-normal distribution with $\mu=0,\sigma^2=1$ to get the odds for each innocent suspect, and from a log-normal distribution with $\mu=C, \sigma^2=1$ ($C$ for Carelessness) for the criminal. So, if Denise is the criminal, and her carelessness is 1, then each piece of real evidence is sampled from the distribution $ln\mathcal{N}(0,1) : ln\mathcal{N}(0,1) : ln\mathcal{N}(0,1) : ln\mathcal{N}(1,1) : ln\mathcal{N}(0,1)$.

($C$, if it’s not intuitively clear, represents how strongly the real evidence points at the criminal. At $C=0$, the criminal is no more suspicious than an innocent; at $C=1$ they’re pretty easy to catch, each piece of evidence pointing $e$ times more at them than at any innocent; and at $C=5$ they’re about 150 times as suspicious, which is to say, super easy to catch.)

Great! We have completely defined this problem in terms of the number of $S$uspects, the number of pieces of $R$eal and $F$ake evidence, and the criminal’s $C$arelessness.

III. Some Basic Analysis

Some natural questions at this point are:

• What’s the best strategy for the criminal?
• What’s the best strategy for the detective?

Before answering these questions, we have to figure out: what’s a “strategy”? And what does it mean for a strategy to be the “best”?

IIIa: Define “Strategy”

In any game, any strategy can be described as a mathematical function that takes “all the information available to you at any point when you have to make a decision” and returns “a probability distribution over all actions available to you at that point.” In the current case, that simplifies to:

• For the criminal: there’s only one point in the game where the criminal makes a decision, i.e. the point where they create fake evidence. The information available to them is describable as an element of $\mathbb{E}^R$, where $\mathbb{E}$ is the set of possible pieces of evidence; and the set of possible actions (the set of possible piles of fake evidence) is $\mathbb{E}^F$. So

  \[Strat_{criminal} := \left\{ f \,\middle|\, f: \mathbb{E}^R \rightarrow PDF(\mathbb{E}^F) \right\}\]

• For the detective: there’s only one point in the game where the detective makes a decision, i.e. the point where they try to identify the criminal. The information available to them is an element of $\mathbb{E}^{R+F}$, and the set of possible actions is ${1, \cdots, S}$. So

  \[Strat_{detective} := \left\{ f \,\middle|\, f: \mathbb{E}^{R+F} \rightarrow PDF(\{1, \cdots, S\}) \right\}\]

IIIb: Define: “Best”

The traditional definition of the “best” strategy for any game is the strategy $s$ that loses the least often to its “best counterstrategy”, i.e. the strategy for the other player that wins most often against $s$.

For example: one detective-strategy is to guess randomly. This ensures victory $1/S$ of the time. All criminal strategies are “best counterstrategies” here, because they all win equally often.

Another (very naive) detective-strategy is to ignore the possibility of fake evidence, and always finger the suspect that looks most suspicious according to all the evidence. One “best counterstrategy” is for the criminal – say, Denise – to produce fake evidence that goes “1:1:1:0:1”, thereby ensuring that she will never be the most suspicious, and therefore always win. Because the “naively most suspicious” detective-strategy loses to its best counterstrategy more often than the “random guessing” detective-strategy loses to its best counterstrategy, we can confidently say that “naively most suspicious” is not the best detective-strategy.

Similarly, the “1:1:1:0:1” criminal-strategy is not the best strategy for the criminal, because there exists a detective-strategy that always beats it (i.e. “pick the naively-least-suspicious suspect”), and there do exist criminal-strategies that don’t always lose.

IV. Finding the Best Strategies

IV(a): Special Case: $F=0$

In this case, the criminal has planted no evidence, so the detective doesn’t need to engage in any of this meta-meta-meta nonsense.

One nice property of log-normal distributions is that if $X$ and $Y$ are both log-normally distributed, then so is $XY$. So the detective’s posterior odds will come from a distribution like

\[ln\mathcal{N}(0, R) : ln\mathcal{N}(0, R) : ln\mathcal{N}(0, R) : ln\mathcal{N}(RC, R) : ln\mathcal{N}(0, R)\]

(where the 4th suspect is the criminal).

I’m sure (by pure intuition) that in this situation, the detective’s best strategy is to finger the most suspicious person. Unfortunately, I can’t find a closed-form formula for how often this strategy wins. However, we can see several intuitively appealing features emerging:

• As $S \rightarrow \infty$, the detective loses: if you take enough samples from $ln\mathcal{N}(0, R)$, you’ll eventually get something larger than your sample from $ln\mathcal{N}(RC, R)$. This sorta intuitively aligns with the intuition that when $S$ is big, the detective needs lots of bits of information to identify the criminal – and therefore, they need either strong or numerous pieces of evidence.

• When $C=0$, the criminal looks just like an innocent; the detective is reduced to random guessing. As $C \rightarrow \infty$, the criminal becomes incredibly suspicious and easy to identify.

• As $R \rightarrow \infty$, the detective wins almost always (as long as $C>0$).

IV(b): Special Case: $F \ge (S-1)R$

In this case, it’s very easy to find the best strategies for criminal and detective!

Suppose Denise is the criminal, and there’s one piece of real evidence: “1:1:1:99:1”. If Denise can plant 4 pieces of fake evidence, she can just cycle the odds of the real piece of evidence, so that the 5 pieces of evidence available to the detective are:

\[\begin{array}{lllll} A & & B & & C & & D & & E \\ 99 &:& 1 &:& 1 &: & 1 &:& 1 \\ 1 &:&99 &:& 1 &: & 1 &:& 1 \\ 1 &:& 1 &:&99 &: & 1 &:& 1 \\ 1 &:& 1 &:& 1 &: &99 &:& 1 \\ 1 &:& 1 &:& 1 &: & 1 &:&99 \\ \end{array}\]

All the suspects are indistinguishable! The detective has no better course than to guess randomly, which is the best the criminal can hope for.

IV(c): Special Case: $C=0$

In this case, the criminal is no more suspicious than an innocent. The detective’s best course must be, again, random guessing. And as long as the criminal doesn’t do something phenomenally stupid, adding fake evidence to incriminate themself, this is still the best they can hope for.

IV(d): The General Case

Exercise left to the reader.