Gambles in casinos are usually set up so that the casino makes a profit in expectation -- as long as gamblers play honestly. However, some gamblers are able to cheat, reducing the casino’s profit. How should the casino address this? A common strategy is to selectively kick gamblers out, possibly even without being sure that they were cheating. In this paper, we address the following question: Based solely on a gambler’s track record,when is it optimal for the casino to kick the gambler out? Because cheaters will adapt to the casino’s policy, this is a game-theoretic question. Specifically, we model the problem as a Bayesian game in which the casino is a Stackelberg leader that can commit to a (possibly randomized) policy for when to kick gamblers out, and we provide efficient algorithms for computing the optimal policy. Besides being potentially useful to casinos, we imagine that similar techniques could be useful for addressing related problems -- for example, illegal trades in financial markets.

Without commitment, this game is solvable by iterated Game theory provides a mathematical framework for rational strict dominance: U strictly dominates D for player 1; after action in settings with multiple agents. As such, algorithms removing D, L strictly dominates R for player 2. So for computing game-theoretic solutions are of great the iterated strict dominance outcome (and hence the only interest to the multiagent systems community in AI. equilibrium outcome) is (U, L), resulting in a utility of 1 for It has long been well known in game theory that being player 1. However, if player 1 can commit to a pure strategy able to commit to a course of action before the before player 2 moves, then player 1 is better off committing other player(s) move(s)--often referred to as a Stackelberg to D, thereby incentivizing player 2 to play R, resulting model (von Stackelberg 1934)--can bestow significant in a utility of 2 for player 1. Even better for player 1 is to advantages. In recent years, the problem of computing commit to a mixed strategy of (.49U,.51D); this still incentivizes an optimal strategy to commit to has started to receive player 2 to play R and results in an expected utility a significant amount of attention, especially in the multiagent of.49

Recently, algorithms for computing game-theoretic solutions have been deployed in real-world security applications, such as the placement of checkpoints and canine units at Los Angeles International Airport. These algorithms assume that the defender (security personnel) can commit to a mixed strategy, a so-called Stackelberg model. As pointed out by Kiekintveld et al. (2009), in these applications, generally, multiple resources need to be assigned to multiple targets, resulting in an exponential number of pure strategies for the defender. In this paper, we study how to compute optimal Stackelberg strategies in such games, showing that this can be done in polynomial time in some cases, and is NP-hard in others.