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