Numb3rs 520: The Fifth Man

Charlie's miscalculation on the numbers of criminals involved in a series of house invasions has terrible  consequences. His brother is badly injured after being stabbed by The Fifth Man, an individual who Charlie missed in his initial analysis. Charlie and the FBI try to locate the missing criminal.

During the investigation Charlie uses Payoff matrices to find the M.O. of the home invaders, Wavelet analysis for finger-print recognition and Dijkstra's algorithm to locate a safety box which will lead to the Fifth Man's arrest.

These concepts have already been discussed in previous episodes: Episodes 107, 110, 222, 321 and 323. Below we will extend the previous presentations on payoff matrices (game theory) and wavelet analysis.

Payoff matrices and game theory

Many situations in real life can be translated into the language of Game Theory: the strategies followed by each of the agents in the game depend on the others' strategies and determine the final outcome. Formally, a game can be represented by specifying the players' strategies and the payoffs for each choice of strategies. This representation is commonly known as the normal-form representation of a game. When the number of players and strategies is finite, the normal-form representation can be visualized in a rectangular array of payoffs called the payoff matrix of the game. One of the most used examples to illustrate the definitions above is a game called The Prisoners' Dilemma (see Episodes 110 and 321):  two suspects are arrested and charged with a crime by the police. The police lacks evidence to convict them, unless one of them confesses. They are held in different rooms and the police explains the consequences that will follow from their actions: If neither confesses they will be convicted of a minor offense and sentenced to 1 month in jail. If both confess then both will be sentenced to 6 months in jail. Finally, if one confesses but the other does not, then the confessor will be released and the other will be sentenced to 9 months in jail. This game has two players whose strategies are to be mum or to fink. The payoff matrix for The Prisoners' Dilemma is 

One possible method to find the outcome of this game is known as Iterated elimination of strictly dominated strategies. This process assumes that both prisoners are rational, are aware of the rationality of their opponent, know that their opponent knows about their rationality, and so on, ad infinitum. A given strategy s is said to be strictly dominated by strategy s' if regardless of the other players' strategies the payoff from playing s is strictly less than the one from playing s'. For instance, in The Prisoner's Dilemma, for Player 1 the strategy of being mum is strictly dominated by the strategy of confessing. Hence, one could argue that Player 1 will never be mum and eliminate this row of the payoff matrix reducing it to the following payoff matrix.

In this payoff matrix, for Player 2 the strategy of being mum is strictly dominated by the strategy of confessing. After eliminating the second column of the matrix one finds that the outcome of this game is that both prisoners fink. This represents the simplest example of a non-cooperative game: if both prisoners were mum their payoffs would be higher, however since they don't have the option of a pre-game arrangement, they decide to play independently.

There exist many examples of games were Iterated elimination of strictly dominated strategies does not predict the outcome of the game. Consider for instance the following game with two players, 1 and 2. The strategies for player 1 are {T,M,B} and strategies for player 2 are {L,C,R}.

An alternative way to find the outcome of the game above is by considering each player's best responses to their opponents strategies. For Player 1, the best response to L is M, the best response to C is T and the best response to R is B. For Player 2, the best response to T is L, the best response to M is C and the best response to B is R. Observe that if Player 1 plays B and Player 2 plays R they're both playing their best responses to the other's strategy. We say in this case that (B,R) is a Nash equilibrium for the game. In general, a Nash equilibrium is a vector of strategies, where for each player the strategy played is the best response to the opponents' strategies given in the vector. 

Not all games admit a Nash equilibrium however. This is illustrated in the example below. 

Theorem: If a vector of strategies is the only "survivor" after iterated elimination of strictly dominated strategies, then this the unique Nash Equilibrium of the game. Moreover, any Nash equilibrium survives iterated elimination of strictly dominated strategies.

Wavelet analysis and fingerprint compression

As we already mentioned in Episode 107 Wavelet analysis refers to the decomposition of finite energy signals into different frequency components by the superposition of functions obtained after scaling and translating an initial function known as Mother Wavelet. As mentioned before, one of the applications of wavelet analysis is data compression, in particular FBI fingerprint compression. Fingerprints are digitalized with a resolution of 500 pixels per inch with 256 levels of gray-scale information per pixel. This represents astronomic amounts of data whose compression brings down the cost of storage by millions of dollars. 

The example discussed in the forementioned episode corresponds to what is known as the Haar Discrete Wavelet Transform. Recall that in this case the scale and wavelet functions are given by h, a function that takes the value 1 on the interval [0,1) and 0 otherwise, and g, a function that takes the value 1 on [0,0.5),the value -1 on [0.5,1), and 0 otherwise. The Haar transform is convenient for the introduction of the subject but not suitable for applications. The main drawback of this transform is that the scale and wavelet functions are discontinuous: they jump at 0 and 1 and at 0,1/2 and 1 respectively.  These discontinuities are reflected in the compressed image, which looses edge clarity and overall smoothness (see image below). 

Hence, in practice it is desirable to use smooth scale and wavelet functions for the analysis. Also it is desirable to have mother wavelets that vanish outside a finite interval so the wavelet analysis has good localization properties. Belgian mathematician and physicist Ingrid Daubechies discovered in 1988 the first infinitely smooth wavelets with compact support . These functions are rather complicated and hard to describe, we show the graph of some of them in the figure below. The scaling functions appear on the left and the corresponding wavelets on the right. 

By using Daubechies' scale and wavelet functions the "continuity" of the original image is preserved after compression. This feature makes them appealing for compression purposes. The functions (filters) used by the FBI are a generalization of these scale and wavelet functions. They are called the Cohen - Daubechies - Feauveau biorthogonal wavelets. The additional feature that these functions posses is that the scale and wavelet families are symmetrical and have similar lengths. We show in the image below the original image of a fingerprint and the compressed version when using these bi-orthogonal wavelets.