diff options
| -rw-r--r-- | main.tex | 67 |
1 files changed, 30 insertions, 37 deletions
@@ -128,7 +128,7 @@ be to prove that $OPT(L_\mathcal{N}, B)$ is close to $V(S_G)$. To do so, our main technical contribution is to prove that $L_\mathcal{N}$ has a bounded approximation ratio to the value function $V$ (Lemma~\ref{lemma:relaxation}). -The resulting mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. The constant $C$ is an absolute constant, that we determine in Section~\ref{...} (See \eqref{...}). +The resulting mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. The constant $C$ is an absolute constant, that we determine in Section~\ref{sec:proofofmainthm} (see \eqref{eq:C}). \begin{algorithm} \caption{Mechanism for \EDP{}}\label{mechanism} \begin{algorithmic}[1] @@ -176,7 +176,7 @@ There is no $2$-approximate, truthful, budget feasible, individionally rational 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}} +\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} \stratis{individual rationality???} @@ -274,25 +274,23 @@ $L_\mathcal{N}$. %\end{displaymath} \end{lemma} Its proof is our main technical contribution, and can be found in Section \ref{sec:relaxation}. -\begin{lemma}\label{lemma:approx} +Using this lemma, we can complete the proof of Theorem~\ref{thm:main} by showing that, %\begin{lemma}\label{lemma:approx} %C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C %(e-1) -10e +2}\right)\right) - For any $\varepsilon > 0$, if $L(x^*)$ has been computed to a precision + for any $\varepsilon > 0$, if $L(x^*)$ has been computed to a precision $\varepsilon$, then the set $S^*$ allocated by the mechanism is such that: - \begin{displaymath} + \begin{align} OPT(V,\mathcal{N}, B) - \leq \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)} V(S^*)+ \varepsilon - \end{displaymath} -\end{lemma} - -\begin{proof} - Let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 2 of algorithm~\ref{mechanism}, a quantity + \leq \frac{14e\!-\!3 + \sqrt{160e^2\!-\!48e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound} + \end{align} +%\end{lemma} + To see this, let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 2 of algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L_{\mathcal{N}\setminus {i^*}}(x^*) \leq \tilde{L}+\varepsilon$ has been computed (lemma~\ref{lemma:complexity} states that this is computed in time within our complexity guarantee). If the condition on line 3 of the algorithm holds, then: \begin{displaymath} - V(i^*) \geq \frac{1}{C}L(x^*)-\frac{\varepsilon}{C} \geq + V(i^*) \geq \frac{1}{C}L_{N\setminus \{i\}}(x^*)-\frac{\varepsilon}{C} \geq \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B) -\frac{\varepsilon}{C} \end{displaymath} as $L$ is a fractional relaxation of $V$ on $\mathcal{N}\setminus \{i^*\}$. Also, @@ -303,52 +301,47 @@ Its proof is our main technical contribution, and can be found in Section \ref{s \begin{equation}\label{eq:bound1} OPT(V,\mathcal{N}, B)\leq (1+C)V(i^*) + \varepsilon \end{equation} - If the condition of the algorithm does not hold, by applying Lemmas - \ref{lemma:relaxation} and \ref{lemma:greedy-bound}: + Note that $OPT(L_{\mathcal{N}\setminus\{i^*\}},B)\leq OPT(L_{\mathcal{N}},B)$. If the condition does not hold, + from Lemmas \ref{lemma:relaxation} and \ref{lemma:greedy-bound}: \begin{align*} - V(i^*) & \leq \frac{1}{C}L(x^*) + \frac{\varepsilon}{C}\leq \frac{1}{C} + V(i^*) & \stackrel{}\leq \frac{1}{C}L_{\mathcal{N}}(x^*) + \frac{\varepsilon}{C}\leq \frac{1}{C} \big(4 OPT(V,\mathcal{N}, B) + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\ & \leq \frac{1}{C}\left(\frac{4e}{e-1}\big(3 V(S_G) + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C} \end{align*} - - Thus: + Thus, if $C$ is such that $C(e-1) -10e +2 > 0$, \begin{align*} V(i^*) \leq \frac{12e}{C(e-1)- 10e + 2} V(S_G) + \frac{(e-1)\varepsilon}{C(e-1)- 10e + 2} \end{align*} - - Finally, using again lemma~\ref{lemma:greedy-bound}, we get: + Finally, using again Lemma~\ref{lemma:greedy-bound}, we get: \begin{multline}\label{eq:bound2} OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{8e}{C (e-1) -10e +2}\right) V(S_G)\\ +\frac{2e\varepsilon}{C(e-1)- 10e + 2} \end{multline} - - Looking at \eqref{eq:bound1} and \eqref{eq:bound2}, we see that the optimal - value for $C$ is: + To minimize the coefficients of $V_{i^*}$ and $V(S_G)$ in \eqref{eq:bound1} and \eqref{eq:bound2} respectively, + we wish to chose for $C=C^*$ such that: \begin{displaymath} C^* = \argmin_C \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C (e-1) -10e +2} \right)\right) \end{displaymath} - This equation has two solutions. Only one of those is such that: - \begin{displaymath} - C(e-1) -10e +2 \geq 0 - \end{displaymath} - which is needed in the above derivation. This solution is: - \begin{displaymath} - C^* = \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)} - \end{displaymath} - For this solution we have: - \begin{displaymath} - \frac{2e\varepsilon}{C(e-1)- 10e + 2}\leq 1 - \end{displaymath} - Plugging the expression of $C^*$ in \eqref{eq:bound1} and \eqref{eq:bound2} - gives the approximation ratio in the lemma's statement. -\end{proof} + $ C(e-1) -10e +2 \geq 0$. + %which is needed in the above derivation. +This solution is: + \begin{align} + C^* = \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)} \label{eq:c} + \end{align} + For this solution, + % \begin{displaymath} + $ \frac{2e\varepsilon}{C^*(e-1)- 10e + 2}\leq \varepsilon. $ + % \end{displaymath} + Placing the expression of $C^*$ in \eqref{eq:bound1} and \eqref{eq:bound2} + gives the approximation ratio in \eqref{approxbound}, and concludes the proof of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed +%\end{proof} \subsection{Proof of lemma \ref{lemma:relaxation}}\label{sec:relaxation} Since $L_\mathcal{N}$ is a relaxation of the value function $V$, we have: |