Statement of the theorem including the complexity in terms of epsilon. The proof has

been completed and adapated accordingly.

1 files changed, 95 insertions, 58 deletions

diff --git a/main.tex b/main.tex
index f7b17f4..048552e 100644
--- a/main.tex
+++ b/main.tex
@@ -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}