monotonicity

1 files changed, 11 insertions, 15 deletions

diff --git a/main.tex b/main.tex
index 03e30fc..fbd3592 100644
--- a/main.tex
+++ b/main.tex
@@ -15,7 +15,7 @@ This process terminates when no more items can be added to $S$ using \eqref{gree
 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 heuristic gives an
+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
@@ -25,7 +25,7 @@ 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 heuristic and define $i^*$:
+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}
@@ -197,31 +197,27 @@ The mechanism is monotone.
     Consider an agent $i$ with cost $c_i$ that is
     selected by the mechanism, and suppose that she reports
     a cost $c_i'\leq c_i$, all the other costs staying the same.
-
-    If $i\neq i^*$, since  $s_i(c_i,c_{-i})=1$,
-    $L_\mathcal{N}(x^*) \geq C V(i^*)$ and $i\in S_G$.
-     By reporting a cost $c_i'\leq c_i$, $i$ may be selected at an earlier iteration of the greedy heuristic.
+    Suppose that when $i$ reports $c_i$, $L_{\mathcal{N}\setminus\{i^*\}}(x^*) \geq C V(i^*)$; as $s_i(c_i,c_{-i})$, $i\in S_G$.
+     By reporting a cost $c_i'\leq c_i$, $i$ may be selected at an earlier iteration of the greedy algorithm.
     %using the submodularity of $V$, we see that $i$ will satisfy the greedy
     %selection rule:
     %\begin{displaymath}
     %    i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\})
     %    - V(S)}{c_j}
     %\end{displaymath}
-    %in an earlier iteration of the greedy heuristic. Let us denote by $S_i$
+    %in an earlier iteration of the greedy heuristic.
+ Denote by $S_i$
     (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$
-    (resp. $c_i'$). We have $S_i'\subseteq S_i$. Moreover:
+    (resp. $c_i'$). We have $S_i'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected greedily under $(c_i',c_{-i})$; if not, then greedy selection would terminate prior to selecting $i$ also when she reports $c_i$, a contradiction. Moreover, we have
     \begin{align*}
         c_i' & \leq c_i \leq
         \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})}\\
         & \leq \frac{B}{2}\frac{V(S_i'\cup\{i\})-V(S_i')}{V(S_i'\cup\{i\})}
     \end{align*}
-    Hence $i$ will still be included in the result set.
-
-    If $i = i^*$, $i$ is included iff $L_\mathcal{N}(x^*) \leq C V(i^*)$.
-    Reporting $c_i'$ instead of $c_i$ does not change the value $V(i^*)$ nor
-    $L_\mathcal{N}(x^*)$ (which is computed over
-    $\mathcal{N}\setminus\{i^*\}$). Thus $i$ is still included by reporting
-    a different cost.
+    by the monotonicity and submodularity  of $V$. Hence  $i\in S_G'$. Moreover, as $L_{\mathcal{N}\setminus \{i^*\}}(x^*)$ is the optimal value of \eqref{relax} under relaxation $L_{\mathcal{N}}$, reducing the costs can only increase this value, so under $c'_i\leq c_i$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$.
+    Suppose now that when $i$ reports $c_i$, $L_{\mathcal{N}\setminus \{i^*\}}(x^*) < C V(i^*)$. Then $s_i(c_i,c_{-1})=1$ iff $i = i^*$. 
+    Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor
+    $L_{\mathcal{N}\setminus \{i^*\}}(x^*) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. 
 \end{proof}
 
 \begin{lemma}\label{lemma:budget-feasibility}