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

\title{Review of \emph{Complexity Theory, Game Theory and Economics} (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.

\section*{Solar lecture 1}

\begin{itemize}

	\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: check oppositional/cooperative. 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.2.7: add quote by Jain.

\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: Is this the ``battle of the sexes'' game?

\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}

\paragraph{Typos.} \begin{itemize}
\end{itemize}

\end{document}