related

5 files changed, 25 insertions, 16 deletions

diff --git a/general.tex b/general.tex
index 429299a..5f80c58 100644
--- a/general.tex
+++ b/general.tex
@@ -29,9 +29,9 @@ where $\mu$ is the smallest eigenvalue of $R$.
 \subsection{Non-Bayesian Setting}
 
 In the non-bayesian setting, \emph{i.e.} when the experimenter has no prior
-distribution on the model, the covariance matrix $R$ is the zero matrix and
-ridge regression \eqref{ridge} reduces to simple least squares. In this case,
-the $D$-optimal criterion takes the following form:
+distribution on the model, the covariance matrix $R$ is the zero matrix. In this case,
+the ridge regression estimation proceedure \eqref{ridge} reduces to simple least squares (\emph{i.e.}, linear regression),
+and the $D$-optimality reduces to the entropy of $\hat{\beta}$, given by:
 \begin{equation}\label{eq:d-optimal}
 V(S) = \log\det(X_S^TX_S)
 \end{equation}
@@ -46,16 +46,14 @@ and individual rationality.
 \begin{lemma}
 For any $M>1$, there is no $M$-approximate, truthful, budget feasible,
 individually rational mechanism for a budget feasible reverse auction with
-value function $V(S) = \det{\T{X_S}X_S}$.  For any $M>1$, there is no
-$M$-approximate, truthful, budget feasible, individually rational mechanism for
-a budget feasible reverse auction with $V(S) =  \det{\T{X_S}X_S}$.
+value function $V(S) = \det{\T{X_S}X_S}$.  
 \end{lemma}
 
 \begin{proof}
 \input{proof_of_lower_bound1}
 \end{proof}
 
-Beyond $D$-optimality, several other objectives such as $E$-optimality (maximizing the smallest eigenvalue of $\T{X_S}X_S$) or $T$-optimality (maximizing $\mathrm{trace}(\T{X_S}{X_S}))$ are encountered in the literature \cite{pukelsheim2006optimal}, 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.
+%Beyond $D$-optimality, several other objectives such as $E$-optimality (maximizing the smallest eigenvalue of $\T{X_S}X_S$) or $T$-optimality (maximizing $\mathrm{trace}(\T{X_S}{X_S}))$ are encountered in the literature \cite{pukelsheim2006optimal}, 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{Beyond Linear Models}
 Selecting experiments that maximize the information gain in the Bayesian setup
diff --git a/intro.tex b/intro.tex
index ce66c1d..f69620f 100644
--- a/intro.tex
+++ b/intro.tex
@@ -39,10 +39,10 @@ subject to a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budge
 \smallskip
 The objective function, which is the key, is formally obtained by optimizing  the information gain in  $\beta$ when the latter is learned  through linear regression, and is related to  the so-called $D$-optimality criterion~\cite{pukelsheim2006optimal,atkinson2007optimum}. 
 \item
-We present a polynomial time, truthful mechanism for \SEDP{}, yielding a constant factor ($\approx 12.98$) approximation. In contrast to this, we show that no truthful, budget-feasible algorithms are possible for \SEDP{}  within a factor 2 approximation. 
+We present a polynomial time, truthful mechanism for \SEDP{}, yielding a constant factor ($\approx 12.98$) approximation to the optimal value of \eqref{obj}. In contrast to this, we show that no truthful, budget-feasible algorithms are possible for \SEDP{}  within a factor 2 approximation. 
 
 \smallskip
-We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results for budget feasible mechanisms under general submodular objectives would yield either a truthful deterministic mechanism that requires exponential time,  or a poly-time algorithm that is not deterministic~\cite{singer-mechanisms,chen}.
+We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results for budget feasible mechanisms under general submodular objectives~\cite{singer-mechanisms,chen} would yield either a deterministic, truthful, constant-approximation mechanism that requires exponential time,  or a non-deterministic, (universally) truthful, poly-time mechanism that yields a constant approximation ratio only \emph{in expectation} (\emph{i.e.}, its approximation guarantee for a given instance may in fact be unbounded).
 \end{itemize}
 
 
@@ -66,7 +66,7 @@ From a technical perspective, we present a convex relaxation of \eqref{obj}, and
 %Our approach to mechanisms for experimental design --- by 
 % optimizing  the information gain in parameters like $\beta$ which are estimated through the data analysis process --- is general.  We give examples of this approach beyond linear regression to a general class that includes logistic regression and learning binary functions, and show that the corresponding budgeted mechanism design problem is also expressed through a submodular optimization.  Hence,  prior work \cite{chen,singer-mechanisms} immediately applies, and gives randomized, universally truthful, polynomial time, constant factor approximation mechanisms for problems in this class. Getting deterministic, truthful, polynomial time mechanisms with a constant approximation factor for this class or specific problems in it, like we did for \EDP, remains an open problem.
 
