Networks: Fall 2013 Practice Midterm SolutionsDavid Easley and Eva Tardos(1)Solution: The network does not satisfy structural balance. There are a few ways to find tripl esthat violate structural balance:Version 1: Finding a triangle with two positive edges and one negative edge. For example, if A isa stude nt in House 1, Year 1, B is a student in House 1, Year 2, and C is a student in House 2,Year 1, then A is friends with B and C,butB and C are enemies — leading to a triangle with twopositive edges and one negative edge, violating structural balance.Version 2: Alternately, finding a triangle with three negative edges. For example, if A is a studentin House 1, Year 1, B is a student in House 2, Year 2, and C i s a student in House 3, Year 3, th enall three are mutual enemies, which is a structure that violates balance theory.Version 3 Another way to show the network doesn’t satisfy the structural balance property is touse the fact that a network with the property can be split into two groups of friends, such that anytwo people in di↵erent grou ps are enemies, as in the Balance Theorem. It’s a bit tricky to arguecorrectly that such a s pli t doesn’t exist, but this is also an option.(2)Solution: In (a), B and E are the most powerful, because they are the only two nodes withmultiple negotiating partners that are completely dependent on them.In (b), nodes A and D get stronger because they now have the option of exchanging with eachother, and hence are no longer completely dependent on B and E. Nodes B and E get weakerbecause one set of weak negotiating partners (A and D respectively) have gotten stronger. NodesC and F get stronger because their sole re spective negotiating partners have gotten weaker, andso — whil e they are stil l somewhat weak — they are now in a better negotiating position.(3)Solution:(b) Solve x/100+ 2 = 5 and get x = 300 users choosing path I and y = 400  100 users choosingpath II. This is an equilibrium, as the two options take equal time, so no u se r can improve traveltime by switching path.(c) Route III is symmetri c with Route I, they take x/100 + 2 and z/100 + 2 time respectively.By using x and z only, and setting y = 0, we get the solution that x = y = 200. This is a Nashequilibrium as both routes take 200/100 + 2 = 4 and the route II not used is longer, so no us er canimprove travel time by switching path.Maybe the most common mistake is to solve for x/100 + 2 = z/100 + 2 = 5, which results i nx = z = 300 and y = 200. The point is that there is no equilibri um in which all three routes haveequal travel time; rather, Routes I and III get used , while Route II, with a longer travel time inequilibrium, is not used by anyone.(4) S olu ti on :(a) See figure below for the game matrix when A has two strategies C1and C2and B has twostrategies C2and C3.Player APlayer BC2C3C17, 10 7, 9C25, 5 10, 9Alternately, some students included the 3rd option for each firm, so ended up with a game wereboth players have 3 strate gy opt i on s C1,C2,C3. This is OK if the payo↵ for A usi ng C3or B usingC1is set so negative that they will never use it, as the problem states. But if the payo↵s for thesethird options are not set p r operly, then it actually changes the game into something di↵erent fromwhat the question describes.(b): The game has two pure Nash equilibria: (C1,C3) or (C2,C2).(c) Yes, there is a mixed Nash equilibrium. To get it, let p the p rob ab il ity of A choos in g C1andq the probabi l i ty of B cho os in g C2.Tofindp we need to make sure B is neutral between his twostrategies. This is done by the equation 10p  5(1  p)=9 getting p =4/5, so the probabil ityof A choosi n g C2is 1/5.Symmetrically, to get A to be neutral between her two choices we need to make sure 7=5q  10(1  q)henceq =3/5, and then the probability of B choosing C3is 2/5.(5) S olu ti on :With A and B priced at 2, z and x prefer C unless C has a price of at least 2 (if they bothwant C the market doesn’t clear). Wi t h C priced at 2, the market clears (x gets B, y gets A andz gets C). This is the lowest price for C. The highest C’s price can get is limited by making surez still wants C.IfC is priced at 7 the above is still market clearing, but for a price above 7, y andz both prefer A.(6)Solution(a) Bidding truthfully is a dominant strategy, so t he bidder should bid his value v3, no matterwhat the other two are doing.(b) The higher of the two values v1and v2should bid his value truthful l y, th e lower one shouldbid 0 (or withdraw), and his bid would be only serving to possibly set the price, and decrease theother bidders value for winning the auction.(7)Solution(a) F i gu re 1 shows the students’ network.ABC EDWSSSSSSSDFigure 1:(b) Anna, Bob, and Dharmendra each satisfy Strong Triadic Closure, since they each havestrong ties only to Carlota and Er e z, who have an edge between them. Carlota and Erez eachviolate Strong Triadic Clos ur e, since they each have strong ties to Anna and Dharmendra, bu tAnna and Dh ar men d ra are not connected by an