Networks: Fall 2012 Practice Final ExamDavid Easley and Eva Tardos December 1, 2013The final exam is Friday, December 13, 2:00 - 4:30 PM. We will be using tworooms for the final and it’s important to take the final in the correct room.Students with last name starting with a letter in the range A-J will take thefinal in Uris Hall G01, and those with last name starting with a letter in therange K-Z will take the final in the Statler Auditorium. It will be a closed-book,closed-notes exam. The final will be cumulative, in that it will draw from all parts of thecourse, both before and after the midterm, and including Chapters 19, 20, 21, and 23 fromthe last couple weeks of classes. The best guide to the coverage of the exam is the contentsof the course lectures; it will also be useful to review the homeworks and the readings.To help in studying, we are providing last year’s final, as a practice exam below. It isstructured to approximately resemble the real final, although of course the actual questionson the real final may cover topics from the course that are not explicitly the focus of anyquestion here. The practice final questions are not meant to be handed in; rather, we willdiscuss them at the final exam review sessions and during office hours.Office hours will be held through the final week of classes, as well as the week of thefinal, times will be announced on blackboard and Piazza. In addition, we will have a reviewsession Tuesday, Dec 10th starting at 3:00 (location to be finalized and announced soon).(1) (5 points)In the payoff matrix below the rows correspond to player A’s strategies and the columnscorrespond to player B’s strategies. The first entry in each box is player A’s payoff and thesecond entry is player B’s payoff.Player APlayer BL M RU 3, 3 2, 8 6, 2D 0, 3 1, 6 5, 8(a) Does either player have a strictly dominant strategy? For each player who has a strictlydominant strategy, say which strategy is strictly dominant.(b) Find all Nash pure Nash equilibria of this game.(c) Does this game have a mixed Nash equilibrium? If it has one, find it, or if it doesn’thave one explain why not.(2) (6 points) Consider the network of Web pages shown in Figure 1. We want todetermine the equilibrium PageRank values of these pages under the Basic PageRank UpdateRule.ADCBFEFigure 1: A network of Web pages.(a) Denote the equilibrium PageRank value of node A by a. What are the equilibriumPageRank values for all the other nodes in terms of a?(b) Give the equilibrium PageRank values of all nodes (not in terms of a, but as actualnumbers).(3) (6 points) Suppose three voters express their rankings among the alternatives X, Y ,and Z, and then a winner is chosen using the Borda count.The first voter (named 1) expresses the following rankingX 1Y 1Z, (1)and the second voter (named 2) expresses the following rankingY 2Z 2X, (2)You aren’t told what the third voter’s ranking was.(a) Suppose you know that X emerges as the winner (not in a tie) when the Borda countis applied to the three rankings (the two rankings that you know plus the one you don’tknow). From this information, can you tell for sure what voter 3’s ranking was? If youthink the answer is “yes,” say what voter 3’s ranking must be, with an explanation. If youthink the answer is “no,” explain why there’s not enough information to tell what voter 3’sranking is.(b) Suppose you know that Y emerges as the winner (not in a tie) when the Borda countis applied to the three rankings (the two rankings that you know plus the one you don’tknow. From this information, can you tell for sure what voter 3’s ranking was? If you thinkthe answer is “yes,” say what voter 3’s ranking must be, with an explanation. If you thinkthe answer is “no,” explain why there’s not enough information to tell what voter 3’s rankingis.(4) (5 points) Consider a set of politicians in a legislature. Each has an opinion oneconomic issues that can be described on a one-dimensional political spectrum, and each alsohas an opinion on social issues that can also be described on a (different) one-dimensionalpolitical spectrum. Thus, each politician can be represented by a point in two dimensions.(For example, a politician could be liberal on economic issues but conservative on socialissues.)economicissuessocialissuesFigure 2: A two-dimensional space of political opinions.Now, we would like to say that two politicians are allies if their views are sufficientlyaligned, and opponents otherwise. The way we do this is shown in Figure 2: we draw linesegments from the origin to the two politicians (represented as the two small circles in thefigure), and look at the angle formed by these line segments. If this angle is 90 degreesor less, then the two politicians are declared to be allies (since their views are sufficientlyaligned). If this angle is more than 90 degrees, then the two politicians are declared to beopponents.Let’s build a complete graph on the set of politicians, joining two of them by a positive(+) edge if they are allies and by a (-) edge if they are not.Here’s the question: Give an example of a set of politicians, each represented by a pointin the plane, for which the resulting complete graph does not satisfy the structural balanceproperty.(5) (6 points) Suppose that there are three types of used cars – good ones, medium ones andbad ones – and that sellers know which type of car they have. Buyers do not know whichtype of car a seller has, and sellers of good and medium cars have no way of proving whatkind of car they have.Buyers know that the fraction of used cars in the total population of used cars thatare good quality is 1/3, the fraction of used cars that are medium quality is 1/3, and thefraction of used cars that are bad quality is 1/3 (but as is typical in these situations, it isnot necessarily the case that all the owners of these used cars will choose to sell them). Thefollowing table summarizes the values of the different cars for sellers and buyers in thousandsof dollarsValue forgood carValue formediumcarValue forbad carbuyer 15 10 5seller 12 7 2We assume that buyers are risk-neutral; that is, they are willing to pay their expected valueof a car. You may assume that there are many more buyers than sellers.(a) Is there a self fulfilling expectations equilibria in the market when all kinds of cars aresold (bad, medium or good quality)? If there is one, what price are the cars sold? ifthere