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]