Assignments:
We are not having assignment due dates or formal assignments, instead, problems are to be posted individually. They are also displayed in reverse chronological order so newer problems are on top. Students should turn in the problem the week they want credit, but the problems expire after a certain point (so we can post solutions). Assignments should be e-mailed to social.networks.class.staff [at] gmail.com, or may be turned in to any TA at any lecture.
EXPIRING 6/5 11:59 PM
NOTICE THESE ARE DUE ON FRIDAY, NOT ON SUNDAY. WE WILL NOT ACCEPT ANY LATE ASSIGNMENTS.
Question 60 (3 points) Expires 6/5/2009 11:59 PM
Suppose there are two slots availabe, and the first has a click-through rate of 4 while the second has a click-through rate of 3. There are also two advertisers; the first has a value per click of 9 while the second has a value per click of 8.
(a) Determine the revenue of the search engine in the market-clearing equilibrium. Compare this to the revenue of the search engine were it to sell just one slot with a click-through rate of 4 (i.e., if it withholds the second slot).
(b) Now suppose a third advertiser enters the market with a value of 7 per click. Calculate the revenue of the search engine in the market-clearing equilibrium if it sells both slots and compare it to the revenue of the search engine were it to sell just one slot with a click-through rate of 4.
Question 59 (1 point) Expires 6/5/2009 11:59 PM
One key design decision for the search engines is to decide how many slots to sell. Discuss the conditions under which a search engine can increase its revenue by withholding slots. (HINT: see above problem.)
Question 58 (1 point) Expires 6/5/2009 11:59 PM
Imagine a new search engine enters the marketplace today and wishes to sell ads alongside its search results using a first-price auction. I.e., the search engine charges each advertiser his bid for each click he receives. Do you think this is a wise strategy for the search engine? Why or why not?
Question 57 (1 point) Expires 6/5/2009 11:59 PM
In a related business, many search engines offer to sell ads on third-party websites like blogs. The third-party websites receive a fraction of the revenue generated from ad sales on their site. If we imagine that these third-party websites are themselves strategic agents, then we must be concerned with their incentives when designing the market. Discuss the benefits and drawbacks of pay-per-impression and pay-per-click for this business.
Question 56 (2 points) Expires 6/5/2009 11:59 PM
Consider the housing allocation problem from lecture. Suppose there are three people on the market, A, B, and C. Person A is rich and owns two houses, h_A1 and h_A2, and wishes to consume two houses. B and C each own one house, h_B and h_C respectively. Derive a set of preferences in which A has an incentive to lie about her preferences over the houses if we use top-trading-cycles to clear the market.
Question 55 (2 points) Expires 6/5/2009 11:59 PM
Suppose there are two types of people in the world - red people and blue people. Red people can only donate kidneys to red people and blue people can only donate kidneys to blue people. Two people get sick and their spouses wish to donate kidneys to them. Each person is equally likely to be red or blue (your color is not correlated with the color of your spouse).
(a) What is the probability that a sick person receives a kidney if exchanges are not allowed?
(b) What is the probability that a sick person receives a kidney if exchanges are allowed?
Question 54 (2 points) Expires 6/5/2009 11:59 PM
In lecture we discussed how to exchange healthy kidneys between patients with incompatible donors. There is another sources of kidneys, so called "angel kidneys" (i.e., people who willing give up kidneys to complete strangers without having an intended recipient). Angel kidneys can be interpretted as nodes with no outgoing arcs. Modify the top-trading-cycles algorithm to handle this setting.
Question 53 (2 points) Expires 6/5/2009 11:59 PM
Consider the following matching market with given preferences.
Adam: Eve > Fran > Gloria > Helen
Bob: Fran > Gloria > Eve > Helen
Carl: Helen > Fran > Gloria > Eve
Dan: Eve > Fran > Helen > Gloria
Eve: Bob > Carl > Adam > Dan
Fran: Adam > Dan > Bob > Carl
Gloria: Bob > Carl > Adam > Dan
Helen: Dan > Helen > Adam > Carl
(a) Find a stable matching.
(b) Is Adam married to Eve in every stable matching? Why or why not? Is Bob married to Gloria in every stable matching? Why or why not?
Question 52 (1 point) Expires 6/5/2009 11:59 PM
Consider the stable marriage setting discussed in class. Construct a market (with at least two men, two women, and their preferences) in which there is exactly one stable matching.
Question 51 (2 points) Expires 6/5/2009 11:59 PM
Consider the the problem of gay stable marriage which is like our original stable marriage problem except that there are only men and each man has a preference list over other men. Find an instance of the gay stable marriage problem with four people in which there is no stable matching.
Question 50 (1 point) Expires 6/5/2009 11:59 PM
Consider the stable marriage setting discussed in class. As discussed there is a men-preferred matching and a women-preferred matching. There are also matchings in between. Notice that we might consider the men-preferred matching to be unfair because it is the worst stable matching for the women (and vice versa for the women-preferred matching). Discuss some possible fairness conditions that you might use to chose a stable matching that is more fair. In your discussion you should both describe your proposed conditions and discuss why they are fair.
Question 49 (3 points) Expires 6/5/2009 11:59 PM
Consider the following voting scenario. Suppose there are two alternatives, a "right" alternative and a "wrong" one. Unfortunately, it is costly to determine which alternative is the correct one. Hence, each person votes for the "right" alternative with probability p>1/2. You want to choose a voting system that maximizes the probability of selecting the "right" alternative.
(a) Under such assumptions, rank your preference between a dictatorship, an electoral system (as we have in the US), or a majority rule. Be sure to explain your ranking.
(b) Suppose the dictator will exert more effort in determining the "right" alternative than the average individual. In other words, the dictator selects the "right" alternative with probability q where 1 > q > p > 1/2. Now would you prefer a dictatorship over a majority? Why or why not?
(c) Now consider majority rule when voting is costly. Each person can pay $c for 0<c<1/2 to vote, in which case he/she votes for the "right" alternative with probability 1>p>1/2. Electing the "right" alternative is worth $1 to each person. Do you expect everyone to vote, no one to vote, or some fraction of the populace to vote in equilibrium?
Question 48 (1 point) Expires 6/5/2009 11:59 PM
Give the preference lists for a voting setting where the winner in majority rule is different from the winner in the Borda rule.
EXPIRING 5/31 11:59 PM
Question 47 (3 points) Expires 5/31/2009 11:59 PM
Problem 9 from part III of book.
Question 46 (3 points) Expires 5/31/2009 11:59 PM
Problem 10 from part III of book.
Question 45 (2 points) Expires 5/31/2009 11:59 PM
Attend the Distinguished Lecture Series Talk: Joan Feigenbaum on "Approximate Privacy: Foundations and Quantification" and/or read the related paper (http://www.cs.yale.edu/homes/jf/dimacs-2009-14.pdf). Write a short summary (1-2 paragraphs) about your reaction.
Question 44 (2 points) Expires 5/31/2009 11:59 PM
Problem 20 (Chapter 8, Page 157)
Question 43 (2 points) Expires 5/31/2009 11:59 PM
Consider selling an item to one of two bidders who have values U[0,1] (distributed uniformly between zero and six). As described in class, the optimal auction is the second price auction with reserve price 1/2. As we said in class the expected revenue of this auction in this setting is 5/12. Show how this can be calculated. Hint: analyze the probabilities and expected revenues of three cases: when both bidders bid above the reserve price, when one bidder bids above the reserve price, when no bidders bid above price.
Question 42 (2 points) Expires 5/31/2009 11:59 PM
Show how to calculate the Bayes-Nash equilibrium strategies in an all pay auction with 2 bidders with values U[0,1]. Recall that in the all-pay auction the highest bidder wins and all bidders must pay their bids. You must show your work to get credit. Hint: refer to the notes posted to the course web page.
EXPIRING 5/24 11:59 PM
Question 41 (2 points) Expires 5/24/2009 11:59 PM
Solve for the expected revenue of the First-Price Auction and Second-Price Auction for three bidders with values uniformly distributed between 0 and 1. Show your work. Compare the revenues. What do you think would happen if there were n bidders? (Hint: you may use your solution to homework problem 8.)
Question 40 (1 point) Expires 5/24/2009 11:59 PM
For the "used car" example described in class where
- the seller's value for a lemon 1 and a good car is 4,
- the buyer's value for a lemon is 2 and a good car is 8, and
- the probability of a good car is 1/4 (the probability of a lemon is 3/4),
recall that in equilibrium the seller only sells lemons. What is the price of anarchy?
Question 39 (1 point) Expires 5/24/2009 11:59 PM
For the "used car" example described in class where
- the seller's value for a lemon 1 and a good car is 4, and
- the buyer's value for a lemon is 2 and a good car is 8,
there is an equilibrium in which the seller sells both good cars and lemons as long as the probability that a car is good is high enough (in class we used a probability of 1/4, and this was not high enough for such an equilibrium). What is the smallest probability of the car being good for which selling both good cars and lemons is an equilibrium?
Question 38 (2 points) Expires 5/24/2009 11:59 PM
Question 18 (page 369)
Question 37 (2 points) Expires 5/24/2009 11:59 PM
Calculate the (mixed) Nash equilibrium of the following game. Show your work!
Left Right
Up (2,4) (3,1)
Down (3,3) (0,4)
Question 36 (1 point) Expires 5/24/2009 11:59 PM
Calculate the fixed-point for the following function f(x) = 1/4 + x - x^2 on the range [0,1]. Show your work!
