Add the properties we seek for mechanisms. Add Myerson's theorem.

1 files changed, 64 insertions, 3 deletions

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}