xi

1 files changed, 13 insertions, 15 deletions

diff --git a/main.tex b/main.tex
index 535f759..9d840da 100644
--- a/main.tex
+++ b/main.tex
@@ -133,10 +133,10 @@ The resulting mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. Th
     \caption{Mechanism for \EDP{}}\label{mechanism}
     \begin{algorithmic}[1]
     \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
-    \State $x^* \gets \argmax_{x\in[0,1]^{n}} \{L_{\mathcal{N}\setminus\{i^*\}}(x)
-                                    \mid c(x)\leq B\}$, with precision $\epsilon>0$
+    \State $\xi \gets \argmax_{\lambda\in[0,1]^{n}} \{L_{\mathcal{N}\setminus\{i^*\}}(\lambda)
+                                    \mid \sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$, with precision $\epsilon>0$
         \Statex
-        \If{$L_{\mathcal{N}\setminus\{i^*\}}(x^*) < C \cdot V(i^*)$} \label{c}
+        \If{$L_{\mathcal{N}\setminus\{i^*\}}(\xi) < C \cdot V(i^*)$} \label{c}
             \State \textbf{return} $\{i^*\}$ 
         \Else
             \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
@@ -197,7 +197,7 @@ 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$ 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$.
+    Suppose that when $i$ reports $c_i$, $L_{\mathcal{N}\setminus\{i^*\}}(\xi) \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:
@@ -214,10 +214,10 @@ The mechanism is monotone.
         \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'$. 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^*$. 
+    by the monotonicity and submodularity  of $V$. Hence  $i\in S_G'$. As $L_{\mathcal{N}\setminus \{i^*\}}(\xi)$ 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^*\}}(\xi) < 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$. 
+    $L_{\mathcal{N}\setminus \{i^*\}}(xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. 
 \end{proof}
 
 \begin{lemma}\label{lemma:budget-feasibility}
@@ -225,8 +225,8 @@ The mechanism is budget feasible.
 \end{lemma}
 
 \begin{proof}
-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^*)$. 
+Suppose that $L_{\mathcal{N}\setminus\{i^*\}}(\xi) < 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^*\}}(\xi) \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
@@ -266,16 +266,14 @@ Hence, the total payment is bounded by the telescopic sum:
 
 Finally, we prove the approximation ratio of the mechanism. We use the
 following lemma, which gives an approximation ratio of the function
-$L_\mathcal{N}$. Its proof is our main technical contribution and is done in
-section \ref{sec:relaxation}.
-
+$L_\mathcal{N}$. 
 \begin{lemma}\label{lemma:relaxation}
     %\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{lemma}
-
+Its proof is our main technical contribution, and can be found in Section \ref{sec:relaxation}.
 \begin{lemma}\label{lemma:approx}
     %C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C
     %(e-1) -10e  +2}\right)\right)
@@ -288,8 +286,8 @@ section \ref{sec:relaxation}.
 \end{lemma}
 
 \begin{proof}
-    We assume that on line 2 of algorithm~\ref{mechanism}, a quantity
-    $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L(x^*) \leq
+    Let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 2 of algorithm~\ref{mechanism}, a quantity
+    $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L_{\mathcal{N}\setminus {i^*}}(x^*) \leq
     \tilde{L}+\varepsilon$ has been computed (lemma~\ref{lemma:complexity}
     states that this can be done in a time within our complexity guarantee).