diff options
| -rw-r--r-- | main.tex | 11 | ||||
| -rw-r--r-- | problem.tex | 67 |
2 files changed, 69 insertions, 9 deletions
@@ -125,12 +125,11 @@ We can now state the main result of this section: \begin{proof} \emph{Truthfulness.} The algorithm only describes the allocation rule. -However, it suffices to prove that the mechanism is monotone, then -Myerson's theorem (see TODO) ensures us that by paying each allocated -user his threshold payment yields a truthful mechanism. The proof of -the monotonicity has already been done in \cite{singer-influence} and -is given here in lemma~\ref{lemma:monotone} below for the sake of -completeness. +However, it suffices to prove that the mechanism is monotone, then Myerson's +theorem (see theorem~\ref{thm:myerson}) ensures us that by paying each +allocated user his threshold payment yields a truthful mechanism. The proof of +the monotonicity has already been done in \cite{singer-influence} and is given +here in lemma~\ref{lemma:monotone} below for the sake of completeness. \emph{Budget feasibility.} Thanks to the analysis of the threshold payment in \cite{chen}, the budget feasibility follows easily. The diff --git a/problem.tex b/problem.tex index 49a861c..a26ae65 100644 --- a/problem.tex +++ b/problem.tex @@ -37,12 +37,73 @@ In this paper, we approach the problem of optimal experimental design from the p As in \cite{singer-mechanisms,chen}, we focus on 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 +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. -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 the set $S\subset \mathcal{N}$ of experiments to be conducted. The payment function returns a vector of payments $[p_i]_{i\in \mathcal{N}}$. As in \cite{singer-mechanisms, chen}, we study mechanisms that are normalized ($i\notin S$ implies $p_i=0$), individually rational ($p_i\geq c_i$) and have no positive transfers $p_i\geq 0$. -TODO: truthful, computationally efficient, budget feasible, approximation to V(S) +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 +vector or costs $[c_i]_{i\in\mathcal{N}}$, the set +$S\subseteq \mathcal{N}$ of experiments to be conducted. The payment function +returns a vector of payments $[p_i]_{i\in \mathcal{N}}$. As in +\cite{singer-mechanisms, chen}, we study mechanisms that are normalized +($i\notin S$ implies $p_i=0$), individually rational ($p_i\geq c_i$) and have +no positive transfers $p_i\geq 0$. + +Furthermore, we want to design a mechanism which is: +\begin{itemize} + \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})$, 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$ + \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 + \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) + \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 + with a truthfulness constraint. + \item \emph{Computationally efficient.} The allocation and payment function + should be computable in polynomial time in the number $|\mathcal{N}|$ of + agents. \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} + +Note that this is a \emph{single parameter} auction: each agent has only one +private value. In this case, Myerson's theorem \cite{myerson} gives +a characterization of truthful mechanisms. + +\begin{theorem}[Myerson \cite{myerson}]\label{thm:myerson} +A normalized mechanism $\mathcal{M} = (f,p)$ for a single parameter auction is +truthful iff: +\begin{itemize} +\item $f$ is \emph{monotone}: for any agent $i$ and $c_i' \leq c_i$, for any +fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in f(c_i, +c_{-i})\implies i\in f(c_i', c_{-i})$. +\item agents are paid their \emph{threshold payments}: agent $i$ receives +$\inf\{c_i: i\in f(c_i, c_{-i})\}$. +\end{itemize} +\end{theorem} -TODO: Myerson's Theorem \begin{comment} \subsection{Experimental Design} |