6CCS3AIN Lecture on Machine Languages SGT Tutorial Questions
Consider the following agent communications protocol:
2-AGENT DIVISION PROTOCOL
1. Description: This is a protocol for 2 autonomous agents, called A (Alice) and B (Bob).
2. Assumptions: The symbol p represents a fraction in the unit interval, [0, 1], such as 0.6.
3. Utterances: The following 6 types of utterances are permitted, for any value of p. (In these utterances, A and B are fixed agent names, while p is a variable.)
START(A,B) DIVIDE(A=p, B=1-p) ACCEPT(A=p, B=1-p) REJECT(A=p, B=1-p) NO-COMMENT
QUIT
4. Combination Rules:
Either agent may utter START(A,B) at any time. This starts a new dialog between agents A and B.
Either agent may utter NO-COMMENT at any time.
Either agent may utter QUIT at any time. If any agent does, the dialog ends.
Either agent may utter DIVIDE(A=p, B=1-p) at any time.
Whenever one agent utters DIVIDE(A=p, B=1-p), the other agent must utter one of the following three utterances:
ACCEPT(A=p, B=1-p) or REJECT(A=p, B=1-p) or NO-COMMENT
5. Termination Conditions:
The dialog terminates whenever one agent utters QUIT.
1
Question 1
(a) What application do you think the protocol is intended for? What type of dialog is it?
(b) What do you think is the intended meaning of the utterance DIVIDE(A=p, B=1-p)?
(c) What do you think are the intended meanings of ACCEPT(A=p, B=1-p) and REJECT(A=p, B=1-p)?
(d) Draw a tree diagram to show the possible dialog trajectories over time (with time along the horizontal axes, and with possible dialogs extending from left to right). (The tree may be infinite, so in this case only draw the first part of the tree.)
(e) Is it possible for dialogs to terminate?
(f) Will dialogs always terminate?
(g) A cycle in a dialog is a situation where the same collection of statements are made over and over again. Are cycles possible under this protocol?
(h) Suppose one agent wants to never reach agreement with the other agent, but also wants the dialog to last as long as possible. What strategy should that agent adopt? What strategy can the other agent adopt to counter this?
(Note: In legal disputes, deliberately delaying the proceedings as long as possible is sometimes a strategy used by one party to the dispute. Usually, this is done by a richer party against a poorer party, in the hope that the poorer party will give up due to the rising costs.)
Question 2 (Continuation)
After experiment with this protocol, an additional termination rule and additional combination rule are added.
Termination rule:
The following sequence of utterances leads immediately to dialog termination:
DIVIDE(A=p, B=1-p) ACCEPT(A=p, B=1-p)
Combination rule:
If either of the following sequences of utterances occurs in a dialog
DIVIDE(A=p, B=1-p)
REJECT(A=p, B=1-p) or
DIVIDE(A=p, B=1-p) NO-COMMENT
2
then the agent who uttered DIVIDE(A=p, B=1-p) must respond immediately with: DIVIDE(A=q, B=1-q) where q < p, in the case that A uttered DIVIDE(A=p, B=1-p),
or where q > p, in the case that B uttered DIVIDE(A=p, B=1-p).
Question 2
(a) What situation do you think the new Termination rule is intended to deal with?
(b) What is the immediate impact of the new Combination rule?
(c) Will dialogs now always terminate?
(d) What additional condition must we place on the variable p to ensure that dialogs always terminate?
3