path: root/roughgarden.tex

\documentclass[12pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[hmargin=1.2in, vmargin=1.2in]{geometry}
\usepackage{amsfonts}

\title{Review of \emph{Complexity Theory, Game Theory and Economics} by Tim
Roughgarden}
%\author{Thibaut Horel}

\begin{document}

\vspace{-5em}

\maketitle


\section*{General impression} Very nice selection of topics, striking
a nice balance between covering classical results and recent papers. The level
of exposition feels right for a general theory audience. My feedback is fairly
local and mostly consists in suggestions for improving the exposition and typo
fixes.

\section*{Solar lecture 1}

\begin{itemize}
	\item Section 1.1: for organisational purposes, it might make sens to move
		the plan to the foreword, or a separated ``Introduction'' or
		``Preface'' chapter.

	\item Section 1.2.3: I suggest also introducing the concept of \emph{pure
		strategy} when defining a \emph{mixed strategy} below the payoff
		matrix. Once this term is defined, I think it should be used instead of
		\emph{deterministic strategy} in later sections (or even lectures?)

\item Proof of Theorem 1.1: I would add variables $v, x$ below the $\max$ in
	the first equation to make it clear what the maximization is over.
		Similarly, add $w, y$ below the $\min$ in the second equation.

\item Section 1.2.6: I think ``competitive'' is more standard than
	``oppositional'' in the contex of games. Similarly, ``collaborative''
		instead of ``cooperative'' in footnote 8. Furthermore, I think the
		content of this section should be moved to the beginning of Section 1.4
		to motivate the transition to bimatrix games. At the moment, it feels
		that it is breaking the flow.

\item Section 1.3.1: the first paragraph is slightly confusing, because it is
	said that players only know their own payoffs (and not those of the other
		player) but the focus of Section 1.3 at this point seems to be zero-sum
		games. I would clarify that the notion of uncoupled dynamics as it is
		defined here is for arbitrary bimatrix games.

\item Sections 1.3.1 and 1.3.2: the two framed boxes are slightly ill-defined
	for $t=1$ since there is no history then. I would maybe make $t=1$ an
		explicit ``initialization'' step and then say ``At time step $t\geq
		2$''.

\item Example 1.7: maybe add that $\eta=+\infty$ corresponds to fictitious play
	\emph{with uniformly random tie-breaking}.

\item Example 1.7: in the framed box, behavior at $t=1$ is ill-defined,
	initialize with uniformly random strategy?

\item Theorem 1.8: say in the theorem statement that this is for a choice of
	$\eta_t = \Theta(\sqrt{t})$.

\item Theorem 1.8: I am curious about the implication of this theorem for the
	computation of a Nash equilibrium: how does it compare to generic solvers
		for linear programs (e.g. the ellipsoid method)?

\item Theorem 1.10: say that $n=|\Lambda|$.

\item Section 1.3.7: the first sentence is unnecessary, the proof seems
	complete to me.

\item Example 1.13: If I am not mistaken, this game is commonly known as the
	``Battle of the sexes'' game. Even though the name is questionable, it
		might be worth mentioning so that people can recognize it in other
		contexts.
\end{itemize}

\paragraph{Typos.} \begin{itemize}
	\item footnote 4 p. 8: welfare $\rightarrow$ warfare
	\item definition 1.2: right-hind $\rightarrow$ right-hand
	\item first paragraph of 1.3.1: a la $\rightarrow$ à la
\end{itemize}

\section*{Solar lecture 2}

\begin{itemize}
	\item Section 2.3.2 Equation (2.2), I would simply write the first term as
		$x_1'^TAx_2$: this is easier to read and more consistent with the
		previous lecture.

	\item Lemma 2.5: I would significantly expand the proof of Sperner's lemma
		because at the moment it is really hard to even get an intuition of why
		it is true. After looking it up it seems that a complete proof can be
		given in a small amount of space: 1. first highlight that there has to
		be an odd number of bichromatic edges through which you enter the
		triangle (this is the dimension 1 case) 2. explain how you
		orient the edges and walk the graph 3. explain why you are guaranteed
		to end up at a sink node (sometimes you will exit the triangle instead
		of finding one, but this removes two bichromatic edges so you can
		iterate by induction).

	\item Section 2.5: this is a minor thing, but I found the roadmap hard to
		read and refer to later. I suggest maybe a bullet list with each item
		starting with ``Step $i$'' ($i\in[4]$) clearly identified in bold.
		Maybe using notations like $\epsilon$-BFP$\leq \epsilon$-NE although
		not fully accurate could help quickly follow the chain of reductions.
		Maybe a picture as well would help visualizing the chain of reductions?

	\item Section 2.6: I found the oracle model confusing: why is it useful to
		consider instances where the $pred$ and $succ$ functions might not be
		consistent with each other (i.e. where $succ(v) = w$ but $pred(w) \neq
		v$)? It seems that when this problem is used in the next lecture, it is
		only used for the promise version of the problem where $pred$ and
		$succ$ are guaranteed to be consistent. If it is not needed, then one
		could get rid of cases (iii) and (iv) in the framed box. If it is
		indeed needed, then I think some explanation of why would be nice.
		
		On the same point, the formulation is confusing because it says that
		(for example) $succ(v)$ is NULL if there is no successor, but later on
		in the same paragraph, we understand that it is allowed for
		$succ(v)=w$, even when $v$ has no successor as long as $pred(w)\neq v$.
		I think it is important to be very clear and distinguish between the
		``true'' successor (or absence thereof) according to the real graph $G$
		and the successor from the perspective of the $succ$ function which is
		allowed to be inconsistent with the graph.
\end{itemize}

\paragraph{Typos.} \begin{itemize}
	\item last paragraph of Section 2.1: Theorem 1.8 $\rightarrow$ Theorem 2.1
	\item Theorem 2.2: space missing before $\mathbb{R}^d$
\end{itemize}

\section*{Solar lecture 3}

\begin{itemize}
	\item Section 3.1.2 and Section 3.1.4. An intuition which was useful for me
		when trying to understand these sections and is already implicitly
		there but might be worth making more explicit:
		\begin{itemize}
			\item $G$ is used to define a ``gradient field'' $g$ on the entire
				hypercube by extrapolation. The extrapolation is designed such
				that the sink nodes of $G$ and source nodes (different from
				$0^n$) correspond to stationary points of the gradient field.
			\item the function $f$ is defined such that finding a fixed point
				of $f$ is equivalent to finding a stationary point of the
				gradient field (this might be a very personal bias but I always
				think of $f$ as expressing a ``gradient ascent'' update:
				$x_{k+1} = x_k + g(x_k)$, for which fixed points correspond to
				stationary points).
			\item by factoring out the parameter $\delta$ out of the definition
				of $g$ and defining $f(x) = x + \delta \cdot g(x)$ we can now
				interpret $\delta$ as the ``step size'' of gradient ascent (in
				any case, factoring $\delta$ out would make things a bit easier
				to read).
			\item it also follows from this gradient ascent perspective: that
				one can indeed solve the EOL problem by ``following'' the
				gradient field. The reduction basically shows that one cannot
				beat gradient ascent to find stationary points\footnote{This
				also made me wonder whether lower bounds on the query
				complexity of finding stationary points and the fact that
				gradient descent is optimal under reasonable assumptions could
				have somehow been leveraged somewhere in these reductions}.
		\end{itemize}
	
	\item Section 3.1.3: I know it is out of scope of this section to give all
		the details, but I wish a little bit more could have been said about
		the ``soft'' classification of points to one of the three categories:
		how is the ``intermediate regime'' defined and why is it useful? Given
		that it is referred in Section 3.1.4, I feel knowing a little bit more
		would help.

	\item Section 3.1.4: I think reordering the cases and using a bit more math
		instead of plain English could make the description of $g$ easier to
		read:
		\begin{itemize}
			\item for directed edge $e = (u, v)\in G$ define $\overrightarrow{e}
				= \frac{\sigma(v)-\sigma(u)}{\|\sigma(v)-\sigma(u)\|}$ also
				denote by $\overrightarrow{d}$ a default direction.
			\item if $x$ is close to $\sigma(e)$ with $e\in G$, then
				$g(x)=\overrightarrow{e}$
			\item if $x$ is close to $v$ with incoming edge $(u,v)$ and
				outgoing edge $(v, w)$, $g(x)$ interpolates between
				$\overrightarrow{uv}$ and $\overrightarrow{vw}$.
			\item if $x$ is close to a source or sink node $v$ with adjacent
				edge $e$, $g(x)$ interpolates between $0^n$ and
				$\overrightarrow{e}$.
			\item in all other cases $g(x)=\overrightarrow{d}$.
		\end{itemize}
	
	\item Section 3.2.2: small typo $H_\epsilon$ is a set of $(1/\epsilon)^d$
		points (and not $(1/\epsilon)^n$).
\end{itemize}

\paragraph{Typos.}\begin{itemize}
	\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}