mkse150  Homework 4

Overview

Do these exercises from the E&K textbook: 15.10.2, 15.10.5, 16.8.3, 16.8.5.
A programming problem follows below, and it relates to the first two questions above.
The paper problems should be handed in at the beginning of class on Apr 4,
and the program should be submitted via turnin by midnight the same day.

Programming Background

In this assignment you will be working with a sponsored search auction and assigning bids to slots using the VCG mechanism. Your job is to implement the algorithm by editing the file Auction.java.

Setting up the Project

Download this eclipse project hw4.zip and Import it into Eclipse.
In the Package Explorer, open hw4/src/DefaultPackage.
Highlight DriverSSA.java and run it. You should get a dozen lines, ending with this:
      clicks    price   profit   bidder
slot:  10.00     0.00     0.00   null
slot:   8.00     0.00     0.00   null
slot:   7.00     0.00     0.00   null
slot:   5.00     0.00     0.00   null
sums:  30.00     0.00     0.00
This means that you have succeeded to compile and run the provided programs.

The 3 numeric columns above are the click-through rate, the price charged for that slot, and the profit expected for the bidder in this slot. The final column is the name of the bidder, and since you haven't done the work yet that column is all null right now. The last row is the expected number of clicks served, the revenue to the auctioneer, and the total profit to the bidders.

Getting Oriented in the SSA

The file DriverSSA.java generates different examples of a Sponsored Search Auction. (Initially, most are commented out.) After constructing one of these objects, it will print out the slot table and the bid table, and then call executeVCG (which is what you will be writing).

Open the file Auction.java. Inside the class, you will see these member fields:

	public final String query;
	public final Vector<Bid> bids;
The query variable says what phrase is being auctioned; you won't need it. The bids Vector holds a name and value (max price) for each player. The constructor for the Auction object guarantees that bids are always arranged in decreasing order of value. The only other data structure you need comes as a parameter to the execute method:
	public void execute(Vector<Slot> slots) {...
By perusing the Slot.java file you will find that it retains a click-through rate (clickThruRate), the assigned bidder, the price the bidder offered, and the profit the bidder is expected to garner. You are going to fill in everything in this data structure except clickThruRate. The slots are always given in decreasing order of click-through rate.

Note that execute is a void method. Its results are carried back to the caller by altering the entries in the slots vector.

Conducting the Auction

Your job is just to finish writing executeVCG. Allocate slots and prices according to the Vickrey-Clarke-Groves mechanism.

When you get your algorithm working, go back to DriverSSA and uncomment those lines in main so that you get more test cases. The first example has as many slots as bidders, but later ones may not be that way. Make sure your code can handle other cases as well.

Peruse the results to see if you believe them. You might find some surprising effects by considering related auctions. For example, Rick's RollerRama altered something; what happened to their total profit? The profit of the auctioneer changed somewhere by doing something under their own control. What was it, and what effect did it have? Don't hand in the answers to these questions; just know the answers.

Finishing up

Use turnin to turn in your Auction.java file.