From 56ef116dcbe0d4b81f7b5bc2d38d9d51add2c62a Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 7 Jul 2013 19:01:14 -0700
Subject: monotone

---
 appendix.tex | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'appendix.tex')

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,
-- 
cgit v1.2.3-70-g09d2

