Errata in the notes

I appeal for your help in fine-polishing the course notes as you re-read between now and the exams - particularly to root out typos and errors. I will add to this page whenever someone writes to me and I make a change to the notes. On page iv of the notes it will say something like "Last updated on December 3, 2015."

1. 03/12/15. Page 95. The "simple proof" of the Gibbard-Satterwaite theorem had a subtle mistake in the arguments of the last 3 paragraphs (either (i) or (ii) is true, but the final paragraph's argument was needing them both to be true). I have rewritten the argument in 3rd to last and last paragraph. Credit goes to Joe Wallace for noticing the issue.
2. 07/12/15/ Page 75. I have made a correction to the displayed equation in the proof of Lemma 16.4. Thanks to Alex Fisch.
3. 09/12/15 Thanks to Carla Groenland:
   - In 2.4: Typo: "optimality of the current solution. Recall that variables of the dual correspond to the Lagrange multipliers"
   - Just above 15.3, minimize changed to maximize.
   - In 16.4: Reference is changed to Lemma 16.4 instead of Lemma 17.1.
   - In 17.3: the knapsack equations changed so that at feasible solution: B=a^tx.
4. 17/01/16 Thanks to Matija Bucić:
   - 5.1 Second paragraph last sentence has surplus word that or lacks word note.
   - 18.3 second line of paragraph in step 1 is should be in
   - 21.2 Paragraph before example 21.4 last sentence
   - Lem 21.1 last sentence: the the
   Here I believe it would be helpful to point out that e(p) is the term which takes into itself the difference between auction systems in Lemma 21.1, I found it relatively hard to figure out what it is from the definition given and only after looking at examples did I figure out what it actually is.
   - Thm 21.2: the last term in rhs of (21.3) shouldn't include f(theta_1).
   - Also (21.3) is not necessarily equal to (21.4) (the term that we cancel out which evaluates at theta* and infinity might not be zero, problem is with the limits (0*infinity is not necessarily 0) for example if F(x)=(x-1)/x for x in [1,infinity) that term is strictly bigger than zero.
   Of course this doesn't “break the theorem” as this term is also independent of the auction style (it simply might not be zero).
   - I think it would be useful to add that theta* is independent of the auction style by the same bidder participation assumption, when we define theta*.
   - Also less relevant but I believe it might be useful to replace p with F^{n-1} in 21.4 as this might make it clearer the expression is really independent of the auction.
   - 21.3 First paragraph second row: n {mechanism!design - probably an uncommented latex reference
   - page 103 first line “other than” rather than “other that”
   - equation 21.5 rhs in the first term there is an extra right parenthesis
   - second paragraph page 103 “A mechanism is manipulable if the exist ” should be there instead of the
   - last equation in proof of theorem 22.2 there is an f missing (there should be an u(f(theta_i,theta_{-i}), theta_i)
   - paragraph with clark pivot rule on page 105 at two places there is v_j(f(theta)) instead of v_j(f(theta), theta_j), as v_j has two parameters.
   - Page 107 third paragraph 4th row, one to is extra “declare θi = u to so as to maximize”
   - Paragraph with participation fee: “then his expected payment is be”
5. 27/01/16. Thanks to Yoni Berger: * Lecture 12, page 57, section 12.4 - is the matrix C1 correct? Why is there a 1 in all diagonal entries? If they both pick phone b for example is it certain that they will not connect? * Lecture 4, page 20 section, 4.2 - last paragraph of the section before Gomory’s cutting method. Should three occurrences of ’n-m’ be replaced my ‘m’?  * What is Newton’s method referred to in Section 12? * Suggested typos: * Lecture 2, page 8, section 2.3 Word ‘appropriately’ written with no apparent context. * Lecture 12: page 54, section 12.1 - y printed instead of lambda for dual objective function * Lecture 17 Section 17.2 page 78 Definition of \bar v is slightly wrong. * Lecture 18 page 85: Before the words Otherwise stop it says 'goto step 1' - should be something like 'go to step 2.'  At the end of step k it says 'goto step k+1' with space missing. * Page 86: Section 18.4 'Suppose a subset of players, S, has an objection to payoff x because S would be have...' Delete the word 'be' 

Lecture 23

In the final lecture I spoke further about auction design, and then showed how the same ideas can be used to design a mechanism for a problem in which agents will share a facility (or a so-called club good). The mechanism receives declarations of agent types, $\theta_1,\dotsc,\theta_n$, and then chooses a size for the facility, $Q$, and extracts payments from the agents to cover its cost, $c(Q)$.

Agents with small $\theta_i$ will not find it worth joining the club and will not be made to make any payments. The analysis harkens back to earlier lectures, in that Lagrangian methods are employed, and a pivoting type algorithm is used to make adjustments to the payments. An agent will find it profitable to join the club iff $\theta_i+\lambda g(\theta_i)\geq 0$, where $\lambda$ is a Lagrange multiplier for the constraint that expected payments cover expected facility cost. The case $\lambda=\infty$ corresponds to maximizing the expected payments taken from the agents.

I gave a talk on this work at London School of Economics: Mechanism Design for a Service Provided in the Cloud. If you view this talk you will see how I managed to work into my talk the playing of the song ‘non, je ne regrette rien’ (‘no, I regret nothing’) (as sung by Edith Piaf).

Exam rubric

Lecturers have been asked to tell students what the rubric will be for the examination in June. For this course it will be:

Attempt no more than FOUR questions.

There are SIX questions in total.

The questions carry equal weight.