Reimport things from the appendix to the main part for the camera-ready version

1 files changed, 18 insertions, 15 deletions

diff --git a/related.tex b/related.tex
index 19b245b..a78693b 100755
--- a/related.tex
+++ b/related.tex
@@ -5,31 +5,29 @@
 }
 \noindent\emph{Budget Feasible Mechanisms for General Submodular Functions.}
 Budget feasible mechanism design was originally proposed by  \citeN{singer-mechanisms}, who 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. 
-He 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 to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization.
+He shows that there exists a randomized, 112-approximation mechanism 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 to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms.
 
 The above approximation guarantees hold for the expected value of the
 randomized mechanism: for a given
-instance, the approximation ratio provided by the mechanism may in fact be
+instance, the approximation ratio provided by the mechanism may be
 unbounded. No deterministic, truthful, constant approximation mechanism that
 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}. 
-
+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}. 
 
 \noindent\emph{Budget Feasible Mechanism Design on Specific Problems.}
-Improved bounds \emph{and} 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 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}. 
-
+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}.}
 The  deterministic mechanisms for \textsc{Knapsack} \cite{chen} and
 \textsc{Coverage} \cite{singer-influence} follow the same general framework,
-which we also employ (see Appendix~\ref{sec:proofofmainthm}). In these two cases, the framework approximates the
-optimal solution to the underlying combinatorial problem by a well-known linear program (LP) relaxation~\cite{pipage}, which is solved exactly in polynomial time. No
+which we also employ. In these two cases, the framework approximates the
+optimal solution to the underlying combinatorial problem by a linear program (LP) relaxation~\cite{pipage}. No
 such  relaxation exists for \EDP, which is unlikely to be
 approximable through an LP due to its logarithmic objective. We develop instead a convex relaxation to \EDP;
 though, contrary to the above LP relaxations, this cannot be solved exactly, we show how to
 incorporate it in the framework of
 \cite{chen,singer-influence} to yield a $\delta$-truthful mechanism for \EDP.  
 
-
 %Our results therefore add \SEDP{} to the set of problems for which a deterministic, polynomial time, constant approximation mechanism is known.
 
 \noindent\emph{Beyond Submodular Objectives.}
@@ -41,11 +39,14 @@ Posted price, rather than direct revelation mechanisms, are also studied in \cit
 
 \noindent\emph{Monotone Approximations in Combinatorial Auctions.}
 Relaxations of combinatorial problems are prevalent
-in \emph{combinatorial auctions}, % \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}, 
-in which an auctioneer aims at maximizing a set function which is the sum of utilities of strategic bidders (\emph{i.e.}, the social welfare). As noted by \citeN{archer-approximate},
-approximations to this maximization must preserve incentive compatibility and truthfulness. Most approximation
-algorithms do not preserve these properties, hence specific relaxations, and corresponding roundings to an integral solution, must be
-constructed. \citeN{archer-approximate} propose a randomized rounding of the LP relaxation of the \textsc{SetPacking} problem, yielding a mechanism
+in \emph{combinatorial auctions}, 
+in which an auctioneer aims at maximizing the social welfare..e.}. As noted by \citeN{archer-approximate},
+approximations to this maximization must preserve incentive compatibility. Most approximation
+algorithms do not preserve this property, hence specific relaxations, and corresponding roundings to an integral solution, must be
+constructed \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}. Because of the specificity of our relaxation, and because we seek a determinist mechanism and $\delta$-truthfulness, not truthfulness-in-expectation, none of the techniques present in these works apply to our setting.
+
+
+\junk{\citeN{archer-approximate} propose a randomized rounding of the LP relaxation of the \textsc{SetPacking} problem, yielding a mechanism
 which is \emph{truthful-in-expectation}. %and in high probability. 
 \citeN{lavi-truthful} construct randomized
 truthful-in-expectation mechanisms for several combinatorial auctions, improving the approximation
@@ -57,7 +58,9 @@ the bidders' utilities are matroid rank sum functions (applied earlier to the \t
 on solving a convex optimization problem which can only be solved approximately. As in \cite{lavi-truthful}, they also treat the fractional solution as a distribution over which they sample integral solutions. The authors ensure that a solver is applied to a
 ``well-conditioned'' problem,  which resembles the technical challenge we face in
 Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $\delta$-truthfulness, not truthfulness-in-expectation. In addition, our objective is not a matroid rank sum function. As such, both the methodology for dealing with problems that are not ``well-conditioned''  as well as the approximation guarantees of the convex relaxation  in \cite{dughmi2011convex} do not readily extend to \EDP.
-\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.
+\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.
 
 \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.