Recursive Inspection Games

Dresher (1962) described a sequential inspection game where an inspector has to distribute a given number of inspections over a larger number of inspection periods in order to detect an illegal act that an inspectee, who can count the inspector’s visits, performs in at most one of these periods. This paper treats two extensions of this game. In the first, more than one illegal act is allowed. Then, under certain reasonable assumptions for the zero-sum payoffs, the optimal strategy of the inspector does not depend on the number of intended illegal acts. This allows a recursive description, which is justified formally using extensive games. The resulting recursive equation in three variables for the value of the game, which generalizes several other known equations of this kind, is solved explicitly. In a second variation of the Dresher game, there is again only one illegal act, which is however always detected at the next inspection, with the payoff to the violator linearly increasing with the time passed in between. The solution of this game is simple and intuitive, but a conceptually sound description employs an extensive game with recursion in only one branch, and its corresponding norma