Unifying pass over the whole paper

8 files changed, 271 insertions, 211 deletions

diff --git a/appendix.tex b/appendix.tex
index 53bc328..2c83e04 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -1,12 +1,12 @@
 \begin{lemma}\label{lemma:monotone}
-Our mechanism for \EDP{} is monotone and budget feasible.
+Our mechanism for \EDP{} is $\delta$-monotone and budget feasible.
 \end{lemma}
 \begin{proof}
     Consider an agent $i$ with cost $c_i$ that is
     selected by the mechanism, and suppose that she reports
-    a cost $c_i'\leq c_i$ while all  other costs stay the same.
+    a cost $c_i'\leq c_i-\delta$ while all  other costs stay the same.
     Suppose that when $i$ reports $c_i$, $OPT'_{-i^*} \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$.
-     By reporting a cost $c_i'\leq c_i$, $i$ may be selected at an earlier iteration of the greedy algorithm.
+     By reporting cost $c_i'$, $i$ may be selected at an earlier iteration of the greedy algorithm.
     %using the submodularity of $V$, we see that $i$ will satisfy the greedy
     %selection rule:
     %\begin{displaymath}
@@ -22,8 +22,9 @@ Our mechanism for \EDP{} is monotone and budget feasible.
         \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})}
          \leq \frac{B}{2}\frac{V(S_i'\cup\{i\})-V(S_i')}{V(S_i'\cup\{i\})}
     \end{align*}
-    by the monotonicity and submodularity  of $V$. Hence  $i\in S_G'$. As
-    $OPT'_{-i^*}$,  is the optimal value of \eqref{eq:primal} under relaxation $L$ when $i^*$ is excluded from $\mathcal{N}$, reducing the costs can only increase this value, so under $c'_i\leq c_i$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$.
+    by the monotonicity and submodularity  of $V$. Hence  $i\in S_G'$. By
+    $\delta$-decreasingness of
+    $OPT'_{-i^*}$, under $c'_i\leq c_i-\delta$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$.
     Suppose now that when $i$ reports $c_i$, $OPT'_{-i^*} < C V(i^*)$. Then $s_i(c_i,c_{-i})=1$ iff $i = i^*$. 
     Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor
     $OPT'_{-i^*} \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone.
diff --git a/approximation.tex b/approximation.tex
index ced53ed..926ca1d 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -1,9 +1,8 @@
-Even though \EDP{} is NP-hard, designing a mechanism for this problem will
-involve being able to find an approximation $\tilde{L}^*(c)$ of $OPT$
-monotonous with respect to coordinate-wise changes of the cost: if $c$ and $c'$
-are two cost vectors such that $c'=(c_i', c_{-i})$ with $c_i' \leq c_i$, then
-we want $\tilde{L}(c')\geq \tilde{L}(c)$. Furthermore, we seek an approximation
-that can be computed in polynomial time.
+\EDP{} is NP-hard, but designing a mechanism for this problem will involve
+being able to find an approximation $\tilde{L}^*(c)$ of $OPT$ with the
+following three properties: first, it must be non-decreasing along
+coordinate-axis, second it must have a constant approximation ratio to $OPT$
+and finally, it must be computable in polynomial time.
 
 This approximation will be obtained by introducing a concave optimization
 problem with a constant approximation ratio to \EDP{}
@@ -15,125 +14,58 @@ object of (Section~\ref{sec:monotonicity}).
 
 \subsection{A concave relaxation of \EDP}\label{sec:concave}
 
-Let us introduce a new function $L$:
-\begin{equation}\label{eq:our-relaxation}
-\forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq
-\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right),
-\end{equation}
-
-This function is a relaxation of the value function $V$ defined in
-\eqref{modified} in the following sense: $L(\id_S) = V(S)$ for all
-$S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$.
-
-The optimization program \eqref{eq:non-strategic} extends naturally to such
-a relaxation. We define:
-\begin{equation}\tag{$P_c$}\label{eq:primal}
-    L^*_c \defeq \max_{\lambda\in[0, 1]^{n}}
-    \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
-    \leq B\right\}
-\end{equation}
-
-\begin{proposition}\label{prop:relaxation}
-     $   L^*(c) \leq 2 OPT
-        + 2\max_{i\in\mathcal{N}}V(i)$.
-\end{proposition}
+A classical way of relaxing combinatorial optimization problems is 
+\emph{relaxing by expectation}, using the so-called \emph{multi-linear}
+extension of the objective function $V$.
 
