Networks: Fall 2013 Homework 3David Easley and´Eva Tardos Due at 11:15am, Monday, September 30, 2013As noted on the course home page, homework solutions must be submitted by upload tocourse’s Blackboard site. The file you upload must be in PDF format. It is fine to write thehomework in another format such as Word; from Word, you can save the file out as PDF foruploading. You can choose type ”pdf” when you save the file, or print it and choose ”Adobepdf” as your printer. (Changing the file extension from doc, or docx to pdf does not changethe format, only makes the file unreadable)Blackboard will stop accepting homework uploads after the posted due date. We cannotaccept late homework except for University-approved excuses (which include illness, a familyemergency, or travel as part of a University sports team or other University activity).Reading: The questions below are primarily based on the material in Chapters 9 and 10 ofthe book.(1) (8 points) In this problem we will examine a second-price, sealed-bid auction for asingle item. Assume that there are three bidders who have private values v1, v2, v3. You arebidder 1. You know that bidders 2 and 3 bid according to the bidding rules: b2(v2) = 2v2and b3(v3) = 3v3. You know your value v1, but not the values of bidders 2 and 3. How muchshould you bid? Provide an explanation for your answer; a formal proof is not necessary.(2) (8 points) In this problem we will examine a second-price, sealed-bid auction for asingle item. We’ll consider a case in which true values for the item may differ across bidders,and it requires extensive research by a bidder to determine her own true value for an item— maybe this is because the bidder needs to determine her ability to extract value from theitem after purchasing it (and this ability may differ from bidder to bidder).There are three bidders. Bidders 1 and 2 have values v1and v2, each of which is arandom number independently and uniformly distributed on the interval [0, 1]. Throughhaving performed the requisite level of research, bidders 1 and 2 know their own values forthe item, v1and v2, respectively, but they do not know each other’s value for the item.Bidder 3 has not performed enough research to know his own true value for the item. Hedoes know that he and bidder 2 are extremely similar, and therefore that his true value v3isexactly equal to the true value v2of bidder 2. The problem is that bidder 3 does not knowthis value v2(nor does he know v1). He does know that bidders 1 and 2 know their own truevalues.(a) How should bidder 2 bid in this auction? How should bidder 1 bid?(b) How should bidder 3 behave in this auction? Provide an explanation for your answer;a formal proof is not necessary.1(3) (8 points) A seller announces that he will sell a painting using a sealed-bid, second-price auction. A group of I individuals plan to bid on this painting. Each bidder is interestedin the painting for his or her personal enjoyment; the bidders’ private values for the paintingmay differ, but they don’t plan to resell the painting. So we will view their values for thepainting as independent, private values (as in Chapter 9 of the text). You are one of thesebidders, in particular, you are bidder number i and your value for the painting is vi.You, and all of the other bidders, have just learned that this seller will collect bids, butwon’t actually sell the painting according the rules of a second-price auction using these bids.Instead, after collecting the bids the seller will tell all of the bidders that some other fictionalbidder submitted a bid equal to the highest of the actual bids. The seller announces thetwo highest bids and then says according to the rules of the “second price auction” a bidderwith the highest bid has won and must pay the second highest bid (including the fictionalbid this second highest bid is equal to the highest bid). The seller always selects the realbidder with the highest bid to be the “winner”. You, and all of the other bidders know thatthis will occur, but you cannot collude with any bidder.Is it a good idea for you to bid your value in this auction, or is it better to bid somethingdifferent? If your bid is different than your value, should it be higher or lower than yourvalue? Explain your reason for your answer. [You do not need to derive an optimal biddingstrategy. It is enough to explain whether your bid would differ from your value and if so inwhat direction.]2 3 1 3 Figure 1: residents and hospitals of problem 4(4) (8 points) Each year the medical community faces a large assignment problem inwhich a large number of hospitals are looking to fill positions for medical residents anda large number of students graduating from medical schools are looking to start medicalresidency programs in hospitals. A small example of such a problem is depicted in Figure 1above.2In this figure circles represent medical students and squares represent hospitals. The 9medical students are each looking to get a position in one of 4 hospitals. The numbers inthe square tell you how many residents they are looking for. The edges represent possibleassignments: if a medical student is not linked to a hospital then that student is not qualifiedto be a resident in that hospital.Is it possible to assign the medical students to hospitals in such a way that hospitals allfill their positions, and each medical student is assigned to a hospital that it’s linked to?Explain your answer in terms understandable to hospital administrators. In particular, giveone of the following two answers to the question:• If your answer is that the desired assignment exists, show the assignment.• If your answer is that the desired assignment doesn’t exist, provide a reason for thisnon-existence that will be understandable to hospital administrators. (That is, in thissecond case — if the assignment doesn’t exist — the reason should not use the words“network,” “graph,” or any other mathematical terms whose definitions come from theclass; also, it should actually be an explanation that will convince them, rather thanjust an assertion that it’s not possible.)(5) (10 points) You are watching the behavior of a matching market that you can onlyincompletely observe. Sometimes you can infer the values of the buyers from how the marketbehaves. Suppose you see that the valuations are as follows, where you know the valuationsof buyers y and z, but you know only that the