diff options
Diffstat (limited to 'problem.tex')
| -rw-r--r-- | problem.tex | 24 |
1 files changed, 12 insertions, 12 deletions
diff --git a/problem.tex b/problem.tex index 3bdbb94..347bce7 100644 --- a/problem.tex +++ b/problem.tex @@ -138,13 +138,13 @@ We study the strategic case, in wich the costs $c_i$ are {\em not} common knowle -When the experiment subjects are strategic, the experimental design problem becomes a special case of a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}. Formally, given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function} +When the experiment subjects are strategic, the experimental design problem becomes a special case of a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}. Formally, given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function}\footnote{Note that $S$ would be more aptly termed as a \emph{selection} function, as this is a reverse auction, but we retain the term ``allocation'' to align with the familiar term from standard auctions.} $S:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$. Given the vector of costs $c=[c_i]_{i\in\mathcal{N}}$, the allocation function $S$ determines the set in $ \mathcal{N}$ of experiments to be purchased, while the payment function returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$. - Let $s_i(c) = \id_{i\in S(c)}$ be the binary indicator of $i\in S(c)$. Mechanism design in budget feasible reverse auctions seeks mechanisms that have the following properties \cite{singer-mechanisms,chen}: + Let $s_i(c) = \id_{i\in S(c)}$ be the binary indicator of $i\in S(c)$. As usual, we seek mechanisms that have the following properties \cite{singer-mechanisms}: \begin{itemize} \item \emph{Normalization.} Unallocated experiments receive zero payments, \emph{i.e.}, \begin{align}s_i(c)=0\text{ implies }p_i(c)=0.\label{normal}\end{align} @@ -162,16 +162,16 @@ returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$. \begin{align} \sum_{i\in\mathcal{N}} p_i(c) \leq B.\label{budget}\end{align} %\end{displaymath} \end{itemize} -We define the \emph{Strategic} version of \EDP{} as -\begin{center} -\textsc{StrategicExperimentalDesignProblem} (SEDP) -%\begin{subequations} -\begin{align*} -\text{Maximize:}&\quad V(S) = \log\det(I_d+\T{X_{S}}X_{S}) \\ %\label{modified} \\ -\text{subject to:}&\quad \mathcal{M}=(S,p)\text{ satisfies }\eqref{normal}-\eqref{budget} -\end{align*} -%\end{subequations} -\end{center} +%We define the \emph{Strategic} version of \EDP{} as +%\begin{center} +%\textsc{StrategicExperimentalDesignProblem} (SEDP) +%%\begin{subequations} +%\begin{align*} +%\text{Maximize:}&\quad V(S) = \log\det(I_d+\T{X_{S}}X_{S}) \\ %\label{modified} \\ +%\text{subject to:}&\quad \mathcal{M}=(S,p)\text{ satisfies }\eqref{normal}-\eqref{budget} +%\end{align*} +%%\end{subequations} +%\end{center} Given that the full information problem \EDP{} is NP-hard, we further seek mechanisms that have the following two additional properties: \begin{itemize} \item \emph{Approximation Ratio.} The value of the allocated set should not |