From 371631e25306393d16402d4527fcb916694e3f1e Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Wed, 31 Oct 2012 13:04:23 -0700
Subject: minor

---
 main.tex | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 061d5b6..bd57295 100644
--- a/main.tex
+++ b/main.tex
@@ -1,15 +1,15 @@
 
 \subsection{D-Optimality Criterion}
-Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes \eqref{dcrit} within a good approximation ratio. As \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation we consider  the (equivalent) maximization of $V(S) = f(\det\T{X_S}X_S )$, for some increasing, on-to function $f:\reals_+\to\reals_+$. However, the following lower bound implies that such an optimization goal cannot be attained under the costraints of  truthfulness, budget feasibility, and individional rationallity.
+Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes \eqref{dcrit} within a good approximation ratio. As \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation we consider  the (equivalent) maximization of $V(S) = f(\det\T{X_S}X_S )$, for some strictly increasing, on-to function $f:\reals_+\to\reals_+$. However, the following lower bound implies that such an optimization goal cannot be attained under the costraints of  truthfulness, budget feasibility, and individional rationallity.
 
 \begin{lemma}
-For any $M>1$, there is no truthful, budget feasible, individionally rational mechanism for optimal mechanism design with value fuction $V(S) = \det{\T{X_S}X_S}$.
+For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individionally rational mechanism for budget feasible experiment design with value fuction $V(S) = \det{\T{X_S}X_S}$.
 \end{lemma}
 \begin{proof}
 \input{proof_of_lower_bound1}
 \end{proof}
 
-This negative result motivates us to look at the following modified objective:
+This negative result motivates us into looking at the following modified objective:
 \begin{align}V(S) = \log\det(I_d+\T{X_S}X_S), \label{modified}\end{align} where $I_d\in \reals^{d\times d}$ is the identity matrix.
 One possible interpretation of \eqref{modified} is that, prior to the auction, the experimenter has free access to $d$ experiments whose features form an ortho-normal basis in $\reals^d$. However, \eqref{modified} can also be motivated in the context of \emph{Bayesian experimental design} \cite{chaloner1995bayesian}. In short, the objective \eqref{modified} arises naturally when the experimenter retrieves the model $\beta$ through \emph{ridge regression}, rather than the linear regression \eqref{leastsquares} over the observed data; we explore this connection in Section~\ref{sec:bed}. From a practical standpoint, \eqref{modified} is a good approximation of \eqref{dcrit} when the number of experiments is large. Crucially, \eqref{modified} is submodular and satifies $V(\emptyset) = 0$, allowing us to use the extensive machinery for the optimization of submodular functions, as well as recent results in the context of budget feasible auctions. 
 
-- 
cgit v1.2.3-70-g09d2

