summaryrefslogtreecommitdiffstats
path: root/main.tex
diff options
context:
space:
mode:
authorThibaut Horel <thibaut.horel@gmail.com>2013-12-16 23:06:45 -0500
committerThibaut Horel <thibaut.horel@gmail.com>2013-12-16 23:06:45 -0500
commit4881402a832d53f56000dab12c460c62a3be3fc3 (patch)
treeeba31d8f05d83ce44d8dcb10446663db520cc28d /main.tex
parent24fdab84d29f2d2fb0bd78a4c7ad7131100afe94 (diff)
downloadrecommendation-4881402a832d53f56000dab12c460c62a3be3fc3.tar.gz
Incorporate Stratis comments
Diffstat (limited to 'main.tex')
-rwxr-xr-xmain.tex11
1 files changed, 5 insertions, 6 deletions
diff --git a/main.tex b/main.tex
index 5998d6a..0354ad6 100755
--- a/main.tex
+++ b/main.tex
@@ -13,17 +13,16 @@ approximation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the
mechanism constructs an allocation $S_G$ greedily; otherwise, the only item
allocated is the singleton $\{i^*\}$. Provided that the approximation used is
within a constant from $OPT$, the above allocation can be shown to also yield
-a constant approximation to $OPT$. Furthermore, using Myerson's
-Theorem~\cite{myerson}, it can be shown that this allocation combined with
+a constant approximation to $OPT$. Furthermore, Myerson's
+Theorem~\cite{myerson} implies that this allocation combined with
\emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below)
constitute a truthful mechanism.
The approximation algorithms used in \cite{chen,singer-influence} are LP
relaxations, and thus their outputs are monotone and can be computed exactly in
-polynomial time. We show that the convex relaxation \eqref{eq:primal}, which
-can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be
-used to construct a $\delta$-truthful, constant approximation mechanism, by
-being incorporated in the same framework.
+polynomial time. We show that the convex relaxation \eqref{eq:primal}, solved
+by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to
+construct a $\delta$-truthful, constant approximation \mbox{mechanism.}
To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in \cite{arxiv}.