Rotecting national infrastructure such as airports, historical
tải về 0.64 Mb. Chế độ xem pdf
|
| Harsanyi Transformation. The first step in solv-
ing Bayesian games for previous methods is to apply the Harsanyi transformation (Harsanyi and Selten 1972) that con verts the incomplete infor- mation game into a normal form game. Given that the Harsanyi transformation is a stan dard concept in game theory, we explain it briefly through a simple example without introducing the mathe- matical for mulations. Consider the case of the two follower types 1 and 2 as shown in figure 4. Fol- lower type 1 will be ac tive with probability α, and follower type 2 will be active with probability 1 – α. Performing the Harsanyi transfor mation in - volves introducing a chance node that determines the follower’s type, thus transforming the leader’s incom plete information regarding the follower into an imperfect information game. The trans- formed, normal form game is shown in figure 5. In the transformed game, the leader still has two strategies while there is a single follower type with four (2 * 2) strategies. For example, consider the sit- uation in the transformed game where the leader takes action a and the follower takes action cc ⬘. The leader’s payoff in the new game is calculated as a weighted sum of its payoffs from the two tables in figure 4, that is, α times payoff of leader when fol- lower type 1 takes action c plus 1 – α times payoff of leader when follower type 2 takes action c ⬘. All the other entries in the new table, both for the leader and the follower, are derived in a similar Articles 46 AI MAGAZINE c d a 2, 1 4,0 b 1,0 3,2 Figure 3. Payoff Table for Example Normal Form Game. Follower Type 1 c d a 2, 1 4,0 b 1,0 3,2 Follower Type 2 c' d' a 1, 1 2,0 b 1,0 3,2 Figure 4. Security Agent Versus Followers 1 and 2. fashion. In general, for n follower types with k strategies per follower type, the transformation results in a game with k n strategies for the follow- er, thus causing an exponential blowup losing compactness. Methods such as those described in Conitzer and Sandholm (2006) and Sandholm, Gilpin, and Conitzer (2005) must use this Harsanyi transfor - mation, which implies the game loses its compact structure. Nonetheless, the solutions their meth- ods obtain can be trans formed back into the origi- nal game. DOBSS One key advantage of the DOBSS approach is that it op erates directly on the Bayesian representation, without re quiring the Harsanyi transformation. In tải về 0.64 Mb. Chia sẻ với bạn bè của bạn:
|