budget

1 files changed, 27 insertions, 33 deletions

diff --git a/main.tex b/main.tex
index fbd3592..aa638d3 100644
--- a/main.tex
+++ b/main.tex
@@ -196,8 +196,8 @@ The mechanism is monotone.
 \begin{proof}
     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.
-    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$.
+    a cost $c_i'\leq c_i$ while all  other costs stay the same.
+    Suppose that when $i$ reports $c_i$, $L_{\mathcal{N}\setminus\{i^*\}}(x^*) \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $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:
@@ -208,14 +208,14 @@ The mechanism is monotone.
     %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$; 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
+    (resp. $c_i'$). We have $S_i'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected by the greedy algorithm 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\})}
+        \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*}
-    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^*$. 
+    by the monotonicity and submodularity  of $V$. Hence  $i\in S_G'$. 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_{-i})=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}
@@ -225,28 +225,24 @@ The mechanism is budget feasible.
 \end{lemma}
 
 \begin{proof}
-Let us denote by $S_G$ the set selected by the greedy heuristic in the
-mechanism of Algorithm~\ref{mechanism}. Let $i\in S_G$, let us also denote by
-$S_i$ the solution set that was selected by the greedy heuristic before $i$ was
-added. We use the following result from Chen et al. \cite{chen}, which bounds
-the reported cost of an agent selected by the greedy heuristic, and holds for
-any submodular function $V$:
+Suppose that $L_{\mathcal{N}\setminus\{i^*\}}(x^*) < C V(i^*)$. Then the mechanism selects $i^*$; as the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible.
+Suppose thus that $L_{\mathcal{N}\setminus\{i^*\}}(x^*) \geq C V(i^*)$. 
+Denote by $S_G$ the set selected by the greedy algorithm, and for $i\in S_G$,  denote by
+$S_i$ the subset of the solution set that was selected by the greedy algorithm just prior to the addition of $i$---both sets determined for the present cost vector $c$. Chen \emph{et al.}~\cite{chen} show that, for any submodular function $V$, and for all $i\in S_G$:
+%the reported cost of an agent selected by the greedy heuristic, and holds for
+%any submodular function $V$:
 \begin{equation}\label{eq:budget}
-    c_i \leq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B
+   \text{if}~c_i'\geq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B~\text{then}~s_i(c_i',c_{-i})=0
 \end{equation}
-
-Assume now that our mechanism selects point $i^*$. In this case, his payment
-his $B$ and the mechanism is budget-feasible.
-
-Otherwise, the mechanism selects the set $S_G$. In this case, \eqref{eq:budget}
-shows that the threshold payment of user $i$ is bounded by:
-\begin{displaymath}
-\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B
-\end{displaymath}
-
-Hence, the total payment is bounded by:
+In other words, if $i$ increases her cost to a value higher than $\frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)}$, she will cease to be in the selected set $S_G$. As a result,
+\eqref{eq:budget}
+implies that the threshold payment of user $i$ is bounded by the above quantity.
+%\begin{displaymath}
+%\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} =  B
+%\end{displaymath}
+Hence, the total payment is bounded by the telescopic sum:
 \begin{displaymath}
-    \sum_{i\in S_M} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B \leq B\qed
+    \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qed
 \end{displaymath}
 \end{proof}
 
@@ -262,10 +258,9 @@ Hence, the total payment is bounded by:
 
     The function $\log\det$ is concave and self-concordant (see
     \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be find
-    to a precision $\varepsilon$ in a number of iterations of Newton's method
-    $O(\log\log\varepsilon^{-1})$. Each iteration of Newton's method can be
+    to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$  of iterations of Newton's method. Each iteration  can be
     done in time $O(\text{poly}(n, d))$. Thus, line 2 of
-    algorithm~\ref{mechanism}, can be computed in time
+    Algorithm~\ref{mechanism} can be computed in time
     $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$.
 \end{proof}
 
@@ -275,11 +270,10 @@ $L_\mathcal{N}$. Its proof is our main technical contribution and is done in
 section \ref{sec:relaxation}.
 
 \begin{lemma}\label{lemma:relaxation}
-    We have:
-    \begin{displaymath}
-        OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B)
+    %\begin{displaymath}
+     $   OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B)
         + 2\max_{i\in\mathcal{N}}V(i)
-    \end{displaymath}
+    %\end{displaymath}
 \end{lemma}
 
 \begin{lemma}\label{lemma:approx}