-The proof of this proposition follows the \emph{pipage rounding} framework of
-\citeN{pipage}.
-
-This framework uses the \emph{multi-linear} extension $F$ of the submodular
-function $V$. Let $P_\mathcal{N}^\lambda(S)$ be the probability of choosing the
+Let $P_\mathcal{N}^\lambda(S)$ be the probability of choosing the
 set $S$ if we select each element $i$ in $\mathcal{N}$ independently with
 probability $\lambda_i$:
 \begin{displaymath}
     P_\mathcal{N}^\lambda(S) \defeq \prod_{i\in S} \lambda_i
     \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i).
 \end{displaymath}
-Then, the \emph{multi-linear} extension $F$ is defined by:
-\begin{displaymath}
+Then, the \emph{multi-linear} extension $F$ of $V$ is defined as the
+expectation of $V$ under the probability distribution $P_\mathcal{N}^\lambda$:
+\begin{equation}\label{eq:multi-linear}
     F(\lambda) 
     \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big]
     = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)
-\end{displaymath}
+\end{equation}
 
-For \EDP{}  the multi-linear extension can be written:
-\begin{equation}\label{eq:multi-linear-logdet}
-    F(\lambda) = \mathbb{E}_{S\sim
-    P_\mathcal{N}^\lambda}\bigg[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big].
+This function is an extension of $V$ in the following sense: $F(\id_S) = V(S)$ for all
+$S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$.
+
+\citeN{pipage} have shown how to use this extension to obtain approximation
+guarantees for an interesting class of optimization problems through the
+\emph{pipage rounding} framework, which has been successfully applied
+in \citeN{chen, singer-influence}. 
+
+However, for the specific function $V$ defined in \eqref{modified}, the
+multi-linear extension cannot be computed (and \emph{a fortiori} maximized) in
+polynomial time. Hence, we introduce a new function $L$:
+\begin{equation}\label{eq:our-relaxation}
+\forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq
+\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right),
 \end{equation}
 Note that the relaxation $L$ that we introduced in \eqref{eq:our-relaxation},
