diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 2 |
1 files changed, 1 insertions, 1 deletions
@@ -9,7 +9,7 @@ Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N Provided that the relaxation used within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and thus their optimal values are monotone and can be computed exactly in weakly polynomial time. In contrast, we extend these results by showing 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. -To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\note{FIXME!!!} +To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\ref{sec:myerson}. % %Instead, \citeN{singer-mechanisms} and \citeN{chen} %suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the |