IB3J30 – Mathematical Game Theory
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
IB3J30 - Mathematical Game Theory
January 2021
Open Book Assessment - 2 hours
Instructions:
A. You have 2 hours and 45 minutes in total to complete your assessment and upload it to the AEP. This includes provision for technical delays.
B. There are 3 questions. You should attempt every question.
C. All questions will carry the same number of marks unless otherwise stated.
D. Save your file with your Student ID number and Module Code before submitting via the AEP.
E. 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.
F. Use the AEP immediately to seek advice if you cannot access the assessment, or believe you are registered to the incorrect paper.
Other information (read the following very carefully):
G. During the online assessment:
i. If you have a question about the content of your assessment you should ask the
Module Convenor/invigilator via the AEP query system. Do not send an email to them, or toundergraduate@wbs.ac.ukas this will not be answered.
ii. If you experience technical difficulties that prevent you from completing and
submitting your answer file please submit a mitigating circumstances case via my.wbs (or the University’s portal if you are anon-WBS student). Please do not attach your answer file as it will not be marked.
H. Your document:
i. You may handwrite your answers and scan/photograph these and convert to a single PDF file to upload to the AEP.
ii. Ensure your answers to each question follow the order in which the questions appear in the exam paper. Start each new question or question part on a new page and write the question number at the top of each page of your answers.
iii. Include on each page of your file your Student ID Number, the module code and the page number (using the format ‘x of y pages’ to confirm how many pages in total you are submitting).
iv. Within your one, single file you may include images (where required or where you want to use as part of your answer) (i.e. screenshots, photos or online drawings) of hand-written calculations, formulae, charts or graphs to complement your answers and show your workings. These images should be embedded at the point in the document where they are relevant in your answers.
v. Ensure that you label any images you include to inform and assist the marker. Where you have handwritten items please write legibly, preferably in dark blue or black ink, and ensure that it is not too faint to be captured by ascan or photograph. Remember, it is your responsibility to ensure that your work can be read.
I. Academic integrity (plagiarism/collusion):
i. You are allowed to access module materials, notes, resources, other reference materials and the internet during the assessment.
ii. You should not communicate with any other candidate during the assessment period as this could be interpreted as collusion and may lead to your work being reviewed for cheating. This includes the sharing of the exam paper with other students. Collusion is taken very seriously by the University.
iii. To further maintain the academic integrity of online assessments:
You are asked to provide details of your working out through the inclusion of images (photos or online drawings) which should include hand-written formulae, charts or graphs to indicate your approach to addressing the questions posed.
Warwick Business School reserves the right to viva any students suspected of cheating.
J. Submitting your answer file:
i. You have an additional 45 minutes beyond the stated duration of the assessment. This is for finalising your answer file, converting to PDF (if relevant), uploading to the AEP – ensure you upload the correct document, and submitting. This includes provision for technical delays.
ii. This online assessment will close at 11:45am UK time and you will not be able to submit your answer file after that time, unless you have Reasonable Exam Adjustments.
iii. If you have an agreement that entitles you to additional time (reasonable
adjustments), you should see the amount of additional time you have been granted on the AEP. If you have any queries regarding the amount of additional time you have been granted please emailexams@wbs.ac.uk.
iv. Only documents submitted via the AEP will be accepted and marked.
v. Incorrect documents submitted via the AEP maybe marked and that mark will be final. You should therefore use the 45 minutes of extra time granted to ensure you submit the correct document.
vi. Documents sent via email or through the mitigating circumstances portal will not be marked.
Your assessment starts below.
[Question 1]
Consider Nim with three positive piles of x,y, and z chips. Suppose x=21 andy=42.
a) What is the winning move when z=1? (10 marks)
b) If this is a winning game for some z, explain why there is only one winning move. (10 marks)
c) For what value of z is this a losing game? (10 marks)
d) Answer the previous question when x= 1(1-4n )/ (1-4 ) andy= 2(1-4n )/ (1-4 ). Hint: finite geometric series. (10 marks)
The game Half-Nim, denoted H(n) starts with a pile of n chips. The Players, starting with Player 1, alternately remove some chips but not more than half. That is, they can remove x chips, where 1 ≤ x ≤ n/2. The first player who cannot move loses. For example H(1) is losing. Let h(i) denote the Nim value of H(i), so for example h(1)=0.
e) Evaluate h(n) for n=0,1,2,3,4. (20 marks)
f) Show that h(2k)=k for k=0,1,… by evaluating h(2k+1) as h(y) for some y<2k. (20 marks)
g) Consider a game with a pile of size y played as regular Nim and a pile of size z played as Half-Nim. What is a winning move when y is 3 and z is 10? (20 marks)
[Question 2]
a) In the tree drawn above, what is the Value of the search game starting at O? State any theorem you use. (10 marks)
b) Is it optimal for the Searcher to arrive at the leaf nodes in the order A, B, D, C in a pure strategy (as part of an optimal mixed strategy)? Explain. (10 marks)
c) What are the optimal probabilities of hiding at the leaf nodes A, B, C and D? (20 marks)
d) Suppose a new network is obtained from this one by identifying nodes B, C and also nodes F, D. What is the Value of the search game on the new network? (10 marks)
Consider the circle network drawn below, with the given arc lengths.
e) What is the Value of the search game starting at O? Give two optimal hiding strategies. (10 marks)
f) For what values of xis hiding at A and B with probability x, C with probability 1-2x,optimal? (20 marks)
g) Suppose an arc of length 1 is added between nodes A and B. Can the new network have a smaller value than the original one? Give an upper bound on the value of the new network. Explain your answer quoting any result you use. (20 marks)
[Question 3]
A ball is hidden at location 1 in boxes 1,2 3 with probabilities (in percentage form) x, 30 and 10 and at boxes 1 and 2 at location 2 with probabilities 40-x. and 20, as shown below. At each location, boxes must be searched upwards (increasing order). Use the ‘forward looking method’ to get the answers.
a) For x=0, what is the optimal search sequence? What is the highest value of x for which this sequence remains optimal? (10 marks)
b) For what x is the search sequence 11221 optimal? (10 marks)
c) For which values of x are there multiple optimal search sequences? (20 marks)
Now consider the problem of finding the exit to the following maze with nodesO,A, B, C and unit length arcs x,y, z,w, assumed to be traversed left to right. If one goes from A to O on the toparc, that is denoted by x*, similarly for the other arcs. The passages at A have been numbered for use in parte).
d) How many Tarry paths are there (possible outcomes of RTA)? (10 marks)
e) Starting from O, find the RTA path resulting from always choosing the lowest numbered available passage at a node when there is a choice. For example, it starts with arc x. (20 marks)
f) What is the expected time to reach B from O with RTA? (Ignore the passage numbers at A.) (30 marks)
2023-12-23