-follows naturally from the \emph{multi-linear} relaxation by swapping the
-expectation and the $\log\det$ in \eqref{eq:multi-linear-logdet}:
+follows naturally from the \emph{multi-linear} extension by swapping the
+expectation and $V$ in \eqref{eq:multi-linear}:
 \begin{displaymath}
     L(\lambda) = \log\det\left(\mathbb{E}_{S\sim
     P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right).
 \end{displaymath}
 
-The proof proceeds as follows:
-\begin{itemize}
-\item First, we prove that $F$ admits the following rounding property: let
-$\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one
-fractional component of $\lambda$ for another until one of them becomes
-integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and
-for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point
-$\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n
-\lambda_i c_i \leq B$.  This rounding property is referred to in the literature
-as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or
-$\varepsilon$-convexity by \citeN{pipage}. This is stated and proven in
-Lemma~\ref{lemma:rounding} and allows us to bound $F$ in terms of $OPT$.
-\item Next, we prove the central result of bounding $L$  appropriately in terms
-of the multi-linear relaxation $F$ (Lemma \ref{lemma:relaxation-ratio}).
-\item Finally, we conclude the proof of Proposition~\ref{prop:relaxation} by
-combining Lemma~\ref{lemma:rounding} and Lemma~\ref{lemma:relaxation-ratio}.
-\end{itemize}
-
-\begin{lemma}[Rounding]\label{lemma:rounding}
-    For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible
-    $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is
-    fractional %, that is, lies in $(0,1)$ and:
-     and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
-\end{lemma}
-\begin{proof}
-    We give a rounding procedure which, given a feasible $\lambda$ with at least
-    two fractional components, returns some feasible $\lambda'$ with one less fractional
-    component such that $F(\lambda) \leq F(\lambda')$.
+The optimization program \eqref{eq:non-strategic} extends naturally to such
+a relaxation. We define:
+\begin{equation}\tag{$P_c$}\label{eq:primal}
+    L^*_c \defeq \max_{\lambda\in[0, 1]^{n}}
+    \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
+    \leq B\right\}
+\end{equation}
 
-    Applying this procedure recursively yields the lemma's result.
-    Let us consider such a feasible $\lambda$. Let $i$ and $j$ be two
-    fractional components of $\lambda$ and let us define the following
-    function:
-    \begin{displaymath}
-        F_\lambda(\varepsilon) = F(\lambda_\varepsilon)
-        \quad\textrm{where} \quad
-        \lambda_\varepsilon = \lambda + \varepsilon\left(e_i-\frac{c_i}{c_j}e_j\right)
-    \end{displaymath}
-    It is easy to see that if $\lambda$ is feasible, then:
-    \begin{equation}\label{eq:convex-interval}
-        \forall\varepsilon\in\Big[\max\Big(-\lambda_i,(\lambda_j-1)\frac{c_j}{c_i}\Big), \min\Big(1-\lambda_i, \lambda_j
-        \frac{c_j}{c_i}\Big)\Big],\;
-            \lambda_\varepsilon\;\;\textrm{is feasible}
-    \end{equation}
-    Furthermore, the function $F_\lambda$ is convex; indeed:
-    \begin{align*}
-        F_\lambda(\varepsilon)
-        & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[
-        (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\
-        & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})
-         + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\
-         & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big]
-    \end{align*}
-    Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is:
-    \begin{displaymath}
-        \frac{c_i}{c_j}\mathbb{E}_{S'\sim
-        P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[
-            V(S'\cup\{i\})+V(S'\cup\{i\})\\
-        -V(S'\cup\{i,j\})-V(S')\Big]
-    \end{displaymath}
-    which is positive by submodularity of $V$. Hence, the maximum of
-    $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is
-    attained at one of its limit, at which either the $i$-th or $j$-th component of
-    $\lambda_\varepsilon$ becomes integral.
-\end{proof}
+The key property of the relaxation $L$, which is our main technical result, is
+that it has constant approximation ratios to the multi-linear extension $F$.
 
 \begin{lemma}\label{lemma:relaxation-ratio}
  %   The following inequality holds:
@@ -306,11 +238,77 @@ Having bound the ratio between the partial derivatives, we now bound the ratio $
     function $V$. Hence, the ratio is equal to 1 on the vertices.
 \end{proof}
 
-To conclude the proof of Proposition~\ref{prop:relaxation}, let us consider
-a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*) = L^*_c$. By
-applying Lemma~\ref{lemma:relaxation-ratio} and Lemma~\ref{lemma:rounding} we
-get a feasible point $\bar{\lambda}$ with at most one fractional component such
-that
+We now prove that $F$ admits the following exchange property: let
+$\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one
+fractional component of $\lambda$ for another until one of them becomes
+integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and
+for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point
+$\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n
+\lambda_i c_i \leq B$.  This rounding property is referred to in the literature
+as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or
+$\varepsilon$-convexity by \citeN{pipage}.
+
+\begin{lemma}[Rounding]\label{lemma:rounding}
+    For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible
+    $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is
+    fractional %, that is, lies in $(0,1)$ and:
+     and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
+\end{lemma}
+\begin{proof}
+    We give a rounding procedure which, given a feasible $\lambda$ with at least
+    two fractional components, returns some feasible $\lambda'$ with one less fractional
+    component such that $F(\lambda) \leq F(\lambda')$.
+
+    Applying this procedure recursively yields the lemma's result.
+    Let us consider such a feasible $\lambda$. Let $i$ and $j$ be two
+    fractional components of $\lambda$ and let us define the following
+    function:
+    \begin{displaymath}
+        F_\lambda(\varepsilon) = F(\lambda_\varepsilon)
+        \quad\textrm{where} \quad
+        \lambda_\varepsilon = \lambda + \varepsilon\left(e_i-\frac{c_i}{c_j}e_j\right)
+    \end{displaymath}
+    It is easy to see that if $\lambda$ is feasible, then:
+    \begin{equation}\label{eq:convex-interval}
+        \forall\varepsilon\in\Big[\max\Big(-\lambda_i,(\lambda_j-1)\frac{c_j}{c_i}\Big), \min\Big(1-\lambda_i, \lambda_j
+        \frac{c_j}{c_i}\Big)\Big],\;
+            \lambda_\varepsilon\;\;\textrm{is feasible}
+    \end{equation}
+    Furthermore, the function $F_\lambda$ is convex; indeed:
+    \begin{align*}
+        F_\lambda(\varepsilon)
+        & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[
+        (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\
+        & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})
+         + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\
+         & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big]
+    \end{align*}
+    Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is:
+    \begin{displaymath}
+        \frac{c_i}{c_j}\mathbb{E}_{S'\sim
+        P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[
+            V(S'\cup\{i\})+V(S'\cup\{i\})\\
+        -V(S'\cup\{i,j\})-V(S')\Big]
+    \end{displaymath}
+    which is positive by submodularity of $V$. Hence, the maximum of
+    $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is
+    attained at one of its limit, at which either the $i$-th or $j$-th component of
+    $\lambda_\varepsilon$ becomes integral.
+\end{proof}
+
+Using Lemma~\ref{lemma:rounding}, we can relate the multi-linear extension to
+$OPT$, and Lemma~\ref{lemma:relaxation-ratio} relates our relaxation $L$ to the
+multi-linear extension. Putting these together gives us the following result:
+
+\begin{proposition}\label{prop:relaxation}
+$L^*_c \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$.
+\end{proposition}
+
+\begin{proof}
+Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that
+$L(\lambda^*) = L^*_c$. By applying Lemma~\ref{lemma:relaxation-ratio} and
+Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most
+one fractional component such that
 \begin{equation}\label{eq:e1}
     L(\lambda^*) \leq 2 F(\bar{\lambda}).
 \end{equation}
@@ -329,43 +327,81 @@ that
     \begin{equation}\label{eq:e2}
         F(\bar{\lambda}) \leq  OPT + \max_{i\in\mathcal{N}} V(i).
     \end{equation}
-    Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma. \hspace*{\stretch{1}}\qed
+    Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma.
+\end{proof}
 
-\subsection{A monotonous Newton's estimator}\label{sec:monotonicity}
+\subsection{A monotonous estimator}\label{sec:monotonicity}
 
-\textbf{TODO} Explain that we only get approximate monotonicity, but even
-that is not immediate since the variation induced by a change of cost on
-coordinate $i$ depends on the allocation at this coordinate which can be
-arbitrarily small.
+The $\log\det$ function is concave and self-concordant (see
+\cite{boyd2004convex}), in this case, the analysis of the barrier method in
+in \cite{boyd2004convex} (Section 11.5.5) can be summarized in the following
+lemma:
 
-For the ease of presentation, we normalize the costs by dividing them by the
-budget $B$ so that the budget constraint in \eqref{eq:primal} now reads
-$\T{c}\lambda\leq 1$.
+\begin{lemma}\label{lemma:barrier}
+For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate
+approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$.
+\end{lemma}
 
-\begin{proposition}\label{prop:monotonicity}
-    Let $\delta\in(0,1]$. For any $\varepsilon\in(0,1]$, there exists
-    an algorithm which computes an approximate solution $\tilde{L}^*_c$ to
-    \eqref{eq:primal} such that:
-    \begin{enumerate}
-        \item $|\tilde{L}^*_c - L^*_c| \leq \varepsilon$
-        \item for all $c' = (c_i', c_{-i})$ with $c_i'\leq c_i-\delta$, $\tilde{L}^*_c \leq \tilde{L}^*_{c'}$
-        \item the routine's running time is $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
-    \end{enumerate}
-\end{proposition}
+Note however that even though $L^*_c$ is non-decreasing along coordinate axis
+(if one of the cost decreases, then the feasible set of \eqref{eq:primal}
+increases), this will not necessarily be the case for an $\varepsilon$-accurate
+approximation of $L^*_c$ and Lemma~\ref{lemma:barrier} in itself is not
+sufficient to provide an approximation satisfying the
+properties requested at the beginning of Section~\ref{sec:approximation}.
 
