related

2 files changed, 97 insertions, 1 deletions

diff --git a/notes.bib b/notes.bib
index d6f188d..507d9ea 100644
--- a/notes.bib
+++ b/notes.bib
@@ -5,6 +5,25 @@
   publisher={Cambridge University Press}
 }
 
+@article{approximatemechanismdesign,
+  author    = {Kobbi Nissim and
+               Rann Smorodinsky and
+               Moshe Tennenholtz},
+  title     = {Approximately Optimal Mechanism Design via Differential
+               Privacy},
+  year      = {2010},
+  ee        = {http://arxiv.org/abs/1004.2888},
+}
+
+@inproceedings{mcsherrytalwar,
+  author    = {Frank McSherry and
+               Kunal Talwar},
+  title     = {Mechanism Design via Differential Privacy},
+  booktitle = {Proc. FOCS},
+  year      = {2007}
+}
+
+
 @article{vandenberghe1998determinant,
   title={Determinant maximization with linear matrix inequality constraints},
   author={Vandenberghe, L. and Boyd, S. and Wu, S.P.},
@@ -530,3 +549,71 @@
   publisher={Springer Series in Statistics}
 }
 
+
+@article{chen:privacy-truthfulness,
+  author    = {Yiling Chen and
+               Stephen Chong and
+               Ian A. Kash and
+               Tal Moran and
+               Salil P. Vadhan},
+  title     = {Truthful Mechanisms for Agents that Value Privacy},
+  journal   = {CoRR},
+  volume    = {abs/1111.5472},
+  year      = {2011},
+  ee        = {http://arxiv.org/abs/1111.5472},
+  bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+
+@inproceedings{roth-schoenebeck,
+ author = {Roth, Aaron and Schoenebeck, Grant},
+ title = {Conducting truthful surveys, cheaply},
+ booktitle = {Proceedings of the 13th ACM Conference on Electronic Commerce},
+ series = {EC '12},
+ year = {2012},
+ isbn = {978-1-4503-1415-2},
+ location = {Valencia, Spain},
+ pages = {826--843},
+ numpages = {18},
+ url = {http://doi.acm.org/10.1145/2229012.2229076},
+ doi = {10.1145/2229012.2229076},
+ acmid = {2229076},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+ keywords = {mechanism design, privacy},
+} 
+
+@inproceedings{roth-liggett,
+  author    = {Katrina Ligett and
+               Aaron Roth},
+  title     = {{Take it or Leave it: Running a Survey when Privacy Comes
+               at a Cost}},
+  booktitle = {Proceedings of the 8th Workshop on Internet and Network Economics},
+  series = {WINE '12},
+  pages = {To appear},
+  year      = {2012},
+}
+
+
+
+
+@article{approximatemechanismdesign,
+  author    = {Kobbi Nissim and
+               Rann Smorodinsky and
+               Moshe Tennenholtz},
+  title     = {Approximately Optimal Mechanism Design via Differential
+               Privacy},
+  year      = {2010},
+  ee        = {http://arxiv.org/abs/1004.2888},
+}
+
+
+@techreport{xiao:privacy-truthfulness, 
+author = "David Xiao", 
+title = "Is privacy compatible with truthfulness?", 
+institution = {{Cryptology ePrint Archive}}, 
+number = "2011/005", 
+year = "2011"
+}
+
+
diff --git a/related.tex b/related.tex
index 2788478..f61abc4 100644
--- a/related.tex
+++ b/related.tex
@@ -13,7 +13,16 @@ a truthful, $O(\log^3 n)$-approximate mechanism
 \cite{dobz2011-mechanisms} as well as a a universally truthful, $O(\frac{\log n}{\log \log n})$-approximate mechanism for subadditive maximization. 
 \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)
 
-\stratis{TODO: privacy discussion. Logdet objective. Should be one paragraph each.}
+ A series of recent papers  \cite{mcsherrytalwar,approximatemechanismdesign,xiao:privacy-truthfulness,chen:privacy-truthfulness} consider the related problem of conducting retreive data from an  \textit{unverified} database: the buyer of the data cannot verify the data reported by individuals and therefore must incentivize them to report truthfully. 
+McSherry and Talwar \cite{mcsherrytalwar} argue that \emph{differentially private} mechanisms also offer a form of \emph{approximate truthfulness}, as the mechanism's output is only slightly purturbed when an individual unilaterally changes her data value; as a result, reporting untruthfully can only increase an individual's utility by a small amount. Xiao \cite{xiao:privacy-truthfulness}, improving upon earlier work by Nissim et al.~\cite{approximatemechanismdesign} construct mechanisms that
+simultaneously achieve exact truthfulness as well as differential privacy. Eliciting private data through a \emph{survey} \cite{roth-liggett}, whereby individuals first decide whether to participate in the survey and then report their data,
+ also fall under the unverified database setting \cite{xiao:privacy-truthfulness}. Our work differs from the above works in that it does not capture user utility through differential privacy; crucially, we also assume that experiments conducted are \emph{tamper-proof}, and individuals can missreport their costs but not their values.
+
+Our work is closest to Roth and Schoenebeck \cite{roth-shoenebeck}, who also consider how to sample individuals from a population to obtain an unbiased estimate of a reported value. The authors assume a prior on the joint distribution
+\stratis{to be continued}
+
+
+%\stratis{TODO: privacy discussion. Logdet objective. Should be one paragraph each.}
 
 \begin{comment}
 Two types of mechanisms: \emph{deterministic} and \emph{randomized}. For