From c7ca7fb461ec2044f8aefcedfcd903d8b5945fc1 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sun, 22 Sep 2013 18:28:41 -0400 Subject: Last fixes --- appendix.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'appendix.tex') diff --git a/appendix.tex b/appendix.tex index 1a5bcc5..6926e00 100755 --- a/appendix.tex +++ b/appendix.tex @@ -880,7 +880,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 -Finally, we prove the lower bound stated in Theorem~\ref{thm:main} +Finally, we prove the lower bound stated in Theorem~\ref{thm:main}. Suppose, for contradiction, that such a mechanism exists. From Myerson's Theorem \cite{myerson}, a single parameter auction is truthful if and only if the allocation function is monotone and agents are paid theshold payments. Consider two experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$ and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must -- cgit v1.2.3-70-g09d2