Practice-final - Practice final PDF

Preview

Summary

Practice final...

Description

Networks: Fall 2012 Jon Kleinberg and Eva Tardos

Practice Final Exam November 28, 2012

The final exam is Friday, December 7, 2:00 - 4:30 PM in Barton Hall (Central and East sections). It will be a closed-book, closed-notes exam. The final will be cumulative, in that it will draw from all parts of the course, both before and after the midterm. The best guide to the coverage of the exam is the contents of the course lectures; it will also be useful to review the homeworks and the readings. To help in studying, we are providing the following practice final exam below. It is structured to approximately resemble the real final, although of course the actual questions on the real final may cover topics from the course that are not explicitly the focus of any question here. The practice final questions are not meant to be handed in; rather, we will discuss them at the final exam review sessions and during office hours. Office hours will be held at their usual times up through the time of the final exam with the exception of the office hours Wednesday Dec 5. Instead, we will have a review session Wednesday Dec 5 starting at 3:00 PM in Kennedy 116 (where we ordinarily hold lecture).

(1) (6 points) A new disease has started to spread among a population of domestic animals on a large farm, where it wasn’t present before. Animals live in very crowded quarters. An infected animal typically meets 150 other animals before the infection is discovered, and infects each of these animals it meets independently with probability .01. To control the disease two alternatives have been proposed. Proposal 1. The farm manager can distribute preventative medicine to the animals. The medicine is not very effective, but it would decrease the probability of infection from 0.01 to 0.007. Proposal 2. The farm’s veterinarian points out that the animals exhibit subtle signs of the disease soon after catching the disease. He proposes to hire extra caretakers for the animals, who will watch for this subtle sign each day, and will quarantine animals who show sign of being infected. Unfortunately, the animals can be infectious even before the sign shows. Taking this measure will decrease the number of other animal that an infected animal meets before getting quarantined to 90. Ideally, the farm would want to take both measures, but due to the ongoing financial crisis they cannot afford to do both. Which of the two measures would you suggest the farm to implement? Explain your answer.

(2) (6 points) Consider a good that has network effects in the sense of our model from Chapter 17. Consumers are named using real numbers between 0 and 1. The reservation

price for consumer x when a z fraction of the population uses the product is given by the formula r(x)f (z), where r(x) = 1 − x and f (z) = 25z. Suppose that the good is sold at price of 4. (a) What are the possible equilibrium fractions of the population purchasing the good? (In case it is useful, remember √ that the formula for solutions √ to the quadratic equation 2 − 4ac −b − b2 − 4ac −b + b and x = ax2 + bx + c = 0 is x = .) 2a 2a (b) Which of the equilibria you found in part (a) are stable? Explain.

(3) (6 points) Figure 1 depicts the links among six Web pages. Find the equilibrium values for the Basic PageRank Update Rule run on these six pages. Show your work.

A

B

C

E

D

F

Figure 1: A collection of Web pages for question 3.

(4) (6 points) Consider the network on the figure below. Assume this is a part of the Web where nodes are Web pages, and edges are pointers. In this question we consider the (small) graph on the figure below rather than the real whole Web to explore the Bow-Tie structure of the web.

Figure 2: Web for question 4.

(a) Identify which nodes belong to the largest strongly connected component. (b) Identify the set of nodes IN, that have a path reaching the largest strongly connected component, but cannot be reached from it. (4c) Identify the set of nodes OUT, that can be reached from the largest strongly connected component, but no path from them reaches the largest strongly connected component. (4d) Some parts of the web contain information that is outdated, a page that has been useful a while back, but has not been updated in a long time. Some of these pages still belong to the giant strongly connected component, but many do not. Is such a page more likely to belong to the IN or OUT part of the Bow-Tie structure of the web? Explain your answer.

(5) (6 points) In this question we will consider the effect of collusion between bidders in a second-price, sealed-bid auction. There is one seller who will sell one object using a second-price sealed-bid auction. The bidders have independent, private values drawn from a distribution on [0, 1]. If a bidder with value v gets the object at price p, his payoff is v − p; if a bidder does not get the object his payoff is 0. We will consider the possibility of collusion between two bidders who know each others’ value for the object. Suppose that the objective of these two colluding bidders is to choose their two bids to maximize the sum of their payoffs. Each bidder can submit any bids he likes as long as the bid is in [0, 1]. As in lecture we will assume that if there is a tie for the highest bid then the seller chooses at random between the bidders with the highest bid—one of them gets the object and pays the common highest bid (as it is also the second highest bid).

(a) Let’s first consider the case in which there are only two bidders with values v1 and v2 . What two bids should they submit? Explain. (b) Now suppose that there is a third bidder, with value v3 , who is not part of the collusion. This bidder knows that bidders 1 and 2 collude, but he does not know their actual values. Bidders 1 and 2 do not know bidder 3’s actual value. What bid should bidder 3 submit? What two bids should the two colluding bidders submit now? Explain.

