diff options
| -rw-r--r-- | main.tex | 6 | ||||
| -rw-r--r-- | proof_of_lower_bound1.tex | 2 |
2 files changed, 4 insertions, 4 deletions
@@ -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. diff --git a/proof_of_lower_bound1.tex b/proof_of_lower_bound1.tex index abef6f7..8a6a2f1 100644 --- a/proof_of_lower_bound1.tex +++ b/proof_of_lower_bound1.tex @@ -1 +1 @@ -Given an $M>1$, consider a scenario with $n=4$ experiments of dimension $d=2$. For $e_1,e_2$ the standard basis vectors in $\reals^2$, let $x_1 = e_1$, $x_2 = e_1$, and $x_3=\delta e_1$, $x_4=\delta e_2$, where $0<\delta<1/(M-1) $. Moreover, assume that $c_1=c_2=0.5+\epsilon$, while $c_3=c_4=\epsilon$, for some small $\epsilon>0$. Suppose, for the sake of contradiction, that there exists a mechanism with approximation ratio $M$. Then, it must include in the solution $S$ at least one of $x_1$ or $x_2$: if not, then $V(S)\leq \delta^2$, while $OPT = (1+\delta)\delta$, a contradiction. Suppose thus that the solution contains $x_1$. By the monotonicity property, if the cost of experiment $x_1$ reduces to $B/2-3\epsilon$, 1 will still be in the solution. By threshold payments, experiment $x_1$ receives in this case a payment that is at least $B/2+\epsilon$. By individual rationality and budget feasibility, $x_2$ cannot be included in the solution, so $V(S)$ is at most $(1+\delta)\delta$. However, the optimal solution includes all experiments, and yields $OPT=(1+\delta)^2$, so the ratio is at least $(1+\delta)/\delta>M$. %\qed +Given an $M>1$, consider a scenario with $n=4$ experiments of dimension $d=2$. For $e_1,e_2$ the standard basis vectors in $\reals^2$, let $x_1 = e_1$, $x_2 = e_1$, and $x_3=\delta e_1$, $x_4=\delta e_2$, where $0<\delta<1/(M-1) $. Moreover, assume that $c_1=c_2=0.5+\epsilon$, while $c_3=c_4=\epsilon$, for some small $\epsilon>0$. Suppose, for the sake of contradiction, that there exists a mechanism with approximation ratio $M$. Then, it must include in the solution $S$ at least one of $x_1$ or $x_2$: if not, then $V(S)\leq \delta^2$, while $OPT = (1+\delta)\delta$, a contradiction. Suppose thus that the solution contains $x_1$. By the monotonicity property, if the cost of experiment $x_1$ reduces to $B/2-3\epsilon$, 1 will still be in the solution. By threshold payments, experiment $x_1$ receives in this case a payment that is at least $B/2+\epsilon$. By individual rationality and budget feasibility, $x_2$ cannot be included in the solution, so $V(S)$ is at most $(1+\delta)\delta$. However, the optimal solution includes all experiments, and yields $OPT=(1+\delta)^2$, a contradiction. %so the ratio is at least $(1+\delta)/\delta>M$. %\qed |