-We consider a perturbation of \eqref{eq:primal} by introducing:
+The estimator we will construct in this section will have a slightly weaker
+form of coordinate-wise monotonicity: \emph{$\delta$-monotonicity}.
+
+\begin{definition}
+Let $f$ be a function from $\reals^n$ to $\reals$, we say that $f$ is
+\emph{$\delta$-increasing} iff:
+\begin{displaymath}
+    \forall x\in\reals^n,\;
+    \forall \mu\geq\delta,\;
+    \forall i\in\{1,\ldots,n\},\;
+    f(x+\mu e_i)\geq f(x)
+\end{displaymath}
+where $e_i$ is the $i$-th basis vector of $\reals^n$. We define
+\emph{$\delta$-decreasing} functions similarly.
+\end{definition}
+
+For the ease of presentation, we normalize the costs by dividing them by the
+budget $B$ so that the budget constraint in \eqref{eq:primal} now reads
+$\T{c}\lambda\leq 1$.  We consider a perturbation of \eqref{eq:primal} by
+introducing:
 \begin{equation}\tag{$P_{c, \alpha}$}\label{eq:perturbed-primal}
     L^*_c(\alpha) \defeq \max_{\lambda\in[\alpha, 1]^{n}}
     \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
-    \leq B\right\}
+    \leq 1\right\}
 \end{equation}
 Note that we have $L^*_c = L^*_c(0)$.  We will also assume that
 $\alpha<\frac{1}{n}$ so that \eqref{eq:perturbed-primal} has at least one
 feasible point: $(\frac{1}{n},\ldots,\frac{1}{n})$.
 
