% -*- mode:LaTeX; mode:flyspell; mode:hl-line; -*-
\documentclass{article}

% Almost always
\usepackage{enumerate}
\usepackage{booktabs}
\usepackage{amsmath, amsthm}
\usepackage{graphicx}
\usepackage[verbose,letterpaper,top=1.25in,bottom=1in,left=1.25in,right=1.25in]{geometry}
\usepackage{sgamevar}

% separate paragraphs by blank lines, not indentation
\setlength{\parindent}{0pt}
\setlength{\parskip}{\baselineskip}

% Special letters
\usepackage{dsfont}
\newcommand{\N}{\ensuremath{\mathds{N}}}
\providecommand{\R}{\ensuremath{\mathds{R}}}\renewcommand{\R}{\ensuremath{\mathds{R}}}

% handy shortcuts
\newcommand{\pref}{\succ}
\newcommand{\lesspref}{\prec}
\newcommand{\prefeq}{\succeq}
\newcommand{\lessprefeq}{\preceq}


% extra stuff for assignments
\newcounter{totalpoints}
\setcounter{totalpoints}{0}

\newcommand{\points}[1]{{\addtocounter{totalpoints}{#1}\textbf{[#1 points]}}}
\usepackage{environ}
\usepackage{etoolbox}
\makeatletter
\NewEnviron{answer}[1]
{\ifx\BODY\@empty
 \vspace{#1}%
\else
 {\sf \BODY}%
\fi}
\makeatother

\usepackage{totcount}
\regtotcounter{totalpoints}
\begin{document}

\pagestyle{myheadings}
\markboth{}{CMPUT 654 --- Assignment \#1}

{\bigskip\hrule\bigskip
\huge
\noindent CMPUT 654, Fall 2019\\
Assignment \#1

\large
Due: Tuesday, Oct.\ 1, 2019, 1:59pm\\
Total points: \total{totalpoints}

\normalsize
Name:\\
Student number:\\
Collaborators and resources:

\bigskip\hrule\bigskip
}


\begin{enumerate}
    
%------------------------------------------------------------------------------------------
\item \textbf{(Utility Theory)}

\begin{enumerate}
    \item \points{20}
    Prove that it is not always possible to represent preferences by maximization of expected utility if the preferences do not satisfy von Neumann and Morgenstern's \textit{Decomposability} condition.  Hint: construct a preference order that satisfies all of the other conditions, but does not satisfy \textit{Decomposability}, and show that this cannot be represented by expected utility maximization.

    \begin{answer}{2.5in}
    % Put your answer here
    \end{answer}

    \item \points{5} \label{q:st-petersburg}
    Consider the following game: A fair coin is tossed.  If it comes up heads, you win \$2.  Otherwise, the coin is flipped again.  If it comes up heads on the second flip, you win \$4.  Otherwise, the coin is flipped again, and so on.
    That is, the coin is flipped until the first heads appears on the $k$th flip; and then you are paid $2^k$ dollars.

    Prove that the expected monetary value of this game is infinite.

    \begin{answer}{1in}
    % Put your answer here
    \end{answer}


    \clearpage
    \item \points{15}
    Suppose that a perfectly rational expected utility maximizer is given the opportunity to play the game from question~(\ref{q:st-petersburg}).
    Suppose further that the agent has strictly monotonic value for money: \$$(x + 1) \pref \$x$ for all values of $x$.
    Is there any value of $y$ such that this agent can rationally turn down the opportunity to play the game in exchange for \$$y$?  (In other words, do there exist and $y \in \R$ and rational preferences $\prefeq$ for which $\$y \pref \text{(game from question~\ref{q:st-petersburg})}$).

    Either construct a preference order $\prefeq$ that satisfies all of the von Neumann-Morgenstern axioms, strictly monotonic value for money, and $\$y \pref \text{(game from question~\ref{q:st-petersburg})}$, or prove that no such preference order exists.

    \begin{answer}{1.5in}
    % Put your answer here
    \end{answer}

\end{enumerate}
    
\clearpage
%------------------------------------------------------------------------------------------
\item \textbf{(Normal Form Games)} \label{q:nfg}

Consider the following game:

\begin{center}
    \begin{game}{5}{4}[$G$]
        \> $L$    \> $M$   \> $R$  \> $Q$\\
        $W$ \> $3,0$ \> $-9,4$ \> $-1,1$ \> $4, 0$ \\
        $X$ \> $9, 1$  \> $2,-1$ \> $3,1$ \> $5, 3$ \\
        $Y$ \> $-2, 7$  \> $1,0$ \> $2,3$ \> $3,7$ \\
        $Z$ \> $-4, 4$ \> $12, 5$ \> $4,6$ \> $2, 4$
    \end{game}
\end{center}
% Q X and R Z

\begin{enumerate}
    \item \points{2} List the Pareto optimal outcomes in game~$G$.

    \begin{answer}{2\baselineskip}
    % Put your answer here
    \end{answer}


    \item \points{3} List the weakly dominated pure strategies in game~$G$.

    \begin{answer}{2\baselineskip}
    % Put your answer here
    \end{answer}

    \item \points{2} List the strictly dominated pure strategies in game~$G$.

    \begin{answer}{2\baselineskip}
            % Put your answer here
            \end{answer}

    \item \points{3} Which pure strategies survive iterated removal of strictly dominated strategies in game~$G$?  Justify your response.

    \begin{answer}{.75in}
    % Put your answer here
    \end{answer}

    \item \points{10}
    For each rationalizable pure strategy of $G$, provide a rationalizable belief to which the strategy is a best response.
    For each unrationalizable pure strategy of $G$, explain why the strategy is not rationalizable.

    \begin{answer}{1.5in}
    % Put your answer here
    \end{answer}

    \item \points{10} Compute and list all of the Nash equilibria in game~$G$. Justify your responses.

    \begin{answer}{.75in}
    % Put your answer here
    \end{answer}


\end{enumerate}
    
\clearpage
%------------------------------------------------------------------------------------------
\item \textbf{(More Normal Form Games)}
\begin{enumerate}

    \item \points{5}
    Construct a normal-form game in which an agent plays a strictly dominated action in some Nash equilibrium and provide the equilibrium, or prove that this is impossible.

    \begin{answer}{.75in}
            % Put your answer here
            \end{answer}


    \item \points{5} \label{q:weak-dom-ne}
    Construct a normal-form game in which an agent plays a weakly dominated action in some Nash equilibrium and provide the equilibrium, or prove that this is impossible.

    \begin{answer}{.75in}
    % Put your answer here
    \end{answer}

    \item \points{5}
    Construct a normal-form game in which an agent plays a very weakly dominated action in some Nash equilibrium and provide the equilibrium, or prove that this is impossible.

    \begin{answer}{.75in}
    % Put your answer here
    \end{answer}


    \item \points{10}
    Consider the following pair of utility functions for money outcomes:
    \begin{align*}
    u_1(\$0) &= 0   & u_2(\$0) &= 0  \\
    u_1(\$1) &= 1   & u_2(\$1) &= 1  \\
    u_1(\$3) &= 3   & u_2(\$3) &= 1.75  \\
    u_1(\$6) &= 6   & u_2(\$6) &= 3
    \end{align*}
    Let $\ell = [.5:\$6, .5:\$0]$ be a lottery that pays out \$6 and \$0 with equal probability.

    Consider the following game: Players 1 and 2 have the utilities specified above and identical net worths of \$0.
    They simultaneously choose between actions $X$ and $Y$.
    If both players choose $X$, then player 1 receives the outcome of lottery $\ell$ and player 2 receives \$6.
    If both players choose $Y$, then player 1 receives \$1 and player 2 receives the outcome of lottery $\ell$.
    If one player chooses $X$ and the other chooses $Y$, then the player who chose $X$ receives \$0 and the player who chose $Y$ receives \$1.

    Represent this situation as a \textbf{normal form game} and list all of its Nash equilibria.

    \begin{answer}{1.5in}
    % Put your answer here
    \end{answer}


\end{enumerate}
    
\clearpage
%------------------------------------------------------------------------------------------
\item \textbf{(Maxmin and Minmax)}

\begin{enumerate}
    \item \points{5} What is the row player's maxmin value in game~$G$ from question~\ref{q:nfg}?  Justify your response.

    \begin{answer}{1in}
    % Put your answer here
    \end{answer}

    \item \points{5} What is the column player's minmax value in game~$G$ from question~\ref{q:nfg}? Justify your response.

    \begin{answer}{1in}
    % Put your answer here
    \end{answer}


    \item \points{5} Prove that a player's maxmin value is less than or equal to their minmax value in all~games.

    \begin{answer}{1in}
    % Put your answer here
    \end{answer}


    \item \points{5} Prove that a player's maxmin value is equal to their minmax value in all~two-player~games.

    \begin{answer}{1in}
    % Put your answer here
    \end{answer}

\end{enumerate}

\clearpage
%------------------------------------------------------------------------------------------
\item \textbf{(Correlated Equilibrium)}

\begin{enumerate}
    \item \points{10}
    Consider the following game:
    \begin{center}
        \begin{game}{4}{3}[$G_1$]
            \>  $L$      \>  $C$    \>  $R$      \\
            $T$  \> $2, -2$  \> $7, -7$   \> $-11, 11$ \\
            $M$  \> $8,-8$     \> $10, -10$   \> $15, -15$    \\
            $B$  \> $-10, 10$ \> $-3, 3$ \> $-1, 1$
        \end{game}
    \end{center}

    Construct a correlated equilibrium for game $G_1$ in which the column player receives an expected utility of $4$, or prove that no such correlated equilibrium exists.

    \begin{answer}{1.75in}
    % Put your answer here
    \end{answer}        


    \item \points{10}
    Consider the following game:
    \begin{center}
        \begin{game}{5}{4}[$G_2$]
            \>  $L$      \>  $C$  \>  $D$    \> $R$  \\
            $T$  \> $20, 4$  \> $16,8$ \> $12, 5$ \> $3, 3$  \\
            $M$  \> $14, 13$  \> $0,0$  \> $-2, -2$ \> $5, 12$  \\
            $B$  \> $13, 13$   \> $7, 7$ \> $0, 0$ \> $8, 16$ \\
            $E$  \> $5, 5 $ \> $13, 13$ \> $13, 14$ \> $4, 20$ 
        \end{game}
    \end{center}


    Construct a correlated equilibrium for game $G_2$ in which the row player receives an expected utility of $14$ and the column player receives an expected utility of $10$, or prove that no such correlated equilibrium exists.

    \begin{answer}{1.75in}
    % Put your answer here
    \end{answer}


    \item \points{10}
    Construct a correlated equilibrium for game $G_2$ in which both players play only two actions with positive probability and receive an expected utility of $13.5$, or prove that no such correlated equilibrium exists.

    \begin{answer}{1.75in}
    % Put your answer here
    \end{answer}


    \item \points{10}
    Consider the following game:
    \begin{center}
        \begin{game}{4}{3}[$G_3$]
            \>  $L$      \>  $C$  \>  $R$      \\
            $T$  \> $5,10$  \> $16,8$  \> $0,0$ \\
            $M$  \> $0,-8$  \> $0,0$   \> $8,16$ \\
            $B$  \> $6,0$   \> $-8, 0$ \> $10,5$
        \end{game}
    \end{center}

    Let $v = (v_1,v_2)$ be signals over the actions for the row and column player respectively. Also let $\sigma = (\sigma_1, \sigma_2)$ be the identity mapping; that is, the signals recommend the actions for players to take. Together with following distribution $\pi$ over signals, is $(v, \pi, \sigma)$ a correlated equilibrium?  Justify your answer.

    \[\pi(v_1,v_2) = \begin{cases}
    \frac{1}{6} &\text{if } v_1=T, v_2=C,\\
    \frac{1}{12} &\text{if } v_1=T, v_2=R,\\
    \frac{1}{12} &\text{if } v_1=M, v_2=C,\\
    \frac{1}{6} &\text{if } v_1=M, v_2=R,\\
    \frac{1}{2} &\text{if } v_1=B, v_2=R,\\
    0 &\text{otherwise.}
    \end{cases}\]

    \begin{answer}{2in}
    % Put your answer here
    \end{answer}

\end{enumerate}


\clearpage
%------------------------------------------------------------------------------------------
\section*{Submission}

Each assignment consists of a \emph{problem set} file in PDF format containing the list of questions to answer.
Each assignment is to be submitted electronically via GradeScope before the due date.
The submission should consist of a PDF file containing the answers to the problem set.

A \LaTeX{} file is provided that you can edit to produce a PDF of your answers if you wish.  Otherwise, you can type your answers into your favourite word processor and print to PDF, or you can write your answers (legibly!) by hand and upload a scan.


%\bibliography{gtdt}
%\bibliographystyle{apalike}
\end{enumerate}
\end{document}
