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 2017 (Period 1)
Time Allowed Rubric
Calculators
Notes
Two hours
ANSWER THREE OF FOUR 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
2017 King’s College London
NOT REMOVE THIS PAPER FROM THE
January 2017 7CCSMAMS
1. a.
b.
What are the main properties of an intelligent agent? Make sure you explain what is meant by each of these properties.
[4 marks]
Five ongoing trends in computing that have played an important part in leading to the development of the eld of multi-agent systems are:
c.
ii. Explain how these trends have inuenced the development of the eld of multi-agent systems.
[7 marks]
Give an example of an application that would be well suited to being implemented as a multi-agent system and explain why this is the case, making reference to the properties you gave for part 1a. (Your example does not have to be an application that exists already; rather it should address a problem that is suited to the multi-agent system approach.)
• ubiquity,
• interconnection,
• intelligence,
• delegation,
• human-orientation.
i. Explain what is meant by each of these computing trends.
QUESTION 1 CONTINUES ON NEXT PAGE
Page 2
SEE NEXT PAGE
[5 marks]
[7 marks]
January 2017 7CCSMAMS
d. 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.
[5 marks]
Page 3
SEE NEXT PAGE
January 2017 7CCSMAMS
2. Consider the following task-oriented domain, which we will refer to through- out 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}).
QUESTION 2 CONTINUES ON NEXT PAGE
Page 4
SEE NEXT PAGE
January 2017 7CCSMAMS
a. Explain what is meant if we say a deal is individual rational.
b. Explain what is meant if we say a deal is pareto optimal.
[2 marks]
[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.
[6 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 stating (i) the proposals made by P1 and P2 in each round and (ii) the outcome of the negotiation.
QUESTION 2 CONTINUES ON NEXT PAGE
Page 5
SEE NEXT PAGE
[4 marks]
January 2017 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.
[7 marks]
Page 6
SEE NEXT PAGE
January 2017
7CCSMAMS
3. a.
Consider the following voter prole:
80voters: D≻C≻B≻A 60voters: A≻B≻D≻C 50voters: C≻B≻D≻A 30voters: A≻C≻B≻D
b.
What is the outcome when following each of the following voting pro- cedures:
i. Plurality;
ii. Instant runo;
iii. Borda count;
iv. Copeland rule.
Consider the following voter prole:
Voter1: D≻C≻B≻A Voter2: A≻B≻D≻C Voter3: A≻C≻D≻B
i. Draw the majority graph.
[3 marks]
[3 marks]
[3 marks]
[3 marks]
ii. Identify the Condorcet winner if one exists, otherwise explain why one does not exist.
QUESTION 3 CONTINUES ON NEXT PAGE
Page 7
SEE NEXT PAGE
[2 marks]
[2 marks]
January 2017 7CCSMAMS
c. Consider the following voter prole:
Voter1: A≻C≻B≻D Voter2: D≻A≻C≻B Voter3: B≻D≻A≻C
A linear sequence of pairwise majority elections are planned. i. Give an agenda that will ensure A is the overall winner.
ii. Give an agenda that will ensure D is the overall winner.
[4 marks]
[4 marks]
d. Explain what it means if a voting procedure satises the independence of irrelevant alternatives condition.
[2 marks]
e. Consider the following voter prole representing the truthful preferences of Alice, Bob, and Charlie:
Alice: B≻C≻A≻D Bob: C≻B≻A≻D Charlie: D≻C≻B≻A
Alice, Bob, and Charlie decide to hold a vote which will be decided ac- cording to the Borda count rule, with ties decided randomly.
In whose interest is it to vote strategically and falsely report their pref- erence (assuming they know the truthful preferences of the other two voters)? Specify the person as well as the ordering they should report instead of their true preference. Show your workings.
[7 marks]
Page 8
SEE NEXT PAGE
January 2017 7CCSMAMS
4. a. Below is some knowledge that an agent has about lms, where X is a variable that can be instantiated by any constant and constants all start with lower-case letters.
N inetiesF ilm(homealone)
ActionF ilm(homealone)
NinetiesFilm(X) ∧ ActionFilm(X) → ¬Watch(X) DirectedBy(johnhughes, homealone) DirectedBy(johnhughes, X) → W atch(X) DirectedBy(johnhughes, X) → ¬ActionF ilm(X)
i. Using the knowledge above, it is possible to construct two arguments that rebut one another. Identify two such arguments, giving the support and the claim of each.
[4 marks]
ii. Using the knowledge above, 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.
QUESTION 4 CONTINUES ON NEXT PAGE
Page 9
SEE NEXT PAGE
[4 marks]
January 2017 7CCSMAMS
b. The gure below shows an abstract argumentation framework.
a
c b
d
i. For the abstract argumentation framework above, give all valid la- bellings under the grounded semantics.
[4 marks]
ii. For the abstract argumentation framework above, give all valid la- bellings under the preferred semantics.
QUESTION 4 CONTINUES ON NEXT PAGE
Page 10
SEE NEXT PAGE
[6 marks]
January 2017 7CCSMAMS
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. When an agent is strategising in an argumentation-based dialogue, it can be useful to take into account what it knows about the other dialogue participant.
i. Describe two types of information the strategising agent might have about the other dialogue participant that could be helpful to the strategising agent in deciding which arguments to put forward during the dialogue.
[4 marks]
ii. It is typically the case that any knowledge the strategising agent has about the other dialogue participant is uncertain. Briey explain why this is a challenge when strategising for argumentation-based dialogues.
[4 marks]
Page 11
FINAL PAGE