(6) (6 points) You are working with a developmental psychologist studying children in a very small elementary school. The school combines pairs of grades in a single classroom. For example, they have grades 2 and 3 all in one classroom. You discover that there are some tensions developing in the classroom. While most students are friendly, there appears to be tension between girls and boys in the 3rd grade. To simplify the question, assume that the class is small enough that all pairs of students know each other well, and all pairs of students are friends, except pairs consisting of a girl and boy both in 3rd grade. Further assume that there are students of each sex in both grades. (a) Does the resulting graph of “friends” and “enemies” satisfy the structural balance property? Explain why, or why not. (b) The social environment of the class is not working well, and a few months later you discover that in addition to the tensions described above, now the two grades don’t get along either; that is, pairs of students in different grades are no longer friends. Does the resulting graph of “friends” and “enemies” satisfy the structural balance property? Explain why, or why not. (c) Can you suggest a likely development of the social structure of the classroom that would restore structural balance? Explain why your suggested development may be likely, and why it would restore balance.

(7) (6 points) In the payoff matrix below the rows correspond to player A’s strategies and the columns correspond to player B’s strategies. The first entry in each box is player A’s payoff and the second entry is player B’s payoff.

Player A

U D

Player B L R 2, 2 2, 0 0, 2 1, 6

(a) Find all Nash equilibria (both pure and mixed, if any) of this game. (b) Now increase player A’s payoff from the pair of strategies (D, L) from 0 to 4. Leave all other payoffs unchanged. Find all Nash equilibria (both pure and mixed, if any) of this new game. (c) Did increasing player A’s payoff from (D, L) increase player A’s average (or expected) equilibrium payoff? What are player A’s expected equilibrium payoffs in part (a) and part (b)?

(8) (6 points) When we considered diffusion of a new behavior in networks in lecture we viewed each edge as equal. In this problem suppose that the network consists of weak and strong edges. As in the model we considered in class, sharing a technology with a neighbor will confer benefits, however sharing technology along strong edges will confer twice as much benefit as sharing a technology along weak edges. Assume sharing technology A along a weak edge has a benefit of 3, while sharing A along a strong edge has a benefit of 6. Sharing technology B along a weak edge has a benefit of 2, while sharing B along a strong edge has a benefit of 4. In the figure below, strong edges are drawn as darker than weak edges. Assume that all nodes are using technology B except for the one node X which uses technology A. U

P

S X

Q

R

T

V

Figure 3: Network for question 8.

(a) Will any of X’s neighbors adopt technology A? if yes, which neighbor(s)? Explain your answer. (8b) Consider the set of nodes {T, U, V } that form tight group of friends connected by strong edges. Is there any set of initial adopters, that does not contain any of T , U or V , so that adoption spreads to this set? Explain how it can, or why it cannot.

(9) (6 points) (a) Suppose you are one of three people voting on a set of four alternatives named A, B, C, and D. The Borda Count will be used as the voting system. The other two voters have the rankings D ≻1 C ≻1 A ≻1 B D ≻2 B ≻2 A ≻2 C

You are voter 3 and would like alternative A to appear first in the group ranking, as determined by the Borda Count. Can you construct an individual ranking for yourself so that this will be the result? If so, explain how you would choose your individual ranking; if not, explain why it is not possible. (b) Let’s consider the same question, but with different rankings for the other two voters, as follows: D ≻1 A ≻1 C ≻1 B B ≻2 D ≻2 A ≻2 C

Again, as voter 3, you would like alternative A to appear first in the group ranking determined by the Borda Count. Can you construct an individual ranking for yourself so that this will be the result? If so, explain how you would choose your individual ranking; if not, explain why it is not possible.

(10) (6 points) Consider a scenario of a technology being considered for adoption by a population of users one by one. Assume that the probability that this technology is good (G) is P r(G) = 1/2. Any individual who rejects the technology receives a payoff of 0. The payoff for adopting depends on whether the technology is good or bad. Lets suppose that if it’s good, then the payoff obtained from adopting it is +1. If the technology is bad, then the payoff is −1. Each person in turn gets a signal about the quality of the product, and also observes the decisions made by all previous people. When the technology is bad, it is very likely that users get bad signals, but the probability of a good signal is not that high even when the technology is good. Concretely, the probability of a high signal when the technology is good is P r(H|G) = 3/5 (and hence P r(L|G) = 2/5), while the probability of a low signal when technology is bad is P r(L|B) = 4/5 (and hence P r(H|B) = 1/5). For this question, it may be useful to recall Bayes’ rule. For two events A and B, Bayes’ rule states that P r(A|B) =

P r (B|A)P r (A) . P r(B)

(a) Assume the first person gets a high signal. What is the probability that the technology is good (given the high signal)?

(b) Now assume that the first person gets a low signal. What is the probability that the technology is good now (given the low signal)? (10c) How should the first person make a decision: what should he/she decide conditional on a high signal? and what should he/she decide conditional on a low signal? (10d) Can the second person infer the signal of the first person from his decision? (10e) Assume the first person adopted the new technology. How should the second person make a decision? Give the decision the second person should make conditional on either high or low signal. Briefly explain your answer. [You do not need to write a proof, or compute probabilities. A brief argument is sufficient.]...