diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 12 |
1 files changed, 11 insertions, 1 deletions
@@ -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}} |