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