From d32f92b8f4a4e373b4ff82b3c64d3a69c5cf9c68 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 7 Jul 2013 17:33:12 -0700
Subject: conclusions

---
 related.tex | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'related.tex')

diff --git a/related.tex b/related.tex
index 91b25c5..6cf059f 100644
--- a/related.tex
+++ b/related.tex
@@ -62,11 +62,11 @@ on solving a convex optimization problem which can only be solved approximately.
 ``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.
+\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.
 
 \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.
+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.
 
 
 \begin{comment}
-- 
cgit v1.2.3-70-g09d2

