%%%%%%%%%%%% 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}