diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 6 |
1 files changed, 3 insertions, 3 deletions
@@ -26,7 +26,7 @@ OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big). \end{displaymath} \end{lemma} This lemma immediately implies that the following algorithm: -\begin{equation}\label{eq:algorithm} +\begin{equation}\label{eq:max-algorithm} \textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\} \;\textbf{else return}\; S_G \end{equation} @@ -34,7 +34,7 @@ has an approximation ratio of $\frac{5e}{e-1}$. \subsection*{Submodular maximization in the strategic case} -In the strategic case, Algorithm~\ref{eq:algorithm} breaks incentive +In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive compatibility. Indeed, \citeN{singer-influence} notes that this allocation function is not monotone, which implies by Myerson's theorem (Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful. @@ -47,7 +47,7 @@ full-information case after removing $i^*$ from the set $\mathcal{N}$: \end{equation} \citeN{singer-mechanisms} and \citeN{chen} prove that using the following allocation: -\begin{displaymath}\label{eq:algorithm} +\begin{displaymath} \textbf{if}\; V(\{i^*\}) \geq C. OPT_{-i^*}\; \textbf{return}\; \{i^*\} \;\textbf{else return}\; S_G \end{displaymath} |