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
BSc, MSci
6CCS3AMS
Agents and Multi-Agent Systems January 2018 (Period 1)
Time Allowed Rubric
Two hours
ANSWER THREE OF FOUR QUESTIONS. ANSWER EACH QUESTION ON A NEW PAGE OF YOUR ANSWER BOOK AND WRITE ITS NUMBER IN THE SPACE PROVIDED.
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
Calculators
Notes
PLEASE DO EXAMINATION ROOM
2018 King’s College London
NOT REMOVE THIS PAPER FROM THE
January 2018 6CCS3AMS
1. a.
Consider a situation in which two agents 1 and 2 bid for items a and b. We assume each agent is only able to obtain at most one item. In other words, ⟨Z1,Z2⟩ is a possible allocation of the goods if and only if the following conditions all hold:
1. (Z1 ∪ Z2) ⊆ {a, b},
2. Z1 ∩ Z2 = ∅, and
3. for all i ∈ {1,2}: Zi ∈ {{},{a},{b}}.
The agents have the following valuation functions.
v1({a}) = 6 v1({b}) = 3 v2({a}) = 9 v2({b}) = 1
The outcome is determined by the Vickrey-Clarke-Groves mechanism (VCG mechanism).
i. Specify all the possible allocations and give the social welfare of each. [3 marks]
ii. Which allocation will be assigned if both agents are truthful about their valuations?
[2 marks]
iii. How much will each agent have to pay to the mechanism for the allocation you determined as the answer to Question 1.a.ii? Show your workings.
[6 marks]
iv. What utility will each agent get if they are truthful about their val- uations?
[4 marks]
v. The dominant strategy for each agent is to provide their true valua- tion. Show this to be the case by explaining why agent 1 does not have any incentive to lie about its valuation.
QUESTION 1 CONTINUES ON NEXT PAGE
Page 2
SEE NEXT PAGE
[4 marks]
January 2018 6CCS3AMS
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 in- cremental 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 a maximum value to the proxy bidding system 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 a maximum value to the proxy bidding system that is the current auction price plus the smallest increment possible until you reach your true valuation of the item.
• Sniping: Wait until just possible point when a bid imum value to the proxy valuation of the item.
QUESTION 1 CONTINUES
before the auction ends, i.e., at the last can be submitted, and then submit a max- bidding system that is equal to your true
ON NEXT PAGE
Page 3
SEE NEXT PAGE
January 2018 6CCS3AMS
c.
i. BuyerA uses maxing and BuyerB uses maxing.
ii. BuyerA uses increments and BuyerB uses sniping.
iii. BuyerA uses increments and BuyerB uses maxing.
i. What is the winner’s curse?
[3 marks]
[3 marks]
[3 marks]
[2 marks]
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.
ii. Consider an eBay auction as described in Question 1.b where all the bidders are using the maxing strategy. Does the winner of the auction risk suering from the winner’s curse? Justify your answer.
[3 marks]
Page 4
SEE NEXT PAGE
January 2018 6CCS3AMS
2. 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 identify 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. When interacting with you, your PDA does so through argumentation- based dialogues. Explain why it is appropriate for your PDA to com- municate with you through an argumentation-based dialogue in this scenario.
QUESTION 2 CONTINUES ON NEXT PAGE
Page 5
SEE NEXT PAGE
[4 marks]
January 2018 6CCS3AMS
b. The pseudo-code below denes the control loop for a practical reasoning 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.
[8 marks]
ii. Explain clearly how you would modify the pseudo-code in order to improve the agent’s performance.
QUESTION 2 CONTINUES ON NEXT PAGE
Page 6
SEE NEXT PAGE
[8 marks]
January 2018 6CCS3AMS
c. If an agent has the property of calculative rationality when deliberating this means that the intentions the agent selects will be those that were optimal when it started the process of deliberation.
Assume an agent with the property of calculative rationality is acting in a dynamic environment. What consequences might the agent observe as a result of having the property of calculative rationality and what steps might it need to take as a result of this?
[5 marks]
Page 7
SEE NEXT PAGE
January 2018 6CCS3AMS
3. 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({v2}) = 8 c({v1, v2}) = 11 c({v2, v3}) = 12
c({v1}) = 3 c({v3}) = 4
c({v1, v3}) = 7 c({v1, v2, v3}) = 15
The initial encounter in the above scenario is δ = ⟨{v1, v2}, {v3}⟩ and the agents are following the monotonic concession protocol.
a. Briey describe the monotonic concession protocol for negotiation.
[7 marks]
b. What is the utility of the deal δ′ = ⟨{v1}, {v2, v3}⟩ for robot R1?
[2 marks]
c. What is the utility of the deal δ′ = ⟨{v1}, {v2, v3}⟩ for robot R2?
[2 marks]
d. Which of the possible deals are Pareto optimal?
e. Which of the possible deals are individual rational?
QUESTION 3 CONTINUES ON NEXT PAGE
[5 marks]
[5 marks]
Page 8
SEE NEXT PAGE
January 2018 6CCS3AMS
f. Which of the possible deals are in the negotiation set? Explain your answer.
[4 marks]
g. If the robots negotiate the task allocation in the scenario above, what will the outcome be? Explain your answer.
[4 marks]
h. Can either agent benet from deceiving the other by hiding one of its tasks? Explain your answer.
[4 marks]
Page 9
SEE NEXT PAGE
January 2018
4. a. Consider the following voter prole:
40voters: B≻C≻A≻D 30voters: C≻B≻A≻D 25voters: D≻B≻C≻A
6CCS3AMS
5voters: A≻C≻B≻D
Identify who is the winner under each of the following voting rules. Show
your workings. – Plurality.
– Instant runo. – Borda count. – Copeland rule.
QUESTION 4 CONTINUES ON NEXT PAGE
[14 marks]
Page 10
SEE NEXT PAGE
January 2018 6CCS3AMS
b. Consider the following voter prole:
43voters: A≻B≻C 12voters: B≻A≻C 45voters: C≻B≻A
The winner is determined through a linear sequence of pairwise elections with the following agenda:
A,B,C
i. What is the outcome? Show your workings.
ii. Construct the majority graph for this voter prole.
[4 marks]
[3 marks]
iii. Is it possible to x the agenda to give a dierent winner than you de- termined for Question 4.b.i? Explain the reasons for your answer.
[6 marks]
c. 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.
[6 marks]
Page 11
FINAL PAGE