diff options
| author | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-07-06 22:27:45 -0700 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-07-06 22:27:45 -0700 |
| commit | 767e7ba86a7e916680faef79f885f1a5ce8c6b2b (patch) | |
| tree | 6857e0558ef8b1ff7326deb1218571800bd891d2 /appendix.tex | |
| parent | a8038aaa6c32a43e95b2730a3b8f63a286193a09 (diff) | |
| download | recommendation-767e7ba86a7e916680faef79f885f1a5ce8c6b2b.tar.gz | |
moved algo to appendix
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 5 |
1 files changed, 3 insertions, 2 deletions
diff --git a/appendix.tex b/appendix.tex index 0f6e6b4..f9564c3 100644 --- a/appendix.tex +++ b/appendix.tex @@ -513,7 +513,8 @@ Formally, there must exist some $\alpha\geq 1$ should be computable in time polynomial in various parameters. %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$? Needed to say something in general, but not in our case where the value function can be computed in polynomial time}. \end{itemize} - +\section{Proof of Lemma~\ref{thm:myerson-variant}}\label{sec:myerson} +\input{myerson} \section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} \begin{algorithm}[!t] @@ -719,7 +720,7 @@ Placing the expression of $C$ in \eqref{eq:bound1} and \eqref{eq:bound2} gives the approximation ratio in \eqref{approxbound}, and concludes the proof of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed -\section{Proof of Theorem \ref{thm:lowerbound}} +\section{Proof of Theorem \ref{thm:lowerbound}}\label{proofoflowerbound} Suppose, for contradiction, that such a mechanism exists. Consider two experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$ |