COMP3477 Algorithmic Game theory - Summative Assignment: Nash Equilibrium, Strategies and Payoffs
Summative Assignment
Module code and title COMP3477 Algorithmic Game theory Academic year 2022/23 Submodule title Coursework title AGT Assignment Coursework credits 10 credits Lecturer Eleni Akrida Deadline* Tuesday, May 02, 2023 14:00 Hand in method Ultra
Additional coursework files • AGTassignment -21-22.tex (optional template for writing the answers to individual exercises)
• AGTassignment -21-22-GROUP.tex (template for writing the group report)
• AGT_Report_Peer_Evaluation_XXXXXX .docx (template for each student to fill in the ir peer evaluations on the group report )
• AGT_Podcast_Peer_Evaluation_XXXXXX.docx (template for each student to fill in their peer evaluations on the group podcast)
Required submission items and formats Per student, where XXXXXX is the CIS username: • SOLUTIONSXXXXXX.pdf • AGT_Report_Peer_Evaluation_XXXXXX.docx • AGT_Podcast_Peer_Evaluation_XXXXXX.docx
Per group, where XX is the group number: • ReportGroupXX .pdf • PodcastGroupXX .mp3
- This is the deadline for all submissions except where an approved extension is in place. Late submissions received within 5 working days of the deadline will be capped at 40%. Late submissions received later than 5 days after the deadline will received a mark of 0.
Important, please read first! •The assignment should be submitted via Blackboard Ultra; the deadline is May 2nd, 2pm. All deadlines can be found in SharePoint. •Familiarise yourself with the required submission items and formats as seen in the coversheet provided with the assignment specification. •Revisit and familiarise yourself with the policies on late submission of work and academic misconduct. Remember that you should not share your work or make it available where others can find it as this can facilitate plagiarism and you can be penalised. This requirement applies until the assessment process is completed which does not happen until the exam board meets in June 2023. •The level of achievement (good/very good/excellent/etc.) for each marking criterion is de- termined based on the marking and classification conventions published in the university core regulations (pp 15-16). •The Algorithmic Game Theory module is only assessed by this coursework (100% of the module mark). •A FAQ section in Blackboard Ultra will be updated with questions as they arise. In the following pages, you will find the specification of the individual component require- ments, followed by the specification of the group work component requirements. Please read those carefully before starting working on the assignment. Alongside the following pages, also read the guidance specific to this assignment provided in Ultra >Algorithmic Game Theory (22/23) >Assessment >Assignment >Guidance and Files. There you will not only find guidance on the group work but also all additional files that you will need to submit.
Algorithmic Game Theory Summative Assignment – Individual Component 2023 You should submit a PDF file named SOLUTIONSXXXXXX for the Individual Component of the assignment, where XXXXXX is your CIS username in lowercase letters. Solve exercises 1 - 4. Your answers should be either written using Latex (you may use the settings of the Latex file AGTassignment- 22-23.tex provided in Ultra >Algorithmic Game Theory (22/23) >Assessment >Assignment >Guidance and Files) and compiled into pdf (only the pdf should be handed in), or handwritten and scanned (in which case you should hand in the scanned pdf). Note 1: Make sure your answers are clear and detailed. Marks will be deducted if your answers are not clear or explanations are missing. Note 2: In the case where you return a scanned copy of your handwritten notes, please make sure your writing is legible and neat. Marks will be deducted if your answers are not neatly written. Note 3: The sum of the marks of the exercises in this sheet is 48 marks. You will receive the remaining 2 marks by submitting your individual peer evaluation forms (one for the group podcast and one for the group report). The remaining 50 marks will come from your group work. 1 Exercise 1. A set Nof|N|=nneighbours decide simultaneously and independently from each other, on one hand whether to build an extension to their home without getting proper planning permission, and on the other hand which of their neighbours to notify the local authority’s planning department about. The possible payoffs for a player i∈Nare: aifibuilt an extension without proper permission and none of the neighbours informed on him; bifidid not build an extension without proper permission; and cifibuilt an extension without proper permission and at least one of the neighbours informed on him. We assume that a > b > c . (a) Let A={v, nv}, where ‘ v’ stands for ‘violating the law (by building an extension without proper permission)’ and ‘ nv’ stands for ‘not violating the law (by not building an extension without proper permission)’. Clearly explain why the set of pure strategies of player iis the setSi={(xi, Ki) :xi∈A , K i⊂N}. What is the meaning of the set Ki? [2 marks] (b) Consider the strategy profile s= ((x1, K1), . . . , (xn, Kn)) and let ∆( s) be the set of players who are not violating the law in s, that is ∆( s) ={i|i∈N , x i=nv}. Also let K(s) be the set of players that are being informed on by at least one neighbour in s, that is K(s) =Sn i=1Ki. Determine a necessary and sufficient condition for sto be a Pure Nash Equilibrium of this game. Justify your answer. [7 marks] Exercise 2. Eve and Alice take turns removing 1 or 2 cards from a stack of 5 cards, i.e., each of them, every time their turn comes, pick 1 or 2 cards to remove. Eve starts the game. Whoever picks the last card wins 1 unit of payoff from the other player. (a) Write down a game tree representing this game in extensive form and find a solution (subgame perfect equilibrium) using backward induction. Clearly describe your steps in detail. Who wins? [5 marks] (b) Generalise your answer for the case where there are ncards in the stack, n∈N. Who wins? Justify your answer and show all your working. [12 marks] 2 Exercise 3. Consider the game in normal form below, played by 3 players, Mary, David and Kate. Mary chooses rows, David chooses columns, and Kate chooses matrices. Only Kate’s payoffs are shown in the matrices below: L R U60 D06 XL R U12 0 D 00 YL R U00 D012 ZL R U55 D55 W (a) Is there any partial (mixed) strategy profile of Mary and David to which Kate’s action Xis a best response? Justify your answer. [4 marks] (b) Examine whether Xis strictly dominated and justify your answer. [4 marks] (c) Let us replace the payoffs of Kate for playing matrix Was shown below, where ε∈R: L R Uεε Dεε W What is the range of values of ε≥0 that allows for Xto be a best response for Kate to some partial (mixed) strategy profile of Mary and David? [3 marks] Exercise 4. (a) Consider the following instances Gof the load balancing game: 1.m= 3 identical machines and n= 7 identical tasks with weights 5 ,5,4,4,3,3,3. 2.m= 4 identical machines and n= 9 identical tasks with weights 7 ,7,6,6,5,5,4,4,4. For each of them, compute a Pure Nash Equilibrium (PNE), A, using the LPT scheduling algorithm and also find an optimum assignment. Compute also the ratiocost (A) opt(G). Show all your working. [4 marks] (b) Generalise the instances above to show that for any number mof identical machines there exists an instance Gsuch that LPT computes a PNE, A, such that cost(A) = (4 3−1 3m)·opt(G). Show all your working. [7 marks] 3 Algorithmic Game Theory Summative Assignment – Group work Component 2023 Each group should submit 2 files:
- a PDF file named ReportGroupXX, and
- an MP3 file named PodcastGroupXX, where XX is your group number, e.g. 03 or 15. Only one member of the group should submit the above files. Your report should be written in LaTeX in the style of this pdf (single column, standard font size 10pt); you may use the settings of the LaTeX source file AGTassignment-22-23-GROUP.tex provided in Ultra>Algorithmic Game Theory (22/23) >Assessment >Assignment >Guidance and Files. One way to create your podcast would be for all members to join a Zoom meeting where you will record the podcast and afterwards extract the audio of the recording, or you can simply all gather in a room and record it. GUIDANCE FOR GROUP MEETINGS: •Each group should aim to meet for a total of 10 hours, i.e., 2 hours per week of term or (roughly) 1 hour per week throughout the duration of the coursework. •If you can meet in person, that is great and preferable. However, please be mindful of your team mates’ schedules and circumstances and find ways to meet that can facilitate everyone joining in and contributing to the work. •Aim to make the meetings productive, i.e, work should get done during the meetings and these should not be just occasions on which you have a chat about what needs doing. Examples of things that groups can do during meetings include: discuss the references, draft the report, write the podcast etc. •Before or during your first meeting, you should set aims for your upcoming meetings. •Before each meeting, you should set an agenda and during each meeting you should set an action log for what needs to be done be each member before the next meeting. •Make sure that you agree in advance, e.g., during your first meeting, how you will be sharing documents so that you can work together in real-time. For LaTeX files, Overleaf (http://overleaf.com/) is a good option to share documents to be worked on by more than one person at the same time. There are two options for the report that you may produce; each group should select only one of the options to submit. There is a single option for the podcast topic and each group should submit a podcast on that topic. REPORT: [25 marks] Option 1: Report on the complexity of Nash equilibria. Provide a combined synopsis of [1]1and [3]. You should read the papers, as well as any relevant literature for general context, and present a condensed combination of them in up to 5 pages (including references) so as to provide: •relevant background material; •an overview of the results; •intuition and/or description of reductions used to show the above results; •further discussion on related research and recent advances, providing references as appropriate. You can assume the reader has knowledge of complexity theory and basic knowledge of game theory, i.e. as a CS graduate would have, so the ‘relevant background material’ would be the material needed for a Computer Scientist - who is not specialised in game theory - to understand the report. Option 2: Report on the complexity of pure Nash equilibria and the Price of Anarchy in congestion games. Provide a combined synopsis of [3] and [4]. You should read the papers, as well as any relevant literature for general context, and present a condensed combination of them in up to 5 pages (including references) so as to provide: •relevant background material; •an overview of the results; •intuition and/or description of reductions and/or proofs used to show the above results; •further discussion on related research and recent advances, providing references as appropriate. You can assume the reader has knowledge of complexity theory and basic knowledge of game theory, i.e. as a CS graduate would have, so the ‘relevant background material’ would be the material needed for a Computer Scientist - who is not specialised in game theory - to understand the report. PODCAST: [25 marks] Podcast on auctions: Create a podcast that presents the subject of auctions in the context of game theory. Assume that your audience is Year 1 Computer Science students who are familiar with the definition of a Nash equilibrium. Your podcast should last a maximum of 12 minutes and should introduce the concept of auctions. You are expected to discuss theory and examples in order to teach your audience about auctions. Each member of the group is expected to speak in the audio, but there is no requirement to speak for at least a specific duration; however, if one member does not contribute much to the presentation of the podcast (speech), they are expected to contribute more towards other aspects of its creation, e.g. organisation of podcast, collection of material to be discussed etc. You will be assessed based on: •your knowledge and understanding in the relevant subject matter; •your argument and reasoning: clarity of thought, argument, analysis and use of evidence, integration of theory and/or practice, reflection; •your oral presentation/commentary: design of podcast including language and style, structure, tailoring to context, clarity, organisation, referencing; •your skills in the presentation: audibility, pace, timing, engagement. 1Note that there is a more condensed version of [1] (see [2]) where some of the details of proofs have been omitted; you can also use that as your reference, but be aware that [1] provides additional context so you may want to refer to it to clarify details of proofs that may not be as clear in the short version. References [1] C. Daskalakis, P. W. Goldberg, C. H. Papadimitriou, The complexity of computing a Nash equilibrium, SIAM Journal on computing 39(1): 195-259 (2009) [2] C. Daskalakis, P. W. Goldberg, C. H. Papadimitriou, The complexity of computing a Nash equilibrium, Commununications of the ACM 52 (2009) 89–97. [3] A. Fabrikant, C. H. Papadimitriou, K. Talwar, The complexity of pure Nash equilibria, STOC (2004) 604–612. [4] D. Fotakis, S. C. Kontogiannis, P. G. Spirakis, Selfish unsplittable flows, Theoretical Computer Science 348 (2005) 226–239.
