diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 3 |
1 files changed, 1 insertions, 2 deletions
@@ -15,7 +15,6 @@ One possible interpretation of \eqref{modified} is that, prior to the auction, t \subsection{Truthful, Constant Approximation Mechanism} - In this section we present a mechanism for \EDP. Previous works on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing auction mechanisms for submodular utility functions \cite{singer-mechanisms, @@ -51,7 +50,7 @@ OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big) \end{lemma} Hence, taking the maximum between the greedy set and the point of maximum value -has an approximation ratio of $\frac{5e}{e-1}$. However, Singer +yields an approximation ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that this approach breaks incentive compatibility and therefore cannot be directly applied to the strategic case. |