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."
- 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.
- 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.
- 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. - 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” - 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'
