Ultimate changes before submission

2 files changed, 6 insertions, 1 deletions

diff --git a/approximation.tex b/approximation.tex
index 2162f14..3a4376b 100755
--- a/approximation.tex
+++ b/approximation.tex
@@ -136,7 +136,7 @@ Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbed problem:
 \end{split}
 \end{align}
 
-The restricted set $\dom_{c,\alpha}$ ensures that the partial derivatives of the optimal solution to $P_{c,\alpha}$ with respect to the costs are bounded from below. This implies that an approximate solution to $P_{c,\alpha}$ given by the barrier method is $\delta$-decreasing with respect to the costs. On the other hand, by taking $\alpha$ small enough, we ensure that the approximate solution to $P_{c,\alpha}$ is still an $\epsilon$-accurate approximation of $L_c^*$. This methodology is summarized in the following proposition whose proof can be found in \cite{arxiv}.
+Restricting the feasible set to $\dom_{c,\alpha}$ ensures that the gradient of the optimal solution with respect to $c$ is bounded from below. This implies that an approximate solution to $P_{c,\alpha}$ given by the barrier method is $\delta$-decreasing with respect to the costs. On the other hand, by taking $\alpha$ small enough, we ensure that the approximate solution to $P_{c,\alpha}$ is still an $\epsilon$-accurate approximation of $L_c^*$. This methodology is summarized in the following proposition, whose proof can be found in \cite{arxiv}.
 
 \begin{proposition}\label{prop:monotonicity}
     For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$, using the barrier
diff --git a/related.tex b/related.tex
index 4c17d1f..60bc295 100755
--- a/related.tex
+++ b/related.tex
@@ -13,6 +13,8 @@ runs in polynomial time is presently known for submodular maximization.
 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 \EDP, 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}. 
 
+\vspace{0.5\baselineskip}
+
 \noindent\emph{Specific Problems.}
 Improved uper and lower bounds \emph{and} deterministic polynomial mechanisms are known for specific submodular objectives \cite{singer-mechanisms, chen, singer-influence}.
 \junk{For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer 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}.}
@@ -35,6 +37,8 @@ a truthful, $O(\log^3 n)$-approximate mechanism
 \cite{bei2012budget}. Moreover, in a Bayesian setup, assuming a prior distribution among the agent's costs, there exists a truthful mechanism with a 768/512-approximation ratio \cite{bei2012budget}. %(in terms of expectations)
 Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}.
 
+\vspace{0.5\baselineskip}
+
 \noindent\emph{Monotone Approximations in Combinatorial Auctions.}
 Relaxations of combinatorial problems are prevalent
 in \emph{combinatorial auctions}, 
@@ -59,6 +63,7 @@ Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $
 \citeN{briest-approximation} construct monotone FPTAS for problems that can be approximated through rounding techniques, which in turn can be used to construct truthful, deterministic, constant-approximation  mechanisms for corresponding  combinatorial auctions.}
 
 %\EDP{} is not readily approximable through such rounding techniques; as such, we rely on a relaxation to approximate it.
+\vspace{0.5\baselineskip}
 
 \noindent\emph{$\delta$-Truthfulness and Differential Privacy.}
 The notion of $\delta$-truthfulness has attracted considerable attention recently in the context of differential privacy (see, \emph{e.g.}, the survey by \citeN{pai2013privacy}).  \citeN{mcsherrytalwar} were the first to observe that any $\epsilon$-differentially private mechanism must also be $\delta$-truthful in expectation, for $\delta=2\epsilon$. This property was used to construct $\delta$-truthful (in expectation) mechanisms for a digital goods auction~\cite{mcsherrytalwar} and for $\alpha$-approximate equilibrium selection \cite{kearns2012}. \citeN{approximatemechanismdesign} propose a framework for converting a differentially private mechanism to a truthful-in-expectation mechanism by randomly selecting between a differentially private mechanism with good approximation guarantees, and a truthful mechanism. They apply their framework to the \textsc{FacilityLocation} problem. We depart from the above works in seeking a deterministic mechanism for \EDP, and using a stronger notion of $\delta$-truthfulness.