FIT 5226 (2022) Assignment 1 Classical and Evolutionary Game Theory Due midnight, August 28, 2022 This assignment is for a total of 25 marks and accounts for 15% of your final mark. Please note that detailed submission instructions will be made available on Moodle shortly. A note on assignments and tutorials: During assignment periods tutorials are structured to give you the maximum support for solving the assignment tasks. We will discuss the assignment in full detail and guide you in solving similar tasks to give you a solid grounding for your own work. You can also discuss your questions and ideas for the assignments with you tutors. Of course, there are limitations - tutors can’t give you solutions but they can vet your ideas and approaches and they can help you to overcome difficulties with coding. The tutorial in Week 4 will lay the groundwork for the task relating to payoff matrix properties. The tutorial in Week 5 will walk you through the basics of implementing an EGT simulations. There are three bonus marks for the final question. Bonus questions are optional and can help you make up for a shortfall in other tasks in this or other assignments. You can reach 25 marks (i.e. 100% of the assignment) without the bonus question and bonus marks will be added to the total of all your assignment results. For programming tasks, you can submit solutions in Python or in Mathematica and your code must be submitted in the form of a Jupyter Notebook or a Mathematica Notebook. If you are using Python you should use Numpy. Solutions that use excessive explicit iteration (for loops) rather than matrix operations may be penalised. 1. The Dining Problem: 2NF Games [8 marks] You will formalise and analyse the following game setting. Two rivalling sport teams want to go out after the competition. They are in a small remote town with only two restaurants: a good one and a mediocre one. Of course, everyone would prefer to go to the good one. The trouble is that the teams really dislike each other and they do not want to dine in the same restaurant. A team visiting the good restaurant will get 10 units of enjoyment from the dinner, a team visiting the mediocre one only 4 units. If both teams visit the same restaurant, the enjoyment will be reduced by 50% for each team. Tasks 1.1 [1 mark] Define the game in normal form by giving the players’ action sets and the payoff matrix. 1.2 [1 mark] Give all dominated strategies or state that there are none. 1.3 [1 mark] Give all pareto-optimal outcomes or state that there are none. 1.4 [1 mark] Give all pure Nash Equilibria. 1.5 [1 mark] What are the implications of the pure Nash equilibirum (equilibria) for the common social benefit? Discuss: is a Nash Equilibrium in this game a good solution that serves both teams well? 1.6 [2 mark] Is there a mixed strategy that would be a better solution in the sense of common social benefit? Give this strategy or the reasons why it does not exist. 1.7 [1 mark] Discuss the usefulness of a mixed strategy by contrasting the case where the game is only played once (the teams going out on a single occasion) with the case where it is played many times (the teams facing this situation every week). 2. Payoff Matrix Properties [6 marks] You will write code to determine certain properties of a 2-player game given in normal form. Your functions should work for any number of actions. You will receive at most 50% of the marks for each task if your functions only work for 2x2 matrices. You must not use any game theory libraries to solve this task. The purpose of the task is for you to compute these properties from scratch. If you are coding this in Python the only library you should use is Numpy. Tasks 2.1 [3 marks] Write a function Dominated(MX, MY) that takes as input two payoff matrices MX (for the row player) and MY (for the column player) and determines the dominated pure strategies for each player. It must return a list of two lists of integer values, where the i-th list contains the indexes of the dominated strategies for Player i. For example, for the game MX= 1 4 7 2 5 8 3 6 9 , MY= 3 1 3 2 2 2 4 2 3 it must return [[1,2], [2,3]]. 2.2 [3 marks] Write a function Nash(MX, MY) that takes as input two payoff matrices MX (for the row player) and MY (for the column player) and determines the pure Nash equilibria of the game. It must return a boolean matrix of the same shape as MX in which an entry M[i,j]=True means that the corresponding strategy profile is a Nash equilibrium and M[i,j]=False means that it isn’t. Note: You can obviously use your code from Task 2 to cross-check your answers to Task 1 and vice- versa. 3. The Tutors’ Problem: Replicator Dynamics [11+3 marks] You will write code to simulate replicator dynamics for the following game and use it to investigate its behaviour. Students and tutors are always trying to come to arrive for class just in time. Unfortu- 2 Assignment 1.nb nately, this means that everyone arrives at the car park at the same time! There are two different car parks available. Car park A is large but far away from the building. Car park B is small but close to the building. It takes only 2 minutes to walk to the tutorial rooms from car park B but 20 minutes from A. Unfortunately, it is never easy to find a parking spot straight away and the situation gets worse the more people are trying to find a spot. If n cars arrive simultane- ously at the large car park A, each will suffer an n-minute delay. In the smaller car park B, each car will even suffer a delay of 5n-minutes if n cars are simultaneously looking for a spot. For the purpose of this assignment, we are considering a group of fixed size n arriving on campus at the same time, i.e. we are considering an n-player game. All players are trying to choose a carpark so that they minimize the total time from their arrival until they reach the building, i.e. the sum of their wait time in the car park and the time to walk to the building. 3.1 [1 mark] Define the payoff for this game. 3.2 [1 mark] What specific type of game is this? (a formally defined type of game) 3.3 [2 marks] Determine the exact steady-state (rest point) of the replicator dynamics for this game analytically (ie. without using a simulation). 3.4 [7 mark] Implement a simulation of replicator dynamics for this game. Your simulation should plot the development of the population against time (think about what makes sense to plot to give useful information on the development of the population!). Note: Even though this is not particularly difficult to do from scratch with a solid working knowl- edge of basic coding, we will discuss in detail how to implement replicator dynamics simulations in the tutorial in Week 5. 3.5 [for 3 bonus marks] You will observe that the replicator dynamics simulation never settles on the exact rest point (try game sizes n=10, 20). Can you explain the reasons for this behaviour? Assignment 1.nb 3
欢迎咨询51作业君
