From f884186cb1e840c7b6abd343978b62cbac206cd8 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Mon, 11 Feb 2013 12:02:10 -0800 Subject: problem --- problem.tex | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'problem.tex') diff --git a/problem.tex b/problem.tex index aaca0cc..536481a 100644 --- a/problem.tex +++ b/problem.tex @@ -138,11 +138,11 @@ 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, 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} $S:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$. Given the -vector or costs $c=[c_i]_{i\in\mathcal{N}}$, the allocation function $S$ determines the set in -$ \mathcal{N}$ of items to be purchased, while the payment function +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}: \begin{itemize} @@ -150,19 +150,19 @@ returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$. \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.}, +\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 agent has no incentive to missreport her true cost. Formally, let $c_{-i}$ + \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(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})$. +\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(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} \end{itemize} -We define the \emph{Strategic} version of \EDP as +We define the \emph{Strategic} version of \EDP{} as \begin{center} \textsc{StrategicExperimentalDesignProblem} (SEDP) %\begin{subequations} @@ -174,7 +174,7 @@ We define the \emph{Strategic} version of \EDP as \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 + \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: @@ -183,7 +183,7 @@ Given that the full information problem \EDP{} is NP-hard, we further seek mecha \end{displaymath} % 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 + \item \emph{Computational Efficiency.} The allocation and payment function 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} -- cgit v1.2.3-70-g09d2