From 767e7ba86a7e916680faef79f885f1a5ce8c6b2b Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sat, 6 Jul 2013 22:27:45 -0700 Subject: moved algo to appendix --- appendix.tex | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'appendix.tex') 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]$ -- cgit v1.2.3-70-g09d2