Rotecting national infrastructure such as airports, historical

termi nals inside LAX. For example, if there are
three canine units available, a possible assignment
may be to place canines on terminals 1, 3, and 6
on the first day, but on terminals 2, 4, and 6 on
another day, and so on based on the available in -
formation. Figure 2 illustrates a canine unit on
patrol at LAX. 
Given these problems, our analysis revealed
three key challenges: first, potential attackers can
observe secu rity forces’ schedules over time and
then choose their attack strategy—this fact makes
deterministic schedules highly susceptible to
attack; second, there is unknown and uncertain in -
formation regarding the types of adversary we may
face; and third, although randomization helps
eliminate deterministic pat 
terns, it must also
account for the different costs and benefits associ-
ated with particular targets. 
In summarizing the domain requirements, we
emphasize the following key points. First, it is
LAWA police, as do main experts, who expressed a
requirement for randomiza 
tion, leading us to
design ARMOR. Second, there exist dif ferent rings
of security (including canines and checkpoints
that ARMOR schedules), which are not static and
therefore may change independently of the other
rings different times. The end result of such shift-
ing randomized security rings is that adversary
costs and uncertainty increase, particularly for
well-planned attacks, which in turn may help deter
and prevent attacks. 
Approach 
We modeled the decisions of setting checkpoints
or canine patrol routes at the LAX airport as
Bayesian Stackelberg games. These games allow us
to accomplish three impor tant tasks: they model
the fact that an adversary acts with knowledge of
security forces’ schedules, and thus random ize
schedules appropriately; they allow us to define
mul tiple adversary types, meeting the challenge of
our uncer tain information about our adversaries;
and they enable us to weigh the significance of dif-
ferent targets differently. Since Bayesian Stackel-
berg games address the challenges posed by our
domain, they are at the heart of generating mean-
ing fully randomized schedules. From this point we
will explain what a Bayesian Stackelberg game con-
sists of, how an LAX security problem can be
mapped onto Bayesian Stackelberg games, some of
the previous methods for solving Bayesian Stackel-
berg games, and how we use DOBSS to optimally
solve the problem at hand. 
Bayesian Stackelberg Games 
In a Stackelberg game, a leader commits to a strat-
egy first, and then a follower selfishly optimizes its
reward, consider 
ing the action chosen by the
leader. For example, given our security domain, the
police force (leader) must first commit to a mixed
strategy for placing checkpoints on roads in or der
to be unpredictable to the adversaries (followers),
where a mixed strategy implies a probability distri-
bution over the actions of setting checkpoints. The
adversaries, after observ ing check - points over
time, can then choose their own strat egy of attack-
ing a specific road. To see the advantage of be ing
the leader in a Stackelberg game, consider a simple
game with the payoff table as shown in figure 3.
The leader is the row player and the follower is the
column player. Given a si multaneous move game,
that is, the leader and follower now act at the same
time, the only pure-strategy Nash equilibrium for
this game is when the leader plays a and the fol-
Articles
SPRING 2009 45
Figure 1. LAX Checkpoint.
Figure 2. LAX Canine Patrol.

lower plays c, which gives the leader a payoff of 2.
However, if the leader commits to a uniform mixed
strategy of playing a and b with equal (0.5) proba-
bility, then the follower will play d in order to max-
imize its payoff, leading to a payoff for the leader
of 3.5. Thus, by committing to a mixed strategy
first, the leader is able to obtain a higher payoff
than could be obtained in a simultaneous move
situation. 
The Bayesian form of such a game, then, implies
that each agent must be of a given set of types. For
our security do main, we have two agents, the
police force and the adver sary. While there is only
one police force type, there are many different
adversary types, such as serious terrorists, drug
smugglers, and petty criminals, denoted by L. Dur-
ing the game, the adversary knows its type, but the
police do not know the adversary’s type; this is an
incomplete in formation game. For each agent (the
police force and the adversary) i, there is a set of
strategies 
σ
i
and a utility func tion u
i
: L
⫻ σ
1
× 
σ
2
→ ᑬ. Figure 4 shows a Bayesian Stackelberg game
with two follower types. Notice that fol lower type
2 changes the payoff of both the leader and the fol-
lower. We also assume knowing a priori probabili-
ty p
l
, where l represents the type of adversary (1, 2,
and so on), of the different follower types (that is l
∈ L). Our goal is to find the optimal mixed strate-
gy for the leader to commit to, given that the fol-
lower may know the leader’s mixed strategy when
choosing its strategy and that the leader will not
know the follower’s type in advance. 
Techniques for Solving 
Stackelberg Games 
In previous work it has been shown that finding an
optimal solution to a Bayesian Stackelberg game
with multiple fol lower types is NP-hard (Conitzer
and Sandholm 2006). Re searchers in the past have
identified an approach, which we will refer to as
the multiple-LPs method, to solve Stackel berg
games (Conitzer and Sandholm 2006), and this can
be used to solve Bayesian Stackelberg games. This
approach, however, requires transforming a
Bayesian game into a nor mal form game using the
Harsanyi transformation (Harsanyi and Selten
1972). Similarly one may apply efficient algo-
rithms for finding Nash equilibria (Sandholm,
Gilpin, and Conitzer 2005), but they require the
same Harsanyi trans formation. Since our research
crucially differs in its nonuse of the Harsanyi trans-
formation, it is important to understand this trans-
formation and its impact. 

tải về 0.64 Mb.

Chia sẻ với bạn bè của bạn: