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 2016 (Period 1)
Time Allowed Rubric
Calculators
Notes
Two hours
ANSWER THREE OF FIVE QUESTIONS.
Each question is worth in total 50 marks. Write your answers in the answer booklets provided. If more than three questions are answered, the three questions with the 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
2016 King’s College London
NOT REMOVE THIS PAPER FROM THE
January 2016
1. a. Consider the following payo matrix.
7CCSMAMS
i
defect
cooperate
-1
-1
2
1
1
2
-1
-1
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.
[9 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.
[9 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.
[9 marks]
iv. Is the game dened in the payo matrix above strictly competitive? Justify your answer.
QUESTION 1 CONTINUES ON NEXT PAGE
Page 2
SEE NEXT PAGE
[9 marks]
January 2016 7CCSMAMS
b. The payo matrix for the prisoner’s dilemma is given below. i
j
defect
cooperate
defect
cooperate
2
2
1
4
4
1
3
3
i. Explain why the TIT-FOR-TAT strategy (which cooperates on the rst round and on each round t > 1 does what its opponent did on round t − 1) won Axelrod’s iterated prisoner’s dilemma tournament. Make sure your explanation identies the dominant strategy for the prisoner’s dilemma and describes the performance of TIT-FOR-TAT when playing against the dominant strategy.
[8 marks]
ii. An agent in a multi-agent system encounters another agent for the rst time and they enter into an interaction that has the same payo matrix as the prisoner’s dilemma. Do you think it is rational for the agent to use the TIT-FOR-TAT strategy in this encounter? Make sure you explain your answer and identify any assumptions you make.
[6 marks]
Page 3
SEE NEXT PAGE
January 2016 7CCSMAMS
2. Two robots (R1 and R2) are collecting valuable items (v1, v2 and v3) from an abandoned warehouse. All valuable items must be collected and each valuable item is collected by a single robot.
We can dene this scenario as a task-oriented domain (TOD) as follows
⟨{v1, v2, v3}, {R1, R2}, c⟩ where the cost function c is dened as
c(∅) = 0
c({v1}) = 3 c({v2}) = 8 c({v3}) = 4
c({v1, v2}) = 11 c({v1, v3}) = 7 c({v2, v3}) = 12 c({v1, v2, v3}) = 15
a. What is a deal for the above scenario?
b. List all the possible deals for the above scenario.
QUESTION 2 CONTINUES ON NEXT PAGE
[4 marks]
[4 marks]
Page 4
SEE NEXT PAGE
January 2016 7CCSMAMS
c. Assume the initial encounter in the above scenario is δ = ⟨{v1, v2}, {v3}⟩.
i. What is the utility of the deal δ′ = ⟨{v1}, {v2, v3}⟩ for robot R1?
[4 marks]
ii. What is the utility of the deal δ′ = ⟨{v1}, {v2, v3}⟩ for robot R2? [4 marks]
iii. Which of the possible deals are Pareto optimal?
iv. Which of the possible deals are individual rational?
[8 marks]
[8 marks]
v. Which of the possible deals are in the negotiation set? Explain your answer.
[8 marks]
vi. If the robots negotiate the task allocation in the scenario above, what will the outcome be? Explain your answer.
[10 marks]
Page 5
SEE NEXT PAGE
January 2016 7CCSMAMS
3. a.Whatdoesitmeanifanitemforsaleatanauctionhascorrelatedvalue? Give an example of an item with correlated value.
[4 marks]
b. What does it mean if an item for sale at an auction has private value? Give an example of an item with private value.
c. Outline the protocol for the following types of auction: i. English
ii. Dutch
iii. First price sealed bid iv. Vickrey
d. What is the dominant strategy when participating in a Vickrey auction? Explain why the strategy you have described is dominant.
QUESTION 3 CONTINUES ON NEXT PAGE
Page 6
SEE NEXT PAGE
[4 marks]
[12 marks]
[10 marks]
January 2016 7CCSMAMS
e. Consider an auction over a single item with private value. There are four bidding agents (Ag1,Ag2,Ag3 and Ag4). Ag1 values the item at 10, Ag2 values the item at 30, Ag3 values the item at 20 and Ag4 values the item at 15.
Assume the agents are all behaving rationally (that is, they are seeking to maximise their utility). If an agent wins the auction, its utility is equal to their valuation of the item minus the price they pay for it; if an agent does not win the auction, its utility is zero.
Further assume that agent Ag2 knows how much each of the other agents values the item by, but that the other agents only know their own evaluation.
Explain what agent Ag2 should do in each of the following auctions and what the outcome would be (that is, say who would win the auction and how much they would pay for the item).
i. English ii. Dutch
iii. First price sealed bid iv. Vickrey
Page 7
SEE NEXT PAGE
[20 marks]
January 2016 7CCSMAMS
4. a.Explain,withtheaidofexamples,thethreedierentaspectsofaspeech act.
[9 marks]
b. Describe, with the aid of examples, the following types of speech act: i. representatives
ii. directives iii. commissives iv. expressives
v. declarations
QUESTION 4 CONTINUES ON NEXT PAGE
[15 marks]
Page 8
SEE NEXT PAGE
January 2016 7CCSMAMS
c. Consider an argumentation based dialogue system with two participating agents and whose topic is an argument about a belief. Each agent has a knowledge base (its beliefs), which is a nite set of arguments about beliefs, and uses the grounded semantics to reason about the acceptability of arguments. The dialogue system is dened as follows.
Moves:
– An agent can ASSERT an argument. – An agent can make a CLOSE move.
Protocol:
– The agents take it in turn to make a move.
– The rst agent to move ASSERTs an argument, which causes that
argument to become the TOPIC of the dialogue.
– For all other turns:
– An agent can ASSERT an argument as long as it has not previously been asserted and it attacks some argument that has previously been asserted during the dialogue.
– An agent can always make a CLOSE move.
Termination rules:
– A dialogue terminates if each agent makes a CLOSE move in succes-
sion (i.e. one agent makes a CLOSE move and then the other agent
makes a CLOSE move immediately afterwards).
– If the TOPIC of the dialogue is acceptable given the abstract argu-
mentation framework that is constructed from all of the arguments that have been asserted during the dialogue, then the outcome of the dialogue is Acceptable(TOPIC).
– If the TOPIC of the dialogue is not acceptable given the abstract ar- gumentation framework that is constructed from all of the arguments that have been asserted during the dialogue, then the outcome of the dialogue is NotAcceptable(TOPIC).
QUESTION 4 CONTINUES ON NEXT PAGE Page 9
SEE NEXT PAGE
January 2016 7CCSMAMS
i. Assume both of the agents are using Strategy 1 given below. Which type of dialogue (from Walton and Krabbe’s dialogue typology) would this produce? Explain your answer.
[8 marks]
ii. Assume both of the agents are using Strategy 2 given below. Which type of dialogue (from Walton and Krabbe’s dialogue typology) would this produce? Explain your answer.
Strategy 1: If it is permissible to ASSERT an argument from your beliefs, then ASSERT some such an argument; otherwise make a CLOSE move.
Strategy 2: If it is permissible to ASSERT an argument from your beliefs and adding that argument to the abstract argumentation framework that is constructed from all of the arguments that have been asserted so far during the dialogue causes the label (i.e. IN, OUT, or UNDECIDED) of the TOPIC to change, then ASSERT such an argument; otherwise make a CLOSE move.
QUESTION 4 CONTINUES ON NEXT PAGE
Page 10
SEE NEXT PAGE
[8 marks]
January 2016 7CCSMAMS
iii. Assume the agent who starts the dialogue is using Strategy 3 and the other agent is using Strategy 4, as given below. Which type of dialogue (from Walton and Krabbe’s dialogue typology) would this produce and why?
Strategy 3: If it is permissible to ASSERT an argument from your beliefs and adding that argument to the abstract argumentation framework that is constructed from all of the arguments that have been asserted so far during the dialogue causes the label of the TOPIC to change to IN, then ASSERT such an argument; otherwise make a CLOSE move.
Strategy 4: If it is permissible to ASSERT an argument from your beliefs and adding that argument to the abstract argumentation framework that is constructed from all of the arguments that have been asserted so far during the dialogue causes the label of the TOPIC to change to OUT, then ASSERT such an argument; otherwise make a CLOSE move.
Page 11
SEE NEXT PAGE
[10 marks]
January 2016 7CCSMAMS
5. a. Briey explain how the winner is decided under each of the following voting rules:
– Plurality,
– Instant runo, – Borda count, – Copeland rule.
b. Consider the following voter prole:
20voters: B≻C≻A≻D 30voters: C≻B≻A≻D 40voters: D≻A≻B≻C 10voters: A≻D≻B≻C
[16 marks]
Identify who is the winner under each of the following voting rules: – Plurality,
– Instant runo, – Borda count, – Copeland rule.
QUESTION 5 CONTINUES ON NEXT PAGE
[16 marks]
Page 12
SEE NEXT PAGE
January 2016
c. Consider the following voter prole:
4voters: A≻B≻C 3voters: B≻C≻A 2voters: B≻A≻C 2voters: C≻A≻B
Identify the Condorcet winner. Show your workings.
7CCSMAMS
d. Suppose that (s1, s2, s3) is an arbitrary Positional Scoring Rule (PSR), where s1,s2,s3 are positive whole numbers such that s1 ≥ s2 ≥ s3 and s1 > s3. Show that this voting rule does not select the Condorcet winner.
[14 marks]
Page 13
FINAL PAGE
[4 marks]