1
|
Given $M>1$, consider $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 $M$. Then, it must include in the solution $S$ at least one of $x_1$ or $x_2$: if not, then $V(S)\leq \delta^2$, while $OPT = (1+\delta)\delta$, a contradiction. Suppose thus that the solution contains $x_1$. By the monotonicity property, if the cost of experiment $x_1$ reduces to $B/2-3\epsilon$, $x_1$ will still be in the solution. By threshold payments, experiment $x_1$ receives in this case a payment that is at least $B/2+\epsilon$. By individual rationality and budget feasibility, $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$, a contradiction. %so the ratio is at least $(1+\delta)/\delta>M$. %\qed
|
