Game theory

Game theory [47] describes the mathematics of individual decisions made by several agents in a shared environment. Each agent has a number of alternatives from which to choose. The utility obtained by each agent depends on the combined choice of all of them and so a matrix is used to specify the utility obtained by each. In general, the agents are self-interested in that there is no particular relation between their individual utility functions. However, in the application of game theory to fully cooperative dialogue it happens that their utility functions are the same, meaning that they favour the same outcomes. The objective of each agent is to make choices that maximise its expected utility. Where agents make a sequence of decisions, a game tree can be used with a node representing each decision. It is possible to calculate an equivalent matrix for any given game tree. The most interesting games are where agents choose simultaneously, or do not immediately find out the other agents' choices. However, in this thesis, agents take turns to make their choices which are immediately observed, and so all that is required is to choose the one that will maximise the agent's utility.

Game theory will be used in this thesis to provide a quantitative aspect to the dialogue planner's choice. Traditional dialogue plan rules are used to generate the alternatives available to the agent, but these alternatives then form a game in which the agent chooses the alternative with the maximum expected utility.

The area of Bayesian games is particularly relevant. Bayesian games generalise standard games to those of incomplete information. In a standard game, every agent knows everything about the alternatives available to the agents and their utility functions. In a Bayesian game, such information is probabilistically known to the agents. Harsanyi [31] showed that uncertainty about applicability of actions can be modelled using the utility function by just using very negative values for those actions. Then, Bayesian games need only be concerned with uncertainty about the utility function. Each agent has a type, which determines its utility function. Each agent uses a set of nested beliefs about the type of the other agents. These beliefs take the form of probability distributions over types. To calculate the utility of an alternative, the agent needs to evaluate the expected utility over the types. This calculation is much the same as that used by the dialogue planner described in this thesis. Instead of using beliefs about types, the planner directly models the alternatives available to the agent through STRIPS preconditions, whose satisfaction is determined using beliefs about the domain state.

Gmytrasiewicz and Durfee [25] have developed a method of computing the utility of games using a probabilistic model of belief, which has its foundation in Bayesian games. While the planner presented here was developed initially without knowledge of this work, it has close similarities. They use a "Recursive Modelling Method", which represents the game in canonical form, that is, as a game matrix. At the root of a tree is a complete matrix, specifying all of the alternatives available in the game. At each node, a belief is taken, and a pair of edges are annotated with the probability of each value of the belief. For each edge, a child matrix is constructed, in which alternatives whose preconditions are disabled by the belief have had their row removed from the matrix. By performing a weighted sum over the leaf matrices in the tree, the expected utility of each alternative can be found. While the Recursive Modelling Method is equivalent to the game trees that will be used in this thesis, it does not provide any way of constructing an RMM tree from plan rules, nor is it clearly explained how the child matrices may be obtained from their parents by consulting the nested belief model. The emphasis of the RMM is on applications in military strategy, using gathered intelligence to inform the nested belief model. They have performed some experiments with human subjects, and found good agreement between the strategies chosen by a human player, and by the RMM.