%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}



%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~38~~~Introduction to Algorithms
                        \hfill Spring 2014} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM
% HERE:


\newcommand{\set}[1]{\left \{{#1} \right \}}

\begin{document}
\problemset{5}{May 15}{\bf May 22}

Note: the due date has been shifted due to Ditch Day.

Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the optional text (CLRS). The full honor code guidelines can be found in the course syllabus.


Please attempt all problems. {\bf To facilitate grading, please
turn in each problem on a separate sheet of paper and put your
name on each sheet. Do not staple the separate sheets.}
\begin{enumerate}
\item Given a flow network with edge capacities $c(e)$, consider the following variants of the maximum flow problem. For each, formulate them as a linear program. 
\begin{enumerate}
\item We are interested in vertex-limited flow: for each vertex $v$ there is a limit $g(v)$, and we want the flow entering $v$ plus the flow exiting $v$ to not exceed $g(v)$. We are interested in the maximum $s$-$t$ flow subject to these additional constraints.

\item There is a distinguished edge $e^*$ which is ``fragile''. We are
  interested in the maximum $s$-$t$ flow that minimizes the flow on
  edge $e^*$. That is, the flow value should be maximum, but among all
  such maximum flows, we want the one with the smallest flow across edge $e^*$.
\end{enumerate}

\item Total unimodularity. A matrix is said to be totally-unimodular
  if every square  submatrix (obtained by restricting to a subset of the rows and subset of the columns) has determinant $0$, $1$, or $-1$. The polytope $\{x : Ax = b, x \in R^n \geq 0\}$ has only integer vertices if $A$ is totally unimodular and $b$ is integer. 
\begin{enumerate}
\item Formulate the Assignment Problem as a linear program in which you assume that the variables take on only integer values (this is called an integer linear program). Show that the constraint matrix is totally unimodular, and hence solving this linear program gives a legitimate solution to the Assignment Problem.
    
\item Suppose a car company has $m$ storage lots and $n$ retail showrooms, and it needs to ship cars from storage lots to showrooms. Each storage lot has a supply $a_i$ and each showroom has a demand $b_i$. We are also given costs $c_{i,j}$ between every storage lot and showroom. Shipping $x$ units from storage lot $i$ to showroom $j$ costs $c_{i,j}x$. You want to determine an optimal shipment scheme subject to the supply and demand constraints, that minimizes total cost. Formulate this as a linear program and then show that the constraint matrix is totally unimodular (so you are never asked to ship 2/3 of a car!)
    

\end{enumerate}
\item Zero-sum games and Nash Equilibria. Consider two players called
  the ``row player'' and the ``column player'' who each have $n$
  possible moves to chose from. An $n \times
  n$ matrix $M$ specifies the payoffs as follows: if the row player
  chooses move $i$ and the column player chooses move $j$, then the
  payoff to the row-player is $M[i,j]$ and the payoff to the column
  player is $-M[i,j]$ (hence the term ``zero sum''). A {\em mixed
    strategy} is one in which the player chooses from some
  distribution of moves, that is they choose move $i$ with probability
  $p_i$ (and we have $p_i \ge 0$ and $\sum_i p_i = 1$). A pair of
  mixed strategies $p$ and $q$, for the row-player and column-player
  gives rise to an expected payoff to the row-player of $\sum_{i,j}
  p_iq_jM[i,j]$ and an expected payoff to the column-player of
  $-\sum_{i,j}p_iq_jM[i,j]$. Such a pair is said to be a Nash
  equilibrium if no player has any incentive to unilaterally deviate
  from their current mixed strategy. That is, 
\begin{enumerate}
\item for any $p' \ne p$, we have $\sum_{i,j} p_i'q_jM[i,j] \leq
  \sum_{i,j} p_iq_jM[i,j]$, and 
\item for any $q' \ne q$, we have $-\sum_{i,j} p_iq_j'M[i,j] \leq -\sum_{i,j}p_iq_jM[i,j]$.
\end{enumerate}
An important question is how to efficiently find such an equilibrium. 
\begin{enumerate}
\item Suppose you are given the sets $S = \{i : p_i > 0\}$ and $T =
  \{j : q_j > 0\}$ for a pair $p, q$ that represent a Nash
  equilibirum. Show how to find a Nash equilibrium in polynomial time using linear
  programming and this information.
\item Give a $2^{O(2n)}\cdot \mbox{poly}(n)$ time algorithm to find a Nash
  equilibrium given the payoff matrix $M$. 
\end{enumerate}

\end{enumerate}
\end{document}