\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}
\newenvironment{Q}
{%
\clearpage
\item
}
{%
\phantom{s}
\bigskip
\textbf{Solution.}
}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 598RM: Algorithmic Game Theory, Fall 2019}
\\[0.5ex]
\textbf{HW 1 (due on Wednesday, 25th Sept at 11:59pm CST)}
\end{center}
\noindent{\bf Instructions:}
\begin{enumerate}
\item We will grade this assignment out of a total of 60 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
\noindent\makebox[\linewidth]{\rule{\textwidth}{0.4pt}}
\begin{enumerate}
%----------------------------------------------------------------------
\begin{Q}
\begin{enumerate}
\item (3 points) The following game has a unique Nash equilibrium. Find
it, and prove that it is unique. {\em (Hint: look for strict dominance.)}
\begin{center}
\begin{tabular}{| c | c | c |}
\hline
4, 0 & 1, 2 & 4, 0 \\ \hline
2, 4 & 2, 4 & 3, 5 \\ \hline
0, 1 & 4, 0 & 4, 0 \\
\hline
\end{tabular}
\end{center}
\item (4 points). Construct a single $2 \times 2$ normal-form game that simultaneously
has all four of the following properties:
\begin{enumerate}
\item The game has a dominant strategy Nash equilibrium (at least one player does not have a dominant strategy).
\item The game is solvable by iterated weak dominance (so that one pure strategy per player remains).
\item In addition to the iterated weak dominance solution (which is a Nash
equilibrium), there is a second pure-strategy Nash equilibrium.
\item Both players strictly prefer the second equilibrium to the first.
{\em (Hints: the second pure-strategy equilibrium should not be strict; the pure strategy equilibria should be in opposite corners of the matrix.)}
\end{enumerate}
If you cannot get all four properties, construct an example with as many of the properties as you can.
\item (3 points). Consider the following game:
\begin{center}
\begin{tabular}{| c | c |}
\hline
5, 5 & 1, 7 \\ \hline
7, 1 & 0, 0 \\
\hline
\end{tabular}
\end{center}
Find a correlated equilibrium that places positive probability on all entries of the matrix, except the lower-right hand entry. Try to maximize the probability in the upper-left hand entry.
\end{enumerate}
\end{Q}
\begin{Q}
Consider a symmetric $2$ person game between Alice and Bob, with the same strategy set $S$ for both players. Let $A(i, j)$ and $B(i,j)$ denote the payoff of Alice and Bob respectively, when Alice plays $i$ and Bob plays $j$. We say that the game is symmetric if we have that $A(i,j) = B(j,i)$ for all $i,j \in S$, {\em i.e.,} $B=A^T$.
\begin{enumerate}
\item (2 points) Can a symmetric game have a pure Nash equilibria? (even if all values $A(i,j)$ are different?)
\item (2 points) Do all symmetric games have pure Nash equilibria?
\item (6 points) Show that a symmetric game always have a symmetric equilibrium, i.e., a probability distribution $x\in \Delta(S)$ such that $(x,x)$ is an Nash equilibrium. {\em (Hint: mimic Nash's proof we did in the class).}
\end{enumerate}
\end{Q}
\begin{Q}
$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 remaining points can receive any color.
\begin{enumerate}
\item (4 points) 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''.
\item (6 points) Show that checking if there are more than one such $k$s is NP-complete. {\em (Hint: reduce from 3-SAT).}
\end{enumerate}
\end{Q}
\begin{Q}
There is a weaker notion than correlated equilibrium called {\em 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 a CCE of game $(A,B)$ if no player wants to opt out when everyone else is opting in.
\begin{enumerate}
\item (4 points) Show that every correlated equilibrium is a coarse-correlated equilibrium.
\item (6 points) Show that the set of all coarse-correlated equilibria of the game $(A,B)$ is convex.
\end{enumerate}
\end{Q}
\begin{Q}
Initially there is one firm in a market for phones. The firm has a linear cost function: $C(Q) = 3 Q$. The market inverse demand function is known, and accordingly the market price for quantity $Q$ is $P(Q) = 15 - Q$.
\begin{enumerate}
\item (3 points) What price will the firm charge? What quantity of phones will the firm sell?
\item (2 points) How much profit will the firm make?
\item (5 points) Now suppose a second firm enters the market and has the same cost function. What is the Stackelberg equilibrium output for each firm in terms of quantity produced and profit made?
\end{enumerate}
\end{Q}
\begin{Q}
Consider the game below:
\begin{figure}[!ht]
\centering
\includegraphics[width=0.5\textwidth]{figure.png}
\caption{An extensive-form game with imperfect information.}
\end{figure}
\begin{enumerate}
\item (3 points). Give the normal-form representation of this game.
\item (3 points). Give a Nash equilibrium where player $1$ sometimes plays left. {\em (Remember that you must specify each playerâ€™s strategy at {\bf every} information set).}
\item (4 points). Characterize the subgame perfect equilibria of the game. {\em (Remember that you must specify each playerâ€™s strategy at {\bf every} information set).}
\end{enumerate}
\end{Q}
\end{enumerate}
\end{document}