editsEC

4 files changed, 10 insertions, 8 deletions

diff --git a/intro.tex b/intro.tex
index 7dcc39c..6002b46 100644
--- a/intro.tex
+++ b/intro.tex
@@ -59,7 +59,7 @@ We note that the objective \eqref{obj} is submodular. Using this fact, applying
 %Though such mechanisms were known to exist for  combinatorial problems with specific submodular objectives such as \textsc{Knapsack} or \textsc{Coverage}~\cite{singer-mechanisms,chen, singer-influence}, these do not readily apply to the more complicated linear-algebraic  objective function \eqref{obj} of  \SEDP.
 %{\bf S+T: could we verify that the above sentence is correct in its implication?}
 
-From a technical perspective, we present a convex relaxation of \eqref{obj}, and show that it is within a constant factor from the so-called multi-linear relaxation of  \eqref{obj}. 
+From a technical perspective, we present a convex relaxation of \eqref{obj}, and show that it is within a constant factor from the so-called multi-linear relaxation of  \eqref{obj}, which in turn can be related to \eqref{obj} through pipage rounding. We establish the constant factor to the multi-linear relaxation by bounding  the partial derivatives of these two functions; we achieve the latter by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices.
 
 
 %This allows us to adopt the approach followed by prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}.   %{\bf FIX the last sentence}
diff --git a/main.tex b/main.tex
index 55df8fe..e112470 100644
--- a/main.tex
+++ b/main.tex
@@ -90,9 +90,12 @@ The function $L$ is well-known to be concave and even self-concordant (see
 method for self-concordant functions in \cite{boyd2004convex}, shows that
 finding the maximum of $L$ to any precision $\varepsilon$ can be done in
 $O(\log\log\varepsilon^{-1})$ iterations. Being the solution to a maximization
-problem, $OPT'_{-i^*}$ satisfies the required monotonicity property. The main challenge
+problem, $OPT'_{-i^*}$ satisfies the required monotonicity property. 
+
+The main challenge
 will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to
 $OPT_{-i^*}$. 
+We show this by establishing that $L$ is within a constant factor from the so-called multi-linear relaxation of  \eqref{modified}, which in turn can be related to \eqref{modified} through pipage rounding. We establish the constant factor to the multi-linear relaxation by bounding  the partial derivatives of these two functions; we obtain the latter bound by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices.
 
 \begin{algorithm}[t]
     \caption{Mechanism for \SEDP{}}\label{mechanism}
diff --git a/problem.tex b/problem.tex
index 358c825..9d67074 100644
--- a/problem.tex
+++ b/problem.tex
@@ -184,8 +184,8 @@ Given that the full information problem \EDP{} is NP-hard, we further seek mecha
  %   The approximation ratio captures the \emph{price of truthfulness}, \emph{i.e.},  the relative value loss incurred by adding the truthfulness constraint. % to the value function maximization.
     We stress here that the approximation ratio is defined with respect \emph{to the maximal value in the full information case}.
     \item \emph{Computational Efficiency.} The allocation and payment function
-    should be computable in polynomial time in the number of
-    agents $n$. %\thibaut{Should we say something about the black-box model for $V$?  Needed to say something in general, but not in our case where the value function can be computed in polynomial time}.
+    should be computable in time polynomial in various parameters. 
+    %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$?  Needed to say something in general, but not in our case where the value function can be computed in polynomial time}.
 \end{itemize}
 
 As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are  \emph{single parameter} auctions: each agent has only one
diff --git a/related.tex b/related.tex
index 01d114c..66d0d0e 100644
--- a/related.tex
+++ b/related.tex
@@ -1,9 +1,8 @@
 \section{Related work}
 \label{sec:related}
 
