1 files changed, 98 insertions, 12 deletions
diff --git a/appendix.tex b/appendix.tex
index 73e879d..1a5bcc5 100755
--- a/appendix.tex
+++ b/appendix.tex
@@ -15,8 +15,8 @@ V(S\cup \{i\}) - V(S)& =   \frac{1}{2}\log\det(I_d
     + \T{X_S}X_S + x_i\T{x_i})
     - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\nonumber\\
     &  = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d +
-\T{X_S}X_S)^{-1})
- = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i)\label{eq:marginal_contrib}
+\T{X_S}X_S)^{-1})\nonumber\\
+&= \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i)\label{eq:marginal_contrib}
 \end{align}
 where $A(S) \defeq I_d+ \T{X_S}X_S$, and the last equality follows from the
 Sylvester's determinant identity~\cite{sylvester}. Monotonicity therefore follows from the fact that $A(S)^{-1}$ is positive semidefinite. Finally, since the inverse is decreasing over positive definite matrices, we have
@@ -107,8 +107,8 @@ for all $S\subseteq\mathcal{N}\setminus\{i\}$. Hence,
     & \geq \frac{1}{4}
     \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
     P_{\mathcal{N}}^\lambda(S)
-    \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
-    +\frac{1}{4}
+    \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
+    &+\frac{1}{4}
     \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
     P_{\mathcal{N}}^\lambda(S\cup\{i\})
     \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
@@ -212,8 +212,8 @@ the proof of the lemma. \qed
         F_\lambda(\varepsilon)
         & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[
         (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\
-        & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})
-         + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\
+        & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})\\
+        &+ (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\
          & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big]
     \end{align*}
     Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is:
@@ -264,7 +264,7 @@ Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed
 %For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate
 %approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$.
 %\end{lemma}
-Our next technical result establishes that, using the barrier method, it is possible to construct an algorithm that computes $L^*_c$ at arbitrary accuracy in polynomial time \emph{and} is $\delta$-decreasing. We achieve this by restricting the optimization over a subset of $\dom_c$ at which the concave relaxation $L$ is ``sufficiently'' concave. Formally, for $\alpha\geq 0$ let $$\textstyle\dom_{c,\alpha} \defeq \{\lambda \in [\alpha,1]^n: \sum_{i\in \mathcal{N}}c_i\lambda_i \leq B\}\subseteq  \dom_c . $$ 
+We begin by a description of Algorithm~\ref{alg:monotone} which computes an approximation of $L^*_c$, which is arbitrarily accurate \emph{and} $\delta$-decreasing. We achieve this by restricting the optimization over a subset of $\dom_c$ at which the concave relaxation $L$ is ``sufficiently'' concave. Formally, for $\alpha\geq 0$ let $$\textstyle\dom_{c,\alpha} \defeq \{\lambda \in [\alpha,1]^n: \sum_{i\in \mathcal{N}}c_i\lambda_i \leq B\}\subseteq  \dom_c . $$ 
 Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concave relaxation \eqref{eq:primal}:
 \begin{align}\tag{$P_{c,\alpha}$}\label{eq:perturbed-primal}
 \begin{split}  \text{Maximize:} &\qquad L(\lambda)\\
@@ -335,6 +335,8 @@ well-behaved with respect to changes of the cost
 (Lemma~\ref{lemma:monotonicity}). These lemmas together imply
 Proposition~\ref{prop:monotonicity}.
 
+We note that the execution of the barrier method on the restricted set $\dom_{c,\alpha}$ is necessary. The algorithm's output when executed over the entire domain may not necessarily be $\delta$-decreasing, even when the approximation accuracy is small. This is because costs become saturated when the optimal $\lambda\in \dom_c$ lies at the boundary: increasing them has no effect on the objective. Forcing the optimization to happen ``off'' the boundary ensures that this does not occur, while taking $\alpha$ to be small ensures that this perturbation does not cost much in terms of approximation accuracy.
+
 Note that the choice of $\alpha$ given in Algorithm~\ref{alg:monotone} implies
 that $\alpha<\frac{1}{n}$. This in turn implies that the feasible set
 $\mathcal{D}_{c, \alpha}$ of \eqref{eq:perturbed-primal} is non-empty: it
@@ -561,7 +563,7 @@ $S:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function}
 $p:\reals_+^n\to \reals_+^n$. 
  Let $s_i(c) = \id_{i\in S(c)}$ be the binary indicator of  $i\in S(c)$. We seek mechanisms that have the following properties \cite{singer-mechanisms}:
 \begin{itemize}
-\item \emph{Normalization.} Unallocated experiments receive zero payments: $s_i(c)=0\text{ implies }p_i(c)=0.\label{normal}$
+\item \emph{Normalization.} Unallocated experiments receive zero payments: $s_i(c)=0$ implies $p_i(c)=0.\label{normal}$
 \item\emph{Individual Rationality.} Payments for allocated experiments exceed
 costs: $p_i(c)\geq c_i\cdot s_i(c).\label{ir}$
 \item \emph{No Positive Transfers.} Payments are non-negative: $p_i(c)\geq 0\label{pt}$.
