minor edits

3 files changed, 8 insertions, 10 deletions

diff --git a/appendix.tex b/appendix.tex
index 6be1a85..904bd45 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -8,7 +8,7 @@ function, similarly to their real counterparts. With this definition, matrix
 inversion is decreasing and convex over symmetric positive definite
 matrices (see Example 3.48 p. 110 in \cite{boyd2004convex}).
 
-The positivity of $V(S)$ follows from the fact that $X_S^TX_S$ is positive semi-definite and, as such $I_d+X_S^TX_S\succeq I_d$, so all its eigenvalues are larger or equal to one, and they are all one if and only if $S=\emptyset$. The marginal contribution of item $i\in\mathcal{N}$ to set
+Recall that the determinant of a matrix equals the product of its eigenvalues. The positivity of $V(S)$ follows from the fact that $X_S^TX_S$ is positive semi-definite and, as such $I_d+X_S^TX_S\succeq I_d$, so all its eigenvalues are larger than or equal to one, and they are all one if $S=\emptyset$. The marginal contribution of item $i\in\mathcal{N}$ to set
     $S\subseteq \mathcal{N}$ can be written as 
 \begin{align}
 V(S\cup \{i\}) - V(S)& =   \frac{1}{2}\log\det(I_d 
@@ -23,13 +23,13 @@ Sylvester's determinant identity~\cite{sylvester}. Monotonicity therefore follow
 \begin{gather}
         \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}. \label{eq:inverse}
 \end{gather}
-and submodularity also follows. \qed
+and submodularity also follows, as a function is submodular if and only if the marginal contributions are non-increasing in $S$. \qed
 
 
 \section{Proofs of Statements in Section~\ref{sec:concave}}
 \subsection{Proof of Lemma~\ref{lemma:relaxation-ratio}}\label{proofofrelaxation-ratio}
 %\begin{proof}
-    The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}}(\lambda)$ follows by the concavity of the $\log\det$ function and Jensen's inequality.
+    The bound $F(\lambda)\leq L(\lambda)$ follows by the concavity of the $\log\det$ function and Jensen's inequality.
     To show the lower bound, 
     we first prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i
     F(\lambda)/\partial_i L(\lambda)$, where we use
@@ -411,17 +411,15 @@ In particular, $|L^*_c - L^*_{c,\alpha}| \leq \alpha n^2$.
         = \frac{1}{\max_{i\in\bar{M}} c_i}
     \end{equation}
     where the last inequality uses Lemma~\ref{lemma:derivative-bounds}.
-
     Combining \eqref{local-2}, \eqref{local-3} and \eqref{local-4}, we get that:
     \begin{displaymath}
         \sum_{i\in M}\mu_i^* \leq |M|\xi^*B \leq n\xi^*B\leq \frac{nB}{\max_{i\in\bar{M}} c_i} \leq n^2
     \end{displaymath}
-    
     This implies that:
     \begin{displaymath}
         \T{\mathbf{1}}\mu^* = \sum_{i=1}^n \mu^*_i = \sum_{i\in M}\mu_i^*\leq n^2
     \end{displaymath}
-    which in addition to \eqref{eq:local-1} proves the lemma.
+    which along with \eqref{eq:local-1} proves the lemma.
 \end{proof} 
 
 \begin{lemma}\label{lemma:monotonicity}
diff --git a/approximation.tex b/approximation.tex
index b1d3453..5e5ee11 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -115,7 +115,7 @@ For any $\varepsilon>0$, the barrier method computes  an
 approximation $\hat{L}^*_c$ that is $\varepsilon$-accurate, \emph{i.e.}, it satisfies $|\hat L^*_c- L^*_c|\leq \varepsilon$, in time $O\left(poly(n,d,\log\log\varepsilon^{-1})\right)$. The same guarantees apply when maximizing $L$ subject to an arbitrary set of $O(n)$ linear constraints.
 \end{lemma}
 
