Rotecting national infrastructure such as airports, historical

mal for follower type l. Indeed this is a linearized
form of the optimality conditions for the linear pro-
gramming problem solved by each follower type.
We explain these constraints as follows: note that
the leftmost inequality ensures that for all j
∈ Q,
.
This means that given the leader’s vector x, a
l
is an
upper bound on follower type l’s reward for any
action. The rightmost inequality is inactive for
every action where q
1
j
= 0, since M is a large positive
quantity. For the action that has q
1
j
= 1 this inequal-
ity states that the adversary’s payoff for this action
must be ≥ a
l
, which combined with the previous
inequality shows that this action must be optimal
for follower type l. Notice that problem one is a
decomposed MIQP in the sense that it does not uti-
lize a full-blown Harsanyi transformation; instead
it solves mul tiple smaller problems using individ-
ual adversaries’ payoffs (indexed by l). Further-
more, this decomposition does not cause any sub-
optimality (Paruchuri et al. 2008). 
We can linearize the quadratic programming
problem 1 through the change of variables z
l
ij
=
x
i
q
l
j
. The substitution of this one variable allows us
to create an MILP. The details of this transforma-
tion and its equivalence to problem 1 are present-
ed in Paruchuri et al. (2008). DOBSS refers to this
equivalent mixed-integer linear program, which
can be solved with efficient integer programming
packages. Although DOBSS still remains as an
exponential solution to solving Bayesian Stackel-
berg games, by avoiding the Harsanyi transforma-
tion it obtains significant speedups over the previ-
ous approaches as shown in the experimental
results and proofs in Paruchuri et al. (2008). 
Bayesian Stackelberg Game for the Los
Angeles International Airport 
We now illustrate how the security problems set
forth by LAWA police can be cast in terms of a
Bayesian Stackel berg game. We focus on the check-
point problem for illustra tion, but the case of the
canine problem is similar. Given the checkpoint
problem, our game consists of two players, the
LAWA police (the leader) and the adversary (the
follower), in a situation consisting of a specific
number of inbound roads on which to set up
checkpoints, say roads 1 through k. LAWA police’s
set of pure strategies consists of a partic ular subset
of those roads to place checkpoints on prior to
adversaries selecting which roads to attack. LAWA
police can choose a mixed strategy so that the
adversary will be unsure of exactly where the
checkpoints may be set up, but the adversary will
know the mixed strategy LAWA police have cho-
sen. We assume that there are m different types of
adversaries, each with different attack capabilities,
planning constraints, and financial ability. Each

tải về 0.64 Mb.

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