diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2013-02-11 01:06:19 -0800 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2013-02-11 01:06:19 -0800 |
| commit | cd7c3fe857f1ec8972959be2a5a9b73c6f4167ef (patch) | |
| tree | 2be979a0806e59d87c8b1113ee943da0f6af26f5 /main.tex | |
| parent | 2b9393eb3d79cd29b5b5c1b0582199c9592459e4 (diff) | |
| download | recommendation-cd7c3fe857f1ec8972959be2a5a9b73c6f4167ef.tar.gz | |
Small fixes to section 3 and 4
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} |
