Sunday, August 19, 2012

The game theory of profiling

Previously, I read a paper that mathematically modeled the search for a malfeasor using profiling techniques.  I concluded that the model does not apply to security against airplane hijackers (though it may apply to other security situations).  You know what, I could build a better model than that!  I'm a physicist, dammit!

This comic seemed appropriate.

So here's my model.  Suppose that there is a small minority of fliers who are "marked" as especially suspicious.  (In Harris vs Schneier, the marked group are Muslims, though Schneier points out that being Muslim usually isn't a visible characteristic, and you'd have to use some proxy, such as "Arab-looking".)  There is a fixed percentage of fliers that airport security can search, but if they like they can choose to search people in the marked group more often.

Security's adversaries are the terrorists.  They have a certain amount of recruitment resources, which they can use to recruit hijackers in the marked group, or outside the marked group.  However, if they recruit outside the marked group, it costs more resources, and thus they can recruit fewer people.

Security plays to minimize the number of successful attacks.  To do this, they must minimize the average number of hijackers not searched.  Terrorists play to maximize the number of successful attacks.  The question: How much should security focus on searching the marked group, and how much should the Terrorists focus on recruiting from the marked group?

Parameters in this model:
m = the ratio of the number of people in the marked group to the number of everyone else
λ = the percentage of fliers that security can search
c = the ratio of the cost of recruiting a hijacker from the marked group to the cost of recruiting elsewhere

Assumptions I will make:
m is very small (the marked group is a very small minority)
λ > m (security can search every single person in the marked minority if they want)
λ < 1/(1+m) (security cannot search every single person outside of the marked group)
c < 1 (It is cheaper to recruit hijackers in the marked minority)
The number of hijackers the terrorists can recruit is smaller than the number of people in the minority.
Lastly, I will ignore the fact that people come in discrete quantities.

The game:
Both airport security and terrorists have a choice to make.  And it's not one of those either/or choices, they have a whole sliding scale to choose from.  Let y be the position of the sliding scale for airport security, and let x be the position of the sliding scale for terrorists.

Legend text: "Percentage of minority searched"; "Percentage of other people searched"; "Hijackers recruited from minority"; "Hijackers recruited elsewhere".  n is the maximum number of hijackers that can be recruited, but this parameter does not figure into the solution.

x and y are each numbers between 0 and 1.  The greater x is, the more the terrorists focus on recruiting from the marked group.  The greater y is, the more airport security focuses on recruiting from the marked group.

The number of successful attacks is a function of x and y.  I will represent this function as the height in the following graph:

Terrorists control the x coordinate, and want to maximize the height.  Airport security controls the y coordinate, and wants to minimize the height.  Assuming both players are rational[1], and know each other to be rational, they will choose the single Nash equilibrium.  This is a saddle point, which I've marked in the above graph.

I could give you the coordinates of the solution[2], but this would be meaningless because x and y are just abstract quantities.  Here are some more meaningful quantities.

Click for larger

Yes, that means the terrorists should be equitable in their recruitment process.  Even if it is easier to recruit from the marked group, they should still make no effort to focus on the marked group.  This solution is exact[3].

The results for the airport security, on the other hand, are approximations only valid for small m.  Basically, security should search a percentage of marked people such that the terrorists get just as much bang for their buck regardless of where they recruit.

If I were to plug in "reasonable" numbers, I would say c = 3/4, and λ = 1/5.  With these numbers, airport security should search 2/5 of people in the marked group, and 1/5 of everyone else.

Applicability of this analysis:

This analysis is inapplicable, because it ignores the additional risk and cost associated with determining a profiling scheme, determining the parameters, and training security personnel to implement it.  There are probably other complications too.  Lastly, it assumes that airport security is rational. So maybe applications are a lost cause, but at least I got to do some math.

[1]This is "rational" in the game theory sense, which is frequently irrational in the colloquial sense.
[2]The exact coordinates are ( cm/(1+cm) , 1 - c(1-λ)(1+m)/(1+cm) ).
[3]That is to say, it does not use the assumption that m is very small. However, it does use the other assumptions.