-Having introduced this perturbed problem, we show that its optimal value is
-close to the optimal value of \eqref{eq:primal} (Lemma~\ref{lemma:proximity})
-while being well-behaved with respect to changes of the cost
+The $\delta$-decreasing approximation of $L^*_c$ is obtained by computing an
+approximate solution of \eqref{eq:perturbed-primal}.
+
+\begin{algorithm}[h]
+    \caption{}\label{alg:monotone}
+    \begin{algorithmic}[1]
+        \State $\alpha \gets \varepsilon(\delta+n^2)^{-1} $ 
+
+        \State Compute a $\frac{1}{2^{n+1}}\alpha\delta b$-accurate approximation of
+        $L^*_c(\alpha)$ using the barrier method
+    \end{algorithmic}
+\end{algorithm}
+
+\begin{proposition}\label{prop:monotonicity}
+    For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$,
+    Algorithm~\ref{alg:monotone} computes a $\delta$-decreasing,
+    $\varepsilon$-accurate approximation of $L^*_c$. The running time of the
+    algorithm is $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
+\end{proposition}
+
+
+We show that the optimal value of \eqref{eq:perturbed-primal} is close to the
+optimal value of \eqref{eq:primal} (Lemma~\ref{lemma:proximity}) while being
+well-behaved with respect to changes of the cost
 (Lemma~\ref{lemma:monotonicity}). These lemmas together imply
 Proposition~\ref{prop:monotonicity}.
 
@@ -560,20 +596,18 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$.
 
 \subsubsection*{End of the proof of Proposition~\ref{prop:monotonicity}}
 
-Let $\varepsilon$ in $(0, 1]$. The routine works as follows: set $\alpha\defeq
-\varepsilon(\delta + n^2)^{-1}$ and return an approximation $\tilde{L}^*_c$ of
-$L^*_c(\alpha)$ with an accuracy $\frac{1}{2^{n+1}}\alpha\delta b$ computed by
-a standard convex optimization algorithm. Note that this choice of $\alpha$
-implies $\alpha<\frac{1}{n}$ as required.
-
+Let $\tilde{L}^*_c$ be the approximation computed by
+Algorithm~\ref{alg:monotone}.
 \begin{enumerate}
     \item using Lemma~\ref{lemma:proximity}:
 \begin{displaymath}
         |\tilde{L}^*_c - L^*_c| \leq |\tilde{L}^*_c - L^*_c(\alpha)| + |L^*_c(\alpha) - L^*_c|
         \leq \alpha\delta + \alpha n^2 = \varepsilon
 \end{displaymath}
+which proves the $\varepsilon$-accuracy.
 
-\item let $c' = (c_i', c_{-i})$ with $c_i'\leq c_i-\delta$, then:
+\item for the $\delta$-decreasingness, let $c' = (c_i', c_{-i})$ with $c_i'\leq
+    c_i-\delta$, then:
 \begin{displaymath}
     \tilde{L}^*_{c'} \geq L^*_{c'} - \frac{\alpha\delta b}{2^{n+1}} 
                      \geq L^*_c + \frac{\alpha\delta b}{2^{n+1}}
@@ -587,14 +621,9 @@ the inner inequality follows from Lemma~\ref{lemma:monotonicity}.
     A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2)}
 \end{displaymath}
 
-The function $L$ 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
-finding the maximum of $L$ to any precision $A$ can be done in
-$O(\log\log A^{-1})$ iterations. Note that:
+Note that:
 \begin{displaymath}
     \log\log A^{-1} = O\bigg(\log\log\frac{1}{\varepsilon\delta b} + \log n\bigg)
 \end{displaymath}
-Furthermore, each iteration of Newton's method can be done in time $O\big(poly(n,
-d)\big)$.\qed
+Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed
 \end{enumerate}
diff --git a/definitions.tex b/definitions.tex
index 281b290..a05edae 100644
--- a/definitions.tex
+++ b/definitions.tex
@@ -1,12 +1,14 @@
 \newcommand{\mutual}{\ensuremath{{I}}}
 \newcommand{\entropy}{\ensuremath{{H}}}
 \newtheorem{lemma}{Lemma}
-\newtheorem{proposition}{Proposition}
-\newtheorem{fact}{Fact}
-\newtheorem{example}{Example}
-\newtheorem{prop}{Proposition}
-\newtheorem{theorem}{Theorem}
-\newtheorem{corollary}{Corollary}
+\newtheorem{proposition}[lemma]{Proposition}
+\newtheorem{fact}[lemma]{Fact}
+\newtheorem{example}[lemma]{Example}
+\newtheorem{prop}[lemma]{Proposition}
+\newtheorem{theorem}[lemma]{Theorem}
+\newtheorem{corollary}[lemma]{Corollary}
+\theoremstyle{definition}
+\newtheorem*{definition}{Definition}
 \newcommand{\citeN}{\citet}
 %\newcommand*{\defeq}{\stackrel{\text{def}}{=}}
 \newcommand*{\defeq}{\equiv}
diff --git a/main.tex b/main.tex
index 21260e1..0e8457c 100644
--- a/main.tex
+++ b/main.tex
@@ -50,7 +50,7 @@ in the full-information case, cannot be computed in poly-time when the
 underlying problem is NP-hard (unless P=NP), as is the case for \SEDP{}.
 
 Instead, \citeN{singer-mechanisms} and \citeN{chen}
