\documentclass{amsart}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[T1]{fontenc} % Output font encoding for international characters
\usepackage{fouriernc} % Use the New Century Schoolbook font
\usepackage{hyperref}
\hypersetup{
colorlinks=true,
linkcolor=blue,
citecolor=blue
}
\usepackage{sgame}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{bb}[theorem]{Blackboard}
\newcommand{\vecl}[1]{\overrightarrow{#1}}
\newcommand{\dls}[1]{\overrightarrow{#1}}
\def\vproj{\mbox{proj}}
\def\half{{\textstyle \frac12}}
\def\third{{\textstyle \frac13}}
\def\C{\mathbb{C}}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\pleq{\preceq}
\def\pgt{\succ}
\def\Z{\mathbb{Z}}
\newenvironment{myenumerate}
{\begin{enumerate}
\setlength{\itemsep}{10pt}}
% \setlength{\parskip}{0pt}
{\end{enumerate}}
\newcommand\blfootnote[1]{%
\begingroup
\renewcommand\thefootnote{}\footnote{#1}%
\addtocounter{footnote}{-1}%
\endgroup
}
\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\vspace{0.15in}{\bf Solution: {#1}}\vspace{0.15in}}
\begin{document}
%\newcommand{\itemt}[2]{\item {\bf {#1}} \newline{#2}}
\blfootnote{Omer Tamuz. Email: tamuz@caltech.edu.}
\section*{PS/Ec 172, Set 2\\Due Friday, April 21\textsuperscript{st} at
11:59pm \\ Resubmission due Friday, May 11\textsuperscript{th} at
11:59pm}
Collaboration on homework is encouraged, but individually written
solutions are required. Also, please name all collaborators and
sources of information on each assignment; any such named source may
be used.
\mbox{}
\begin{myenumerate}
\item {\em Equilibria in strategic form games.} Find all the
equilibria in the following games, which are described in the
lecture notes.
\begin{myenumerate}
\item {\em 10 points.} Voter turnout when $N^a$ and $N^b$ are the
same size.
\item {\em 10 points.} Voter turnout when $N^a$ is larger than $N^b$.
\end{myenumerate}
\item {\em Cournot competition.} The Cournot competition game is
described in the lecture notes.
\begin{myenumerate}
\item {\em 10 points}. An equilibrium is said to be
\emph{symmetric} if all players choose the same strategy. Find a
symmetric pure Nash equilibrium of the Cournot competition game,
as described in Exercise 3.9 of the lecture notes.
\item {\em 10 points}. Imagine that an organized crime boss is
brought in to enforce a cartel policy that maximizes the total
utility of the companies. By how much does their total utility
increase?
\end{myenumerate}
\item {\em Elimination of weakly dominated strategies.} In this
problem we will show that eliminating weakly dominated strategies
can change the set of pure Nash equilibria. This is in contrast to
what happens when eliminating strictly dominated strategies, which
does not change the set of pure equilibria (see the lecture
notes).
In the following game the additional strategy $A$ was added to
matching pennies.
\begin{center}
\begin{game}{3}{3}
& $H$ & $T$ & $A$ \\
$H$ & $1,0$ & $0,1$ & $2,0$ \\
$T$ & $0,1$ & $1,0$ & $1,0$ \\
$A$ & $1/2,0$ & $0,1$ & $2,2$
\end{game}
\end{center}
\begin{myenumerate}
\item {\em 10 points}. Show that this game has a pure Nash equilibrium.
\item {\em 10 points}. What are the weakly dominated strategies?
\item {\em 10 points}. Iteratively remove the weakly dominated
strategies. What is the resulting game? What are its pure Nash
equilibria?
\end{myenumerate}
\item {\em Mixed Nash equilibria}. In the {\em auditing game} a
taxpayer has to decide whether to cheat, and the IRS has to decide
whether to audit. The benefit to the taxpayer from cheating is some $b >
0$. The cost of auditing is $c > 0$. The fine for cheaters is $f >
0$. Thus the game is described by
\begin{center}
\begin{game}{2}{2}
& audit & not audit \\
cheat & $-f,f-c$ & $b,0$ \\
not cheat & $0,-c$ & $0,0$
\end{game}
\end{center}
\begin{myenumerate}
\item {\em 10 points}. For every possible value of $b$, $c$ and $f$,
find all the mixed Nash equilibria.
\item {\em 10 points}. In what direction does the equilibrium
probability of an audit change as a function of $b$, $c$ and $f$?
How about the probability of cheating?
\item {\em 10 points}. In what direction do the players' equilibrium
expected utilities change as a function of $b$, $c$ and $f$?
\end{myenumerate}
\item {\em Bonus question.} A prisoner escapes to the number line. He
chooses some $n \in \Z$ to hide on the zeroth day. He also chooses
some $k \in \Z$, and every day hides at a number that is $k$ higher
than in the previous day. Hence on day $t \in \{0,1,2,\ldots\}$ he
hides at $n + k\cdot t$.
Every day the detective can check one number and see if the prisoner
is there. If he is there, she wins. Otherwise she can check again
the next day.
Formally, the game played between the prisoner and the detective is
the following. The prisoner's strategy space is
$\{(n,k) \,:\,n,k \in \Z\}$, and the detective's strategy space is
the set of sequences $(a_0,a_1,a_2,\ldots)$ in $\Z$. The detective wins
if $a_t = n + k \cdot t$ for some $t$. The prisoner wins otherwise.
\begin{myenumerate}
\item {\em 1 point.} Prove that the detective has a winning
strategy.
\end{myenumerate}
\end{myenumerate}
\end{document}