diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 14 |
1 files changed, 14 insertions, 0 deletions
@@ -1,3 +1,17 @@ + +\subsection{D-Optimality Criterion} +\begin{lemma} +For any $M>0$, there is no truthful, budget feasible, individionally rational mechanism for optimal mechanism design with value fuction $V(S) = \det{\T{X_S}X_S}$. +\end{lemma} +\begin{proof} +\input{proof_of_lower_bound1} +\end{proof} + +This motivates us to look at $$V(S) = \log\det(I_d+\T{X_S}X_S).$$ Interesting for many reasons. Experiment with basis points $e_1$,\ldots,$e_d$, already given for free. Connections to Baysian optimal experiment design: we explore this more in Section~\ref{...}. Close to $D$-optimality criterion when number of experiments is large. Important properties $V(\emptyset)=0$, $V$ is submodular, allows us to exploit the arsenal in our disposal to deal with budget feasible mechanism design for submodular functions. + +\subsection{Truthful, Constant Approximation Mechanism} + + In this section we present a mechanism for the problem described in section~\ref{sec:auction}. Previous works on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and desiging auction mechanisms for |