budget feasible and first lower bound

1 files changed, 1 insertions, 0 deletions

diff --git a/proof_of_lower_bound1.tex b/proof_of_lower_bound1.tex
new file mode 100644
index 0000000..ac957a0
--- /dev/null
+++ b/proof_of_lower_bound1.tex
@@ -0,0 +1 @@
+Given an $M>0$, consider a scenario with $n=4$ experiments of dimension $d=2$. For $e_1,e_2$ the standard basis vectors in $\reals^2$, let $x_1 = e_1$, $x_2 = e_1$, and $x_3=\delta e_1$, $x_4=\delta e_2$, where $0<\delta<1/(M-1) $. Moreover, assume that $c_1=c_2=0.5+\epsilon$, while $c_3=c_4=\epsilon$, for some small $\epsilon>0$. Suppose, for the sake of contradiction, that there exists a mechanism with approximation ratio less than $M$. Then, it must include in the solution $S$ at least one of $x_1$ or $x_2$: if not, then $V(S)\leq \det \left(x_3\T{x_3}+x_4\T{x^4}\right)=\delta^2$, while $OPT = (1+\delta)\delta$, so their ratio is greater than $M$, a contradiction. W.l.o.g., suppose thus that the solution contains $x_1$. By the monotonicity property, if user $1$ reduces her cost to $B/2-3\epsilon$, she will still be in the solution. By threshold payment, she must receive in this case a payment that is at least $B/2+\epsilon$ (as increasing her cost to this value still keeps her in the solution). By individual rationality, user $x_2$ cannot be included in the solution, so $V(S)$ is at most $(1+\delta)\delta$. However, the optimal solution includes all experiments, and yields $OPT=(1+\delta)^2$, so the ratio is at least $(1+\delta)/\delta>M$. \qed