THE UNIVERSITY OF WARWICK
LEVEL 7 Open Book Assessment [2 hours]
Department of Computer Science
CS4041 Agent-based Systems
Instructions
1. Read all instructions carefully and read through the entire paper at least once before you
start writing.
2. There are 5 questions. You should attempt 4 questions.
3. All questions will carry the same number of marks unless otherwise stated.
4. You should handwrite your answers either with paper and pen or using an electronic device
with a stylus (unless you have special arrangements for exams which allow the use of a
computer). Start each question on a new page and clearly mark each page with the page
number, your student id and the question number. Handwritten notes must be scanned or
photographed and all individual solutions should (if you possibly can) be collated into a
single PDF with pages in the correct order. You must upload two files to the AEP: your
PDF of solutions and a completed cover sheet. You must click FINISH ASSESSMENT
to complete the submission process. After you have done so you will not be able to upload
anything further.
5. Please ensure that all your handwritten answers are written legibly, preferably in dark blue
or black ink. If you use a pencil ensure that it is not too faint to be captured by a scan or
photograph.
6. Please check the legibility of your final submission before uploading. It is your responsibility
to ensure that your work can be read.
7. You are allowed to access module materials, notes, resources, references and the internet
during the assessment.
8. You should not try to communicate with any other candidate during the assessment period
or seek assistance from anyone else in completing your answers. The Computer Science
Department expects the conduct of all students taking this assessment to conform
to the stated requirements. Measures will be in operation to check for possible misconduct.
These will include the use of similarity detection tools and the right to require live
interviews with selected students following the assessment.
1
9. By starting this assessment you are declaring yourself fit to undertake it. You are expected
to make a reasonable attempt at the assessment by answering the questions in the paper.
Please note that:
– You must have completed and uploaded your assessment before the 24 hour assessment window
closes.
– You have an additional 45 minutes beyond the stated duration of this assessment to allow for
downloading and uploading the assessment, your files and technical delays.
– For further details you should refer to the AEP documentation.
Use the AEP to seek advice immediately if during the assessment period:
• you cannot access the online assessment;
• you believe you have been given access to the wrong online assessment;
Please note that technical support is only available between 9AM and 5PM (BST).
Invigilator support will be also be available (via the AEP) between 9AM and 5PM (BST).
because:
• you lose your internet connection;
• your device fails;
• you become unwell and are unable to continue;
• you are affected by circumstances beyond your control (e.g. fire alarm).
Please note that this is for notification purposes, it is not a help line.
Your assessment starts below.
2
1. Consider the following instance of rock-paper-scissors
Consider three populations: ª (always rock), « (always paper), ¬ (always scissors).
As their name says, individuals in these populations always play the same strategy, no
matter the opponent.
At each round, individuals are paired, equally likely, from one of the three populations,
and are made to play k times against each other. So, each individual has 1
3
chance to play a
game against an individual from either population, including its own, and each such game
is repeated k times.
(a) What is the expected utility at the end of the first round for each of these strategies,
for k = 2.
[8]
(b) Assume now that ¬ mutate into the population °, which play against the opponent
empirical mixed strategy, breaking ties in favour of scissors. This means that, at the
beginning, ° starts with scissors, chooses the subsequent moves best responding to
the opponent empirical mixed strategy and always chooses scissors when indifferent
among some actions to play.
What is the expected utility at the first round for °, for k = 2?
[8]
(c) Consider strategies ¬, ª, «and °. Identify the evolutionarily stable strategies with
respect to the pool above, for k = 2.
[9]
3
2. Three elves are each wearing a hat. The colour of each hat can be either red or blue
and this is decided uniformly at random. Moreover, the colours of the hats are chosen
independently of each other. Each elf can see the others’ hats but not their own. No
communication is allowed.
(a) Describe the set of possible worlds and each elf’s indistinguishability relation. [8]
(b) Describe the event that all elves wear the same colour in terms of possible worlds and
calculate its probability. [8]
(c) The elves are required to complete this task: at least one of the elves has to shout a
colour, trying to guess their own. If more than one elf shouts a colour, they need to do
so simultaneously (e.g., no shout can be informed by other shouts). If all guesses are
correct, then all the elves survive, otherwise they are all beheaded.
Figure 1: Wumpus World
3. Figure 1 is an instance of the Wumpus World, with one Wumpus (W), one pit (P) and a
heap of gold (G). The agent can only perceive whether a square is breezy (b) or smelly (s).
As usual, the squares surrounding a pit are breezy and those surrounding the Wumpus are
smelly.
The agent starts at the bottom left corner. The agent can attempt a single move to any of
the adjacent squares from where she finds herself.
The agent will reach the intended square with probability 0.8 and the pit square (regardless
of the initial position) with probability 0.2.
If she reaches the square with the Wumpus she dies, getting utility -50. If she reaches the
square with the gold she wins, getting utility +100. Squares with no pit, Wumpus or gold
have utility 0.
The only pit in the game is always random: if the agent enters that square, she gets sent
with probability 1
6
to any square in the grid (including the always random pit square itself).
Hitting the wall has the effect of leaving the agent in the same square.
(a) Calculate the expected utility of moving to the right from the starting square, showing
the procedure you use to get to your result. Assume that the agent has perfect
knowledge of the environment (i.e., she knows she is playing on the grid depicted
above) and the discounting factor is 1. [8]
(b) Consider now the case in which the agent starts at the bottom left square, but it has
only explored that one square. Calculate the expected utility of moving to the right,
considering the fact that the agent knows the shape of the grid, and that there is only
one always random pit, one Wumpus and one heap of gold scattered around and they
are all in three separate squares. The agent assumes that all possible grid configurations
consistent with her knowledge have equal probability, and has a discounting
factor of 1. Show the procedure you use to get to your result. [8]
(c) Give the values of the discounting factor γ ∈ [0, 1] such that all actions have zero
expected utility. [9]
5
4. A monopolist is facing the threat of a competitor entering the market. The competitor
can either enter or stay out. If the competitor stays out, the competitor gets 1 and the
monopolist 4. If the competitor enters, the monopolist can either fight or share the market.
If the monopolist fights they both get 0, if the monopolist shares they both get 2.
(a) Model this scenario as an extensive game and calculate all the pure strategy Nash
equilibria. [8]
(b) Calculate the backwards induction outcome. [8]
(c) Modify the payoffs of the competitor so that the resulting game has no unique backwards
induction outcome. [9]
5. Some elves just found a treasure. Each piece of the treasure needs two elves to be carried
and each group of elves receives +1 for each piece they manage to carry. elves can only
collect once, i.e., they cannot go back and collect more pieces.
(a) Model this as a cooperative game and describe the value function. [8]
(b) Show whether the core of the game is non-empty. [8]
(c) Calculate the payoff that each elf receives in a stable imputation. [9]