-\subsection{Experimental Design} The classic experimental design problem, which we also briefly review in Section~\ref{sec:edprelim}, deals with  which $k$ experiments to conduct among a set of $n$ possible experiments. It is a well studied problem both in the non-Bayesian \cite{pukelsheim2006optimal,atkinson2007optimum,boyd2004convex} and Bayesian setting \cite{chaloner1995bayesian}. Beyond $D$-optimality, several other objectives are encountered in the literature  \cite{pukelsheim2006optimal}; many involve some function of the covariance matrix of the estimate of $\beta$, such as $E$-optimality (maximizing the smallest eigenvalue of the covariance of $\beta$) or $T$-optimality (maximizing the trace). Our focus on $D$-optimality is motivated by both its tractability as well as its relationship to the information gain.  %are encountered in the literature, though they do not relate to entropy as $D$-optimality. We leave the task of approaching the maximization of such objectives from a strategic point of view as an open problem.
-
-
+\junk{\subsection{Experimental Design} The classic experimental design problem, which we also briefly review in Section~\ref{sec:edprelim}, deals with  which $k$ experiments to conduct among a set of $n$ possible experiments. It is a well studied problem both in the non-Bayesian \cite{pukelsheim2006optimal,atkinson2007optimum,boyd2004convex} and Bayesian setting \cite{chaloner1995bayesian}. Beyond $D$-optimality, several other objectives are encountered in the literature  \cite{pukelsheim2006optimal}; many involve some function of the covariance matrix of the estimate of $\beta$, such as $E$-optimality (maximizing the smallest eigenvalue of the covariance of $\beta$) or $T$-optimality (maximizing the trace). Our focus on $D$-optimality is motivated by both its tractability as well as its relationship to the information gain.  %are encountered in the literature, though they do not relate to entropy as $D$-optimality. We leave the task of approaching the maximization of such objectives from a strategic point of view as an open problem.
+}
 \subsection{Budget Feasible Mechanisms for General Submodular Functions}
 Budget feasible mechanism design was originally proposed by  \citeN{singer-mechanisms}. Singer considers the problem of maximizing an arbitrary submodular function subject to a budget constraint in the \emph{value query} model, \emph{i.e.} assuming an  oracle providing the  value of the submodular objective on any given set. 
  Singer shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen}  improve this result by providing a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization.
@@ -29,7 +28,7 @@ Posted price, rather than direct revelation mechanisms, are also studied in \cit
 
 
 \subsection{Data Markets}
- A series of recent papers  \cite{mcsherrytalwar,approximatemechanismdesign,xiao:privacy-truthfulness,chen:privacy-truthfulness} consider the related problem of retrieving data from an  \textit{unverified} database, where strategic users may misreport their data to ensure their privacy. \citeN{mcsherrytalwar} argue that \emph{differentially private} mechanisms offer a form of \emph{approximate truthfulness}: if users have a utility that depends on their privacy, reporting their data untruthfully can only increase their utility by a small amount.  %\citeN{xiao:privacy-truthfulness}, improving upon earlier work by~\citeN{approximatemechanismdesign}, constructs mechanisms that simultaneously achieve exact truthfulness as well as differential privacy. 
+ A series of recent papers  \cite{mcsherrytalwar,approximatemechanismdesign,xiao:privacy-truthfulness,chen:privacy-truthfulness} consider the related problem of retrieving data from an  \textit{unverified} database, where strategic users may misreport their data to ensure their privacy. %\citeN{mcsherrytalwar} argue that \emph{differentially private} mechanisms offer a form of \emph{approximate truthfulness}: if users have a utility that depends on their privacy, reporting their data untruthfully can only increase their utility by a small amount.  %\citeN{xiao:privacy-truthfulness}, improving upon earlier work by~\citeN{approximatemechanismdesign}, constructs mechanisms that simultaneously achieve exact truthfulness as well as differential privacy. 
 We depart by assuming that experiment outcomes are tamper-proof and cannot be manipulated.  
 A different set of papers \cite{ghosh-roth:privacy-auction,roth-liggett,pranav} consider a setting where data cannot be misreported, but the utility of users is a function of the differential privacy guarantee an analyst provides them. We do not focus on privacy; any privacy costs in our setup are internalized in the costs $c_i$.  %Eliciting private data through a \emph{survey} \cite{roth-liggett}, whereby individuals first decide whether to participate in the survey and then report their data,
 % also falls under the unverified database setting \cite{xiao:privacy-truthfulness}. In the \emph{verified} database setting, \citeN{ghosh-roth:privacy-auction} and~\citeN{pranav} consider budgeted auctions where users have a utility again captured by differential privacy. Our work departs from the above setups in that utilities do not involve privacy, whose effects are assumed to be internalized in the costs reported by the users; crucially, we also assume that experiments are tamper-proof, and individuals can misreport their costs but not their values.