lowerbound

1 files changed, 11 insertions, 1 deletions

diff --git a/main.tex b/main.tex
index 1de8ac4..4b28a4f 100644
--- a/main.tex
+++ b/main.tex
@@ -155,7 +155,17 @@ We can now state the main result of this section:
     \end{displaymath}
 \end{theorem}
 
-\stratis{Add lowerbound here too.}
+%\stratis{Add lowerbound here too.}
+
+In addition, we prove the following lower bound.
+\begin{theorem}\label{thm:lowerbound}
+There is no $2$-approximate, truthful, budget feasible, individionally rational mechanism for EDP. 
+\end{theorem}
+\stratis{move the proof as appropriate}
+\begin{proof}
+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]$  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, a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity it remains in the solution; by  threshold payment, it is paid at least $B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility and individual rationality: hence, the selected set attains a value $\log2$, while the optimal value is $2\log 2$.
+
+\end{proof}
 
 \subsection{Proof of theorem~\ref{thm:main}}