\documentclass{article}[12pt]

\newtheorem{thm}{Theorem}
\usepackage{hyperref}

\newfont{\bssten}{cmssbx10}

\newcommand{\p}{\ensuremath{\mbox{Pr}}}
\newcommand{\E}{\ensuremath{\mbox{E}}}

%%---------------------------------------------------------------------------
%%      Margins:
%%---------------------------------------------------------------------------
%\oddsidemargin  0in
%\evensidemargin 0in
%\topmargin -0.5in
%\headheight 0.25in
%\headsep 0.25in
%\textwidth   6.5in
%\textheight 9in
%\marginparsep 0pt \marginparwidth 0pt
%\parskip 1.5ex  \parindent 0ex \footskip 20pt




\begin{document}

\begin{center}
{\Large \bf MS\&E 337 Information Networks \\ Fall 2007 \\ Homework
\#2 \\ Due Fri. 12/14}
\end{center}
\vspace{3pt}

%\maketitle
\begin{enumerate}
\item Show that the diameter of a graph $G(V,E)$ with constant expansion is at
  most logarithmic in the number of vertices $n$. 
\item Given a simple, undirected graph $G(V,E)$, the \emph{switch}
  operation is as follows: 
\begin{itemize}
\item Pick two distinct edges $(i,j)$ and $(k,l)$
  uniformly at random.  
\item Choose a perfect matching $M$ of
  $\{i,j,k,l\}$.  
\item If the resulting graph remains simple, remove
$(i,j)$, $(k,l)$ and add $M$. Otherwise do nothing.
\end{itemize}

Note that a \emph{switch} operation preserves the degree sequence of $G$.
Show that the Markov chain defined by \emph{switch} is ergodic with
uniform stationary distribution over the space of graphs with the same
degree sequence of $G$.

\item A coordination game on a graph $G$ with parameter $q$ is a game in
  which, across each edge $(v,w)$, nodes $v$ and $w$ each receive a payoff
  of $q$ if they both choose behavior A, they each receive a payoff of
  $1-q$ if they both choose behavior B, and they each receive a payoff
  of $0$ if they choose opposite behaviors.  It is natural to ask what
  happens if we consider a more general kind of coordination game on
  each edge. Suppose in particular that, on each edge $(v,w)$, node
  $v$ receives payoff $u_{XY}$ if it chooses strategy $X$ while $w$
  chooses strategy $Y$, for any choice of $X \in \{A,B\}$ and $Y \in
  \{A,B\}$. Moreover, to preserve the coordination aspect, we assume
  that it is still better to play matching strategies: $u_{AA} >
  u_{BA}$ and $u_{BB} > u_{AB}$.

  Prove that for any infinite graph $G$ with finite node degrees, and
  for any choice of payoffs $\{u_{AA}, u_{BA}, u_{AB}, u_{BB}\}$ satisfying
  $u_{AA} > u_{BA}$ and $u_{BB} > u_{AB}$, there exists a real number
  $q$ such that the following holds: A finite set $S$ is contagious in
  $G$ with respect to the coordination game defined by $\{u_{AA}, u_{BA},
  u_{AB},u_{BB}\}$ if and only if it is contagious in $G$ with respect to the
  coordination game with parameter $q$.

(Note: this question is from \emph{Cascading Behavior in Networks:
  Algorithmic and Economic Issues} by Jon Kleinberg, available at\\
\url{http://www.cs.cornell.edu/home/kleinber/agtbook-ch24.pdf},\\ also
handed out in class.  For background and definitions, see his paper.)

\end{enumerate} 
\end{document}