diff options
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}. |