King’s College London
This paper is part of an examination of the College counting towards the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board.
Degree Programmes
Module Code Module Title Examination Period
MSc, MSci
7CCSMAMS
Agents and Multi-Agent Systems January 2015 (Period 1)
Time Allowed Rubric
Calculators
Notes
Two hours
ANSWER THREE OF FIVE QUESTIONS.
All questions carry equal marks. If more than three ques- tions are answered, the three answers with highest marks will count.
Calculators may be used. The following models are permit- ted: Casio fx83 / Casio fx85.
Books, notes or other written material may not be brought into this examination
PLEASE DO EXAMINATION ROOM
2015 King’s College London
NOT REMOVE THIS PAPER FROM THE
January 2015 7CCSMAMS
1. a.
Consider the following scenario:
Your personal digital assistant (PDA) sees that you have received an email inviting you to give a talk at a conference in Buenos Aires next year. Your PDA knows that giving this talk will be good for your career and that you have always wanted to visit South America, so it immediately starts to arrange some provi- sional travel and accommodation plans. It communicates with several travel operator digital agents to secure the best deal and sends you a message that gives details of this deal and explains why it is your best option.
i. Explain whether you think it would be appropriate to model the PDA from the scenario above as an agent. Make sure you refer to each of the main properties of intelligent agents and explain how they relate to the scenario.
[8 marks]
ii. Explain whether the environment that the PDA is situated in is ac- cessible or inaccessible.
[2 marks]
Give an example of a situation where an agent (which could be a soft- ware agent, a robot or a human) has to balance reactive and proactive behaviour. Explain why it is important that the agent nds a good balance of reactive and proactive behaviour.
b.
QUESTION 1 CONTINUES ON NEXT PAGE
Page 2
SEE NEXT PAGE
[7 marks]
January 2015 7CCSMAMS
c. A utility function over runs is dened by the function ur : RE → R. A utility function over environment states is dened by the function ue : E → R.
(Recall: E is the set of all possible environment states; Ac is the set of all possible actions; RE is the set of all possible runs over E and Ac that end with an environment state; R is the set of real numbers.)
i. Is the following statement true: Every utility function dened over runs can be expressed by a utility function dened over states?
If true, show how a utility function dened over runs can be expressed by a utility function dened over states. If not true, then give a counter example of a utility function dened over runs that cannot be expressed by a utility function dened over states.
[5 marks]
ii. Is the following statement true: Every utility function dened over states can be expressed by a utility function dened over runs?
If true, show how a utility function dened over states can be ex- pressed by a utility function dened over runs. If not true, then give a counter example of a utility function dened over states that cannot be expressed by a utility function dened over runs.
QUESTION 1 CONTINUES ON NEXT PAGE
Page 3
SEE NEXT PAGE
[5 marks]
January 2015 7CCSMAMS
d. The game of paper-scissors-stone is a two player game where each agent simultaneously picks one of paper (P), scissors (Sc) or stone (St). The winner is determined as follows:
• P beats St,
• St beats Sc,
• Sc beats P,
• all other combinations result in a tie.
The opponent agent (the environment) plays P with probability 0.2, Sc with probability 0.3 and St with probability 0.5. The utility of winning is 1, the utility of losing is -1 and the utility of a tie is 0.
What is the expected utility of an agent that plays each of the following against the opponent?
i. P ii. Sc iii. St
Page 4
SEE NEXT PAGE
[6 marks]
January 2015 7CCSMAMS
2. a. The gure below shows an abstract argumentation framework.
a
c
h
j
f
b
d
g i
k
e
i. What are all the valid preferred labellings of the abstract argumen- tation framework above? Please say which arguments are IN, which are OUT and which are UNDECIDED under each valid preferred la- belling, and explain why this is the case. You must also explain why the labellings you give are the only valid preferred labellings.
[10 marks]
ii. Under what conditions is an argument acceptable under the preferred skeptical semantics?
[2 marks]
iii. Which of the arguments that appear in the abstract argumentation framework above are acceptable under the preferred skeptical seman- tics?
QUESTION 2 CONTINUES ON NEXT PAGE
Page 5
SEE NEXT PAGE
[2 marks]
January 2015 7CCSMAMS
b. An agent’s knowledge base ∆ is given below.
∆={a, b, d, a∧b→¬c, d→c, d→¬b}
Using the knowledge from ∆, it is possible to construct two arguments such that one undercuts the other. Identify two such arguments, giving the support and the claim of each. Make it clear in your answer which argument undercuts the other.
[6 marks]
c. Give an example of an application for which it would be appropriate to communicate using an argumentation-based dialogue. Explain why an argumentation-based dialogue is appropriate in this case.
[7 marks]
d. Explain, with the aid of examples, the three dierent aspects of a speech act.
[6 marks]
Page 6
SEE NEXT PAGE
January 2015 7CCSMAMS
3. a.Thepseudo-codebelowdenesthecontrolloopforapracticalreasoning agent.
1. B:=B0; /⋆ B0isinitialvalueofB⋆/
2. I:=I0; /⋆ I0isinitialvalueofI⋆/
3. while true do
4. get next percept ρ;
5. B:= brf(B, ρ);
6. D:= options(B, I);
7. I:= filter(B, D, I);
8. π:= plan(B, I);
9. while not empty(π) do
10. α:= hd(π);
11. execute(α);
12. π:= tail(π);
13. get next percept ρ;
14. B:= brf(B, ρ);
15. if not sound(π, I, B) then
16. π:= plan(B, I);
17. end-if
18. end-while
19. end-while
i. Identify any situations in which you think this agent would not be- have optimally, making reference to the pseudo-code to explain your answer.
[4 marks]
ii. Explain clearly how you would modify the pseudo-code in order to improve the agent’s performance.
QUESTION 3 CONTINUES ON NEXT PAGE
Page 7
SEE NEXT PAGE
[6 marks]
January 2015
b. Here is an example Concurrent MetateM agent system.
rp(ask1, ask2)[give1, give2] :
ask1 → ♦give1
7CCSMAMS
rc1(give1)[ask1] :
ask2 → ♦give2
start → ¬(give1 ∧ give2) start → (give1 → ¬give2)
start → ask1 ask1 → ask1
rc2(ask1, give2)[ask2] :
(ask1 ∧ ¬ask2) → ask2
For reference, these are the descriptions of the temporal operators used in this example.
φ φ true in previous state
♦φ φ true now or at some point in future φ φ true now and at all points in future
i. Describe the behaviour of the system above.
ii. Use a table like the one below to trace the operation of the system above for the rst six time steps.
[5 marks]
[5 marks]
time
rp
rc1
rc2
propositions
commitments
propositions
commitments
propositions
commitments
0
…
…
…
…
…
…
. . . . . . . QUESTION 3 CONTINUES ON NEXT PAGE
Page 8
SEE NEXT PAGE
January 2015 7CCSMAMS
c. Describe the two key problems that have to be solved in order to build a symbolic reasoning agent.
[6 marks]
d. Practical reasoning involves both deliberation and means-ends reasoning. Describe what these two terms mean.
[4 marks]
e. Explain what it means if an agent has the property of calculative ratio- nality when deliberating.
[3 marks]
Page 9
SEE NEXT PAGE
January 2015 7CCSMAMS
4. Consider the following task-oriented domain, which we refer to throughout this question as the postal domain. There are two postal workers P1 and P2 who each start at the post oce. Between them they must deliver post to houses at A, B and C and then each return to the post oce. The cost of delivering to a set of houses is the minimum distance that must be travelled in order to visit each house in the set and return to the post oce. The graph below shows the roads that the postal workers can travel on and the length of each road.
Post Office
5
A
3
2
B
6 C
In the initial task allocation, P1 has been allocated the tasks of delivering to houses A and B, and P2 has been allocated the task of delivering to house C. This means the conict deal is ({A, B}, {C}).
a. Explain what is meant if we say a deal is individual rational.
QUESTION 4 CONTINUES ON NEXT PAGE
[2 marks]
Page 10
SEE NEXT PAGE
January 2015 7CCSMAMS
b. Explain what is meant if we say a deal is pareto optimal.
[2 marks]
c. For every possible deal δ in the postal domain given on the previous page:
i. Give the cost of δ to each of the postal workers P1 and P2. ii. Give the utility of δ to each of the postal workers P1 and P2.
iii. Say whether δ is individual rational. iv. Say whether δ is pareto optimal.
[10 marks]
d. What is the negotiation set of the postal domain given on the previous page?
[2 marks]
e. Briey describe the monotonic concession protocol for negotiation.
[8 marks]
f. Assume that each of the postal workers in the postal domain given on the previous page is using the Zeuthen strategy with the monotonic concession protocol to negotiate their allocated tasks. Explain what would happen in the negotiation by giving the proposals that get made in each round and stating which deal would be agreed on.
QUESTION 4 CONTINUES ON NEXT PAGE
Page 11
SEE NEXT PAGE
[4 marks]
January 2015 7CCSMAMS
g. Assume that each of the postal workers in the postal domain given at the start of this question is using the Zeuthen strategy with the monotonic concession protocol to negotiate their allocated tasks. It is possible for each of the postal workers to hide one or more of the tasks allocated to them in the original task allocation. Would either of the postal workers be able to benet from hiding any of their tasks? Make sure you clearly explain your answer.
[5 marks]
Page 12
SEE NEXT PAGE
January 2015
5. a. Consider the following payo matrix.
7CCSMAMS
i
defect
cooperate
3
3
4
2
1
1
2
4
j
defect
cooperate
i. Explain the notion of a dominant strategy. For each of the agents (for agent i and for agent j) identify any dominant strategies in the game dened in the payo matrix above. Justify your answer.
[6 marks]
ii. Explain the notion of a Nash equilibrium and identify any Nash equi-
libria that exist in the game dened in the payo matrix above.
[6 marks]
iii. Explain the notion of a Pareto optimal outcome and identify all out- comes of the game dened in the payo matrix above that are not Pareto optimal, explaining why this is the case.
[6 marks]
iv. Explain the notion of a strictly competitive scenario and say whether the scenario dened in the payo matrix above is strictly competitive, explaining why this is the case.
QUESTION 5 CONTINUES ON NEXT PAGE
Page 13
SEE NEXT PAGE
[6 marks]
January 2015 7CCSMAMS
b. Auctions on eBay are ascending price open-cry auctions but with a proxy bidding system, which proceeds as follows.
• The auctioneer sets a reserve price and an ending time.
• Potential buyers use a proxy bidding system. They submit a max- imum value to the proxy bidding system (this must be higher than the reserve price and the current auction price), which then makes incremental ascending bids on their behalf until their maximum value
is reached.
• The potential buyers are able to increase their maximum value at
any point during the auction, as long as it is higher than the current
auction price.
• The proxy bidding system ensures that the bidder who submits the
maximum value wins the auction and the price they pay is the max- imum value of the second highest bidder (plus a small increment).
Consider the following three possible bidder strategies.
• Maxing: At the start of the auction, submit to the proxy bidding system a maximum value that is equal to your true valuation of the item and then wait for the auction to close.
• Increments: If you are not the highest bidder, submit to the proxy bidding system a maximum value that is the current auction price plus the smallest increment possible until you reach your true valuation of the item.
• Sniping: Wait until the last moment before the end of the auction at which it is possible to submit a new maximum value to the proxy bid- ding system and then submit to the proxy bidding system a maximum value that is equal to your true valuation of the item.
QUESTION 5 CONTINUES ON NEXT PAGE
Page 14
SEE NEXT PAGE
January 2015 7CCSMAMS
Assume there are only two potential buyers for an eBay auction, BuyerA and BuyerB. BuyerA’s true valuation of the item is ¿50 and BuyerB’s true valuation of the item is ¿60. The reserve price is ¿40 and the increment value is ¿1. What would be the outcome of the auction in the following situations? Say who would win the auction and what price they would end up paying.
i. BuyerA uses maxing and BuyerB uses maxing.
ii. BuyerA uses increments and BuyerB uses sniping. iii. BuyerA uses increments and BuyerB uses maxing.
Page 15
FINAL PAGE
[9 marks]