related

1 files changed, 11 insertions, 5 deletions

diff --git a/related.tex b/related.tex
index f929c75..91b25c5 100644
--- a/related.tex
+++ b/related.tex
@@ -41,7 +41,7 @@ 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}.
 
-\paragraph{Relaxations in Mechanism Design}
+\paragraph{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},
@@ -58,10 +58,16 @@ Beyond LP relaxations,
 \citeN{dughmi2011convex} propose
 truthful-in-expectation mechanisms for combinatorial auctions in which
 the bidders' utilities are matroid rank sum functions (applied earlier to the \textsc{CombinatorialPublicProjects} problem \cite{dughmi-truthful}). As in our case, their framework relies
-on solving a convex optimization problem and ensuring that it is
-``well-conditioned'', resembling 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, so the approximation guarantees of convex relaxation  in \cite{dughmi2011convex} do not readily extend to \EDP.
-Closer to us, \citeN{briest-approximation} \ldots. However, we \ldots \note{NEEDS TO BE FIXED!}
+on solving a convex optimization problem which can only be solved approximately. 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 monote 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.
+
+\paragraph{$\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, an a truthful mechanism, and apply it to a mechanism for the facility location problem. We depart from the above works in seeking a deterministic mechanism for \EDP, and using a stronger notion of $\delta$-truthfulness.
+
 
 \begin{comment}
 \paragraph{Data Markets}