mathematics//game theory//Stackelberg game

A Stackelberg game is a two-player game in which one player, the leader, commits to a strategy first and the other, the follower, chooses its best response after seeing that commitment; it is the model for anyone who must act in the open and can be studied before being attacked, such as a patrol, a perimeter guard, an inspection regime or a firm that publishes its prices. Where the simultaneous games of game theory ask what each side does without seeing the other, here the order of moves is the whole problem, and the leader looks for the commitment whose best response hurts it least.

A Stackelberg game is a two-player game in which one player, the leader, commits to a strategy first and the other, the follower, chooses its best response after seeing that commitment; it is the model for anyone who must act in the open and can be studied before being attacked, such as a patrol, a perimeter guard, an inspection regime or a firm that publishes its prices. Where the simultaneous games of game theory ask what each side does without seeing the other, here the order of moves is the whole problem, and the leader looks for the commitment whose best response hurts it least.

A guard is a leader whether it wants to be or not. Whatever schedule the drones of a perimeter fly, an intruder can watch for weeks before acting, so any fixed route is learnt and exploited. The leader's useful move is a commitment to probabilities: watch the fuel depot on two nights out of three and the workshop on the third, drawn fresh each evening, so the observer learns the distribution and still cannot know tonight's draw (a mixed strategy). The follower then picks the target with the best expected payoff under those probabilities, and the leader chooses the probabilities that make that best payoff as small as possible, which in a two-target case is the point where the follower is indifferent between targets.

Committing first only hurts a predictable leader. With a randomized commitment the leader loses nothing in a zero-sum setting, because the minimax theorem makes the order of moves irrelevant there, and the information the follower gains is only the distribution, never the draw.

It is deployed. Stackelberg security games computed the randomized checkpoint and canine schedules of Los Angeles airport (the ARMOR system, from 2007) and US Coast Guard patrols in ports such as Boston (PROTECT); the book counts them as a real niche. What goes in is the list of targets, what each is worth to both sides and how many resources there are; what comes out is a probability of covering each target, from which a scheduler draws each day's plan. The leader's optimum is found with one linear program per possible follower response, or one mixed integer program (integer linear programming).

Its assumptions are where it breaks. It supposes that the follower observes the distribution exactly, knows its own payoffs and responds rationally; real intruders are boundedly rational and the payoff table is a guess, so robust variants plan against a range of follower types. A schedule drawn from a predictable generator, or a shift pattern that tired staff fall into, hands the follower the draw itself.

The name collides with the leader-follower scheme of formation control, where the follower tracks the leader's motion and nobody has opposing aims. When both players move without seeing each other the solution concept is the Nash equilibrium; when their payoffs are exactly opposed the game is zero-sum.