-suggest to replace $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
+suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
 following properties:
 \begin{itemize}
     \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported
@@ -61,27 +61,52 @@ following properties:
     \item $OPT'_{-i^*}$ must be computable in polynomial time.
 \end{itemize}
 
-
 One of the main technical contributions of \citeN{chen} and
-\citeN{singer-influence} is to come up with appropriate such relaxations for
-\textsc{Knapsack} and \textsc{Coverage}, respectively.
+\citeN{singer-influence} is to come up with appropriate such quantity by
+considering relaxations of \textsc{Knapsack} and \textsc{Coverage},
+respectively.
 
 \subsection{Our Approach}
 
+Using the results from Section~\ref{sec:approximation}, we come up with
+a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being
+$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as
+defined below.
+
+\begin{definition}
+Let $\mathcal{M}= (S, p)$ a mechanism, and let $s$ denote the indicator
+function of $S$ ($s_i(c) = \id_{i\in S(c)}$). We say that $\mathcal{M}$ is
+$\delta$-truthful iff:
+\begin{displaymath}
+\forall c\in\reals_+^n,\;
+\forall\mu\geq\delta,\;
+\forall i\in\{1,\ldots,n\},\;
+p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i
+\end{displaymath}
+where $e_i$ is the $i$-th basis vector of $\reals^n$.
+\end{definition}
+
+$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
+variant of Myerson's theorem.
 
-\begin{comment}
-The main challenge
-will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to
-$OPT_{-i^*}$. 
-We show this by establishing that $L$ is within a constant factor from the so-called multi-linear relaxation of  \eqref{modified}, which in turn can be related to \eqref{modified} through pipage rounding. We establish the constant factor to the multi-linear relaxation by bounding  the partial derivatives of these two functions; we obtain the latter bound by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices.
-\end{comment}
+\begin{lemma}\label{thm:myerson-variant}
+\sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
+$\delta$-truthful iff:
+(a) $S$ is $\delta$-decreasing, \emph{i.e.}, for any agent $i$ and $c_i' \leq
+c_i-\delta$, for any
+fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i,
+c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
+ agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$.
+\end{lemma}
 
 \begin{algorithm}[t]
     \caption{Mechanism for \SEDP{}}\label{mechanism}
     \begin{algorithmic}[1]
     \State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$
     \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
-    \State $OPT'_{-i^*} \gets \max_{\lambda\in[0,1]^{n}} \{L(\lambda)
+    \State $OPT'_{-i^*} \gets$ using Proposition~\ref{prop:monotonicity},
+    compute a $\varepsilon$-accurate, $\delta$-decreasing
+    approximation of $\max_{\lambda\in[0,1]^{n}} \{L(\lambda)
                                     \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$
         \Statex
         \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c}
@@ -100,7 +125,7 @@ We show this by establishing that $L$ is within a constant factor from the so-ca
 \end{algorithm}
 
 \fussy
-In summary, the resulting mechanism for \EDP{} is composed of
+Our mechanism for \EDP{} is composed of
 \begin{itemize}
 \item the allocation function presented in Algorithm~\ref{mechanism}, and 
 \item the payment function which pays each allocated agent $i$ her threshold
@@ -114,11 +139,13 @@ be found in~\cite{singer-mechanisms}.
 We can now state our main result:
 \begin{theorem}\label{thm:main}
     \sloppy
