Bayesian games

The planner must be capable of examining the actions that will be taken in different belief outcomes. For example, in a questioning dialogue, the belief outcome of the questioned agent determines the answer it is expected to give. Some representation of the set of belief states, and the plans that occur in each of these states is needed. In section 2.10 the theory of Bayesian games was described. In this theory, a probabilistic model of belief is used to determine the efficient strategy in a game by examining the applicable actions in each belief outcome, and so the Bayesian game model is appropriate. In evaluating a Bayesian game using the maximum expected utility rule, the utility of each strategy is determined in each of the belief outcomes of the user, and a weighted sum of utility is taken over those outcomes according to their probability. In each of the belief outcomes, a different game tree is obtained, since in different belief outcomes, different alternative acts are believed to have satisfied preconditions. The central design element of the planner is therefore an algorithm that can perform computations with Bayesian games.

In a game tree, the permissible alternatives available to an agent correspond with the edges at a node corresponding with that agent's turn in the dialogue. Those permissible alternatives are determined by the rules of the game. In keeping with the requirement that the dialogue is planned using hierarchical plan rules, the second design element becomes clear. A planner is required that can plan a step in a dialogue according to a given set of beliefs about the domain state and about the dialogue plan rules, and for each candidate step, an alternative be supplied to the algorithm that generates the game tree.