diff options
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]$ |