
%%%%%%%%%%%% Subject: template for lecture notes %%%%%%%%%%%%%%%%%%%%
%
% (As usual, stolen from Yishay)
%
% Please send me the scribe notes as soon at they are ready (fiat@tau.ac.il).
%
% Here is the template file for writing up notes for this course.
% If you scribe on a Tuesday we ask that you please bring your
% notes by the following Tuesday.
%
%
% In order to make the notes more uniform and easier to read, we are providing
% several macros for theorems and such.  (Some examples of their use are
% included below.) Also, we ask that you follow a few stylistic conventions:
%
% Please write your notes as if you were explaining the material to another
% student, rather than as minutes of a meeting. (That is, don't write
% things like ``Today we started discussing...'' or ``next time,
% we will...'' or ``then, someone asked the question...''
% Just explain the material as clearly as you can.
%
% If you need to refer to an earlier lecture, use the lecture number.
% For example,  ``In Lecture 6 it was shown that...''
% To refer to a later lecture for which you don't know the number,
% just say something like,
% ``This impossibility result will be discussed further in a later
% lecture.'' (At the end of the course, I will go back and fill in the
% appropriate lecture numbers.)
%
% If material from a handout is covered in lecture, then we would like to
% include the text of the handout as a part of the notes to make them more
% self-contained.  To make your job easier, I will mail you the latex
% files for the relevent handouts, and you can merge them in at the
% appropriate places.  Also, you may want to annotate the handout as you
% see fit.  If you happen to take notes on a day that a homework is assigned,
% I will also mail you the exercises, which you can put at the end of your
% notes.
%
% Figures should be done in Latex, if at all possible.  You may have available
% on your system a program called ``texdraw.''  The program lets to draw
% figures with the mouse and then generates a latex file, which you can then
% insert into your text.  If you don't have this program, usually writing the
% latex commands yourself isn't that hard.  For very complicated figures, you
% may wish to leave the appropriate space in the text and draw the figures
% neatly (each on a separate page) in black ink.  For the first draft you
% hand in, you may not want to invest a lot of time drawing the figures very
% neatly, because there's a chance that we will want you to modify
% them.  Save that effort for the draft to be handed out.
%
% Please let me know if you have any questions.
%
%
\documentclass[12pt]{book}

\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{amssymb}


\usepackage{algorithm}

\usepackage{algorithmicx}

%Use algorithmicx to write "code", if needed.
% See http://ftp.ntua.gr/mirror/ctan/macros/latex/contrib/algorithmicx/algorithmicx.pdf

\usepackage{algpseudocode}


\newenvironment{proof}[1][Proof]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{definition}[1][Definition]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remark]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newcommand{\qed}{\nobreak \ifvmode \relax \else
      \ifdim\lastskip<1.5em \hskip-\lastskip
      \hskip1.5em plus0em minus0.5em \fi \nobreak
      \vrule height0.75em width0.5em depth0.25em\fi}
%
% this command enables to remove a whole part of the text
% from the printout
% to use it just enter
% \remove{
% before the text to be excluded and
% }
% after the text
\newcommand{\remove}[1]{}

%
% The following macros are used to generate nice code for programs.
% See example on how to use it below
%

%%%%%%%%%%%%%%%%%%%%% program macros %%%%%%%%%%%%%%%%%

