diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2013-12-16 23:06:45 -0500 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2013-12-16 23:06:45 -0500 |
| commit | 4881402a832d53f56000dab12c460c62a3be3fc3 (patch) | |
| tree | eba31d8f05d83ce44d8dcb10446663db520cc28d /main.tex | |
| parent | 24fdab84d29f2d2fb0bd78a4c7ad7131100afe94 (diff) | |
| download | recommendation-4881402a832d53f56000dab12c460c62a3be3fc3.tar.gz | |
Incorporate Stratis comments
Diffstat (limited to 'main.tex')
| -rwxr-xr-x | main.tex | 11 |
1 files changed, 5 insertions, 6 deletions
@@ -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}. |
