Tutorial questions: topic 6
Consider the following task oriented domain. There are two postal workers Ag1 and Ag2 who each start at the post office and must deliver some letters to particular houses. So a task relates to a particular letter and is represented by the house it must be delivered to. The cost of a set of tasks is the minimum distance the postal workers must travel to visit each of the houses he/she must deliver to and to return to the post office.
1. A specific scenario is shown in the figure below. We see that there are eight possible houses that the agents may need to visit (the nodes in the figure: a,b,…,h) and the post office is at the same location as house a. We assume that the distance between each node is 1 (e.g., the minimum distance from a to b is 1, the minimum distance from a to g is 2).
(a) Consider we have the following initial encounter: ⟨{b,f},{e}⟩
So there are three tasks that need performing (to deliver a letter to b, e, and f). Initially, Ag1 has been allocated the tasks to deliver to both b and f, and Ag2 has been allocated the task to deliver to e. The cost of this encounter to Ag1 is 8, and the cost of this encounter to Ag2 is also 8. (Remember, the cost of a set of tasks is the minimum distance an agent must cover in order to travel from the post office, visit each of the houses, and return to the post office.)
i. What are all the possible deals for this scenario?
({}, {b, e, f}), ({b}, {e, f}), ({e}, {b, f}), ({f}, {b, e}), ({b, e}, {f}), ({b, f}, {e}), ({e,f},{b}), ({b,e,f},{})
ii. Which deals are in the negotiation set? ({}, {b, e, f}), ({b, e, f}, {})
iii. What happens if the agents each use the Zeuthen strategy with the mono- tonic concession protocol to try to redistribute their tasks? What is the expected utility that each agent can expect to gain from this negotiation? (Reminder: expected utility is equal to the summation over all possible outcomes of the probability that each outcome will occur times the utility of that outcome.) (Reminder: if each agent is equally willing to risk the conflict deal, flip a fair coin to decide who should make a concession.)
1
First round: Ag1 proposes ({}, {b, e, f }); Ag2 proposes ({b, e, f }, {}). Ag1’s willingness to risk the conflict deal: 8−0 = 1.
8
Ag2’s willingness to risk the conflict deal: 8−0 = 1. 8
Since each equally willing to risk conflict, flip a coin to decide who concedes: 0.5 probability that Ag1 will concede, 0.5 probability that Ag2 will concede. Whoever concedes will match the other agent’s proposal in the next round, so there is 0.5 probability they will agree on ({},{b,e,f}) and 0.5 proba- bility they will agree on ({b, e, f }, {}).
This means that each agent has an expected utility of (0.5×0)+(0.5×8) = 4.
2
(b) Now consider that Ag1 deceives Ag2 by hiding the fact that it has been allo- cated the task to deliver to b in the initial allocation.
The (untruthful) initial encounter is thus presented as ⟨{f},{e}⟩, and so the agents will negotiate over the tasks e and f. Whatever the result of the negoti- ation is, Ag1 will also have to perform task b (since this task has been allocated to Ag1 in the truthful initial encounter, and Ag1 has no chance of giving it away since it has hidden this task from the other agent).
i. Which deals are in the negotiation set, given Ag1’s deception here? ({}, {e, f })
ii. What happens if the agents each use the Zeuthen strategy with the mono- tonic concession protocol to try to redistribute their tasks? What is the expected utility that each agent can expect to gain from this negotiation? (Hint: don’t forget that Ag1 will also have to perform the task that it hid, to deliver to b.)
Since there is only one member of the negotiation set, both agents will propose this in the first round and they will agree to: ({},{e,f}).
Thus, after the negotiation, Ag1 will have to carry out task b, and Ag2 will need to carry out tasks e and f. The expected utility of this to Ag1 is 6, the expected utility of this to Ag2 is 0.
3
2. A different postal office domain scenario is shown in the figure below. Here there are six possible houses that the agents may need to visit. Again, we assume that the distance between each node is 1.
(a) Consider we have the following initial encounter: ⟨{c, d}, {c, d}⟩.
So there are four letters that need to be delivered (two to house c and two to house d) and in the initial allocation each agent has to visit both house a and b. The cost of this encounter to Ag1 is 6, and the cost of this encounter to Ag2 is also 6.
i. Which deals are in the negotiation set?
({c, d}, {}), ({c}, {d}), ({d}, {c}), ({}, {c, d})
ii. What happens if the agents each use the Zeuthen strategy with the mono- tonic concession protocol to try to redistribute their tasks? What is the expected utility that each agent can expect to gain from this negotiation? (Reminder: expected utility is equal to the summation over all possible outcomes of the probability that each outcome will occur times the utility of that outcome.) (Reminder: if each agent is equally willing to risk the conflict deal, flip a fair coin to decide who should make a concession.) First round: Ag1 proposes ({}, {c, d}); Ag2 proposes ({c, d}, {}).
Ag1’s willingness to risk the conflict deal: 6−0 = 1. 6
Ag2’s willingness to risk the conflict deal: 6−0 = 1. 6
Since each equally willing to risk conflict, flip a coin to decide who concedes: 0.5 probability that Ag1 will concede, 0.5 probability that Ag2 will concede. Let’s assume that Ag1 loses the coin toss and has to concede. The small- est concession that Ag1 can make is to say it will take on task d. This would give the following values of the agents’ willingness to risk the con- flict deal (if Ag1 concedes to ({d}, {c}) and Ag2 sticks with their proposal ({c, d}, {})).
For Ag1: 4−0 = 1. For Ag2: 6−2 = 2. So this is enough to change the 463
balance of risk, and Ag2 will then need to concede.
The smallest concession that Ag2 can make is to say it will take on task d. This would give the following values of the agents’ willingness to risk the conflict deal (if Ag1 sticks with their proposal of ({d},{c}) and Ag2 concedes to ({c}, {d})).
4
For Ag1: 4−2 = 1. For Ag2: 4−2 = 1. So this is enough to change the 42 42
balance of risk, and they need to flip a coin to see who concedes next. Whoever loses the coin toss will need to concede to the proposal on offer by the other agent, so there is a 0.5 chance they will end up agreeing to ({a}, {b}) and a 0.5 chance they will end up agreeing to ({b}, {a}). Since the situation is symmetric, we get the same thing if we assume that Ag2 loses the initial coin toss.
The expected utility to each agent is (0.5 × 2) + (0.5 × 4) = 3.
(b) Now consider that Ag1 deceives Ag2 by pretending that it has also been allo- cated a task to deliver a letter to house f in the initial allocation.
The (untruthful) initial encounter is thus presented as ⟨{c, d, f }, {c, d}⟩.
i. Which deals are in the negotiation set, given Ag1’s deception here?
({c,d,f},{}), ({d,f},{c})
ii. What happens if the agents each use the Zeuthen strategy with the mono- tonic concession protocol to try to redistribute their tasks? What is the expected utility that each agent can expect to gain from this negotiation? (Hint: whatever the result of the negotiation is, no agent will actually have to visit house f since this task does not actually exist.)
First round: Ag1 proposes ({d, f }, {c}); Ag2 proposes ({c, d, f }, {}). Ag1’s willingness to risk the conflict deal: 4−0 = 1.
4
Ag2’s willingness to risk the conflict deal: 6−2 = 2. 63
Ag2 has to concede and they end up agreeing to ({d,f},{c}). The expected utility to Ag1 is 4. The expected utility to Ag2 is 2.
5