Dear class,
As promised, we're going to hold an auction for the project presentation
slots. The explanation is below. (If you're doing a project) you must bid
by tomorrow (Th) 11:59pm, by e-mail to me.
*If you fail to bid, I will interpret your bid as all 0s.*
Hopefully this will be fun. There will be presentation slots on 11/13,
11/18, and 11/20. Please note that the final project *writeup* is due on
11/24 for everyone, so that you can still add things after your
presentation.
Here's how it's going to work. You are going to bid some number of points
for each presentation day before the last day. This bid represents the
minimum number of bonus points by which you want to be compensated for
going in a slot on that day. (This number is implicitly 0 for the slots on
the last day, and are relative to a possible score of 100 on the
presentation part of the project.) Then we'll run a VCG mechanism.
Example:
Suppose we have four slots, one on day 1, two on day 2, and one on day 3.
A bids 25, 10 (meaning, he wants to be compensated 25 for going on the
first day, and 10 for going on the second day (and implicitly 0 for
going on the last day))
B bids 30, 20
C (who is way behind on his project) bids 80, 30
D (who is in good shape on his project) bids 15, 10
First, we choose the solution that minimizes cost. This is to put D
on day 1, A and B on day 2, and C on day 3, for a total cost of
15+10+20=45.
Let's determine A's compensation. To do so, we will solve for the
optimal solution in which A goes last. This is D on day 1, and B and
C on day 2, for a total cost of 15+20+30=65. From this we subtract
15+20=35 (the cost to other students, D and B, in the real solution)
to obtain a compensation of 30 bonus points
For B: the optimal solution with B last is: D on day 1 and A and C on
day 2 for a cost of 15+10+30=55. Subtract from this 15+10=25 to get a
compensation of 30 bonus points.
For C: C is already on the last day so the difference must be 0, i.e.,
C gets no bonus points.
For D: the optimal solution with D last is B on day 1 and A and C on
day 2 for a cost of 30+10+30=70. Subtract from this 10+20=30 to get a
compensation of 40 bonus points.
(Again, you can see the incentive for having your project in good
shape soon...)
Let me know if anything doesn't make sense (or if I made a mistake in
this example). How to solve the larger real instance is something
I'll have to deal with.
So, your bid should have 2 nonnegative numbers (probably decreasing)
separated by commas, e.g.
30, 20
represents you want to be compensated at least 30 for going on 11/13,
and at least 20 for going on 11/18 (and implicitly 0 for 11/20, the
last day). There should be one bid per team.
Please, no bids involving pi, e, or other craziness. No collusion, either
:-)
Best,
Vince