@@ -590,7 +592,91 @@ Formally, there must exist some $\alpha\geq 1$ and $\beta>0$
 \section{Proof of Lemma~\ref{thm:myerson-variant}}\label{sec:myerson}
 \input{myerson}
 
-\section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
+\section{Description of our mechanism for \EDP{} and proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
+
+We begin by a description of the methodology used to construct our mechanism.
+Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in
+\mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set
+constructed greedily, by selecting elements of maximum marginal value per cost.
+The general framework used by \citeN{chen}  and by \citeN{singer-influence} for
+the \textsc{Knapsack}   and \textsc{Coverage} value functions contructs an
+allocation as follows. First, a polynomial-time, monotone approximation of
+$OPT$ is computed over all elements excluding $i^*$. The outcome of this
+approximation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the
+mechanism constructs an allocation $S_G$ greedily; otherwise, the only item
+allocated is the singleton $\{i^*\}$.  Provided that the approximation used is
+within a constant from $OPT$, the above allocation can be shown to also yield
+a constant approximation to $OPT$. Furthermore, using Myerson's
+Theorem~\cite{myerson}, it can be shown that this allocation combined with
+\emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below)
+constitute a truthful mechanism. 
+
+The approximation algorithms used in \cite{chen,singer-influence} are LP
+relaxations, and thus their outputs are monotone and can be computed exactly in
+polynomial time. We show that the convex relaxation \eqref{eq:primal}, which
+can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be
+used to construct a $\delta$-truthful, constant approximation mechanism, by
+being incorporated in the same framework.
+
+To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in Appendix~\ref{sec:myerson}.
+%
+%Instead, \citeN{singer-mechanisms} and \citeN{chen}
+%suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
+%following properties:
+%\begin{itemize}
+%    \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported cost and must
+%    be decreasing with respect to the costs. This is to ensure the monotonicity
+%    of the allocation function.
+%    \item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded
+%    approximation ratio.
+%    \item $OPT'_{-i^*}$ must be computable in polynomial time.
+%\end{itemize}
+%
+%One of the main technical contributions of \citeN{chen} and
+%\citeN{singer-influence} is to come up with appropriate such quantity by
+%considering relaxations of \textsc{Knapsack} and \textsc{Coverage},
+%respectively.
+%
+%\subsection{Our Approach}
+%
+%Using the results from Section~\ref{sec:approximation}, we come up with
+%a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being
+%$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as
+%defined below.
+%
+%\begin{definition}
+%Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator
+%function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is
+%$\delta$-truthful iff:
+%\begin{displaymath}
+%\forall c\in\reals_+^n,\;
+%\forall\mu\;\text{with}\; |\mu|\geq\delta,\;
+%\forall i\in\{1,\ldots,n\},\;
+%p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i
+%\end{displaymath}
+%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$.
+%\end{definition}
+%
+%Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie
+%by more than $\delta$ about their reported costs. In practical applications,
+%the bids being discretized, if $\delta$ is smaller than the discretization
+%step, the mechanism will be truthful in effect.
+
+%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
+%variant of Myerson's theorem.
+
+\begin{lemma}\label{thm:myerson-variant}
+ A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
+$\delta$-truthful if:
+(a) $S$ is $\delta$-monotone, \emph{i.e.}, for any agent $i$ and $c_i' \leq
+c_i-\delta$, for any
+fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i,
+c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
+ agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$.
+\end{lemma}
+Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the
+above framework, yielding Theorem~\ref{thm:main}.
+
 \begin{algorithm}[!t]
     \caption{Mechanism for \SEDP{}}\label{mechanism}
     \begin{algorithmic}[1]
@@ -729,7 +815,8 @@ OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
 \end{displaymath}
 \end{lemma}
 
-Using Proposition~\ref{prop:relaxation} and Lemma~\ref{lemma:greedy-bound} we can complete the proof of
+Using Proposition~\ref{prop:relaxation} and Lemma~\ref{lemma:greedy-bound} we
+can complete the proof of the approximation ratio of our mechanism
 Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if
 $OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from
 $\mathcal{N}$, has been computed to a precision $\varepsilon$, then the set
@@ -793,8 +880,7 @@ Placing the expression of $C$ in \eqref{eq:bound1} and \eqref{eq:bound2}
 gives the approximation ratio in \eqref{approxbound}, and concludes the proof
 of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed
 
-\section{Proof of Theorem \ref{thm:lowerbound}}\label{proofoflowerbound}
-
+Finally, we prove the lower bound stated in Theorem~\ref{thm:main}
 Suppose, for contradiction, that such a mechanism exists. From Myerson's Theorem \cite{myerson}, a single parameter auction is truthful if and only if the allocation function is monotone and agents are paid theshold payments. Consider two
 experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$
 and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must