Fix some typos and inconsistent notations

3 files changed, 10 insertions, 10 deletions

diff --git a/appendix.tex b/appendix.tex
index 11607b0..b1d35d6 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -5,7 +5,7 @@ Our mechanism for \EDP{} is monotone and budget feasible.
     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(\xi) \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$.
+    Suppose that when $i$ reports $c_i$, $OPT'_{-i^*} \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:
@@ -22,18 +22,18 @@ Our mechanism for \EDP{} is monotone and budget feasible.
         \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(\xi)$,  is the optimal value of \eqref{relax} under relaxation $L$ when $i^*$ is excluded from $\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(\xi) < 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 $OPT'_{-i^*}$,  is the optimal value of \eqref{relax} under relaxation $L$ when $i^*$ is excluded from $\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$, $OPT'_{-i^*} < 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(\xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone.
+    $OPT'_{-i^*} \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone.
 %\end{proof}
 %\begin{lemma}\label{lemma:budget-feasibility}
 %The mechanism is budget feasible.
 %\end{lemma}
 %\begin{proof}
 
-To show budget feasibility, suppose that $L(\xi) < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible.
-Suppose  that $L(\xi) \geq C V(i^*)$. 
+To show budget feasibility, suppose that $OPT'_{-i^*} < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible.
+Suppose  that $OPT'_{-i^*} \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, 
diff --git a/main.tex b/main.tex
index e112470..d8635db 100644
--- a/main.tex
+++ b/main.tex
@@ -1,7 +1,7 @@
 \label{sec:main}
 
 In this section we present our mechanism for \SEDP. Prior approaches to budget
-feasible mechanisms for sudmodular maximization build upon the full information
+feasible mechanisms for submodular maximization build upon the full information
 case, which we discuss first.
 
 \subsection{Submodular Maximization in the Full Information Case}
@@ -67,7 +67,7 @@ $\mathcal{N}$ if $L(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S
 denotes the indicator vector of $S$. The optimization program
 \eqref{eq:non-strategic} extends naturally to such relaxations:
 \begin{align}
-    OPT' = \argmax_{\lambda\in[0, 1]^{n}}
+    OPT' \defeq \max_{\lambda\in[0, 1]^{n}}
     \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
     \leq B\right\}\label{relax}
 \end{align}
@@ -102,7 +102,7 @@ We show this by establishing that $L$ is within a constant factor from the so-ca
     \begin{algorithmic}[1]
     \State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$
     \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
-    \State $OPT'_{-i^*} \gets \argmax_{\lambda\in[0,1]^{n}} \{L(\lambda)
+    \State $OPT'_{-i^*} \gets \max_{\lambda\in[0,1]^{n}} \{L(\lambda)
                                     \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$
         \Statex
         \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c}
diff --git a/problem.tex b/problem.tex
index 9d67074..c9037b0 100644
--- a/problem.tex
+++ b/problem.tex
@@ -155,7 +155,7 @@ returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$.
     \item \emph{Truthfulness/Incentive Compatibility.} An experiment subject has no incentive to missreport her true cost. Formally, let $c_{-i}$
  be a vector of costs of all agents except $i$. Then, %    $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i',
 %    c_{-i})$, then the 
-\begin{align}  p_i(c_i,c_{-i}) - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s(c_i',c_{-i})\cdot c_i, \label{truthful}\end{align} for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$.
+\begin{align}  p_i(c_i,c_{-i}) - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s_i(c_i',c_{-i})\cdot c_i, \label{truthful}\end{align} for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$.
     \item \emph{Budget Feasibility.} The sum of the payments should not exceed the
     budget constraint, \emph{i.e.}
     %\begin{displaymath}