diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 50 |
1 files changed, 33 insertions, 17 deletions
@@ -1,10 +1,16 @@ - +\label{sec:main} %\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 value functions \cite{singer-mechanisms, -chen, singer-influence} rely on a greedy algorithm. In this algorithm, elements +In this section we present a mechanism for \EDP. + +\paragraph{Prior approach on sub modular optimization, without strategy} + Previous works~\cite{nemhauser, sviridenko-submodular,singer-mechanisms,chen, singer-influence} +% +%on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing +%auction mechanisms for submodular value functions \cite{singer-mechanisms, +%chen, singer-influence} +% +rely on a greedy algorithm. In this algorithm, elements are added to the solution set according to the following greedy selection rule. Assume that $S\subseteq \mathcal{N}$ is the solution set constructed thus far; then, the next element $i$ to be included in $S$ is the one with the highest \emph{marginal-value-per-cost}: @@ -14,36 +20,46 @@ included in $S$ is the one with the highest \emph{marginal-value-per-cost}: This process terminates when no more items can be added to $S$ using \eqref{greedy} under budget $B$. This is the generalization of the \emph{value-per-cost} ratio used in the greedy approximation algorithm for \textsc{Knapsack}. However, in contrast to \textsc{Knapsack}, for general submodular functions, the marginal value of an element in \eqref{greedy} depends on the set to which it the element is added. - +% Unfortunately, even for the full information case, the greedy algorithm gives an unbounded approximation ratio. Let $i^* -= \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value (as a singleton -set). It has been noted by Khuller \emph{et al.}~\cite{khuller} that for the maximum += \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value. +% (as a singleton set). +%It has been noted by Khuller \emph{et al.}~\cite{khuller} that + For the maximum coverage problem, taking the maximum between the greedy solution and $V(i^*$) -gives a $\frac{2e}{e-1}$ approximation ratio. In the general case, we have the +gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller} . In the general case, +\junk{we have the following result from Singer \cite{singer-influence} which follows from Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...} +} -\begin{lemma}[Singer \cite{singer-influence}]\label{lemma:greedy-bound} -Let $S_G$ be the set computed by the greedy algorithm and define $i^*$: -\begin{displaymath} - i^* = \argmax_{i\in\mathcal{N}} V(i) -\end{displaymath} -then the following inequality holds: +\begin{lemma}~\cite{singer-influence}\label{lemma:greedy-bound} +Let $S_G$ be the set computed by the greedy algorithm and let +%define $i^*$: +%\begin{displaymath} +$i^* = \argmax_{i\in\mathcal{N}} V(i).$ +%\end{displaymath} +We have: +% the following inequality holds: \begin{displaymath} OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big). \end{displaymath} \end{lemma} Hence, taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation -ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that +ratio of $\frac{5e}{e-1}$. However, this approach breaks incentive compatibility and therefore cannot be directly -applied to the strategic case. Indeed, suppose this allocation mechanism is used, and consider a case where +applied to the strategic case.~\cite{singer-influence} +\junk{ +Indeed, suppose this allocation mechanism is used, and consider a case where the allocates the greedy set ($V(S_G) \geq V(i^*)$). If an agent $i$ from $S_G$ reduces her cost, it could happen that $V(S_G)$ becomes smaller than $V(i^*)$. In this case the mechanism's allocation becomes $i^*$, and $i$ is excluded from the allocated set. This violates the monotonicity of the allocation function and hence also truthfulness, by Myerson's Theorem. +} + To address this, Chen \emph{et al.}~\cite{chen} %and Singer~\cite{singer-influence}, introduce a third quantity: if $V(i^*)$ is larger than this quantity, the |