diff options
| -rw-r--r-- | main.tex | 153 |
1 files changed, 95 insertions, 58 deletions
@@ -72,7 +72,6 @@ $R_\mathcal{N}(\mathbf{1}_S) = V(S)$. The optimization program \leq B\right\} \end{displaymath} - A relaxation which is commonly used, due to its well-behaved properties in the context of maximizing submodular functions, is the \emph{multi-linear} extension: @@ -111,13 +110,14 @@ in the above formula: &= \log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right) \end{align} -This function is well-known to be concave (see \emph{e.g.} -\cite{boyd2004convex}). Hence, its maximum value can be computed in polynomial -time (TODO elaborate) and can be used as a threshold rule in our mechanism. -The main challenge will 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}). +This function is well-known to be concave and even self-concordant (see \emph{e.g.} +\cite{boyd2004convex}). In this case, the analysis of Newton's method for +self-concordant functions in \cite{boyd2004convex}, shows that it is possible +to find the maxmimum of $L_\mathcal{N}$ to any precision $\varepsilon$ in +a number of iterations $O(\log\log\varepsilon^{-1})$. The main challenge will +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 mechanism for \EDP{} is presented in algorithm \ref{mechanism}. \begin{algorithm} @@ -144,15 +144,16 @@ The mechanism for \EDP{} is presented in algorithm \ref{mechanism}. We can now state the main result of this section: \begin{theorem}\label{thm:main} - The mechanism described in Algorithm~\ref{mechanism} is truthful, - and budget feasible. Furthermore, choosing: - \begin{displaymath} - C = C^* = \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)} - \end{displaymath} - we get an approximation ratio of: - \begin{displaymath} - 1 + C^* = \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)}\simeq 19.68 - \end{displaymath} + The mechanism described in algorithm~\ref{mechanism} is truthful, + and budget feasible. Furthermore, for any $\varepsilon>0$, the mechanism + has a complexity $O\left(\text{poly}(|\mathcal{N}|, d, + \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that: + \begin{align*} + OPT(V,\mathcal{N}, B) + & \leq \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)} V(S^*)+ + \varepsilon\\ + & \simeq 19.68V(S^*) + \varepsilon + \end{align*} \end{theorem} %\stratis{Add lowerbound here too.} @@ -164,7 +165,6 @@ There is no $2$-approximate, truthful, budget feasible, individionally rational \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}} @@ -242,25 +242,58 @@ Hence, the total payment is bounded by: \end{displaymath} \end{proof} -\begin{lemma}\label{lemma:approx} - Let $S^*$ be the set allocated by the mechanism. Let us write: +\begin{lemma}\label{lemma:complexity} + For any $\varepsilon > 0$, the complexity of algorithm~\ref{mechanism} is + $O(\text{poly}(|\mathcal{N}|, d, \log\log \varepsilon^{-1}))$. +\end{lemma} + +\begin{proof} + The value function $V$ \eqref{modified} can be computed in time + $O(\text{poly}(|\mathcal{N}|, d))$ and the mechanism only involves a linear + number of queries to the function $V$. + + The function $\log\det$ is concave and self-concordant (see + \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be find + to a precision $\varepsilon$ in a number of iterations of Newton's method + $O(\log\log\varepsilon^{-1})$. Each iteration of Newton's method can be + done in time $O(\text{poly}(|\mathcal{N}|, d))$. Thus, line 2 of + algorithm~\ref{mechanism}, can be computed in time + $O(\text{poly}(|\mathcal{N}|, d, \log\log \varepsilon^{-1}))$. +\end{proof} + +Finally, we prove the approximation ratio of the mechanism. We use the +following lemma, which gives an approximation ratio of the function +$L_\mathcal{N}$. Its proof is our main technical contribution and is done in +section \ref{sec:relaxation}. + +\begin{lemma}\label{lemma:relaxation} + We have: \begin{displaymath} - C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C - (e-1) -10e +2}\right)\right) + OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B) + + 2\max_{i\in\mathcal{N}}V(i) \end{displaymath} +\end{lemma} - Then: +\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 + $\varepsilon$, then the set $S^*$ allocated by the mechanism is such that: \begin{displaymath} - OPT(V, \mathcal{N}, B) \leq - C_\text{max}\cdot V(S^*) + 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} - + We assume that on line 2 of algorithm~\ref{mechanism}, a quantity + $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L(x^*) \leq + \tilde{L}+\varepsilon$ has been computed (lemma~\ref{lemma:complexity} + states that this can be done in a 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^*) \geq + V(i^*) \geq \frac{1}{C}L(x^*)-\frac{\varepsilon}{C} \geq \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B) \end{displaymath} @@ -270,45 +303,57 @@ Hence, the total payment is bounded by: \end{displaymath} Hence: - \begin{displaymath} - V(i^*) \geq \frac{1}{C+1} OPT(V,\mathcal{N}, B) - \end{displaymath} + \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}: \begin{align*} - V(i^*) & \leq \frac{1}{C}L(x^*) \leq \frac{1}{C} - \big(4 OPT(V,\mathcal{N}, B) + 2 V(i^*)\big)\\ + V(i^*) & \leq \frac{1}{C}L(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) - + V(i^*)\right) + + 2 V(i^*)\right) + \frac{\varepsilon}{C} \end{align*} Thus: \begin{align*} - V(i^*) \leq \frac{12e}{C(e-1)- 10e + 2} V(S_G) + 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: - \begin{displaymath} + \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)\qed - \end{displaymath} -\end{proof} - -The optimal value for $C$ is: -\begin{displaymath} - C^* = \argmin_C C_{\textrm{max}} -\end{displaymath} + (e-1) -10e +2}\right) V(S_G)\\ + +\frac{2e\varepsilon}{C(e-1)- 10e + 2} + \end{multline} -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 proof of the previous lemma. Computing this solution, -gives the result of the theorem. + Looking at \eqref{eq:bound1} and \eqref{eq:bound2}, we see that the optimal + value for $C$ is: + \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} -\subsection{An approximation ratio for $L_\mathcal{N}$}\label{sec:relaxation} + 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} +\subsection{Proof of lemma \ref{lemma:relaxation}}\label{sec:relaxation} Since $L_\mathcal{N}$ is a relaxation of the value function $V$, we have: \begin{displaymath} @@ -552,14 +597,6 @@ i\leq |\mathcal{N}|} \lambda_i c_i \leq B$. \end{align*} \end{proof} -\begin{lemma}\label{lemma:relaxation} - We have: - \begin{displaymath} - OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B) - + 2\max_{i\in\mathcal{N}}V(i) - \end{displaymath} -\end{lemma} - \begin{proof} Let us consider a feasible point $\lambda^*\in[0,1]^{|\mathcal{N}|}$ such that $L_\mathcal{N}(\lambda^*) = OPT(L_\mathcal{N}, B)$. By applying lemma~\ref{lemma:relaxation-ratio} |