diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 4 |
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, |