small

1 files changed, 7 insertions, 7 deletions

diff --git a/problem.tex b/problem.tex
index 1ac1a38..15f0c11 100644
--- a/problem.tex
+++ b/problem.tex
@@ -91,10 +91,10 @@ The cost $c_i$ can capture, \emph{e.g.}, the amount the subject $i$ deems suffic
 \begin{subequations}
 \begin{align}
 \text{Maximize}\quad V(S) &= \log\det(I_d+\T{X_S}X_S) \label{modified} \\
-\text{subject to}\quad \sum_{i\in S} c_i&\leq B
+\text{subject to}\quad \sum_{i\in S} c_i&\leq B\label{lincon}
 \end{align}\label{edp}
 \end{subequations}
-\emph{W.l.o.g.}, we assume that $c_i\in [0,B]$ for all $i\in \mathcal{N}$, as no $i$ with $c_i>B$ can be in $S$. We denote by
+\emph{W.l.o.g.}, we assume that $c_i\in [0,B]$ for all $i\in \mathcal{N}$, as no $i$ with $c_i>B$ can be in an $S$ satisfying \eqref{lincon}. Denote by
 \begin{equation}\label{eq:non-strategic}
     OPT = \max_{S\subseteq\mathcal{N}} \Big\{V(S) \;\Big| \;
     \sum_{i\in S}c_i\leq B\Big\}
@@ -106,11 +106,11 @@ $w_i$, to an experiment with $x_i^2=w_i$.% Moreover, \eqref{modified} is submodu
 
 The value function \eqref{modified} has the following properties, which are proved in Appendix~\ref{app:properties}. First, it is non-negative, \emph{i.e.}, $V(S)\geq 0$
 for all $S\subseteq\mathcal{N}$. Second, it is
-also monotone, \emph{i.e.}, $V(S)\leq V(T)$ for all $S\subset T$, with
-$V(\emptyset)=0$. Finally, it is a submodular, \emph{i.e.}, 
-$V(S)+V(T)\geq V(S\cup T)+V(S\cap T)$ for all $S,T\subseteq \mathcal{N}$. 
+also monotone, \emph{i.e.}, $V(S)\leq V(T)$ for all $S\subseteq T$, with
+$V(\emptyset)=0$. Finally, it is submodular, \emph{i.e.}, 
+$V(S\cup \{i\})-V(S)\geq V(T\cup \{i\})-V(T)$ for all $S\subseteq T\subseteq \mathcal{N}$ and $i\in \mathcal{N}$. 
 %Finally, we define the strategic version  of \EDP{} (denoted by \SEDP) by adding the additional constraints of truthfulness, individual rationality, and normal payments, as described in the previous section.
-The above three properties imply that a greedy algorithm yields a constant approximation ratio to \EDP.
+The above imply that a greedy algorithm yields a constant approximation ratio to \EDP.
 In particular, consider the greedy algorithm in which, for
 %In the full-information case, submodular maximization under a budget constraint
 %\eqref{eq:non-strategic} relies on a greedy heuristic in which elements are
@@ -145,7 +145,7 @@ We seek mechanisms that are \emph{normalized} (unallocated experiments receive z
 We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring that reporting one's true cost is an \emph{almost-dominant} strategy: no subject increases their utility by reporting a cost that differs more than $\delta>0$ from their true cost. Under this definition, a mechanism is truthful if $\delta=0$. 
 In addition, we would like the allocation $S(c)$ to be of maximal value; however, $\delta$-truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with that  are \emph{$(\alpha,\beta)$-approximate}, \emph{i.e.}, there exist $\alpha\geq 1$ and $\beta>0$ s.t.~$OPT \leq \alpha V(S(c))+\beta$, and are \emph{computationally efficient}, in that $S$ and $p$ can be computed in polynomial time.
 
-We note that  the greedy algorithm \eqref{eq:max-algorithm} breaks
+We note that  the constant approximation algorithm \eqref{eq:max-algorithm} breaks
 truthfulness. Though this is not true for all submodular functions (see, \emph{e.g.}, \cite{singer-mechanisms}), it is true for the objective of \EDP{}: we show this in Appendix~\ref{sec:non-monotonicity}. This motivates our study of more complex mechanisms.
 
 \begin{comment}