\documentclass[10pt]{article}
\usepackage[OT4]{fontenc}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}
\usepackage{enumerate}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\input{preamble.tex}
\newcommand{\psetsol}[3]{\handout{#1}{}{Author:
#2}{Collaborator: #3}{Solutions to Problem Set #1}}

\parindent 0pt

\newcommand{\cS}{\mathcal{S}}
\newcommand{\ocS}{\overline{\mathcal{S}}}
\newcommand{\bbR}{\mathbb{R}}

\begin{document}



\psetsol{2}{Your name here}{Name/``None''}


{\bf Problem 1.} A three-player game is zero-sum if the utilities of all three players always sum up to zero. Show that one can reduce the problem of finding a Nash equilibrium in a \emph{general} two-player game to the problem of finding a Nash equilibrium in a three-player \emph{zero-sum} one.\\

\emph{Note: In Lecture 6, we saw that one can find an (approximate) Nash equilibrium of any two-player zero-sum games efficiently. As there is strong evidence suggesting that finding Nash equilibrium is computationally hard already for general two-person games, the above reduction shows that finding Nash equilibrium in zero-sum games becomes much more difficult once we move from two to three players.}\\

% Your solution goes here

\bigskip

{\bf Problem 2.} Consider a two-player game where the sets of possible (pure) actions of both players are the same, i.e., $\cS_1=\cS_2=\cS^*$. We say that such game is \emph{symmetric} iff for any $s_1,s_2\in \cS^*$, 
$$u_1(s_1,s_2)=u_2(s_2,s_1),$$
i.e., the values of players' utilities swap when the players swap their actions. 
\begin{enumerate}[(a)]
\item Show that if there are only two (pure) actions, i.e., $|\cS^*|=2$, then any symmetric game has to have a \emph{pure} Nash equilibrium.
\item Consider now the case when there is more than two (pure) actions, i.e., $|\cS^*|>2$. Either prove that each such game has to have a pure Nash equilibrium too, or disprove this claim by exhibiting a counterexample.
\end{enumerate}

% Your solution goes here

\bigskip

{\bf Problem 3.} 
Consider a communication network modeled as a directed graph $G=(V,E)$ in which every arc $e\in E$ is owned by different player. Our goal is to choose a communication path between two specified nodes $s$ and $t$ in $G$ and we want to do it in a way that maximizes the social welfare. Each player has a \emph{private} utility function $u_e$ that is $0$ if his/her arc is not a part of this $s$-$t$ path, and equal to $-c_e$ otherwise. (We assume here that all $c_e$ are non-negative.) Design an incentive compatible mechanism that will choose this path in a way that maximizes social welfare. Be explicit regarding what the outcome choice is and what are the corresponding payments.\\

% Your solution goes here

\bigskip

{\bf Problem 4.} Let us say that a two-person game is a \emph{conflicting interests} game if for any two outcomes $s,s'\in \ocS$, we have $$u_1(s)>u_1(s') \ \textrm{iff} \ u_2(s)<u_2(s').$$ (Note that any zero-sum game is a conflicting interests game, but the reverse is not necessarily true.) Let us fix some conflicting interests game and let us define $$s^*_1 := \arg\max_{s_1\in \ocS_1} \min_{s_2\in \ocS_2} u_1(s_1,s_2) \ \textrm{and} \ s^*_2 := \arg\max_{s_2\in \ocS_2} \min_{s_1\in \ocS_1} u_2(s_1,s_2).$$ Show that $(s_1^*,s_2^*)$ is a Nash equilibrium.\\

\emph{Note: MinMax theorem proves this for the case of zero-sum games.}\\

% Your solution goes here

\bigskip
\end{document}




