diff options
| -rw-r--r-- | main.tex | 16 | ||||
| -rw-r--r-- | problem.tex | 31 |
2 files changed, 29 insertions, 18 deletions
@@ -1,19 +1,5 @@ -\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 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 $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 study 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. - -\subsection{Truthful, Constant Approximation Mechanism} +%\subsection{Truthful, Constant Approximation Mechanism} In this section we present a mechanism for \EDP. Previous works on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing diff --git a/problem.tex b/problem.tex index 237894e..b8e6af8 100644 --- a/problem.tex +++ b/problem.tex @@ -38,8 +38,9 @@ the uncertainty on $\beta$, as captured by the entropy of its estimator. %\end{align} %There are several reasons -Value function \eqref{dcrit} has several appealing properties. To begin with, it is a submodular set function (see Lemma~\ref{...} and Thm.~\ref{...}). In addition, the maximization of convex relaxations of this function is a well-studied problem \cite{boyd}. Note that \eqref{dcrit} is undefined when $\mathrm{rank}(\T{X_S}X_S)<d$; in this case, we take $V(S)=-\infty$ (so that $V$ takes values in the extended reals). - + Value function \eqref{dcrit} is undefined when $\mathrm{rank}(\T{X_S}X_S)<d$; in this case, we take $V(S)=-\infty$ (so that $V$ takes values in the extended reals). +Note that \eqref{dcrit} is a submodular set function, \emph{i.e.}, +$V(S)+V(T)\geq V(S\cup T)+V(S\cap T)$ for all $S,T\subseteq \mathcal{N}$; it is also monotone, \emph{i.e.}, $V(S)\leq V(T)$ for all $S\subset T$. %In addition, the maximization of convex relaxations of this function is a well-studied problem \cite{boyd}. \subsection{Budget Feasible Reverse Auctions} A \emph{budget feasible reverse auction} @@ -51,7 +52,7 @@ B$.We write: OPT(V,\mathcal{N}, B) = \max_{S\subseteq\mathcal{N}} \left\{V(S) \mid \sum_{i\in S}c_i\leq B\right\} \end{equation} -for the optimal value achievable in the full-information case. \stratis{Should be $OPT(V,c,B)$\ldots better drop the arguments.} +for the optimal value achievable in the full-information case. \stratis{Should be $OPT(V,c,B)$\ldots better drop the arguments here and introduce them wherever necessary.} In the \emph{strategic case}, each items in $\mathcal{N}$ is held by a different strategic agent, whose cost is a-priori private. A \emph{mechanism} $\mathcal{M} = (f,p)$ comprises (a) an \emph{allocation function} @@ -127,6 +128,30 @@ biometric information (\emph{e.g.}, her red cell blood count, a genetic marker, etc.). The cost $c_i$ is the amount the participant deems sufficient to incentivize her participation in the study. Note that, in this setup, the feature vectors $x_i$ are public information that the experimenter can consult prior the experiment design. Moreover, though a participant may lie about her true cost $c_i$, she cannot lie about $x_i$ (\emph{i.e.}, all features are verifiable upon collection) or $y_i$ (\emph{i.e.}, she cannot falsify her measurement). +%\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 one would consider the (equivalent) maximization of $V(S) = \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 $M$-approximate, truthful, budget feasible, individionally rational mechanism for a budget feasible reverse auction 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 study a problem with a modified objective: +\begin{center} +\textsc{ExperimentalDesign} (EDP) +\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 +\end{align}\label{edp} +\end{subequations} +\end{center} 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 orthonormal 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}. + +Note that maximizing \eqref{modified} is equivalent to maximizing \eqref{dcrit} in the full-information case. In particular, $\det(\T{X_S}X_S)> \det(\T{X_{S'}}X_{S'})$ iff $\det(I_d+\T{X_S}X_S)>\det(I_d+\T{X_{S'}}X_{S'})$. In addition, \eqref{edp} (and the equivalent problem with objective \eqref{dcrit}) are NP-hard; to see this, note that \textsc{Knapsack} reduces to EDP with dimension $d=1$ by mapping the weight of each item $w_i$ to an experiment with $x_i=w_i$. Nevertheless, \eqref{modified} is submodular, monotone 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 \cite{chen,singer-mechanisms}. |