-    The allocation described in Algorithm~\ref{mechanism}, along with threshold
-    payments, is truthful, individually rational and budget feasible.
-    Furthermore, there exists an absolute constant $C$ such that, for any
-    $\varepsilon>0$, the mechanism runs in time  $O\left(\text{poly}(n, d,
-    \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
+    For any $\delta$, the allocation described in Algorithm~\ref{mechanism},
+    along with threshold payments, is $\delta$-truthful, individually rational
+    and budget feasible.  Furthermore, there exists an absolute constant $C$
+    such that, for any $\varepsilon>0$, the mechanism runs in time
+    $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
+    and returns
+    a set $S^*$ such that:
     \begin{align*}
         OPT
         & \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
@@ -129,7 +156,9 @@ We can now state our main result:
 The value of the constant $C$ is given by \eqref{eq:constant} in
 Section~\ref{sec:proofofmainthm}.
 In addition, we prove the following simple lower bound.
+
 \begin{theorem}\label{thm:lowerbound}
-There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. 
+There is no $2$-approximate, truthful, budget feasible, individually rational
+mechanism for EDP. 
 \end{theorem}
 
diff --git a/paper.tex b/paper.tex
index f0a6e93..8a8775c 100644
--- a/paper.tex
+++ b/paper.tex
@@ -1,5 +1,5 @@
-\documentclass[11pt]{article}
-\usepackage[vmargin=1.5in]{geometry}
+\documentclass[11pt,letterpaper]{article}
+\usepackage[margin=1in]{geometry}
 \usepackage[numbers]{natbib}
 \usepackage[utf8]{inputenc}
 \usepackage{amsmath,amsfonts}
@@ -10,7 +10,7 @@
 \input{definitions}
 \title{Budget Feasible Mechanisms for Experimental Design}
 \author{
-    Thibaut Horel\\École normale supérieure\\\texttt{thibaut.horel@ens.fr}
+    Thibaut Horel\\École Normale Supérieure\\\texttt{thibaut.horel@ens.fr}
     \and
     Stratis Ioannidis\\Technicolor\\\texttt{stratis.ioannidis@technicolor.com}
     \and
@@ -19,17 +19,19 @@
 
 \begin{document}
 \maketitle
+\thispagestyle{empty}
 \begin{abstract}
 \input{abstract}
 \end{abstract}
-\newpage
 
+\clearpage
+\setcounter{page}{1}
 \section{Introduction}
 \input{intro}
 
 \section{Preliminaries}\label{sec:peel}
 \input{problem}
-\section{Approximation results}
+\section{Approximation results}\label{sec:approximation}
 \input{approximation}
 \section{Mechanism for \SEDP{}}
 \input{main}
diff --git a/problem.tex b/problem.tex
index c9037b0..6bfac6b 100644
--- a/problem.tex
+++ b/problem.tex
@@ -197,7 +197,7 @@ a characterization of truthful mechanisms.
 truthful iff:
 %\begin{enumerate}
 %\item 
-(a) $f$ is \emph{monotone}, \emph{i.e.}, for any agent $i$ and $c_i' \leq c_i$, for any
+(a) $S$ is \emph{monotone}, \emph{i.e.}, for any agent $i$ and $c_i' \leq c_i$, for any
 fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i,
 c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
 %\item
diff --git a/proofs.tex b/proofs.tex
index 6169bb5..4cefc25 100644
--- a/proofs.tex
+++ b/proofs.tex
@@ -1,26 +1,25 @@
 \subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 
-We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual
-rationality follow from monotonicity and threshold payments.  Monotonicity and
-budget feasibility follow the same steps as the analysis of \citeN{chen};
- for the sake of completeness, we restate their proof in the Appendix.
+We now present the proof of Theorem~\ref{thm:main}. $\delta$-truthfulness and
+individual rationality follow from $\delta$-monotonicity and threshold
+payments. $\delta$-monotonicity and budget feasibility follow the same steps as the
+analysis of \citeN{chen}; for the sake of completeness, we restate their proof
+in the Appendix.
 
 The complexity of the mechanism is given by the following lemma.
 
 \begin{lemma}[Complexity]\label{lemma:complexity}
-    For any $\varepsilon > 0$, the complexity of the mechanism  is
-    $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$.
+    For any $\varepsilon > 0$ and any $\delta>0$, the complexity of the mechanism  is
+    $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
 \end{lemma}
 
 \begin{proof}
     The value function $V$ in \eqref{modified} can be computed in time
     $O(\text{poly}(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 found
-    to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$  of iterations of Newton's method. Each iteration  can be
-    done in time $O(\text{poly}(n, d))$. Thus, line 3 of
-    Algorithm~\ref{mechanism} can be computed in time
+
+    By Proposition~\ref{prop:monotonicity}, line 3 of Algorithm~\ref{mechanism}
+    can be computed in time
     $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. Hence the allocation
     function's complexity is as stated. 
     %Payments can be easily computed in time  $O(\text{poly}(n, d))$ as in prior work.
@@ -55,28 +54,26 @@ OPT
 \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!
 + \! \varepsilon .
 \end{equation}
-To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to
-$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume
-that on line 3 of Algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that
-$\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been
-computed (Lemma~\ref{lemma:complexity} states that this  is computed in time
-within our complexity guarantee).
+To see this, let $L^*_{-i^*}$ be the true maximum value of $L$ subject to
+$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line
+3 of Algorithm~\ref{mechanism}, we have
+$L^*_{-i^*}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{-i^*}+\varepsilon$.
 
-If the condition on line 3 of the algorithm holds, then
+If the condition on line 4 of the algorithm holds, then
 \begin{displaymath}
-    V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq
-    \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}
+    V(i^*) \geq \frac{1}{C}L^*_{-i^*}-\frac{\varepsilon}{C} \geq
+    \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}.
 \end{displaymath}
-as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$,
+Indeed, $L^*_{-i^*}\geq OPT_{-i^*}$ as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$,
 hence,
 \begin{equation}\label{eq:bound1}
     OPT\leq (1+C)V(i^*) + \varepsilon.
 \end{equation}
 
-If the condition  does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and
+If the condition  does not hold, by observing that $L^*_{-i^*}\leq L^*_c$ and
 applying Proposition~\ref{prop:relaxation}, we get
 \begin{displaymath}
-    V(i^*)  \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
+    V(i^*)\leq \frac{1}{C}L^*_{-i^*} + \frac{\varepsilon}{C}
     \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}.
 \end{displaymath}
 Applying Lemma~\ref{lemma:greedy-bound},
diff --git a/related.tex b/related.tex
index 66d0d0e..84d0762 100644
--- a/related.tex
+++ b/related.tex
@@ -3,7 +3,7 @@
 
 \junk{\subsection{Experimental Design} The classic experimental design problem, which we also briefly review in Section~\ref{sec:edprelim}, deals with  which $k$ experiments to conduct among a set of $n$ possible experiments. It is a well studied problem both in the non-Bayesian \cite{pukelsheim2006optimal,atkinson2007optimum,boyd2004convex} and Bayesian setting \cite{chaloner1995bayesian}. Beyond $D$-optimality, several other objectives are encountered in the literature  \cite{pukelsheim2006optimal}; many involve some function of the covariance matrix of the estimate of $\beta$, such as $E$-optimality (maximizing the smallest eigenvalue of the covariance of $\beta$) or $T$-optimality (maximizing the trace). Our focus on $D$-optimality is motivated by both its tractability as well as its relationship to the information gain.  %are encountered in the literature, though they do not relate to entropy as $D$-optimality. We leave the task of approaching the maximization of such objectives from a strategic point of view as an open problem.
 }
-\subsection{Budget Feasible Mechanisms for General Submodular Functions}
+\paragraph{Budget Feasible Mechanisms for General Submodular Functions}
 Budget feasible mechanism design was originally proposed by  \citeN{singer-mechanisms}. Singer considers the problem of maximizing an arbitrary submodular function subject to a budget constraint in the \emph{value query} model, \emph{i.e.} assuming an  oracle providing the  value of the submodular objective on any given set. 
  Singer shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen}  improve this result by providing a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization.
 
@@ -16,10 +16,10 @@ However, assuming access to an oracle providing the optimum in the
 full-information setup, Chen \emph{et al.},~propose a truthful, $8.34$-approximate mechanism; in cases for which the full information problem is NP-hard, as the one we consider here, this mechanism is not poly-time, unless P=NP.  Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful deterministic mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. 
 
 
-\subsection{Budget Feasible Mechanism Design on Specific Problems}
+\paragraph{Budget Feasible Mechanism Design on Specific Problems}
 Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate  mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-influence}. Our results therefore add \SEDP{} to the set of problems for which a deterministic, polynomial time, constant approximation mechanism is known.
 