- Clearly, the optimal value $L^*_c$ of \eqref{eq:primal} is monotone in $c$. Formally, for any two $c,c'\in \reals_+^n$ s.t.~$c\leq c'$ coordinate-wise, $\dom_{c'}\subseteq \dom_c$ and thus $L^*_c\geq L^*_{c'}$. Hence, the map $c\mapsto L^*_c$ is non-increasing. Unfortunately, the same is not true for the output $\hat{L}_c^*$ of the barrier method: there is no guarantee that the $\epsilon$-accurate approximation $\hat{L}^*_c$ exhibits any kind of monotonicity.
+ Clearly, the optimal value $L^*_c$ of \eqref{eq:primal} is monotone in $c$: formally, for any two $c,c'\in \reals_+^n$ s.t.~$c\leq c'$ coordinate-wise, $\dom_{c'}\subseteq \dom_c$ and thus $L^*_c\geq L^*_{c'}$. Hence, the map $c\mapsto L^*_c$ is non-increasing. Unfortunately, the same is not true for the output $\hat{L}_c^*$ of the barrier method: there is no guarantee that the $\epsilon$-accurate approximation $\hat{L}^*_c$ exhibits any kind of monotonicity.
 
 Nevertheless, we prove that it is possible to use the barrier method to construct an approximation of $L^*_{c}$ that is ``almost'' monotone. More specifically, given $\delta>0$,  we say that $f:\reals^n\to\reals$ is
 \emph{$\delta$-decreasing}  if
diff --git a/main.tex b/main.tex
index b6031cb..251680d 100644
--- a/main.tex
+++ b/main.tex
@@ -1,13 +1,13 @@
 \label{sec:main}
 
-In this section we use the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} to design a mechanism for \SEDP. The construction follows a methodology employed by \citeN{chen} and \citeN{singer-influence} to construct deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. We briefly outline this below.
+In this section we use the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} to design a mechanism for \SEDP. The construction follows a methodology proposed in \cite{singer-mechanisms} and employed by \citeN{chen} and \citeN{singer-influence} to construct deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. We briefly outline this below (see also Algorithm~\ref{mechanism} in Appendix~\ref{sec:proofofmainthm} for a detailed description).
 
 
 %In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive compatibility. Indeed, \citeN{singer-influence} notes that this allocation function is not monotone, which implies by Myerson's theorem (Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful.
 
-Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set constructed greedily, by selecting elements of maximum marginal value per cost. The general framework used by \citeN{chen}  and by \citeN{singer-influence} for the \textsc{Knapsack}   and \textsc{Coverage} value functions contructs an allocation as follows. First, a polynomial-time, monotone relaxation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this relaxation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the mechanism constructs an allocation $S_G$ greedily; otherwise, the only item allocated is the singleton $\{i^*\}$.
+Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set constructed greedily, by selecting elements of maximum marginal value per cost. The general framework used by \citeN{chen}  and by \citeN{singer-influence} for the \textsc{Knapsack}   and \textsc{Coverage} value functions contructs an allocation as follows. First, a polynomial-time, monotone approximation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this approximation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the mechanism constructs an allocation $S_G$ greedily; otherwise, the only item allocated is the singleton $\{i^*\}$.  Provided that the approximation used is within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, this allocation combined with \emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below), the mechanism can be shown to be truthful using Myerson's Theorem~\cite{myerson}. 
 
-Provided that the relaxation used within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and thus their optimal values are monotone and can be computed exactly in weakly polynomial time. In contrast, we extend these results by showing that the convex relaxation \eqref{eq:primal}, which can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to construct a $\delta$-truthful, constant approximation mechanism. 
+The approximation algorithms used in \cite{chen,singer-influence} are LP relaxations, and thus their outputs are monotone and can be computed exactly in polynomial time. We show that the convex relaxation \eqref{eq:primal}, which can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to construct a $\delta$-truthful, constant approximation mechanism, by being incorporated in the same framework.
 
 To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in Appendix~\ref{sec:myerson}.
 %