diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 23 |
1 files changed, 21 insertions, 2 deletions
@@ -151,10 +151,29 @@ The mechanism is monotone. The mechanism is budget feasible. \end{lemma} -The proof is the same as in Chen and is given here for the sake of -completeness. \begin{proof} +Let us denote by $S_M$ the set selected by the greedy heuristic in the +mechanism of Algorithm~\ref{mechanism}. Let $i\in S_M$, let us also denote by +$S_i$ the solution set that was selected by the greedy heuristic before $i$ was +added. Recall from \cite{chen} that the following holds for any submodular +function: if the point $i$ was selected by the greedy heuristic, then: +\begin{equation}\label{eq:budget} + c_i \leq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_M)} B +\end{equation} +Assume now that our mechanism selects point $i^*$. In this case, his payement +his $B$ and the mechanism is budget-feasible. + +Otherwise, the mechanism selects the set $S_M$. In this case, \eqref{eq:budget} +shows that the threshold payement of user $i$ is bounded by: +\begin{displaymath} +\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_M)} B +\end{displaymath} + +Hence, the total payement is bounded by: +\begin{displaymath} + \sum_{i\in S_M} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_M)} B \leq B +\end{displaymath} \end{proof} The following lemma proves that the relaxation $L_\mathcal{N}$ that we are |