diff options
Diffstat (limited to 'problem.tex')
| -rw-r--r-- | problem.tex | 47 |
1 files changed, 15 insertions, 32 deletions
diff --git a/problem.tex b/problem.tex index 6bfac6b..a5db2ac 100644 --- a/problem.tex +++ b/problem.tex @@ -146,22 +146,20 @@ $ \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)$. 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} -\item\emph{Individual Rationality.} Payments for allocated experiments exceed costs, \emph{i.e.}, - \begin{align} p_i(c)\geq c_i\cdot s_i(c).\label{ir}\end{align} -\item \emph{No Positive Transfers.} Payments are non-negative, \emph{i.e.}, -\begin{align}p_i(c)\geq 0\label{pt}.\end{align} - \item \emph{Truthfulness/Incentive Compatibility.} An experiment subject has no incentive to missreport her true cost. Formally, let $c_{-i}$ - be a vector of costs of all agents except $i$. Then, % $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i', -% c_{-i})$, then the -\begin{align} p_i(c_i,c_{-i}) - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s_i(c_i',c_{-i})\cdot c_i, \label{truthful}\end{align} for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$. - \item \emph{Budget Feasibility.} The sum of the payments should not exceed the - budget constraint, \emph{i.e.} - %\begin{displaymath} - \begin{align} \sum_{i\in\mathcal{N}} p_i(c) \leq B.\label{budget}\end{align} - %\end{displaymath} +\item \emph{Normalization.} Unallocated experiments receive zero payments: $s_i(c)=0\text{ implies }p_i(c)=0.\label{normal}$ +\item\emph{Individual Rationality.} Payments for allocated experiments exceed +costs: $p_i(c)\geq c_i\cdot s_i(c).\label{ir}$ +\item \emph{No Positive Transfers.} Payments are non-negative: $p_i(c)\geq 0\label{pt}$. +\item \emph{Truthfulness/Incentive Compatibility.} Reporting her true cost is +a dominant strategy for an experiment subject. Formally, let $c_{-i}$ + be a vector of costs of all agents except $i$. Then, $p_i(c_i,c_{-i}) + - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s_i(c_i',c_{-i})\cdot c_i, + \label{truthful}$ for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$. + \item \emph{Budget Feasibility.} The sum of the payments should not exceed the + budget constraint, \emph{i.e.} $\sum_{i\in\mathcal{N}} p_i(c) \leq + B.\label{budget}$ \end{itemize} + %We define the \emph{Strategic} version of \EDP{} as %\begin{center} %\textsc{StrategicExperimentalDesignProblem} (SEDP) @@ -172,15 +170,13 @@ returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$. %\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 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 \leq \alpha V(S). - \end{displaymath} + such that $OPT \leq \alpha V(S)$. % 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. We stress here that the approximation ratio is defined with respect \emph{to the maximal value in the full information case}. \item \emph{Computational Efficiency.} The allocation and payment function @@ -614,19 +610,6 @@ TODO? Explain what are the points which are the most valuable : points which are aligned along directions where the spread over the already existing points is small. -\subsection{Auction} - -TODO Explain the optimization problem, why it has to be formulated as an auction -problem. Explain the goals: -\begin{itemize} - \item truthful - \item individually rational - \item budget feasible - \item has a good approximation ratio - -TODO Explain what is already known: it is ok when the function is submodular. When -should we introduce the notion of submodularity? -\end{itemize} \end{comment} |