CE322 Algorithmic Game TheoryAssignment 2022/23 Answer all (four) questions below. The filename of each submitted file (report and matlab files) should contain your registrationnumber. For example, CE322 RegNumber Report.pdf, CE322 RegNumber Task3.m. Make sure that your code is easy to follow by adequately commenting on your code and/or brieflydescribing in the report the steps you take. Your assignment will be assessed on the quality of the files you submit –correctness, work qualityand quality of presentation– and how clearly you explain what you have done. Aim for precise andconcise answers and explanations. Explicit marking criteria have been uploaded in a separate document on moodle.Question 1 [25%]Four colleagues, A, B,C, and D, want to decide how to commute to work. The company they work foroffers a shuttle service, for a total cost of 12 pounds, that would be evenly split among the people whochose to use it. For example, if two people use the shuttle service, each of them would pay 6 pounds.Each person also has the option to drive with their own car to work. The cost for using their own car isfixed but different for each person: A’s cost for driving is 2; B’s cost for driving is 3, C’s cost for drivingis 5; D’s cost for driving is 11. Your tasks:a. [6% ] Give a formal definition of the game described above. Who are the players, what are theirstrategies and how are their utilities defined for each state (strategy combination).b. [9% ] Are there any strictly dominated strategies in this game? If so, reduce the game as much aspossible by eliminating them.c. [5% ] Identify all pure Nash equilibria of the game and their social cost (sum of costs).d. [5% ] What is the price of stability of the game?Question 2 [20%]Consider the following zero sum game G:A B C DX 1 1 2 5Y 0 3 4 4Z -3 2 2 4Your tasks:a. [4% ] Reduce the game as much as possible by removing any possible strictly dominated strategies.b. [4% ] Is there a pure Nash equilibrium in the remaining game? Justify your answer.c. [12% ] Compute a mixed Nash equilibrium using the indifference conditions of the players. Present boththe equilibrium and the analysis clearly. No coding is required.1Question 3 [25%]Consider the following general normal form game G. Your task is to find the correlated equilibriumthat maximizes the sum of players’ utilities, using Linear Programming in MATLAB. In your report,you need to present the equilibrium that you have computed, the linear program that you are solving(which should include the equilibrium conditions that are satisfied), and a screenshot of your MATLABinput AND output. Use the following ordering of variables when constructing your MATLAB input:pXA, pXB , pXC , pY A, pY B , pY C , pZA, pZB , pZC .A B CX 0,7 2,5 7,0Y 5,2 0,0 5,2Z 7,0 2,5 0,7Question 4 [30%]Consider the following sponsored search auction instance I: 2 slots. The top slot has a known click-through rate (CTR) ctr1 = 1 and the bottom slot has aknown click-through rate ctr3 = 0.5. 2 advertisers. Advertiser 1 has a private value-per-click v1 = 1 and advertiser 2 has a privatevalue-per-click v2 = 0.5. The utility of the advertiser (let’s call them i, i = 1, 2) is:– (vi p), if i is assigned to the top slot, where p is the price charged per-click in the top slot.– 0.5 · vi, if i is assigned to the bottom slot (price 0 is charged per-click in the bottom slot).Under the Generalized Second-Price (GSP) auction rule:- Advertisers are asked to place bids in the auction (players are supposed to declare their value perclick, but the bids aren’t always truthful!). Advertisers are then ranked according to their bidsand the advertiser with the highest bid is assigned to the slot with the highest CTR (top slot),the other advertiser is assigned to the slot with the lowest CTR (bottom slot). In case of a tie,advertiser 1 is allocated to the top slot. The per-click payment p at the top slot is set to be equalto the bid of the advertiser assigned to the bottom slot.a. [4% ] Compute the optimal/highest social welfare (sum of individual values) in I.b. [6% ] Let b1 and b2 denote the bids placed by advertiser 1 and 2, respectively, and assume b1 > b2.Formulate the conditions that need to be satisfied at equilibrium. The conditions should containonly variables v1, v2, b1 and b2.c. [8% ] Write a function in MATLAB that takes as input the bids of the two players and outputs theirutilities.d. [12% ] Assume the following strategy sets (the allowed strategies each player can make) S1 = {0, 0.5, 1}and S2 = {0, 0.5}. Write MATLAB code that computes all Nash equilibria in I, and outputs theequilibrium strategies and the associated social welfare. Your code can call the function of part c.You can (or not) follow a brute-force approach, i.e. consider all possible combinations of bids andfor each of them check if it is an equilibrium. Copy and paste your MATLAB code in your report,and explicitly mention where in your MATLAB code you guarantee that the equilibrium conditions aresatisfied. If your code successfully computes one or more equilibria, present them in the report alongsidetheir social welfare.