%\newcommand{\Do}{{\small\bf do}\ }
%%\newcommand{\Return}{{\small\bf return\ }}
%\newcommand{\Proc}[1]{#1\+}
%\newcommand{\Returns}{{\small\bf returns}}
%\newcommand{\Procbegin}{{\small\bf begin}}
%\newcommand{\If}{{\small\bf if}\ \=\+}
%\newcommand{\Then}{{\small\bf then}\ \=\+}
%\newcommand{\Else}{\<{\small\bf else}\ \>}
%\newcommand{\Elseif}{\<{\small\bf elseif}\ }
%\newcommand{\Endif}{\<{\small\bf end\ if\ }\-\-}
%\newcommand{\Endproc}[1]{{\small\bf end} #1\-}
%\newcommand{\For}{{\small\bf for}\ \=\+}
%\newcommand{\Endfor}{{\small\bf end\ for}\ \-}
%\newcommand{\Loop}{{\bf loop}\ \= \+}
%\newcommand{\Endloop}{{\bf end\ loop}\ \-}
%\newenvironment{program}{
%    \begin{minipage}{\textwidth}
%    \begin{tabbing}
%    \ \ \ \ \=\kill
%  }{
%    \end{tabbing}
%    \end{minipage}
%  }

% a blank line
\def\blankline{\hbox{}}

%%%%%%%%%%%%%%%%%%%%% End of PROGRAM macros %%%%%%%%%%%%%%%%%


%
% The following macro is used to generate the header.
%
%

\newcommand{\lecture}[5]{
   \pagestyle{headings}
   \thispagestyle{plain}
   \newpage
   \setcounter{chapter}{#1}
   \setcounter{page}{#2}
%  \set\thechapter{#3}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 6.28in { {\bf Computational  Game Theory
                        \hfill Spring Semester, 2011/2012} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Lecture #1: #3  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Lecturer: #4 \hfill Scribe: #5} }
      }
   }
   \end{center}
   \markboth{Lecture #1: #3}{Lecture #1: #3}
   \vspace*{4mm}
}

%
% Use these macros for organizing sections of your notes.
% Each command takes two arguments: (1) the title of the section and and
% (2) a keyword for that section to appear in the index.  (See examples.)
% Please don't use \section, \subsection, and \subsubsection directly!
%

\newcommand{\topic}[2]{\section{#1} \index{#2} \markright{#1}}
\newcommand{\subtopic}[2]{\subsection{#1} \index{#2}}
\newcommand{\subsubtopic}[2]{\subsubsection{#1} \index{#2}}

%
% Convention for citations is first author's last name followed by other
% authors' last initials, followed by the year.  For example, to cite the
% seventh entry in the course bibliography, you would type: \cite{BurnsL80}
% (To avoid bibliography problems, for now we redefine the \cite command.)
%

\renewcommand{\cite}[1]{[#1]}

%
% These are just to make things a little easier:
%
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\blank}{\vspace{1ex}}   % generates a blank line in the output

%
% Use these for theorems, lemmas, proofs, etc.
%
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}

%
% Use the following for definitions.
% \bigdef is for definitions to be set off by themselves; \smalldef is for
% definitions given in the middle of a paragraph.
%
\newenvironment{dfn}{{\vspace*{1ex} \noindent \bf Definition }}{\vspace*{1ex}}
\newcommand{\bigdef}[2]{\index{#1}\begin{dfn} {\rm #2} \end{dfn}}
\newcommand{\smalldef}[1]{\index{#1} {\em #1}}


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

\begin{document}
%\lecture{**LECTURE-NUMBER**}{**1ST-PAGE**}{**DATE**}{**LECTURER**}{**SCRIBE**}
\lecture{1}{1}{March 7}{Amos Fiat}{Adam Smith}

% **** YOUR NOTES GO HERE

%    Some general latex examples and examples making use of the
% macros follow.  You may want to latex this file and print out the result
% to get an idea of how things look. (You will need to latex the file twice
% to get the cross-references right.)
%    Even if you already know latex, you should take a few minutes to
% look over these examples, so that you understand the general conventions
% we're using.


\topic{Some theorems and stuff}{stuff} % Don't be this informal in your notes!

We now delve right into the proof.

\begin{lemma}
\label{L7:mylemma}   % label used to refer to the lemma later. (see below)
                        % IMPORTANT: to keep labels unique among lectures,
                        % please precede every label with the lecture number,
                        % as shown (this prefix would be used for lecture 7.
This is the first lemma of the lecture.
\end{lemma}

\begin{proof}
The proof is by induction on \ldots
\end{proof}

\begin{theorem}
This is the first theorem.
\end{theorem}

\begin{proof}
This is the proof of the first theorem theorem.
\end{proof}

\subtopic{A few notes}{few items}

Here is an itemized list:
\bi
\item this is the first item
\item this is the second item
\ei

\subtopic{A few more items}{more items}

Here is an enumerated list:
\be
\item this is the first item
\item this is the second item
\ee

\topic{Next topic}{myword}

We are now ready for a major definition.

\bigdef{myword}{This is the definition of {\em myword}.}

\begin{corollary}
This is a corollary following from the definition of myword.
\end{corollary}

Sometimes we define terms in the middle of a paragraph.
This is a \smalldef{different term} being defined.

On to the next page:

\newpage  % it's not necessary to do this before a figure -- latex should
          % position the figures appropriately

%
% **** HERE'S AN EXAMPLE OF HOW TO DO FIGURES WITH LATEX -- DON'T GET SCARED:
% **** THIS FIGURE PROBABLY IS MORE COMPLICATED THAT ANY YOU WILL NEED
% **** TO DRAW...
%
\begin{figure}
\begin{picture}(400,250)(0,25) % begins picture environment

\put(200,262.5){\circle{25}}
\put(200,262.5){\makebox(0,0)[c]{U}}

\put(100,187.5){\circle{25}}
\put(100,187.5){\makebox(0,0)[c]{U}}
\put(300,187.5){\circle{25}}
\put(300,187.5){\makebox(0,0)[c]{U}}
\put(315,187.5){\makebox(0,0)[bl]{...}}

\put(50,112.5){\circle{25}}
\put(50,112.5){\makebox(0,0)[c]{U}}
\put(150,112.5){\circle{25}}
\put(150,112.5){\makebox(0,0)[c]{U}}
\put(165,112.5){\makebox(0,0)[bl]{...}}
\put(250,112.5){\circle{25}}
\put(250,112.5){\makebox(0,0)[c]{$x$}}
\put(350,112.5){\circle{25}}
\put(350,112.5){\makebox(0,0)[c]{U}}
\put(365,112.5){\makebox(0,0)[bl]{...}}

\put(25,62.5){\circle{25}}
\put(25,62.5){\makebox(0,0)[c]{$a$}}
\put(75,62.5){\circle{25}}
\put(75,62.5){\makebox(0,0)[c]{$b$}}
\put(90,62.5){\makebox(0,0)[bl]{...}}
\put(125,62.5){\circle{25}}
\put(125,62.5){\makebox(0,0)[c]{$x$}}
\put(175,62.5){\circle{25}}
\put(175,62.5){\makebox(0,0)[c]{$y$}}
\put(190,62.5){\makebox(0,0)[bl]{...}}
\put(325,62.5){\circle{25}}
\put(325,62.5){\makebox(0,0)[c]{$x$}}
\put(375,62.5){\circle{25}}
\put(375,62.5){\makebox(0,0)[c]{$a$}}
\put(390,62.5){\makebox(0,0)[bl]{...}}

\thinlines
\put(200,250){\line(-2,-1){100}}
\put(200,250){\line(2,-1){100}}

\put(100,175){\line(-1,-1){50}}
\put(100,175){\line(1,-1){50}}
\put(300,175){\line(-1,-1){50}}
\put(300,175){\line(1,-1){50}}

\put(50,100){\line(-1,-1){25}}
\put(50,100){\line(1,-1){25}}
\put(150,100){\line(-1,-1){25}}
\put(150,100){\line(1,-1){25}}

\put(350,100){\line(-1,-1){25}}
\put(350,100){\line(1,-1){25}}

\end{picture}
\caption{This is my picture.} % the figure caption (numbered by latex)
\label{L7:mypicture}       % identifies figure so you can refer to it --
                           % the label always goes after the caption
\end{figure}

%
% **** Here's how to handle figures you draw yourself:
%

\begin{figure}
   \vspace{3.5cm}                % amount of space to leave
   \caption{This is a new picture.} % the figure caption (numbered by latex)
   \label{L7:myotherpicture}  % identifies figure so you can refer to it
\end{figure}

%
% **** Here's how to refer to figures:
%
This can be seen in Figure \ref{L7:mypicture}.  Note that latex actually
places this text {\em before} the figure, even though it appears after the
figure in the .tex file.
%
% **** Here's how to write code using algorithmicx:
%

% Definitions used below: 
\newcommand{\bk}{\mathbf{k}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bbb}{\mathbf{b}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\ef}[0]{\textsf{EF}}
\newcommand{\demandi}[0]{D_i}
\newcommand{\demandiplus}[0]{D_i^{+}}
\newcommand{\pstar}{p^{*}}
\newcommand{\reals}[0]{\mathbb{R}}
\newcommand{\integers}[0]{\mathbb{Z}}
\newcommand{\revenue}[0]{\mathrm{R}}

\begin{algorithm}[h]
\begin{algorithmic}[1]

\Procedure{Multi-Unit Auction with Budgets}{$v,b,m$}

\parbox{12cm}{$\triangleright$ {Input:  $\mathcal{A} = \left\langle n, m, \bbb, \bv \right\rangle$.}}


\State{Let \vspace{-0.3cm}$$p^* = \min \left\{ p\geq 0 \mid
\sum_{i=1}^n D_i^+(p) \leq m\right\}.$$} \label{alg:setpstar}

\parbox{12cm}{$\triangleright$ {It must be that $\sum_{i=1}^n D_i(p^*) > m \mbox{\ and\ } \sum_{i=1}^n D_i^+(p^*) \leq m.$}\par}

\State{Set $R_1=0$, $R_2=0$.}

\parbox{12cm}{$\triangleright$ {We consider two different envy-free allocations: $R_1$ is the case where we sell items at a price strictly $> p^*$, and we meet all demands. $R_2$ is the case where we sell items at a price of $p^*$, while avoiding envy.}\par}

\If{$\sum_{i=1}^n D_i^+(p^*)>0$} \Comment{See Figure \ref{fig-r1}.}
\State{Let  \vspace{-0.3cm} $$\epsilon^* = \max\left\{\epsilon>0
\mid \sum_{i=1}^n D_i^+(p^*) = \sum_{i=1}^n D_i(p^*+\epsilon)
\right\}.$$} \State{Set  \vspace{-0.3cm} $$R_1 = (p^*+\epsilon^*)
\cdot \sum_{i=1}^n D_i^+(p^*).$$} \label{alg:r1}

\EndIf \State{Let  \vspace{-0.3cm} $$t_j = \left|\{ i \mid
D_i(p^*)\geq j, v_i \neq p^*\}\right|.$$}

\parbox{12cm}{$\triangleright$ {$t_j$ is the number of non-value limited bidders with demand $\geq j$, i.e., rows.}}

\If{$\sum_{j\geq 1} t_j \leq m$} \label{alg:ifr2}

\parbox{12cm}{$\triangleright$ {See Figure
\ref{fig-r2a}, we satisfy positive demands of all bidders except
those for which $v_i = p^*$. All the remaining items
 can be sold arbitrarily to such agents. In total we will sell exactly $m$ items at price $p^*$.}\par}

\State{Set  \vspace{-0.3cm} $$R_2 = m \cdot p^*.$$}
\label{alg:r2case1} \Else

\State{Let $r = \max \{\ell | t_\ell >0, \sum_{j=1}^\ell t_j \leq
m\}$.} \Comment{$r$ is the number of ``rows" we sell to.}
\label{alg:setr}

\parbox{12cm}{$\triangleright$ {See Figure \ref{fig-r2b}, we don't meet the total demand of non-value limited bidders. We
sell row by row so that no bidder with unmet demand will envy
another with a larger bundle. We sell all items  at a price of
$p^*$, but this is {\sl not} proper item pricing.}\par}

\State{Set \vspace{-0.3cm} $$R_2 = p^* \cdot \sum_{j=1}^r t_j.$$}
\label{alg:r2case2} \EndIf \EndProcedure
\end{algorithmic} \caption{Multi-Unit Auction with Budgets ($m\ge n$)} \label{alg:multienvy}
\end{algorithm}


% And adding a jpg figure:



\newpage
\begin{figure}[t]
\centering
%\fbox
{\includegraphics[scale=0.35]{diplus.jpg}}
 \caption{Figure includes jpg file.}.
\label{fig-diopt}
\end{figure}



% **** THIS ENDS THE EXAMPLES. DON'T DELETE THE FOLLOWING LINE:

\end{document}
