monotone

1 files changed, 2 insertions, 2 deletions

diff --git a/appendix.tex b/appendix.tex
index 9175e34..6be1a85 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -641,7 +641,7 @@ The complexity of the mechanism is given by the following lemma.
     The value function $V$ in \eqref{modified} can be computed in time
     $O(\text{poly}(n, d))$ and the mechanism only involves a linear
     number of queries to the function $V$. 
-    By Proposition~\ref{prop:monotonicity}, line 3 of Algorithm~\ref{mechanism}
+    By Proposition~\ref{prop:monotonicity}, line \ref{relaxexec} of Algorithm~\ref{mechanism}
     can be computed in time
     $O(\text{poly}(n, d, \log\log \frac{B}{b\varepsilon\delta}))$. Hence the allocation
     function's complexity is as stated. 
@@ -732,7 +732,7 @@ of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed
 
 \section{Proof of Theorem \ref{thm:lowerbound}}\label{proofoflowerbound}
 
-Suppose, for contradiction, that such a mechanism exists. Consider two
+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
 be in the set selected by the mechanism, otherwise the ratio is unbounded,