-\subsection{Beyond Submodular Objectives}
+\paragraph{Beyond Submodular Objectives}
 Beyond submodular objectives, it is known that no truthful mechanism with approximation ratio smaller than $n^{1/2-\epsilon}$ exists for maximizing  fractionally subadditive functions (a class that includes submodular functions) assuming access to a value query oracle~\cite{singer-mechanisms}. Assuming access to a stronger oracle (the \emph{demand} oracle), there exists
 a truthful, $O(\log^3 n)$-approximate mechanism 
 \cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-approximate mechanism for subadditive maximization 
@@ -27,7 +27,7 @@ a truthful, $O(\log^3 n)$-approximate mechanism
 Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}.
 
 
-\subsection{Data Markets}
+\paragraph{Data Markets}
  A series of recent papers  \cite{mcsherrytalwar,approximatemechanismdesign,xiao:privacy-truthfulness,chen:privacy-truthfulness} consider the related problem of retrieving data from an  \textit{unverified} database, where strategic users may misreport their data to ensure their privacy. %\citeN{mcsherrytalwar} argue that \emph{differentially private} mechanisms offer a form of \emph{approximate truthfulness}: if users have a utility that depends on their privacy, reporting their data untruthfully can only increase their utility by a small amount.  %\citeN{xiao:privacy-truthfulness}, improving upon earlier work by~\citeN{approximatemechanismdesign}, constructs mechanisms that simultaneously achieve exact truthfulness as well as differential privacy. 
 We depart by assuming that experiment outcomes are tamper-proof and cannot be manipulated.  
 A different set of papers \cite{ghosh-roth:privacy-auction,roth-liggett,pranav} consider a setting where data cannot be misreported, but the utility of users is a function of the differential privacy guarantee an analyst provides them. We do not focus on privacy; any privacy costs in our setup are internalized in the costs $c_i$.  %Eliciting private data through a \emph{survey} \cite{roth-liggett}, whereby individuals first decide whether to participate in the survey and then report their data,