MKSE150   Homework 4

Answers

Text book exercise 15.10.2
The optimal allocation is to give slot a to x, b to y, and c to z.
The VCG prices are (6,4,0) respectively.

Text book exercise 15.10.5
(a) Similar to the previous case, the optimal allocation is to give slot a to x, and slot b to y. The VCG prices are 28, 0, for a and b respectively.
(b)Since the second-price auction is truthful, a and b bid their true values, i.e. 60,48 respectively. Therefore a wins and pays 48.
(c ) 48-28=20 is the excess revenue of the second-price auction.
(d) The revenue of VCG is v_y(r_a - r_b), and the revenue of the second-price auction is v_y(r_a). So in general the second-price auction generates higher revenue.

Text book exercise 16.8.3
(a) The probability that the first person chooses Accept, is equal to the probability she sees a high signal. Since the true state is Good, this probability is 3/4. Similarly, the probability of Reject is 1/4.
(b) Note that the decision of the second player depends only on her own signal. So we can write:
Pr(A,A) = 3/4 * 3/4 = 9/16
Pr(A,R) = 3/4 * 1/4 = 3/16
Pr(R,A) = 1/4 * 3/4 = 3/16
Pr(R,R) = 1/4 * 1/4 = 1/16
(c ) A cascade happens when the first and second person both choose the same decision. So the probability of a cascade is Pr(A,A)+ Pr(R,R) = 10/16

Text book exercise 16.8.5
(a) It is possible that a cascade of information has led to the wrong decision: The first 2 people who announced their vote were in favor of A. This made other people to ignore their own opinion and follow the majority.
(b) The solution is to hide people's opinion from one another, to get their true vote. For example this can be done by using ballot.

Programming Component

Here is one solution to the programming problem:

		float price= 0, lowerCTR=0;
		for (int i= slots.size()-1; i>=0; i--) {
			if (i>=bids.size()) { 
				slots.elementAt(i).price= 0;
				slots.elementAt(i).bidder= null;
				slots.elementAt(i).profit= 0;
			} else {
				if (i+1<bids.size()) 
					price+= bids.elementAt(i+1).value * (slots.elementAt(i).clickThruRate - lowerCTR);
				slots.elementAt(i).price= price;
				slots.elementAt(i).bidder= bids.elementAt(i);
				slots.elementAt(i).profit= bids.elementAt(i).value*slots.elementAt(i).clickThruRate - slots.elementAt(i).price;
				//System.out.println("price="+price);
			}
			lowerCTR= slots.elementAt(i).clickThruRate;
		}
Here is another:
		while (slots.size() > bids.size()) bids.add(new Bid());
		while (slots.size() < bids.size()) slots.add(new Slot());
		float price= 0, lowerCTR=0;
		for (int i= slots.size()-1; i>=0; i--) {
			slots.elementAt(i).price= price;
			slots.elementAt(i).bidder= bids.elementAt(i);
			slots.elementAt(i).profit= bids.elementAt(i).value*slots.elementAt(i).clickThruRate - slots.elementAt(i).price;
			if (i>0) 
				price+= bids.elementAt(i).value * (slots.elementAt(i-1).clickThruRate - slots.elementAt(i).clickThruRate);
			//System.out.println("price="+price);
			lowerCTR= slots.elementAt(i).clickThruRate;
		}