diff options
| -rw-r--r-- | definitions.tex | 1 | ||||
| -rw-r--r-- | main.tex | 16 | ||||
| -rw-r--r-- | problem.tex | 156 | ||||
| -rw-r--r-- | related.tex | 2 |
4 files changed, 94 insertions, 81 deletions
diff --git a/definitions.tex b/definitions.tex index effdb4e..25b8729 100644 --- a/definitions.tex +++ b/definitions.tex @@ -24,3 +24,4 @@ \newcommand{\T}[1]{#1^T} \newcommand{\EDP}{EDP} \newcommand{\E}{{\tt E}} +\newcommand{\id}{\mathbbm{1}} @@ -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 a8b89f4..5631f7a 100644 --- a/problem.tex +++ b/problem.tex @@ -1,4 +1,4 @@ -\subsection{Optimal Experimental Design} +\subsection{Experimental Design} The theory of experimental design \cite{pukelsheim2006optimal,atkinson2007optimum} studies how an experimenter should select the parameters of a set of experiments she is about to conduct. In general, the optimality of a particular design depends on the purpose of the experiment, \emph{i.e.}, the quantity the experimenter is trying to learn or the hypothesis she is trying to validate. Due to their ubiquity in statistical analysis, a large literature on the subject focuses on learning \emph{linear models}, whereby the experimenter wishes to fit a linear map to the data she has collected. @@ -8,7 +8,7 @@ More precisely, putting cost considerations aside, suppose that an experimenter \end{align} where $\beta$ a vector in $\reals^d$, commonly referred to as the \emph{model}, and $\varepsilon_i$ (the \emph{measurement noise}) are independent, normally distributed random variables with zero mean and variance $\sigma^2$. -The purpose of these experiments is to allow the experimenter to estimate the model $\beta$. In particular, assuming Gaussian noise, the maximum likelihood estimator of $\beta$ is the \emph{least squares} estimator: for $X_S=[x_i]_{i\in S}\in \reals^{|S|\times d}$ the matrix of experiment features and +The purpose of these experiments is to allow the experimenter to estimate the model $\beta$. In particular, under \eqref{model}, the maximum likelihood estimator of $\beta$ is the \emph{least squares} estimator: for $X_S=[x_i]_{i\in S}\in \reals^{|S|\times d}$ the matrix of experiment features and $y_S=[y_i]_{i\in S}\in\reals^{|S|}$ the observed measurements, \begin{align} \hat{\beta} &=\max_{\beta\in\reals^d}\prob(y_S;\beta) =\argmin_{\beta\in\reals^d } \sum_{i\in S}(\T{\beta}x_i-y_i)^2 \nonumber\\ & = (\T{X_S}X_S)^{-1}X_S^Ty_S\label{leastsquares}\end{align} @@ -20,9 +20,9 @@ the noise terms $\varepsilon_i$). In particular, $\hat{\beta}$ has mean $\beta$ (\emph{i.e.}, it is an \emph{unbiased estimator}) and covariance $(\T{X_S}X_S)^{-1}$. -Let $V:2^\mathcal{N}\to\reals$ be a value function, quantifying how informative a set of experiments $S$ is in estimating $\beta$. The standard optimal experimental design problem amounts to finding a set $S$ that maximizes $V(S)$ subject to the constraint $|S|\leq k$. +Let $V:2^\mathcal{N}\to\reals$ be a \emph{value function}, quantifying how informative a set of experiments $S$ is in estimating $\beta$. The standard optimal experimental design problem amounts to finding a set $S$ that maximizes $V(S)$ subject to the constraint $|S|\leq k$. -A variety of different value functions are used in experimental design\cite{pukelsheim2006optimal}; almost all make use of the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. A value functioned preferred because of its relationship to entropy is the \emph{$D$-optimality criterion}: %which yields the following optimization problem +A variety of different value functions are used in experimental design~\cite{pukelsheim2006optimal}; almost all make use of the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. A value function preferred because of its relationship to entropy is the \emph{$D$-optimality criterion}: %which yields the following optimization problem \begin{align} V(S) &= \frac{1}{2}\log\det \T{X_S}X_S \label{dcrit} %\\ \end{align} @@ -38,97 +38,123 @@ 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 Mechanism Design} -In this paper, we approach the problem of optimal experimental design from the -perspective of \emph{a budget feasible reverse auction} -\cite{singer-mechanisms}. In particular, we assume that each experiment $i\in -\mathcal{N}$ is associated with a cost $c_i$, that the experimenter needs to -pay in order to conduct the experiment. The experimenter has a budget -$B\in\reals_+$. In the \emph{full information case}, the costs are common -knowledge; optimal design in this context amounts to selecting a set $S$ +\subsection{Budget Feasible Reverse Auctions} +A \emph{budget feasible reverse auction} +\cite{singer-mechanisms} comprises a set of items $\mathcal{N}=\{1,\ldots,n\}$ as well as a single buyer. Each item has a cost $c_i\in\reals_+$. Moreover, the buyer has a positive value function $V:2^{\mathcal{N}}\to \reals_+$, as well as a budget $B\in \reals_+$. In the \emph{full information case}, the costs $c_i$ are common +knowledge; the objective of the buyer in this context is to select a set $S$ maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq -B$. We write: +B$.We write: \begin{equation}\label{eq:non-strategic} 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} -the best value we can reach under the budget constraint $B$ when selecting -experiments from the set $\mathcal{N}$. +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.} -As in \cite{singer-mechanisms,chen}, we focus in a \emph{strategic scenario}: -experiment $i$ corresponds to a \emph{strategic agent}, whose cost $c_i$ is -private. For example, each $i$ may correspond to a human participant; the -feature vector $x_i$ may correspond to a normalized vector of her age, weight, -gender, income, \emph{etc.}, and the measurement $y_i$ may capture some -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. - -A mechanism $\mathcal{M} = (f,p)$ comprises (a) an \emph{allocation function} +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} $f:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$. Given the -vector or costs $[c_i]_{i\in\mathcal{N}}$, the allocation function determines the set -$S\subseteq \mathcal{N}$ of experiments to be conducted, while the payment function -returns a vector of payments $[p_i]_{i\in \mathcal{N}}$. As in +vector or costs $c=[c_i]_{i\in\mathcal{N}}$, the allocation function $f$ determines the set in +$ \mathcal{N}$ of items to be purchased, while the payment function +returns a vector of payments $[p_i]_{i\in \mathcal{N}}$. Let $s_i(c) = \id_{i\in f_i(c)}$ be the binary indicator of $i\in f(c)$. As in \cite{singer-mechanisms, chen}, we study mechanisms that are normalized -($i\notin S$ implies $p_i=0$), individually rational ($p_i\geq c_i$) and have -no positive transfers $p_i\geq 0$. +($i\notin f(c)$ implies $p_i(c)=0$), individually rational ($p_i(c)\geq c_i\cdot s_i(c)$) and have +no positive transfers ($p_i(c)\geq 0$). -Moreover, we want to design a mechanism which has the following properties: +In addition to the above, mechanism design in budget feasible reverse auctions seeks mechanisms that have the following properties \cite{singer-mechanisms,chen}: \begin{itemize} - \item \emph{Truthful.} An agent has no incentive to report a cost $c_i'$ - different from his true cost $c_i$. Formally, let us write $(c_i', c_{-i})$ - the vector of costs when agent $i$ reports cost $c_i'$ (all the other costs - $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i', - c_{-i})$, then the mechanism is truthful iff (a) $i\notin - f(c_i,c_{-i})\implies i\notin f(c_i',c_{-i})$ and (b) $p_i - c_i \geq p_i' - - c_i$. - \item \emph{Budget Feasible.} The sum of the payments should not exceed the + \item \emph{Truthfulness.} An agent has no incentive to missreport her true cost. Formally, let $c_{-i}$ + be a vector of costs of all agents except $i$. % $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i', +% c_{-i})$, then the +A mechanism is truthful iff every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$ + $p_i(c_i,c_{-i}) - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s(c_i',c_{-i})\cdot c_i$. + \item \emph{Budget Feasibility.} The sum of the payments should not exceed the budget constraint: \begin{displaymath} \sum_{i\in\mathcal{N}} p_i \leq B. \end{displaymath} \item \emph{Approximation ratio.} The value of the allocated set should not - be too far from the optimum value of the non-strategic case + be too far from the optimum value of the full information case \eqref{eq:non-strategic}. Formally, there must exist some $\alpha\geq 1$ such that: \begin{displaymath} OPT(V,\mathcal{N}, B) \leq \alpha V(S). \end{displaymath} - The approximation ratio captures the \emph{price of truthfulness}: this is - what you loose by moving from the non-strategic case to the strategic case - with a truthfulness constraint. + 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. \item \emph{Computationally efficient.} The allocation and payment function - should be computable in polynomial time in the number $|\mathcal{N}|$ of - agents. \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 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}. \end{itemize} -Note that this is a \emph{single parameter} auction: each agent has only one -private value. In this case, Myerson's theorem \cite{myerson} gives +As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are \emph{single parameter} auctions: each agent has only one +private value. In this case, Myerson's Theorem \cite{myerson} gives a characterization of truthful mechanisms. -\begin{theorem}[Myerson \cite{myerson}]\label{thm:myerson} -A normalized mechanism $\mathcal{M} = (f,p)$ for a single parameter auction is +\begin{lemma}[Myerson \cite{myerson}]\label{thm:myerson} +\sloppy A normalized mechanism $\mathcal{M} = (f,p)$ for a single parameter auction is truthful iff: -\begin{enumerate} -\item $f$ is \emph{monotone}: for any agent $i$ and $c_i' \leq c_i$, for any +%\begin{enumerate} +%\item +(a) $f$ is \emph{monotone}, \emph{i.e.}, for any agent $i$ and $c_i' \leq c_i$, for any fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in f(c_i, -c_{-i})\implies i\in f(c_i', c_{-i})$. -\item agents are paid their \emph{threshold payments}: agent $i$ receives -$\inf\{c_i: i\in f(c_i, c_{-i})\}$. -\end{enumerate} -\end{theorem} +c_{-i})$ implies $i\in f(c_i', c_{-i})$, and (b) +%\item + agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in f(c)$, $p_i(c)=\inf\{c_i': i\in f(c_i', c_{-i})\}$. +%\end{enumerate} +\end{lemma} +\fussy +Myerson's Theorem is particularly useful when designing a budget feasible truthful +mechanism, as it allows us to focus on designing a monotone allocation function. Then, the +mechanism will be truthful as long as we give each agent her threshold payment---the caveat being that the latter need to sum to a value below $B$. + +\subsection{Budget Feasible Experimental Design} +In this paper, we approach the problem of optimal experimental design from the +perspective of a budget feasible reverse auction, as defined above. + In particular, we assume the experimenter has a budget +$B\in\reals_+$ and plays the role of the buyer. +Each experiment $i\in +\mathcal{N}$ corresponds to a strategic agent, whose cost $c_i$ is +private. In order to obtain the measurement $y_i$, the experimenter needs to +pay agent $i$ a price that exceeds her cost. + +For example, each $i$ may correspond to a human participant; the +feature vector $x_i$ may correspond to a normalized vector of her age, weight, +gender, income, \emph{etc.}, and the measurement $y_i$ may capture some +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}. + +\stratis{A potential problem is that all of the above properties hold also for, \emph{e.g.}, $V(S)=\log(1+\det(\T{X_S}X_S))$\ldots} -This theorem is particularly useful when designing a budget feasible truthful -mechanism: we can focus on designing a monotone allocation function. Then, the -mechanism will be truthful as long as we give each agent her threshold payment. -Finally, it suffices to prove that the sum of threshold payments does not -exceed the budget to ensure budget feasibility. \begin{comment} \subsection{Experimental Design} diff --git a/related.tex b/related.tex index c037d86..f2db40e 100644 --- a/related.tex +++ b/related.tex @@ -1,7 +1,7 @@ \subsection{Related work} -Budget feasible mechanism design was originally proposed by Singer \cite{singer-mechanism}. 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. +Budget feasible mechanism design was originally proposed by Singer \cite{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). Chen \emph{et al.}~\cite{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. In contrast to the above results, no 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$-appoximate 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$. Moreover, Chen et al.~prove a $1+\sqrt{2}$ lower bound for truthful mechanisms, improving upon an earlier bound of 2 by Singer \cite{singer-mechanisms}. |