-In what follows, we describe related work in Section~\ref{sec:related}. We briefly review  experimental design and budget feasible mechanisms in Section~\ref{sec:peel} and define \SEDP\ formally. In Section~\ref{sec:main} we present our mechanism for \SEDP\ and prove our main results. A generalization of our framework to machine learning tasks beyond linear regression is presented in Section~\ref{sec:ext}. 
+In what follows, we describe related work in Section~\ref{sec:related}. We briefly review  experimental design and budget feasible mechanisms in Section~\ref{sec:peel} and define \SEDP\ formally. In Section~\ref{sec:main} we present our mechanism for \SEDP\ and state our main results,  which are proved in Section~\ref{sec:proofs}. A generalization of our framework to machine learning tasks beyond linear regression is presented in Section~\ref{sec:ext}. 
 
 \junk{
 
diff --git a/notes.bib b/notes.bib
index ef54082..125dc6a 100644
--- a/notes.bib
+++ b/notes.bib
@@ -619,3 +619,14 @@ year = "2011"
   bibsource = {DBLP, http://dblp.uni-trier.de}
 }
 
+
+@inproceedings{singerposted,
+ author = {Badanidiyuru, Ashwinkumar and Kleinberg, Robert and Singer, Yaron},
+ title = {Learning on a budget: posted price mechanisms for online procurement},
+ booktitle = {Proceedings of the 13th ACM Conference on Electronic Commerce},
+ series = {EC '12},
+ year = {2012},
+ pages = {128--145},
+} 
+
+
diff --git a/paper.tex b/paper.tex
index 90afeaa..c42b342 100644
--- a/paper.tex
+++ b/paper.tex
@@ -35,9 +35,9 @@ S. Muthukrishnan \affil{Rutgers University, Microsoft Research}}
 \input{problem}
 \section{Mechanism for \SEDP{}}
 \input{main}
-\section{Proofs}
+\section{Proofs}\label{sec:proofs}
 \input{proofs}
-\section{Extension to Other Problems}\label{sec:ext}
+\section{Extensions}\label{sec:ext}
 \input{general}
 %\section{Conclusion}
 %\input{conclusion}
diff --git a/related.tex b/related.tex
index 5c5357d..ce84d66 100644
--- a/related.tex
+++ b/related.tex
@@ -3,20 +3,20 @@
 
 \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 mechanisms for submodular maximization.
+ 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.
 
-In contrast to the above results, no deterministic, truthful, constant approximation mechanism that runs in polynomial time is presently known for submodular maximization.  However, assuming access to an oracle providing the optimum in the full-information setup, Chen \emph{et al.},~provide a truthful, $8.34$-approximate mechanism; in cases for which the full information problem is NP-hard, as the one we consider here, this mechanism is not poly-time, unless P=NP.  Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. 
+The above approximation guarantees hold \emph{in expectation}: for a given instance, the approximation ratio provided by the mechanism may in fact be unbounded. No deterministic, truthful, constant approximation mechanism that runs in polynomial time is presently known for submodular maximization.  However, assuming access to an oracle providing the optimum in the full-information setup, Chen \emph{et al.},~provide a truthful, $8.34$-approximate mechanism; in cases for which the full information problem is NP-hard, as the one we consider here, this mechanism is not poly-time, unless P=NP.  Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful deterministic mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. 
 
 
 \subsection{Budget Feasible Mechanism Design on Specific Problems}
-Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives under the value query model. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate  mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-mechanisms,singer-influence}. Our results therefore extend the set of problems for which a deterministic, polynomial mechanism is known to include \SEDP.
+Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate  mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-influence}. Our results therefore add \SEDP{} to the set of problems for which a deterministic, polynomial time, constant approximation mechanism is known.
 
 \subsection{Beyond Submodular Objectives}
 Beyond submodular objectives, it is known that no truthful mechanism with approximation ratio smaller than $n^{1/2-\epsilon}$ exists for maximizing  fractionally subadditive functions (a class that includes submodular functions) assuming access to a value query oracle~\cite{singer-mechanisms}. Assuming access to a stronger oracle (the \emph{demand} oracle), there exists
 a truthful, $O(\log^3 n)$-approximate mechanism 
 \cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-approximate mechanism for subadditive maximization 
 \cite{bei2012budget}. Moreover, in a Bayesian setup, assuming a prior distribution among the agent's costs, there exists a truthful mechanism with a 768/512-approximation ratio \cite{bei2012budget}. %(in terms of expectations)
-
+Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}.
 
 
 \subsection{Data Markets}