diff options
| -rw-r--r-- | main.tex | 3 | ||||
| -rw-r--r-- | problem.tex | 11 |
2 files changed, 5 insertions, 9 deletions
@@ -15,7 +15,6 @@ One possible interpretation of \eqref{modified} is that, prior to the auction, t \subsection{Truthful, Constant Approximation Mechanism} - In this section we present a mechanism for \EDP. Previous works on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing auction mechanisms for submodular utility functions \cite{singer-mechanisms, @@ -51,7 +50,7 @@ OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big) \end{lemma} Hence, taking the maximum between the greedy set and the point of maximum value -has an approximation ratio of $\frac{5e}{e-1}$. However, Singer +yields an approximation ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that this approach breaks incentive compatibility and therefore cannot be directly applied to the strategic case. diff --git a/problem.tex b/problem.tex index 2c80d4e..5723581 100644 --- a/problem.tex +++ b/problem.tex @@ -34,8 +34,6 @@ As $\hat{\beta}$ is a multidimensional normal random variable, the $D$-optimalit \subsection{Budget Feasible Mechanism Design} In this paper, we approach the problem of optimal experimental design from the perspective of \emph{a budget feasible reverse auction} \cite{singer-mechanisms}. In particular, we assume that each experiment $i\in \mathcal{N}$ is associated with a cost $c_i$, that the experimenter needs to pay in order to conduct the experiment. The experimenter has a budget $B\in\reals_+$. In the \emph{full information case}, the costs are common knowledge; optimal design in this context amounts to selecting a set $S$ maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq B$. -As in \cite{singer-mechanisms,chen}, we focus in a \emph{strategic scenario}: experiment $i$ corresponds to a \emph{strategic agent}, whose cost $c_i$ is private. For example, each $i$ may correspond to a human participant; the feature vector $x_i$ may correspond to a normalized vector of her age, weight, gender, income, \emph{etc.}, and the measurement $y_i$ may capture some biometric information (\emph{e.g.}, her red cell blood count, a genetic marker, etc.). The cost $c_i$ is the amount the participant deems sufficient to incentivize her participation in the study. - As in \cite{singer-mechanisms,chen}, we focus in a \emph{strategic scenario}: experiment $i$ corresponds to a \emph{strategic agent}, whose cost $c_i$ is private. For example, each $i$ may correspond to a human participant; the @@ -45,7 +43,6 @@ biometric information (\emph{e.g.}, her red cell blood count, a genetic marker, etc.). The cost $c_i$ is the amount the participant deems sufficient to incentivize her participation in the study. - A mechanism $\mathcal{M} = (f,p)$ comprises (a) an \emph{allocation function} $f:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$. The allocation function determines, given the @@ -61,21 +58,21 @@ Furthermore, we want to design a mechanism which is: \item \emph{Truthful.} An agent has no incentive to report a cost $c_i'$ different from his true cost $c_i$. Formally, let us write $(c_i', c_{-i})$ the vector of costs when agent $i$ reports cost $c_i'$ (all the other costs - $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = f(c_i', + $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i', c_{-i})$, then the mechanism is truthful iff (a) $i\notin f(c_i,c_{-i})\implies i\notin f(c_i',c_{-i})$ and (b) $p_i - c_i \geq p_i' - - c_i$ + - c_i$. \item \emph{Budget Feasible.} The sum of the payments should not exceed the budget constraint: \begin{displaymath} - \sum_{i\in\mathcal{N}} p_i \leq B + \sum_{i\in\mathcal{N}} p_i \leq B. \end{displaymath} \item \emph{Approximation ratio.} The value of the allocated set should not be too far from the optimum value of the non-strategic case \eqref{eq:non-strategic}. Formally, there must exist some $\alpha\geq 1$ such that: \begin{displaymath} - OPT(V,\mathcal{N}, B) \leq \alpha V(S) + OPT(V,\mathcal{N}, B) \leq \alpha V(S). \end{displaymath} The approximation ratio captures the \emph{price of truthfulness}: this is what you loose by moving from the non-strategic case to the strategic case |