\documentclass[11pt]{article}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 598RM: Algorithmic Game Theory, Fall 2018}
\\[0.5ex]
\textbf{HW 1 (due on Monday, Thu 20th Sept at 3:30pm CST)}
\end{center}
\noindent{\bf Instructions:}
\begin{enumerate}
\item We will grade this assignment out of a total of 30 points.
\item Feel free to discuss with fellow students, but write your own answers. If you do discuss a problem with someone then write their
names at the starting of the answer for that problem.
\item Please type your solutions if possible in Latex or doc whatever is suitable. We will upload submission instructions on the course webpage and Piazza.
\item Even if you are not able to solve a problem completely, do submit whatever you have. Partial proofs, high-level ideas, examples,
and so on.
\item Except where otherwise noted, you may refer to lecture slides/notes, and to the references provided.
You cannot refer to textbooks, handouts, or research papers that have not been listed. If you do use any approved sources, make
sure you cite them appropriately, and make sure to write in your own words.
\item No late assignments will be accepted.
\item By AGT book we mean the following book: Algorithmic Game Theory (edited) by Nisan, Roughgarden, Tardos and Vazirani.
Its free online version is available at Prof. Vijay V. Vazirani's webpage.
\end{enumerate}
\medskip
\medskip
\hline
\begin{enumerate}
%----------------------------------------------------------------------
\item (5 points) Consider a two player game where the set of strategies of the first and second players are $S_1$ and $S_2$ respectively. Let $m=|S_1|$ and $n=|S_2|$, then such a game can be represented by two $m\times n$ payoff matrices $(A,B)$. In addition, suppose, $A(i,j), B(i,j)>0,\ \forall i\in S_1, \forall j \in S_2$. Consider the symmetric game $(C,C^T)$ with the following $(m+n)\times(m+n)$-dimensional block-matrix:
\[
\left[
\begin{array}{cc}
0 & A \\
B^T & 0
\end{array}
\right]
\]
Show that a symmetric Nash equilibrium of game $(C,C^T)$ gives a Nash equilibrium of game $(A,B)$.
\item (5 points) Given a two-player game $(A,B)$ of Problem 1, design an algorithm to find a Nash equilibrium of the game. Your algorithm should terminate in finite time.
\medskip
\noindent{\bf Extra credit.} Given that the game has finitely many Nash equilibria, design a finite time algorithm to enumerate all of it's Nash equilibria.
\item (5 points) Show that if a mixed-strategy profile $(x,y)$ is a Nash equilibrium of game $(A,B)$, then matrix $P$ where $p_{ij}=x_i*y_j$ is a correlated equilibrium (CE) of the game.
\item (10 points) 1-dimensional Sperner's is defined on a 1-dimensional grid from $[0, 2^n-1]$, with each integer being a grid
point. There are two colors red and blue represented by $0$ and $1$ respectively.
There is a Boolean circuit named {\em Color} which outputs color (0/1 bit) of a grid point given its bit representation, such that,
Color($0$)=red, Color($2^n-1$)=blue, and the rest gets any color. Show that there exists
an integer $0\le k \le 2^n-1$ such that Color($k$)=red and Color($k+1$)=blue. Furthermore, we can compute it in $O(n)$
calls to the Boolean circuit ``Color''. Finally, show that checking if there are more than one such $k$s is NP-hard (hint: reduce from
3-SAT).
\item (5 points) Problem 1.2 of the AGT book.
\medskip
\noindent{\bf Note.} Since finding a Nash equilibrium is PPAD-hard in the worst-case, the next immediate question is to do {\em beyond worst-case} analysis. Average case, where the game is sampled uniformly at random, is one such regime. This question sheds light on average-case complexity of Nash equilibrium computation.
\end{enumerate}
\vspace{1in}
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item Problem 1.3 of the AGT book.
\item Show that checking if a two-player game has more than one Nash equilibrium is NP-hard (hint: reduce from
the problem of checking if a graph has clique of size $k$.)
\item (Open problem) Rank of a two-player game $(A,B)$ as $rank(A+B)$. Adsul et al (STOC'11) showed that computing Nash
equilibrium of a rank-1 game can be done in polynomial time by reducing the problem to 1-dimensional fixed-point. On the other hand
games with rank 2 and more are PPAD-hard.
Show that checking if a rank-1 game has more than one Nash equilibrium is NP-hard. NP-hardness for even constant rank would be good.
\item Problem 1.5 of the AGT book.
\item There is a weaker notion than CE called coarse-correlated equilibrium (CCE). Here the mediator announces the joint distribution matrix $P$, and asks each player to opt in or out before it starts suggesting them. If the player chooses to opt out then it can play whatever it wants, on the other hand if it chooses to opt in then it has to play what the mediator suggests. In other words, a player can not get the suggestions and then not play what is suggested. Matrix $P$ is called CCE of game $(A,B)$ if no player wants to opt out if everyone else is opting in.
\begin{itemize}
\item[$(a)$] Show that every correlated equilibrium is a coarse-correlated equilibrium.
\item[$(b)$] Show that all the coarse-correlated equilibria of game $(A,B)$ can be captured by a linear feasibility problem formulation.
\end{itemize}
\end{itemize}
\end{document}