next up previous contents
Next: Demonstration 2: Holding the Up: Demonstrations Previous: Demonstrations   Contents

Demonstration 1: Telling and proposing

In this demonstration, the desirable property of the necessity of the propose act is shown. When an agent proposes an alternative that is unexpected by the other agent, a lot of information is communicated. The cost of convincing the hearer that it prefers a proposed alternative using a combination of tell acts could be greater than that of the propose. The approximate relation between the likelihood of the proposed alternative and the equivalent number of tells is given by information theory [66]. The cost in terms of number of tells is related to the information content of the propose, which is calculated from its probability by:

$\displaystyle H = log(1/p)$ (5.4)

For example, a propose that requires four beliefs to be held as preconditions, each of which has a probability of 0.5 in the hearer's mind, would correspond with a probability of one in two raised to the fourth power, or one in sixteen. This represents four bits of information, or four tell acts. On the other hand, an alternative whose probability of being chosen depends on the probability of just one belief, would at worst be as good as using a tell to communicate that belief.

As an example, agent 1 must choose whether to make fish or to make an omelette. If agent 2 has both sugar and fruit, it will save the eggs that would have been used for the omelette, and instead make fish allowing agent 2 to follow with a pavlova. This is quite an unlikely alternative though since it must have both sugar and fruit, whose belief values are both set at 0.5. The plan library for this problem is given in figure 5.4 and the corresponding game tree is given in figure 5.5.

The utility values for the problem were set at 50 for make-fish, 100 for make-omelette, and 100 for make-pavlova.

Figure 5.4: Plan library for propose example

Figure 5.5: Game tree for the domain-level plan

Figure 5.6: Game tree for the negotiation plan without proposing (top), and with proposing (bottom)
\includegraphics[width=1\textwidth]{figures/propose_plantree2.eps} \includegraphics[width=0.7\textwidth]{figures/propose_plantree3.eps}

Negotiation acts were added to the agent's repertoire one by one to demonstrate the utility gain offered by each. To start, there were no negotiation acts, and so the game tree just consisted of the domain-level tree, with a value of 100 for make-omelette. Next, the pass and tell acts were added. This produced the negotiation game tree in the top part of figure 5.6. This tree shows the best play only for the agent, so that each choice node is pruned down to only one alternative. Notice that in response to a pass, agent 2 uses a pair of tells in the true,true branch of the game tree. This subdialogue is efficient, and since it happens in one quarter of instances, the value for the tree is 102.5, which is a marginal gain over the 100 obtained from the plain domain-level plan. Next, the ask acts were added, but these were dominated by the pass and tell combination, and so the same result of 102.5 was obtained. Next, propose was added. This produced the tree in the bottom part of figure 5.6, with propose dominating instead of tell. Since the negotiation ends with the proposal, there is a smaller cost than in the top game tree in figure 5.6. The overall utility of the dialogue turns out to be 106, compared with 102.5 obtained without using propose. It can be concluded then that propose is a necessary member of the repertoire, since it is dominant in this example.

next up previous contents
Next: Demonstration 2: Holding the Up: Demonstrations Previous: Demonstrations   Contents
bmceleney 2006-12-19