Finish review of Roughgarden

1 files changed, 169 insertions, 0 deletions

diff --git a/roughgarden.tex b/roughgarden.tex
index 422ea35..9d3520a 100644
--- a/roughgarden.tex
+++ b/roughgarden.tex
@@ -199,4 +199,173 @@ fixes.
 	\item Section 3.1.3 footnote 3: details,, $\rightarrow$ details,
 \end{itemize}
 
+\section*{Solar lecture 4}
+
+\begin{itemize}
+	\item Figure 4.2: PPP is absent form this figure and I was wondering what
+		is known about its relationship with other classes.
+
+	\item Section 4.3.2, last sentence: ``These convergence proofs\dots''. This
+		sentence felt redundant and, I think, can be removed.
+
+	\item Section 4.3.3: the discussion below Theorem 4.3 would be better
+		postponed and merged with the discussion below Theorem 5.2 (next
+		lecture). At the moment, these two discussions (about the same result)
+		are quite redundant with each other.
+
+	\item Section 4.4, title: maybe replace ``Hardness'' with ``Hardness of
+		TFNP''?
+
+	\item Section 4.4.2: I found the second paragraph a little confusing.  The
+		standard problem for one-way functions (the way their security is defined
+		in cryptography) is the one of inverting the image of a random input.
+		In other words, the adversary is given $y=f(x)$ for a random input $x$
+		and has to find a preimage of $y$. This problem is total by definition.
+		
+		It is thus surprising to me to consider a non-standard problem
+		involving the one-way function, and then state that it is not total,
+		when the standard problem is. I understand that when one only has
+		a distribution $D_n$ (with no guarantee that $D_n$ is supported on $L$)
+		there is not much else that can be done than the parallel repetition
+		technique of Attempt 1 or 2, but then maybe the remark about one-way
+		functions should be moved above the introduction of $D_n$, or
+		contrasted better with it? The main difference is that $D_n$ is not
+		guaranteed to only output instances in $L$ whereas the standard one-way
+		function task only involves instances in the range of $f$ (and hence is
+		total for the relation $\{(f(x), x)\}$).
+
+	\item Claim 4.6: it seems that the proof shows a stronger statement:
+		``with high probability'' is in fact ``with overwhelming probability''
+		(in this case, it is even ``unless with exponentially small
+		probability'').
+\end{itemize}
+
+\section*{Solar lecture 5}
+
+I found this lecture extremely clear and well-written and have little to say
+about it except:
+\begin{itemize}
+	\item as already mentioned, the discussion below Theorem 4.3 in the
+		previous lecture could be merged with the discussion below Theorem 5.2.
+		The remark about local decodability was very illuminating and should be
+		kept in the merge process.
+\end{itemize}
+
+\paragraph{Typos.}
+
+\begin{itemize}
+	\item Section 5.2.2, last words: the forward pointer should be to Section
+		5.2.9, not Section 5.2.8
+\end{itemize}
+
+\section*{Lunar lecture 1}
+
+\begin{itemize}
+	\item As a general comment, I was wondering whether it would help to add
+		a  section at the beginning of this lecture to formally introduce and
+		define auction mechanism design: explain that the goal is to design the
+		``rules of the game'', introduce the notions of bidders, their
+		valuations, the fact that a mechanism is typically the pair of
+		a  selection rule and a pricing rule. Then maybe formally present
+		(single item) first and second price auctions and discuss their
+		properties.
+	\item if the previous item is implemented, the presentation of (single
+		item) second-price auctions in Section 1.3.1 and first-price auctions
+		in Section 1.3.4 could be removed since they will then be redundant. At
+		the moment, they are presented in an extremely terse way in the middle
+		of a more general point and make the flow hard to follow. It seems
+		possibly worthwhile to pay a small cost upfront to present them in this
+		extra initial section.
+
+	\item possibly, the extra initial section could also contain a formal
+		definition of the combinatorial auction setting. Again, the current
+		presentation at the beginning of Section 1.3.4 feels very terse---at
+		the very least I would put it in a separate definition environment and
+		maybe use a bulleted list.  I found the presentation of the model at
+		the beginning of the next lecture (Section 2.1) easier to read and
+		maybe the two should be merged; presently the same model is defined
+twice a couple of pages apart.
+
+	\item In section 1.3.4 when talking about price of anarchy, give a forward
+		pointer to section 2.3.2 (next lecture)
+\end{itemize}
+
+\paragraph{Typos.}
+
+\begin{itemize}
+	\item Section 1.2.1, footnote 2: there is seemingly a missing word,
+		maybe ``[\dots] Auction \emph{ended} up clearing''
+	\item Section 1.3.3, footnote 10: $v$ has not been defined yet at this
+		point, say that it is the bidder's valuation for a set of items
+	\item Section 1.3.3, footnote 10: $v(AB)\rightarrow v(A, B)$ having a comma
+		between the two items would be clearer
+	\item Section 1.3.3, footnote 11: same problem as footnote 10
+\end{itemize}
+
+\section*{Lunar lecture 2}
+
+\begin{itemize}
+	\item In Section 2.2.3, maybe put the proof of Lemma 2.3 below the actual
+		statement, and inside a proof environment?
+	\item (very minor) I found the sentence ``As a thought experiment'' a quite
+		unusual (and also probably unnecessary for a theory audience) way to
+		present the probabilistic method in the proof of Lemma 2.3.
+	\item Footnote 6 in section 2.3.1 is a bit redundant since second-price
+		auctions were already discussed in Lunar Lecture 1 (and even more so if
+		the suggestion of having a separate section on single item auctions at
+		the beginning of Lunar lecture 1 is implemented).
+\end{itemize}
+
+\paragraph{Typos.}
+
+\begin{itemize}
+	\item Section 2.1 below equation (2.1): ``using communication polynomial in
+		$n$ and $m$''. I think $n$ should be replaced by $k$.
+	\item Section 2.3.4, statement of Theorem 2.7: ``Let $\epsilon$ be
+		[\dots] of $n$ and $m$''. I think $n$ should be replaced by $k$.
+\end{itemize}
+
+\section*{Lunar lecture 3}
+
+I found this lecture exceptionally clear and well written (and also
+interesting!) and did not find anything to say about it.
+
+\paragraph{Typo.} Section 3.1.3, Example 3.4: in the definition of $v_2$,
+``when $T$ is $\{A\}$ or $\{B\}$'' ($T$ is a set so it should be
+singletons).
+
+\section*{Lunar lecture 4}
+
+\begin{itemize}
+	\item Section 4.1.2: when presenting Myerson's optimal auction, maybe
+		explain what a \emph{reserve price} is?
+	\item Section 4.2.3, footnote 9: if I am not mistaken the standard term is
+		just \emph{interim} (without \emph{ex})
+	\item Definition 4.1, second equation: is there a reason to write the
+		expectation on the right-hand side as a sum over $v_{-i}$ and not just
+		as an expectation as in the first equation of Section 4.2.3? I found it
+		harder to read in this form and it doesn't seem to be used later.
+	\item Definition 4.6: I would expand a little bit what it means to
+		``efficiently recognize'' a linear equality: the algorithm receives as
+		input a list of coefficients (written in such a way that we know which
+		variable they are ``attached'' to).
+\end{itemize}
+
+\section*{Lunar lecture 5}
+
+\begin{itemize}
+	\item Section 5.2, first framed box (\emph{Uncoupled Dynamics}): in step 2,
+		I think ``observes'' would be better than ``learns'' (which is
+		confusing in this context since the players are actually performing
+		some learning over time).
+	\item Section 5.2 second framed box: same comment as in the previous point.
+	\item (minor) Proposition 5.3: it seems that it would be more illuminating
+		to change the order or presentation here.  State the proposition as
+		saying that $\epsilon$ regret is equivalent to being an $\epsilon$
+		coarse correlated equilibrium (in the average sense) and provide the
+		two-line proof, whose advantage would mostly be to remind the reader of
+		the definition of regret. Then, as a corollary or discussion below the
+		proposition, remind that smooth fictitious play has vanishing regret.
+\end{itemize}
+
 \end{document}